Lignes de partage des eaux dans les graphes à arêtes valuées

Graphes à arêtes valuées

Dans ce chapitre, nous étudions les LPE des fonctions qui valuent (pond`erent) les arêtes, et non les sommets, d’un graphe. Nous commençons par quelques rappels et définitions de bases pour appréhender ce genre de graphes. Soit C un sous-ensemble de E, nous rappelons que C désigne le complémentaire de C dans E, i.e., C = E \ C. Le graphe induit par C est le graphe dont l’ensemble d’arêtes est C et dont l’ensemble de sommets est composé de tous les points qui appartiennent à une arête de C, i.e., ({x ∈ V | ∃u ∈ C, x ∈ u}, C).

Par la suite, lorsque cela n’induit pas en confusion, le graphe induit par C est également noté C. Remarque importante : Nous disons que F(E) est la famille de toutes les fonctions qui valuent (pond`erent) les arêtes de G. Dans la suite de ce chapitre F désigne une fonction qui pond`ere les arêtes de G et, pour toute arête u dans E, F(u) est appelée l’altitude (pour F) de u. Dans les applications à la segmentation d’image, nous supposons que le niveau d’une arête u contenant deux pixels x et y, représente la dissimilarité entre les pixels x et y (e.g., F(u) est la différence absolue d’intensité entre x et y). Ainsi, nous supposons que les contours saillants sont localisés sur les arêtes les plus élevées. Soit k ∈ Z, notons que F[k], la section (supérieure) de F au niveau k, est l’ensemble des arêtes de G dont le niveau est supérieur ou égal à k.

Nous appelons minimum (régional) de F (au niveau k) toute composante X du graphe induit par F[k + 1] qui vérifie F[k] ∩ E(X) = ∅. Notons qu’un minimum régional dans un graphe à arêtes valuées est un sous-graphe (et non un sous-ensemble des sommets) de G. Nous désignons par M(F) le graphe dont les ensembles de sommets et d’arêtes sont, respectivement, l’union des ensembles de sommets et ensembles d’arêtes de tous les minima de F.

Lignes de partage des eaux

L’idée intuitive qui sous tend la notion de LPE provient de la topographie : une goutte d’eau tombant sur un relief topographique s’écoule selon un chemin descendant pour atteindre finalement un minimum du relief. La LPE peut être vue comme l’ensemble des lignes qui séparent les domaines d’attraction des gouttes d’eau. 

Extensions et coupures dans les graphes

Comme nous l’avons vu dans les chapitres précédents, la notion d’extension (Définition 13) joue un rˆole primordial pour définir une LPE (Définition 14). Nous commençons par adapter cette notion aux graphes, puis nous dérivons une définition de coupure dans un graphe qui est analogue à celle de clivage pour les ensembles de sommets (Définition 3). Définition 62 (extension dans un graphe) Soient X et Y deux sous-graphes non-vides de G. On dit que Y est une extension de X (dans G) si X ⊆ Y et si toute composante de Y contient exactement une composante de X. Les graphes (dessinés en gras) Figure 4.1b, c et d sont trois extensions de celui Figure 4.1a.

La notion d’extension est tr`es générale. De nombreux algorithmes de segmentation étendent dans un graphe des composantes dites “graines” : ils produisent une extension des graines. La 59 Chapitre 4. Lignes de partage des eaux dans les graphes à arêtes valuées (a) (b) (c) (d) Fig. 4.1 – Extension dans un graphe. Les ensembles de sommets et d’arêtes en gras sont : (a), un sous-graphe X ; (b), une extension de X ; (c), une extension Y de X qui est maximale ; et (d), forêt couvrante relative à X. L’ensemble des arêtes en traits pointillés Figure (c) est une coupure relative à X. plupart d’entre eux s’arrêtent lorsqu’ils ont atteint une extension qui couvre tous les sommets du graphe. La séparation ainsi produite est appelée coupure.

Définition 63 (coupure) Soient X ⊆ G et C ⊆ E. On dit que C est une coupure (de graphe) relative à X si C est une extension de X et si C est minimal pour cette propriété, i.e., T ⊆ C et T est une extension de X, impliquent T = C. L’ensemble C des arêtes en pointillé Figure 4.1c est une coupure relative à X (Figure 4.1a). On peut vérifier que C (en gras Figure 4.1c) est une extension de X et que C est minimal pour cette propriété. Si X est un sous-graphe de G et C une coupure relative à X, il peut être facilement démontré que C est une extension maximale de X. La notion de coupure qui est étudiée depuis de nombreuses années [14, 13], est souvent définie au moyen de partitions. Dans ce cas, un ensemble d’arêtes C ⊆ E est appelé coupure s’il existe une partition Ψ de V telle que C est l’ensemble des arêtes dont les extrémités sont dans deux ensembles distincts de la partition Ψ.

Si chaque ensemble de la partition est connexe et contient les sommets d’une unique composante d’un sous-graphe de G, alors C est une coupure relative à ce sous-graphe. Il peut être facilement vérifié que cette définition est équivalente à la Définition 63. Un des résultats les plus fondamentaux en optimisation combinatoire traite des coupures dans les graphes. Etan ´ t donnés deux sommets distincts d’un graphe à arêtes valuées (appelés source et puits), trouver une coupure de cout ˆ minimal qui sépare ces deux sommets est équivalent à trouver un flot maximum [2]. Il existe des algorithmes polynomiaux pour extraire une telle coupure (min-cut, en anglais).

A contrario, déterminer une coupure minimale parmi toutes les coupures relatives à un sous-graphe non réduit à deux sommets isolés est NP-difficile [97]. Dans les sections suivantes, nous introduisons les coupures par LPE et montrons qu’elles satisfont aussi une propriété d’optimalité. Un avantage majeur est qu’elles peuvent être calculées en temps linéaire