Graphes de fusion clivages et proprités de la fusion de regions

La notion de connexité abordée dans le chapitre précédent joue un rˆole essentiel dans la tˆache importante et difficile qu’est la segmentation d’une image. Dans de nombreux cas, une segmentation est un ensemble de régions connexes séparées par un ensemble fronti`ere. La fusion de régions est une approche populaire en segmentation d’image [9, 6]. Elle consiste, `a partir d’une segmentation initiale, `a fusionner progressivement des paires de régions voisines jusqu’`a ce qu’un certain crit`ere soit satisfait. Le crit`ere permettant d’identifier la prochaine paire de régions qui doit ˆetre fusionnée, tout comme la condition d’arrˆet, est spécifique `a chaque application. Etant donnée une image en niveau de gris, comment obtenir un ensemble initial de régions ´ pour une procédure de fusion ? La LPE, dont les variantes les plus significatives ont été présentées au chapitre précédent, est un outil puissant pour résoudre ce probl`eme (voir Figure 2.1a,b). A cause de la texture et du bruit, les images réelles comprennent souvent un grand nombre de minima et donc la LPE a souvent un aspect “mosa¨ıque” comme celui observé dans l’exemple Figure 2.1b. Ce chapitre ne s’attarde pas sur les méthodes permettant d’obtenir une LPE. Nous considérons directement le résultat d’un tel algorithme : dans un graphe, un clivage (Définition 3) est un ensemble de sommets qui ne peut ˆetre réduit sans changer le nombre des composantes connexes de son complémentaire. Une premi`ere question se pose lorsque nous considérons un clivage dans un graphe. Etant ´ donné un sous-ensemble rectangulaire D de Z 2 et le graphe (D, E4) qui correspond au graphe induit par la 4-adjacence, nous observons qu’un clivage peut contenir des “points intérieurs”, i.e., des points qui ne sont adjacents `a aucun point en dehors du clivage (voir Figure 2.1c,d). Nous pouvons dire qu’un clivage dans (D, E4) n’est pas nécessairement mince. D’autre part, de tels points intérieurs ne semblent pas apparaˆıtre avec E8, la relation de 8-adjacence. Les clivages dans (D, E8) sont-ils toujours minces ? Nous allons montrer que c’est en effet le cas. Plus généralement, nous introduisons dans ce chapitre un cadre mathématique pour étudier les propriétés de minceur des clivages dans n’importe quel type de graphe. Nous identifions la classe des graphes dans lesquels tout clivage est nécessairement mince. Ce résultat est l’un des résultats principaux du chapitre (Théor`eme 36). 27 Graphes de fusion clivages et propriés de la fusion de regions Chapitre 2. Graphes de fusion : clivages et propriétés de la fusion de régions (a) (b) (c) x y w z A B C D (d) (e) Fig. 2.1 – Introduction aux probl`emes liés a` la fusion de régions. (a) : Image originale (section d’une image de cerveau, apr`es avoir appliqué un opérateur de gradient). (b) : Un clivage obtenu grˆace a` une LPE par inondation de (a) pour la 4-adjacence (pixels noirs). (c) : Points intérieurs de l’image précédente (pixels noirs). (d) : Zoom sur une partie de (b). Les points z et w sont intérieurs. (e) : Un clivage pour la 8-adjacence (pixels noirs). Il n’y a pas de points intérieurs. Revenons maintenant au probl`eme de la fusion de régions. Que se passe-t-il si l’on souhaite fusionner deux régions A et B et que chaque pixel adjacent a` ces deux régions est également adjacent a` une troisi`eme région que l’on ne souhaite pas fusionner ? La Figure 2.1d illustre une telle situation : le point x est adjacent aux régions A, B et C et y est adjacent a` A, B et D. Dans cet exemple, il est impossible de fusionner les régions A et B sans fusionner également ou C ou D. Ce probl`eme a` été identifié, en particulier, par T. Pavlidis (voir [6], section 5.6 : “When three regions meet” [“Ou` trois régions se rencontrent”]) et a été traité de mani`ere ad-hoc selon les besoins applicatifs. Jusqu’`a maintenant aucune étude systématique des propriétés liées a` la fusion de régions dans les graphes n’avait été effectuée. Une contribution majeure de ce chapitre (voir aussi [87, 111, 84]) est la définition et l’étude de quatre classes de graphes définis en considérant les différentes possibilités de “blocages” pouvant survenir dans les processus de fusion de régions (Section 2.3, Section 2.4). En particulier, nous disons qu’un graphe est un graphe de fusion si toute région A dans ce graphe peut toujours ˆetre fusionnée avec une autre région B, tout en préservant toutes les autres régions. Le résultat le plus frappant de cette étude est que la classe des graphes de fusion est précisément celle des graphes dans lesquels tout clivage  Ensembles minces et graphes d’arˆetes est nécessairement mince (Théor`eme 36). Nous donnons également des caractérisations locales pour deux de ces quatre classes de graphes et montrons que les deux autres ne peuvent pas ˆetre caractérisées localement (Section 2.5). En utilisant ce cadre mathématique, nous analysons le statut des graphes les plus fréquemment utilisés en analyse d’image, c’est-`a-dire ceux qui correspondent aux 4- et 8-adjacences sur Z 2 et aux 6- et 26-adjacence sur Z 3 (Section 2.6). Dans l’une des classes de graphes introduites dans la Section 2.4, appelée la classe des graphes de fusion parfaits, toute paire de régions voisines A et B peut ˆetre fusionnée en préservant toutes les autres régions. De plus, la fusion de A et B peut ˆetre simplement réalisée en supprimant de l’ensemble fronti`ere tous les pixels adjacents a` la fois a` A et a` B. Nous montrons qu’aucun des graphes classiques de l’analyse d’image n’est un graphe de fusion parfait. Finalement, dans la Section 2.7, nous introduisons un graphe sur Z n (quel que soit n entier positif) appelé grille de fusion parfaite, qui est en effet un graphe de fusion parfait, et qui est entre – au sens de l’inclusion des relations d’adjacence – les graphes d’adjacence directe et d’adjacence indirecte qui généralisent les 4- et 8-adjacence a` Z n . De plus, dans un article en préparation, nous prouvons que cette grille n-dimensionnelle est le seul graphe (`a une translation pr`es) possédant ces deux propriétés. Les preuves des propriétés énoncées dans ce chapitre peuvent ˆetre trouvées dans la référence [87], qui est reprise dans l’Annexe A du manuscrit

Ensembles minces et graphes d’arˆetes

Dans cette partie, nous présentons les notions d’ensemble mince et de graphe d’arˆetes. Commen¸cons par quelques rappels et définitions élémentaires sur les graphes. Soit p ∈ V et P ⊆ V , nous rappelons que : – Γ ? (p) = {q ∈ V | {p, q} ∈ E} ; – Γ(p) = Γ ? (p) ∪ {p} ; – Γ(P) = [ S {Γ(p) | p ∈ P}] ; et – Γ ∗ (P) = Γ(P) \ P. Si P et Q sont deux sous-ensembles de V et si Γ(P) ∩ Q 6= ∅, nous disons que Q est adjacent a` P. Soit G0 = (V 0 , E0 ) un graphe, on dit que G et G0 sont isomorphiques s’il existe une bijection f de V dans V 0 telle que, pour tous sommets x et y de G, y appartient a` Γ(x) si et seulement si f(y) appartient a` ΓG0(f(x)). Dans le chapitre précédent nous avons abordé les notions de W-amincissement ensembliste et de clivage qui reposent sur la suppression de points uniconnectés. Dans la suite du présent chapitre, et en particulier dans notre analyse des méthodes de fusion de régions, nous cherchons a` caractériser les invariants préservés (ou non) lors de la suppression d’autres types de points. Définition 25 Soit P ⊆ V , et soit p ∈ P. On dit que p est un point de bord (pour P) si p est adjacent a` P. On dit que p est un point intérieur (pour P) si p n’est pas un point de bord pour P. 29 Chapitre 2. Graphes de fusion : clivages et propriétés de la fusion de régions On dit que p est séparant (pour P) si p est adjacent a` au moins deux composantes de P. On dit que p est un point multiple (pour P) si p est adjacent a` au moins trois composantes de P. Etan ´ t donné un ensemble de sommets P, tout élément de P est soit un point intérieur soit un point de bord. Tout point de bord est soit uniconnecté, soit séparant et tout point multiple est nécessairement un point séparant. Dans l’exemple de la Figure 2.2a, p est a` la fois un point de bord et un point uniconnecté pour l’ensemble P constitué des sommets noirs; q est un point intérieur. Dans la Figure 2.2b, z est un point de bord qui est séparant, et w est un point de bord séparant et multiple. Dans ce chapitre, nous étudions certaines propriétés de minceur des clivages. Les notions de minceur et d’intérieur sont étroitement liées. Définition 26 (ensemble mince) Soit P ⊆ V , l’intérieur de P, noté int(P), est l’ensemble des points intérieurs pour P. On dit que l’ensemble P est mince si int(P) = ∅. En d’autres termes, l’intérieur d’un ensemble P est int(P) = {p ∈ P | Γ(p) ⊆ P}. Dans la Figure 2.2b, l’ensemble de sommets noirs est mince. En revanche, celui de la Figure 2.2a n’est pas mince. p q w z (a) (b) (c) (d) (e) Fig. 2.2 – Clivages minces et non-minces. (a) : Un graphe G et un ensemble P (points noirs) de sommets de G. (b) : Le sous-ensemble formé des sommets noirs est un clivage mince ; c’est également un clivage de l’ensemble P de la sous-figure (a). Les points de bord z et w sont tous deux séparant, seul w est un point multiple. (c, d, e) : Le sous-ensemble constitué des points noirs et gris est un clivage non-mince dont l’intérieur est représenté en gris. Un clivage est un ensemble qui ne contient pas de point uniconnecté, cependant, comme le montrent les exemples de la figure ci-dessus, un tel ensemble n’est pas nécessairement mince (au sens de la Définition 26). Les Figures. 1.3d et 2.2b présentent des exemples de clivages minces : dans chacun des cas, l’ensemble des sommets noirs ne contient ni point uniconnecté ni point intérieur. Les Figures. 2.2c,d et e présentent trois exemples de clivages non-minces (ensembles de points noirs et gris). Nous concluons cette section par un rappel de la définition de graphe d’arˆetes (line graph en anglais) [4]. Cette classe de graphes permet d’établir un lien fort entre l’approche développée dans ce chapitre ou` un clivage est constitué de sommets et les approches reposant sur une séparation constituée uniquement d’arˆetes.