Segmentation : principes• Objectif : décomposer l’image X en un

ensemble de sous-parties connexes formant une partition

• Notations :#R : nbre de régions, Ri région n°i,

• Segmentation vérifie :–

–

– i[1,#R], Ri est connexe

XRRi i #

1

ji RRjiRji ,,]#,1[),( 2

Rappel : application du théorème de Jordan sur la trame carrée : la 4 et la 8 connexité sont duale (région n-connexe courbe (12-n) connexe

Suppose 1 connexité

Segmentation : principes• Prédicats de base :

– La région Ri est homogène i[1,#R], H(Ri) vrai

– La région Ri est distincte de ses voisines

segmentation maximale (i,j)[1,#R]2, H(RiRj) faux

0 0 0 0 0 0 0 0 0 0 0 0 0 0 00 0 0 1 0 0 1 0 0 1 1 1 0 0 00 0 0 1 0 0 1 0 0 1 0 0 0 0 00 0 0 1 0 0 1 0 0 1 1 1 0 0 00 0 0 1 0 0 1 0 0 1 0 0 0 0 00 0 0 0 1 1 0 0 0 1 1 1 0 0 00 0 0 0 0 0 0 0 0 0 0 0 0 0 00 0 0 0 0 0 0 0 0 0 0 0 0 0 00 1 0 0 0 0 1 1 1 0 1 0 0 0 00 1 0 0 0 0 1 0 0 0 1 0 0 0 00 1 0 1 0 0 1 0 0 0 1 0 1 0 00 1 1 1 1 0 1 1 1 0 1 1 1 1 00 0 0 1 0 0 0 0 1 0 0 0 1 0 00 0 0 1 0 0 1 1 1 0 0 0 1 0 00 0 0 0 0 0 0 0 0 0 0 0 0 0 00 0 0 0 0 0 0 0 0 0 0 0 0 0 0

Segmentations maximales :

4-connexité → 8 régions,

8-connexité → 6 régions,

12-connexité → 4 régions

• Ex : segmentation en 8 régions 4-connexes

non maximale en 8-connexité

0 0 0 0 0 0 0 0 0 0 0 0 0 0 00 0 0 1 0 0 1 0 0 1 1 1 0 0 00 0 0 1 0 0 1 0 0 1 0 0 0 0 00 0 0 1 0 0 1 0 0 1 1 1 0 0 00 0 0 1 0 0 1 0 0 1 0 0 0 0 00 0 0 0 1 1 0 0 0 1 1 1 0 0 00 0 0 0 0 0 0 0 0 0 0 0 0 0 00 0 0 0 0 0 0 0 0 0 0 0 0 0 00 1 0 0 0 0 1 1 1 0 1 0 0 0 00 1 0 0 0 0 1 0 0 0 1 0 0 0 00 1 0 1 0 0 1 0 0 0 1 0 1 0 00 1 1 1 1 0 1 1 1 0 1 1 1 1 00 0 0 1 0 0 0 0 1 0 0 0 1 0 00 0 0 1 0 0 1 1 1 0 0 0 1 0 00 0 0 0 0 0 0 0 0 0 0 0 0 0 00 0 0 0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 0 0 0 0 00 0 0 1 0 0 1 0 0 1 1 1 0 0 00 0 0 1 0 0 1 0 0 1 0 0 0 0 00 0 0 1 0 0 1 0 0 1 1 1 0 0 00 0 0 1 0 0 1 0 0 1 0 0 0 0 00 0 0 0 1 1 0 0 0 1 1 1 0 0 00 0 0 0 0 0 0 0 0 0 0 0 0 0 00 0 0 0 0 0 0 0 0 0 0 0 0 0 00 1 0 0 0 0 1 1 1 0 1 0 0 0 00 1 0 0 0 0 1 0 0 0 1 0 0 0 00 1 0 1 0 0 1 0 0 0 1 0 1 0 00 1 1 1 1 0 1 1 1 0 1 1 1 1 00 0 0 1 0 0 0 0 1 0 0 0 1 0 00 0 0 1 0 0 1 1 1 0 0 0 1 0 00 0 0 0 0 0 0 0 0 0 0 0 0 0 00 0 0 0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 0 0 0 0 00 0 0 1 0 0 1 0 0 1 1 1 0 0 00 0 0 1 0 0 1 0 0 1 0 0 0 0 00 0 0 1 0 0 1 0 0 1 1 1 0 0 00 0 0 1 0 0 1 0 0 1 0 0 0 0 00 0 0 0 1 1 0 0 0 1 1 1 0 0 00 0 0 0 0 0 0 0 0 0 0 0 0 0 00 0 0 0 0 0 0 0 0 0 0 0 0 0 00 1 0 0 0 0 1 1 1 0 1 0 0 0 00 1 0 0 0 0 1 0 0 0 1 0 0 0 00 1 0 1 0 0 1 0 0 0 1 0 1 0 00 1 1 1 1 0 1 1 1 0 1 1 1 1 00 0 0 1 0 0 0 0 1 0 0 0 1 0 00 0 0 1 0 0 1 1 1 0 0 0 1 0 00 0 0 0 0 0 0 0 0 0 0 0 0 0 00 0 0 0 0 0 0 0 0 0 0 0 0 0 0

Recherche de zones possédant des attributs similaires Approche duale de la

détection de contours

Méthodes de segmentation :

•par classification

•par transformation de régions (croissance de régions, split&merge, graphe de régions)

•par analyse d’une image de gradient (ligne de partage des eaux)

•par méthode variationnelle (Mumford & Shah)

1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 11 1 1 2 1 1 3 1 1 5 5 5 1 1 1 11 1 1 2 1 1 3 1 1 5 1 1 1 1 1 11 1 1 2 1 1 3 1 1 5 5 5 1 1 1 11 1 1 2 1 1 3 1 1 5 1 1 1 1 1 11 1 1 1 4 4 1 1 1 5 5 5 1 1 1 11 1 1 1 1 1 1 1 1 1 1 1 1 1 1 11 1 1 1 1 1 1 1 1 1 1 1 1 1 1 11 6 1 1 1 1 8 8 8 1 7 1 1 1 1 11 6 1 1 1 1 8 1 1 1 7 1 1 1 1 11 6 1 6 1 1 8 1 1 1 7 1 7 1 1 11 6 6 6 6 1 8 8 8 1 7 7 7 7 1 11 1 1 6 1 1 1 1 8 1 1 1 7 1 1 11 1 1 6 1 1 8 8 8 1 1 1 7 1 1 11 1 1 1 1 1 1 1 1 1 1 1 1 1 1 11 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 11 1 1 2 1 1 3 1 1 5 5 5 1 1 1 11 1 1 2 1 1 3 1 1 5 1 1 1 1 1 11 1 1 2 1 1 3 1 1 5 5 5 1 1 1 11 1 1 2 1 1 3 1 1 5 1 1 1 1 1 11 1 1 1 4 4 1 1 1 5 5 5 1 1 1 11 1 1 1 1 1 1 1 1 1 1 1 1 1 1 11 1 1 1 1 1 1 1 1 1 1 1 1 1 1 11 6 1 1 1 1 1 7 1 1 1 1 11 6 1 1 1 1 1 1 1 7 1 1 1 1 11 6 1 6 1 1 1 1 1 7 1 7 1 1 11 6 6 6 6 1 1 7 7 7 7 1 11 1 1 6 1 1 1 1 1 1 1 7 1 1 11 1 1 6 1 1 1 1 1 7 1 1 11 1 1 1 1 1 1 1 1 1 1 1 1 1 1 11 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 11 1 1 2 1 1 3 1 1 5 5 5 1 1 1 11 1 1 2 1 1 3 1 1 5 1 1 1 1 1 11 1 1 2 1 1 3 1 1 5 5 5 1 1 1 11 1 1 2 1 1 3 1 1 5 1 1 1 1 1 11 1 1 1 4 4 1 1 1 5 5 5 1 1 1 11 1 1 1 1 1 1 1 1 1 1 1 1 1 1 11 1 1 1 1 1 1 1 1 1 1 1 1 1 1 11 6 1 1 1 1 1 1 1 1 1 11 6 1 1 1 1 1 1 1 1 1 1 1 11 6 1 6 1 1 1 1 1 1 1 1 11 6 6 6 6 1 1 1 11 1 1 6 1 1 1 1 1 1 1 1 1 11 1 1 6 1 1 1 1 1 1 1 11 1 1 1 1 1 1 1 1 1 1 1 1 1 1 11 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 11 1 1 2 1 1 3 1 1 5 5 5 1 1 1 11 1 1 2 1 1 3 1 1 5 1 1 1 1 1 11 1 1 2 1 1 3 1 1 5 5 5 1 1 1 11 1 1 2 1 1 3 1 1 5 1 1 1 1 1 11 1 1 1 4 4 1 1 1 5 5 5 1 1 1 11 1 1 1 1 1 1 1 1 1 1 1 1 1 1 11 1 1 1 1 1 1 1 1 1 1 1 1 1 1 11 1 1 1 1 1 1 1 1 1 11 1 1 1 1 1 1 1 1 1 1 1 11 1 1 1 1 1 1 1 1 1 11 1 1 1 11 1 1 1 1 1 1 1 1 1 1 1 11 1 1 1 1 1 1 1 1 1 11 1 1 1 1 1 1 1 1 1 1 1 1 1 1 11 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 11 1 1 2 1 1 3 1 1 1 1 1 11 1 1 2 1 1 3 1 1 1 1 1 1 1 11 1 1 2 1 1 3 1 1 1 1 1 11 1 1 2 1 1 3 1 1 1 1 1 1 1 11 1 1 1 4 4 1 1 1 1 1 1 11 1 1 1 1 1 1 1 1 1 1 1 1 1 1 11 1 1 1 1 1 1 1 1 1 1 1 1 1 1 11 1 1 1 1 1 1 1 1 1 11 1 1 1 1 1 1 1 1 1 1 1 11 1 1 1 1 1 1 1 1 1 11 1 1 1 11 1 1 1 1 1 1 1 1 1 1 1 11 1 1 1 1 1 1 1 1 1 11 1 1 1 1 1 1 1 1 1 1 1 1 1 1 11 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 11 1 1 2 1 1 3 1 1 1 1 1 11 1 1 2 1 1 3 1 1 1 1 1 1 1 11 1 1 2 1 1 3 1 1 1 1 1 11 1 1 2 1 1 3 1 1 1 1 1 1 1 11 1 1 1 1 1 1 1 1 1 11 1 1 1 1 1 1 1 1 1 1 1 1 1 1 11 1 1 1 1 1 1 1 1 1 1 1 1 1 1 11 1 1 1 1 1 1 1 1 1 11 1 1 1 1 1 1 1 1 1 1 1 11 1 1 1 1 1 1 1 1 1 11 1 1 1 11 1 1 1 1 1 1 1 1 1 1 1 11 1 1 1 1 1 1 1 1 1 11 1 1 1 1 1 1 1 1 1 1 1 1 1 1 11 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 11 1 1 2 1 1 1 1 1 1 1 11 1 1 2 1 1 1 1 1 1 1 1 1 11 1 1 2 1 1 1 1 1 1 1 11 1 1 2 1 1 1 1 1 1 1 1 1 11 1 1 1 1 1 1 1 1 1 11 1 1 1 1 1 1 1 1 1 1 1 1 1 1 11 1 1 1 1 1 1 1 1 1 1 1 1 1 1 11 1 1 1 1 1 1 1 1 1 11 1 1 1 1 1 1 1 1 1 1 1 11 1 1 1 1 1 1 1 1 1 11 1 1 1 11 1 1 1 1 1 1 1 1 1 1 1 11 1 1 1 1 1 1 1 1 1 11 1 1 1 1 1 1 1 1 1 1 1 1 1 1 11 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 11 1 1 1 1 1 1 1 1 1 11 1 1 1 1 1 1 1 1 1 1 1 11 1 1 1 1 1 1 1 1 1 11 1 1 1 1 1 1 1 1 1 1 1 11 1 1 1 1 1 1 1 1 1 11 1 1 1 1 1 1 1 1 1 1 1 1 1 1 11 1 1 1 1 1 1 1 1 1 1 1 1 1 1 11 1 1 1 1 1 1 1 1 1 11 1 1 1 1 1 1 1 1 1 1 1 11 1 1 1 1 1 1 1 1 1 11 1 1 1 11 1 1 1 1 1 1 1 1 1 1 1 11 1 1 1 1 1 1 1 1 1 11 1 1 1 1 1 1 1 1 1 1 1 1 1 1 11 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 00 0 0 1 0 0 1 0 0 2 2 2 0 0 0 00 0 0 1 0 0 1 0 0 2 0 0 0 0 0 00 0 0 1 0 0 1 0 0 2 2 2 0 0 0 00 0 0 1 0 0 1 0 0 2 0 0 0 0 0 00 0 0 0 1 1 0 0 0 2 2 2 0 0 0 00 0 0 0 0 0 0 0 0 0 0 0 0 0 0 00 0 0 0 0 0 0 0 0 0 0 0 0 0 0 00 3 0 0 0 0 5 5 5 0 3 0 0 0 0 00 3 0 0 0 0 5 0 0 0 3 0 0 0 0 00 3 0 3 0 0 5 0 0 0 3 0 3 0 0 00 3 3 3 3 0 5 5 5 0 3 3 3 3 0 00 0 0 3 0 0 0 0 5 0 0 0 3 0 0 00 0 0 3 0 0 5 5 5 0 0 0 3 0 0 00 0 0 0 0 0 0 0 0 0 0 0 0 0 0 00 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 00 0 0 1 0 0 1 0 0 1 1 1 0 0 0 00 0 0 1 0 0 1 0 0 1 0 0 0 0 0 00 0 0 1 0 0 1 0 0 1 1 1 0 0 0 00 0 0 1 0 0 1 0 0 1 0 0 0 0 0 00 0 0 0 1 1 0 0 0 1 1 1 0 0 0 00 0 0 0 0 0 0 0 0 0 0 0 0 0 0 00 0 0 0 0 0 0 0 0 0 0 0 0 0 0 00 1 0 0 0 0 1 1 1 0 1 0 0 0 0 00 1 0 0 0 0 1 0 0 0 1 0 0 0 0 00 1 0 1 0 0 1 0 0 0 1 0 1 0 0 00 1 1 1 1 0 1 1 1 0 1 1 1 1 0 00 0 0 1 0 0 0 0 1 0 0 0 1 0 0 00 0 0 1 0 0 1 1 1 0 0 0 1 0 0 00 0 0 0 0 0 0 0 0 0 0 0 0 0 0 00 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

Segmentation à partir d’1 classification

• Classification → partition en c classes homogènes (du point de vue de la loi supposée) ayant chacune 1 ou plus composantes connexes

• Etiquetage en composantes connexes des c classes → segmentation

• Ex.

Segmentation à partir d’1 classification

• algorithme :

– Initialisations : k=0, sS, zs=0

– Pour chaque classe i

• Créer l’image binaire B de la classe (bs=1 xs=i)

• Pour tout pixel sS :– Si bs=1 et zs=0, alors :

» Calcul de la composante connexe CC{s} de s dans B(par exemple selon 1 des algo. d’étiquetage en composantes connexes donnés)

» k=k+1tCC{s}, zt=k

– #R=k

Étiquetage en composantes connexes

• Algo. 1 : Calcul de la composante connexe CC{s} de s dans B• initialisation de la pile avec s et de la composante connexe à 0• tant que la pile n’est pas vide

– extraire t de la pile– mettre t à 1 dans la composante connexe– pour tout r voisin de t non déjà traité (ni déjà dans la pile)

» si xr=i rajouter r dans la pile

• Algo. 2 : Etiquetage de l’ensemble de l’image en 1 passe• initialiser l’image des étiquettes Z à 0• balayer l’image, soit s le pixel courant

– soit l1 et l2 les 2 étiquettes des voisins de s (masque causal 2-connexité)

– si (l1=l2) ou (li 0 et l3-i=0, i{1,2}), affecter li à s dans Z

– si (l1l2), affecter min(l1,l2) à s dans Z, et mettre à jour la table d’équivalence entre les étiquettes : l1l2

– si (l1=l2=0), créer une nouvelle étiquette l et affecter l à s dans Z

• balayer l’image pour uniformiser les étiquettes selon la table d’équivalence

Segmentation à partir d’1

classification

• Exemple :

#cl = 2, clas. aveugle #cl = 3, clas. aveugle #cl = 3, clas. MRF

#R = 6 #R = 32 !!!!!! #R = 21

Chaque pixel est classé selon sa valeur indépendamment de

ses voisins

Markov Random Field → chaque pixel est classé en tenant compte de sa valeur (attache aux données) ET des labels de ses voisins (a priori sur le champ des labels, e.g. régulier)

Croissance de région (region growing)

• À partir de pixels-germes (généralement sélectionnés à partir de l’histogramme), on fait croître les régions en ‘agglomérant’ les pixels ou régions connexes tels que l’union vérifie le prédicat d’homogénéité

• Pb du choix des germes :– Dans le cas général, la croissance de région

s’arrête avant d’avoir obtenu une segmentation :

– Si on part de la segmentation triviale (chaque pixel est un germe), dépendance à l’ordre de fusion des régions

XRRi i #

1

Critères d’homogénéité d’1 région

• Exemples de critères globaux à la région

– Contraste : H(Ri) vrai

– Variance : H(Ri) vrai

– Distance interquartiles : H(Ri) vrai

– Entropie : H(Ri) vrai

• Exemples de critères locaux à la région

– Distance avec pixels voisins : H(Ri{s}) vrai

contrastesRs

sRs

syyii

minmax

varianceRs Rs

si

si

syR

yR

i i

21

11

quartileqqiqisq szzqzRsyPziii

12

,,/ ,2,1

entropieRsy

ss sypypis

/

log.

distancersrsRr

syyi

connexes , et

min

Sélection de germes sur histogramme

• Algorithme– k=0– tant que pixels non labelisés

• Calcul de l’histogramme Hres des pixels non labelisés

• xval = mode de Hres, s_germe / xs_germe= xval

• k=k+1• Croissance de région à partir de s_germe :

– zs_germe=k

– Tant que t connexe à Rk et Rk{t} vérifie prédicat d’homogénéïté, Rk ← Rk{t}

tRk, zt=k

– #R=k

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 00 0 0 1 0 0 1 0 0 2 2 2 0 0 0 00 0 0 1 0 0 1 0 0 2 0 0 0 0 0 00 0 0 1 0 0 1 0 0 2 2 2 0 0 0 00 0 0 1 0 0 1 0 0 2 0 0 0 0 0 00 0 0 0 1 1 0 0 0 2 2 2 0 0 0 00 0 0 0 0 0 0 0 0 0 0 0 0 0 0 00 0 0 0 0 0 0 0 0 0 0 0 0 0 0 00 3 0 0 0 0 4 4 4 0 3 0 0 0 0 00 3 0 0 0 0 4 0 0 0 3 0 0 0 0 00 3 0 3 0 0 4 0 0 0 3 0 3 0 0 00 3 3 3 3 0 4 4 4 0 3 3 3 3 0 00 0 0 3 0 0 0 0 4 0 0 0 3 0 0 00 0 0 3 0 0 4 4 4 0 0 0 3 0 0 00 0 0 0 0 0 0 0 0 0 0 0 0 0 0 00 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

0

50

100

150

200

250

1 2 3 4 5valeur pixel

# p

ixel

s

1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 11 1 1 1 1 1 1 1 1 1 11 1 1 1 1 1 1 1 1 1 1 1 11 1 1 1 1 1 1 1 1 1 11 1 1 1 1 1 1 1 1 1 1 1 11 1 1 1 1 1 1 1 1 1 11 1 1 1 1 1 1 1 1 1 1 1 1 1 1 11 1 1 1 1 1 1 1 1 1 1 1 1 1 1 11 1 1 1 1 1 1 1 1 1 11 1 1 1 1 1 1 1 1 1 1 1 11 1 1 1 1 1 1 1 1 1 11 1 1 1 11 1 1 1 1 1 1 1 1 1 1 1 11 1 1 1 1 1 1 1 1 1 11 1 1 1 1 1 1 1 1 1 1 1 1 1 1 11 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

0

5

10

15

20

25

1 2 3 4 5valeur pixel

# p

ixel

s

1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 11 1 1 1 1 1 1 1 1 1 11 1 1 1 1 1 1 1 1 1 1 1 11 1 1 1 1 1 1 1 1 1 11 1 1 1 1 1 1 1 1 1 1 1 11 1 1 1 1 1 1 1 1 1 11 1 1 1 1 1 1 1 1 1 1 1 1 1 1 11 1 1 1 1 1 1 1 1 1 1 1 1 1 1 11 2 1 1 1 1 1 1 1 1 1 11 2 1 1 1 1 1 1 1 1 1 1 1 11 2 1 2 1 1 1 1 1 1 1 1 11 2 2 2 2 1 1 1 11 1 1 2 1 1 1 1 1 1 1 1 1 11 1 1 2 1 1 1 1 1 1 1 11 1 1 1 1 1 1 1 1 1 1 1 1 1 1 11 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

0

2

4

6

8

10

12

14

1 2 3 4 5valeur pixel

# p

ixel

s

1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 11 1 1 1 1 1 1 1 1 1 11 1 1 1 1 1 1 1 1 1 1 1 11 1 1 1 1 1 1 1 1 1 11 1 1 1 1 1 1 1 1 1 1 1 11 1 1 1 1 1 1 1 1 1 11 1 1 1 1 1 1 1 1 1 1 1 1 1 1 11 1 1 1 1 1 1 1 1 1 1 1 1 1 1 11 2 1 1 1 1 3 3 3 1 1 1 1 1 11 2 1 1 1 1 3 1 1 1 1 1 1 1 11 2 1 2 1 1 3 1 1 1 1 1 1 11 2 2 2 2 1 3 3 3 1 1 11 1 1 2 1 1 1 1 3 1 1 1 1 1 11 1 1 2 1 1 3 3 3 1 1 1 1 1 11 1 1 1 1 1 1 1 1 1 1 1 1 1 1 11 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

0

2

4

6

8

10

12

1 2 3 4 5valeur pixel

# p

ixel

s

1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 11 1 1 1 1 1 1 4 4 4 1 1 1 11 1 1 1 1 1 1 4 1 1 1 1 1 11 1 1 1 1 1 1 4 4 4 1 1 1 11 1 1 1 1 1 1 4 1 1 1 1 1 11 1 1 1 1 1 1 4 4 4 1 1 1 11 1 1 1 1 1 1 1 1 1 1 1 1 1 1 11 1 1 1 1 1 1 1 1 1 1 1 1 1 1 11 2 1 1 1 1 3 3 3 1 1 1 1 1 11 2 1 1 1 1 3 1 1 1 1 1 1 1 11 2 1 2 1 1 3 1 1 1 1 1 1 11 2 2 2 2 1 3 3 3 1 1 11 1 1 2 1 1 1 1 3 1 1 1 1 1 11 1 1 2 1 1 3 3 3 1 1 1 1 1 11 1 1 1 1 1 1 1 1 1 1 1 1 1 1 11 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

0

2

4

6

8

10

12

1 2 3 4 5valeur pixel

# p

ixel

s

1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 11 1 1 5 1 1 1 1 4 4 4 1 1 1 11 1 1 5 1 1 1 1 4 1 1 1 1 1 11 1 1 5 1 1 1 1 4 4 4 1 1 1 11 1 1 5 1 1 1 1 4 1 1 1 1 1 11 1 1 1 1 1 1 4 4 4 1 1 1 11 1 1 1 1 1 1 1 1 1 1 1 1 1 1 11 1 1 1 1 1 1 1 1 1 1 1 1 1 1 11 2 1 1 1 1 3 3 3 1 1 1 1 1 11 2 1 1 1 1 3 1 1 1 1 1 1 1 11 2 1 2 1 1 3 1 1 1 1 1 1 11 2 2 2 2 1 3 3 3 1 1 11 1 1 2 1 1 1 1 3 1 1 1 1 1 11 1 1 2 1 1 3 3 3 1 1 1 1 1 11 1 1 1 1 1 1 1 1 1 1 1 1 1 1 11 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

0

2

4

6

8

10

12

1 2 3 4 5valeur pixel

# p

ixel

s

1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 11 1 1 5 1 1 1 1 4 4 4 1 1 1 11 1 1 5 1 1 1 1 4 1 1 1 1 1 11 1 1 5 1 1 1 1 4 4 4 1 1 1 11 1 1 5 1 1 1 1 4 1 1 1 1 1 11 1 1 1 1 1 1 4 4 4 1 1 1 11 1 1 1 1 1 1 1 1 1 1 1 1 1 1 11 1 1 1 1 1 1 1 1 1 1 1 1 1 1 11 2 1 1 1 1 3 3 3 1 6 1 1 1 1 11 2 1 1 1 1 3 1 1 1 6 1 1 1 1 11 2 1 2 1 1 3 1 1 1 6 1 6 1 1 11 2 2 2 2 1 3 3 3 1 6 6 6 6 1 11 1 1 2 1 1 1 1 3 1 1 1 6 1 1 11 1 1 2 1 1 3 3 3 1 1 1 6 1 1 11 1 1 1 1 1 1 1 1 1 1 1 1 1 1 11 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

0

1

2

3

4

5

6

7

1 2 3 4 5valeur pixel

# p

ixel

s

1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 11 1 1 5 1 1 7 1 1 4 4 4 1 1 1 11 1 1 5 1 1 7 1 1 4 1 1 1 1 1 11 1 1 5 1 1 7 1 1 4 4 4 1 1 1 11 1 1 5 1 1 7 1 1 4 1 1 1 1 1 11 1 1 1 1 1 1 4 4 4 1 1 1 11 1 1 1 1 1 1 1 1 1 1 1 1 1 1 11 1 1 1 1 1 1 1 1 1 1 1 1 1 1 11 2 1 1 1 1 3 3 3 1 6 1 1 1 1 11 2 1 1 1 1 3 1 1 1 6 1 1 1 1 11 2 1 2 1 1 3 1 1 1 6 1 6 1 1 11 2 2 2 2 1 3 3 3 1 6 6 6 6 1 11 1 1 2 1 1 1 1 3 1 1 1 6 1 1 11 1 1 2 1 1 3 3 3 1 1 1 6 1 1 11 1 1 1 1 1 1 1 1 1 1 1 1 1 1 11 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

0

0,5

1

1,5

2

2,5

1 2 3 4 5valeur pixel

# p

ixel

s

1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 11 1 1 5 1 1 7 1 1 4 4 4 1 1 1 11 1 1 5 1 1 7 1 1 4 1 1 1 1 1 11 1 1 5 1 1 7 1 1 4 4 4 1 1 1 11 1 1 5 1 1 7 1 1 4 1 1 1 1 1 11 1 1 1 8 8 1 1 1 4 4 4 1 1 1 11 1 1 1 1 1 1 1 1 1 1 1 1 1 1 11 1 1 1 1 1 1 1 1 1 1 1 1 1 1 11 2 1 1 1 1 3 3 3 1 6 1 1 1 1 11 2 1 1 1 1 3 1 1 1 6 1 1 1 1 11 2 1 2 1 1 3 1 1 1 6 1 6 1 1 11 2 2 2 2 1 3 3 3 1 6 6 6 6 1 11 1 1 2 1 1 1 1 3 1 1 1 6 1 1 11 1 1 2 1 1 3 3 3 1 1 1 6 1 1 11 1 1 1 1 1 1 1 1 1 1 1 1 1 1 11 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

Croissance de régions

• Exemple :

Cmax = 80 → #R = 6 Cmax = 70 → #R = 17Cmax = 100 → #R = 6

Cmax = 100 → #R = 6 Cmax = 80 → #R = 5 Cmax = 70 → #R = 12

≠≠≠

Sél

ectio

n de

ger

mes

su

r hi

stog

ram

me

Sél

ectio

n de

ge

rmes

alé

atoi

re

Pyramide du Quadtree

00 01

02 03

10 11

12 13

20 21

22 23

30 31

32 33

0 1

2 3

000

00100

2003

010

01101

201302

002102

2023

030

03103

2033

100

10110

2103

110

11111

211313

013113

2133

200

20120

2203

210

21121

221322

022122

2223

230

23123

2233

300

30130

2303

310

31131

231332

032132

2323

330

33133

2333

Construction du quadtree par parcours de Peano :

Clé de Peano :

Pixel de coordonnées-image (i,j)

i7 j7 i6 j6 i5 j5 i4 j4 i3 j3 i2 j2 i1 j1 i0 j0

i7 i6 i5 i4 i3 i2 i1 i0i7 i6 i5 i4 i3 i2 i1 i0 j7 j6 j5 j4 j3 j2 j1 j0j7 j6 j5 j4 j3 j2 j1 j0+

Ex. :(2,3) 13

(6,2) 44

120

12112

2123

Partage / réunion de régions• region splitting : soit Ri / H(Ri) faux, alors diviser Ri

• region merging : soit Ri , Rj connexes / H(RiRj) vrai, alors Ri=RiRj, supprimer Rj

• Application à la structure du quadtree (image NxN)– Initialisations : l0 niveau de départ dans la pyramide, t0=N/2l0 , n=4l0

– Fusion : j=l0, t=t0 , k=1• Tant que j>0

– Pour i variant de 0 à n-1 par pas de 4l0-j+1

» Si les 4 blocs i, i+k, i+2k, i+3k sont de taille t, et si le critère d’homogénéité est vérifié pour l’union des 4 blocs, alors

Les fusionner : mise à jour des tailles et caractéristiques des blocs (on ne garde que le bloc n°i)

– Passage au niveau supérieur de la pyramide : j=j-1, t=2t, k=4k

– Division : j=l0• Pour i variant de 0 à n-1

– Si la taille du bloc i est ≤t0 et >0» Tant que le critère d’homogénéité n’est pas vérifié pour le bloc i

subdiviser le bloc i en 4 blocs : mettre à jour les paramètres de i à partir du sous-bloc et créer les 3 autres sous-blocs indicés n+1, n+2, n+3, et actualiser n à n+3

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 00 0 0 1 0 0 1 0 0 2 2 2 0 0 0 00 0 0 1 0 0 1 0 0 2 0 0 0 0 0 00 0 0 1 0 0 1 0 0 2 2 2 0 0 0 00 0 0 1 0 0 1 0 0 2 0 0 0 0 0 00 0 0 0 1 1 0 0 0 2 2 2 0 0 0 00 0 0 0 0 0 0 0 0 0 0 0 0 0 0 00 0 0 0 0 0 0 0 0 0 0 0 0 0 0 00 3 0 0 0 0 4 4 4 0 3 0 0 0 0 00 3 0 0 0 0 4 0 0 0 3 0 0 0 0 00 3 0 3 0 0 4 0 0 0 3 0 3 0 0 00 3 3 3 3 0 4 4 4 0 3 3 3 3 0 00 0 0 3 0 0 0 0 4 0 0 0 3 0 0 00 0 0 3 0 0 4 4 4 0 0 0 3 0 0 00 0 0 0 0 0 0 0 0 0 0 0 0 0 0 00 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 00 0 0 1 0 0 1 0 0 2 2 2 0 0 0 00 0 0 1 0 0 1 0 0 2 0 0 0 0 0 00 0 0 1 0 0 1 0 0 2 2 2 0 0 0 00 0 0 1 0 0 1 0 0 2 0 0 0 0 0 00 0 0 0 1 1 0 0 0 2 2 2 0 0 0 00 0 0 0 0 0 0 0 0 0 0 0 0 0 0 00 0 0 0 0 0 0 0 0 0 0 0 0 0 0 00 3 0 0 0 0 4 4 4 0 3 0 0 0 0 00 3 0 0 0 0 4 0 0 0 3 0 0 0 0 00 3 0 3 0 0 4 0 0 0 3 0 3 0 0 00 3 3 3 3 0 4 4 4 0 3 3 3 3 0 00 0 0 3 0 0 0 0 4 0 0 0 3 0 0 00 0 0 3 0 0 4 4 4 0 0 0 3 0 0 00 0 0 0 0 0 0 0 0 0 0 0 0 0 0 00 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

0 0 1 1 5 5 6 6 38 38 40 40 46 46 46 46

0 0 1 2 5 5 7 6 38 39 41 41 46 46 46 46

0 0 3 4 5 5 8 9 42 43 44 44 46 46 46 46

0 0 3 4 5 5 8 9 42 43 45 45 46 46 46 46

10 10 11 12 13 13 15 16 47 48 49 49 46 46 46 46

10 10 11 11 14 14 16 16 47 48 50 50 46 46 46 46

10 10 10 10 17 17 17 17 51 51 51 51 46 46 46 4610 10 10 10 17 17 17 17 51 51 51 51 46 46 46 46

18 19 20 20 25 25 26 26 52 53 54 55 63 63 63 63

18 19 20 20 25 25 26 27 53 53 54 55 63 63 63 63

21 22 23 24 28 28 30 31 56 56 58 59 64 65 63 63

21 22 24 24 29 28 30 30 57 56 58 58 64 64 63 63

32 32 33 34 35 35 36 36 60 61 62 62 66 67 68 68

32 32 33 34 35 35 37 37 60 61 62 62 66 67 68 68

32 32 32 32 35 35 35 35 62 62 62 62 68 68 68 6832 32 32 32 35 35 35 35 62 62 62 62 68 68 68 68

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 00 0 0 1 0 0 1 0 0 2 2 2 0 0 0 00 0 0 1 0 0 1 0 0 2 0 0 0 0 0 00 0 0 1 0 0 1 0 0 2 2 2 0 0 0 00 0 0 1 0 0 1 0 0 2 0 0 0 0 0 00 0 0 0 1 1 0 0 0 2 2 2 0 0 0 00 0 0 0 0 0 0 0 0 0 0 0 0 0 0 00 0 0 0 0 0 0 0 0 0 0 0 0 0 0 00 3 0 0 0 0 4 4 4 0 3 0 0 0 0 00 3 0 0 0 0 4 0 0 0 3 0 0 0 0 00 3 0 3 0 0 4 0 0 0 3 0 3 0 0 00 3 3 3 3 0 4 4 4 0 3 3 3 3 0 00 0 0 3 0 0 0 0 4 0 0 0 3 0 0 00 0 0 3 0 0 4 4 4 0 0 0 3 0 0 00 0 0 0 0 0 0 0 0 0 0 0 0 0 0 00 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 00 0 0 1 0 0 1 0 0 2 2 2 0 0 0 00 0 0 1 0 0 1 0 0 2 0 0 0 0 0 00 0 0 1 0 0 1 0 0 2 2 2 0 0 0 00 0 0 1 0 0 1 0 0 2 0 0 0 0 0 00 0 0 0 1 1 0 0 0 2 2 2 0 0 0 00 0 0 0 0 0 0 0 0 0 0 0 0 0 0 00 0 0 0 0 0 0 0 0 0 0 0 0 0 0 00 3 0 0 0 0 4 4 4 0 3 0 0 0 0 00 3 0 0 0 0 4 0 0 0 3 0 0 0 0 00 3 0 3 0 0 4 0 0 0 3 0 3 0 0 00 3 3 3 3 0 4 4 4 0 3 3 3 3 0 00 0 0 3 0 0 0 0 4 0 0 0 3 0 0 00 0 0 3 0 0 4 4 4 0 0 0 3 0 0 00 0 0 0 0 0 0 0 0 0 0 0 0 0 0 00 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

Exemple de segmentation contrainte par le quadtree

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 00 0 0 1 0 0 1 0 0 2 2 2 0 0 0 00 0 0 1 0 0 1 0 0 2 0 0 0 0 0 00 0 0 1 0 0 1 0 0 2 2 2 0 0 0 00 0 0 1 0 0 1 0 0 2 0 0 0 0 0 00 0 0 0 1 1 0 0 0 2 2 2 0 0 0 00 0 0 0 0 0 0 0 0 0 0 0 0 0 0 00 0 0 0 0 0 0 0 0 0 0 0 0 0 0 00 3 0 0 0 0 4 4 4 0 3 0 0 0 0 00 3 0 0 0 0 4 0 0 0 3 0 0 0 0 00 3 0 3 0 0 4 0 0 0 3 0 3 0 0 00 3 3 3 3 0 4 4 4 0 3 3 3 3 0 00 0 0 3 0 0 0 0 4 0 0 0 3 0 0 00 0 0 3 0 0 4 4 4 0 0 0 3 0 0 00 0 0 0 0 0 0 0 0 0 0 0 0 0 0 00 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

À partir du niveau 1 de la pyramide Fusion de 4 blocs de niveau 1 en 1 bloc de niveau 2

Scission de blocs de niveau 1 en 4 blocs de niveau 0

Fusion de sous-blocs d’1 même bloc de niveau 2

Fusion de sous-blocs d’1 même bloc de niveau 1

Labellisation des blocs

Réunion de régions• Tests statistiques entre deux régions à fusionner

Hyp. : bruit gaussien sur une image assimilée à une fonction 2D constante par morceau

– Test du 2 d’homogénéité v.a. qui suit 1 loi du 2 à m-1 degrés de liberté ?

– Test de Student d’égalité des espérances intervalle de confiance de l’estimateur de l’espérance d’une loi normale dont la variance est inconnue avec

– Test de Fisher-Snedecor d’égalité des moyennes et des variances…

– Test de Wilcoxon : soit (somme pour chaque

pixel de R1 du # de pixels de R2 de valeur inférieure) : on teste

si U suit 1 loi normale N(n1n2/2, n1n2(n1+n2+1)/12)

m

j j

jj

n

nnerr

1

2

'

'

, , 1

2/11

2/1 n

Stx

n

Stx nn

1

,1,22Rs

st xxRU

n

ii

n

ii xx

nSx

nx

1

2

1 1

1,

1

Fusion de régions dans un graphe• Le graphe est constitué de :

– Une liste de sommets LS : chaque région Ri est représentée par 1 sommet s auquel sont associés : les caract. de Ri, la liste des pixels de Ri, le # et la liste des arrêtes impliquant s

– Une liste d’arrêtes LA : chaque arrête a est caractérisée par les 2 sommets qu’elle relie, son coût ct(a), un indicateur de validité

• Exemple de construction du graphe d’adjacence :

1

2

3

56

7

8

4

1

2

3

56

7

8

4

Fusion de régions dans un graphe• Exemple d’algorithme :

– Initialisations : # de régions = # pixels, initialisation de LS et LA

– Tant que # de régions > # de régions voulu• Sélection des arrêtes a0 de moindre coût par accord

mutuel (a0 relie si et sj et j=argmink{ct(a)/a=(si,sk)} et i=argmink{ct(a)/a=(sj,sk)}

• Fusion des régions associées aux arrêtes a0 :– mise à jour de la liste des sommets (liste des arrêtes

associées, liste des pixels, caractéristiques de la région représentée)

– Mise à jour de la liste des arrêtes (validité, coût, sommets associés)

• Mise à jour du # de régions = # sommets

– Création de l’image des régions (d’après liste de pixels des sommets)

0 0 0 0 0 0 0 0 0 0 0 0 16 16 16 16

0 0 0 2 0 0 7 0 0 43 43 43 16 16 16 16

0 0 0 2 0 0 7 0 0 43 16 16 16 16 16 16

0 0 0 2 0 0 7 0 0 43 43 43 16 16 16 16

0 0 0 2 0 0 7 16 16 43 16 16 16 16 16 16

0 0 0 0 14 14 16 16 16 43 43 43 16 16 16 16

0 0 0 0 16 16 16 16 16 16 16 16 16 16 16 160 0 0 0 16 16 16 16 16 16 16 16 16 16 16 16

0 24 16 16 16 16 26 26 26 16 64 16 0 0 0 0

0 24 16 16 16 16 26 16 16 16 64 16 0 0 0 0

0 24 16 24 16 16 26 16 16 16 64 16 64 0 0 0

0 24 24 24 24 16 26 26 26 16 64 64 64 64 0 0

0 0 0 24 0 0 0 0 26 16 0 0 64 0 0 0

0 0 0 24 0 0 26 26 26 16 0 0 64 0 0 0

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 00 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

0 16121 82

0 0 0 0 0 0 0 0 0 0 0 0 16 16 16 16

0 0 0 2 0 0 7 0 0 43 43 43 16 16 16 16

0 0 0 2 0 0 7 0 0 43 16 16 16 16 16 16

0 0 0 2 0 0 7 0 0 43 43 43 16 16 16 16

0 0 0 2 0 0 7 16 16 43 16 16 16 16 16 16

0 0 0 0 14 14 16 16 16 43 43 43 16 16 16 16

0 0 0 0 16 16 16 16 16 16 16 16 16 16 16 160 0 0 0 16 16 16 16 16 16 16 16 16 16 16 16

0 24 16 16 16 16 26 26 26 16 64 16 63 63 63 63

0 24 16 16 16 16 26 16 16 16 64 16 63 63 63 63

0 24 16 24 16 16 26 16 16 16 64 16 64 63 63 63

0 24 24 24 24 16 26 26 26 16 64 64 64 64 63 63

0 0 0 24 63 63 63 63 26 16 63 63 64 63 63 63

0 0 0 24 63 63 26 26 26 16 63 63 64 63 63 63

0 0 0 0 63 63 63 63 63 63 63 63 63 63 63 630 0 0 0 63 63 63 63 63 63 63 63 63 63 63 63

0 16 6368 82 53

0 0 0 0 0 0 0 0 0 0 0 0 46 46 46 46

0 0 0 2 0 0 7 0 0 43 43 43 46 46 46 46

0 0 0 2 0 0 7 0 0 43 46 46 46 46 46 46

0 0 0 2 0 0 7 0 0 43 43 43 46 46 46 46

0 0 0 2 0 0 7 16 16 43 46 46 46 46 46 46

0 0 0 0 14 14 16 16 16 43 43 43 46 46 46 46

0 0 0 0 16 16 16 16 16 16 16 16 46 46 46 460 0 0 0 16 16 16 16 16 16 16 16 46 46 46 46

0 24 16 16 16 16 26 26 26 16 64 16 63 63 63 63

0 24 16 16 16 16 26 16 16 16 64 16 63 63 63 63

0 24 16 24 16 16 26 16 16 16 64 16 64 63 63 63

0 24 24 24 24 16 26 26 26 16 64 64 64 64 63 63

0 0 0 24 63 63 63 63 26 16 63 63 64 63 63 63

0 0 0 24 63 63 26 26 26 16 63 63 64 63 63 63

0 0 0 0 63 63 63 63 63 63 63 63 63 63 63 630 0 0 0 63 63 63 63 63 63 63 63 63 63 63 63

0 16 46 6368 46 36 53

0 0 0 0 0 0 0 0 0 0 0 0 46 46 46 46

0 0 0 2 0 0 7 0 0 43 43 43 46 46 46 46

0 0 0 2 0 0 7 0 0 43 46 46 46 46 46 46

0 0 0 2 0 0 7 0 0 43 43 43 46 46 46 46

10 10 0 2 0 0 7 16 16 43 46 46 46 46 46 46

10 10 0 0 14 14 16 16 16 43 43 43 46 46 46 46

10 10 10 10 16 16 16 16 16 16 16 16 46 46 46 4610 10 10 10 16 16 16 16 16 16 16 16 46 46 46 46

10 24 16 16 16 16 26 26 26 16 64 16 63 63 63 63

10 24 16 16 16 16 26 16 16 16 64 16 63 63 63 63

10 24 16 24 16 16 26 16 16 16 64 16 64 63 63 63

10 24 24 24 24 16 26 26 26 16 64 64 64 64 63 63

10 10 10 24 63 63 63 63 26 16 63 63 64 63 63 63

10 10 10 24 63 63 26 26 26 16 63 63 64 63 63 63

10 10 10 10 63 63 63 63 63 63 63 63 63 63 63 6310 10 10 10 63 63 63 63 63 63 63 63 63 63 63 63

0 10 16 46 6338 30 46 36 53

0 0 0 0 0 0 0 0 0 0 0 0 46 46 46 46

0 0 0 2 0 0 7 0 0 43 43 43 46 46 46 46

0 0 0 2 0 0 7 0 0 43 46 46 46 46 46 46

0 0 0 2 0 0 7 0 0 43 43 43 46 46 46 46

10 10 0 2 0 0 7 16 16 43 46 46 46 46 46 46

10 10 0 0 14 14 16 16 16 43 43 43 46 46 46 46

10 10 10 10 16 16 16 16 16 16 16 16 46 46 46 4610 10 10 10 16 16 16 16 16 16 16 16 46 46 46 46

10 24 16 16 16 16 26 26 26 16 64 16 63 63 63 63

10 24 16 16 16 16 26 16 16 16 64 16 63 63 63 63

10 24 16 24 16 16 26 16 16 16 64 16 64 63 63 63

10 24 24 24 24 16 26 26 26 16 64 64 64 64 63 63

10 10 10 24 62 62 62 62 26 16 62 62 64 63 63 63

10 10 10 24 62 62 26 26 26 16 62 62 64 63 63 63

10 10 10 10 62 62 62 62 62 62 62 62 63 63 63 6310 10 10 10 62 62 62 62 62 62 62 62 63 63 63 63

0 10 16 46 62 6338 30 46 36 26 27

0 0 0 0 5 5 5 5 5 5 5 5 46 46 46 46

0 0 0 2 5 5 7 5 5 43 43 43 46 46 46 46

0 0 0 2 5 5 7 5 5 43 46 46 46 46 46 46

0 0 0 2 5 5 7 5 5 43 43 43 46 46 46 46

10 10 0 2 5 5 7 16 16 43 46 46 46 46 46 46

10 10 0 0 14 14 16 16 16 43 43 43 46 46 46 46

10 10 10 10 16 16 16 16 53 53 53 53 46 46 46 4610 10 10 10 16 16 16 16 53 53 53 53 46 46 46 46

10 24 16 16 16 16 26 26 26 53 64 53 63 63 63 63

10 24 16 16 16 16 26 53 53 53 64 53 63 63 63 63

10 24 16 24 16 16 26 53 53 53 64 53 64 63 63 63

10 24 24 24 24 16 26 26 26 53 64 64 64 64 63 63

10 10 10 24 62 62 62 62 26 53 62 62 64 63 63 63

10 10 10 24 62 62 26 26 26 53 62 62 64 63 63 63

10 10 10 10 62 62 62 62 62 62 62 62 63 63 63 6310 10 10 10 62 62 62 62 62 62 62 62 63 63 63 63

0 5 10 16 46 53 62 6316 22 30 25 36 21 26 27

Segmentation maximale à partir du résultat contraint par

le quadtree0 0 0 0 5 5 5 5 5 5 5 5 46 46 46 46

0 0 0 2 5 5 7 5 5 43 43 43 46 46 46 46

0 0 0 2 5 5 7 5 5 43 46 46 46 46 46 46

0 0 0 2 5 5 7 5 5 43 43 43 46 46 46 46

10 10 0 2 5 5 7 16 16 43 46 46 46 46 46 46

10 10 0 0 14 14 16 16 16 43 43 43 46 46 46 46

10 10 10 10 16 16 16 16 53 53 53 53 46 46 46 4610 10 10 10 16 16 16 16 53 53 53 53 46 46 46 46

10 24 16 16 16 16 26 26 26 53 64 53 63 63 63 63

10 24 16 16 16 16 26 53 53 53 64 53 63 63 63 63

10 24 16 24 16 16 26 53 53 53 64 53 64 63 63 63

10 24 24 24 24 16 26 26 26 53 64 64 64 64 63 63

32 32 32 24 62 62 62 62 26 53 62 62 64 68 68 68

32 32 32 24 62 62 26 26 26 53 62 62 64 68 68 68

32 32 32 32 62 62 62 62 62 62 62 62 68 68 68 6832 32 32 32 62 62 62 62 62 62 62 62 68 68 68 68

0 5 10 16 32 46 53 62 63 6816 22 16 25 14 36 21 26 13 14

0 0 1 1 5 5 6 6 38 38 40 40 46 46 46 46

0 0 1 2 5 5 7 6 38 39 41 41 46 46 46 46

0 0 3 4 5 5 8 9 42 43 44 44 46 46 46 46

0 0 3 4 5 5 8 9 42 43 45 45 46 46 46 46

10 10 11 12 13 13 15 16 47 48 49 49 46 46 46 46

10 10 11 11 14 14 16 16 47 48 50 50 46 46 46 46

10 10 10 10 17 17 17 17 51 51 51 51 46 46 46 4610 10 10 10 17 17 17 17 51 51 51 51 46 46 46 46

18 19 20 20 25 25 26 26 52 53 54 55 63 63 63 63

18 19 20 20 25 25 26 27 53 53 54 55 63 63 63 63

21 22 23 24 28 28 30 31 56 56 58 59 64 65 63 63

21 22 24 24 29 28 30 30 57 56 58 58 64 64 63 63

32 32 33 34 35 35 36 36 60 61 62 62 66 67 68 68

32 32 33 34 35 35 37 37 60 61 62 62 66 67 68 68

32 32 32 32 35 35 35 35 62 62 62 62 68 68 68 6832 32 32 32 35 35 35 35 62 62 62 62 68 68 68 68

0 0 0 0 5 5 5 5 5 5 5 5 46 46 46 46

0 0 0 2 5 5 7 5 5 43 43 43 46 46 46 46

0 0 0 2 5 5 7 5 5 43 46 46 46 46 46 46

0 0 0 2 5 5 7 5 5 43 43 43 46 46 46 46

10 10 0 2 5 5 7 16 16 43 46 46 46 46 46 46

10 10 0 0 14 14 16 16 16 43 43 43 46 46 46 46

10 10 10 10 16 16 16 16 53 53 53 53 46 46 46 4610 10 10 10 16 16 16 16 53 53 53 53 46 46 46 46

10 24 20 20 20 20 26 26 26 53 64 53 63 63 63 63

10 24 20 20 20 20 26 53 53 53 64 53 63 63 63 63

10 24 20 24 20 20 26 53 53 53 64 53 64 63 63 63

10 24 24 24 24 20 26 26 26 53 64 64 64 64 63 63

32 32 32 24 35 35 35 35 26 53 62 62 64 68 68 68

32 32 32 24 35 35 26 26 26 53 62 62 64 68 68 68

32 32 32 32 35 35 35 35 62 62 62 62 68 68 68 6832 32 32 32 35 35 35 35 62 62 62 62 68 68 68 68

0 5 10 16 20 32 35 46 53 62 63 6816 22 16 13 12 14 14 36 21 12 13 14

0 0 0 0 5 5 6 6 6 6 6 6 46 46 46 46

0 0 0 2 5 5 7 6 6 43 43 43 46 46 46 46

0 0 0 2 5 5 7 6 6 43 46 46 46 46 46 46

0 0 0 2 5 5 7 6 6 43 43 43 46 46 46 46

10 10 0 2 5 5 7 16 16 43 46 46 46 46 46 46

10 10 0 0 14 14 16 16 16 43 43 43 46 46 46 46

10 10 10 10 16 16 16 16 51 51 51 51 46 46 46 4610 10 10 10 16 16 16 16 51 51 51 51 46 46 46 46

10 24 20 20 20 20 26 26 26 53 64 51 63 63 63 63

10 24 20 20 20 20 26 53 53 53 64 51 63 63 63 63

10 24 20 24 20 20 26 53 53 53 64 51 64 63 63 63

10 24 24 24 24 20 26 26 26 53 64 64 64 64 63 63

32 32 32 24 35 35 35 35 26 53 62 62 64 68 68 68

32 32 32 24 35 35 26 26 26 53 62 62 64 68 68 68

32 32 32 32 35 35 35 35 62 62 62 62 68 68 68 6832 32 32 32 35 35 35 35 62 62 62 62 68 68 68 68

0 5 6 10 16 20 32 35 46 51 53 62 63 6816 10 12 16 13 12 14 14 36 11 10 12 13 14

0 0 0 0 5 5 6 6 6 6 6 6 46 46 46 46

0 0 0 2 5 5 7 6 6 43 43 43 46 46 46 46

0 0 0 2 5 5 7 6 6 43 46 46 46 46 46 46

0 0 0 2 5 5 7 6 6 43 43 43 46 46 46 46

10 10 0 2 5 5 7 16 16 43 46 46 46 46 46 46

10 10 0 0 14 14 16 16 16 43 43 43 46 46 46 46

10 10 10 10 17 17 17 17 51 51 51 51 46 46 46 4610 10 10 10 17 17 17 17 51 51 51 51 46 46 46 46

10 24 20 20 20 20 26 26 26 53 64 51 63 63 63 63

10 24 20 20 20 20 26 53 53 53 64 51 63 63 63 63

10 24 20 24 20 20 26 53 53 53 64 51 64 63 63 63

10 24 24 24 24 20 26 26 26 53 64 64 64 64 63 63

32 32 32 24 35 35 35 35 26 53 62 62 64 68 68 68

32 32 32 24 35 35 26 26 26 53 62 62 64 68 68 68

32 32 32 32 35 35 35 35 62 62 62 62 68 68 68 6832 32 32 32 35 35 35 35 62 62 62 62 68 68 68 68

0 5 6 10 16 17 20 32 35 46 51 53 62 63 6816 10 12 16 5 8 12 14 14 36 11 10 12 13 14

0 0 1 1 5 5 6 6 38 38 38 38 46 46 46 46

0 0 1 2 5 5 7 6 38 39 39 39 46 46 46 46

0 0 1 2 5 5 7 6 6 43 46 46 46 46 46 46

0 0 1 2 5 5 7 6 6 43 43 43 46 46 46 46

10 10 1 2 5 5 7 16 16 48 46 46 46 46 46 46

10 10 1 1 14 14 16 16 16 48 48 48 46 46 46 46

10 10 10 10 17 17 17 17 51 51 51 51 46 46 46 4610 10 10 10 17 17 17 17 51 51 51 51 46 46 46 46

18 19 20 20 20 20 26 26 26 53 58 51 63 63 63 63

18 19 20 20 20 20 26 53 53 53 58 51 63 63 63 63

18 19 20 24 20 20 30 53 53 53 58 51 64 63 63 63

18 19 24 24 24 20 30 30 30 53 58 58 64 64 63 63

32 32 32 24 35 35 35 35 37 53 62 62 64 68 68 68

32 32 32 24 35 35 37 37 37 53 62 62 64 68 68 68

32 32 32 32 35 35 35 35 62 62 62 62 68 68 68 6832 32 32 32 35 35 35 35 62 62 62 62 68 68 68 68

0 0 1 1 5 5 6 6 38 38 38 38 46 46 46 46

0 0 1 2 5 5 7 6 38 39 39 39 46 46 46 46

0 0 1 2 5 5 7 9 9 43 44 44 46 46 46 46

0 0 1 2 5 5 7 9 9 43 45 45 46 46 46 46

10 10 11 12 13 13 15 16 47 48 49 49 46 46 46 46

10 10 11 11 14 14 16 16 47 48 50 50 46 46 46 46

10 10 10 10 17 17 17 17 51 51 51 51 46 46 46 4610 10 10 10 17 17 17 17 51 51 51 51 46 46 46 46

18 19 20 20 25 25 26 26 26 53 58 55 63 63 63 63

18 19 20 20 25 25 26 27 53 53 58 55 63 63 63 63

18 19 20 24 25 25 30 27 56 56 58 55 64 63 63 63

18 19 24 24 24 25 30 30 30 56 58 58 64 64 63 63

32 32 32 34 35 35 35 35 60 56 62 62 64 68 68 68

32 32 32 34 35 35 37 37 60 56 62 62 64 68 68 68

32 32 32 32 35 35 35 35 62 62 62 62 68 68 68 6832 32 32 32 35 35 35 35 62 62 62 62 68 68 68 68

À partir du résultat ‘quadtree’

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 2 0 0 7 0 0 43 43 43 0 0 0 0

0 0 0 2 0 0 7 0 0 43 0 0 0 0 0 0

0 0 0 2 0 0 7 0 0 43 43 43 0 0 0 0

0 0 0 2 0 0 7 0 0 43 0 0 0 0 0 0

0 0 0 0 14 14 0 0 0 43 43 43 0 0 0 0

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 00 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

0 24 0 0 0 0 26 26 26 0 64 0 0 0 0 0

0 24 0 0 0 0 26 0 0 0 64 0 0 0 0 0

0 24 0 24 0 0 26 0 0 0 64 0 64 0 0 0

0 24 24 24 24 0 26 26 26 0 64 64 64 64 0 0

0 0 0 24 0 0 0 0 26 0 0 0 64 0 0 0

0 0 0 24 0 0 26 26 26 0 0 0 64 0 0 0

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 00 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

0203

Hypothèses : 4-connexité, coût d’1 arête / ct(Ri,Rj) = |RiRj| si contraste(RiRj)=0, ct(Ri,Rj)=+ sinon

Fusion de régions dans un graphe

• Exemple :

#R = 5 #R = 8#R = 4

#R = 12 #R = 16 #R = 20

Ligne de partage des eaux : définition

• Postulat : image = une surface topographique / niveau de gris = altitude

0 0 2 1 0 5 2 0

0 0 4 5 7 1 6 0

9 6 3 5 3 0 4 3

8 6 4 4 1 0 2 1

9 7 5 2 2 4 2 1

0 1 3 0 2 6 5 4

0 3 3 1 4 6 7 8

0 1 2 2 3 4 9 9

0 0 2 1 0 5 2 0

0 0 4 5 7 1 6 0

9 6 3 5 3 0 4 3

8 6 4 3 2 0 2 1

9 7 5 2 2 4 2 1

0 1 3 0 2 6 5 4

0 3 1 1 4 6 7 8

0 1 2 2 3 4 9 9

Cas ‘facile’ Cas ‘difficile’

0 0 2 1 0 5 2 0

0 0 4 5 7 1 6 0

9 6 3 5 3 0 4 3

8 6 4 4 1 0 2 1

9 7 5 2 2 4 2 1

0 1 3 0 2 6 5 4

0 3 3 1 4 6 7 8

0 1 2 2 3 4 9 9

Ligne de partage des eaux : définition

• Ligne de partage des eaux (LPE) par immersion à partir des minima régionaux mi, faire croître niveau des eaux progressivement de sorte que :

(i) A chaque fois que la hauteur de l’eau atteint l’altitude d’un minimum régional, un nouveau bassin versant est créé

(ii) A chaque fois que deux bassins se rencontrent, on empêche leur fusion en construisant une “digue”.

LPE = ensemble des digues.

LPE par immersion : algorithme• Algorithme :

– On note B(i) l’image binaire des valeurs ys (de Y) ≤ i

– Initialisation : W-1=

– Pour i variant de 0 à imax

• {mi} = {x : x B(i), x CC{mi-1}} =

• W(i) = IZB(i)(W(i-1)) {mi}

– LPE =

• Calcul de IZ géodésique : IZX(Y)

– Initialiser IZX(Y) à Y

– Initialiser la liste L à X-Y – Tant que L non vide et |L| varie :

• Pour tout pixel de L : – calculer s’il peut se rattacher à IZX(Y) par épaississement

– si oui, mettre sa valeur à 1 dans IZX(Y) et le retirer de L

1sup

0iBiB

niBS

n

maxiW

Les mj sont les nouveaux minima

apparus à l’itération iZones d’influence géodésiques des bassins versants obtenus à l’it. précédente dans l’image bin.

courante des valeurs i

LPE : exemple (© Course on Math. Morphology, J. Serra)

Image initiale : 4 niveaux de gris

1. minima pour i=0, B(0)=W(0) ;

2. B(1)-B(0)

W(1) : minima apparus à i=1 zones d’influence géodésiques

de W(0) dans B(1)

1. W(1)2. B(2)-W(1) W(2) : zones d’influence

géod. de W(1) dans B(2)

Ligne de partage des eaux superposée à

l’image initiale

LPE : Application à la segmentation d’une image en

niveaux de grisUtiliser l’image de la norme du gradients

Risque de sur-segmentation

→ discrétiser les valeurs entre 0 et imax (#régions)

→ filtrer PB l’image du gradient (e.g. ouverture, fermeture)

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 00 1 1 1 1 0 0 0 0 0 0 0 0 0 0 00 1 1 1 1 0 0 0 0 0 2 2 0 0 0 00 1 1 1 1 0 0 0 0 2 2 2 2 0 0 00 1 1 1 1 0 0 0 2 2 1 1 2 2 0 00 0 0 0 0 0 0 0 2 2 1 1 2 2 0 00 0 0 0 0 0 0 0 0 2 2 2 2 0 0 00 0 0 0 0 0 0 0 0 0 2 2 0 0 0 00 0 0 0 0 0 0 0 0 0 0 0 0 0 0 00 0 0 0 3 0 0 0 0 0 0 0 0 0 0 00 0 0 3 3 3 0 0 0 0 0 0 0 0 0 00 0 0 3 3 3 0 0 0 0 0 0 0 0 0 00 0 3 3 3 3 3 0 0 0 0 0 0 0 0 00 0 3 3 3 3 3 0 0 0 0 0 0 0 0 00 3 3 3 3 3 3 3 0 0 0 0 0 0 0 00 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 00 2 1 1 2 1 0 0 0 0 2 2 0 0 0 00 1 0 0 1 1 0 0 0 4 4 4 4 0 0 00 1 0 0 1 1 0 0 4 4 1 1 4 4 0 00 2 1 1 2 1 0 2 4 1 2 2 1 4 2 00 1 1 1 1 0 0 2 4 1 2 2 1 4 2 00 0 0 0 0 0 0 0 4 4 1 1 4 4 0 00 0 0 0 0 0 0 0 0 4 4 4 4 0 0 00 0 0 0 3 0 0 0 0 0 2 2 0 0 0 00 0 0 6 3 6 0 0 0 0 0 0 0 0 0 00 0 3 6 0 6 3 0 0 0 0 0 0 0 0 00 0 6 3 0 3 6 0 0 0 0 0 0 0 0 00 3 6 0 0 0 6 3 0 0 0 0 0 0 0 00 6 3 0 0 0 3 6 0 0 0 0 0 0 0 00 3 3 3 3 3 3 3 3 0 0 0 0 0 0 00 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

Ligne de partage des eaux

• Exemple :

Fermeture sur gradient morphologique

Ouverture sur gradient morphologique

Gradient morphologique, boule 33 8-connexité

#R = 25 #R = 15 #R = 15

LPE : Application à la segmentation

• Cas d’objets binaires circulaires : utiliser image des distances inverses mais risque de sur-segmentation

utiliser la reconstruction de l’image des distances diminuée d’une faible valeur sous l’image des distances (rq: SKIZ positionne mal les frontières pour objets de tailles différentes)

• Cas d’1 image en niveaux de gris : utiliser l’image des gradients mais risque de sur-segmentation

utiliser la technique du swamping pour imposer les minima locaux à considérer (et seulement ceux-là)

• Autres cas d’1 image en niveaux de gris : utiliser image top-hat / top-hat conjugué

LPE : exemple 1 (© I. Bloch ENST)

Image binaire initiale

Image des distances (fausses couleurs)

LPE sur image des distances

inversée

LPE sur image reconstruite de la distance -2 sous

la distance

Image du gradientaprès fermeture

LPE correspondante

LPE : exemple 2 (© I. Bloch ENST)

Image du gradient après reconstruction par swamping

LPE correspondante

Approches variationnelles (I)• Energie de Gibbs (Geman & Geman, 1984) →

1ère méthode variationnellePb : estimer x (champ des labels) connaissant y (champ des

observations) définir :(i) un modèle ‘d’attache aux données’, i.e. reliant X et Y,

ET (ii) un modèle a priori pour X, i.e. favorisant certains types de solutions Ex. : modèles ‘réguliers’ i.e. favorise

pixels voisins de même label

Solution du Maximum A Posteriori (MAP) :

Somme des potentiels des cliques sur le voisinage

• Cas d’un champ de Markov caché (X,Y) avec |S| l’espace des états de X

• P(X = x,Y = y) = P(Y = y / X = x).P(X = x)

• Hypothèses supplémentaires :

avec

Ss

sssCc

sc yxUcsxUZ

yYxXP ,),(exp, 01

Sx Cc

sc csxUZ ),(expConstante de normalisation issue de la distribution a priori

P(Y=y / X=x) = sS P(Ys=ys / Xs=xs) (indép. cond. à X)sS, P(Ys=ys / Xs=xs) > 0 U0,s (xs,ys)=-ln(P(ys /xs))

Approches variationnelles (II)• Exemple de distribution a posteriori

– Y gaussien conditio. aux classes

– Loi a priori = modèle de Potts (i,j) =

P(X=x / Y=y) = P(Y=y / X=x).P(X=x)/P(Y=y)

• Cas plus général : avec ‘processus ligne’Énergie à minimiser :

où hs et vs {0,1} indiquent les bords horizontaux et verticaux, et Z est l’image des moyennes des classes :

ss

sx

x

xssss

yyxU

.ln

., 2

2 2

20

tstsc xxxxU ,.., 21

Ss Vttsx

x

xs

ss

s

s xxy

Z,ln

.exp

21

22

2

12

jissssjissjisss

G hvhzzvzzzyxE,

21,

2,1

21.1.

sxszSs ,

Approches variationnelles (III)• Principes :

– Il existe une méthode de détection des frontières qui soit universelle (indépendante du type d’image)

– La précédente détection doit présenter une invariance spatiale et d’échelle

– Les résultats doivent pouvoir être comparés quantitativement (valeurs des énergies respectives)

• Fonctionnelle d’énergie comprend des termes :– D’autosimilarité des régions (pour le type d’image

considéré : canaux fréquentiels, paramètres de texture…)

– La taille, la régularité et la localisation des frontières de régions

Fonctionnelle de Mumford & Shah (I)• Cadre fonctionnel :

soit R2 un ouvert rectangulaire, soient les images u0 (observation) et u (restauration), de → [0,1], et soit K un ensemble fermé définissant les contours de u, alors

KLongueurdxdyudxdyuuKuEK

MS ..,\

220

s

ss uu2

0

ssjissjis huuvuu 1.1.

21,

2,1

s

ss hv

• Conjecture : (u,K) minimiseur de EMS tel que1. u C1()

2. K est une union finie d’arcs réguliers tels que• au plus 3 arcs se rencontrent en 1 point triple tel que les angles

entre chacun d’eux soient 2/3• Au plus 1 arc peut rencontrer en 1 point et perpendiculairement

Fonctionnelle de Mumford & Shah (II)

• Cas particulier :– u est constante sur chaque région : sRi, u(x,y)=gi=cst

Connaissant K, u est donné E(u,K)=E(K)La régularisation repose entièrement sur la minimisation

des longueur de contoursParamètre définit l’échelle de perception de l’image

i Ki Ri R

MS

iii

dldxdyyxudxdyyxuyxuKuE .,.,,,22

0

iRi

i dxdyyxuRSurface

g ,1

0

i Ki R

iMS

ii

dldxdyyxugKuE .,, 200

croissance de région : absence de critère sur

contours génère régions irrégulières, étroites, petites…

faible segmentation ‘fine’ croit segmentation devient de + en + ‘grossière’

Preuve : (i) soit 1 courbe c1 de K et K1 la seg. obtenue en supprimant c1 (K1 est 1-maximale) ; c1 contient au max 2 intersections avec K1

(ses extrémités si c’est 1 courbe de Jordan ouverte).(ii) Si c1 est fermée, c’est la seule courbe qui disparaît, sinon s’il y a

intersection de 3 courbes, les 2 autres courbes fusionnent.

Propriétés de Segmentation 1-maximale pas de frontière interne à 1 région

Soit K 1 seg. 1-maximale / #R>1 2 régions R1 et R2 / (R1,R2) est 1 courbe de Jordan ((s,s’)]0,1[, ss‘ c(s)c(s’) )

Soit K 1 seg. 1-maximale / #R= K est l’union de -1 courbes de Jordan sans segment commun

Soit K 1 seg. 1-maximale / #R=, #courbes géométriques=, #croissements géométriques= (i) : 2.(-1) et (ii) : 3.(-1)-2

Segmentation 2-maximale 0E(K’)-E(K)=

|R| a une borne inférieure et l(R) a une borne supérieure

|R|1/2 Cste.l(R) élimination des régions trop étroites

jiR

jR

iRR

ij RRldxdyugdxdyugdxdyug

jiji

,.20

20

20

KuEKuEMS ,,0

K est n-maximale si pour tout n-upplet de régions, la segmentation K’ obtenue par

fusion de ces n régions vérifie E(K’)>E(K)

22

4

.

infsup.288#

C

ggSR

2infsup.,min,. ggRRRRl jiji 2infsup.

.

ggR

CRN

ii

#régions voisines de Ri

Preuve :

rique)isopérimét const. ( . et

infsup..

infsup.,. , de voisine

2

2

CRCRl

ggRRNRl

ggRRRlRR jj

2

6

33

infsup.288

.

ggS

CR

augmenter n permet d’éliminer les petites régions 22 infsup..#infsup.. ggSRggRRNRl

Preuve :

R

gg

C

S

RR

gg

C

S

RRNS

RRR

RS

RRRCardSR

jjj

jji

i

.#3 et

infsup

..

2

#

4

#

infsup

..

2

#,

#

2/

2

#

#

2

2

2

Preuve :

222

4

222

4

infsup.

.

.

infsup.288

infsup.

.#

.

infsup.288

ggR

C

C

ggS

ggR

CRNR

C

ggS

Résolution multiéchelle de Koepfler

• Algorithme– Soit la segmentation triviale : #R=|S|, soit 0– Tant que #R>nbre de régions souhaité

• Pour i[1,#R]– Pour chaque région Rj adjacente à Ri, calculer jj=|Rj|.|Ri|/(|

Rj|+|Ri|)||gi-gj||2/l((Ri,Rj))

• = minjj(jj)+• Parcourir la liste des régions, et fusionner celles telles

que E(K\(Ri,Rj)-E(K)<0

• Actualiser #R

• Préliminaires : soit Ri et Rj disjointes|RiRj|(RiRj)= |Ri|(Ri)+ |Rj|(Rj)

|RiRj|2(RiRj)=|Ri|2(Ri)+|Rj|2(Rj)+ |Rj|.|Ri|/(|Rj|+|Ri|)((Ri)+(Rj))2

RjRji

jiR

ji

jiRR

ji

jiR

RjRji

jiR

ji

j

RssR

ji

i

Rss

RjRji

jiR

ji

jR

ji

i

RRss

RRjiRRs

sRRs

RRsRRs

RRsRRsRRji

ijjii

ijj

ii

ijiji

jijiji

jiji

jijiji

RR

RR

RR

RR

RR

RR

RR

RR

RR

Rx

RR

Rx

RR

RR

RR

R

RR

Rx

RRxxx

xRR

.2..

..

.2..

.2..

...2

2222

2

2

222

2

2

2

22

2

2222

22

Approche variationnelle

• Exemple :

#R = 5 #R = 8#R = 4

#R = 12 #R = 16 #R = 20