Graphes, clivages et lignes de partage des eaux

Graphes, clivages et lignes de partage des eaux

Graphes

Segmenter une image consiste `a en extraire des “régions” possédant des caractéristiques intéressantes vis-`a-vis d’une application pratique. La notion de connexité est essentielle pour définir une région. L’objectif de cette premi`ere section est d’introduire les notions élémentaires de théorie des graphes qui fournissent, en particulier, les outils pour appréhender la connexité dans les ensembles discrets. Notations ensemblistes. Soit V un ensemble fini, le cardinal de V , noté |V |, est le nombre d’éléments de V . Soit V 0 un deuxi`eme ensemble, V 0 est inclus dans V , noté V 0 ⊆ V , si tout élément de V 0 est aussi un élément de V . Dans ce cas, on dit que V 0 est une partie ou un sous-ensemble de V . Si V 0 ⊆ V et V 0 6= V , on dit que V 0 est un sous-ensemble strict de V et on écrit V 0 ⊂ V . On désigne par 2V , l’ensemble de toutes les parties de V . L’union de V et V 0 , notée V ∪ V 0 , est l’ensemble formé des éléments de V et de V 0 . L’intersection de V et V 0 , notée V ∩ V 0 , est l’ensemble des éléments qui sont `a la fois dans V et dans V 0 . La différence (ensembliste) de V et V 0 , notée V \ V 0 , est l’ensemble des éléments de V qui n’appartiennent pas `a V 0 . Enfin, si V 0 ⊆ V , le complémentaire de V 0 dans V , noté V 0 V est l’ensemble V \ V 0 . Graphes. Un graphe est un couple X = (V (X), E(X)) composé d’un ensemble fini V (X) et d’un ensemble E(X) de paires non-ordonnées d’éléments de V (X), i.e., E(X) est un sousensemble de V (X)⊗V (X) = {{x, y} ⊆ V (X) | x 6= y}. Tout élément de V (X) est appelé sommet ou point (de X), et tout élément de E(X) est appelé arˆete (de X). Si V (X) 6= ∅, on dit que X est non-vide. Soit X un graphe. On consid`ere également l’application Γ? X, de V (X) dans l’ensemble des parties de V (X), qui associe `a tout sommet x de X l’ensemble de ses voisins : Γ? X(x) = {y ∈ V (X) | {x, y} ∈ E(X)}. De plus, pour tout sommet x de G, on désigne par ΓX(x) l’ensemble Γ(x) ∪ {x}. Soient x et y deux sommets de X. Si y ∈ Γ ? X(x), on dit que x et y sont adjacents (pour X). La figure suivante (Figure 1.1) montre un exemple de graphe X. Les sommets sont représentés par des cercles et les arˆetes par des segments reliant deux sommets. L’ensemble de sommets de X 7 graphes, clivages et lignes de partage des eaux Chapitre 1. Préambule : graphes, clivages et lignes de partage des eaux est : V (X) = {a, b, c, d, e, f, g, h,i, j, k} ; l’ensemble E(X) des arˆetes de X est : {{a, b}, {a, e}, {b, d}, {b, e}, {b, g}, {d, e}, {d, g}, {e, g}, {e,i}, {g, h}, {g,i}, {f, j}, {f, k}, {j, k}}. Le sommet a est adjacent a` b et Γ ∗ X(a) = {b, e}. a b c d e g h i j k f Fig. 1.1 – Un graphe. Chemin et connexité. Soit i et j deux entiers, i.e., i ∈ Z, j ∈ Z, on désigne par [i, j] l’ensemble {k ∈ Z | k ≥ i et k ≤ j}. Soit X un graphe. Soit π = hx0, . . . , x`i une séquence ordonnée de sommets de X, π est un chemin de x0 a` x` dans X si pour tout i ∈ [1, `], xi est adjacent a` xi−1. Dans ce cas, on dit que x0 et x` sont liés pour X. Si ` = 0, alors π est un chemin trivial dans X. Le graphe X est connexe si pour tout couple de sommets x et y de X, x et y sont liés pour X. Dans le graphe X de la Figure 1.1, la séquence ha, b, e, g, hi est un chemin : les sommets a et h sont liés. En revanche, les sommets b et c ne sont pas liés. En effet, il n’existe pas, dans X, de chemin de b a` c. Le graphe X n’est donc pas connexe. Par contre, le graphe Y = ({f, j, k}, {{f, j}, {f, k}, {j, k}}) est connexe. Remarquons également que X peut ˆetre “décomposé” en trois graphes connexes : il s’agit des composantes connexes de X. Sous-graphes et composantes connexes. Soient X et Y deux graphes. Si V (Y ) ⊆ V (X) et E(Y ) ⊆ E(X), on dit alors que Y est un sous-graphe de X et on écrit Y ⊆ X. On dit que Y est une composante connexe de X, ou simplement une composante de X, si Y est un sous-graphe connexe de X qui est maximal pour cette propriété, i.e., pour tout graphe connexe Z, Y ⊆ Z ⊆ X implique Z = Y . On peut remarquer que deux composantes connexes C et C 0 d’un graphe X sont nécessairement disjointes : V (C) ∩ V (C 0 ) = ∅ et E(C) ∩ E(C 0 ) = ∅. Le graphe Y = ({f, j}, {{f, j}}) (Figure 1.1) est un sous-graphe connexe de X mais ce n’est pas une composante connexe de X. En effet, le graphe Z = ({f, j, k}, {{f, j}, {f, k}, {j, k}}) est connexe et Y est un sous-graphe de Z ; Z, en revanche, est une composante connexe de X. Remarques importantes. Dans tout le manuscrit G désigne un graphe connexe. Pour simplifier les notations, on écrit G = (V, E) a` la place de G = (V (G), E(G)) et l’application associée ΓG est notée Γ. Nous supposons également que E 6= ∅.

Clivages

Intuitivement, dans un graphe, un clivage (ou une ligne de partage des eaux binaire) est un sous-ensemble de sommets qui ne peut ˆetre “réduit” sans changer le nombre de régions (i.e., composantes connexes) de son complémentaire. Cette notion, qui permet d’appréhender l’idée d’ensemble fronti`ere dans un graphe, est formalisée dans les définitions suivantes. Définition 2 (point uniconnecté) Soit P un sous-ensemble de V . On dit que p est uniconnecté (pour P) si p est adjacent a` exactement une composante de P. r p q (a) (b) (c) (d) Fig. 1.3 – W-amincissements ensemblistes et clivages. (a) : Un graphe G = (V, E) et un sous-ensemble P (sommets noirs) de V . Le point p est un point de bord qui est uniconnecté, et q est un point intérieur. (b) : L’ensemble Q = P \ {p} (sommets noirs) est un W-amincissement de P. (c) : L’ensemble R (sommets noirs) est un W-amincissement de P and Q. Les ensembles Q et R ne sont pas des clivages : il existe des points uniconnectés pour ces deux ensembles. (d) : Un clivage de P (sommets noirs), qui est aussi un clivage de Q et R. Le sommet p (Figure 1.3a) est uniconnecté pour l’ensemble P composé des sommets noirs. Il peut ˆetre remarqué que si l’on ote ˆ le point p de l’ensemble P, le nombre de composantes connexes de P (i.e., les sommets blancs) reste inchangé. Les sommets q et r ne sont, par contre, pas uniconnectés. En effet, ils sont adjacent a` respectivement 0 et 2 composantes connexes de P. Si l’on retire q de P, une nouvelle composante connexe blanche est créée ; si l’on retire r de P, alors deux composantes connexes blanches sont fusionnées. En fait, on peut montrer facilement 11 Chapitre 1. Préambule : graphes, clivages et lignes de partage des eaux qu’un sommet p peut ˆetre enlevé d’un ensemble P ⊆ V sans changer le nombre de composantes de P si et seulement si p est uniconnecté. Définition 3 (clivage) Soit P un sous-ensemble de V . Le sous-ensemble P est un clivage s’il n’existe aucun point uniconnecté pour P. L’ensemble Q des sommets noirs dans la Figure 1.3d ne contient aucun point uniconnecté : Q est donc un clivage. On a constaté précédemment que le point p est uniconnecté pour l’ensemble P (Figure 1.3a) : P n’est donc pas un clivage. Le processus de W-amincissement, introduit cidessous, permet de dériver un clivage a` partir d’un sous-ensemble quelconque de sommets. Définition 4 Soient P et Q deux sous-ensembles de V . On dit que Q est un W-amincissement de P si : i) Q = P ; ou si ii) il existe un sous-ensemble R de P qui est un W-amincissement de P et un point p ∈ R uniconnecté pour R, tel que Q = R \ {p}. Un sous-ensemble Q de P est un clivage de X (dans G) si Q est un W-amincissement de P et si Q est un clivage. En d’autres termes, un W-amincissement de P peut ˆetre obtenu, a` partir de P, par suppressions itératives de points uniconnectés; un ensemble Q est un clivage de P si Q est un Wamincissement de P qui ne contient pas de point uniconnecté. La Figure 1.3 montre un ensemble P et quelques W-amincissements de P, le dernier étant un clivage de P. Notons qu’il existe en général différents clivages d’un mˆeme ensemble P.

Lignes de partage des eaux d’un graphe `a sommets valués

Pour son intérˆet topographique, la ligne de partage des eaux (LPE) a été étudiée de mani`ere extensive d`es le 19`eme si`ecle par, entre autres, Maxwell [22] et Jordan [23]. Un si`ecle plus tard elle a été introduite par Digabel et Lantuéjoul [93] pour la segmentation d’image et elle est maintenant utilisée comme une étape fondamentale dans de nombreuses procédures de segmentation d’image (voir, par exemple, Figure 1.4). Une image en niveau de gris peut ˆetre per¸cue comme un relief topographique (cf. Figures. 1.4b et d). Le niveau de gris d’un pixel de l’image est interprété comme son altitude dans le relief topographique. Un point est d’autant plus élevé dans le relief qu’il est clair dans l’image. Les pixels sombres correspondent donc aux vallées et bassins du relief alors que les pixels clairs correspondent aux collines et lignes de crˆetes. Une goutte d’eau tombant sur un relief topographique s’écoule selon un chemin descendant pour finalement atteindre un minimum régional. Intuitivement, les lignes de partage des eaux (cf. Figures. 1.4c et e) du relief correspondent aux limites des domaines d’attraction des gouttes d’eau. Apr`es un bref rappel des définitions de bases permettant d’appréhender une fonction numérique discr`ete, nous présentons différentes notions et algorithmes de ligne de partage des eaux (LPE) et discutons leurs points forts et faiblesses.