Images binaires - 1 IMAGES BINAIRES 1. TOPOLOGIE Connexité Composantes connexes : étiquetage 2. METRIQUE Norme, courbure et orientation Transformée de

Images binaires - 1

IMAGES BINAIRES

1. TOPOLOGIE Connexité Composantes connexes : étiquetage

2. METRIQUE Norme, courbure et orientation Transformée de Hough Distance à une référence Paramètres morphométriques

3. TRAITEMENTS BINAIRES Traitements locaux par LUT Morphologie mathématique Squelettisation

4. EXTENSIONS MULTI-NIVEAUX Morphologie en niveaux de gris

FIN DE PRESENTATION

Voir Prétraitement des images :

Binarisation

Images binaires - 2

TOPOLOGIE

Topologie structure : connexité, dénombrement, nombre de connexité ( ou d’Euler )

Métrique mesure : distance, périmètre, surface

toutes notions sans ambiguïté dans R2, mais problèmes dans N2

NOTIONS DE TOPOLOGIE : CONNEXITE

Maillage carré : 4 voisins ( 4-connexité ) invariance en rotation de k./2

8 voisins ( 8-connexité ) invariance en rotation de k./4

connexité de 2 points : invariance : conservation de la connexité = homotopie

Maillage hexagonal : 6 voisins, en pratique approché par translation ½ pixel, ou interpolation

d’un réseau carré

{ } { }1, 2 X chemin 1 2 Xx x x xÎ Þ $ « Ì

Nombre de connexité : C = Nbre de composantes connexes – Nbre de trous C = Nbre de sommets + Nbre de faces – Nbre d’arêtes

Relation d’Euler : C {X} + C {X} = 1

Images binaires - 3

0 01 0

1 00 0

0 10 0

0 00 1

1 01 1

1 11 0

1 10 1

0 11 1

0 11 0

1 00 1

U

U

U

U U

U U

U 1 00 1

0 11 0

U

TOPOLOGIE ( 2 )

NOMBRE DE CONNEXITE

Calcul en 4-connexité : analyse de la maille élémentaire 2x2, sommet = élément bas / gauche

1 sommet :

1 face :

- 2 arêtes :

En tenant compte des symétries ( 4 sommets / maille )

4 x C4 = Nbre

- Nbre une analyse similaire mène au calcul de C8

+ Nbre

x x1 x

1 11 1

1 x1 x

x x1 1

0 01 0

1 01 0

0 11 0

1 11 0

0 01 1

1 01 1

0 11 1

1 11 1

1 01 0

1 11 0

1 01 1

1 11 1

0 01 1

1 01 1

0 11 1

1 11 1

Enumération des configurationspuis élimination des redondances

C4 = Nbre + Nbre - Nbre0 01 0

0 11 0

1 01 1

Images binaires - 4

TOPOLOGIE ( 3 )

8– ET 4–CONNEXITE

Vérification de la relation d’Euler sur une image binaire C {X} + C {X} = 1 :

Calcul de C4 Calcul de C8

Pixels à 1

{X} {X} {X}

Liens de connexité

C4 {X} =

4 – 0 = 4

C8 {X} =

1 – 1 = 0

{X} {X}C4 {X} =

2 – 1 = 1

C8 {X} =

1 – 4 = -3

Somme = 5 ! Somme = -3 !

Pour conserver la relation d’Euler il faut utiliser la 4-connexité pour {X} ( les régions à 1 )

la 8-connexité pour {X} ( le fond )

alors C4 {X} + C8 {X} = 1

Images binaires - 5

COMPOSANTES CONNEXES

ETIQUETAGE

C4 ne permet pas directement le dénombrement des composantes connexes ( les régions ) d’une

image binaire. De plus il faut pouvoir les différencier attribution d’un identificateur ou étiquette.

Etiquette = numéro identique attribué à chaque pixel d’une même composante connexe. La visualisation de l’image des étiquettes attribue donc une couleur par région.

procédure d’étiquetage ou de coloriage des régions

Principe : balayage de l’image par un motif 3 pixels ( A,B,C )

AB C

Si C ≠ 0 : les étiquettes de A et B déjà fixées imposent l’étiquette du pixel C Si C = 0 : pixel du fond, il reste invariant NB : initialiser bordures haute / gauche à 0 C1 C2

C6

C3

C5

C4

C7C2

A=0,B=1

C=B=1

C3

A=1,B=0

C=A=1

C4

A=B=1

C=A=1

C5

A=0,B=0

N=N+1

C=N=2

C6

A=1,B=2

C=min(A,B)=1

et équivalence

max(A,B) ~ C

2 ~ 1

C7

A=0,B=0

N=N+1

C=N=3

= 1= 2= 3

C1

A=0,B=0

N=N+1

C=N=1

N = Nbre étiquettes ( initialisé à 0 )

Images binaires - 6

COMPOSANTES CONNEXES ( 2 )

GESTION DES EQUIVALENCES

En cas d’équivalence ( exemple 2 ~ 1 ) : retour en arrière et ré-écriture de tous les « 2 » … lent !

mémorisation dans table puis second balayage global

étiquette équivalent ( étiquette )

Chaque ligne de la table d’équivalence est initialisée par son numéro :

0123

2 ~ 1

0113

re-étiquetage

pix = EQ( pix )

EQ

Pbs : pour une image Nx colonnes x Ny lignes

nombres maximum d’étiquettes créées ? nombre maximum d’équivalences à résoudre ?

EQ

Avant re-étiquetage :

renumérotation pournuméros consécutifs

0112

re-étiquetage

pix = EQ( pix )

Images binaires - 7


TABLE D’EQUIVALENCE

Dimension de la table d’équivalence :

nombre maximum d’étiquettes sur une ligne : Nx/2

sur 2 lignes : Nx étiquettes différentes, en damier

dans l’image Nx.Ny/2 nombre de bits des étiquette log2( Nx.Ny ) -1

exemple : 512x512 = 29.29 218 / 2 soit 17 bits

Nombre d’équivalences à résoudre ( fusions ) :

nombre maximum d’étiquettes : Nx/2

sur 2 lignes : Nx/2 fusions, en peigne

peigne isolé sur 3 lignes dans l’image ( Nx.Ny ) /6 fusions exemple : 512x512 maximum ~ 44000 équivalences

Réduction du nombre d’étiquettes et de fusions :

création nouvelle étiquette indispensable en C1 inutile en C2

attente avant création ( retard à l’étiquetage ) de 1…N pixels

en C1 aucune équivalence création et étiquetage a posteriori

en C3 : C2 ~ C1 pas de création, propagation d’étiquette

C1

C2 C3

Images binaires - 8


RETARD INFINI : SEGMENTS CONNEXES

Codage d’une image binaire par segments ( codage RLE « Run Length Encoding » ) :

mémorisation de liste : nbres de lignes et colonnes image

pour chaque ligne, nbre de segments,

colonnes début ( 0↑1 ) et fin ( 1↓0 ) de chaque segment

Ny Nx

Y1 Ns1 D0 F0 D1 F1

Y2 Ns2 D0 F0Intérêt compression, exemple :

taille d’origine : 33600 octets taille de liste : 1768 octets ( 5%, données sur 2 octets )

remarque : le codage RLE peut s’étendre à des images d’étiquettes, début et fin sont remplacés par numéro d’étiquette et nombre de pixel du segment

Etiquetage par connexité de segments, analogue à motif 3 pixels :segment sans voisin à ligne précédente nouvelle étiquette avec 1 voisin connexe à ligne précédente propagation d’étiquette N voisins connexes gestion des équivalences comme pour 3 pixels

Connexité : ( Dn(Y) ≤ Fk(Y-1) ) ET ( Fn(Y) ≥ Dk(Y-1) )

Images binaires - 9


50 100 150 200 250 300

50

100

150

200

250

50 100 150 200 250 300

50

100

150

200

250

1 – Binarisation : image ≤190

50 100 150 200 250 300

50

100

150

200

250

Analyse par motif 3 points

362 étiquettes sans retard80 étiquettes avec 3 attentes26 régions finales

2 - Etiquetage

Segments connexes

57 étiquettes temporaires26 régions finales

Comparaison : motif 3 points ( avec et sans retard à l’étiquetage ) et segments connexes

Images binaires - 10


CHAÎNES D’EQUIVALENCES

Equivalences en cascade ( étiquetage sans retard ) :

fusions multiples chaînées renumérotation de la table ( transitivité )

algorithme pour l’étiquette N : k=N; tant que (k ≠ EQ(k) ) k=EQ(k); EQ(N)=k;

Accélération de l’étiquetage : en C1 2 ~ 1 puis en C2 3 ~ 2 chaînage : 3 ~ 1

C1

C2

si pour la fusion A≠0, B≠0 : C = min(A,B); EQ( max(A,B) ) = C devient

A = EQ(A)C = min( A,B ) B vient d’être calculée donc B = EQ(B)EQ(A) = EQ(B) = C 2 écritures évitent le test du maximum

C1

C2

0123

C1 : 3 ~ 2

0122

EQ EQ 0112

EQ

C2 : 2 ~ 1

0111

EQ 3 ~ 2 2 ~ 1 1 ~ 1

: 3 ~ 1

Moins de cascades d’équivalences caréliminées pour ce type de configuration

0123

C1

0113

EQ 0111

C2



RUPTURE DE CHAÎNE D’EQUIVALENCES

Rupture de la chaîne d’équivalence :

en C1 : 3 ~ 2 puis en C2 : 3 ~ 1 avec l’algorithme C = min(A,B); EQ( max(A,B) ) = C

C1

C2

0123

EQ 0122

0121C1 C2

Pb : « 2 » reste isoléor 2 ~ 1 !

Solution : avec la nouvelle formulation complétée, si fusion A≠0, B≠0

A = EQ(A); C = min( A,B ); EQ(A) = EQ(B) = C

0123

EQ 0122

0112C1 C2

La connexité de « 2 » et « 1 » est résoluereste le chaînage 3 ~ 2 sans problème

forme finale de l’algorithme

A=2, B=3A=EQ(A)=2

A=3, B=1A=EQ(A)=2


50 100 150 200 250 300

50

100

150

200

250

50 100 150 200 250 300

50

100

150

200

250


50 100 150 200 250 300

50

100

150

200

250

1 - Binarisation

50 100 150 200 250 300

50

100

150

200

250

Seuillage : image ≤ 190

362 étiquettes sans retard80 étiquettes avec 3 attentes26 régions finales

2 - Etiquetage

Seuillage : image ≤ 210

343 étiquettes sans retard65 étiquettes avec 3 attentes26 régions finales( ≠ des précédentes )

EXEMPLES

Les couleurs sont modifiées selon la connexité des régions ( ici selon le seuil )

Les couleurs sont réutilisées modulo le nombre de couleurs distinctes affichables


METRIQUE

DISTANCE DE 2 POINTS : NORMES

Différentes normes dans le plan : distance (x0,y0)↔(x1,y1) = ( |x0-x1| N + |y0-y1| N ) 1/N

N = 2 : distance euclidienne D2 = sqrt( ∆x 2 + ∆y 2 ) Pb : complexité de calcul

N = 1 : « city bloc distance » D1 = |∆x| + |∆y|

N = ∞ : « chess board distance » D∞ = max( |∆x|, |∆y| )

Simulation numérique dans plan discret ∆x = 0…100, ∆y = 0…100 :

( % ) erreur relative par rapport à D2 moyenne D1 : 27 D∞ : -10

maximale D1 : 41 D∞ : 0 ( max par excès )

minimale D1 : 0 D∞ : -30 (max par défaut)

calculs simples mais erreurs trop importantes recherche d’une approximation

Combinaison de D1 et D∞, par optimisation : Dc = max( |∆x|, |∆y|, C.(|∆x|+|∆y|) )

critère moy = 0 C = .74171 moy = 0, max < 4.9, - min < 5.6

critère max = - min C = .74514 moy < 0.3, max < 5.4, - min < 5.4

critère de calcul simple C = ¾ moy < 0.7, max < 6.1, - min < 5.2

Pb : précision ?


10 20 30 40 50 60 70 80 90 100

10

20

30

40

50

60

70

80

90

100

METRIQUE ( 2 )

COURBES D’ ISODISTANCES

Points à distance 100 de l’origine :

Autre approche, partition angulaire :

10 20 30 40 50 60 70 80 90 100

10

20

30

40

50

60

70

80

90

100

D∞D1D2 ( référence )Dc ( C = ¾ )

D1 ≥ D2 ≥ D∞

3 zones angulaires ( évite « max » )

• horizontale : |∆x| > 2.|∆y| Da = |∆x| • verticale : |∆y| > 2.|∆x| Da = |∆y|• oblique Da = sqrt(2). (|∆x|+|∆y|)/2 ~ ¾ (|∆x|+|∆y|)

angles limites : atan(2) et atan(0.5) soit 63.5° et 26.5°

horizontale

oblique

vertic.

moy < -0.3, max < 6.1, - min < 10.4 mais donne information sur la direction par rapport à horizontale


ORIENTATION

CODAGE DES ORIENTATIONS

Zones angulaires, angles limites 63.5° et 26.5° :

limites optimales pour un codage par pas de /4 : 67.5° et 22.5°

• horizontale : |∆x| > 2.|∆y|• verticale : |∆y| > 2.|∆x| et utilisation du signe pour l’orientation• oblique sinon

Angle = k./4 ( modulo 2. ) k : code de Freeman

• ∆y ≥ 0, ∆x ≥ 0 : k = 0 ... 2• ∆y ≥ 0, ∆x < 0 : k = 2 ... 4• ∆y < 0, ∆x < 0 : k = 4 …6• ∆y < 0, ∆x ≥ 0 : k = 6 …8 (0)

k = 0( référence )

k = 1

k = 2

k = 3

k = 4

k = 5

k = 6

k = 7


ORIENTATION ( 2 )

CHAINE DE FREEMAN

Chaîne de Freeman = liste des codes de Freeman d’un contour de région

origine = coordonnées (x0,y0 ) du 1er point de la région

orientation courante présumée Fc = 0

algorithme de suivi point à point du contour (xc,yc) = (x0,y0) :

recherche point suivant en 8-connexité :

x0

y0

1 23456

1er point non nul dans l’ordre 16, motif tourné de k./4 selon Fc

création listes de x = xc+∆x, y = yc+∆y, F, ∆F

mise à jour du point courant : (xc,yc) = (x,y) et Fc = F si (xc,yc) ≠ (x0,y0) itération, sinon fin de suivi

yc

xc

1 2 3 4 5 6test :

∆F : 2 1 0 -1 -2 -3

F

∆x

∆y

01234567Fc

Table de recherchedu suivant selon Fc

23456701 56701

0-1-1-10111 -10111

-1-101110-1 1110-1


ORIENTATION ( 3 )

Propriétés de quasi-invariance :

invariance stricte en translation

à une « N-plication » des codes près en échelle

à une constante additive k près, modulo 8, en rotation de k./4

descripteur de forme

Chaîne dérivée, courbure :

liste constituée des ∆F : dérivée de l’orientation, invariante en rotation de k./4

x0

y0

F = { 0,7,5,4,4,2,1 }

correction de métrique : si F impair ( diagonale ) longueur associée au code = sqrt(2) si F pair longueur unitaire

courbure en fonction de l’abscisse curvilignemeilleure invariance en rotation

∆F = { -1,-1,-2,-1,0,-2,-1 }

remarques : longueur de liste = périmètre ici tous ∆F ≤ 0 aucune concavité

la liste peut être lissée ( moyenne glissante ) élimination des irrégularités locales


ORIENTATION ( 4 )

EXEMPLE : ORIENTATION ET COURBURE

Pour la visualisation les codes sont : orientation (1) : Fv = 3.F

courbure (2) : ∆Fv = 3.∆F

soit une résolution de /12 ( 15° )

La courbure est lissée par une moyenne 7 points puis mise à l’échelle [1…12]

+ (concave) : 7…12 - (convexe) : 1…6

les 2 courbures sont « comparables »

Contours extérieurs


ORIENTATION ( 5 )

TRANSFORMEE DE HOUGH

Transformation globale de l’espace image en un espace paramétrique.

But : rechercher des structures rectilignes dans une image binaire

Droite de l’espace (x,y) : y = x.tg( /2 + o ) + o / sin(o) soit o = x.cos(o) + y.sin(o)

Transformation : (x,y) (, ) | = x.cos() + y.sin()

Dans l’espace (, ) 1 point (x’,y’) un arc de sinusoïde N points alignés famille de N sinusoïdes

passant par (o, o) définissant la droite

Exemple, soient 3 points de (x,y) : (1,1),(2,0.5),(3,0)

Remarque : est algébrique, donc varie de 0 à les axesx et y sont centrés dans l’image tels que

x = L – Nl / 2 ; y = C – Nc /2

ainsi est l’orientation selon Freeman de la droite dans l’image

x

o

o D

y

0.5 1 1.5 2 3 3.5

0

L

C

o y

x


ORIENTATION ( 6 )

Algorithme : est discrétisé dans [0,] par pas de est discrétisé dansmax,maxpar pas de( oùmax = ½ diagonale )le tableauest initialisé à 0

pour chaque point p(x,y) à 1 et pour chaque valeur de dans [0,] incrémenter la case ( , (,x,y) )

en fin de traitement chaque case contient le nombre de points alignésselon la droite ( + .. + ) : histogramme bidimensionneldont les pics représentent des segments rectilignes.

Variante : utiliser le code de l’orientation du point p(x,y) et ne « voter » que pour cette case accélération du calcul. Exemple ci-dessous avec une résolution de /12

Image binaire et son contour

3 orientations : 0,6,9 soit 0,90°,135°5 droites supports des contours

Espace de Hough

La verticale comporte 2 segments disjoints de

même support


ORIENTATION ( 7 )

Noter :

- la périodicité en ( 0° 180° )

- la présence des 5 pics 2 à 0°, 2 à 90°, 1 à 135°

- les 2 segments verticaux ont été comptabilisés dans la même case de l’histogramme ( même support )

- le bruit de fond autour des pics

Des alignements accidentels ( 3 pts sont toujours alignés ! ), ou deserreurs d’orientation ou de localisation, ou encore un défaut de résolutionen ou provoquent une dispersion des votes localisation des pics plus complexe

( importance du choix de et )

Des objets rectilignes discontinus du faitdu bruit ( lacunes ) pourrons être reconstruits


DISTANCE A UNE REFERENCE

DISTANCE A UN ENSEMBLE DE POINTS

Distance d’un point à un ensemble de référence :

réfPD0

DN

D( P ↔ { réf } ) = min { D0,D1, … DN }

Méthode : le chemin P ↔ Pr Є { réf } est décomposé en cheminsélémentaires dont les coûts sont cumulés : pas horizontal ou vertical coût = 1 pas diagonal coût = sqrt(2)

P

Pr

CN = (7x1h, 3x1v )

C0 = (4x1h, 3x1v )

CPPr = min( C0,…,CN )

L’ensemble des coûts est ainsi calculé, d’où la distance :

D = min { CPPr | Pr Є { réf } } = min ( min { Ci } )

Optimisation : les coûts sont convertis en entiers en multipliant la distance par un coefficient : 1 → 2, sqrt(2) → 2x1.4 ~ 3 : approximation de 2 x distance euclidienne ( 13% par défaut ) 1 → 3, sqrt(2) → 3x1.4 ~ 4 : approximation de 3 x distance ( 8% par excès )

Distances dite de « chamfer » (2-3) ou (3-4)


DISTANCE A UNE REFERENCE ( 2 )

CARTE DES DISTANCES

Généralisation : distance de chaque point à l’ensemble de référence carte des distances

l’ensemble de référence est l’ensemble des points à 1 de l’image

algorithme, phase 1 complémentation image ( distance Pr ↔ { réf } = 0 )

bordure d’image mise à N ( N >> max coeff x distance )

1

1 1

1 1

0

0 0

0 0

99

0

0 0

0 0

phase 2 balayage de l’image par une fenêtre de 5 points, les coûts des points a,b,c,d sont soit déjà calculés ( sens du balayage ) soit imposés par la valeur de la bordure à une valeur neutre, les surcoûts sont ajoutés :

ed

cbae = min(a+C2, b+C1, c+C2, d+C1 ) avec (C1,C2) = (2,3) ou (3,4)



phase 2, propagation des distances, les points à N ne sont pas traités :

99

0

0 0

0 0

99

0 2 4 6 8 10

2 3 5 7 9 11

4 5 6 0 0 2

6 7 0 0 2 3

8 3 2 2 3 5

6 5 4 4 5 6

ici (C1,C2) = (2,3)

La causalité du balayage fait que les points en aval

ne sont pas pris en compte

D’où phase 3

phase 3 balayage inverse par motif symétrique : propagation inverse, les coûts initiaux sont recalculés

abc

dee = min( e, a+C2, b+C1, c+C2, d+C1 )

654456

532235

320024

200234

322332

544420

99

remarque : si (C1,C2) = (1,∞) distance D1 si (C1,C2) = (1,1) distance D∞



EXEMPLES

Distances des points objets au fond

Distance des points du fond à l’objet

La distance ( chamfer 2-3 ), valeur > 0est représentée par un niveau de gris :

distance croissante gris → blanc


DISTANCE GEODESIQUE

DISTANCE DANS UN ESPACE CONTRAINT

Distance d’un point à un ensemble de référence { réf }, avec espace interdit { int } :

distance euclidienne ≠ distance dite géodésique, longueur réelle du chemin

réf

int

distance euclidiennedistance géodésique ≥ distance euclidienne

L’espace interdit ( contrainte par pixel > 1 ) ne doit pas intervenir dans le calcul des coûts cumulés imposée à valeur N d’initialisation de bordure

Exemple : distance de chamfer (3-4) fond ( 0 : noir ) ↔ référence ( 1 : bleue ) avec contrainte ( 2 : rouge ), valeurs > 1 mises à N puis algorithme double balayage :

Zones interditesdistance ∞ ( N )

Référence,distance = 0


PARAMETRES DE COMPOSANTE CONNEXE

CARACTERISATION D’UNE REGION

Pour chaque composante connexe, calcul de paramètres morphométriques :

paramètres de base surface S = card { pixel(x,y) = 1 }

périmètre P = card { pixels contour }

le contour peut être intérieur ou extérieur à la région

compacité C = 4. S / P2 voir [ binarisation ]

centre de gravité G = xG = 1/S. (x | pixel(x,y) = 1 )

yG = 1/S. (y | pixel(x,y) = 1 )

axes d’inertie : vecteurs propres V1 et V2 de la matrice d’inertie M =

xx = 1/S. (x – xG)2 = 1/S. (x2) – xG2

avec xy = yx = 1/S. (x – xG).(y – yG) = 1/S. (x.y) – xG.yG

yy = 1/S. (y – yG)2 = 1/S. (y2) – yG2

soit : V1 : ( [xx – yy + sqrt( (xx-yy)2 + 4.xy2 )] / 2.xy , 1 )

V2 : ( [xx – yy – sqrt( (xx-yy)2 + 4.xy2 )] / 2.xy , 1 )

NB : si xy = 0 → V1,V2 : (0,1), (1,0)

xx xyyx yy

V1 ┴ V2

Inertie.mws


PARAMETRES DE COMPOSANTE CONNEXE ( 2 )

Paramètres de convexité, rectangle englobant :changement d’axes (x,y) → axes d’inertie V1,V2

rotation d’angle α : tan(2α) = 2.xy / ( xx – yy ) soit

dimensions du rectangle englobant :

L = max(xr) – min(xr)

l = max(yr) – min(yr)

élongation = L / l

rapport des surfaces = S / (L.l)

cos( ) sin( ).

sin( ) cos( )

xr x

yr y

a a

a a

-=

y

x

V1V2

α

Convexité, enveloppe convexe d’une région :convexité : pour tous couples de points P1,P2 de la région,

non convexe convexe

Enveloppe convexe = forme englobante convexe

indice de concavité = S / ( aire enveloppe convexe )

{ }1 2segment P ...P régionÌ


TRAITEMENTS BINAIRES

TRAITEMENTS LOCAUX PAR LUT

Analyse du voisinage en 4- ou 8-connexité calcul d’un descripteur utilisé comme index :

4-connexité, les voisins sont numérotés 0 à 3, le descripteur est :

l’index adresse une table de décision ( LUT ) de taille 2 4 = 16

8-connexité, les voisins sont numéroté 0 à 7, la table comporte 2 x 256 positions :0,3

2 .Pii

iIndex

== å

3 2 1

4 P 0

5 6 70,7

2 .Pii

iIndex

== å

P=0 P=1

01..

P = LUT( P, Index )

LUT

les 2 cas P = 0 et P = 1 sont souvent traités en 2 passes successives sur l’image.les voisinages plus étendus sont difficiles à analyser : 5x5 → table de taille 2 24

~16.8 M positions !

Décision 0 / 1

Adressage de LUT

Application : élimination des lacunes et fausses alarmes isolées lissage ou régularisation des bordures d’objets détection de configurations de voisinage particulières, exemple : enveloppe convexe


TRAITEMENTS BINAIRES ( 2 )

Lacunes et fausses alarmes, configurations établies pour P0 = 0/1, toutes les autres config.

peuvent en être déduites par rotations de /2 : Pi P(i+2)modulo 8 et doivent être ajoutées

3 2 1

4 P 0

5 6 7

x 1 x

x 0 1

x 1 x

x 0 x

0 1 0

x 0 x

( x = indifférent )

Lacune : un 0 avec au moins 3 voisins à 1 est mis à 1P0+P2+P4+P6 >= 3 1

Fausse alarme : un 1 avec 4 voisins à 0 est mis à 0P0+P2+P4+P6 ≠ 0 1

Binarisation :

Img < 160 lacunesImg < 210 fausses alarmes


Lacunes comblées par 2 itérations ( vert )

x 1 x

x 0 1

x 1 x

0 0 x

0 1 1

0 0 x

0 0 0

0 1 x

0 0 x

Fausses alarmes éliminées ( orange )

Lissage des bordures, 2 passes successives, lissage des 0 puis des 1 :

Concavités :

(P0+P2+P4+P6) >= 3 1

Bordure W ( ouest ) aspérités ou pts saillants, notation Matlab :

~(P2 | P3 | P4 | P5 | P6) & (P0| ~P1| ~P3) 0

0 0 x

0 1 x

0 0 0

et rotations de /2




x 1 x

x 0 1

x 1 x

x x 1

x 0 1

x 1 1

x 1 1

x 0 1

x x 1

Enveloppe convexe, itérations jusqu’à stabilisation ( invariance ) de l’image, ici convexité 8-C :

P0 & P2 & P6 1P0 & P1 & P7 & P6 1P0 & P1 & P7 & P2 1

Contours lissés ( 0→1 vert, 1→0 orange )

Génération de LUT

Déficience de convexité = { E(X) – X }Point W, ajouter rotation de /2


MORPHOLOGIE MATHEMATIQUE

OPERATIONS DE BASE

Théorie ensembliste basée sur les travaux de Minkowski et Hadwiger, développée par Matheron et Serra.

Notations et définitions :

{ } { }ensemble objet | 1 fond | 0

origine d'un ensemble ( ) : point de référence

symétrique ( ) d'un ensemble par rapport à : s

X x x X x x

o X o

X o o

= = = =

{ }Addition de 2 ensembles et , ou addition de Minkovski :

( ) ( ) ( opération commutative ) dilatation | ( )

de par l'élément structurant :

z Z x Xs

X Z

Y X Z X z Z x Y y S y X

X S Y X S

Î Î= Å = = Þ = Ç ¹ Æ

= Å

U U

Dilatation

Xs(o)

X(o)

Ss(o)X(o)

( )sz S

X zÎU

{ }| ( )y S y XÇ ¹ Æ

S(o), l’élément structurant est caractérisé par son origine, sa forme et ses dimensions

Elément centré, symétrique, de taille minimale en 4-C ou 8-C :


MORPHOLOGIE MATHEMATIQUE ( 2 )

Ss(o)X(o)

( )sz S

X zÎI

{ }| ( )y S y XÇ =Æ

{ } { }Soustraction de 2 ensembles ( Hadwiger ) :

( ) érosion | ( ) | ( )

de par l'élément structurant :

z Zs

Y X Z X z Y y S y X y S y X

X S Y X S

Î= = Þ = Í = Ç =Æ

=

I

Erosion

$

$

{ }

{ } ( )

( ) ( )( )

:

| ( )

| ( )

Autres relations : ( inclusion )

1 2 1 2

1 2

s

s s

s

Y X S y S y X

Y y S y X X S X S X S

X S X X S

X S S X S S

X S S X

= = Ç =Æ ®

= Ç ¹ Æ = Å ® = Å

Ì Ì Å

Å Å = Å Å

=

Dualité des 2 opérations

$

$

$

$ $ $ ( )1 2sS SÅ

Itérations d’opérations :

puis S2S1

S



EXEMPLE : EROSION ET DILATATION

Erosion en 4-C et 8-C :

Les objets de taille inférieure à S disparaissent → pts oranges éliminés,la connexité n’est pas conservée( dissociation de régions ).

Dilatation en 4-C et 8-C :

Les trous de taille inférieure à S disparaissent → pts verts ajoutés, la connexité n’est pas conservée( fusions de régions voisines )

Pour les éléments structurants de taille minimale 4-C ou 8-C, l’érosion correspond à uneélimination d’un pixel de bordure, et la dilatation correspond à une croissance de un pixel en bordure. L’itération de ces opérations conduit donc à des croissances ou contractions de N pixels.

S 4-connexe S 8-connexe



CASCADES D’OPERATEURS

Erosion et dilation modifient la taille globale des régions, la succession des 2 opérations ramènent les objets à leurs dimensions par compensation.

Ci-dessous, exemples pour S = Ss 4-connexe.

Ouverture : érosion puis dilatation

{ }

{ }( ) ( ) | ( )

( ) | ( )

sY X S X S S S y S y X

S y S y X

= = Å = Ì =

Ç =Æ

d $

Fermeture : dilatation puis érosion

{ }( ) ( ) | ( )s sY X S X S S S y S y X= = Å = Ç ¹ Æ# $

sX S$

sX SÅ

X Sd

X S#

Propriétes :

( inclusion )

( ) ( dualité )

( ) et ( ) ( idempotence )

s

X S X X S

X S X S

X S S X S X S S X S

Ì Ì

=

= =

d

d

d d d

#

#

# # #



MISE EN OEUVRE ALGORITHMIQUE

Nous supposons ci-dessous que S est symétrique : S = Ss

Algorithmes basés sur des fonctions booléennes :

dilatation : pour tous pixels

érosion : pour tous pixels

Algorithmes basés sur les cartes des distances, pour S de taille 2.N+1 :

dilatation : calcul des distances dans fond à X puis mise à 1 de

érosion : calcul des distances dans X au fond puis mise à 1 de

Algorithmes basés sur une convolution ( image S ) :

dilatation :

érosion :

: ( ) ( 'ou' booléen )s S

x X x X sÎ

Î ® U

: ( ) ( 'et' booléen )s S

x X x X sÎ

Î ® I

{ }/1| ( )Xx dist x N<

{ }/ 0| ( )Xx dist x N<

{ }| ( ) ( ) 0Y X S y S y X image S= Å = Ç ¹ Æ = Ä ¹

{ }| ( ) ( ) ( )Y X S y S y X image S Card S= = Ì = Ä =$



APPLICATIONS

Les exemples suivants utilisent S = Ss 4-connexe. En orange pts éliminés, en vert ajoutés

Périmètre d’un objet : contour intérieur Ci = X – ( X S ) ou extérieur Ce = ( X S ) - X

S étant en 4-connexité, le contour est 8-connexe ( et inversement )

Sélection de détails de petite taille face à l’élément structurant : D = X – ( X S )

« Top Hat Transform »



APPLICATIONS : « Hit or Miss Transform »

Transformation par tout ou rien - TTR

Les transformations par descripteur de voisinage et LUT peuvent être reformulées :

détection des pts de bordure ouest W( les configurations {S0,S1} ont été répertoriées alphabet de Golay )

0 x 1

0 1 1

0 x 1 10

110

0

V = (P0 & P1 & P7) & (~P3 & ~P4 & ~P5) ( notation Matlab )

2 éléments structurants disjoints mais demême origine S0(o) = { 0 } et S1(o) = { 1 }

{ 1 } { ( | 1( ) ) et ( 0( ) ) }

{ 1 } ( 1 ) ( 0 )ss

V x S x X S x X

V X S X S

= Û Ì Ì

Þ = = Ç$ $

Sous la forme de 2 éléments structurants, il n’y aplus de limite de dimension du voisinage ( # LUT )

NB : contours intérieurs

Ci = X – ( X S )

1

Bordure W : les points oranges sont éliminés

Sw = {S0,S1}

TTR( X,SW )



APPLICATIONS : AMINCISSEMENT / EPAISSISSEMENT

La transformation par tout ou rien ( illustrée ici par Sw ) permet des opérations :

- d’amincissement - d ’épaississement

TR wX - T (X,S ) TR WX T (X,S )È

( amincissement W ) ( épaississement E )

L’application de ces opérations avec les 8 éléments structurants successifs S i selon les 8

orientations de la 8-connexité conduit à des amincissements ou épaississements isotropes.L’itération du cycle d’amincissement par { Si=0,7 } conduit à une invariance ou idempotence :

X X1 X2 invariante ultérieurement

1 2



AMELIORATION D’IMAGE BINAIRE

Rappel : les points oranges sont éliminés ( 1 0 ), les points verts sont ajoutés ( 0 1 ). Ouverture ( 1 ) : l’érosion élimine les fausses alarmes, la dilatation restitue la taille d’origine

Fermeture ( 2 ) : la dilatation « bouche » les lacunes, l’érosion restitue la taille d’origine

1 2

X S = ( X S ) S X S = ( X S ) S

( X S ) S ( X S ) S

puis opération duale :


SQUELETTISATION

NOTION DE SQUELETTE

Graphe (1) caractéristique de la forme d’un objet binaire, qui peut permettre de le reconstituer (2) 1 - c’est un ensemble de points connexes2 - c’est une transformation réversible

Deux définitions similaires dans R2 ( mais non dans N2 ) :

- Lieu des centres des disques de rayon maximum inscrits dans l’objet, le rayon en chaque point permet de reconstruire l’objet.

- Axe médian, ensemble des points équidistants de 2 bords de l’objet, cette définition correspond à l’état stable obtenu par érosions successives sans perte de connexité. La distance aux bords permet la reconstruction.

==


SQUELETTISATION ( 2 )

PROPRIETES

- invariance présumée en rotation- sensibilité aux détails des objets : irrégularité des bordures, lacunes … éventuel lissage des bordures avant squelettisation ( voir traitements par LUT )

Nombreux algorithmes et versions multiples, aboutissant à des squelettes légèrement différents :

- algorithmes parallèles : érosions conditionnelles sans propagation d’information- algorithmes séquentiels : érosions conditionnelles avec propagation des modifications in situ- algorithmes basés sur la recherche de maxima locaux dans une carte de distance

lacune irrégularitélocale



ALGORITHMES D’ EROSION CONDITIONNELLE

Algorithme parallèle : itération d’amincissements avec conservation de la connexité

cas de la bordure W ( configurations similaires pour les autres bordures ), P 0 si :

3 2 1

4 P 0

5 6 7

0 1 x

0 1 1

0 1 x

0 0 x

0 1 1

x 1 x

( x = indifférent )

Du fait du parallélisme les bandes de largeur paire ( 2 pixels )disparaissent configurations de conservation sur 4 points:

~P4 & P & P0 & ~P8 P = 1~P2 & P & P6 & ~P9 P = 1

9

8

110

110

110

00

00

00

Algorithme séquentiel : les modifications s’effectuent dans l’image en cours de balayagece qui introduit une dépendance du sens de balayage

configurations essentielles ( sans modification ), cas de la bordure W :

1 0 x

0 1 x

x x x

x x x

0 1 x

1 0 x

x 0 0

0 1 1

x 0 0

- si x = 0 P est une extrémité- si x = 1 P est un lien de connexité locale



ALGORITHMES D’ EROSION CONDITIONNELLE

Algorithme séquentiel, dernière configuration ( 4 configurations essentielles ) :

y y y

0 1 0

x x x

- si x,y = 0 P est un point isolé ( à conserver )- si x et y = 1 P est un lien de connexité locale- si x = 0 et y = 1 P est une extrémité ou un lien de connexité

Les points essentiels sont des points du squelette, les numéros des itérations où ils sont déclarésessentiels correspondent aux rayons des disques centrés sur ces points.

Les points non essentiels sont marqués, valeur < 0, puis sont éliminés en fin de balayage.

Séquencement des itérations :

Initialisation : Iter = 1

Itération tant que des points sont éliminés, 2 sous cycles pour symétriser le squelette :

1 - test bordures E,W si essentiel P = Iter, sinon marqué2 - test bordures N,S non marquées si essentiel P = Iter, sinon marquéPoints marqués = 0, Iter = Iter +1

Fin d’itérations { P > 0 } = squelette valué



ALGORITHMES BASE SUR LES CRETES DE DISTANCES

Pour les algorithmes précédents, le nombre de passes dépend de la taille des objets, pourl’algorithme basé sur les maximums locaux de la carte des distances il n’y a que 3 passes :2 passes pour la carte des distances + 1 pour la recherche des lignes de crêtes

Principe : - calcul des distances des points des objets au fond : chamfer - seuillage éventuel pour éliminer les irrégularités locales - maximums locaux directionnels

si maximum strict, sur 3 points a b c : (b > a) & (b > c)

problème de squelette non connexe, exemple avec la norme D, les maximums stricts sont en gras, reste le 2 central :

d’où tests de maximums relatifs sur 4 points a b c d :

crête : ((b > a) & (b > c)) | ((b > a) & (b = c) & (c > d))

Profil de crête : ou selon les 4 directions à /4

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



RESULTATS : VARIABILITE DU SQUELETTE

Sans régularisation des bordures

Avec régularisationdes bordures

Algorithmes

Parallèle Séquentiel Crêtes de distances (3-4)

( seuil = 6 )



QUALITE DU SQUELETTE ?

Sans régularisation des bordures

Avec régularisationdes bordures

Algorithmes

Parallèle Séquentiel Crêtes de distances (3-4)

( seuil 9 )



CAS PARTICULIER : OBJETS MINCES

Dans le cas d’objets de faibles épaisseurs ( < 5 pixels par exemple ) une approche parconvolution est rapide, 2 passes sur l’image :

axe médian = lignes des crêtes de l’image convoluée par un masque triangulaire

0 5 10 15 20 25 300

0.2

0.4

0.6

0.8

1

1.2

1.4

Exemple 2Dpointillé noir : image binaire

IB k.[1 2 3 2 1]

les 2 zones distinctes ne sont pas résolues

IB k.[1 2 8 2 1]

max(coeff) > somme(coeff) – max(coeff)

les maximums locaux (non stricts) donnent les axes médians



ZONES D’ INFLUENCE

Le squelette du fond { x | x = 0 } donne, après élimination des branches pendantes, les limites des zones d’influence des objets.

Branche pendante = partie du squelette ayant une ( ou plus ) extrémité libre, ici le squelette doit être constitué de boucles fermées si le bord de l’image est considéré comme un objet.

Squelette de ~X ( vert ) Zones d’influence : étiquetage des régionsdélimitées par le squelette du fond

Bord à 1

La zone d’influence d’un objet est l’ensemble des points à distance de cet objet inférieureaux distances des autres objets.


EXTENSIONS MULTI-NIVEAUX

MORPHOLOGIE MULTI-NIVEAUX

Bases ensembliste : analogie des opérations 2D binaires d’érosion et dilatation L’image en niveaux de gris ( espace N3 ) est représentée par son sous-graphe :

g g(x)

x

-

Sous-graphe de g(x) : x N2, g N SG( g(x) ) = { (x,g) | g g(x) }

L’élément structurant est aussi représenté par son sous-graphe

élément structurant So(x) 3Dcentré en o

Les opérations de base se ramènent donc à des unions / intersections / complémentations ensemblistes :

Erosion : Y = X S = { y | Sy X } { (y,g) | SG( Sy(x)+g) ) SG( X(x) )

Dilatation par dualité : Y = X S = ( X Ss ) { (y,g) | SG(-Sy(-x)+g ) SG( X(x) ) }

SG( g(x) )

x

g

SG( g(x) ) Noter pour Ss la symétrie 3D

x


EXTENSIONS MULTI-NIVEAUX ( 2 )

OPERATIONS DE BASE

Erosion : Y = X S { (y,g) | SG( Sy(x)+g ) ) SG( X(x) ) }

x

So(x)

X(x)

g(x) = érodé( X(x) )

Analogie avec un palpeur suivant le profil X(x)l’érodé est la trajectoire du point de référence( ou origine ) du palpeur.

La forme 3D du palpeur ( élément structurant )fixe son comportement dans les pics de X(x) érosion des pics

Expression analytique pour S centré en xo : x [xo-x1…xo+x2] X(x) – ( Sxo(x)+g(xo) ) 0 g(xo) = min( X(x) – Sxo(x) )

Il s’agit donc d’une transformation non linéaire contrairement aux filtres classiques

La translation de niveaux qui peut amener des g < 0, peut être compensée par une translation de valeur max( So(x) ), sans changer le profil de g(x) :

g(x) = min( X – Sx ) + max( S )

g

-x1 x2



Dilatation : Y = X S { (y,g) | SG( -Sy(-x)+g ) ) SG( X(x) ) }

x

So(x) X(x)

g(x) = dilaté( X(x) )

Même analogie avec un palpeur :

La forme 3D du palpeur ( élément structurant )fixe son comportement dans les vallées de X(x) comblement des vallées

Expression analytique pour S centré en xo : x [xo-x1…xo+x2] X(x) + Sxo(x) g(xo) g(xo) = max( X(x) + Sxo(x) )

La translation de niveaux peut amener des g > gmax, d’où une translation optionnelle devaleur - max( So(x) ), sans changer le profil de g(x) :

g(x) = max( X + Sx ) - max( S )

Remarque, cas particulier de l’élément structurant « plat » : x [-x1…x2] So(x) = 0

filtres ‘ inf ’ : érosion = min( X ) et ‘ sup ‘ : dilatation = max( X ) ( voir lissage des bruits – opérateurs de base )

g

-x1 x2


-2-1

01

2

-2

0

2-4

-2

0

2

4


ouverture : X S = ( X S ) S )

fermeture : X S = ( X S ) S)

« top hat » : X – ( X S )

lissage morphologique ( non linéaire ) : ( X S ) S ou ( X S ) S

gradient morphologique : ( X S ) – X ou X - ( X S ) ou ( X S ) – ( X S )

laplacien morphologique : ( X S) + ( X S) – 2.X

OPERATIONS COMBINEES

Elément structurant 5 x 5

-4 -1 0 -1 -4

-1 2 3 2 1

0 3 4 3 0

-1 2 3 2 1

-4 -1 0 -1 -4

Forme 3D



EXEMPLES

Image originale

Ouverture Fermeture

Lissages

fermeture ouverture

Gradientmorphologique



AMINCISSEMENT / EPAISSISSEMENT

Par analogie avec la morphologie binaire, deux éléments structurants multi-niveaux disjointspermettent de définir l’amincissement AMM et l’épaississement EPM multi-niveaux :

-N -N 1

-N 1 1

-N -N 1

S1 = S0 =

1 -N -N

1 -N -N

1 -N -N

-N = - « infini », élément neutre de l’opération, les pixelscorrespondants ne sont pas traités.

Ici exemple de l’élément structurant ouest W

0 0 1sup ( ) si sup ( ) inf ( )( )

sinonS S SX X X X

AMM XX

< £=

0 1 0inf ( ) si sup ( ) inf ( )( )

sinonS S SX X X X

EPM XX

£ <=

Amincissement et épaississement isotropes sont obtenus par application successive des {S0,S1}correspondants aux 8 orientations de la 8-connexité ( rotations de 45° ).


Intuitivement : amincissement contraction des plages claires épaississement extension des plages claires


X image d’origine

AMM(X)

EPM(X)


RETOUR AU PLAN

FIN DE PRESENTATION

FIN DE PRESENTATION


GENERATION DE LUT - CODE MATLAB

EXEMPLE : LISSAGE DES BORDURES

Code Matlab pour établir les LUTs :

function [Lut0,Lut1]=lislutV8=[0:255];P0=bitget(V8,1); P1=bitget(V8,2); P2=bitget(V8,3); P3=bitget(V8,4);P4=bitget(V8,5); P5=bitget(V8,6); P6=bitget(V8,7); P7=bitget(V8,8);Modif=(~P0 & ~(P1|P2|P6|P7) & (~P3|P4|~P5)) | ... (~P2 & ~(P3|P4|P0|P1) & (~P5|P6|~P7)) | ... (~P4 & ~(P5|P6|P2|P3) & (~P7|P0|~P1)) | ... (~P6 & ~(P7|P0|P4|P5) & (~P1|P2|~P3));Lut1=~Modif; % Pc=1 : si modif -> 0Lut0=((P0+P2+P4+P6) >= 3);

x 1 x

x 0 1

x 1 x

0 0 x

0 1 1

0 0 x

0 0 0

0 1 x

0 0 x

2 passes successives, lissage des 0 puis des 1 2 LUTs ( Lut1 et Lut0 ) :

Concavités :

(P0+P2+P4+P6) >= 3 1

Bordure W ( ouest ) aspérités, pts saillants, en notation Matlab :

~(P2 | P3 | P4 | P5 | P6) & (P0| ~P1| ~P3) 0

0 0 x

0 1 x

0 0 0

( et rotations de /2 )


ZOOM – LACUNES


ZOOM – FAUSSES ALARMES


ZOOM – LISSAGE BORDURES


CONTOURS – ORIENTATION


CONTOURS – COURBURE

Documents

Images binaires - 1 IMAGES BINAIRES 1. TOPOLOGIE Connexité Composantes connexes : étiquetage 2. METRIQUE Norme, courbure et orientation Transformée de