Algorithmes des bassins versants appliqués à des images en niveaux de gris

 

De nombreux algorithmes de bassins versants existent. Appliqués à des images en niveaux de gris, ils permettent de segmenter celles-ci et de mettre ainsi en évidence les Lignes de Partage des Eaux (LPE) suivant les variations rapides des niveaux de gris.

Nous avons choisi d'implémenter l'algorithme de Vincent-Soille qui est le suivant :

 

 

Cet algorithme utilise une pile fifo (First In First Out) où les différentes fonctions sont possibles :

• Fifo_init (queue) : Initialise la pile fifo queue à NULL

• Fifo_add (p, queue) : Ajoute à la fin de la pile queue le pixel p

• Fifo_remove (queue) : Supprime et renvoie le premier pixel de la pile queue

• Fifo_empty (queue) : Renvoie vrai si la pile queue est vide, faux sinon

///////////////////////////////////////DESCRIPTION DE L'ALGO/////////////////////////////////////////////////

Les images sur lesquelles nous avons testé cet algorithme sont les suivantes :

 

MMs

Nous avons jugé cette image intéressante car elle comporte des ovoïdes de différents niveaux de gris se chevauchant. Idéalement, l'algorithme des bassins versants devrait permettre de les détecter.

 

Cell

Cette image, qui se rapproche de la précédente, a néanmoins quelques différences notables: Les cellules sont du même niveau de gris et sont plus espacées. De plus, le fond est beaucoup moins dégradé que sur MMs

 

Lenna

Lenna est une image classique du traitement d'image. Elle est appréciée pour la richesse des caractéristiques qu'elle présente. Il nous a semblé intéressant de voir ce que la détection des LPE donnerait sur cette image, même si elle n'est pas adaptée.

Application

Nous allons maintenant appliquer l'algorithme sur ces 3 images. Les résultats se présentent sous la forme d'une succession de deux images. Sur la première sont représentés les LPE trouvées avec les bassins dont le niveau de gris correspond à son altitude. Sur la deuxième image, nous avons superposé les LPE à l'image initiale.

Une première application de l'algorithme de Vincent-Soille nous donne les résultats suivants :

 

Bassins versants appliqués sur MMs

 

 

Bassins versants appliqués sur Cell

 

 

Bassins versants appliqués sur Lenna

Pour les trois images de départ, les images résultats obtenues sont sur-segmentées. Cela est dû aux nombreux minima locaux présents dans les textures et au bruit.

Afin de tenter de résoudre ce problème, on applique l'algorithme des bassins versants avec une connexité 4. Cela nous donne les résultats suivants :

 

Bassins versants appliqués sur MMs en 4-connexité

 

 

Bassins versants appliqués sur Cell en 4-connexité

 

Bassins versants appliqués sur Lenna en 4-connexité

Les images résultantes sont moins segmentées. Néanmoins, elles sont toujours sur-segmentées étant donné qu'aucun traitement n'a été effectué. De plus, on peut remarquer que les bassins ne sont pas fermés.

On se propose donc, dans un premier temps, d'appliquer l'algorithme de Vincent-Soille puis un second permettant de fermer les bassins. On obtient les images suivantes :

MMs avec bassins fermés

 

 

Cell avec bassins fermés

 

 

Lenna avec bassins fermés

 

Les résultats obtenus sont bien meilleurs que les précédents. Cependant l'algorithme permettant de fermer les bassins donne de très mauvais résultats en 8-connexité (comme le prouve les images suivantes). De plus, comme on l'a vu précédemment, la 8-connexité sur-segmente davantage les images. On choisit donc de rester en 4-connexité.

 

 

MMs avec bassins fermés (8-connexité)

 

 

Cell avec bassins fermés (8-connexité)

 

 

Lenna avec bassins fermés (8-connexité)

 

 

NB: Dorénavant, l'algorithme des bassins versants, et uniquement celui-là, sera utilisé avec la 4-connexité (sauf mention).

 

 

 

Filtrage

On se penche maintenant sur la résolution de la sur-segmentation des images. Celle-ci était due aux nombreux minima locaux. On va donc traiter les images à l'aide de différents filtres afin de réduire le nombre de ces minima.

 

 

FILTRE LINEAIRE

On procède à un filtrage par filtre linéaire de taille 3x3. Cette taille apparaît être le meilleur compromis entre segmentation et reconnaissance de l'image initiale. On obtient les résultats suivants :

 

 

MMs avec filtrage linéaire

 

 

Cell avec filtrage linéaire

 

 

Lenna avec filtrage linéaire

Les images sont beaucoup moins sur-segmentées. On commence même à se rapprocher du résultat idéal pour MMs et à distinguer certaines formes de Lenna. Il y a néanmoins quelques invraisemblances (surtout sur MMs).

Pour Cell, certaines cellules sont largement délimitées (principlament en bas à droite), mais dans l'ensemble le résultat est très peu satisfaisant.

 

FILTRE MEDIAN

Comme précédemment, on procède à un filtrage par un filtre médian cette fois, de taille 3x3 (pour les mêmes raisons). Les résultats sont les suivants:

MMs avec filtrage médian

 

 

Cell avec filtrage médian

 

 

Lenna avec filtrage médian

Sur MMs, le résultat est beaucoup plus probant avec cette méthode de filtrage. En effet, l'image n'est pas sur-segmentée et les ovoïdes sont grossièrement délimités. Cependant un léger hic demeure quand au fond de l'image.

Pour Lenna, le résultat est également plus probant. Malgré les sur-segmentations du fond, celles présentes au niveau du chapeau et des plumes sont normales (cela est dû à la nature des objets). On commence même à distinguer les formes importantes de l'image initiale (visage, chapeau, épaule).

Quand à Cell, le résultat n'est toujours pas mieux.

 

 

 

Contrainte par marqueurs

Speech sur les marqueurs, c'est cool, t'es une pédale, etc...

 

 

CHAPEAU HAUT ET BAS DE FORME

Petit speech encore...

Cette fois le résultat comporte une image de plus; c'est l'image qui a servi de marqueur. Pour MMs et Cell elles ont été surexposées afin de permettre une meilleure distinction.

MMs par chapeau haut et bas de forme

r=20 // sb=0 // sh=60

 

 

Cell par chapeau haut et bas de forme

r=20 // sb=5 // sh=25

 

 

Lenna par chapeau haut et bas de forme

r=140 // sb=30 // sh=200

 

Les résultats sont satisafaisants sur les 3 images.

 

Les ovoïdes sur MMs sont bien délimités. Néanmoins, il est difficile de détecter 2 ovoïdes lorsque ceux-ci se chevauchent et qu'ils sont foncés. La détection par rapport au fond est cependant bonne.

 

Le résultat sur Cell est beaucoup mieux que pour les traitements par filtre. En effet, toutes les cellules sont parfaitement détectés, à l'exception de celles qui se chevauchent. Leur détection reste quand même satisfaisante.

 

Certaines parties de Lenna, comme le chapeau, les cheveux et l'épaule sont bien détectées. La sur-segmentation de la plume est là encore due à sa complexité. Certains traits du visage sont détectés, ainsi que des parties aussi fines que les yeux. Enfin, malgré quelques améliorations, le fond reste sur-segmenté.

Conclusion

La segmentation d'une image en niveau de gris par la méthode des bassins versants conduit à une sur-segmentation de celle-ci. En effet, cette méthode est sensible aux minima locaux de l'image initiale. Il est donc possible d'amoindrir cette sur-segmentation en traitant préalablement l'image par des filtres qui réduisent ces minima. Le filtre médian