Traitement d'images (1996)

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.

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.

• Segmentation en 4-connexité avec extraction des régions et des contours.

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

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

java CMain SEGMT ../IMA/damier.bmp 60
 

• Sequelettisation par détection de crête sur image de distance.

compute SQUEL ../IMA/lettres.bmp 20 0 0

• Lissage adaptatif avec segmentation et détection de front.

compute LISS ../IMA/femme.bmp 80 35 40

• Détection de frontières sur images multi-texturées par analyse de la matrice de cooccurrence.

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

• La calcul d'enveloppe convexe (algorithme de Graham, Jarvi).

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 textures de brodatz avec leur matrice de cooccurrence.

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:

• les paramètres statistiques.

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

• les paramètres de forme.

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.

• Les images mutli-texturées segmentées.

• Principe.

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.

• Paramètres utilisés pour la division.

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.

• Paramètres utilisés pour la fusion.

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.

• Résultats.

Texture 1-2.

Extraction des caractéristiques des régions.

Texture 1-7.

Extraction des caractéristiques des régions.

Texture 2-6.

Extraction des caractéristiques des régions.

Texture 3-4.

Extraction des caractéristiques des régions.

Texture 9-8.

Extraction des caractéristiques des régions.