De Ensiwiki.

(Redirigé depuis Segmentation d'images médicales par coupure de graphe)

Sommaire

1 Segmentation d'images médicales par coupure de graphe

Segmentation d'images médicales par coupure de graphe

Labo	LJK & GIPSA-Lab
Equipe	EVASION & GPig
Encadrants	Franck.Hetroy@imag.fr Michel.Desvignes@grenoble-inp.fr, Franck.Hetroy@imag.fr

Étudiant

Sonia Yuki SELMI, étudiante en 2A MMIS option bio-informatique

Introduction

Cette étude porte sur la segmentation d'images médicales par coupure de graphe et associe ainsi des notions de théorie des graphes, d'algorihmique et de traitement d'mages. L'algorithme est utilisé sur plusieurs jeux de données 3D, provenant d'acquisition IRM de l'arbre vasculaire-cérébral. Ce sujet est dans la continuité de travaux antérieurs sur la détection de sténéoses ou d'anévrismes.

La segmentation est une partition de l'image en régions connexes. Chaque région répond à un critère d'homogénéité. Dans notre cas, le but est donc de détecter les vaisseaux du fond de l'image.

Le problème posé comme sujet de TER est l'étude du comportement de la segmentation sur des objets longilignes et fins.

Pour l'étude de ce sujet, nous avons utilisé l'article Graph Cuts and Efficient N-D Image Segmentation de Y. Boycov et G. Funka-Lea qui propose une nouvelle approche en utilisant la théorie des graphes.

Visualisation 3D des vaisseaux sanguins

Éléments de pré-requis

Voici les notions indispensables pour la compréhension du travail effectué.

Problème de flot maximum

Le problème de flot maximum consiste à trouver un flot réalisable depuis une source unique vers un puit unique qui soit maximum dans un graphe.

Soit G = (V,E) un graphe avec la source $s \in V$ , le puit $p \in V$ et $u e$ la capacité de l'arc e.

L'algorithme pour la recherche du flot maximum le plus connu est celui de Ford et Fulkerson. Il est basé sur la recherche de chaine augmentante dans le graphe c'est à dire une chaine de la source vers le puit tel que les arcs de la chaine ne soient pas saturés en flot. Le coût de l'algorithme est $O (n 2 m)$

Théorème flot max/coupe min

On appele (s-t)coupe un ensemble de sommets S tel que $s\in S,t \notin S$ . La capacité de la coupe représente la capacité des arcs sortants de S.

$u(S)=\sum_{e \in \delta^+(S)} u_e$

Pour tout graphe, tout couple (s,t) de sommets du graphe, et pour toute pondération positive, la valeur maximum du flot de s à t est égale à la capacité minimum d'une coupe séparant s et t.

F * t s = u (S * )

Travail réalisé

Mon travail se décompose en plusieurs parties:

Travail de bibliographie sur les différentes approches concernant la segmentation et choix d'une méthode
Compréhension de la méthode à la fois en théorie des graphes et en traitement d'images
Implémentation du sujet (en C++)
Analyse des résultats et modifications (ajout de prétraitement par exemple) pour améliorer les résultats.

Modélisation du problème comme une minimisation avec contraintes

Notre but est d'étudier une nouvelle technique de segmentation interactive d'images en 3D. L'image segmentée est alors divisée en 2 parties:

"object", les vaisseaux sanguins
"background", le fond de l'image.

L'utilisateur impose les contraintes dures qui indiquent si un pixel appartient à l'objet ou non. De plus, d'autres contraintes incluent des informations sur les bords et les régions de l'image.

L'objectif est alors de trouver une coupe optimale de graphe donnant une segmentation. En optimisation combinatoire, le coût d'une coupe est définie comme la somme des poids des arêtes sortantes:

$|C|=\sum_{e \in C} w_e$

La solution obtenue donne le meilleur équilibre entre les proprités de bords et des régions parmi toutes les solutions respectant les contraintes.

La fonction-objective à minimiser est la suivante:

E (A) = λ R (A) + B (A)

avec

λ > 0

avec $R(A) = \sum_{p \in P} R_p(A_p)$ $B(A) = \sum_{{p,q} \in N} B_{p,q}.\delta_{A_p \neq A_q}$

$|\delta_{A_p\neq A_q}| = \left\{ \begin{array}{ll} 1 & \qquad \mathrm{si} A_p\neq A_q \\ 0 & \qquad \mathrm{sinon} \\ \end{array} \right.$

Le coefficient $λ$ spécifie l'importance relative du terme "région" R(A) par rapport au terme "contour" B(A).

Exemple de graphe 3x3. Après l'application du flot max, on obtient la coupe min contenant le sommet fictif de la source. La coupe min traverse les arcs sortants dont la capacité est minimale. Or d'après la définition des capacités des arcs, ce sont les pixels voisins ayant un fort écart d'intensité qui ont été séparés

Le terme R(A) correspond à l'affectation du pixel/voxel p à l'objet ou au fond par les valeurs $R p (' o b j')$ et $R p (' b k g')$ . On peut par exemple poser $R p (.)$ comme l'intensité de p.

Le terme B(A) spécifie les propriétés de "bord" de la segmentation. Le coefficient $B p, q$ peut être interpretré comme une pénalité de la discontinuité entre deux pixels p et q. $B p, q$ est grand quand les intensités de p et q sont similaires. Au contraire quand il y a un écart "important" entre p et q, $B p, q$ est proche de zéro. La fonction proposée par Boykov et Funka-Lea est la suivante: $B_{p,q} = exp\Big(-\frac{(I_p-I_q)^2}{2\sigma^2}\Big)$

Cette fonction pénalise fortement les pixels voisins d'intensité similaire (quand $| I p - I q | < σ$ ).

Au contraire, si les pixels sont différents ( $| I p - I q | > σ$ ), la pénalité est petite.

$σ$ peut être estimé comme le contraste moyen de l'image. Ainsi, quand $| I p - I q | < σ$ , on considère p et q proche.

Nous utilisons le critère de Michelson pour calculer le contraste moyen. Pour une image de taille w*h: $GlobalConstrast = \frac{1}{w*h} \sum_{p:pixel}constrast(p)$

$constrast(p)=\frac{L_{max}-L_{min}}{L_{max}+L_{min}}$

avec $L m a x$ = luminance max dans le voisinage de p et $L m i n$ = luminance min dans le voisinage de p

Construction du graphe et algorithme du flot max

On construit un graphe à partir de l'image 3D avec les propriétés suivantes:
- un noeud correspond à un pixel
- un arc entre deux noeuds voisins a pour capacité le coût $B p, q$ . Ce sont ces arcs qui vont permettre de déterminer si deux voisins appartienent à la même région.
- chaque noeud est relié à la source et au puits avec respectivemen une capacité de $B s, q$ et $B p, t$ . Ce sont ces deux arcs qui influencent l'appartenance du noeud à l'objet ou au fond. De plus, un noeud est relié à ses voisins (6 voisins en 3D).

La source et le puits sont des sommets fictifs.

Par la suite, on applique l'algorithme du flot max sur le graphe de l'image afin d'obtenir la coupe minimale. Nous utilisons l'algorithme du flot max/coupe min développé par Yuki Boykov et Vladimir Kolmogorov. Ce nouvel algorithme qui améliore les performances empiriques de l'algorithme de Ford & Fulkerson est basé aussi sur les chaînes augmentantes. Pour plus de précision sur l'algorithme, voir l'article An experimental Comparison of Min-Cut/Max-Flow Algorithms for Energy Minimization in Vision (2004).

Premiers résultats

Pour tester l'algorithme, nous avons utilisé plusieurs jeux de données 3D, provenant d'acquisition IRM ou scanner de l'arbre vasculaire-cérébral. Le principal défi était d'observer le bon comportement de l'algorithme flot-max sur des images contenant des objets fins. L'utilisateur sélectionne sur l'image les pixels source et puits.

Nous observons tout d'abord que les résultats dépendent fortement des valeurs choisies au départ. Alors que la valeur du "fond" reste presque constante, on peut obtenir un écart d'intensité important entre plusieurs pixels de la source. Dans notre cas, l'intensité du fond ne varie en moyenne de 4% (dans les tests que nous avons fait) alors que celle de la "source" varie de plus de 20% sur l'échelle des intensités.

D'autre part, nous remarquons que la qualité de la segmentation se dégrade lorque l'intensité prise par la source est très élevée. Ceci s'explique pour le fait que les pixels moins clairs appartenant à la source sont "absorbés" alors par le fond car plus proches d'eux en terme d'intensité. Pour un pixel appartenant à la source, l'arc entre la source et le pixel doit être dominant. Cependant, si l'intensité entre le pixel et celle de la source est assez important, alors le pixel peut être absorbé par ses voisins (arcs avec ses voisins dominent) ou pire absorbé par le puits. De même, dans le cas contraire, si l'intensité de la source est trop faible (c'est à dire très proche de l'intensité du puits), alors tous les pixels font partie de la source.

Segmentation avec mauvaise valeur de source. Le vaisseau est coupé car l'intensité des pixels du vaisseau diminue.

Segmentation avec bonne valeur de source. Le résultat est bon

L'enjeu principal est donc de définir l'intensité de la source correctement. Ainsi, le manque de précision entraine une différence entre les résultats et pour obtenir une meilleure homogéneité des résultats, il est nécessaires d'utiliser d'autres informations que nous avons à notre disposition.

Prétraitement de l'image

Connaissant bien les caractéristiques de l'image, on peut apporter des informations supplémentaires pour favoriser la segmentation. En effet, les vaisseaux (pixels plus clairs) ne représentent qu'une petite partie de l'image. Nous nous penchons sur l'histogramme particulier de l'image à segmenter.

Type d'histogramme obtenu

Un histogramme est un graphique statistique permettant de représenter la distribution des intensités des pixels d'une image, c'est-à-dire le nombre de pixels pour chaque intensité lumineuse. L'image étant bipartie, on peut modéliser l'histogramme comme un mélange de 2 gaussiennes (la première est le fond bruité et la seconde les vaisseaux). Cependant, dans notre cas, les pixels des vaisseaux ne représentant que 0.1% de 'imge, la gaussienne de l'objet est très peu marquée sur l'histogramme. On utilise donc cette caractéristique pour effectuer une présegmentation.

Algorithme de classification

On utilise un algorithme basée sur le principe de l'algorithme du K-means afin de classifier notre image en deux parties. Cette classification nous permet ainsi de déterminer la valeur moyenne des pixels de fond et la valeur moyenne des pixels de l'objet. Ces valeurs nous sont utiles pour la construction du graphe (déterminer les poids des arcs entre les pixels et la source, les pixels et le puits). On note m_g la moyenne des pixels de l'image, s l'écart-type, me la médiane et m_f la moyenne des pixels du fond L'algorithme se déroule en 2 étapes:

initialisation: tous les pixels sont l'intensité est inférieur à m_g+s appartiennent au fond, le reste à l'objet.
classification: on parcours les pixels de l'objet par ordre croissant. Un pixel passe dans l'ensemble "fond" tant que m_f<(m_g+me)/2.

Par la suite, on définit la valeur de la source comme étant l'intensité minimale de l'ensemble "objet" et la valeur du fond comme étant la moyenne des pixels de l'image.

Résultats avec prétraitement

Le prétraitement permets d'éviter à l'utilisateur de devoir faire une saisie des pixels "source" et "puits".

Segmentation sans présegmentation.

Segmentation avec présegmentation. Le résultat est bon puisque les petits vaiseaux sont bien détectés

Conclusion

L'objectif du travail de ce module était de segmenter des images médicales contenant des fins vaisseaux.

On a pu constater qu'une simple initialisation avec la valeur de la source et du puits est très sensible aux intensités de départ. Si ces intensités sont mal évaluées, les pixels risquent d'être absorbés à tort par les pixels voisins de l'autre ensemble. Cette forte sensibilité nous encourage à effectuer un prétraitement de l'image afin de pouvoir régler les paramètres de départ. Une présegmentation par classification permet de "contrôler" les arcs entre pixel, source et puits.

Il est plus difficile d'intervenir au niveau des contours (arcs entre voisins). Il serait intéressant de pouvoir "maitriser" les contours car nous remarquons que les cas les plus difficiles à segmenter sont ceux où les bords entre vaisseaux et fond ne sont pas nets.

Références

[1] Yuri Boykov and Gareth Funka-Lea. Graph Cuts and Efficient N-D Image Segmentation. International Journal of Computer Vision 70, 109-131, 2006

[2] Yuri Boykov and Vladimir Kolmogorov. An experimental comparison of Min-Cut/Max-Flow Algorithms for Energy Minimization in Vision. In IEEE Transactions on PAMI, Vol. 26, No. 9, pp. 1124-1137, Sept. 2004

Documents additionnels

Transparents de la soutenance : Media:Soutenance_selmis.pdf
Rapport : Media:Rapport_selmis.pdf

Segmentation d'images par coupure de graphe