Graphes de fusion ligne de partage des eaux et fusion de régions 

Introduction

Les méthodes de fusion de régions [27, 6, 54] consistent à améliorer une segmentation initiale en fusionnant itérativement des paires de régions voisines. Etant donnée une segmentation ´ initiale, le chapitre précédent développe un cadre théorique pour étudier les propriétés de fusion dans les graphes. Un clivage (Définition 3) est un ensemble qui ne peut ˆetre réduit sans changer le nombre de composantes connexes de son complémentaire. Cette notion formalise l’idée d’ensemble fronti`ere. Dans le cas général, un clivage peut ˆetre épais et ainsi la relation induite de voisinage entre régions ne poss`ede pas nécessairement de bonnes propriétés pour la fusion. Un résultat important du chapitre précédent (Théor`eme 36) établit l’équivalence entre la classe des graphes dans lesquels tout clivage est mince et celle des graphes dans lesquels toute région peut ˆetre fusionnée avec l’une de ces voisines en préservant toutes les autres régions. Dans ce chapitre (voir également [90, 112, 84]), nous étudions une question différente mais non moins essentielle pour les méthodes de fusion de régions. Etant donnée une image en niveau ´ de gris, comment extraire une segmentation initiale qui permette de garantir la stabilité des crit`eres de sélection des régions à fusionner ? Afin d’identifier la prochaine paire de régions à fusionner ou bien pour déterminer la condition d’arrˆet du processus, les méthodes hiérarchiques utilisent souvent le niveau de gris des pixels appartenant au clivage initial. En particulier, en morphologie mathématique [98, 50, 102], certaines méthodes reposent implicitement sur le fait que le clivage initial satisfait une contrainte fondamentale. Le niveau de gris de ses pixels doit permettre de retrouver les valeurs de connexion (une notion de contraste, voir Définition 18) entre les paires de minima de l’image. D’un point de vue topographique, la valeur de connexion entre deux minima A et B peut ˆetre intuitivement interprétée comme l’altitude minimale que doit atteindre une inondation globale du relief pour fusionner les lacs qui inondent A et B. L’approche topologique de la LPE [104, 71, 73, 72], présentée Chapitre 1, s’intéresse à une transformation qui abaisse les valeurs de l’image tout en préservant la connexité de chacune de ses sections (seuils) inférieures. Cette transformation (ainsi que son résultat) est appelée W-amincissement ; une LPE topologique étant un W-amincissement minimal. Nous appelons séparation induite par une fonction l’ensemble des points qui n’appartiennent à aucun minimum. La séparation induite par une LPE topologique constitue une segmentation initiale intéressante 45 Graphes de fusion ligne de partage des eaux et fusion de r´ Chapitre 3. Graphes de fusion : ligne de partage des eaux et fusion de régions pour les méthodes de fusion. En effet, il a été démontré [71, 72] que les W-amincissements sont les seules transformations – par abaissement de valeurs – qui permettent d’obtenir une séparation préservant les valeurs de connexion entre minima. Ainsi, la séparation induite par un W-amincissement constitue un point d’entrée intéressant pour de nombreuses méthodes de fusion de régions. De mani`ere surprenante, les séparations induites par les algorithmes de LPE [38, 95, 41], et en particulier par ceux de LPE topologiques, ne sont pas toujours des clivages et peuvent parfois ˆetre épaisses, mˆeme dans les graphes de fusion. Dans ce chapitre, nous étudions une notion de minceur pour les fonctions et obtenons une caractérisation locale de la classe des graphes dans lesquels toute LPE topologique est nécessairement mince. Néanmoins, mˆeme dans de tels graphes, les séparations induites par les LPE topologiques ne sont pas nécessairement des clivages. Pour cette raison, nous introduisons une transformation, appelée C-LPE, qui proc`ede par abaissement de valeurs et induit des séparations qui sont nécessairement des clivages. La classe des graphes de fusion parfaits (Définition 34) est un cadre idéal pour les méthodes de fusion. Dans ces graphes, deux régions voisines peuvent toujours ˆetre fusionnées a` travers leur voisinage commun sans effet de bord indésirable induit par la fusion d’une troisi`eme région. La grille de fusion parfaite (Définition 44) est un graphe de fusion parfait régulier dont les sommets sont Z n . Cette grille se situe entre les graphes induits par les relations d’adjacence directe et indirecte qui généralisent les 4- et 8-adjacences a` Z n . Elle est donc adaptée aux applications de la fusion de régions en analyse d’image. Dans ce chapitre, nous démontrons que, dans les graphes de fusion parfaits, toute C-LPE est un W-amincissement et donc vérifie la propriété de préservation de contraste requise par les méthodes morphologiques. De plus, nous obtenons une caractérisation locale de la classe des graphes dans lesquels cette propriété est vérifiée. Nous avons démontré (Propriété 35) que tout graphe de fusion parfait est un graphe de fusion. Comme toute C-LPE induit un clivage et que tout clivage dans un graphe de fusion est mince, nous déduisons que les séparations induites par les C-LPE sont minces dans les graphes de fusion parfaits. Ces propriétés montrent que les C-LPE dans les graphes de fusion parfaits constituent une segmentation intéressante pour initialiser les méthodes de fusion de régions. 

Minceur des LPE topologiques

Une fonction F dont les minima sont cerclés de blanc ; (b) : une LPE topologique de F, la séparation induite est composé des pixels cerclés de blanc. Les séparations induites par les algorithmes de LPE [38, 95, 41] et en particulier par ceux de LPE topologique ne sont pas toujours des clivages et peuvent parfois ˆetre épaisses mˆeme dans les graphes de fusion. Considérons par exemple les images F et H des Figure 3.1a et b et supposons qu’elles soient équipées de la 8-adjacence. Bien que la fonction H soit une LPE topologique de F et que le graphe considéré soit un graphe de fusion (Propriété 42), le pixel étiqueté s (Figure 3.1b) est intérieur pour M(H) la séparation induite par H. Donc M(H) n’est pas mince. Une telle épaisseur peut poser probl`eme pour définir et implémenter une future étape de fusion de régions. Dans le chapitre précédent, nous avons présenté un résultat (Théor`eme 36) qui permet de caractériser, grˆace a` une propriété de fusion, la classe des graphes dans lesquels tout clivage est mince. Les LPE topologiques étendent les clivages aux cas des fonctions (Théor`eme 17). Dans cette section nous présentons un résultat similaire au Théor`eme 36 pour le cas des fonctions (Théor`eme 49). Afin d’atteindre cet objectif, nous commen¸cons par introduire une définition de minceur sur les fonctions qui étend la notion ensembliste (Définition 26) grˆace aux sections supérieures. Remarque importante : Dans la suite de ce chapitre, F désigne une fonction de F(V ). Soit k ∈ K. Nous rappelons que F[k], la section supérieure de F au niveau k est l’ensemble des sommets de G dont l’altitude est supérieure ou égale a` k. Définition 48 (fonction mince) Soit x ∈ V et k = F(x). On dit que x est un point intérieur pour F si x est intérieur pour F[k]. L’intérieur de F, noté int(F), est l’ensemble des points de M(F) qui sont intérieurs pour F. On dit que F est mince si int(F) = ∅. En d’autres termes, un point est intérieur pour une fonction si tous ses voisins ont une altitude supérieure ou égale a` sa propre altitude. Ainsi, une fonction est mince si tout point dans la 47 Chapitre 3. Graphes de fusion : ligne de partage des eaux et fusion de régions séparation qu’elle induit a au moins un voisin d’altitude strictement inférieure. Nous observons, par exemple, que la LPE topologique de la Figure 3.3c est mince alors que celle de la Figure 3.1b ne l’est pas (le point étiqueté s est intérieur). Il découle de la définition d’une LPE topologique et du Théor`eme 36 que, si toutes les LPE topologiques sont minces dans G, alors G doit nécessairement ˆetre un graphe de fusion. La fonction de la Figure 3.1b démontre que, contrairement au cas des clivages, la réciproque n’est en général pas vraie. Malgré cela, comme l’établit le théor`eme de caractérisation ci-dessous, il existe des liens forts entre ces deux classes de graphes. Théor`eme 49 (Théor`eme 9, Annexe B) Toute LPE topologique dans G est mince si et seulement si pour tout clivage P ⊆ V , toute composante connexe A de P est telle que le sousgraphe de G induit par A est un graphe de fusion. Nous remarquons que la condition ci-dessus, qui caractérise les graphes dans lesquels toute LPE topologique est mince, est un affaiblissement de la condition iv du Théor`eme 40 qui caractérise les graphes de fusion parfaits. Nous pouvons donc déduire que toute LPE topologique dans un graphe de fusion parfait est mince. En revanche, la réciproque n’est pas exacte. Il existe des graphes, comme celui de la Figure 3.2, qui ne sont pas des graphes de fusion parfaits et dans lesquels toute LPE topologique est mince.

C-LPE dans les graphes de fusion parfaits

Dans cette section, nous introduisons une nouvelle transformation, appelée C-LPE. Elle proc`ede par abaissement de valeurs et induit des séparations qui sont nécessairement des clivages. Un résultat important (Théor`eme 53) est que, dans un graphe de fusion parfait, toute C-LPE d’une fonction est un W-amincissement de cette fonction et donc préserve les valeurs de connexion au sens de la Définition 22. D’autre part, comme tout graphe de fusion parfait est un graphe de fusion (Propriété 35) et que tout clivage dans un graphe de fusion est nécessairement mince (Théor`eme 36), nous déduisons que dans les graphes de fusion parfaits toute C-LPE induit nécessairement un clivage mince. De plus, nous proposons et prouvons un algorithme linéaire pour le calcul des C-LPE dans les graphes de fusion parfaits. Définition 50 (point M-falaise) Soit p ∈ V . On dit que p est un point falaise (pour F) si p est uniconnecté pour M(F). On dit que p est un point M-falaise (pour F) si p est un point falaise d’altitude minimale ( i.e., F(p) = min{F(q) | q ∈ V est un point falaise pour F}). En d’autres termes, un point falaise pour F est un point de M(F) qui n’est adjacent qu’à un seul minimum de F. Un point falaise p est M-falaise pour F si aucun autre point de M(F) adjacent a` un unique minimum n’a une altitude strictement inférieure a` celle de p. Dans la Figure 3.3a, les points de niveau 3 sont des points falaises et le sommet cerclé de gras est le seul point M-falaise. Dans les Figures. 3.3b,c et d, on remarque qu’il n’y a ni point M-falaise ni point falaise. 49 Chapitre 3. Graphes de fusion : ligne de partage des eaux et fusion de régions Soit p ∈ V un point W-destructible pour F et soit ` ∈ Z. Le point p est W-destructible jusqu’à ` (pour F) si : – pour tout h ∈ Z tel que ` < h ≤ F(p), p est uniconnecté pour F[h] ; et si – p n’est pas uniconnecté pour F[`]. Lemme 51 (Lemme 11, Annexe B) Soit p ∈ V un point M-falaise pour F et soit ` ∈ K l’altitude du seul minimum de F adjacent a` p. Si G est un graphe de fusion parfait alors p est W-destructible jusqu’à ` pour F. Remarquons que dans un graphe qui n’est pas de fusion parfait, les points M-falaise ne sont pas nécessairement W-destructibles. En effet, on peut vérifier que le graphe de la Figure 3.2 n’est pas un graphe de fusion parfait et que tous les sommets cerclés de gras sont des points M-falaise non W-destructibles. Le Lemme 51 nous invite a` étudier la famille des W-amincissements qui proc`edent par abaissement de valeurs des points M-falaise. Soit ` ∈ Z et p ∈ V , nous dénotons par [Fp,`] la fonction de F(V ) définie par [Fp,`](p) = ` et [Fp,`](q) = F(q) pour tout q ∈ V \ {p}. Définition 52 Soit H ∈ F(V ). On dit que H est un C-amincissement de F si : i) H = F, ou si ii) il existe une fonction I qui est un C-amincissement de F et un point p M-falaise pour I tels que H = [Ip,`], ou` ` est l’altitude du seul minimum de I adjacent a` p. On dit que F est une C-LPE s’il n’existe aucun point M-falaise pour F. Si H est a` la fois un C-amincissement de F et une C-LPE, on dit que H est une C-LPE de F. Le théor`eme suivant est une conséquence du Lemme 51, des Définitions 50 et 52 et du Théor`eme 36. En bref, il établit que, dans les graphes de fusion parfaits, les séparations induites par des C-LPE constituent des segmentations intéressantes vis-à-vis des contraintes discutées dans l’introduction du présent chapitre. Théor`eme 53 (Théor`eme 13, Annexe B) Supposons que G soit un graphe de fusion parfait. Soit H une C-LPE de F. Alors, H est un W-amincissement de F. De plus, la séparation induite par H est un clivage mince. Afin d’illustrer le précédent théor`eme, intéressons-nous a` la Figure 3.3. La fonction H (figure b) est une C-LPE de la fonction F (figure a). On peut vérifier que H est bien un W-amincissement de F et que la séparation induite par H est bien un clivage mince. On remarque également qu’une C-LPE n’est pas une LPE topologique. Par exemple, H est une C-LPE mais comme les points d’altitude 9 sont W-destructibles, elle n’est pas une LPE topologique. Néanmoins, la propriété suivante implique que toute séparation induite par une C-LPE de F est égale a` une séparation induite par une LPE topologique de F. Propriété 54 (Propriété 14, Annexe B) Supposons que F soit une C-LPE. Toute séparation induite par un W-amincissement de F est égale a` la séparation induite par F. Les algorithmes de [73] pour calculer (la séparation induite par) une LPE topologique de F ne sont pas linéaires en temps de calcul et requi`erent une structure de données auxiliaire appelée 50 3.3. C-LPE dans les graphes de fusion parfaits arbre des coupes [78]. Nous allons montrer qu’il est possible d’atteindre, dans un graphe de fusion parfait, une meilleure complexité pour calculer une C-LPE, et donc d’apr`es la Propriété 54 une séparation induite par une LPE topologique. Dans une séquence de C-amincissements, les points qui sont dans un minimum a` une itération donnée ne deviennent jamais des points M-falaise dans les itérations suivantes. Cette observation nous conduit a` définir un algorithme (Algorithme 1) tr`es simple pour le calcul des C-LPE.