Segmentation
Version détaillée
1
Objectif de la segmentation ?
• Identifier/extraire des objets.
• Séparer/distinguer « Arrière plan »/ « Avant plan ».
• Attention: Objet superposé en couche
• Etiqueter : Attribution d’une nouvelle valeur (étiquette) aux pixels formant un
objet distincts.
Forme du Résultat ?
Contours étiquettes Pseudo couleurs Couleurs moyennes
3
Erreurs fréquentes
Sur-Segmentation
(deux segment de cheveu !!)
contours Sous-Segmentation
(Rivière et Arbre)
BENHAMZA Digital Image Processing 4
Exemple d’application
5
Conditions « d’une bonne segmentation »
• La segmentation doit assurer:
• Complétude
• un pixel appartient à un et Un seul objet/région
• Adjacence
• composants connexe
• Difficulté avec des objets déposée en couche.
• Séparabilité: Les régions sont séparées (pas de pixel en commun)
• Mathématiquement:
• ⋃ 𝑅 = 𝑅.
• 𝑅 𝑒𝑠𝑡 𝑢𝑛 𝑒𝑛𝑠𝑒𝑚𝑏𝑙𝑒 𝑑 é𝑙é𝑚𝑒𝑛𝑡 , 𝑖 = 1,2 … 𝑛.
• 𝑅 ⋂ 𝑅 = ∅ 𝑝𝑜𝑢𝑟 𝑡𝑜𝑢𝑡 𝑖 𝑒𝑡 𝑗, 𝑖 ≠ 𝑗
• 𝑄 𝑅 = TRUE 𝑝𝑜𝑢𝑟 i = 1,2, … n.
• 𝑄(𝑅 ⋃ 𝑅 ) 𝐹𝐴𝐿𝑆𝐸 𝑝𝑜𝑢𝑟 𝑡𝑜𝑢𝑡𝑒𝑠 𝑎𝑑𝑗𝑎𝑐𝑒𝑛𝑐𝑒𝑠 𝑑𝑒 𝑟𝑒𝑔𝑖𝑜𝑛𝑠𝑅 𝑒𝑡 𝑅
6
Segmentation d’image
Segmentation: un problème mal posé:
• Solution non unique
• Qu’est une segmentation idéale? Pas de réponse unique/objectif!
7
Approches ….
• Similarité: partitionne l’image en régions similaire selon des critère
prédéfini (couleur, niveau de gris, texture,…).
• Approche Régions (critère d’homogénéité)
• Discontinuité: Se concentre sur la recherche des changements brutes
(les contours)
• Approches contours
Région Vs Contour
•Approches duales:
1. Une région est délimiter par un contour.
2. Un contour sépare deux régions.
Vue d’ensemble des Techniques de
Segmentation
Seuillage Approche Contour Templatte Matching Approche Région
Derivatives Active contours
Methods
Edge detection
Markovian Structural
+ Texture Approachs
Edge linking Methods
Analysis and
classification
BENHAMZA Digital Image Processing 10
Quels technique préférer/choisir?
• Dépend :
• Nature de l’image (lumière, contours, texture, bruit ...)
• Opérations/traitements post-segmentation
• Compression
• Reconnaissance de Forme, interprétation,…
• Mesures
• Primitives à extraire (lignes, régions, textures, ...)
• Contraintes algorithmique (temps-réel, mémoire, ...)
• Contexte
11
Type d’image!
Facile à segmenter
Difficile à segmenter
12
Seuillage
Global
Adaptative
Optimal
Aussi: Local, Minimisation de variance, Entropique, Classification Bayésienne, Ligne de
Partage des eaux
Pour plus de détail, consulter ce lien
Seuillage
•
•
•Obtenir le Seuil?
1. Sur toute l’image (Seuillage global)
2. localement (Seuillage local ou adaptative)
3. Optimal (Otsu, Kapur)
BENHAMZA Digital Image Processing 14
Seuillage global
Choisir un seuil entre deux pics/maxima
• Identifier 2 maximas
• Prendre une valeur médian entre eux
• Attention de choisir des maxima qui paraissent séparer, mais appartiennes à la même
région (d’un seul maximum donné) en réalité
15
Seuillage global
16
Seuillage global
• Seuillage globale basé sur l’algorithme des k-means
• Choisir un seuil T initial (moyenne, médian, …)
• Obtenir 2 groups de pixels
• G1 if I(x, y) > T and G2 if I(x, y) ≤ T
• Calculer la moyenne de G1 et G2 (m1 and m2)
• Calculer un nouveau seuil T
• T = 0.5 (m1+ m2)
• Répéter jusqu’à T converge/se stabilise
• Ex: après 3 itérations, On trouve T = 125 (initialement T0 était la moyenne)
17
Seuillage global: limitation!
18
Seuillage global: limitation!
• Noise (Gaussian, salt and pepper,…)!
19
Seuillage global: limitation!
• Importance des filtres passe-bas
20
Seuillage global: limitation!
• Bruit Lumineux (ex: Effet d’ombre)!
21
Seuillage Adaptative
• Seuillage Adaptative , quand ? un effet de lumière.
• Echec avec un seuillage global.
• Dans un tel cas:
• Décomposer l’image en petite régions.
• Trouver un seuil adéquat pour chaque sous-région.
• La segmentation finale est l’union de toute les sous-régions.
Seuillage Adaptative: Exemple 1
23
Seuillage Adaptative: Exemple 2
24
Seuillage Adaptative: Exemple 3
25
Seuillage Optimal
•Histogramme considéré comme un mélange de gaussienne
•Optimisation du seuil S par modélisation densités gaussiennes de
probabilités
•Minimisation de l'erreur quadratique moyenne entre l'histogramme et les
densités de probabilités
•Toutes les méthodes peuvent être utilisées : simplexe, Newton, …
26
Seuillage Optimal
• Deux classes («Arrière plan » et « Premier plan »)
• Hypothèses: les deux plans suivent une fonction de densité gaussienne.
• Meilleur seuil= Celui qui minimise l’erreur de classification.
• On supposera:
• Première Gaussienne : Arrière Plan.
• Deuxième Gaussienne: Avant Plan (Ou Objet).
Histogramme réel
𝛿
𝛿 Gray Level
𝜇 𝜇
𝑝 𝑥 = 𝑒 et 𝑝 𝑥 = 𝑒 avec 𝑃 +𝑃 =1
27
Seuillage Optimal
• Pour un seuil S, l’erreur de classification est égale à:
• Erreur Minimum lorsque
• Si = = , alors
BENHAMZA Digital Image Processing 28
Seuillage Otsu
• Hypothèses:
• H1: l'image contient deux classes de pixels - premier plan (PP) et Arrière-plan(AP)
• H2: l'image a un histogramme bimodal affichant deux pics
• Idée: Trouver le seuil, S, tel que la somme pondéré des variance intraclasse (𝜎 , 𝜎 ) soit
minimisées.
• Variance Intraclasse: variance entre individu de même classe.
• Variance Interclasse: variance entre deux ou plusieurs classes.
• min 𝑉𝑎𝑟𝑖𝑎𝑛𝑐𝑒 𝑆 = 𝜎 𝑆 + 𝜎 (𝑆)
• Cela revient à maximiser la variance inter-classes.
Figure par: Par Lucas(CA) — Travail personnel, CC BY-SA 4.0, 29
[Link]
Seuillage Otsu
Histogrammme
10
0 0 1 4 4 5
8
7
0 1 3 4 3 4
6
1 3 4 2 1 3
5
4
4 4 3 1 0 0
3
5 4 2 1 0 0
2
1
5 5 4 3 1 0
0
1 2 3 4 5 6
BENHAMZA Digital Image Processing 30
Seuillage Otsu
• 𝑊𝑒𝑖𝑔ℎ𝑡 𝑊 = = 0,4722
( ∗ ) ( ∗ ) ( ∗ )
• 𝑀𝑒𝑎𝑛 𝜇 = = 0,6471
(( , ) ∗ ) (( , ) ∗ (( , ) ∗ )
• 𝑉𝑎𝑟𝑖𝑎𝑛𝑐𝑒 𝜎 = = 0,4637
• 𝑊𝑒𝑖𝑔ℎ𝑡 𝑊 = = 0,5278
( ∗ ) ( ∗ ) ( ∗ )
• 𝑀𝑒𝑎𝑛 𝜇 = = 3,8947
(( , ) ∗ ) (( , ) ∗ (( , ) ∗ )
• 𝑉𝑎𝑟𝑖𝑎𝑛𝑐𝑒 𝜎 = = 0,5152
BENHAMZA Digital Image Processing 31
Seuillage Otsu
• Variance Intraclasse:
32
Seuille 0 1 2 3 4 5
0 0 1 4 4 5 1 1 1 1 1 1 0 0 1 1 1 1 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0 0 0 1
0 1 3 4 3 4 1 1 1 1 1 1 0 1 1 1 1 1 0 0 1 1 1 1 0 0 1 1 1 1 0 0 0 1 0 1 0 0 0 0 0 0
1 3 4 2 1 3 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 0 1 0 1 1 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0
4 4 3 1 0 0 1 1 1 1 1 1 1 1 1 1 0 0 1 1 1 0 0 0 1 1 1 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0
5 4 2 1 0 0 1 1 1 1 1 1 1 1 1 1 0 0 1 1 1 0 0 0 1 1 0 0 0 0 1 1 0 0 0 0 1 0 0 0 0 0
5 5 4 3 1 0 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 0 0 1 1 1 1 0 0 1 1 1 0 0 0 1 1 0 0 0 0
## ## ## ## ## ##
10 10 10 10 10 10
8 8 8 8 8 8
6 6 6 6 6 6
4 4 4 4 4 4
2 2 2 2 2 2
0 0 0 0 0 0
1 2 3 4 5 6 1 2 3 4 5 6 1 2 3 4 5 6 1 2 3 4 5 6 1 2 3 4 5 6 1 2 3 4 5 6
0 1 2 3 4 5 0 1 2 3 4 5 0 1 2 3 4 5 0 1 2 3 4 5 0 1 2 3 4 5 0 1 2 3 4 5
Coeff, Arrière Plan C_ap = 0 C_ap = 0,222 C_ap = 0,4167 C_ap = 0,4722 C_ap = 0,6389 C_ap = 0,8889
Moyenne, Arrière Plan M_ap = 0 M_ap = 0 M_ap = 0,4667 M_ap = 0,6471 M_ap = 1,2609 M_ap = 2,03,13
Variance, Arrière Plan V_ap = 0 V_ap = 0 V_ap = 0,2489 V_ap = 0,4637 V_ap = 1,4102 V_ap = 2,5303
Coeff, Premier Plan C_pp = 1 C_pp = 0,7778 C_pp = 0,5833 C_pp = 0,5278 C_pp = 0,3611 C_pp = 0,1111
Moyenne, Premier Plan M_pp = 2,3611 M_pp = 2,3611 M_pp = 3,7143 M_pp = 3,8947 M_pp = 4,3077 M_pp = 5
Variance, Premier Plan V_pp = 3,1196 V_pp = 3,1196 V_pp = 0,7755 V_pp = 0,5152 V_pp = 0,213 V_pp = 0
Variance IntraLcasse V_intra = 3,1196 V_intra = 1,5268 V_intra= 0,5561 V_intra= 0,4909 V_intra= 0,9779 V_intra= 2,2491
33
• By a bit of manipulation, you can calculate what is called the between
class variance, which is far quicker to calculate. Luckily, the threshold
with the maximum between class variance also has the minimum
within class variance. So it can also be used for finding the best
threshold and therefore due to being simpler is a much better
approach to use.
34
BENHAMZA Digital Image Processing 35
Formula
BENHAMZA Digital Image Processing 36
Algorithme
BENHAMZA Digital Image Processing 37
38
Seuillage:
•Approprié lorsque
•Les régions sont homogènes
• L’arrière plan et les objets d’avant plan sont bien discernable
•inapproprié lorsque
• Les régions possèdes de grand gradient
• Les régions sont texturés
•Conclusion sur Seuillage:
•Méthode simple
•Allume/Eteint chaque pixel (en espérant séparer l’arrière plan de l’avant
plan)
•N’assure pas l’adjacence des objets
39
Recursive Histogramme Splitting (RHS)
Idée: Si les objets présents dans l’image ont des couleurs bien distinctes et uniformes, ils
vont apparaître comme des pics dans l’histogramme.
Zone « vert »
=> Segmentation dans un espace dérivé de l’image 40
Récursive Histogramme Splitting (RHS)
Chaque pixel est décrit selon certains channels: R,G,B,H,S,V,…
=> L’algorithme travaille sur plusieurs histogrammes, un par channel
MAX
HR HG HB
…
voisinage
Réinjection des
régions de taille Retroprojection de
Image initiale suffisante la fenêtre de
l’histogramme
Suppression
de la région
extraite
Récursive Histogramme Splitting (RHS)
• Avantage
• Méthode rapide.
• Peu sensible au bruit.
• Inconvénients:
• Méthode globale: aucune exploitation de e l’information de proximité; qui
permet l’utilisation de seuils variables locaux.
• Deux objets ayant une même couleur? Seront considérer comme un même
objet !! Remède : Croissance de régions.
BENHAMZA Digital Image Processing 42
Approches basé-Continuité
Ascendante (Croissance Région,… –fusion-)
Descendante (Quadtree,… -division-)
Hybride (division-fusion)
BENHAMZA Digital Image Processing 43
Croissance de Région
BENHAMZA Digital Image Processing 44
Croissance de région
45
Croissance de région
• Regroupement des pixels selon des critère d’homogénéité
• Caractéristiques (features): Niveau de gris, couleur, texture, position, mouvement…
• Classé parmi les Méthodes ascendante (Bottom-up)
• Image bruité: Segmentation contour trouve des difficulté -> la segmentation par
similarité est plus adapté/robuste.
• Choisir un/plusieurs pixel(s) d’amorçage (graine(s))
• … ou même une petite région carrément
• Identifier les pixels de voisinage.
• Décider de les joindre à la Région ou pas.
• Recommencer, jusqu’à ce que la région ne croît plus.
46
Croissance de région
• Critère de croissance:
• Homogénéité
• Connexité/Adjacence
• Exemple de critère d’homogénéité:
• seuil
•
•
• Un pixel P est intégré à R si
• Ses caractéristiques (local, ou régional) sont proches de ceux de R
• P est connexe à R.
BENHAMZA Digital Image Processing 47
Croissance de région
48
Croissance de région
• Avantage
• Conceptuellement Simple
• ~Rapide !
• Exploite bien l’information Multi spectrale
• Inconvénient
• Segmentation par approche locale (on préfère une vision globale)
• Problème du gradient
• Risque de trouver un chemin de petit gradient pour n’importe quel deux points de
caractéristique différentes
• Sensible au bruit, … instable! ..
49
Exemple:
• Segmenter l’image suivante. Le pixel « graine » est le centre de
l’image. Critère d’homogénéité: |I(x,y)-G|<5
10 10 10 10 10 10 10
10 10 10 69 70 10 10
59 10 60 64 59 56 60
10 59 10 60 70 10 62
10 60 59 65 67 10 65
10 10 10 10 10 10 10
10 10 10 10 10 10 10
50
Segmentation par Division (Split & Merge)
• -> ex: Seuil = 100%
BENHAMZA Digital Image Processing 51
Segmentation par Division (Split & Merge)
• Principe de « Division »
• Définir un critère d’homogénéité
• Vérification du critère sur l’image
• Si le critère est valide alors (fin de segmentation)
• Sinon, découper l’image en zones plus petites (ex: 4 régions) et relancer la méthode sur
les nouvelles zones
• Arrêt lorsqu’il toutes les nouvelles zones vérifies leur critère d’homogénéité
• Pas de régions non similaires
• Les régions est réduite au pixel !!
BENHAMZA Digital Image Processing 52
BENHAMZA Digital Image Processing 53
Construction du RAG
Région Adjaency Graph
L’image est stockée dans un arbre (RAG).
Initialement, arbre racine = image complète
• Le RAG connecte les régions adjacentes
• Arrêtes = mesures de différence d’homogeneite
BENHAMZA Digital Image Processing 54
Approche basé-Discontinuité
Filtre Passe Haut
Contour
Link
BENHAMZA Digital Image Processing 55
Type de discontinuité
1. Point
2. Ligne –Cercle- Courbe (paramétrique)!-
3. Contour
• Besoin de filtre passe haut!
BENHAMZA Digital Image Processing 56
Détecteur de Point (isolé):
• Le “Point” isolé => l’amplitude du Laplacian dépasse un seuil: ex |R| >T.
Détecteurs de Lignes
R1 R2 R3 R4
• Que détecte chacun de ces Masques?
• Pour un pixel P, comment savoir sur quelle ligne il se trouve?
• Comment les appliquer/exploiter?
• Proposer un script.
58
Détecteurs de Lignes
Détection de Contour
• Revoir le chapitre sur Filtre passe Haut.
• Un bord est un concept "local", tandis qu'une frontière de région, en raison
de la façon dont elle est définie, est une idée plus globale.
Contour ?
61
62
Contour: Dérivé 1ière et 2nd
63
Contour: Dérivé 1ière et 2nd
64
Contour: Dérivé 1ière et 2nd
1. La dérivée première produit (généralement) des bords plus épais
dans une image.
2. La dérivée seconde a une réponse plus forte aux détails fins
• lignes minces, les points isolés et le bruit.
3. La dérivée seconde produit une réponse à double bordure aux
contour de type « rampe » et « pas ».
4. Le signe de la seconde dérivée peut être utilisé pour déterminer si
une transition dans un bord est de clair à foncé ou de foncé à clair.
65
Contour: Impact du bruit (gaussien)!
• Image avec profile horizontal de type rampe.
• Lignes: Corruption avec Bruit Gaussian /sigma={0,0.1,1,10}
• Colonne 1: image et profil
• Colonne 2: 1ière dérivé
• Colonne 3: 2nd dérivé
66
Détection de Contour
• Opérateur Gradient
Gx x
f f
G y
y
f G G 2
x y
2 1/ 2
for 3 3 mask
Gx (z 7 z8 z9 ) (z1 z2 z3 )
Gy (z 3 z6 z9 ) (z1 z4 z7 )
67
Détection de Contour (sans lissage)
68
Détection de Contour (après lissage)
69
Détéction de contour (Horizental)
• Detecteur Diagonale:
1. Prewitt D.
2. Sobel
70
Détection de Contour (Diagonal)
71
Détection de Contour (Après seuillage)
72
Détection de contour
La 2nd dérivé: Laplacian
BENHAMZA Digital Image Processing
Détection de contour
Laplacian du Gaussian (LoG)
75
Laplacian du Gaussian (LoG)
76
Transformé de Hough
77
Transformé de Hough
78
Transformé de Hough
79
Transformé de Hough
Evaluation de la segmentation
1. Précision et rappel
2. F-mesure
3. Indice de Jaccard
4. Distance euclidienne
5. Indice de Dice
BENHAMZA Digital Image Processing 81
Méthode Avancée de Segmentation
• Semi-automatique
• Apprentissage Profond
• Multi-modale
BENHAMZA Digital Image Processing 82