Upload
sylviane-josse
View
105
Download
0
Embed Size (px)
Citation preview
ESIEA 30/11/2005 1Philippe Ciuciu SHFJ/CEA
Plan
I. Définitions & classification
II. Approche fonctionnelle
III. Quelques méthodes de segmentation
ESIEA 30/11/2005 2Philippe Ciuciu SHFJ/CEA
Segmentation d’images
Philippe Ciuciu (CEA/SHFJ)
http://www.madic.org/people/ciuciu
ESIEA 30/11/2005 3Philippe Ciuciu SHFJ/CEA
Cours préparé à partir de ressources Web et de
Jean-François Mangin (CEA/SHFJ)
ESIEA 30/11/2005 4Philippe Ciuciu SHFJ/CEA
La segmentation est un traitement bas-niveau qui consiste à créer une partition de l'image I en sous-ensembles Ri appelés régions telles que :
i
i
jiji
ii
RI
RRji
R
0 ;
0
,
Une région est un ensemble de pixels connexes ayant des propriétés communes qui les différencient des pixels des régions voisines.
I. Définitions & classification
ESIEA 30/11/2005 5Philippe Ciuciu SHFJ/CEA
Le choix d'une technique est lié :
A la nature de l'image (éclairage, contours, texture ...)
Aux opérations en aval de la segmentation
- Compression - Reconnaissance de formes, interprétation - Mesure
Aux primitives à extraire (droites, régions, textures,...)
Aux contraintes d'exploitation (tps réel, mémoire ...)
Pas de norme, de méthode unique ! Pas de recette !
ESIEA 30/11/2005 6Philippe Ciuciu SHFJ/CEA
Approches « région »
- Basées sur l'homogénéité de caractéristiques localisées spatialement et calculées sur les niveaux de gris
- Homogénéité : variation à l'intérieur d'une région < variation entre 2 régions
- Robustes aux bruits mais mauvaise localisation spatiale
ESIEA 30/11/2005 7Philippe Ciuciu SHFJ/CEA
Approches « frontière »
- Basées sur l'information de gradient pour localiser les frontières des régions
- 2 approches : détection et fermeture de contours ou techniques de contours déformables
- Sensibles aux bruits et aux contours mal définis, elles offrent une bonne localisation spatiale
ESIEA 30/11/2005 8Philippe Ciuciu SHFJ/CEA
Techniques de segmentation
Approches région
Approches frontière
Seuillage adaptatif
Méthodes variationnelles(contours actifs) Méthodes dérivatives
Template Matching
Texture Méthodes
Markoviennes Approches structurales
Analyse et classification
Détection de contours
+Fermeture des
contours
Vue d'ensemble
ESIEA 30/11/2005 9Philippe Ciuciu SHFJ/CEA
II. Approche fonctionnelle
Critères
Mesures
Évolution
Modification Arrêt
InitialisationImage
Carte desrégions
bloc élémentaire
ESIEA 30/11/2005 10Philippe Ciuciu SHFJ/CEA
Bloc 1
N1
Bloc k
Nk
Bloc 2
N2
Approche fonctionnelle et méthodes complexes
ESIEA 30/11/2005 11Philippe Ciuciu SHFJ/CEA
Bloc Mesures
- Réalise les mesures nécessaires pour évaluer l'homogénéité des régions
- Des mesures images : moyenne, variance, entropie, gradient, texture ...
- spatiales- fréquentielles
- Des mesures régions : forme, surface, périmètre ...
ESIEA 30/11/2005 12Philippe Ciuciu SHFJ/CEA
Choix des mesures : un problème compliqué Texture
Détection decontour !
Seuillage
ESIEA 30/11/2005 13Philippe Ciuciu SHFJ/CEA
Texture = information visuelle qualitative:Grossière, fine, tachetée, marbrée, régulière,
périodique...Région homogène: Assemblage plus ou moins régulier
de primitives plus ou moins similaires.
Texture microscopique: Aspect chaotique mais régulier, primitive de base réduite.
Texture macroscopique: primitive de baseévidente, assemblage régulier. ?
ESIEA 30/11/2005 14Philippe Ciuciu SHFJ/CEA
Approches pour l'analyse de Texture
Structurelles: recherche de primitives de base bien définies et de leur organisation (règles de placement)
Méthodes peu utiliséesStochastiques: primitives mal définies et organisation +/- aléatoire.
Principe: évaluation d’un paramètre dans une petite région(fenêtre de taille dépendant de la texture (!) ): Analyse fréquentielle, statistiques, comptage d’événements, corrélation,....
Pas de modèle général de texture Nombreuses méthodes ad-hoc.
ESIEA 30/11/2005 15Philippe Ciuciu SHFJ/CEA
Trouver les bons paramètres
4x4 8x8
16x16 32x32
Le choix et le réglagedes mesures estfondamental en segmentation
ESIEA 30/11/2005 16Philippe Ciuciu SHFJ/CEA
Bloc Critères
- Fusionne les mesures en un seul critère qui sera utilisé pour évaluer le besoin de modification
- Introduction d'hyper-paramètres conditionnant le résultat de la segmentation
M
i
ni
ni
n EwC1
.
ESIEA 30/11/2005 17Philippe Ciuciu SHFJ/CEA
Bloc Evolution
- Estime à partir des critères le besoin d'évolution des régions
- Evolution par seuillage : binaire ou progressive
- Evolution par dérivée : variation du critère entre 2 itérations
ESIEA 30/11/2005 18Philippe Ciuciu SHFJ/CEA
Bloc Modification- Modifie la carte des régions
- N constant : seuillage, contour actif, ...- N+ : split- N- : merge
- Stratégies diverses ... et représentation des régions adaptée
- déplacement de point- étiquetage- maillage
- Considéré comme le cœur des méthodes de segmentation
ESIEA 30/11/2005 19Philippe Ciuciu SHFJ/CEA
Bloc Arrêt
- Décide l'arrêt des itération
- Par défaut, arrêt quand la carte de segmentation ne bouge plus
- Autres possibilités : manuel, nombre d'itération, nombre de points modifiés ...
ESIEA 30/11/2005 20Philippe Ciuciu SHFJ/CEA
III. Quelques méthodes de segmentation
III.1 Segmentation par seuillage adaptatif
III.2 Segmentation par détection / fermeture de contours
III.3 Segmentation par contours actifs
III.4 Segmentation par Split / Merge
III.5 Segmentation par Template Matching
ESIEA 30/11/2005 21Philippe Ciuciu SHFJ/CEA
H(N)
Seuil
N
Objet
Fond
• Détection de vallées, en prenant le minimum de l’histogramme situé entre les 2 pics• Optimisation du seuil S par modélisation Gaussienne p1(x) et p2(x) et en minimisant l’expression basée sur les fonctions de répartition : Min F x S F x S1 1 2 ( ) ( )
III.1 Segmentation par seuillage adaptatif
ESIEA 30/11/2005 22Philippe Ciuciu SHFJ/CEA
Objectif : Trouver le seuil S qui minimise la somme des moments centrés d’ordre 2 (somme des Variances) des 2 classes
Centre de gravité G d’une classe
G S
xh x
h xi
x C
x C
i
i
( )
( )
( )
Var S x G h xi ix Ci
( ) ( ) ( ) 2 Variance Var d’une classe
h(x) : histogramme de l’image
Exemple : Méthode Fisher
ESIEA 30/11/2005 23Philippe Ciuciu SHFJ/CEA
)()( 21 SVarSVarMinSS
opt
Trouver S qui minimise la somme des variances :
En simplifiant les termes en carrés, cela revient à maximiser la fonctionnelle J(S) :
J S
xh x
h x
xh x
h x
x C
x C
x C
x C
( )
( )
( )
( )
( )
1
1
2
2
2 2
Le problème de seuillage ou de partitionnement revient à chercher S dans {0,255} qui maximise J(S)
ESIEA 30/11/2005 24Philippe Ciuciu SHFJ/CEA
Détection decontour
Extraction decontour
Fermeture decontour
La détection de contour est suivie d’une localisation de contour et de la recherche d’un ensemble connexe de points
III.2 Segmentation par détection / fermeture de contours
ESIEA 30/11/2005 25Philippe Ciuciu SHFJ/CEA
Détection de contour
• Un contour caractérise la frontière d’une région• Un contour est défini par une variation «rapide» de caractéristique
Contour Contour ? Contour ?
ESIEA 30/11/2005 26Philippe Ciuciu SHFJ/CEA
Définition continue d'un contour
Mesure du gradient de f(x,y) dans la direction rLa direction q du contour est obtenue pour :
2 max
),(
gpour
r
yxf
f(x,y)
r
x
g
f x y
r
( , )
0
ESIEA 30/11/2005 27Philippe Ciuciu SHFJ/CEA
)sin()cos(
y
f
x
f
r
y
y
f
r
x
x
f
r
f
0)cos()sin(
y
f
x
f
f x y
r
( , )
0
22
max
y
f
x
f
r
f
g
fy
fx
arctan( )
ESIEA 30/11/2005 28Philippe Ciuciu SHFJ/CEA
Applications aux images numériques• Pour chaque pixel (i,j), on mesure le gradient dans deux directions orthogonales : Dx Dy
• Calcul de l’amplitude du gradientM D Dx y 2 2
• Calcul de la direction du gradient
Arctan
D
Dy
x
f(i,j)
Dx
Dy
M
Carte d’amplitude
Carte de direction
H1
H2
ESIEA 30/11/2005 29Philippe Ciuciu SHFJ/CEA
Contour détecté si M dépasse une certaine valeur (seuil).
Carte de direction utilisée pour «suivre» les contours.
Exemples d’opérateurs H1 H2
Roberts
Prewitt
Sobel
0 1
1 0
1 0
0 1
1 0 1
1 0 1
1 0 1
1 1 1
0 0 0
1 1 1
1 0 1
2 0 2
1 0 1
1 2 1
0 0 0
1 2 1
ESIEA 30/11/2005 30Philippe Ciuciu SHFJ/CEA
« Roberts »Zoom
Direction
Amplitude
blanc=...gris = +128x128
(inhomogénéitédu contour)
Exemple de détection de contours
ESIEA 30/11/2005 31Philippe Ciuciu SHFJ/CEA
Amplitude
Direction
ESIEA 30/11/2005 32Philippe Ciuciu SHFJ/CEA
Éventail de méthodes de détection de contour :• Dérivation au premier ordre
Prewitt, Sobel, Roberts, Kirsh, Compass, dérivateurs...• Dérivation au second ordre
Laplacien, Marr et Hildreth,...• Filtrage optimal
Canny-Deriche, Shen• Modélisation des contours
Hueckel, Haralick
• Morphologie mathématiquegradient morphologique, ligne de partage des eaux...
Caractéristiques:Complexité, précision de localisation, sensibilité au bruit, création de faux contours
ESIEA 30/11/2005 33Philippe Ciuciu SHFJ/CEA
Un contour = ligne de crête dans l’image de la norme du gradient (IG):
• des niveaux de gris toujours élevés• de faibles dénivelés le long de ces lignes• de forts dénivelés dans les autres directions
==> les points de contour = maxima locaux de IG
Principe :comparer le gradient G en un point M avec les gradients G1 et G2 des deux voisins pris dans la direction du gradientsi G>G1 et G>G2, alors M est un maximum local
contour
G
G1
G2
direction de G
M
Extraction des contours
ESIEA 30/11/2005 34Philippe Ciuciu SHFJ/CEA
Hypothèse : l’image de la norme de gradient est disponible et les extrémités des contours à fermer sont connues
contour de l’image A
arc d’un chemin solution
Trouver le chemin du coût minimum :• S qui minimise
• S qui minimise la distance entre S0 et Sf
S0
Sf
SR
A S A R( ) ( )
Fermeture des contours
ESIEA 30/11/2005 35Philippe Ciuciu SHFJ/CEA
• Un contour actif : courbe fermée ou non, initialisée à proximité du contour recherché qu’on déforme par itérations successives afin de converger vers le contour réel• L’évolution du contour actif est régie par une minimisation d’énergie• L’évolution s’arrête par un critère d’arrêt qui correspond à une condition de stabilité
Finalcontour
Initialcontour
La convergence traduit une adéquation entre la forme finale de la courbe C et la fonction image au voisinage de la courbe
III.3 Segmentation par contours actifs
ESIEA 30/11/2005 36Philippe Ciuciu SHFJ/CEA
• Le contour actif est assimilé à une courbe C :
s est l‘abscisse curviligne, v(s,t) est un point courant de C, a et b sont les extrémités de C, l’évolution temporelle se fait entre 0 et T• l’énergie E(C) est mesurée à chaque pas t •E(C) intègre :
• les caractéristiques intrinsèques de la courbe C• les caractéristiques de l’image I au voisinage de C• l’interaction entre I et C
C v s t x s t y s t s a b t T ( , ) ( , ), ( , ) ; [ , ], [ , ]0
Contours actifs : définitions
ESIEA 30/11/2005 37Philippe Ciuciu SHFJ/CEA
Contours actifs : Energie du contour E(C)
E C E C E C E Cext image( ) ( ) ( ) ( )int
Eint : - lié à la rigidité (tension), il agit sur la longueur- lié à l'élasticité (flexion), il agit sur la courbure
Eext : - introduit des contraintes opérateur (points de contrôle ...)
Eimage : - introduit des caractéristiques images (gradient)
ESIEA 30/11/2005 38Philippe Ciuciu SHFJ/CEA
• Calculer l'énergie pour chaque point
• Faire la liste des points par ordre d’énergie décroissante
• Faire évoluer le point avec l'énergie maximale
• Calculer l'énergie nouvelle pour ce point et organiser la
liste
• si la distance entre deux points est trop grande, ajouter
un point entre les deux
Évolution temporelle du contour actif
ESIEA 30/11/2005 39Philippe Ciuciu SHFJ/CEA
• Contour initial sélectionné manuellement
• Contour initial relativement proche du contour final
• Modèle non utilisable en présence de texture
• Modèle perturbé en présence de bruit
• Minimisation d'énergie demande l’inversion de matrices
de grande taille à chaque itération
Problèmes liés aux contours actif
calcul très
long
ESIEA 30/11/2005 40Philippe Ciuciu SHFJ/CEA
• Méthodes structurales visant à regrouper des ensembles de points ou de régions selon des critères d’homogénéité
• Ces méthodes garantissent la connexité des régions
• Les stratégies utilisées peuvent être :• ascendante : mécanisme de croissance (MERGE) de régions : du niveau élémentaire (ex : pixel) aux grandes régions
• descendante : mécanisme de division (SPLIT) de régions : du niveau haut (ex : image) vers la décomposition en petites régions
III.4 Segmentation par Split / Merge
ESIEA 30/11/2005 41Philippe Ciuciu SHFJ/CEA
• Croissance conduite selon deux critères :
• homogénéité pour une région R formée de N pixels
• connexité (adjacence) du pixel à intégrer dans R
• Exemples de contrainte d’homogénéité :
• Variance Var(R) inférieure à un seuil
• Borner le nombre de pixels M dont les NG se situent
hors d’un intervalle [Moy(R)-EcType(R),Moy(R)+EcType(R)]
• Pixel S intégré à R si
• ses caractéristiques (NG, couleur, texture centrée sur
ce point,..) sont proches de celles de R
• S est connexe à R
Méthode ascendante : Croissance de régions
ESIEA 30/11/2005 42Philippe Ciuciu SHFJ/CEA
• Les méthodes descendantes divisent l’image ou une partie d’image en régions en utilisant des partitions élémentaires connues comme le quadtree
Méthodes descendantes : division de régions
• Division d’une région R en sous-régions si R ne remplit pas la contrainte d’homogénéité fixée
• Le maillage peut être – régulier ou irrégulier– de type rectangulaire, triangulaire ou polygonal quelconque
ESIEA 30/11/2005 43Philippe Ciuciu SHFJ/CEA
• La méthode Template Matching est basée sur la recherche de la position spatiale d’un motif (objet) M connu dans une image I
• La position du motif est donnée par les maxima de la fonction d’intercorrélation CIM
qp, tdéplacemen tout pour
m n
IM qnpmMnmIqpC ),(),(),(
III.5. Segmentation par Template Matching
• La recherche (ou le collage) se fait par le calcul de l’intercorrélation bidimensionnelle C(p,q) entre I et M :
ESIEA 30/11/2005 44Philippe Ciuciu SHFJ/CEA
Imageoriginale
Motif
Image d’intercorrélation seuilléeImage d’intercorrélation