08/03/2023
Segmentation
A. B. mars 2023
Introduction
• Segmentation : décomposition d’une image en régions qui ont un
sens ! les “objets” de l’image
• Segmentation = étiquetage des pixels/voxels de l’image
• pixels/voxels de même étiquette = pixels/voxels de même région
1
08/03/2023
Introduction
• Facile pour un être humain : connaissances préalables,
image vue dans sa totalité, déductions (par exemple pour
les frontières cachées)
• Méthodes :
• Approche région : grouper pixels/voxels semblables => régions
homogènes
• Approche frontière : rechercher pixels/voxels dissemblables =>
contours/surfaces entre zones hétérogènes
• Approche hybride : combinaison des deux précédentes
Exemple d’application
• Imagerie médicale
• Reconstruction 3D du cortex cérébral, (Approche contour : modèle
déformable)
Images 3D (3 coupes) Segmentation Reconstruction 3D
2
08/03/2023
Exemple d’application
• Imagerie médicale,
• Localiser les tumeurs et autres pathologies
• Mesurer les volumes de tissus
• Diagnostic, étude de la structure anatomique
• Planification de la chirurgie
• Simulation de chirurgie virtuelle
• Navigation intra-chirurgicale
Exemple d’application
• Recherche d'images basée sur le contenu
David Liu
3
08/03/2023
Exemple d’application
• Détection d'objets
• Détection de piétons, visages, feux de freinage, localisation d'objets dans des
images satellites (routes, forêts, cultures, etc.)
Exemple d’application
• Systèmes de contrôle du trafic
• Vidéosurveillance
• Co-segmentation d'objets vidéo et localisation d'actions
4
08/03/2023
Exemple d’application
https://ultralytics.com/yolov8
Définition
• Segmentation : application de 𝑋 ∈ {1, … , 255} dans un espace
d’étiquettes, généralement L = {1, … , 𝑘}
• Étiqueter == partitionne
• segmentation de 𝑋: 𝑆𝑖 𝑖=1,𝑛 , sous-ensembles de 𝑋 tels que
• 𝑋 = =𝑖ڂ1,𝑛 𝑆𝑖 (partition de 𝑋)
• ∀𝑖 ∈ {1, 𝑛}, 𝑆𝑖 est connexe
• ∀𝑖, 𝑗 ∈ 1, 𝑛 , 𝑆𝑖 adjacent à 𝑆𝑗 et 𝑖 ≠ 𝑗 ⇒ 𝑆𝑖 ∩ 𝑆𝑗 = ∅
5
08/03/2023
Segmentation : approches région
• Segmentation par seuillage
• But : affecter chaque pixel d’une image en
niveaux de gris à une classe. classes = intervalles
de niveaux de gris
• Principe :
• extraire des seuils à partir de l’histogramme
(image/région)
• classification d’un pixel p par comparaison de 𝐼(𝑝)
aux seuils
Segmentation par seuillage
• histogramme de 𝐼 représente la distribution des valeurs dans la
région 𝑅.
• Exemple : objet assez uniforme alors histogramme approximé par
gaussienne de variance faible
• histogramme bimodal : X possède deux objets de moyennes
différentes
• Seuillage : trouver le(s) seuil(s) qui sépare(nt) au mieux les deux
objets (ou plus).
6
08/03/2023
Segmentation par seuillage
• Devient difficile lorsque les moyennes se rapprochent.
Segmentation par seuillage
• Devient difficile lorsque les moyennes se rapprochent.
7
08/03/2023
Segmentation par seuillage
• pixel : (𝑥; 𝑦),
• niveau de gris : 𝐼(𝑥; 𝑦)
• propriété locale : 𝑃(𝑥; 𝑦)
• seuil utilisé pour classer le pixel (𝑥; 𝑦) ∶ 𝑆(𝑥; 𝑦)
• 3 types de méthodes de seuillage :
• seuillage global : 𝑆(𝑥; 𝑦) = 𝑆(𝐼(𝑥; 𝑦))
• seuillage local : 𝑆(𝑥; 𝑦) = 𝑆(𝐼(𝑥; 𝑦); 𝑃(𝑥; 𝑦))
• seuillage dynamique : 𝑆(𝑥; 𝑦) = 𝑆(𝐼(𝑥; 𝑦); 𝑃(𝑥; 𝑦); 𝑥; 𝑦)
Seuillage global, Binarisation [Otsu79]
• Intuition : trouver le seuil T qui minimise la variance intra-classe du
premier plan et de l'arrière-plan (comme pour k-means)
• De manière équivalente, maximiser la variance entre classes
8
08/03/2023
Seuillage global, Binarisation [Otsu79]
• Algorithme : Recherche du seuil T pour maximiser la variance entre
classes (Utiliser la propriété de récursivité pour balayer T sur
l'histogramme)
T=112
Seuillage global, Binarisation [Otsu79]
T=56
9
08/03/2023
Seuillage global, Binarisation [Otsu79]
Seuillage local? Binarisation
• Faites glisser une fenêtre sur l'image
• Pour chaque position de la fenêtre, décidez si vous devez
effectuer un seuillage
• Le seuillage ne doit pas être effectué dans des zones
uniformes
• Utiliser la variance ou un autre critère approprié
• Zones non uniformes : appliquer la méthode d'Otsu
(basée sur l'histogramme local)
• Zones uniformes : classer la zone entière comme étant
avant-plan ou arrière-plan en fonction de la valeur
moyenne
10
08/03/2023
Seuillage local? Binarisation
Valeur du seuil Résultat
Seuillage local? Binarisation [Sauvola00]
• Intuition : le seuil est adapté au contraste local.
• 𝜇 𝑥, 𝑦 ; 𝜎(𝑥, 𝑦) moyenne et écart type des intensités dans la fenêtre
de calcul. Valeurs standard des paramètres: k = 0:5, R = 128
• Exemple pour k=0.1, 0.2, r = 15 (fenêtre)
11
08/03/2023
Seuillage dynamique, Binarisation [Chow,
Kaneko72]
• Image découpée en blocs
• Calcul d’un seuil pour chaque bloc
:
• l’histogramme du bloc est-il
bimodal ?
• Si oui, le seuil trouvé est affecté au
centre du bloc
• Si non, le seuil prend pour valeur la
moyenne des seuils des blocs
voisins.
• Le seuil de chaque pixel est calculé
par interpolation bilinéaire à
partir des seuils des centres des
blocs voisins.
Clustering
12
08/03/2023
Méthode des k-means : exemple
• Rechercher de 2 classes
Méthode des k-means : exemple
• Clustering de 5000 point générés aléatoirement. Les points noirs
représentent les centres de cluster
13
08/03/2023
Méthode des k-means : exemple
• Image couleur
Méthode des k-means : exemple
• Rechercher 3 classes
14
08/03/2023
Méthode des k-means : exemple
• Rechercher 3 classes
Méthode des k-means : exemple
• Rechercher 3 classes
15
08/03/2023
Clustering Hiérarchique Ascendant (CHA)
• Exemple (Bisson 2001)
• Schéma du milieu : dendrogramme = représentation des fusions successives
• Hauteur d’un cluster dans le dendrogramme = distance entre les 2 clusters avant fusion (sauf
exception avec certaines mesures de similarité)...
Clustering Hiérarchique Ascendant (CHA)
16
08/03/2023
Segmentation : approches région
• Le seuillage est une opération sur les pixels
• Ne produit pas forcement des régions connexes!
• On peut utiliser le seuillage pour les régions, mais il faut ‘nettoyer’ le
résultats obtenu
• Eliminer les pixels, conserver les régions
• Il existe des méthodes de segmentation en régions
• Conservent la connexité entre régions
Split and merge
• Etape de division (split)
• diviser récursivement tout un bloc non-
homogène selon un critère prédéfini
(variance, min,...)
• La division donne 4 sous blocs
• les attributs de chaque sous-bloc sont
recalculés
• Etape de fusion (merge)
• Regrouper les blocs adjacents représentant
des régions homogènes selon un critère
prédéfini
17
08/03/2023
Split and merge
• L’image est stockée dans un arbre
• Au début, arbre racine = image complète
• Récursivement, chaque feuille F est
subdivisée en 4 si elle n’est pas assez
homogène
• les 4 sous-images sont ajoutées en tant que
feuilles de F
• L’algorithme poursuit tant qu’il reste des
feuilles non homogènes à diviser
Split and merge
Image initiale
Split 1
Split 2
Split 3
Clovis Tauber
18
08/03/2023
Split and merge
• Connecter les régions adjacentes homogènes
Croissance de régions
• On débute avec un pixel, et on « ajouter/connecte » les pixels voisins qui
répondent à un critère d'appartenance : Variance faible, seuil, …
• Les pixels initiaux sont appelés « germes », ou semences
• Choix des pixels initiaux automatiques ou semi-automatiques
• La région « grandit » à partir de son germe
• Besoin d’une critère (ou prédicat) pour choisir les pixels à ajouter
19
08/03/2023
Contours actifs
• Principe : utiliser des courbes déformables qui sont attirées par les
formes et contours recherchés dans l’image
Contours actifs : modèle explicite
• Comment modélise-t-on un contour actif ?
P9 P8
P10
P7
P11 P6
P3
P1 P5
P2 P4
Esnake Einterne Eexterne
• Propriétés intrinsèques • Propriétés locales de l’image
• Longueur, courbure… autour du snake Clovis Tauber
20
08/03/2023
Contours actifs : modèle explicite
• Comment évolue un contour actif ?
Comportement dynamique du snake?
Minimiser l’énergie totale (interne + externe)
Calculer les forces à appliquer à chaque point de contrôle de
F E telle sorte que l’énergie soit minimisée
E ( x, y )
Fx x
Fy E ( x, y )
y
Contours actifs : modèle explicite
• Exemples d’énergie EXTERNE (Image):
Zones brillantes ou sombres: Eext I
Eext I
2
Contours en tant que maxima de la norme du gradient:
21
08/03/2023
Contours actifs : modèle explicite
• Avantages:
• Adaptation aux déformations des tissus biologiques
• Adaptation aux différences d’organe entre coupes
• Quelques itérations suffisent
• Désavantages du modèle classique :
• Le contour initial ne peut pas être sélectionné automatiquement (sauf cas simple)
• Le contour initial doit être proche du contour final
• Le modèle classique n’est pas utilisable dans le cas de la présence de texture
• Le modèle classique peut être perturbé en présence de bruit
• La minimisation d'énergie demande l’inversion de matrices de grandes tailles à chaque itération
Ensembles de niveaux (level sets)
• Représentation du contour actif comme la courbe de niveau 0 d’une
fonction de degré supérieur
• Déplacement à une vitesse F suivant une direction normale au
contour
z
F
=PHI(x,y,t)
y
Dehors y
phi(1)
Dedans
phi(0) x
phi(0) =Level
Dehors phi(1) set
x Clovis Tauber
22
08/03/2023
Ensembles de niveaux (level sets)
• Intérêt majeur : prise en compte des changements topologiques
t t
y
y
Clovis Tauber
Ensembles de niveaux (level sets)
23
