Traitement d'images (1996)

Présentation

Les algorithmes de traitement d'images qui sont présentés constituent la base de cette vaste discipline. Ils concernent le filtrage, la segmentation ou la morphologie mathématique.

Conception

Les implémentations réalisées l'on été soit en JAVA soit en C++ avec l'utilisation du concepte des templates propres à ce langage. Le format des images traitées est le format BMP.

Captures d'écrans

La segmentation est une opération dont le but est le partitionnement d'une image en régions connexes représentant les faces des objets. Plusieurs techniques sont utilisées pour effectuer un tel traitement sur une image. On distingue deux types d'algorithmes: les algorithmes de fusion et les algorithmes de division. Ces derniers génèrent un parcours différent dans l'image.

L'algorithme de fusion permet de réaliser la croissance de régions. Dans ce cas les régions initiales de taille unité ( 1 pixel ) croissent dans les directions du plan ( parcours en 4-connexité ou en 8-connexité ). La segmentation en régions par divisions successives génère la stratégie opposée. Alors que l'on effectue un parcours ascendant dans l'image pour la fusion ( pixel ð image ) la division réalise un parcours descendant ( image ð pixel ). Dans ce cas la région initiale est constituée de l'image entière que l'on divise successivement.

On peut classer ces deux méthodes de segmentation selon l'approche que l'on veut réaliser pour caractériser les régions d'une image. On distingue ainsi l'approche "lignes et contours" de l'approche "régions". On peut considérer une région comme étant une partie de l'image dans laquelle les points possèdent des propriétés statistiques, voire géométriques, voisines. De tels algorithmes nécessitent donc la mise en place de trois paramètres: Un critère d'appartenance qui sera le plus souvent statistique et selon lequel sera jugée l'homogénéité d'une région ( le plus courant est la moyenne des niveaux de gris ). Les attributs les plus couramment employés concernent le niveau de gris, les contours et la texture. Un seuil d'appartenance selon lequel le critère évoqué ci-dessus sera testé. Une structure de données représentatives des régions qui contiendra des informations symboliques sur les régions ( localisation, taille, répartition statistique des niveaux de gris... ).

java CMain SEGMT ../IMA/triangle.bmp 45
triangle-seg.gif (66614 octets) triangle-seg-grad.gif (66614 octets)

Régions (seuil=45)
PixelsEnglobantPixelsEnglobant
0 56576 [0,0][255,255] 1 501 [112,7][144,38]
2 1038 [189,55][240,94] 3 993 [89,58][119,104]
4 503 [149,62][179,96] 5 997 [136,105][174,163]
6 971 [96,110][138,159] 7 2035 [168,146][234,213]
8 1922 [79,166][140,235]   

Une phase de calcul de caractéristiques peut être enchaînée sur les résultats issus de la segmentation par croissance de régions. Elle constitue donc une phase d'interprétation. Celle-ci peut avoir deux buts: premièrement quantifier la qualité de la segmentation réalisée, deuxièmement donner des informations suffisantes pour pouvoir effectuer de la reconnaissance de formes présentes sur l'image initiale. Les caractéristiques proposées pour chaque région sont de trois types: des paramètres de position, des paramètres statistiques sur la répartition des "couleurs" présentes dans la région, des paramètres de forme.


java CMain SEGMT ../IMA/damier.bmp 20
damier-seg-0.gif (66614 octets) damier-seg-grad-0.gif (66614 octets)

Régions (seuil=20)
PixelsEnglobantPixelsEnglobant
0 1024 [0,0][31,31] 1 1024 [32,0][63,31]
2 1024 [64,0][95,31] 3 1024 [96,0][127,31]
4 1024 [128,0][159,31] 5 1024 [160,0][191,31]
6 1024 [192,0][223,31] 7 1024 [224,0][255,31]
8 1024 [0,32][31,63] 9 1024 [32,32][63,63]
10 1024 [64,32][95,63] 11 2048 [96,32][159,63]
12 1024 [160,32][191,63] 13 1024 [192,32][223,63]
14 1024 [224,32][255,63] 15 1024 [0,64][31,95]
16 1024 [32,64][63,95] 17 1024 [64,64][95,95]
18 1024 [96,64][127,95] 19 1024 [128,64][159,95]
20 1024 [160,64][191,95] 21 1024 [192,64][223,95]
22 1024 [224,64][255,95] 23 1024 [0,96][31,127]
24 2048 [32,96][63,159] 25 1024 [64,96][95,127]
26 3072 [96,96][159,159] 27 1024 [160,96][191,127]
28 1024 [192,96][223,127] 29 1024 [224,96][255,127]
30 1024 [0,128][31,159] 31 1024 [64,128][95,159]
32 1024 [128,128][159,159] 33 1024 [160,128][191,159]
34 1024 [192,128][223,159] 35 1024 [224,128][255,159]
36 1024 [0,160][31,191] 37 1024 [32,160][63,191]
38 1024 [64,160][95,191] 39 1024 [96,160][127,191]
40 1024 [128,160][159,191] 41 1024 [160,160][191,191]
42 1024 [192,160][223,191] 43 1024 [224,160][255,191]
44 1024 [0,192][31,223] 45 1024 [32,192][63,223]
46 1024 [64,192][95,223] 47 1024 [96,192][127,223]
48 1024 [128,192][159,223] 49 1024 [160,192][191,223]
50 1024 [192,192][223,223] 51 1024 [224,192][255,223]
52 1024 [0,224][31,255] 53 1024 [32,224][63,255]
54 1024 [64,224][95,255] 55 1024 [96,224][127,255]
56 1024 [128,224][159,255] 57 1024 [160,224][191,255]
58 1024 [192,224][223,255] 59 1024 [224,224][255,255]

java CMain SEGMT ../IMA/damier.bmp 60
damier-seg-1.gif (66614 octets) damier-seg-grad-1.gif (66614 octets) 

Régions (seuil=60)
PixelsEnglobantPixelsEnglobant
0 1024 [0,0][31,31] 1 1024 [32,0][63,31]
2 1024 [64,0][95,31] 3 1024 [96,0][127,31]
4 52224 [0,0][255,255] 5 1024 [0,32][31,63]
6 1024 [32,32][63,63] 7 1024 [64,32][95,63]
8 1024 [0,64][31,95] 9 1024 [32,64][63,95]
10 1024 [64,64][95,95] 11 1024 [96,64][127,95]
12 1024 [0,96][31,127] 13 1024 [64,96][95,127]

compute SQUEL ../IMA/lettres.bmp 20 0 0
lettres.bmp (263222 octets) lettres-squel.bmp (263222 octets)


compute LISS ../IMA/femme.bmp 80 35 40
femme-lis.gif (31259 octets) femme-lis-seg.gif (4460 octets) femme-lis-seg-grad.gif (3233 octets)


Pour appréhender cette méthode de segmentation il faut posséder les notions suivantes

Les matrices de co-occurence peuvent être définies de différentes manières. Il s'agit de matrice symétrique M ( distance, orientation, déplacement ) donnant la probabilité de la transition de niveaux de gris ( i, j ) pour une distance et une orientation données entre deux pixels. La matrice de co-occurence d'une image constitue en fait l'histogramme bidimentionnel de celle-ci.
Elle est définie au moyen de trois paramètres comme on peut le voir sur la figure précédente. La distance représente la taille de l'élément structurant permettant d'observer le voisinage, l'orientation donne l'angle d'observation, et le déplacement est égal au pas du masque de co-occurence.

Les images qui suivent permettent de visualiser, avec une vue de dessus, la matrice de co-occurence associée à chaques textures. Les matrices sont seuillées c'est à dire que les pics sont "plats" et sont donc représentés par un point sans se soucier des intensités. Les paramètres d'observation sont les suivants: distance égale à 1, orientation égale à 0 ( direction horizontale ) et déplacement du masque de co-occurence valant 1.

On peut observer que chaque texture présente une matrice de co-occurence dont la forme lui est caractéristique. Nous voyons d'ors et déjà apparaître dans cette propriété les paramètres discriminants nécessaires pour la segmentation. Il s'agit à présebt de mettre en place un système de quantification de cette différence, avec des paramètres discriminants sur lesquels s'appuiera l'algorithme de segmentation. Ces paramètres peuvent être regroupés en deux catégories:

Ces paramètres sont des moments calculés sur les valeurs de la matrice de cooccurrence.

Il est nécessaire avant de définir ce type de paramètre de créer une forme à partir des points de la matrice de cooccurrence. Nous utilisons pour ce faire les algorithmes de calcul d'enveloppes convexes. Une fois la forme convexe créée à partir du nuage de points il convient de trouver un paramètre qui la quantifie, nous utilisons pour cela l'algorithme de codage de Freeman pour en calculer le périmètre.

L'algorithme de division / fusion consiste à faire se succéder sur l'image que l'on désire segmentée une phase de division puis une phase de fusion des régions issues de la division.

La phase de division doit remplir une double fonction. Premièrement elle permet de créer des régions de taille plus ou moins importante, deuxièmement les différentes régions détectées doivent être représentatives des différentes textures de l'image initiale. Ils existent en fait deux types de division. La première est une division conditionnelle, la méthode la plus connue étant le Quadtree, la deuxième est une division inconditionnelle conduisant à obtenir dans l'image résultat des régions de taille identique. Notre algorithme utilise le deuxième type de division, c'est à dire une division uniforme. Il est important de remarquer que ce choix n'implique pas de conséquence sur le résultat de l'algorithme de segmentation car la phase de division est suivie d'une phase de fusion.

A partir des résultats issus de cette phase de division inconditionnelle on peut enchaîner une phase de fusion de régions. Cette opération consiste à parcourir le graphe d'adjacence des régions et à réunir les régions connexes qui satisfont au critère d'homogénéité. On peut considérer que l'on réalise de la croissance de région avec une différence importante: on ne fusionne plus des pixels avec la région en cours de formation mais directement des régions entre elles ( celles provenant de la division ).

L'avantage évident de cet algorithme de division / fusion réside dans le fait que la phase de division permet de créer des régions représentatives des textures, avec le calcul des paramètres discriminants présentés dans le chapitre précédent, alors que la croissance qui est enchaînée regroupe ces régions de manière à obtenir des zones uniformes pour chaque texture.

Comme nous l'avons vu précédemment le but de la division est de créer des régions caractéristiques des textures présentes dans l'image. Nous utilisons donc comme "critère" de division les paramètres discriminants présentés dans le chapitre précédent: paramètres statistiques et paramètre de forme définis sur la matrice de co-occurence. Ces paramètres sont calculés sur une zone de l'image initiale qui correspond à l'élément structurant selon lequel s'effectue la division. Il s'agit tout simplement d'un carré dont la taille est passée en paramètre et dont la valeur en chacun des points, dans l'image résultat, est égale à la valeur du paramètre discriminant.

La phase de fusion permet de reconstruire à partir des régions issues de la division les zones correspondant à chaque texture. L'algorithme de croissance utilisé parcours en fait le graphe d'adjacence, où chaque noeud représente une région, et recompose des zones de plus grandes tailles. Les valeurs présentes dans l'image issue de la division étant directement "proportionnelles" aux textures, la croissance se fait selon la moyenne des intensités des pixels. On peut considérer cette image comme une image non plus en niveau de gris mais une image en niveau de texture sur laquelle on peut appliquer des algorithmes classiques de traitement d'image: croissance, filtrage...

L'image résultat, après l'enchaînement des deux phases présentées précédemment, est donc une image "d'étiquettes" où chaque région est "labelisée". C'est à partir de cette dernière que l'on effectue l'extraction de caractéristiques avec l'algorithme présenté dans le chapitre V de manière à compléter les résultats de la segmentation.

La phase de division et la phase de fusion sont séparées par un filtrage de l'image. Celui-ci est en fait un moyenneur réalisé par l'algorithme du filtre moyenneur récursif présenté dans le chapitre II. Cette phase de lissage permet d'adoucir les frontières entre les régions issues de la division. Cela permet d'obtenir des frontières qui, une fois la segmentation terminée, ne ressemblent pas à des marches d'escalier, dues à la forme de l'élément structurant responsable de la division. Il est important de noter que la taille du moyenneur étant importante l'implémentation sous forme récursive de l'opérateur moyenne est nécessaire pour obtenir un algorithme rapide.

Texture 1-2.

Extraction des caractéristiques des régions.

Région n°0 Région n°1
Rectangle ex-inscrit (x,y) 000 308 000 511 105 511 000 511
Nombre de pixels 103799 158345
Coordonnées du barycentre (x,y) 109.17 213.33 351.06 283.15
Moyenne des paramètres de la matrice 539.332336 195.156052
Variance des paramètres de la matrice 6825.274414 727.366821
Orientation 1.328041 1.259639
Elongation -16041.673828 -16271.841797
Rectangularité 0.656092 0.759871
Surface 103799.000000 158345.000000
Perimètre 1537.525391 1733.523438
Compacité 0.551770 0.662148
Convexité 0.959520 0.980695
M11 -416287360.00 -644151808.00
M20 526758752.00 1520201984.00
M02 2104697472.00 3315977472.00
M21 -26580389888.00 61490958336.00
M12 -17275066368.00 24262137856.00
M22 11617796358144.00 32713606168576.00
M30 17275017216.00 -36417982464.00
M03 99885260800.00 -104197890048.00

Texture 1-7.

Extraction des caractéristiques des régions.

Région n°0 Région n°1
Rectangle ex-inscrit (x,y) 000 511 000 374 000 511 114 511
Nombre de pixels 125842 136302
Coordonnées du barycentre (x,y) 303.64 135.61 210.66 366.20
Moyenne des paramètres de la matrice 202.963806 370.094666
Variance des paramètres de la matrice 839.921875 350.212952
Orientation 2.766825 2.749825
Elongation 21199.542969 21623.929688
Rectangularité 0.655427 0.668882
Surface 125842.000000 136302.000000
Perimètre 1623.788696 1669.795166
Compacité 0.599759 0.614307
Convexité 0.973316 0.966578
M11 666938752.00 736836608.00
M20 2453007360.00 2707164416.00
M02 1019856000.00 1227991936.00
M21 -34308761600.00 35801440256.00
M12 48344829952.00 -58522099712.00
M22 21803791548416.00 26430295506944.00
M30 -127056969728.00 134807560192.00
M03 44558336000.00 -53478227968.00

Texture 2-6.

Extraction des caractéristiques des régions.

Région n°0 Région n°1
Rectangle ex-inscrit (x,y) 000 511 000 317 000 511 120 511
Nombre de pixels 112593 149551
Coordonnées du barycentre (x,y) 298.07 118.72 223.08 358.48
Moyenne des paramètres de la matrice 609.426208 1222.196533
Variance des paramètres de la matrice 16406.490234 3694.280273
Orientation 2.866683 2.814864
Elongation 17151.371094 17973.742188
Rectangularité 0.691535 0.745132
Surface 112593.000000 149551.000000
Perimètre 1542.594360 1690.599854
Compacité 0.594590 0.657533
Convexité 0.969852 0.968532
M11 482771168.00 671987328.00
M20 2248169984.00 3116939264.00
M02 672692672.00 1361658496.00
M21 -25004498944.00 26190821376.00
M12 30946590720.00 -60804300800.00
M22 14068767260672.00 29164482592768.00
M30 -110038827008.00 122324344832.00
M03 22344486912.00 -42219872256.00

Texture 3-4.

Extraction des caractéristiques des régions.

Région n°0 Région n°1
Rectangle ex-inscrit (x,y) 000 465 000 511 054 511 000 511
Nombre de pixels 135001 127143
Coordonnées du barycentre (x,y) 160.19 186.17 356.16 329.13
Moyenne des paramètres de la matrice 2071.536133 409.277557
Variance des paramètres de la matrice 188715.109375 7405.257812
Orientation 0.937004 0.945261
Elongation -28185.626953 -27829.162109
Rectangularité 0.565824 0.542197
Surface 135001.000000 127143.000000
Perimètre 1753.994873 1737.994385
Compacité 0.551430 0.528939
Convexité 0.982712 0.954420
M11 -951278080.00 -884576832.00
M20 1692340224.00 1515340672.00
M02 2287571200.00 2101081344.00
M21 -66399358976.00 58150797312.00
M12 -63586705408.00 60552409088.00
M22 33306913538048.00 29753251725312.00
M30 105563299840.00 -94058135552.00
M03 151850221568.00 -145894948864.00

Texture 9-8.

Extraction des caractéristiques des régions.

Région n°0 Région n°1
Rectangle ex-inscrit (x,y) 000 511 000 326 000 511 249 511
Nombre de pixels 143301 118843
Coordonnées du barycentre (x,y) 266.21 140.39 242.06 394.31
Moyenne des paramètres de la matrice 507.017639 351.692871
Variance des paramètres de la matrice 1537.343506 845.846802
Orientation 3.039773 3.054013
Elongation 6295.604980 5854.966309
Rectangularité 0.855917 0.882567
Surface 143301.000000 118843.000000
Perimètre 1696.470947 1528.474854
Compacité 0.625700 0.639244
Convexité 0.936969 0.967517
M11 225529936.00 173944352.00
M20 3158729728.00 2529520128.00
M02 974443648.00 563751680.00
M21 3245882624.00 8202375168.00
M12 22406569984.00 -12169409536.00
M22 22091831181312.00 11638449111040.00
M30 -43118759936.00 43671355392.00
M03 5738704896.00 -3244193280.00