Module de traitement d'images

DEA ATS - Avril 2003

Salima Makni - Marta Nogaj - Julie Battais

Segmentation d'images par ligne de partage des eaux sous contraintes

I - Introduction

Dans le cadre du module de traitement des images du DEA ATS, on a implémenté des algorithmes et des fonctions qui nous ont permis de tester la méthode de segmentation des images avec la LPE sans et avec contraintes. On a donc implémenté une application qui nous a permis d'effectuer nos tests pour produire ce rapport. Le developpement de cette application a été effectué avec le language Java (version 1.4.1).

Vous pouvez accéder à cette application par le lien suivant : application.jar

I - Segmentation par lignes de partage des eaux

I.1 - Définition

 

La morphologie mathématique fournit de nombreux outils de segmentation d'images. Nous allons nous intéresser ici à l'une des techniques les plus répandues : la technique de la Ligne de Partage des Eaux (LPE).
Une idée pour segmenter les images est de déterminer les lignes le long desquelles les niveaux de gris varient rapidement. En faisant une analogie géographique, cela se rapproche de la notion de ligne de crête du module du gradient de l'image. Ici, l'image est vue comme une zone géographique dans laquelle les lignes de crêtes ou ligne de partage des eaux sont assimilées aux contours de l'image. Pour cela, on définit son complémentaire : les bassins versants.
Un bassin versant est une zone géographique d'où une goutte d'eau, suivant la ligne de plus grande pente, arrivera dans ce minimum. On associe d'ailleurs un minimum à un bassin versant.
Cette technique nous donne de façon efficace des contours fermés et squelettisés ; ces contours fermés forment donc une partition de l'image.

Voir l'annimation FLASH de la LPE.

 

 

I.2 - Algorithme de la LPE

 

Nous appliquons ici l'algorithme de partage des eaux sur des d'images à teintes de gris et à valeurs discrètes afin de retrouver les contours des formes. Cet algorithme est appliqué directement sur les images.

Il y a plusieurs manières d'implémenter le principe de la lpe. Certains algorithmes ne simulent pas le principe de l'immersion mais trouvent directement les lignes de partages des eaux. Nous avons donc choisi d'implémenter un algorithme d'immersion qui est celui de Vincent-Soille pour des raisons principalement pédagogiques.

 

L'algorithme de Vincent-Soille est le suivant :

Toutefois, cet algorithme de segmentation d'images, qui sont à niveaux de gris dans notre cas, nécessite la mise en évidence et le repérage des contours des objets. Cette détermination des minima et des maxima utilise les variations du contraste de l'image, quantifiées par le calcul du gradient. De nombreuses méthodes de calcul du gradient existent. On peut notamment, par les outils morphologiques, calculer un gradient de l'image. C'est le gradient morphologique.
En fait, on pourrait définir le gradient morphologique autrement comme étant la différence entre le dilaté de l'image originale I par l'élément structurant symétrique B et l'érodé de I par B.

 

 

I.3 - Les tests

 

Les images sur les quelles on a testé l'algorithme sont les suivantes :

 

Cell

Lenna

Cell est une image typique pour ce genre de segmentation : des cellules avec des niveaux de gris semblables et qui parfois se chevauchent, ce qui rend leur segmentation par les autres méthodes classiques de détection de contours trés difficile.

Lenna est une image classique du traitement des images. Elle est appréciée pour la richesse des caractèristiques qu'elle présente. Il sera intérressant de voir ce que donne l'algorithme de la LPE implémenté sur cette image. Cette image est transformée en une image à niveaux de gris par le programme pour pouvoir y appliquer les traitements implémentés et notamment celui de la LPE.

On calcule d'abord le gradient de ces images pour une sphère de rayon 3 et avec une connexité de 8 voisins. L'implémentation que nous avons fait des fonctions morphologiques nous permet de choisir la taille de la sphère et la connexité (4 ou 8).

On applique ensuite la lpe implémentée avec comme paramètre la connexité initialisée à 8 aussi. Il faut voir que dans l'algorithme de la lpe il y a l'utilisation de la notion de voisins d'un pixel. Cette notion varie suivant la connexité choisie. On a donc laissé le choix de la connexité à l'utilisateur pour paramètrer le déroulement de cet algorithme.

Les résultats obtenus sont les suivants :

 

LPE de Cell

LPE de Lenna

A gauche, on visualise le résultat de la LPE en attribuant des couleurs aléatoires pour les zônes trouvées. Et à droite, on superpose les lignes de partage des eaux (lignes de séparation des zones) sur l'image originale.

On adoptera cette représentation pour la suite du document.

Les résultats ainsi obtenus sont sur-segmentés. Ceci est du au grand nombre de minima locaux présents dans les images en raison de la texture bien-sûr mais aussi du bruit.

Ainsi, pour remédier à ce problème, il faut filtrer l'image d'origine.

On choisit de filtrer ces images par un des filtres suivants :

- le filtre moyenneur : Ce filtre nous fournit la moyenne sur les voisins d'un point et ceci par une convolution de l'image avec une fenêtre de taille nxn. Dans notre implémentation de cette opération, on laisse libre choix à l'utilisateur de la taille de la fenêtre. On choisi, pour bien homogéniser l'image, une fenêtre de taille 5x5.

- le filtre alterné séquentiel : Ce filtre est un filtre morphologique qui consiste à faire une succession d'alternations d'ouvertures et de fermutures par des sphères de rayons croissants. Pour les tests, on a fait qu'une seule itération du couple ouverture/fermeture par une sphère de taille 2.

On applique ensuite le gradient morphologique sur les images filtrées suivi de la LPE et on obtient :

LPE de Cell filtrée avec un filtre moyenneur

LPE de Lenna filtrée avec un filtre moyenneur

Malgré l'existence d'une amélioration (on commence àdeviner la forme du chapeau de lenna et on commence à distinger des formes parfaites de cellules), cette LPE fait encore apparaître une forte sur segmentation due au fait que le gradient présente encore plusieurs petites fluctuations radiométriques malgré les filtrages que nous avons fait.

 

 

I.4 Conclusion

 

Le problème majeur de la LPE est la sur segmentation. En effet, cet algorithme, étant sensible à tout minimum local dans l'image, tend à surdéfinir les lignes de partage des eaux.

Afin de remédier au problème de sur-segmentation, plusieurs techniques ont été développées pour imposer des contraintes à l'algorihme. On a donc développé deux des principales techniques qui sont la LPE contrainte par des marqueurs, et la LPE contrainte par le contraste.

II - Segmentation par lignes de partage des eaux sous contraintes

 

 

II.1 - LPE contrainte par des marqueurs

 

L'idée consiste à choisir le nombre de minima locaux et donc le nombre de zones que l'on souhaite mettre en évidence grâce à la LPE. Nous éliminons ainsi les informations qui ne nous intéressent pas.
En fait, le type d'information que l'on introduit est de nature géométrique. On suppose que l'on connaît un ensemble connexe de points faisant partie de l'objet ainsi qu'un ensemble de points de l'extérieur. Ces ensembles de points connexes sont appelés des marqueurs.
On va alors modifier l'image en lui imposant que ces ensembles soient les uniques minima régionaux, chaque bassin devenant ainsi soit un unique objet, soit le fond de l'image.

marqueurs de Cell

marqueurs de Lenna

Les marqueurs de l'image cell sont obtenus à partir de plusieurs transformations morphologiques de l'image de départ. Ces opérations morphologiques (faits aprés un seuillage initial) ont pour but de séparer les marqueurs sans perdre de l'information sur des cellules.

Les marqueurs de l'image Lenna ont été choisis manuellement suivant les zônes d'intérêts qu'on a porté à cette image :

- Le châpeau

- Le visage

- Le reste du corps

- Le reste de l'image (le fond de l'image).

 

Pour mettre au point cette méthode, on érode géodésiquement le masque selon l'image masquée par un élément de taille infinie.Les connexes du masque représentant les marqueurs sont à 0 (noir). Et l'image masquée est obtenue en prenant pour chaque pixel, le pixel minimun de celui de l'image et de celui du masque. Ensuite on calcule la lpe de cette image résultat.

LPE de Cell contrainte par des marqueurs

LPE de Lenna contrainte par des marqueurs

Tout d'abord, on remarque que le nombre de régions d'intérêt choisi est bien respecté. Ces régions on été les seules à être prises en compte dans la LPE. Tous les autres minima locaux, entre information utile et parasite, qu'on n'a pas séléctionné on été ignorés.

Dans l'image de Cell contrainte par des marqueurs, on remarque que les grains marqués ont été bien séparés des autres grains marqués et qu'il n'y a plus de ligne de séparation qui vient couper un grain en deux ou plusieurs morceaux. La non séparation de quelques grains est due uniquement à l'inexactitude de l'image du masque des grains. Tous les grains n'y ont pas été marqués, et cela pour mettre en évidence le résultat d'une telle lacune qui s'avère être la fusion du grain non marqué avec un de ses voisins.

Dans l'image de Lenna les trois zônes qu'on a marqué pour leurs segmentations (sans compter le fond de l'image) ont été bien segmentées. On arrive à bien les identifier dans l'image de gauche. Cependant une partie du châpeau a été attribuée au fond de l'image et cela pour la raisons suivantes : les niveaux de gris (déduits des couleurs) de cette partie omise du châpeau sont plus proches de ceux des pixels du fond voisins de cette partie haute du châpeau que de ceux des pixels de la partie basse des chapeaux.

Cette imperfection aurait pu être évitée si le marqeur du châpeau avait des pixels (de niveau 0) inclus dans cette partie haute du châpeau. Le même phénomène est rencontré pour le frond du visage de lenna qui a été attribué au châpeau.

 

Remarque :

La connexité 8 est mal adaptée pour ce traitement car l'érosion géodésique passe par l'opération d'érosion d'une image masquée. L'érosion prend la valeur de niveau de gris minimale des voisins du pixel. On a donc entre autre une propagation de la frontière (de l'mage masquée). Si la connexité est mise à 8, il y a un risque qu'un minimum régional, qui se trouve à cette frontière à une diaganale du pixel à calculer, soit pris en compte dans ce calcul au lieu du pixel directement voisin (sans diagonale). On se retrouve donc à une multiplication de minima locaux et donc avec un résultat sursegmenté qui comporte beaucoup plus d'objets que ceux marqués. La preuve avec ce résultat pour l'image Lenna pour les mêmes paramètres (même marqueurs) que le précédent test mais avec une connexité 8 :



LPE de Lenna contrainte par des marqueurs pour une connexité 8

 

 

II.2 - LPE contrainte par le contraste (seuillage des dynamiques de bassin)

 

L'idée est de supprimer des minima selon un critère de contraste (ou de dynamique) qui est la quantité dont on est obligé de monter d'un minimum régional pour atteindre un autre minimum d'altitude moindre que le premier.

Soit h la valeur du contraste qu'on veut imposer.

Pour éliminer les minima régionaux de g de dynamique inférieure à h, on fait l'érosion géodésique de taille infinie de l'image f+g selon l'image g.

On obtient les résultats suivants pour une dynamique de bassin de 8:

 

LPE de Cell contrainte par le contraste

LPE de Lenna contrainte par le contraste

 

Les résultats ont été obtenus aprés avoir effectuer des tests avec différentes valeurs du seuil de contraste h. A chaque modification du seuil une distribution nouvelle des zônes apparait. Si on augmente ce seuil, le nombre de zônes détectées diminue. Le seuil 8, pour notre exemple permet de garder l'essentiel des informations sur les régions.

Pour l'image de Lenna contrainte par le contraste, on remarque que des parties aussi fines que les yeux ont été segmentées et qu'il existe une forte sursegmentation des plûmes du châpeau. On pense alors à augmenter le contraste (la
dynamique) seuil des minima. Cependant, au dessus de ce seuil (8) , on perd des informations sur la forme du châpeau. En effet, il s'avère que le contraste entre le châpeau et le fond est moins important que ceux de la texture des plûmes du châpeau. Il nous est donc impossible, avec cette méthode de contrainte, de supprimer certaines sursegmentations parasites.

L'image de Cell contrainte par le contraste est elle aussi sursegmentée. Mais elle est bien meilleure que celle de la LPE sans contraintes. De même pour cette image, si on augmente la valeur du contraste seuil dans le but de réduire la sursegmentation, on perd des lignes de sépartion de cellules et donc on se prive d'informations importantes.

 

 

III - Conclusion

 

La segmentation par lignes de partage des eaux est trés sensible au bruit, il est donc nécessaire de filtrer les images avant de les segmenter. Même aprés filtrage, et pour une image réelle, il est impossible d'éliminer tous les minima locaux. Cela se fait donc sentir au niveau du résultat de la segmentation par la présence de nombreuses zônes parasites qui rendent l'image sursegmentée.

Le critère utilisé pour éliminer les zônes parasites dans la deuxième méthode est bien approprié. En effet, il y a de forte chance qu'un minimum ayant une dynamique faible soit un minimum indésirable. Cependant ce critère ne se superpose pas toujours au critère premier qui est subjectif : zône utile/ zône parasite (comme c'est le cas pour nos résultats).

La première méthode restreint la segmentation aux zônes d'intérêt de l'utilisateur. C'est ce qui fait que les résultats obtenus par cette méthode sont plus significatifs au point de vu de l'utilisateur que ceux de la deuxième méthode.
Cepandant, le prix à payer pour ces résultats est une détermination souvent manuelle des marqueurs. Alors que dans la deuxième méthode l'utilisateur n'intervient que pour fixer le seuil du contraste.