Analyse d’images

– Segmentation –
Définitions Seuillage Méthodes basées région Autres méthodes Evaluation

Bibliographie

Ouvrages :
→ Digital Image Processing, 3rd Ed., chapter 10 ”Image segmentation”, Rafael C.
Gonzalez and Richard E. Woods, Prentice Hall, 2008.

Cours :
→ Vincent Mazet, cours ”Outils fondamentaux pour le traitement d’image”,
http ://[Link]/mazet/ofti
→ Vincent Noblet, cours ”Traitement d’images” TICS2A,
http ://[Link]/fr/[Link]/Traitement d’images TICS2A

2/53
Définitions Seuillage Méthodes basées région Autres méthodes Evaluation

Plan du chapitre

1. Définitions
1.1 Segmentation
1.2 Relations entre les pixels
1.3 Intérêt de la segmentation

2. Segmentation par seuillage

3. Méthodes basées région

4. Autres méthodes

5. Critères d’évaluation de la segmentation

2/53
Définitions Seuillage Méthodes basées région Autres méthodes Evaluation

Qu’est-ce que la segmentation ?

Définition
Une segmentation d’image est une partition de l’image en ensembles de pixels
homogènes (selon un critère pré-défini).

3/53
Définitions Seuillage Méthodes basées région Autres méthodes Evaluation

Qu’est-ce que la segmentation ?

Définition
Une segmentation d’image est une partition de l’image en ensembles de pixels
homogènes (selon un critère pré-défini).

Propriétés :
→ La segmentation n’est pas unique (algorithmes, critère d’homogénéité,
initialisation, etc)
→ Partition de l’image = ensemble de régions non vides, deux à deux disjointes qui
recouvrent l’intégralité de l’image.

Image originale Segmentation Segmentation

à 3 classes à 2 classes

3/53
Définitions Seuillage Méthodes basées région Autres méthodes Evaluation

Qu’est-ce que la segmentation ?

Définition
Une segmentation d’image est une partition de l’image en ensembles de pixels
homogènes (selon un critère pré-défini).

Propriétés :
→ La segmentation n’est pas unique (algorithmes, critère d’homogénéité,
initialisation, etc)
→ Partition de l’image = ensemble de régions non vides, deux à deux disjointes qui
recouvrent l’intégralité de l’image.

Image originale Segmentation Segmentation

à 3 classes à 2 classes

→ Segmentation d’une image = représentation haut niveau.

3/53
Définitions Seuillage Méthodes basées région Autres méthodes Evaluation

Critère d’homogénéité

Segmentation par niveaux de gris :

→ Utilisation de l’histogramme

4/53
Définitions Seuillage Méthodes basées région Autres méthodes Evaluation

Critère d’homogénéité

Segmentation par couleurs :

→ Utilisation des informations des 3 images R, G, B.

5/53
Définitions Seuillage Méthodes basées région Autres méthodes Evaluation

Critère d’homogénéité

Segmentation par texture :

Image aérienne

→ Utilisation du contenu fréquentiel de

l’image.

6/53
Définitions Seuillage Méthodes basées région Autres méthodes Evaluation

Critère d’homogénéité

Segmentation par contours :

→ Approche frontière : recherche des pixels dissemblables → contours entre les

zones homogènes.

7/53
Définitions Seuillage Méthodes basées région Autres méthodes Evaluation

Relations entre les pixels

Voisinage
Le pixel p de coordonnées (i, j) a quatre voisins horizontaux et verticaux :

(i − 1, j), (i + 1, j), (i, j − 1), (i, j + 1)

Cet ensemble est appelé le 4-voisinage de p.

On appelle 8-voisinage de p l’ensemble de pixels constitué du 4-voisinage et des pixels
voisins dans la diagonale :

(i − 1, j − 1), (i − 1, j + 1), (i + 1, j − 1), (i + 1, j + 1)

i,j i,j

4-voisinage 8-voisinage

8/53
Définitions Seuillage Méthodes basées région Autres méthodes Evaluation

Relations entre les pixels

Adjacence
Soit V un ensemble de valeurs d’intensité. Les pixels p et q à valeur dans V sont dits
4-adjacents (resp. 8-adjacents) si q appartient au 4-voisinage (resp. 8-voisinage) de p.

Chemin
On appelle chemin un ensemble de pixels

(i0 , j0 ), (i1 , j1 ), . . . , (in , jn )

tels que pour tout k = 1, . . . , n, (ik−1 , jk−1 ) et (ik , jk ) sont adjacents. On note n la
longueur du chemin.
Si (i0 , j0 ) = (in , jn ) on dira que le chemin est fermé.

Application : p q r
→ quels pixels sont adjacents dans V = {0} (pixels noirs) ? s t u
→ quels chemins possibles dans V ?
v w x

9/53
Définitions Seuillage Méthodes basées région Autres méthodes Evaluation

Relations entre les pixels

Pixels connectés
Soit S un ensemble de pixels. Deux pixels p et q sont dit connectés dans S s’il existe
un chemin les reliant constitué uniquement de pixels de S.

p q r
Application :
→ s et u sont-ils connectés ? s t u
v w x

10/53
Définitions Seuillage Méthodes basées région Autres méthodes Evaluation

Relations entre les pixels

Pixels connectés
Soit S un ensemble de pixels. Deux pixels p et q sont dit connectés dans S s’il existe
un chemin les reliant constitué uniquement de pixels de S.

p q r
Application :
→ s et u sont-ils connectés ? s t u
v w x

Régions
On appelle région ou ensemble connecté tout sous-ensemble de pixels connectés dans
l’image.

R1 R1

R2 R3 R2 R3
R4

3 régions 4 régions
(pas de connexion entre R4 et R2)
10/53
Définitions Seuillage Méthodes basées région Autres méthodes Evaluation

Intérêt de la segmentation : classification

La segmentation sert de base à la classification des régions de l’image

Segmentation pour la classification d’une région agricole. c INRIA - Projet Ariana

11/53
Définitions Seuillage Méthodes basées région Autres méthodes Evaluation

Intérêt de la segmentation : imagerie médicale

Estimation de la taille des lésions dans le cerveau

12/53
Définitions Seuillage Méthodes basées région Autres méthodes Evaluation

Intérêt de la segmentation : incrustation vidéo

Exemple basé sur la segmentation couleur (fond vert)

13/53
Définitions Seuillage Méthodes basées région Autres méthodes Evaluation

Intérêt de la segmentation : incrustation vidéo

Importance de faire une bonne segmentation :

→ mauvaise segmentation de l’image sur fond vert = problème d’incrustation de la

vidéo.

14/53
Définitions Seuillage Méthodes basées région Autres méthodes Evaluation

Plan du chapitre

1. Définitions

2. Segmentation par seuillage

2.1 Binarisation
2.2 Choix du seuil
2.3 Seuillage automatique
2.4 Méthode de Otsu
2.5 Seuillage multiple
2.6 Cas problématiques et prétraitement des données
2.7 Méthodes de clustering

3. Méthodes basées région

4. Autres méthodes

5. Critères d’évaluation de la segmentation

14/53
Définitions Seuillage Méthodes basées région Autres méthodes Evaluation

Segmentation à deux classes d’une image en niveaux de gris

Segmentation pixels clairs vs. pixels foncés → binarisation de l’image

15/53
Définitions Seuillage Méthodes basées région Autres méthodes Evaluation

Segmentation à deux classes d’une image en niveaux de gris

Segmentation par seuillage :


 1 (blanc) si I (i, j) > S
Iseg (i, j) =
0 (noir) si I (i, j) < S


où S est le seuil (niveau de gris).

Image I Image Iseg

16/53
Définitions Seuillage Méthodes basées région Autres méthodes Evaluation

Segmentation à deux classes d’une image en niveaux de gris

Segmentation par seuillage :


 1 (blanc) si I (i, j) > S
Iseg (i, j) =
0 (noir) si I (i, j) < S


où S est le seuil (niveau de gris).

Image I Image Iseg

Comment choisir le seuil S ?

16/53
Définitions Seuillage Méthodes basées région Autres méthodes Evaluation

Choix de seuil

Image originale (256 niveaux de gris) Seuil à 150

Seuil à 70 Seuil à 220

17/53
Définitions Seuillage Méthodes basées région Autres méthodes Evaluation

Choix de seuil : analyse de l’histogramme

→ Dans certains cas, le choix du seuil est facile :

18/53
Définitions Seuillage Méthodes basées région Autres méthodes Evaluation

Choix de seuil : analyse de l’histogramme

→ Dans d’autres cas, le choix du seuil est moins évident :

19/53
Définitions Seuillage Méthodes basées région Autres méthodes Evaluation

Choix de seuil : analyse de l’histogramme

→ Dans d’autres cas, le choix du seuil est moins évident :

19/53
Définitions Seuillage Méthodes basées région Autres méthodes Evaluation

Choix de seuil : analyse de l’histogramme

→ Dans d’autres cas, le choix du seuil est moins évident :

19/53
Définitions Seuillage Méthodes basées région Autres méthodes Evaluation

Seuillage automatique

Algorithme :
1. Calcul de l’histogramme de l’image.
2. Sélectionner un seuil initial T0 .
3. Calculer des intensités moyennes m1 et m2 des groupes G1 et G2 .
4. Calcul du nouveau seuil T = (m1 + m2)/2.
5. Continuer jusqu’à ce que les variations de T soient inférieures à  (défini par
l’utilisateur).

Histogramme à 256 classes

·105

1
G1 G2
0.5

0
0 50 100 150 200 250

T0

20/53
Définitions Seuillage Méthodes basées région Autres méthodes Evaluation

Méthode de Otsu

2
Principe : Trouver le seuil qui minimise la variance intra-classe pondérée σw
(raffinement de la méthode du seuillage automatique).
Variance intra-classe :
2
σw (T ) = q1 (T )σ12 (T ) + q2 (T )σ22 (T )
Histogramme à 256 classes
·105

Probabilité de chaque classe :

1
K
G1 G2 T
X 2X −1
q1 (T ) = p(r ) et q2 (T ) = p(r )
0.5 r =0 r =T +1

avec
0 h(r )
0 50 100 150 200 250 p(r ) = la probabilité de r
N ×M
T
h : l’histogramme de l’image

21/53
Définitions Seuillage Méthodes basées région Autres méthodes Evaluation

Méthode de Otsu

Moyennes :
K
T 2X −1
X r × p(r ) r × p(r )
m1 (T ) = et m2 (T ) =
r =0
q1 (T ) r =T +1
q2 (T )

Variances :
K
T 2X −1
X p(r ) p(r )
σ12 (T ) = (r − m1 (T ))2 et σ22 (T ) = (r − m2 (T ))2
r =0
q1 (T ) r =T +1
q2 (T )

Implémentation de la méthode : Calculer pour tous les seuils T possibles

(T = 0, . . . , 2K − 1) la variance intra-classe pondérée σw
2 et retenir le seuil T qui

minimise σw 2.

22/53
Définitions Seuillage Méthodes basées région Autres méthodes Evaluation

Méthode de Otsu

A noter : la variance de l’image σ 2 s’écrit :

σ 2 = σw
2 2
+ σ1,2

2 est la variance inter-classe.

où σ1,2

23/53
Définitions Seuillage Méthodes basées région Autres méthodes Evaluation

Méthode de Otsu

A noter : la variance de l’image σ 2 s’écrit :

σ 2 = σw
2 2
+ σ1,2

2 est la variance inter-classe.

où σ1,2

On en déduit :
2 est équivalent à maximiser σ 2 .
→ Le problème initial qui consiste à minimiser σw 1,2

23/53
Définitions Seuillage Méthodes basées région Autres méthodes Evaluation

Méthode de Otsu

A noter : la variance de l’image σ 2 s’écrit :

σ 2 = σw
2 2
+ σ1,2

2 est la variance inter-classe.

où σ1,2

On en déduit :
2 est équivalent à maximiser σ 2 .
→ Le problème initial qui consiste à minimiser σw 1,2
→ C’est-à-dire que construire deux groupes de pixels qui se ressemblent ...

23/53
Définitions Seuillage Méthodes basées région Autres méthodes Evaluation

Méthode de Otsu

A noter : la variance de l’image σ 2 s’écrit :

σ 2 = σw
2 2
+ σ1,2

2 est la variance inter-classe.

où σ1,2

On en déduit :
2 est équivalent à maximiser σ 2 .
→ Le problème initial qui consiste à minimiser σw 1,2
→ C’est-à-dire que construire deux groupes de pixels qui se ressemblent ...
→ ... revient à construire deux groupes très dissemblables de pixels.

23/53
Définitions Seuillage Méthodes basées région Autres méthodes Evaluation

Seuillage multiple

→ Plusieurs modes visibles sur l’histogramme.

→ Seuillage à plusieurs classes :

 r ∈ [0, T1 ]
 r ∈]T1 , T2 ]

 r ∈]T2 , 2K − 1]

24/53
Définitions Seuillage Méthodes basées région Autres méthodes Evaluation

Cas problématiques : défaut d’éclairage

Varia(on d’illumina(on
J

Es(ma(on de la varia(on d’illumina(on g

F • Modèle paramétrique es(mé de
sorte
La que l’histogramme
variation soit plus
d’illumination ne permet pas
« piqué
de » correctement l’image. Plusieurs
seuiller
G solutions sont possibles :
I = F/g
→ Le défaut d’éclairage G est connu, on
g utilise un modèle paramétrique pour
le décrire et on corrige l’image avant
le ou
seuillage :

∀(i, j) : I (i, j) = J(i, j)/G (i, j)

I
Seuillage adapta(f

25/53
Définitions Seuillage Méthodes basées région Autres méthodes Evaluation

Cas problématiques : défaut d’écairage

→ Le défaut d’éclairage G est inconnu : on peut utiliser un seuillage local.

Digital Image Processing, Gonzalez & Woods

26/53
Effet du bruit sur l’histogramme
Définitions Seuillage

Cas problématiques : bruit

Méthodes basées région Autres méthodes Evaluation

Ajout du bruit sur l’image ⇒ convolution de l’histogramme de l’image par une

gaussienne (histogramme du bruit).
jout d’un bruit gaussien sur l’image => convolu(on de l’histogramme par une gaus
Soient X et n deux variables aléatoires indépendantes :

oient X et n deuxY variables

=X +n ⇒ aléatoires
fY (u) = (fX ∗ fnindépendantes
)(u)
27/53
Définitions Seuillage Méthodes basées région Autres méthodes Evaluation

Cas problématiques : effet du bruit sur l’histogramme

Solutions possibles :

→ Filtrer l’image initiale :

• filtre gaussien,
• filtre médian,
• filtre moyenneur,
• méthode de débruitage

28/53
Définitions Seuillage Méthodes basées région Autres méthodes Evaluation

Cas problématiques : effet du bruit sur l’histogramme

Solutions possibles :

→ Filtrer l’image initiale :

• filtre gaussien,
• filtre médian,
• filtre moyenneur,
• méthode de débruitage

→ Filtrer l’image seuillée :

• opérateurs morphologiques (cf cours suivant),
• filtre médian

28/53
Définitions Seuillage Méthodes basées région Autres méthodes Evaluation

Cas problématiques : effet du bruit sur l’histogramme

Solutions possibles :

→ Filtrer l’image initiale :

• filtre gaussien,
• filtre médian,
• filtre moyenneur,
• méthode de débruitage

→ Filtrer l’image seuillée :

• opérateurs morphologiques (cf cours suivant),
• filtre médian

→ Incorporer de l’information spatiale dans la méthode de segmentation.

28/53
Définitions Seuillage Méthodes basées région Autres méthodes Evaluation

Méthodes de clustering – K-moyennes

Extension du seuillage d’histogramme aux images couleurs :

→ Un pixel est maintenant représenté par un vecteur (intensités R,G et B)
contrairement aux images en niveaux de gris (un pixel = un scalaire).
G

B
→ La représentation de l’image par son histogramme n’est plus possible.
→ Principe des méthodes de clustering : regrouper les vecteurs en groupes
homogènes.

29/53
Définitions Seuillage Méthodes basées région Autres méthodes Evaluation

Méthodes de clustering – K-moyennes

Algorithme des K-moyennes :

→ Partitionnement aléatoire des points en K clusters.

Exemple :

partition intiale

30/53
Définitions Seuillage Méthodes basées région Autres méthodes Evaluation

Méthodes de clustering – K-moyennes

Algorithme des K-moyennes :

→ Partitionnement aléatoire des points en K clusters.
→ Calcul du centroı̈de de chacun des clusters.

Exemple :

x partition intiale

30/53
Définitions Seuillage Méthodes basées région Autres méthodes Evaluation

Méthodes de clustering – K-moyennes

Algorithme des K-moyennes :

→ Partitionnement aléatoire des points en K clusters.
→ Calcul du centroı̈de de chacun des clusters.
→ Pour chaque point :
• Calcul de la distance du point au centroı̈de de chaque cluster.
• Affectation du point au cluster le plus proche.

Exemple :

x partition intiale, i= 0

30/53
Définitions Seuillage Méthodes basées région Autres méthodes Evaluation

Méthodes de clustering – K-moyennes

Algorithme des K-moyennes :

→ Partitionnement aléatoire des points en K clusters.
→ Calcul du centroı̈de de chacun des clusters.
→ Pour chaque point :
• Calcul de la distance du point au centroı̈de de chaque cluster.
• Affectation du point au cluster le plus proche.
→ Calcul des centroı̈des des nouveaux clusters formés.

Exemple :

x
nouvelle partition, i=1

30/53
Définitions Seuillage Méthodes basées région Autres méthodes Evaluation

Méthodes de clustering – K-moyennes

Algorithme des K-moyennes :

→ Partitionnement aléatoire des points en K clusters.
→ Calcul du centroı̈de de chacun des clusters.
→ Pour chaque point :
• Calcul de la distance du point au centroı̈de de chaque cluster.
• Affectation du point au cluster le plus proche.
→ Calcul des centroı̈des des nouveaux clusters formés.
→ Répéter les étapes 3 et 4 jusqu’à ce qu’il n’y ait plus de changement dans
l’assignement des points (ou des centroı̈des).

Exemple :

x
nouvelle partition, i=1

30/53
Définitions Seuillage Méthodes basées région Autres méthodes Evaluation

Méthodes de clustering – K-moyennes

Algorithme des K-moyennes :

→ Partitionnement aléatoire des points en K clusters.
→ Calcul du centroı̈de de chacun des clusters.
→ Pour chaque point :
• Calcul de la distance du point au centroı̈de de chaque cluster.
• Affectation du point au cluster le plus proche.
→ Calcul des centroı̈des des nouveaux clusters formés.
→ Répéter les étapes 3 et 4 jusqu’à ce qu’il n’y ait plus de changement dans
l’assignement des points (ou des centroı̈des).

Exemple :

x nouvelle partition, i=2

30/53
Définitions Seuillage Méthodes basées région Autres méthodes Evaluation

Méthodes de clustering – K-moyennes

Algorithme des K-moyennes :

→ Partitionnement aléatoire des points en K clusters.
→ Calcul du centroı̈de de chacun des clusters.
→ Pour chaque point :
• Calcul de la distance du point au centroı̈de de chaque cluster.
• Affectation du point au cluster le plus proche.
→ Calcul des centroı̈des des nouveaux clusters formés.
→ Répéter les étapes 3 et 4 jusqu’à ce qu’il n’y ait plus de changement dans
l’assignement des points (ou des centroı̈des).

Exemple :

x nouvelle partition, i=2

30/53
Définitions Seuillage Méthodes basées région Autres méthodes Evaluation

Méthodes de clustering – K-moyennes

K-moyennes

k=3

k=5 k = 10

31/53
Définitions Seuillage Méthodes basées région Autres méthodes Evaluation

Plan du chapitre

1. Définitions

2. Segmentation par seuillage

3. Méthodes basées région

3.1 Croissance de région
3.2 Segmentation par décomposition et regroupement

4. Autres méthodes

5. Critères d’évaluation de la segmentation

31/53
Définitions Seuillage Méthodes basées région Autres méthodes Evaluation

Limitation des méthodes de seuillage

Limite fondamentale des méthodes de seuillage : pas de prise en compte

l’information de voisinage, uniquement l’information de distribution des intensités
(histogramme).

32/53
Définitions Seuillage Méthodes basées région Autres méthodes Evaluation

Limitation des méthodes de seuillage

Limite fondamentale des méthodes de seuillage : pas de prise en compte

l’information de voisinage, uniquement l’information de distribution des intensités
(histogramme).

Avantage des méthodes basées région : agréger des pixels spatialement proches et
ayant des intensités similaires.

32/53
 en compte l’informa(on
Définitions Seuillage de voisinage, uniquement
Méthodes basées région l’informa(on
Autres méthodes de distribu(on
Evaluation

des intensités (histogramme)

Croissance de région
L’idée de base des méthodes de croissance de région est d’agréger des pixels
spa(alement proches et ayant des intensités similaires.

On part des
Principe d’unméthodes
point germe (seed) et de
de croissance l’onrégion
l’étend en ajoutant
: On part d’unles points
point de et
germe la on
l’étend en ajoutant
fron(ères les pixels
qui sa(sfont du voisinage
le critère satisfaisant le critère d’homogénéité.
d’homogénéité

Point germe croissance région finale

33/53
 en compte l’informa(on
Définitions Seuillage de voisinage, uniquement
Méthodes basées région l’informa(on
Autres méthodes de distribu(on
Evaluation

des intensités (histogramme)

Croissance de région
L’idée de base des méthodes de croissance de région est d’agréger des pixels
spa(alement proches et ayant des intensités similaires.

On part des
Principe d’unméthodes
point germe (seed) et de
de croissance l’onrégion
l’étend en ajoutant
: On part d’unles points
point de et
germe la on
l’étend en ajoutant
fron(ères les pixels
qui sa(sfont du voisinage
le critère satisfaisant le critère d’homogénéité.
d’homogénéité

Point germe croissance région finale

Choix du point germe :

→ Manuellement (dans la zone d’intérêt)
→ Automatiquement : en évitant les zones de fort contraste (fort gradient)

33/53
Définitions Seuillage Méthodes basées région Autres méthodes Evaluation

Croissance de région

Critère de similarité : Si un pixel et une région, ou deux régions A et B, sont

considérés comme suffisamment similiaires, ils sont fusionnés, sinon une nouvelle
région est créée.

Exemple de critère pour l’ajout d’un pixel (i, j) dans la région A :

|I (i, j) − µA | < T σA

Choix du seuil T :
→ Valeur de seuil élevé : facile pour de nouveaux pixels d’être acceptés dans la
région.
→ Valeur de seuil faible : difficile pour de nouveaux pixels d’être acceptés dans la
région.

Choix de la connexité : 4-voisinage ou 8-voisinage.

34/53
Définitions Seuillage Méthodes basées région Autres méthodes Evaluation

Croissance de région : mode d’emploi

Définition d’une zone R qui contient la région à extraire et une file FIFO (First In,
First Out) S qui contient les points frontière de R.

Initialisation :
→ R contient le point germe.
→ S contient le voisinage du point germe.

Méthode : On retire p de S
→ Si p est homogène avec R :
• on ajoute p à R,
• on ajoute à S les points du voisinage de p qui ne sont pas dans R et qui ne sont pas
incompatibles.
→ sinon :
• On marque p comme incompatible.
On recommence tant que S n’est pas vide.
Rq : en cas d’utilisation de statistique globale pour le test d’homogénéité, l’ordre de
traitement des pixels peut influencer le résultat final.

35/53
Définitions Seuillage Méthodes basées région Autres méthodes Evaluation

Croissance de région : exemple

Croissance de région
Segmentation des éclairs :

Au moins deux points germes nécessaires

Au moins deux points germes sont nécessaires.

36/53
Définitions Seuillage Méthodes basées région Autres méthodes Evaluation

Croissance de région : exemple

Influence du seuil :

Croissance de région
Croissance de région

T%
tî tî

Influence du seuil
Influence du seuil

37/53
 Définitions Seuillage Méthodes basées région Autres méthodes Evaluation

Croissance de région : exemple

Croissance de région
ion growing : principes Region growing : exemple
Influence du seuil :
pixel un groupe ●Remarques / Questions :
● Comment se comporte la méthode pour

moyenne µR et des gradients petits (régions type

rampe) ?
● Régularité locale n'implique pas
voisins de R qui régularité de la région...
à R, par ex:

«V(x)} < seuil

r des critères
mme par ex :
au moins 3 et
connexe.

2 IAD La croissanceAntoine
de MANZANERA
région –ne
Coursfournit
TERI – Master 2pas une
IAD page 8 partition de l’image, mais permet de page 9

segmenter une ou plusieurs structures d’intérêt via la sélection de points germes

adaptés.

38/53
 Définitions Seuillage Méthodes basées région Autres méthodes Evaluation

Croissance de région : exemple

Croissance de
ion growing : principes
région
Region growing : exemple
Influence du seuil :
pixel un groupe ●Remarques / Questions :
● Ce n'est en soi une méthode de
moyenne µR et segmentation : comment choisir
convenablement les seeds de chaque
région ?
oisins de R qui ● En général, l'ordre dans lequel les régions

à R, par ex: sont construites, mais aussi l'ordre dans

lequel sont ajoutés les pixels dans une
région a une grande influence sur le
«V(x)} < seuil résultat.
● Implémentation : très rapide, si l'on
utilise une structure de donnée adaptée
des critères
(files d'attente).
mme par ex :
au moins 3 et
connexe.

2 IAD Ne fournit
La croissance depas
Antoine une par((on
région
MANZANERAne fournit
– Cours depas
TERI – Master 2l’image,
une
IAD page 8 mais permet
partition de segmenter
de l’image, une ou de page 10
mais permet
plusieurs
segmenter unestructures
ou plusieurs d’intérêt
structures via la d’intérêt
sélec(on via
de points germesdeadaptés
la sélection points germes
adaptés.

38/53
Définitions Seuillage Méthodes basées région Autres méthodes Evaluation

Méthode split and merge

Principe d’une méthode de décomposition/fusion :

→ Partition initiale par divisions successives de chaque région non-uniforme de
l’image.
→ Fusions successives des régions adjacentes satisfaisant un critère d’homogénéité.

39/53
Définitions Seuillage Méthodes basées région Autres méthodes Evaluation

Méthode split and merge

Principe d’une méthode de décomposition/fusion :

→ Partition initiale par divisions successives de chaque région non-uniforme de
l’image.
→ Fusions successives des régions adjacentes satisfaisant un critère d’homogénéité.

Nécessité d’une représentation hiérarchique de l’image !

→ Construction de la représentation hiérarchique lors de l’étape de division (pendant
ou après).
→ Utilisation lors de l’étape de fusion.

39/53
Définitions Seuillage Méthodes basées région Autres méthodes Evaluation

Représentation par arbre

Les représentations en arbre sont utilisées pour créer une représentation de haut
niveau de l’image.

Les arbres définissent un ensemble de régions structurées hiérarchiquement.

40/53
Définitions Seuillage Méthodes basées région Autres méthodes Evaluation

Représentation par arbre : le quad-tree

Le quad-tree est une arborescence dont la racine est l’image entière et donc chaque
noeud possède également quatre fils :
→ l’image est partagée en quatre quadrants récursivement,
→ un quadrant q est partagé en quatre s’il n’est pas décrété homogène : σq2 > T .

41/53
Définitions Seuillage Méthodes basées région Autres méthodes Evaluation

Décomposition par représentation quad-tree

Décomposi(on / fusion Split and merge

ExempleReprésenta)on
:
Split & Merge: Quad-tree split
par quad-tree

Antoine MANZANERA – Cours TERI – Master 2 IAD page 12

42/53
Définitions Seuillage Méthodes basées région Autres méthodes Evaluation

Décomposition par représentation quad-tree

Décomposi(on / fusion Split and merge

ExempleReprésenta)on
:
Split & Merge: Quad-tree split
par quad-tree

Antoine MANZANERA – Cours TERI – Master 2 IAD page 13

42/53
Définitions Seuillage Méthodes basées région Autres méthodes Evaluation

Décomposition par représentation quad-tree

La méthode de décomposition par quad-tree fait apparaı̂tre des régions carrées sur
l’image segmentée.

Le problème majeur de cette structure provient de la rigidité des divisions réalisées sur
l’image, mais cela fournit une partition initiale de l’image.

43/53
Définitions Seuillage Méthodes basées région Autres méthodes Evaluation

Représentation par graphe d’adjacence

Le graphe d’adjacence est une arborescence dont les noeuds sont les régions et les
arcs définissent une relation d’adjacence (proximité spatiale).

R1

R2 R3
R4

Utilisation pour l’étape de fusion :

→ Initialisation : partition de l’image (par exemple avec le quad-tree) et graphe
d’adjacence associé.

→ Modification de la partition initiale en fusionnant les régions adjacentes : pour

chaque sommet R, on cherche s’il existe un sommet R 0 voisin dans le graphe, de
valeur suffisamment proche pour être fusionné avec R (par exemple si
|µR − µR 0 | < seuil).

44/53
Définitions Seuillage Méthodes basées région Autres méthodes Evaluation

Décomposi(on / fusion
Représentation par graphe d’adjacence Split and merge

Split & Merge: [Link]

Représenta)on par graphe d’adjacence & Merge
Exemple :

Antoine MANZANERA – Cours TERI – Master 2 IAD page 16

45/53
Définitions Seuillage Méthodes basées région Autres méthodes Evaluation

Représentation par graphe d’adjacence

Décomposi(on / fusion Split and merge

Split & Merge: [Link]

Représenta)on par graphe d’adjacence & Merge
Exemple :

Antoine MANZANERA – Cours TERI – Master 2 IAD page 17

45/53
Définitions Seuillage Méthodes basées région Autres méthodes Evaluation

Fusion des régions

Résumé de la segmentation par décomposition/fusion :

→ Partition intiale par méthode des quad-tree par exemple.

Décomposi(on / fusion
Décomposi(on
Décomposi(on /
Split and merge
fusion
/ fusion
→ Représentation de l’image segmentée par un graphe d’adjacence. Split and

→ Fusion des zones segmentées adjacentes en fonction d’un critère d’homogénéité.

merge
Split and me

Split & Merge:Split

Représenta)on par quad-tree & Merge:
Quad-tree
Split & split
Représenta)on R.A.G.
Merge: & Merge
R.A.G.
Merge
par graphe
Représenta)on & Merge
Merge
d’adjacence
par graphe d’adjacence

46/53
Définitions Seuillage Méthodes basées région Autres méthodes Evaluation

Plan du chapitre

1. Définitions

2. Segmentation par seuillage

3. Méthodes basées région

4. Autres méthodes
4.1 Quelques méthodes de l’état de l’art
4.2 Ligne de partage des eaux
4.3 Segmentation par contour déformable

5. Critères d’évaluation de la segmentation

46/53
Définitions Seuillage Méthodes basées région Autres méthodes Evaluation

Méthodes basées contour

→ Segmentation par ligne de partage des eaux.

→ Segmentation par contour déformable.
→ Les méthodes de détection de contours peuvent être utilisées → détection de
caractéristiques.

47/53
Définitions Seuillage Méthodes basées région Autres méthodes Evaluation

Segmentation par ligne de partage des eaux

L’idée est de transformée l’image à segmenter par une carte d’élévation (terrain en
3D) où les frontières entre deux régions à segmenter seraient les crêtes et les régions,
les bassins.
→ On utilise en général la norme du gradient de l’image pour la carte d’élévation.

Représentation 3D du gradient
Image à segmenter

Image originale

Gradient de l’image

48/53
Définitions Seuillage Méthodes basées région Autres méthodes Evaluation

Segmentation par ligne de partage des eaux

Principe de la méthode :
→ Construire la carte d’élévation.
→ Remplir progressivement d’eau chaque bassin versant.
→ Lorsque l’eau monte et que deux bassins se rejoignent, la ligne de partage des
eaux est marquée comme frontière.

Illustration sur un signal 1D :

49/53
Définitions Seuillage Méthodes basées région Autres méthodes Evaluation

Segmentation par ligne de partage des eaux

Principe de la méthode :
→ Construire la carte d’élévation.
→ Remplir progressivement d’eau chaque bassin versant.
→ Lorsque l’eau monte et que deux bassins se rejoignent, la ligne de partage des
eaux est marquée comme frontière.

Illustration sur un signal 1D :

Bassins versants

49/53
Définitions Seuillage Méthodes basées région Autres méthodes Evaluation

Segmentation par ligne de partage des eaux

Principe de la méthode :
→ Construire la carte d’élévation.
→ Remplir progressivement d’eau chaque bassin versant.
→ Lorsque l’eau monte et que deux bassins se rejoignent, la ligne de partage des
eaux est marquée comme frontière.

Illustration sur un signal 1D :

49/53
Définitions Seuillage Méthodes basées région Autres méthodes Evaluation

Segmentation par ligne de partage des eaux

Principe de la méthode :
→ Construire la carte d’élévation.
→ Remplir progressivement d’eau chaque bassin versant.
→ Lorsque l’eau monte et que deux bassins se rejoignent, la ligne de partage des
eaux est marquée comme frontière.

Illustration sur un signal 1D :

49/53
Définitions Seuillage Méthodes basées région Autres méthodes Evaluation

Segmentation par ligne de partage des eaux

Principe de la méthode :
→ Construire la carte d’élévation.
→ Remplir progressivement d’eau chaque bassin versant.
→ Lorsque l’eau monte et que deux bassins se rejoignent, la ligne de partage des
eaux est marquée comme frontière.

Illustration sur un signal 1D :

49/53
Définitions Seuillage Méthodes basées région Autres méthodes Evaluation

Segmentation par ligne de partage des eaux

Principe de la méthode :
→ Construire la carte d’élévation.
→ Remplir progressivement d’eau chaque bassin versant.
→ Lorsque l’eau monte et que deux bassins se rejoignent, la ligne de partage des
eaux est marquée comme frontière.

Illustration sur un signal 1D :

frontière

49/53
Définitions Seuillage Méthodes basées région Autres méthodes Evaluation

Segmentation par ligne de partage des eaux

Principe de la méthode :
→ Construire la carte d’élévation.
→ Remplir progressivement d’eau chaque bassin versant.
→ Lorsque l’eau monte et que deux bassins se rejoignent, la ligne de partage des
eaux est marquée comme frontière.

Illustration sur un signal 1D :

frontière

49/53
Définitions Seuillage Méthodes basées région Autres méthodes Evaluation

Segmentation par ligne de partage des eaux

Principe de la méthode :
→ Construire la carte d’élévation.
→ Remplir progressivement d’eau chaque bassin versant.
→ Lorsque l’eau monte et que deux bassins se rejoignent, la ligne de partage des
eaux est marquée comme frontière.

Illustration sur un signal 1D :

frontière

49/53
Définitions Seuillage Méthodes basées région Autres méthodes Evaluation

Segmentation par ligne de partage des eaux

Principe de la méthode :
→ Construire la carte d’élévation.
→ Remplir progressivement d’eau chaque bassin versant.
→ Lorsque l’eau monte et que deux bassins se rejoignent, la ligne de partage des
eaux est marquée comme frontière.

Illustration sur un signal 1D :

Segmentation finale

49/53
Définitions Seuillage Méthodes basées région Autres méthodes Evaluation

Segmentation par ligne de partage des eaux

Implémentation :
→ Calculer le gradient (ou le Laplacien) de l’image.
→ Commencer avec tous les pixels ayant la valeur la faible possible : ceux-ci forment
l’ensemble des bassins versants initiaux.
→ Pour chaque niveau d’intensité r :
• Pour chaque groupe de pixels d’intensité r :
Si adjacent à exactement une région existante, ajouter ces pixels dans cette région.
Sinon, si adjacent à plusieurs régions simultanément, marquer comme ligne de partage des eaux.
Sinon, commencer une nouvelle région.

50/53
Définitions Seuillage Méthodes basées région Autres méthodes Evaluation

Segmentation par ligne de partage des eaux

Implémentation :
→ Calculer le gradient (ou le Laplacien) de l’image.
→ Commencer avec tous les pixels ayant la valeur la faible possible : ceux-ci forment
l’ensemble des bassins versants initiaux.
→ Pour chaque niveau d’intensité r :
• Pour chaque groupe de pixels d’intensité r :
Si adjacent à exactement une région existante, ajouter ces pixels dans cette région.
Sinon, si adjacent à plusieurs régions simultanément, marquer comme ligne de partage des eaux.
Sinon, commencer une nouvelle région.

Limitation : s’il y a beaucoup de minima locaux dans le gradient, cela donne une
sur-segmentation → lissage du gradient avant d’appliquer l’algorithme.

→ Possibilité de choisir manuellement les bassins versants d’intérêt avec des

marqueurs.

50/53
Définitions Seuillage Méthodes basées région Autres méthodes Evaluation

Segmentation par contour déformable

Autres terminologies : Snake, contour actif, etc.

Principe des contours déformables :

→ On se donne un contour initial (modèle) près de l’objet à segmenter.
→ Le but est de faire évoluer le contour pour qu’il adhère au bord de l’objet.
→ La modification du contour se fait de manière itérative de façon à ce qu’il
converge vers les zones de fort gradient (=contour) sous certaines contraintes
(forme, longueur, etc).

Outils utilisés :
→ Contour = chemin fermé = représentation discrète.
→ Définition de fonctions d’énergies interne et externe.
→ Minimisation de la fonction d’énergie.

51/53
Définitions Seuillage Méthodes basées région Autres méthodes Evaluation

Plan du chapitre

1. Définitions

2. Segmentation par seuillage

3. Méthodes basées région

4. Autres méthodes

5. Critères d’évaluation de la segmentation

51/53
Définitions Seuillage Méthodes basées région Autres méthodes Evaluation

Critères d’évaluation de la segmentation

52/53
Définitions Seuillage Méthodes basées région Autres méthodes Evaluation

A suivre ...

Analyse d’image – Morphologie

53/53