Lignes de partage des eaux d’un graphe a sommets values

Télécharger le fichier pdf d’un mémoire de fin d’études

Lignes de partage des eaux d’un graphe `a sommets valu´es

Pour son int´erˆet topographique, la ligne de partage des eaux (LPE) a ´et´e ´etudi´ee 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 ´et´e introduite par Digabel et Lantu´ejoul [93] pour la segmentation d’image et elle est main-tenant utilis´ee comme une ´etape fondamentale dans de nombreuses proc´edures 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´et´e comme son altitude dans le relief topographique. Un point est d’autant plus ´elev´e dans le relief qu’il est clair dans l’image. Les pixels sombres correspondent donc aux vall´ees et bassins du relief alors que les pixels clairs cor-respondent aux collines et lignes de crˆetes.
Une goutte d’eau tombant sur un relief topographique s’´ecoule selon un chemin descendant pour finalement atteindre un minimum r´egional. 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´efinitions de bases permettant d’appr´ehender une fonction num´erique discr`ete, nous pr´esentons diff´erentes notions et algorithmes de ligne de partage des eaux (LPE) et discutons leurs points forts et faiblesses.

Lignes de partage des eaux par distance topographique

Intuitivement, une goutte d’eau tombant sur un relief topographique s’´ecoule le plus “ra-pidement” possible vers un minimum. Comme nous l’avons mentionn´e dans la Remarque 6, la LPE par inondation ne respecte pas cette id´ee intuitive. Dans son article de 1993 [42] (voir ´egalement [43, 60]), F. Meyer propose la notion de LPE topographique. Il propose entre autres une caract´erisation reposant sur les chemins de plus grande pente.
D´efinition 8 (chemin de plus grande pente) Soit π = hx0, . . . , x`i un chemin dans V . On dit que π est un chemin descendant pour F si pour tout k ∈ [1, `], F (xk−1) ≥ F (xk).
On dit que π est un chemin de plus grande pente pour F si π est un chemin descendant pour F et si pour tout k ∈ [1, `], F (xk) = min{F (y), {xk−1, y} ∈ E}.
Le bassin d’attraction (topographique) de M (pour F ) est l’ensemble des points de V depuis lesquels M est le seul minimum de F qui peut ˆetre atteint par un chemin de plus grande pente pour F .
La LPE par distance topographique de F est l’ensemble des points de V qui n’appartiennent a` aucun bassin d’attraction de F .
Contrairement aux LPE par inondation, nous remarquons que la LPE par distance topogra-phique est d´efinie de mani`ere unique pour une fonction F donn´ee.
La Figure 1.7 montre les bassins d’attraction des fonctions pr´esent´ees Figures. 1.5 et 1.6.
Un autre d´efinition [42] de la LPE topographique repose sur une pseudo-m´etrique : la distance topographique. La motivation principale ´etait de fournir une d´efinition qui poss`ede de bonnes propri´et´es (voir ´egalement [43]) dans le cas de fonctions continues suffisamment r´eguli`eres (C2) pour permettre un lien entre LPE et squelettes par zones d’influence, une g´en´eralisation des cartes de Vorono¨ı.
D’apr`es les deux illustrations dont nous avons discut´ees ci-dessus, il est possible de d´eduire les deux remarques suivantes.

Lignes de partage des eaux topologiques

Les deux pr´ec´edentes notions de LPE s’int´eressent principalement aux bassins versants et non a` la “ligne” qui les s´epare. Dans certains cas, il est important de disposer d’un ensemble de pixels constituant une fronti`ere. Tout comme la LPE par immersion (Section 1.3.2), la ligne de partage des eaux topologique, introduite par M. Couprie et G. Bertrand en 1997 [104], produit une s´eparation entre les bassins. Le d´eveloppement et l’´etude [71, 73, 72] de cette approche radicalement diff´erente puise sa motivation dans la Remarque 7. Il est en effet souhaitable lorsque deux minima sont s´epar´es par une crˆete que les bassins versants correspondants soient s´epar´es par une crˆete de mˆeme altitude. La LPE topologique produit une s´eparation v´erifiant cette propri´et´e.

Lignes de partage des eaux d’un graphe a` sommets valu´es

De plus, comme l’ont montr´e les deux articles [71, 72], si l’on a besoin d’une transformation v´erifiant une telle propri´et´e alors il faut n´ecessairement utiliser une transformation de type “ligne de partage des eaux topologique”.
Extensions et LPE topologiques [71]
D´efinition 13 (extension ensembliste) Soient P et Q deux sous-ensembles de V . On dit que Q est une extension de P si P et Q sont vides ou si P ⊆ Q et si chaque composante de Q contient exactement une composante de P . Le sous-ensemble Q est une co-extension de P si Q est une extension de P .
Dans la Figure 1.3, l’ensemble Q form´e des sommets blancs dans la sous-figure (c) est une extension des sommets blancs de la sous-figure (a). Donc, Q (sommets noirs en (c)) est une co-extension de P (a).
Si H est un ´el´ement de F(V ) tel que, pour tout point p de V , H(p) ≤ F (p), on ´ecrit H ≤ F .
A travers ses sections sup´erieures, toute fonction de F(V ) peut ˆetre per¸cue comme un em-pilement d’ensembles. En fait, cette vision ouvre la voie vers une m´ethode syst´ematique pour ´etendre aux fonctions les d´efinitions ensemblistes. On remarque, par exemple, que H ∈ F(V ) est telle que H ≤ F si et seulement si pour tout k ∈ K, Hk ⊆ Fk : la relation ≤ ´etend la relation ensembliste ⊆. De la mˆeme mani`ere, il est possible d’´etendre les notions ensemblistes d’extension et co-extension aux ´el´ements de F(V ).
D´efinition 14 (LPE topologique) Soit H une fonction de F(V ).
On dit que H est une co-extension de F , si, pour tout k ∈ K, H[k] est une co-extension de F [k]. On dit que H est une LPE topologique de F si H est une co-extension minimale de F , i.e., H est une co-extension de F telle qu’il n’existe aucune co-extension I de F qui satisfasse I ≤ H et I 6= H. Dans ce cas, on dit ´egalement que la fonction H est une LPE topologique.
En d’autres termes, H est une LPE topologique de F si chaque section inf´erieure de H est une extension de la section inf´erieure correspondante de F et s’il n’existe aucune fonction I 6= H dont les composantes inf´erieures sont toutes des extensions des sections inf´erieures correspondantes de H.
La Figure 1.9a pr´esente un graphe G et une fonction F associ´ee. Une co-extension H de F est montr´ee en (b). Par exemple, H4 comprend trois composantes connexes (cercl´ees) et chacune d’elles contient exactement une composante connexe de F4 ; de la mˆeme mani`ere, les deux composantes de H5 contiennent les deux composantes de F5. De plus, nous pouvons observer, que si nous abaissions n’importe quelle valeur de H, la fonction r´esultante ne serait plus une co-extension de F : H est donc une LPE topologique de F . Une autre LPE topologique de F est repr´esent´ee en (c). Dans la sous-figure (d), nous montrons une co-extension J de F . Cette co-extension n’est pas une LPE topologique de F car H ≤ J, et H 6= J.

Ensembles minces et graphes d’arˆetes

Dans cette partie, nous pr´esentons les notions d’ensemble mince et de graphe d’arˆetes.
Commen¸cons par quelques rappels et d´efinitions ´el´ementaires 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 adja-cent 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´ec´edent nous avons abord´e les notions de W-amincissement ensembliste et de clivage qui reposent sur la suppression de points uniconnect´es. Dans la suite du pr´esent chapitre, et en particulier dans notre analyse des m´ethodes de fusion de r´egions, nous cherchons a` caract´eriser les invariants pr´eserv´es (ou non) lors de la suppression d’autres types de points.
D´efinition 25 Soit P ⊆ V , et soit p ∈ P .
On dit que p est un point de bord (pour P )
On dit que p est un point int´erieur (pour P )
si p est adjacent a` P .
si p n’est pas un point de bord pour P .
On dit que p est s´eparant (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 . Etant donn´e un ensemble de sommets P , tout ´el´ement de P est soit un point int´erieur soit un point de bord. Tout point de bord est soit uniconnect´e, soit s´eparant et tout point multiple est n´ecessairement un point s´eparant.
Dans l’exemple de la Figure 2.2a, p est a` la fois un point de bord et un point uniconnect´e pour l’ensemble P constitu´e des sommets noirs ; q est un point int´erieur. Dans la Figure 2.2b, z est un point de bord qui est s´eparant, et w est un point de bord s´eparant et multiple.
Dans ce chapitre, nous ´etudions certaines propri´et´es de minceur des clivages. Les notions de minceur et d’int´erieur sont ´etroitement li´ees.
D´efinition 26 (ensemble mince) Soit P ⊆ V , l’int´erieur de P , not´e int(P ), est l’ensemble des points int´erieurs pour P . On dit que l’ensemble P est mince si int(P ) = ∅.
En d’autres termes, l’int´erieur d’un ensemble P est int(P ) = {p ∈ P | Γ(p) ⊆ P }.

Caract´erisations locales

Les graphes de fusion faibles, fusion, fusion forts et fusion parfaits sont d´efinis par des conditions qui doivent ˆetre v´erifi´ees pour tous les sous-ensembles de sommets du graphe. Ainsi, en utilisant une m´ethode directe reposant sur les d´efinitions, v´erifier si un graphe appartient a` l’une de ces classes n´ecessite un temps de calcul exponentiel par rapport aux nombres de sommets du graphe.
A contrario, les graphes d’arˆetes peuvent ˆetre reconnus grˆace a` une condition qui peut ˆetre v´erifi´ee ind´ependamment dans un voisinage limit´e de chaque sommet. Existe-t-il de telles ca-ract´erisations pour les quatre classes de graphes de fusion ? Nous montrons dans cette section que les graphes de fusion faibles et les graphes de fusion ne peuvent pas ˆetre caract´eris´es lo-calement et donnons des conditions locales qui caract´erisent les graphes de fusion forts et les graphes de fusion parfaits.
Soit X un graphe, soit x ∈ V (X) et k ∈ N, nous d´enotons par ΓkX (x) le voisinage d’ordre k de x, c’est a` dire, ΓkX (x) = ΓX (ΓkX−1(x)), o`u Γ0X (x) = {x}.
Nous disons qu’il existe une caract´erisation locale d’une classe de graphes s’il existe k un entier positif arbitraire et P une propri´et´e sur les graphes tels qu’un graphe X est dans cette classe si et seulement si pour tout sommet x de X, P[X(x, k)] est vraie, X(x, k) ´etant le sous-graphe de X induit par ΓkX (x).
Propri´et´e 38 (Propri´et´es 35 et 36, Annexe A) i) Il n’existe pas de caract´erisation locale des graphes de fusion faibles.
ii) Il n’existe pas de caract´erisation locale des graphes de fusion.
Soient p et q deux sommets de G, on dit que p et q sont 2-adjacents si q ∈/ Γ(p) et Γ∗(p)∩Γ∗(q) 6= ∅.

Grilles d’adjacence usuelles en analyse d’image

Th´eor`eme 39 (Th´eor`eme 40, Annexe A) Le graphe G est un graphe de fusion fort si et seulement si, pour toute paire de points p, q ∈ V qui sont 2-adjacents, il existe a ∈ Γ∗(p) et b ∈ Γ∗(q) tels que a et b sont adjacents et Γ({a, b}) ⊆ [Γ(p) ∩ Γ(q)].
Nous rappelons que dans les graphes de fusion parfaits, toute paire de composantes voisines A et B de P (P ⊆ V ) peut ˆetre fusionn´ee a` travers Γ∗(A) ∩ Γ∗(B). Ainsi, les graphes de fusion parfaits constituent un cadre id´eal pour les m´ethodes de fusion de r´egions. Dans les propri´et´es suivantes, nous utilisons le symbole GN pour d´enoter le graphe (a) de la Figure 2.4.
Th´eor`eme 40 (Th´eor`eme 41, Annexe A) Les huit propositions suivantes sont ´equivalentes :
i) G est un graphe de fusion parfait ;
ii) pour tout x ∈ E, tout sous-ensemble de Γ(x) contient au plus deux composantes connexes ;
iii) pour tout clivage non-trivial P ⊆ V , chaque point p appartenant a` P est F-simple ;
iv) pour tout sous-ensemble connexe A de V , le sous-graphe de G induit par A est un graphe de fusion ;
v) pour tout sous-ensemble P de V , il n’existe aucun point multiple pour P ;
vi) le graphe GN n’est induit par aucun sous-ensemble de sommets de G ;
vii) tous sommets p, q et r de G, mutuellement non-adjacents, sont tels que Γ(p)∩Γ(q)∩Γ(r) = ∅ ;
viii) pour toute paire de points p, q ∈ V qui sont 2-adjacents, tout sommet r ∈ Γ∗(p) ∩ Γ∗(q) est tel que Γ(r) ⊆ [Γ(p) ∪ Γ(q)].
Remarquons que la proposition viii ressemble fortement a` la caract´erisation locale des graphes de fusion forts (Th´eor`eme 39). Nous rappelons que tout graphe d’arˆetes est un graphe de fu-sion parfait (Propri´et´e 35). Nous pouvons voir, grˆace au Th´eor`eme 40 (condition vi ), que les graphes de fusion parfaits peuvent ˆetre caract´eris´es d’une mani`ere similaire au Th´eor`eme 28 qui caract´erise les graphes d’arˆetes, mais avec une condition beaucoup plus simple. Remarquons, a` titre d’illustration, que tous les graphes de la Figure 2.4 except´es GN sont des graphes de fusion parfaits, car GN n’est un sous-graphe d’aucun de ces graphes.

Grilles d’adjacence usuelles en analyse d’image

L’objectif de cette section et de la suivante est de r´epondre a` la question : quelles sont les grilles (relations d’adjacence) qui peuvent ˆetre utilis´ees pour effectuer des op´erations de fusion maˆıtris´ees sur des images digitales ? Dans cette section, nous consid´erons les diff´erentes grilles utilis´ees commun´ement pour l’analyse d’images bidimensionnelles et tridimensionnelles. Notre r´esultat principal est qu’aucune de ces grilles n’est un graphe de fusion parfait, certaines n’´etant pas mˆeme des graphes de fusion. Nous montrons ainsi que l’op´eration de fusion la plus simple, qui consiste a` fusionner deux r´egions a` travers leur voisinage commun, n’est pas une op´eration maˆıtris´ee dans ces grilles.
Dans cette section et la suivante nous supposons que n est un entier strictement positif.
Soit P un ensemble, P n est le produit cart´esien de n copies de P . Tout ´el´ement p de P n peut ˆetre interpr´et´e comme une application de {1, . . . , n} dans P , pour tout i ∈ {1, . . . , n}, pi est la i-`eme coordonn´ee de p.
Nous consid´erons les familles d’ensembles H01, H11 telles que H01 = {{a} | a ∈ Z}, H11 = {{a, a + 1} | a ∈ Z}. Un sous-ensemble C de Zn qui est le produit cart´esien d’exactement m ≤ n ´el´ements de H11 et (n − m) ´el´ements de H01 est un m-cube.
Pour munir d’une structure de graphe les images digitales, des relations d’adjacence sont d´efinies sur Zn. Les d´efinitions suivantes permettent de retrouver les relations d’adjacence uti-lis´ees le plus fr´equemment en analyse d’image comme par exemple les 4- et 8- adjacence sur Z2.
D´efinition 41 Soit m ≤ n, deux ´el´ements distincts x et y de Zn sont m-adjacents s’il existe un m-cube qui contient a` la fois x et y. Nous d´efinissons Emn la relation telle que pour tous x et y dans Zn, {x, y} ∈ Emn si et seulement si x et y sont m-adjacents.
Afin de manipuler des graphes qui peuvent ˆetre arbitrairement grands, nous d´efinissons une grille comme une paire (Zn, E), o`u E est un sous-ensemble de {{x, y} | x ∈ Zn, y ∈ Zn, x 6= y}. Soit D ⊆ Zn, la restriction de (Zn, E) a` D est la paire (D, ED) telle que ED = {{x, y} ∈ E | x ∈ D, y ∈ D}. Si D est un ensemble fini, alors (D, ED) est un graphe. Dans la suite, pour simplifier les notations, nous omettons l’indice D et ´ecrivons donc E a` la place de ED.
Examinons tout d’abord le cas des grilles bidimensionnelles usuelles.
Propri´et´e 42 (Propri´et´es 45 et 47, Annexe A) Soient w et h deux entiers positifs tels que w > 2 et h > 2. Soit D = {x ∈ Z2 | 0 ≤ x1 < w et 0 ≤ x2 < h}.
i) Si {w, h} 6= {3, 4}, alors (D, E12) n’est pas un graphe de fusion faible. Si {w, h} = {3, 4}, alors (D, E12) est un graphe de fusion faible mais pas un graphe de fusion.
ii) Le graphe (D, E22) est un graphe de fusion mais n’est pas un graphe de fusion fort.
Dans la litt´erature (tout comme dans le Chapitre 1), la relation E12 (resp. E22) est g´en´eralement appel´ee 4− (resp. 8−) adjacence. Les affirmations suivantes sont des cons´equences directes de cette propri´et´e, des d´efinitions des graphes de fusion et du Th´eor`eme 36.
Soit P un sous-ensemble de pixels d’une image de dimension sup´erieure a` 3 × 4.
– Si l’image est ´equip´ee de la 4-adjacence, alors il est possible qu’aucune des composantes de P ne puisse ˆetre fusionn´ee (voir, par exemple, l’ensemble des sommets noirs Figure 2.8a).
– Si l’image est ´equip´ee de la 4-adjacence et si P est un clivage, alors il est possible que P ne soit pas mince (voir, par exemple, l’ensemble des sommets noirs et gris Figure 2.8a).
– Si l’image est ´equip´ee de la 8-adjacence, alors il est possible que deux r´egions voisines de P ne puissent ˆetre fusionn´ees (voir, par exemple, la Figure 2.8b).
– Si l’image est ´equip´ee de la 8-adjacence et si P est un clivage alors P est n´ecessairement mince.
Examinons maintenant le cas des grilles tridimensionnelles usuelles.
Propri´et´e 43 (Propri´et´es 49 et 50, Annexe A) Soient w, h et d trois entiers strictement sup´erieurs a` 1. Soit D = {x ∈ Z3 | 0 ≤ x1 < w, 0 ≤ x2 < h et 0 ≤ x3 < d}.
i) Le graphe (D, E13) n’est pas un graphe de fusion faible.
ii) Si w ≥ 5, h ≥ 5, d ≥ 5, alors le graphe (D, E33) n’est pas un graphe de fusion.
Dans la litt´erature, la relation E13 (resp. E33) est g´en´eralement appel´ee 6− (resp. 26−) adjacence.
Soit P un sous-ensemble de voxels d’une image de dimension sup´erieure a` 5 × 5 × 5.
– Si l’image est ´equip´ee de la 6-adjacence, alors il est possible qu’aucune des composantes de P ne puisse ˆetre fusionn´ee.

Minceur des LPE topologiques

Les s´eparations 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 ´epaisses mˆeme dans les graphes de fusion. Consid´erons par exemple les images F et H des Figure 3.1a et b et supposons qu’elles soient ´equip´ees de la 8-adjacence. Bien que la fonction H soit une LPE topologique de F et que le graphe consid´er´e soit un graphe de fusion (Propri´et´e 42), le pixel ´etiquet´e s (Figure 3.1b) est int´erieur pour M (H) la s´eparation induite par H. Donc M (H) n’est pas mince. Une telle ´epaisseur peut poser probl`eme pour d´efinir et impl´ementer une future ´etape de fusion de r´egions. Dans le chapitre pr´ec´edent, nous avons pr´esent´e un r´esultat (Th´eor`eme 36) qui permet de ca-ract´eriser, grˆace a` une propri´et´e de fusion, la classe des graphes dans lesquels tout clivage est mince. Les LPE topologiques ´etendent les clivages aux cas des fonctions (Th´eor`eme 17). Dans cette section nous pr´esentons un r´esultat similaire au Th´eor`eme 36 pour le cas des fonctions (Th´eor`eme 49).
Afin d’atteindre cet objectif, nous commen¸cons par introduire une d´efinition de minceur sur les fonctions qui ´etend la notion ensembliste (D´efinition 26) grˆace aux sections sup´erieures.
Remarque importante : Dans la suite de ce chapitre, F d´esigne une fonction de F(V ).
Soit k ∈ K. Nous rappelons que F [k], la section sup´erieure de F au niveau k est l’ensemble des sommets de G dont l’altitude est sup´erieure ou ´egale a` k.
D´efinition 48 (fonction mince) Soit x ∈ V et k = F (x). On dit que x est un point int´erieur pour F si x est int´erieur pour F [k]. L’int´erieur de F , not´e int(F ), est l’ensemble des points de M (F ) qui sont int´erieurs pour F . On dit que F est mince si int(F ) = ∅.
En d’autres termes, un point est int´erieur pour une fonction si tous ses voisins ont une altitude sup´erieure ou ´egale a` sa propre altitude. Ainsi, une fonction est mince si tout point dans la s´eparation qu’elle induit a au moins un voisin d’altitude strictement inf´erieure. 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 ´etiquet´e s est int´erieur).
Il d´ecoule de la d´efinition d’une LPE topologique et du Th´eor`eme 36 que, si toutes les LPE topologiques sont minces dans G, alors G doit n´ecessairement ˆetre un graphe de fusion. La fonction de la Figure 3.1b d´emontre que, contrairement au cas des clivages, la r´eciproque n’est en g´en´eral pas vraie. Malgr´e cela, comme l’´etablit le th´eor`eme de caract´erisation ci-dessous, il existe des liens forts entre ces deux classes de graphes.
Th´eor`eme 49 (Th´eor`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 sous-graphe de G induit par A est un graphe de fusion.
Nous remarquons que la condition ci-dessus, qui caract´erise les graphes dans lesquels toute LPE topologique est mince, est un affaiblissement de la condition iv du Th´eor`eme 40 qui caract´erise les graphes de fusion parfaits. Nous pouvons donc d´eduire que toute LPE topologique dans un graphe de fusion parfait est mince. En revanche, la r´eciproque 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.
D’une part, la notion de clivage formalise l’id´ee d’ensemble fronti`ere dans un graphe (D´efinition 3, Chapitre 1). D’autre part, la s´eparation induite par une LPE topologique constitue une seg-mentation int´eressante de l’image de d´epart (Chapitre 1). Il serait donc souhaitable que la s´eparation induite par une LPE topologique soit un clivage. Malheureusement, une telle pro-pri´et´e n’est pas toujours v´erifi´ee mˆeme pour un graphe dans lequel toutes les LPE topologiques sont minces. Consid´erons par exemple le graphe G et la fonction F de la Figure 3.2. On peut v´erifier, grˆace au Th´eor`eme 49, que toute LPE topologique dans G est mince. Cependant, on peut ´egalement observer que les points cercl´es en gras sont uniconnect´es pour M (F ) la s´eparation induite par F . Donc, M (F ) n’est pas un clivage. Observons ´egalement que le sommet noir est int´erieur pour M (F ) et donc que M (F ) n’est pas mince dans le sens ensembliste (D´efinition 26). Il d´ecoule de ce contre-exemple que la notion de minceur d´efinie dans cette section est trop faible et ne caract´erise pas les LPE topologiques adapt´ees aux m´ethodes de fusion de r´egions. Dans les sections suivantes, nous ´etudions les LPE topologiques dans las graphes de fusion parfaits et montrons que ce genre de probl`emes ne peut pas se produire.

Table des matières

1 Preambule : graphes, clivages et lignes de partage des eaux
1.1 Graphes
1.2 Clivages
1.3 Lignes de partage des eaux d’un graphe a sommets values
1.3.1 Fonctions numeriques discretes
1.3.2 Lignes de partage des eaux par inondation
1.3.3 Lignes de partage des eaux par distance topographique
1.3.4 Lignes de partage des eaux inter-pixel (par inondation)
1.3.5 Lignes de partage des eaux topologiques
1.3.6 Classication des lignes de partage des eaux
2 Graphes de fusion : clivages et proprietes de la fusion de regions
2.1 Introduction
2.2 Ensembles minces et graphes d’ar^etes
2.3 Fusion de regions
2.4 Graphes de fusion
2.5 Caracterisations locales
2.6 Grilles d’adjacence usuelles en analyse d’image
2.7 Grille de fusion parfaite
2.8 Conclusions
3 Graphes de fusion : ligne de partage des eaux et fusion de regions
3.1 Introduction
3.2 Minceur des LPE topologiques
3.3 C-LPE dans les graphes de fusion parfaits
3.4 LPE topologiques dans les graphes de fusion parfaits
3.5 Perspectives : schemas hierarchiques dans les grilles de fusion parfaites
4 Lignes de partage des eaux dans les graphes a ar^etes valuees
4.1 Introduction
4.2 Graphes a ar^etes valuees
4.3 Lignes de partage des eaux
4.3.1 Extensions et coupures dans les graphes
4.3.2 LPE par le principe de la goutte d’eau
4.3.3 Bassins d’attraction par une propriete de plus grande pente
4.4 For^ets couvrantes de poids minimum
4.5 Amincissements optimaux
4.5.1 Amincissement par bord et LPE
4.5.2 Algorithme lineaire de coupure par M-bord
4.6 Flux et algorithme de LPE lineaire
4.7 Coupures par LPE, for^ets de plus courts chemins et LPE topologiques
4.7.1 Valeur de connexion
4.7.2 For^ets de plus courts chemins
4.7.3 LPE topologiques
4.8 Illustrations et resultats experimentaux
4.8.1 Segmentation en k regions
4.8.2 Procedure semi-automatique de segmentation
4.8.3 Temps d’execution de quelques algorithmes de LPE
4.9 Conclusions
4.10 Annexe du Chapitre 4 : algorithme recursif de coupure par
5 Segmentation cardiaque spatio-temporelle
5.1 Introduction
5.2 Que segmenter ?
5.2.1 Topologie
5.2.2 Geometrie
5.2.3 Intensite
5.3 Comment segmenter ?
5.3.1 Frontiere endocardique
5.3.2 Frontiere epicardique
5.4 Donnees experimentales
5.4.1 Images
5.4.2 Segmentations manuelles
5.4.3 Segmentations automatiques
5.5 Resultats experimentaux
5.5.1 Precision des contours
5.5.2 Parametres critiques du diagnostic cardiaque
5.5.3 Coherence temporelle
5.5.4 Robustesse
5.6 Conclusions
Pour conclure 
1 Resume des contributions
1.1 Classication de quelques approches discretes de ligne de partage de eaux
1.2 Graphes de fusion : clivages et proprietes de la fusion de regions
1.3 Graphes de fusion : lignes de partage des eaux et fusion de regions
1.4 Ligne de partage des eaux dans les graphes a ar^etes valuees
1.5 Segmentation d’images cardiaques spatio-temporelles
2 Perspectives
2.1 Arbres de poids minimum par ligne de partage des eaux
2.2 Lignes de partage des eaux dans les complexes
2.3 Lignes de partage des eaux hierarchiques : saillance des contours
2.4 Analyse d’images medicales

Télécharger le rapport complet