Segmentation d’images 3D à l’aide de la carte …xlim-sic.labo.univ-poitiers.fr/publications/files/publi2184.pdf · thode de segmentation région, trois grandes familles qui

Master Sciences et Technologiesmention STIC (Sciences et Technologies de l’Information et de la

Communication)

Segmentation d’images 3Dà l’aide de la carte topologique

Alexandre DUPAS

Mémoire de Stage recherche M2, spécialité F3I

effectué sous la direction de Guillaume DAMIAND

au laboratoire SICUniversité de Poitiers - UFR SFA

Juillet 2006

Remerciements

Je remercie l’équipe du laboratoire SIC de m’avoir accueilli pendant cestage de Master Recherche.

Je remercie tout particulièrement Guillaume Damiand, mon encadrant destage, pour ses conseils, ses indications et sa lecture attentive de ce rapport.Je remercie également Carine Grasset-Simon pour ses conseils avisés que cesoit sur le fond ou sur la forme.

Enfin j’exprime ma gratitude envers ma famille et mes amis qui me sou-tiennent et me supportent tous les jours.

1

Table des matières

Introduction 7

1 Modèle de la carte topologique 91.1 Rappel sur les cartes combinatoires . . . . . . . . . . . . . . . 91.2 Opérations de suppression . . . . . . . . . . . . . . . . . . . . 121.3 Image et intervoxel . . . . . . . . . . . . . . . . . . . . . . . . 151.4 La carte topologique . . . . . . . . . . . . . . . . . . . . . . . 161.5 Construction de la carte topologique . . . . . . . . . . . . . . 171.6 L’arbre d’inclusion des régions . . . . . . . . . . . . . . . . . . 211.7 Représentation des sphères topologiques . . . . . . . . . . . . 231.8 La géométrie . . . . . . . . . . . . . . . . . . . . . . . . . . . 24

2 Opération de fusion 252.1 Principe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 252.2 Algorithme de fusion . . . . . . . . . . . . . . . . . . . . . . . 26

2.2.1 Détection des faces internes à E . . . . . . . . . . . . . 272.2.2 Mise à jour de l’arbre d’inclusion . . . . . . . . . . . . 282.2.3 Suppression des faces internes . . . . . . . . . . . . . . 342.2.4 Suppression des faces . . . . . . . . . . . . . . . . . . . 352.2.5 Simplification des arêtes . . . . . . . . . . . . . . . . . 362.2.6 Simplification des sommets . . . . . . . . . . . . . . . . 37

2.3 Complexité et résultats . . . . . . . . . . . . . . . . . . . . . . 382.3.1 Complexité de l’algorithme de fusion . . . . . . . . . . 382.3.2 Résultats . . . . . . . . . . . . . . . . . . . . . . . . . 39

3 Segmentation 433.1 Principes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43

3.1.1 Critère de segmentation : Erreur Quadratique . . . . . 43

3

3.2 Algorithme de segmentation . . . . . . . . . . . . . . . . . . . 443.3 Présegmentation . . . . . . . . . . . . . . . . . . . . . . . . . 46

3.3.1 Modification d’algorithme d’extraction . . . . . . . . . 463.3.2 Ajout de la présegmentation . . . . . . . . . . . . . . . 48

3.4 Résultats . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50

Conclusion 53

Bibliographie 55

4

Introduction

Le traitement d’images 3D est un défi qui se pose dans l’analyse et l’inter-prétation des images produites notamment par le monde médical. Les cartestopologiques ont été définies par [2] afin d’améliorer le traitement de cesimages. Ce modèle représente toutes les relations entre les cellules compo-sant une image 3D et mets ainsi à disposition des différents algorithmes cesinformations dans le but d’améliorer la qualité des traitements. La carte to-pologique propose une représentation compacte de toutes ces informationsfacilitant leur utilisation dans une chaîne de traitement d’images. En plus dumodèle en lui même, une méthode d’extraction d’une carte topologique surune image labélisée a été proposé. Celle-ci permet de construire une premièrecarte associée à une image déjà segmentée.

La segmentation d’image 3D est une tâche importante dans le traitementd’images qui joue un rôle clef dans l’analyse des images. La segmentationpeut être vue comme le découpage de l’image en régions homogènes selon uncritère particulier.

Nous nous intéressons dans ce travail à la segmentation dans la cartetopologique. Le modèle, dans sa définition même, découpe l’image en ré-gions. De ce fait, les approches de segmentation dîtes région, présentée dans[3], nous sont apparues comme les plus appropriées. Il y a, dans cette mé-thode de segmentation région, trois grandes familles qui sont les approchesbottom-up, top-down et mixte. L’approche bottom-up part d’une image sur-segmentée – pouvant même ne pas être segmentée du tout et donc avoir unerégion par voxel – et à l’aide de fusions successives de régions propose unemeilleure segmentation. L’approche top-down, à l’inverse, utilise une imagesous-segmentée et par divisions successives des régions produit une meilleuresegmentation. Enfin l’approche mixte combine les deux méthodes précédentesafin d’améliorer encore le résultat.

7

Nous avons choisis d’étudier l’approche bottom-up dans la carte topo-logique. Cette approche nécessite la connaissance des relations d’adjacenceentre les régions. Elle a également besoin d’une première segmentation dé-taillée qui peut être produite par l’algorithme d’extraction. Pour mettre enoeuvre cette méthode nous nous sommes d’abord intéressé à la définitiond’une opération de fusion de régions dans la carte topologique. Cette opéra-tion doit conserver les propriétés du modèle afin qu’elle puisse être utiliséedans la segmentation. D’autre part, pour travailler sur des images réelles,nous avons étudié la modification de l’algorithme d’extraction pour produireune première carte en partant d’une image quelconque et pas forcément d’uneimage labélisée. Cela nous permet d’effectuer une présegmentation ayant pourobjectif de diminuer le nombre de régions dans la carte initiale qui sera lepoint de départ de la segmentation.

Dans ce mémoire, nous commençons chapitre 1 par présenter le modèle descartes topologiques qui est le cadre de notre travail.

Dans un second temps, chapitre 2, nous détaillons toutes les étapes denotre algorithme de fusion. Cet algorithme permet de fusionner un nombrequelconque de régions connexes dans la carte topologique. Nous étudions enmême temps sa complexité et montrons quelques résultats.

Le chapitre 3 présente l’algorithme de segmentation ainsi que le critèred’homogénéité utilisé. Nous expliquons dans ce même chapitre les modifi-cations apportées à l’algorithme d’extraction afin d’obtenir une carte topo-logique à partir de de n’importe qu’elle image, et permettant aussi de laprésegmenter.

Enfin, nous concluons et présentons les perspectives sur lesquelles dé-bouche ce travail.

8

Chapitre 1

Modèle de la cartetopologique

La carte topologique est une structure combinatoire représentant les fron-tières intervoxels dans une image tridimensionnelle labélisée. Nous allonsmaintenant présenter cette structure de manière détaillée ainsi que les di-verses structures de données utilisées.

1.1 Rappel sur les cartes combinatoiresLa subdivision d’un espace topologique 3D est une partition de l’espace

en 4 sous-ensembles dont les éléments sont des 0D, 1D, 2D, 3D cellules (res-pectivement appelées sommets, arêtes, faces, volumes, et notées i-cellule pourune cellule de dimension i). Des relations de bords sont définies entre ces cel-lules où le bord d’une i-cellule est un ensemble de (j < i)-cellules. On dit quedeux cellules sont incidentes lorsqu’une appartient au bord de l’autre et quedeux cellules sont adjacentes si elles sont toutes les deux incidentes à unemême (j < i)-cellule.

La topologie d’une subdivision d’un espace 3D orientable sans bord peut-être représentée par une carte combinatoire de dimension 3 ou 3-carte. Nouspouvons obtenir une carte combinatoire 3D par la décomposition successived’un objet 3D (voir figure 1.1). Tout d’abord, nous distinguons les volumesd’un objet puis les faces de ces volumes, ensuite les arêtes de ces faces. Leséléments obtenus lors de la dernière décomposition sont appelés les brins.Ce sont les éléments de base d’une carte combinatoire. Pour obtenir la carte,nous ajoutons des relations d’adjacences portant sur les brins (notées βi). Cesopérations βi doivent vérifier des conditions particulières afin de s’assurer de

9

1.1. RAPPEL SUR LES CARTES COMBINATOIRES

A B C D

Fig. 1.1 – Les décompositions successives d’un objet pour obtenir la 3-cartecorrespondante. (A) Un objet 3D. (B) Volumes disjoints. (C) Faces disjointes.(D) Arêtes disjointes.

la validité de la subdivision représentée.

Définition 1 (Carte combinatoire 3D). Une carte combinatoire 3D, (ou 3-carte) est un quadruplet C = (B, β1, β2, β3) où :

1. B est un ensemble fini de brins ;2. β1 est une permutation sur B ;3. β2 et β3 sont des involutions sur B.4. β1 ◦ β3 est une involution.

Nous présentons dans la figure 1.2 B, un exemple de carte combinatoire quicorrespond à la décomposition de l’objet représenté dans la figure 1.2 A. β1

connecte les brins (représentant des arêtes orientées) entre eux pour formerles faces. β2 connecte les brins incidents à la même arête et au même volume.β3 connecte deux brins incidents à la même arête et à la même face. Afin desimplifier le schéma, nous ne représentons pas explicitement les relations βi

mais elles peuvent être déduites de la forme des objets comme nous pouvonsle voir figure 1.2 B.

Dans le cadre des cartes combinatoires, toutes les cellules sont représen-tées par la notion d’orbite. Intuitivement une orbite < βi1 , . . . , βij > (b) estl’ensemble des brins qui peuvent être atteint dans un parcours en largeur dela carte en partant du brin b et en utilisant toutes les compositions possibledes βik ou β−1

ikpermutations, avec k compris entre 1 et j. Avec cette notion,

10

1.1. RAPPEL SUR LES CARTES COMBINATOIRES

4

1

3

2

A B

Fig. 1.2 – Représentation usuelle d’une carte combinatoire 3D. (A) Un objet3D. (B) Représentation implicite de la carte combinatoire correspondante.Les applications βi ne sont pas explicitement dessinées mais peuvent géné-ralement être déduite de la forme des objets. Les brins sont représentés pardes flèches noires qui donnent l’orientation des faces. Deux brins consécutifssont liés par β1. Les brins liés par β2 et β3 sont dessinés proches, parallèleset dans une orientation inverse. Dans cet exemple, nous pouvons retrouverque β1(1) = 2, β2(1) = 3 et β3(2) = 4.

11

1.2. OPÉRATIONS DE SUPPRESSION

chaque cellule est définie par une orbite particulière. La définition 2 présentela définition formelle d’une orbite.

Définition 2 (Orbite). Soit Φ = {f1, . . . , fk} un ensemble de permutationssur B. Nous notons < Φ > le groupe de permutations généré par Φ. Il s’agitde l’ensemble des permutations obtenues par toutes compositions et inversionsdes permutations contenues dans Φ. L’orbite d’un brin b relativement à Φ estdéfinit par < Φ > (b) = {φ(b)|φ ∈ Φ}.

L’orbite < β1, β2 > décrit un volume, l’orbite < β1, β3 > une face, l’orbite< β2, β3 > une arête et l’orbite < β−1

1 β2, β−11 β3 >. En se basant sur la

définition des cellules, nous pouvons retrouver la notion de degré des cellules.

Définition 3 (Degré d’une cellule). Le degré d’une i-cellule c est le nombrede (i + 1)-cellules distinctes qui sont incidentes à c.

Dans un espace de dimension n, la notion de degré n’est définie que pourles i-cellules avec 0 ≤ i < n. En effet, les cellules de degré n + 1 n’existentpas dans un tel espace.

Dans ce travail, nous avons également besoin de la notion de degré lo-cal. Ce degré local est mis en place afin de pouvoir distinguer différentesconfigurations de multi-incidences.

Définition 4 (Degré local d’une cellule). Le degré local d’une i-cellule c estla somme pour chaque (i + 1)-cellules c′ incidente à c du nombre de fois quec′ est incidente à c.

Intuitivement cette notion correspond à la notion classique de degré d’unecellule mais en considérant les cellules localement. En général le degré d’unecellule est égal au degré local d’une cellule. Les différences apparaissent lors-qu’une cellule est plusieurs fois incidente à la cellule considérée (par exemple,dans le cas d’un sommet incident à une boucle).

1.2 Opérations de suppressionLes cartes topologiques sont principalement construites à l’aide d’opé-

rations de suppression. L’opération de suppression en dimension i (noté i-suppression) consiste à supprimer une i-cellule. La suppression d’une i-celluleconduit à la fusion des deux (i + 1)-cellules qui lui sont incidentes. Pourune subdivision 3D, nous pouvons supprimer une face (2-suppression), unearête (1-suppression) ou un sommet (0-suppression). Nous présentons ici lesgrandes notions à propos de ces opérations. Une description plus complètepeut être trouvée dans [1] où la définition générale de la suppression et de lacontraction est donnée en toutes dimension.

12


d

A B C

Fig. 1.3 – 2-suppression d’une face incidente à un brin b. (A) Configurationinitiale avec deux volumes adjacents. (B) 2-décousure de tous les brins de laface incidente au brin b. (C) 2-couture des brins décousus, les deux volumesinitiaux sont fusionnés.

N’importe qu’elle face d’une 3-carte peut-être supprimée sans contraintecar le degré d’une face dans une subdivision 3D est toujours égal à un oudeux. La suppression de face consiste principalement à modifier les relationsβ2 pour chaque brin appartenant au voisinage de la face supprimée. Nouspouvons observer cette opération figure 1.3.

La suppression d’arête (1-suppression) ne peut être appliquée que pourles arêtes de degré un ou deux. Dans le cas contraire, il est impossible dedécider automatiquement comment connecter les faces incidentes à l’arêtesupprimée. Cette opération s’effectue de manière similaire à la suppressionde face sauf que l’on modifie ici les relations β1 (voir figure 1.4).

La suppression de sommet (0-suppression) peut seulement être appliquéeaux sommets de degré un ou deux. Le traitement est similaire à la suppressiond’arête mais plusieurs cas sont à prendre en considération dû à la définitionnon-homogène des cartes combinatoires (β1 est une permutation alors queles autres βi sont des involutions). La figure 1.5 montre un exemple de 0-suppression.

La validité des opérations de suppression peut être prouvée quelque soitla configuration initiale et la cellule à supprimer.

13


d d

A B C

Fig. 1.4 – 1-suppression d’une arête incidente à un brin b. (A) Configurationinitiale avec deux faces adjacentes. (B) 1-décousure de tous les brins de l’arêteincidente au brin d. (C) 1-couture des brins décousus, les deux faces initialessont fusionnées.

d d

A B C

Fig. 1.5 – 0-suppression d’un sommet incident à un brin b. (A) Configurationinitiale avec deux arêtes adjacentes. (B) 1-décousure de tous les brins dusommet incident au brin b. (C) 1-couture des brins décousus, les deux arêtesinitiales sont fusionnées.

14

1.3. IMAGE ET INTERVOXEL

pointel

surfel

voxel

linel

Fig. 1.6 – Les différentes cellules de l’intervoxel dans un espace 3D.

1.3 Image et intervoxelUn voxel est un point de l’espace discret Z3 associé à une valeur qui peut

être une couleur, un niveau de gris, . . . . Une image tridimensionnelle est unensemble fini de voxels. Nous utilisons la notion de 0-connectivité lorsquedeux voxels se touchent par un sommet, 1-connectivité lorsque deux voxelsse touchent par une arête et 2-connectivité lorsque deux voxels se touchentpar une face. Dans l’ensemble de ce rapport, nous utiliserons la notion de 2-connectivité lorsque nous cherchons des éléments connexes. Nous utilisons descartes combinatoires pour représenter des ensembles de voxels d’une imagelabélisée qui ont la même valeur et sont 2-connexes.

Définition 5 (Image labélisée). Une image labélisée est un ensemble devoxels tel que deux voxels ayant le même label appartiennent à la même com-posante 2-connexe.

Nous parlons de région pour un ensemble de voxel ayant le même label.Deux voxels ayant un même label appartiennent à la même région et deuxrégions différentes ont des labels différents.

Dans le cadre de l’intervoxel, une image n’est pas seulement considéréecomme une matrice de voxels mais comme une subdivision d’un espace 3Den un ensemble de cellules : les voxels sont les 3-cellules, les surfels entre deux3-cellules sont les 2-cellules, les lignels entre deux 2-cellules sont les 1-celluleset les pointels entre deux 1-cellules sont les 0-cellules. La figure 1.6 montreles différentes cellules de l’intervoxel. Avec ces cellules, la notion de surfaceest définie comme un ensemble de surfels adjacents et la notion de courbecomme un ensemble de lignels adjacents.

La frontière en intervoxel entre deux régions Ri et Rj est l’ensemble dessurfels incidents à un voxel de Ri et un voxel de Rj. La frontière entre deuxrégions peut être vide lorsque les régions ne sont pas adjacentes et qu’elle

15

1.4. LA CARTE TOPOLOGIQUE

R1

R2

R3

R0 1

24

5

3

6

A B

Fig. 1.7 – Intervoxel et frontière d’une image labélisée. (A) Une image 3D.(B) Bords en intervoxel des régions de l’image. Il y a 6 surfaces frontièresétiqueté de 1 à 6 dans cette figure

peut être formée d’une unique surface ou de plusieurs surfaces en cas demulti-adjacence.

Afin d’éviter des traitements particuliers sur les bords de l’image, nousconsidérons une région infinie R0 contenant tous les voxels n’appartenantpas à l’image. Avec cette région, chaque voxel a exactement 6 voisins. On ditqu’une région Ri est incluse dans une autre région Rj si et seulement si tousles chemins 2-connexes allant d’un voxel de Ri à un voxel de la région infinieR0 contient au moins un voxel de la région Rj. Chaque région est donc aumoins incluse dans la région infinie.

La figure 1.7 A représente une image labélisée et la figure 1.7 B ses fron-tières en intervoxel. Il y a 6 différentes surfaces frontières dans cette image.Par exemple, la surface frontière entre les régions R0 et R1 qui est étiqueté 1dans la figure 1.7 B, et celle entre R2 et R3 qui est étiqueté 5. Il est à noterque la définition de frontière en intervoxel est valide pour toutes régions grâceà l’existence de la région infinie.

1.4 La carte topologiquePour représenter des images labélisées, l’idée principale de la carte to-

pologique est tout d’abord de construire une carte combinatoire complètequi représente toutes les cellules de l’intervoxel et de la simplifier progres-sivement à l’aide des opérations de suppression tant que l’on ne perd pasd’informations topologiques.

16

1.5. CONSTRUCTION DE LA CARTE TOPOLOGIQUE

La carte topologique est la carte minimale obtenue par ce principe. Ellereprésente toutes les relations d’incidences et d’adjacences entre les régionsde l’image. C’est là le principal intérêt de la carte topologique : être minimaletout en conservant les informations d’adjacences et d’incidences. Pour éviterde perdre des informations, nous contrôlons les opérations utilisées pendantla construction. Il y a deux problèmes pouvant se poser :

– le premier est celui de la déconnexion de volume (voir figure 1.8) quandune région est complètement incluse dans une autre. Dans ce cas, nousobtenons un modèle qui comporte deux composantes connexes, l’unereprésentant la surface externe et l’autre représentant la surface interne.Pour résoudre ce problème, nous ajoutons un arbre d’inclusion sur lesrégions de l’image. Cet arbre nous permet de conserver les relationsentre ces deux surfaces.

– le second problème est celui de la déconnexion de face, quand une faceà plusieurs bords (voir figure 1.9).Nous ajoutons pour en tenir compte une contrainte sur la 1-suppression.Ce cas ne se produit lorsque nous supprimons une arête de degré 1 quin’est pas pendante. Si nous ne supprimons pas cette arête, les bords dela carte restent reliés et par conséquent chaque face est homéomorpheà un disque topologique.Nous appelons arêtes fictives ces arêtes particulières que l’on gardepar contrainte additionnelle car elles ne représentent aucune relationd’adjacence entre les régions.Par opposition, les autres arêtes sont appelées arêtes réelles. Nous intro-duisons également la notion de degré réel d’un sommet qui est le degrédu sommet sans considérer les arêtes fictives qui lui sont incidentes.

1.5 Construction de la carte topologiqueLa construction de la carte topologique (son extraction) est réalisée au

travers de 5 étapes chacune d’entre elles étant une simplification de la carteobtenue à l’étape précédente.

– Etape 1 : Initialisation. Soit une image 3D labélisée, construire une3-carte représentant une grille 3D composée de cubes et d’un volumeenglobant représentant la région infinie.

– Etape 2 : Supprimer toutes les faces partagées par deux voxels ayant lemême label. Cette étape fusionne les volumes appartenant à la mêmerégion. Après cette étape, chaque frontière entre deux régions est re-présentée par une unique surface composée de faces carrées correspon-dantes aux surfels.

17


A B

Fig. 1.8 – Déconnexion de volumes. (A) Une carte durant sa construction.A ce moment, la carte est connectée. (B) Après la 2-suppression de la facesombre, la carte est maintenant composée de deux composantes connexesdistinctes.

A B

Fig. 1.9 – (A) La face supérieure du volume du dessous possède deux bords.(B) Afin de conserver toutes les faces homéomorphes à un disque, on conserveune arête dîtes fictives.

18


– Etape 3 : Supprimer toutes les arêtes de degré deux et toutes les arêtespendantes sauf les arêtes isolées. Cette étape simplifie les frontières dechaque région en fusionnant ses faces. Nous pouvons classer chaquearête e en fonction de son degré d :– d > 2 : e n’est pas supprimée pour respecter la précondition de la

1-suppression. Ces arêtes appartiennent à la jonction de différentesfrontières ;

– d = 2 : e est supprimée parce que les deux faces incidentes appar-tiennent à la même frontières et peuvent donc être fusionnées en uneface unique. De plus cette suppression n’entraîne pas de déconnexionparce que les deux faces sont différentes ;

– d = 1 et e est une arête isolée : ce cas correspond à la représenta-tion minimale de la sphère avec deux sommets, une arête isolée etune face (voir section 1.7). Ainsi, e n’est pas supprimée sinon noussupprimerions une surface qui représente une relation d’adjacence.

– d = 1 et e est une arête pendante : e est supprimée parce qu’elle nereprésente aucune relation d’adjacence et sa suppression n’entraînepas de déconnexion.

– d = 1 et e n’est pas une arête pendante : e n’est pas supprimée pourne pas entraîner de déconnexion. C’est l’unique cas qui entraîne lacréation d’une arête fictive.

– Etape 4 : Supprimer tous les sommets de degré réel deux incidents àdeux arêtes qui ne sont pas des boucles, après avoir déplacer toutes lesarêtes fictives incidentes à ce sommet. Cette étape simplifie les fron-tières de chaque région en fusionnant les arêtes réelles. Comme cetteétape et la suivante sont concernées par le degré réel des sommets, lesexplications sont proposées après l’étape suivante.

– Etape 5 : Supprimer tous les sommets de degré réel zéro incidents à aumoins deux arêtes, y compris une non-boucle, après avoir déplacé lesarêtes fictives qui sont incidentes à ce sommet le long de l’arête non-boucle. Cette étape permet de simplifier les frontières de chaque régionen groupant les arêtes fictives sur le même sommet.Nous pouvons classer chaque sommet v en fonction de son degré réel d.Nous considérons le degré réel et non le degré puisque nous ne tenonspas compte des arêtes fictives durant la simplification des bords. Maiselles sont nécessaire pour garder chaque face connectée et pour cela,elles sont déplacées (poussées le long d’une arête incidente) avant lasuppression d’un sommet. Si le degré d est :– d > 2 : v n’est pas supprimé parce qu’il appartient à la jonctions de

différentes frontières avec plus de deux arêtes réelles ;– d = 2 : si au moins une arête réelle est une boucle, v n’est pas

19


A B C D E

Fig. 1.10 – Les différents étapes de la carte topologique (A) Image des diffé-rentes faces de l’image. (B) Carte complète avec tous les voxels explicitementreprésentés. (C) Les faces séparant deux voxels de la même région sont sup-primées. (D) Les arêtes de degré 2 sont supprimées. (E) Les sommets dedegré 2 sont supprimées. La carte est minimale.

supprimé car la boucle correspond à une face et ainsi représente uneinformation d’adjacence. Sinon, v est supprimé parce que les deuxarêtes réelles incidentes appartiennent au même bord ;

– d = 1 : v n’est pas supprimé parce que l’arête réelle incidente est uneboucle (et nous sommes donc dans le même cas que précédemment) ;

– d = 0 : si v est incident à une unique arête, il n’est pas supprimépuisque nous sommes dans le cas d’une sphère. Si v est seulementincident à 2k boucles, v n’est pas supprimé car il s’agit de la repré-sentation minimale d’un tore à k trous. Sinon, il y a au moins deuxarêtes et au moins une arête qui n’est pas une boucle. Dans ce cas,nous supprimons v afin de regrouper les arêtes fictives sur un mêmesommet.

Nous avons ainsi présenté la construction de la carte topologique par étapessuccessives comme la figure 1.10 le montre. En pratique nous utilisons unalgorithme incrémental d’extraction qui extrait la carte topologique en uneseule passe de l’image. L’image est balayée de gauche à droite, de derrière àdevant et de haut en bas. Pour chaque voxel, un cube est ajouté à la cartecombinatoire déjà construite. Puis nous supprimons des faces, des arêtes etdes sommets en fonction de la configuration locale.

Cet algorithme ne fonctionne actuellement que pour des images labéliséeset donc présegmentées. Le mode de construction ne permet pas d’utiliser desvraies images puisqu’il part du principe que tous les voxels d’une mêmecouleur sont connexes et forment ainsi une seule région. Hors dans le casgénéral, cette hypothèse s’avère fausse.

Nous verrons dans la section 3.3 comment nous avons résolu ce problèmeà l’aide d’une version modifiée de l’opération d’extraction.

20

1.6. L’ARBRE D’INCLUSION DES RÉGIONS

1.6 L’arbre d’inclusion des régionsNous avons vu que l’arbre d’inclusion des régions a été introduit pour

résoudre le problème de déconnexion entre les faces internes et la face ex-terne d’une région. En effet une région R dans la carte peut être composéede plusieurs surfaces déconnectées lorsqu’il y a plusieurs régions totalementincluses dans R.

Chaque brin de la carte est lié à sa région d’appartenance notée region(b)et vérifie que : ∀b∀b′, region(b) = region(b′) si et seulement si b et b′ appar-tiennent à la même région.

Chaque région dans la carte topologique est associée à un de ses brins.Ce brin est appelé brin représentant. Il doit appartenir à la face externe de larégion, nous permettant de retrouver les régions de la composante connexeà l’aide des opérations βi ainsi que la face interne correspondante dans larégion englobante.

L’arbre d’inclusion a toujours pour racine la région infinie R0 qui englobenotre image. Cette région permet à la carte d’être une subdivision complètede l’espace puisque tout voxel n’appartenant pas à l’image est dans la régioninfinie.

Lorsque qu’une région R possède des régions totalement incluses, si cesrégions sont dans une même composante connexe, alors R ne possède qu’uneface interne. De même si les régions incluses sont dans deux composantesconnexes différentes, alors la région possède deux faces internes. De manièregénérale, R possède une face interne pour chaque composante connexe derégions incluses dans R. Ainsi pour pouvoir retrouver toutes les faces in-ternes, en sachant à quelles régions ces faces internes correspondent, nousutilisons non seulement les relations d’inclusion mais également les relationsde composantes connexes. Il s’agit d’une optimisation permettant de parcou-rir rapidement toutes les surfaces d’un volume.

Les régions sont donc regroupées dans des listes de composantes connexes.Toutes les régions de cette liste sont incluses dans la même région R, etsont entourées par la même surface interne de R. La tête de cette liste estappelée région représentante de la composante connexe. Le brin représentantde cette région a pour particularité que son β3 est un brin de la face internede la région englobante.

21

1.6. L’ARBRE D’INCLUSION DES RÉGIONS

R

R R

R

RR

R

R01

2

34

6

75

7

6

5

2

3

1

4

0

Fig. 1.11 – Une image et son arbre d’inclusion. Il faut voir l’image comme lacoupe au milieu d’une image 3D. Le plan du dessus et du dessous étant com-posés de voxels appartenant tous à la région R1. Dans l’arbre, les rectanglesreprésentent les composantes connexes. Les flèches représentent les relationsd’inclusions directes. La région représentante de chaque composante connexeest la première de chaque rectangle.

Nous ajoutons aux régions représentantes des composantes connexes, larelation d’inclusion avec la région englobante. Ainsi chaque région R est liéedirectement avec les régions représentantes des composantes connexes quisont incluses dans R. Ces informations d’inclusion sont représentées par unarbre n-aire que nous implémentons par les relations fils-frère. Nous pouvonspar ce biais retrouver directement les différentes surfaces internes de la régionR.

Enfin, pour pouvoir naviguer dans l’arbre aussi bien en descendant de laracine vers les feuilles qu’en remontant, nous avons ajouter une relation pèrequi lie chaque région à sa région englobante.

Nous ne représentons dans notre arbre que les inclusions directes, lesautres pouvant être retrouvées par transitivité (si Ri est incluse dans Rj etsi Rj est incluse dans Rk alors Ri est incluse dans Rk).

Prenons l’exemple proposé figure 1.11. Toutes les régions sont incluses dansla région infinie R0. Nous avons les régions R1, R2, R3 et R4 qui sont dansune même composante connexe directement incluse dans R0. Les régions R2,R3 et R4 sont incluses dans R0 et pas dans R1 par ce qu’il existe un chemin2-connexe parmi les voxels de l’image permettant de passer de R2, R3 ouR4 à R0 sans passer par R1. Nous avons la région R5, dans une composanteconnexe séparée, incluse dans la région R1. Enfin les région R6 et R7 qui sont

22

1.7. REPRÉSENTATION DES SPHÈRES TOPOLOGIQUES

Face 1Face 1

Face 1

Face 2

A B

Fig. 1.12 – Deux représentations minimales de la sphère. (A) Représentation(choisie dans notre modèle) de la sphère avec deux sommets, une arête et uneface. (A) Représentation de la sphère avec un sommet, une arête et deux faces.

dans une même composante connexe et incluses dans la région R1.

1.7 Représentation des sphères topologiquesL’un des problèmes restant dans notre modèle est celui de la représenta-

tion des sphères. En effet, les sphères (topologiques) peuvent être représentéesde deux manières différentes : soit avec une face, une arête, deux sommets ;soit avec deux faces, une arête et un sommet comme nous le montre la figure1.12.

Ces deux représentations de la sphère sont minimales en terme de cellulespuisque chacune nécessite 4 cellules pour être représentée. Nous avons doncune double représentation de la sphère. Afin de ne pas avoir à prendre enconsidération les deux cas possible, nous avons choisit de ne conserver qu’uneseule représentation dans la carte topologique.

Intuitivement, une sphère n’a qu’une seule surface de contact avec sarégion englobante. Ainsi dans le modèle, la première représentation (c’està dire la sphère avec deux sommets, une arête et une face présentée figure1.12 A) est utilisée.

Nous pouvons passer d’une représentation à l’autre échangeant les rela-tions β2 et β3.

23

1.8. LA GÉOMÉTRIE

A B

Fig. 1.13 – Carte et plongement en intervoxel. (A) Deux représentations dela même carte avec deux faces, trois arêtes et deux sommets. (B) Surfaceset courbes correspondantes dans l’intervoxel. Tous les surfels représentés engris foncé sont le plongement de la face représentée par les brins dessiné engris.

1.8 La géométriePour pouvoir utiliser toutes les informations liées à chaque région, nous

associons un plongement à la carte combinatoire. Pour chaque face dans lacarte combinatoire, nous associons un ensemble de surfels correspondant àune surface frontière. Pour chaque arête non-fictive dans la carte combina-toire, nous associons un ensemble de lignels formant la courbe de l’arête.Enfin nous plongeons chaque sommet de la carte par un pointel.

Ces informations sont stockées dans une matrice appelée matrice intervoxelqui permet de représenter tout l’intervoxel d’une image 3D. En fait, nousassocions à chaque brin un triplet désignant un pointel, un lignel et un surfeldans la matrice de l’intervoxel. La surface associée à une face de la cartetopologique, se retrouve en parcourant l’ensemble des surfel adjacents dansla matrice intervoxel. Nous observons figure 1.13 la représentation dans lacarte de deux faces, trois arêtes et deux sommets et leur plongement dans lamatrice de l’intervoxel.

24

Chapitre 2

Opération de fusion

Nous avons besoin, afin de mettre en oeuvre une méthode de segmentationbottom-up, d’une opération de fusion de régions dans la carte topologique.Cette opération a pour objectif de rassembler dans une même région la partiede l’image désignée par un ensemble fini de régions connexes de l’image.

La fusion s’applique sur une carte topologique et doit donc conserver sapropriété de minimalité. De plus, cette opération doit être efficace puisqu’elleest amenée à être abondamment utilisée dans le cadre de la segmentationbottom-up.

2.1 PrincipeLa fusion de régions travaille dans la carte topologique à plusieurs ni-

veaux. D’une part, il faut que la topologie représentée par la carte combina-toire soit mise à jour. L’arbre d’inclusion des régions qui contient lui aussi desinformations topologique doit également refléter l’ensemble des modificationsengendrées par la fusion. Enfin la géométrie représentée dans notre modèlepar l’intervoxel doit également correspondre à la nouvelle région.

Afin de limiter le temps d’exécution de notre processus de fusion, nous cher-chons une opération qui soit locale, n’impliquant pas de reconstruire toutela carte après chaque fusion. Nous nous restreignons alors à modifier la carteafin de refléter le résultat de la fusion. Il s’agit essentiellement de supprimerles faces internes des régions tout en tenant compte des problèmes de décon-nexions. Afin de résoudre ces problèmes, nous modifions l’arbre d’inclusiondes région pour qu’il corresponde à l’image après la fusion. Les suppres-sions entraînent l’apparition de cellules non-minimales, c’est à dire que l’onpeut supprimer sans perte d’informations. Ainsi nous simplifions les arêtes et

25

2.2. ALGORITHME DE FUSION

sommets de manière analogue au processus de simplifications successives quipermet de construire la carte topologique à partir de la carte combinatoirecomplète.

Nous travaillons sur la fusion d’un ensemble de n régions 2-connexes oùde nombreuses configurations différentes peuvent apparaître. Nous pouvonsciter par exemple le cas d’inclusion de régions dans la région résultat oula déconnexion de composantes connexes parmi les régions préalablementincluses dans la région résultat. L’algorithme doit fonctionner dans tous lescas possibles.

2.2 Algorithme de fusionDans la carte, nous pouvons identifier les faces qui sont incidentes à deux

régions de l’ensemble des régions à fusionner. Nous qualifions ces faces d’internes.Ces faces internes sont des éléments superflus dans la définition de la

carte topologique. Notre objectif est donc de les supprimer puis de simplifierles arêtes et sommets incidents dont la configuration a pu changer. Ainsinous obtenons progressivement la carte topologique minimale associée à notreimage fusionnée.

L’opération de fusion telle que nous l’avons définie se déroule en 3 grandesétapes.

– Tout d’abord, nous détectons les brins que nous devons supprimer, c’està dire les brins qui appartiennent aux faces internes de notre ensemblede régions.

– Ensuite, nous mettons à jour l’arbre d’inclusion pour qu’il reflète lasituation une fois les régions fusionnées. Nous nous servons des facesinternes marquées afin de détecter les cas où l’on modifie les relationsentre les régions.

– Enfin, nous supprimons effectivement les brins que nous avons pré-cédemment identifiés puis minimisons la carte par simplification desarêtes puis des sommets.

L’algorithme 1 présente le principe général de la fusion d’un ensemble Ede régions 2-connexes dans la carte topologique.

Le choix de la région principale (mainRegion) est un choix topologique.Nous cherchons, parmi les régions de E, une région R dont le brin re-

présentant est situé sur la surface externe de la région que nous allons créerpar la fusion de E. Cette région sera la région d’accueil du résultat de la

26


Algorithme 1 : Opération de fusionEntrées : Carte Topologique C,Ensemble de régions ERésultat : Fusion des régions de E dans Cdébut

mainRegion← région de E ;Détection des faces internes à E;Mettre à jour l’arbre d’inclusion;Suppression des brins marqués ;

fin

fusion. En d’autres mots, nous allons fusionner toutes les régions de E dansmainRegion.

La complexité de cette recherche de région est linéaire en fonction nombrede régions dans E. Ainsi l’opération consistant à trouver la région principaleest en O(|E|). Nous détaillons maintenant chaque étape de l’algorithme.

2.2.1 Détection des faces internes à E

Pour fusionner les régions, c’est à dire faire en sorte qu’elles ne formentplus qu’un seul et même volume, nous allons supprimer toutes les faces in-ternes de l’ensemble des régions. Nous cherchons donc à détecter tous lesbrins appartenant à ces faces.

Nous réalisons dans la carte, un parcours de tous les brins des régionsà fusionner. Si nous détectons que le brin courant b et β3(b) appartiennenttous les deux à des régions de l’ensemble des régions à fusionner alors c’estqu’ils font partie d’une face interne de notre région résultat. Nous marquonsces brins comme à supprimer.

L’algorithme 2 effectue ce parcours et le marquage de chaque brin appar-tenant à une face interne de notre ensemble de régions E.

L’algorithme commence par marquer les régions à fusionner afin que le testd’appartenance d’une région à l’ensemble E soit réalisé en temps constant(O(1)). Puis l’algorithme détecte les brins des faces internes en parcourantl’ensemble des brins appartenant aux régions à fusionner. La complexité del’opération dépend donc du nombre de brins de la carte puisque dans le piredes cas toutes les régions sont sélectionnées, entraînant le parcours de tousles brins de la carte. L’opération de détection des faces à supprimer à pourcomplexité O(|B|).

27


Algorithme 2 : Détection des faces internesEntrées : Carte Topologique C,Ensemble de régions ERésultat : Marque dans C les faces internes de Edébut

pour chaque région Ri de E fairemarquer Ri comme région à fusionner;

pour chaque brin b de chaque région de E fairesi la région region(β3(b)) est marquée alors

marquer b comme brin à supprimer;marquer β3(b) comme brin à supprimer;

fin

2.2.2 Mise à jour de l’arbre d’inclusion

Lors de la première étape de l’opération de fusion, nous trouvons unerégion dont le brin représentant peut être représentant de la nouvelle régionissue de la fusion. Plutôt que de créer une nouvelle région, nous lui attribuonstous les brins et les régions filles associées aux régions de E. En d’autrestermes, nous fusionnons dans mainRegion, l’ensemble des régions 2-connexesdésignées par E.

La mise à jour de l’arbre d’inclusion passe par deux grandes étapes. Dansun premier temps, la suppression des régions fusionnées de l’arbre d’inclusion(c’est à dire toutes les régions de E sauf mainRegion) et dans un secondtemps la modification de la structure de l’arbre pour refléter les changementséventuels de topologie.

L’opération de suppression met également à jour les brins des régions quidisparaissent pour refléter le fait qu’ils appartiennent désormais à la régionprincipale.

Pour chaque région, l’opération de suppression des régions dans l’arbred’inclusion se décompose en 3 étapes comme nous pouvons le voir dans l’al-gorithme 3. Nous commençons par déconnecter la région dans l’arbre d’in-clusion. Puis nous parcourons l’ensemble des brins de cette région pour lesaffecter à la région principale. Enfin nous ajoutons tous les fils de la régionsupprimée comme fils de la région principale.

La déconnexion de l’arbre est une opération locale. On enlève la région del’arbre tout en évitant de perdre des informations. Ainsi même si la région estreprésentante d’une composante connexe, nous lui trouvons un remplaçant.

28


A

R0R1

2RR3

R7R5 R6

R4

1

2

0

3

4

7

5

6

B

R0R1

2RR3

R7R5 R6

R4

7

5

4

3

1

0

Fig. 2.1 – (A) Image et arbre d’inclusion associé. Il faut encore voir cetteimage comme la coupe d’une image 3D avec un plan de voxel appartenant àla région R1 au dessus et au dessous du plan représenté. (B) Image et arbred’inclusion résultant de la suppression des régions R2 et R6 dans l’arbre.

29


La figure 2.1 montre un exemple de suppression de régions. Nous sou-haitons fusionner R1, R2 et R6. Nous commençons par chercher quelle régionpeut être qualifiée de principale. Nous cherchons une région dont le brin re-présentant serait sur la surface externe de notre région finale. Seul R2 et R1

peuvent correspondre : nous choisissons arbitrairement R1. Nous déconnec-tons R2 et R6. Pour R2 il s’agit de l’enlever de la composante connexe. PourR6, il faut lui trouver un remplaçant pour être représentant de la composanteconnexe. Si R2 ou R6 avaient eu des régions incluses alors nous les aurionsincluses dans R1. Nous pouvons ensuite supprimer R2 et R6 de l’arbre. Nousavons en même temps relabélisé les brins des régions R2 et R6 pour qu’ilsappartiennent à présent à R1.

Algorithme 3 : Suppression des régions fusionnées dans l’arbre d’in-clusionEntrées : Carte Topologique C,Ensemble de régions E,Région principale mainRegionRésultat : Suppression des régions de E dans l’arbre d’inclusiondébut

pour chaque région Ri ∈ E, Ri 6= mainRegion faireDéconnecter Ri de l’arbre d’inclusion;pour chaque brin b de Ri faire

Region(b)← mainRegion;pour chaque fils Rj de Ri /∈ E faire

Déconnecter Rj de l’arbre d’inclusion ;Ajouter Rj comme fils de mainRegion ;

fin

L’opération de suppression de région implique des parcours parmi lesrégions. Il s’agit de déconnecter chaque région amenée à disparaître, puis rat-tacher toutes les filles de ces régions à la région principale. Ainsi la complexitéde l’opération est linéaire en nombre de régions contenues dans l’image ainsiqu’en nombre de brins des régions de E puisque nous relabélisons tous leursbrins (O(|B|)).

Il faut à présent mettre à jour l’arbre d’inclusion pour refléter les change-ments dû à la fusion. Celle-ci peut engendrer des modifications de la topologieet donc des modifications des relations d’inclusion entre les régions.

30


Il y a deux modifications possibles. D’une part, des régions qui étaientdans la même composante connexe que la région principale peuvent êtremaintenant incluses dans la région principale. D’autre part, les régions quiétaient dans une même composante connexe peuvent être dans des compo-santes connexes séparées.

Afin de représenter fidèlement la nouvelle configuration des régions, nousallons recalculer l’arbre d’inclusion lié à la région principale. Cette opérationest présentée par l’algorithme 4.

Au moment où nous cherchons à recalculer l’arbre d’inclusion, nous n’avonspas encore supprimé les faces internes de notre région. Nous savons égalementque c’est leur suppression qui peut entraîner des modifications dans la topo-logie.

Algorithme 4 : Reconstruction de l’arbre d’inclusionEntrées : Carte Topologique C,Région principale mainRegionRésultat : Arbre d’inclusion mis à jourdébut

Chercher les nouvelles faces internes I;pour chaque face interne i ∈ I faire

Construire la composante connexe cc associée;Ajouter cc comme fils de mainRegion;

fin

Pour traiter le cas des régions nouvellement incluses, nous marquons tousles brins appartenant à la surface externe de notre future région. Il s’agitd’un parcours de surface (orbite < β1, β2 >) modifié afin de “sauter” lesbrins marqués comme à supprimer. Ce marquage nous permet par la suite dedétecter en temps constant si un brin appartient ou non à la future surfaceexterne de notre région

Dans un second temps, nous effectuons un parcours classique de la sur-face externe de la région principale, c’est à dire en ne sautant pas les brinsmarqués. Lorsque nous détectons un brin qui n’est ni sur la surface externede la nouvelle région, ni à supprimer, alors c’est qu’il s’agit d’un brin d’unenouvelle face interne de notre région.

Nous marquons toute la surface interne à l’aide du même parcours quepour la surface externe (c’est à dire en “sautant” les brins marqués) afin dene pas retraiter tous ces brins.

31


A l’aide de ces opérations, nous obtenons un ensemble de surfaces in-ternes que nous pouvons analyser pour construire les composantes connexesnouvellement incluses dans notre région principale.

Pour traiter le deuxième cas, celui où des régions préalablement situéesdans une même composante connexe sont à présent dans des composantesconnexes différentes, nous effectuons un parcours de chaque face interne denotre région.

Si nous détectons un brin qui n’est pas à supprimer, c’est que nous avonslà encore trouvé une nouvelle surface interne que nous marquons à l’aide del’opération expliquée plus haut. Si nous ne rencontrons pas de brin à suppri-mer, la composante connexe n’a pas changé et nous pouvons la conserver.

Nous avons à présent un ensemble de faces internes désignées par l’undes brins qui la compose. Pour chaque face interne, nous construisons lacomposante connexe associée à l’aide d’un parcours de l’orbite < β1, β2, β3 >sans jamais passer par des brins à supprimer. Nous passons ainsi par tousles brins contenus par la surface interne. Nous pouvons ainsi ajouter toutesleurs régions d’appartenance à la composante connexe.

Lorsque nous avons construit toutes ces composantes connexes, il ne nousreste plus qu’à les ajouter à l’arbre d’inclusion comme fille de la région prin-cipale.

La figure 2.2 montre comment cette opération fonctionne. Nous fusion-nons dans cette image les régions R1, R2 et R6. Le marquage des faces internesa identifié toutes les faces entre les régions R1 et R2 et toutes les faces entreles régions R1 et R6. L’opération de suppression de l’algorithme 3 a retiré lesrégions R2 et R6 de l’arbre d’inclusion et attribué tous les brins de ces régionsà la région R1. Dans la figure 2.2 B, nous parcourons la carte afin de détecterles nouvelles faces internes de la région principale R1. Nous construisons dansla figure 2.2 C, une composante connexe par face interne détectée. Puis nousparcourons dans la carte les composantes connexes incluses dans les faces in-ternes afin de détecter les régions incluses et ainsi pouvoir compléter l’arbre(figure 2.2 D). Nous avons ainsi détecté une nouvelle face interne contenantR3 et R4. Cette face interne est née de la fusion de deux régions de la mêmecomposante connexe R1 et R2. Nous avons également scindé une composanteconnexe en deux en fusionnant R1 et R6. Nous avons ainsi présenté les deuxcas possible de création de nouvelles faces internes.

La complexité de l’étape de suppression des régions fusionnées dans l’arbred’inclusion est linéaire en fonction du nombre de brins |B|.La seconde étape,

32


A

R0R1

R3

R7R5

R4 R4

3

4

1

0

5

7

B

R0R1

R3

R7R5

R4 R4

3

4

1

0

5

7

C

R0R1

R3

R7R5

R4 R4

1

0

5

7

3

4

D

R0R1

R3

R7R5

R4 R4

1

0

54

3

7

Fig. 2.2 – Exemple de reconstruction des régions. (A) Image et arbre d’in-clusion associé où l’on a supprimé les régions fusionnées. En pointillés sontreprésentées les faces internes qui ne sont pas encore supprimées. (B) Ondétecte les nouvelles faces internes. L’arbre ne change pas. (C) On construitles 3 composantes connexes. On détache les régions pour les rassembler dansles composantes connexes. (D) Image et arbre résultant de la reconstructionde l’arbre.

33


R1

R2

A1 A2

R1

R2

B1 B2

Fig. 2.3 – Suppression d’une face interne entre les régions R1 et R2.(A1) Carte originale. (A2) Plongement correspondant. On remarque en grisfoncé la face interne que nous allons supprimer. (B1) Carte où l’on a sup-primé la face. (B2) Plongement correspondant. Les brins en noir représententles arêtes de degré 2 à simplifier.

pour reconstruire l’arbre d’inclusion, effectue des parcours dans la carte.Chaque brin de la carte n’est parcouru au maximum qu’une fois. Ainsi lacomplexité de cette étape s’exprime en fonction du nombre de brins.

La complexité totale de cet algorithme est linéaire en fonction du nombrede brins de la carte (O(|B|)).

2.2.3 Suppression des faces internes

La suppression des brins est la dernière étape de l’opération de fusion.Il s’agit de supprimer les faces qui ont préalablement été détectées maiségalement de simplifier la carte afin de la rendre minimale.

Par exemple, la figure 2.3 présente la fusion de deux régions R1 et R2.Lorsque l’on supprime la face qui sépare les deux régions, nous obtenonsun volume unique mais dont la surface comporte une arête de degré deux(2.3 B1, arête en gras). Le modèle devant redevenir minimal, il nous fautdonc simplifier la carte.

34


Il s’agit en fait d’appliquer les principes de simplifications utilisés dans laconstruction de la carte topologique.

L’algorithme 5 de suppression des brins se décompose en 4 grandes étapes.Tout d’abord, nous supprimons les faces marquées. Nous simplifions les arêtesqui doivent l’être. Ensuite nous simplifions les sommets non minimaux, puisnous mettons à jour le plongement dans la matrice de l’intervoxel.

Algorithme 5 : Suppression des faces internesEntrées : Carte Topologique CRésultat : C simplifiéedébut

Suppression des faces marquées;Simplifications des arêtes;Simplifications des sommets;Mise à jour du plongement;

fin

2.2.4 Suppression des faces

Afin de supprimer l’ensemble des faces marquées, nous allons tout d’aborddéconnecter chaque face à supprimer de la carte. Pour cela, nous parcouronstous les brins. Lorsque nous arrivons sur un brin marqué qui appartient à uneface qui n’a pas encore été traitée, nous appliquons l’opération de suppressionde face définie dans le modèle et présenté dans la section 1.2.

Algorithme 6 : Suppression des faces marquéesEntrées : Carte Topologique CRésultat : Suppression des faces marquées dans Cdébut

pour chaque brins b de B fairesi b appartient aux brins à supprimer alors

Coudre par β2 les brins β2(b) et β2(β3(b)) ;Supprimer b et β3(b);Supprimer le plongement de la face;

fin

Nous réalisons lors de la suppression du premier brin de la face la mise àjour du plongement. Nous effectuons un parcours de surface dans la matrice

35


de l’intervoxel et nous enlevons tous les surfels rencontrés. La face est limitéepar un chemin de lignels que nous ne franchissons pas lors du parcours.

La suppression de face réalise un parcours des brins de la carte combina-toire. Sa complexité est O(|B|).

2.2.5 Simplification des arêtes

Nous devons à présent simplifier les arêtes. En effet, la suppression deface présentée section 2.2.4 a pu engendrer l’apparition d’arêtes de degré 2.

Plusieurs cas sont possibles. D’une part, l’arête peut-être une boucle.C’est le cas d’une sphère topologique représentée par la “mauvaise” solution(figure 1.12 B). Nous allons donc apporter un traitement particulier afin demodifier cette représentation. D’autre part, la suppression simple de l’arêtepeut entraîner une déconnexion. Pour l’éviter, nous devons désigner cettearête comme fictive. Et enfin dans les autres cas, nous pouvons supprimersans crainte l’arête lorsque elle est de degré deux.

Dans un post-traitement, nous devons modifier la géométrie de façon àêtre cohérent avec la carte. La suppression ou le marquage de l’arête commefictive modifie le plongement de la carte. En effet, lorsqu’une arête est sup-primée ou si l’arête devient fictive alors la géométrie correspondante doitêtre effacée. Nous devons donc faire disparaître la courbe dans la matriceintervoxel qui est associée à l’arête simplifiée. L’algorithme 7 effectue la sim-plification d’arêtes.

Nous discutons à présent de la complexité de cette opération. Le calculdu degré local d’une arête est une opération réalisée en temps linéaire avecle nombre de brins de l’arête tout comme la vérification que l’arête est uneboucle.

Pour vérifier qu’une arête peut être supprimée sans déconnexion il fautvérifier que le brin courant b et β2(b) n’appartiennent pas à la même face,c’est à dire qu’il n’existe pas une suite d’opération β1 permettant depuis bd’arriver à β2(b).

Ce test peut-être vérifié par un parcours de l’orbite < β1 > (b). Si nousutilisons cette méthode, nous aurons alors une complexité quadratique ennombre de brins |D|. Dans ses travaux, Guillaume Damiand a résolu ce pro-blème par l’utilisation d’arbres union-find (voir [4]).

Nous réutilisons dans notre opération de fusion la structure de donnéesprésente et créée lors de l”extraction de la carte afin d’améliorer la complexité.

36


Algorithme 7 : Simplification des arêtesEntrées : Carte Topologique CRésultat : Arêtes simplifiées dans Cdébut

pour chaque brin b de B fairesi l’arête représentée par b est de degré 2 alors

si l’arête est une boucle alorsFormer une arête et une face;Marquer l’arête comme fictive;

sinonsi l’arête peut être retirée sans déconnexion alors

Supprimer l’arête;sinon

Marquer l’arête comme fictive;

si l’arête originale n’était pas fictive alorsSupprimer les lignels correspondants;

fin

Lors de la création, nous associons un arbre union-find à chaque face, etlorsque deux faces fusionnent, nous fusionnons alors les arbres associés auxdeux faces. Avec ces arbres, tester si b et β2(b) appartiennent à la même facecoûte α(|B|) où α() est l’inverse de la fonction d’Ackerman. Dans les caspratiques, cette fonction peut être considérée comme constante (≤ 5). Pourles autres fonctions, la complexité est constante.

Nous pouvons ainsi déterminer que l’opération de simplification des arêtesest linéaire (O(|B|)).

2.2.6 Simplification des sommets

Les opérations successives sur les faces puis sur les arêtes ont pu engendrerla création de sommets de degré 2 qu’il faut simplifier.

Dans un premier temps, nous supprimons les sommets de degré réel zéro.C’est à dire les sommets fictifs qui se trouvent être incident uniquement àdes arêtes fictives. En même temps, nous supprimons les éventuels pointelsqui en sont le plongement.

Ensuite nous parcourons l’ensemble des brins. Si le sommet courant estincident à deux arêtes réelles qui ne sont pas des boucles, nous supprimons lesommet et nous enlevons le pointel correspondant à son plongement. Ensuite

37

2.3. COMPLEXITÉ ET RÉSULTATS

nous supprimons la géométrie des sommets qui n’ont plus de raisons d’enavoir. C’est le cas de tous les sommets dont le degré est inférieur ou égal àdeux, exceptés les sommets incidents à deux arêtes réelles mais dont l’une aumoins est une boucle. L’algorithme 8 présente en détail cette simplification.

Algorithme 8 : Simplification des sommetsEntrées : Carte Topologique CRésultat : Sommets simplifiés dans Cdébut

Suppression des sommets dont le degré réel est 0 ;pour chaque brin b de B faire

si le sommet b est de degré deux et que les arêtes incidentes nesont pas des boucles alors

Supprimer le sommet b;Supprimer le pointel correspondant à b;

si le degré de b ≤ 2 ou si le sommet n’est pas incident à deuxarêtes réelles dont au moins l’une est une boucle alors

Supprimer le pointel correspondant à b;

fin

L’opération de suppression des sommets de degré réel 0 est réalisée parun parcours de la carte. Les tests sur le degré et le type du sommet sontdes opérations réalisées en temps constant. Ainsi nous en déduisons que lacomplexité de l’opération de simplification des sommets est O(|B|).

2.3 Complexité et résultats

2.3.1 Complexité de l’algorithme de fusion

Nous avons étudié la complexité de tous les algorithmes utilisés lors de lafusion de régions dans la carte topologique. Comme le nombre de brins esttoujours supérieur ou égal au nombre de régions, nous pouvons en conclureque l’opération de fusion dans la carte topologique est linéaire en fonction dunombre de brins de la carte. La complexité finale de l’opération est O(|B|).

Nous avons vérifié que la complexité calculée correspond bien aux tempsde calculs que nous pouvons observer dans la pratique. Pour cela nous avonsmis en place un programme qui, dans une image générée aléatoirement, ef-fectue la fusion d’un nombre fixé de régions connexes. Nous pouvons ainsi

38


Fig. 2.4 – Courbe représentant le temps d’exécution en fonction du nombrede brins total dans la carte

voir dans la figure 2.4 que la complexité est en pratique linéaire en nombrede brins dans la carte.

2.3.2 Résultats

Nous présentons maintenant quelques résultats obtenus par le logiciel lorsde fusions guidées par l’utilisateur. Nous avons représenté dans chaque cas, lasituation originale et la situation finale après la fusion dans la représentationen intervoxel.

La figure 2.5 présente la fusion d’une région située au milieu d’une com-posante connexe avec sa région englobante. Dans l’image 2.5 B, nous voyonsquelle région va fusionner. On remarque qu’après la fusion dans l’image 2.5 C,il n’y a plus de plongement pour les faces de cette région ni de plongementsur les arêtes et sommets qui y étaient incident. Cela traduit la suppressiondes faces mais également la minimisation. La dernière image (2.5 C) est doncle résultat de la fusion présentée ici.

Nous allons maintenant fusionner les deux régions d’une même composanteconnexe. Ainsi le résultat que l’on souhaite obtenir est une sphère topolo-gique. Nous avons, figure 2.6 A, sélectionné les deux régions que nous allonsfusionner. Nous observons dans la figure 2.6 B que le plongement de la faceinterne a disparu et que le plongement de l’arête incidente qui est maintenant

39


A

B

C

Fig. 2.5 – Fusion d’une région avec sa région englobante

40


A B

Fig. 2.6 – Fusion de deux régions d’une composante connexe

A B

Fig. 2.7 – Fusion d’une région et de son unique fille

de degré 2 a également disparu. Nous sommes devant la représentation d’unesphère topologique. La carte a été modifiée en conséquence.

La figure 2.7 montre la fusion d’une région seule dans sa composanteconnexe avec sa région englobante. Nous voyons que la surface interne dela grande région disparaît (figure 2.7 B).

Nous sommes dans la figure 2.8 dans le même cas que pour la figure 2.6cependant, le plongement de la face a supprimer est beaucoup plus important.Nous observons la encore que la surface interne disparaît tout comme l’arêteincidente qui est minimisée.

41


A B

Fig. 2.8 – Fusion de deux régions dans une composante connexe

42

Chapitre 3

Segmentation

Nous allons maintenant rentrer dans la description du processus de seg-mentation proprement dit. Nous allons d’abord voir les principes utiliséspour réaliser la segmentation mise en oeuvre durant ce stage. Nous parleronségalement de notre critère d’homogénéité que nous détaillerons. Et nous pré-senterons l’algorithme de segmentation qui a été utilisé. Nous détailleronsensuite une étape importante qui est la présegmentation, étape permettantde créer une carte topologique pour une image quelconque. Enfin nous pré-senterons des résultats de segmentation produit par la chaîne de traitementqui a été mise en oeuvre.

3.1 PrincipesNous avons étudié dans le cadre de ce travail la segmentation par approche

bottom-up. Cette méthode, part d’une image sur-segmentée, puis fusionne lesrégions proches dans l’image afin d’obtenir des régions de plus en plus grosses.Le mécanisme s’arrête lorsque le résultat obtenu est satisfaisant, par exemplesi le nombre de régions est suffisamment petit ou s’il n’existe plus de couplede régions homogènes.

La notion de proximité de régions dans l’image est définie par l’utilisationd’un critère. Il s’agit d’une fonction nous indiquant si nous devons fusionnerdeux régions entre elles. Il existe de nombreux critères qui se basent princi-palement sur la couleur des régions (en l’occurrence ici le niveau de gris) afinde déterminer si deux régions doivent être fusionnées.

3.1.1 Critère de segmentation : Erreur Quadratique

Dans le cadre du stage, nous avons trouvé une référence à un critère desegmentation relativement simple et qui s’adapte bien à notre problématique.

43

3.2. ALGORITHME DE SEGMENTATION

Il s’agit du critère dit de l’erreur quadratique. Ce critère a pour objectif demesurer l’homogénéité d’une région. Plus l’erreur quadratique d’une régionest petite, plus la région est qualifiée d’homogène.

Nous supposons qu’à l’initialisation, toutes les régions sont homogènes.Sous cette condition, nous posons que la segmentation résultante n’est com-posée que de régions homogènes. Nous avons ainsi une contrainte nous per-mettant de savoir quand fusionner ou ne pas fusionner.

Nous pouvons maintenant décrire plus en détail le critère et la méthodepar laquelle il est calculé. Deux régions adjacentes doivent être fusionnéessi leur union est homogène en fonction du critère. L’erreur quadratique EQd’une région R correspond à la comparaison du carré des niveaux de gris quicompose l’image, avec le carré de la moyenne des niveaux de gris. Ce critèrepeut être exprimé à l’aide les moments d’ordre zéro (M0), un (M1) et deux(M2) d’une région :

EQ(R) = M2(R)−M0(R)v(R)2

Avec M0(R) le nombre de voxels de la région R, M1(R) la somme desniveaux de gris de la région R, M2(R) la somme des carrés des niveaux degris de la région R et v(R) = M1(R)

M0(R).

A l’aide de cette formule nous pouvons voir que l’erreur quadratique d’unerégion résultante de la fusion de deux régions peut-être calculé efficacementpuisque les moments d’une région peuvent être calculé incrémentalement.

∀i ∈ {0, 1, 2}, Mi(R1 ∪R2) = Mi(R1) + Mi(R2).

Afin de savoir si deux régions A et B doivent être fusionnées, nous cal-culons l’erreur quadratique de leur union A

⋃B. Si l’erreur quadratique est

inférieur à un seuil T fixé par l’utilisateur ou par un algorithme, la régionrésultante est qualifiée d’homogène et donc les deux régions sont fusionnées.Sinon, la région résultante n’est pas homogène et donc la fusion n’est paseffectuée pour ne pas rompre le principe d’homogénéité des régions.

3.2 Algorithme de segmentationPour pouvoir mettre en oeuvre cette approche, nous cherchons un al-

gorithme simple permettant de créer les ensembles de régions connexes del’image qui doivent être fusionnés. Nous avons choisis d’utiliser un parcoursde la carte en cherchant pour chaque voisin s’il doit être fusionné ou non.

44

3.2. ALGORITHME DE SEGMENTATION

L’algorithme construit à partir d’une région R, l’ensemble E des régionsde son voisinage qui doivent fusionner selon notre critère. Nous commençonsavec E = {R}. Nous définissions les différents moments M0(R), M1(R) etM2(R) de E comme étant les moments de R.

Puis pour tous les voisins 2-connexes Ri des régions de E, nous calculonsl’erreur quadratique de l’union de E et Ri (EQ(E

⋃Ri)). Afin de découvrir

tous les voisins deux connexes d’une région, nous parcourons la surface ex-terne. A chaque face de la surface externe correspond une région. Pour nepas traiter plusieurs fois une même région, nous nous servons d’une marque.Cependant le parcours de la surface externe de chaque région de E ne suffitpas à découvrir toutes les régions du voisinage. Pour traiter le cas des régionsincluses nous allons en plus parcourir les surfaces internes en utilisant l’arbred’inclusion et les régions représentantes de chaque composante connexe.

Si la nouvelle erreur quadratique est inférieure au seuil que nous avonspréalablement fixé, alors nous insérons la région Ri dans l’ensemble E. Nousincrémentons les moments de E avec les moments de Ri. Et nous continuonsnotre parcours des voisins 2-connexes de E en tenant maintenant compte desvoisins de Ri également.

Algorithme 9 : Segmentation bottom-up à l’aide de l’erreur quadra-tiqueEntrées : Carte Topologique C,Seuil de segmentation SRésultat : Segmentation de Cdébut

Initialisation des moments pour chaque région;pour chaque région r non-marquée faire

E ← {r};Marquer r;pour chaque région v voisine de E et non-marquée faire

si EQ(E, v) < S alorsAjouter v à E;Marquer v;

Fusionner E;fin

Lorsque nous avons testé tout le voisinage de E et qu’il n’existe plus derégions validant le critère alors l’ensemble E est dans un état stable. Nouspouvons alors à ce moment là utiliser l’algorithme de fusion sur l’ensembledes régions contenue dans E.

45

3.3. PRÉSEGMENTATION

Nous prenons à présent une autre région afin d’initialiser la recherched’un nouvel ensemble E. Nous itérons ainsi le processus sur l’ensemble desrégions de l’image.

Le parcours des régions non-marquées est un parcours de toutes les ré-gions guidé par l’arbre d’inclusion. Nous commençons par parcourir toutesles régions de la composante connexe puis nous passons aux régions qui sontincluses. Cette méthode de parcours fait que la progression va du bord versle centre. Cependant, la segmentation obtenue est dépendante de l’ordre deparcours.

Il serait envisageable de remédier à ce problème en cherchant indivi-duellement quelles régions deux à deux seraient fusionnable. Autrement dit,chercher quelles sont les faces qui doivent disparaître. Le problème étantque ce type de recherche conduit à des régions non-homogènes. En effet,même si EQ(A, B) < P et EQ(B, C) < P , nous n’avons pas forcémentEQ(A

⋃B, C) < P ou EQ(A, B

⋃C) < P . Nous ne respectons pas la défi-

nition du critère devant nous mener à des régions homogènes.

3.3 PrésegmentationLe traitement d’image 3D pose rapidement le problème de la complexité

en mémoire. Lorsque l’image est très segmentée, le modèle initial prend tropd’espace et ce qui peut empêcher sa construction. Pour diminuer l’espacemémoire, il faut diminuer le nombre de régions de la première segmentation.Nous allons donc mettre en oeuvre une étape de présegmentation qui nouspermet de disposer initialement d’un nombre de régions plus faible.

Dans un premier temps, nous présentons les modifications apportées àl’algorithme d’extraction pour tenir compte d’images quelconques c’est à direnon-labélisées. Puis nous parlerons des modifications nécessaire à la préseg-mentation et nous finirons par présenter quelques exemples de présegmenta-tion.

3.3.1 Modification d’algorithme d’extraction

L’algorithme d’extraction tel qu’il est présenté section 1.5 travaille surdes images labélisées. Il se sert de la propriété des images labélisées afin deconstruire convenablement les régions de l’image. Ainsi l’algorithme d’ex-traction balaye l’image et sait en temps constant à quelle région un voxelappartient.

46


1 11

1 12

V4

V1 V2 V3

V5 V6

1 11

1 12

V4

V1 V2 V3

V5 V6

1 11

1 12

V4

V1 V2 V3

V5 V6

1 1

1 12

?

V4

V1 V2 V3

V5 V6

A B C D

Fig. 3.1 – Algorithme d’extraction modifié. (A) Image originale en niveau degris. (B) Début du balayage de l’image, la première région est créée autourdu premier voxel. (C) Seconde étape du balayage, une deuxième région estcréée autour du second voxel. (D) Nous avons continué le balayage en créantune troisième région autour du 3ème voxel. Les deux premier voxel de ladeuxième ligne sont dans la première région. Mais pour le dernier voxel, nousne pouvons pas savoir. En effet, à ce moment, il faudrait fusionner la premièreet la troisième région.

L’exemple classique de ce que sait faire l’algorithme est celui du “n” pré-senté figure 3.1 A.

L’algorithme d’extraction effectue un balayage de limage de gauche àdroite et de bas en haut. Ainsi lorsque nous arrivons sur le voxel V1, nouscréons une nouvelle région (étiquette 1). Nous passons ensuite au voxel V2et nous créons une nouvelle région (étiquette 2). Lorsque nous arrivons surle voxel V3, nous nous servons de la propriété de l’image labélisée afin dene pas créer un nouvelle région mais d’ajouter ce voxel à la région étiquetée1. Nous continuons ainsi avec les voxels V4 et V5. Pour chacun d’eux nousutilisons la région de même couleur dans le voisinage afin de les ajouter à larégion étiquetée 1. Puis nous arrivons au voxel V6. Dans son voisinage il n’ya qu’une seule région qui lui corresponde donc nous ajoutons ce voxel à larégion 1.

Maintenant si l’image n’est pas labélisée, nous avons un problème commenous le montre la figure 3.1. Les voxels V1, V4 et V5 sont dans la mêmerégion étiquetée 1. Le voxel V2 est dans une région étiquetée 2. Enfin levoxel V3 est dans une deuxième région étiquetée 1. En effet, il n’y a pas dansle voisinage du voxel courant de région portant la même étiquette. Lorsqueque nous cherchons dans le voisinage du voxel V6 une région correspondanteà notre couleur, il y a deux choix valides, qui sont les deux régions étiquetées1 soit celle du voxel V1 et celle du voxel V3. Ce qui veut dire que tous lesvoxels des régions étiquetées 1 appartiennent à une seule et même région.Nous devons donc relabéliser l’ensemble des voxels d’une des deux régions

47


afin de les fusionner.Une approche directe de cette méthode conduit à réaffecter à chaque nou-

velle fusion beaucoup de brins dans la carte et produit un algorithme quadra-tique en nombre de voxels. Afin d’éviter de reparcourir à chaque réaffectationtoute la carte associée aux régions devant disparaître, nous mettons en placeun arbre union-find sur les régions nous permettant de fusionner deux régionsen temps quasi-linéaire.

L’algorithme dans sa version originale construit la carte et en même tempsconstruit la liste des régions qu’il a crée. Une fois la carte construite, il par-cours la carte afin de construire l’arbre d’inclusion.

Notre modification construit la carte selon le même principe que l’algo-rithme original sauf que nous incrémentons le label affecté à chaque région aufur et à mesure que nous découvrons de nouvelles régions. Ainsi la premièrerégion crée a pour étiquette 1, la seconde 2, . . . . Lors du balayage, si nousrencontrons un voxel pour lequel il y a plusieurs régions qui conviennent,nous fusionnons alors dans l’arbre union-find ces régions en gardant la ré-gion de plus faible étiquette (la région rencontrée la plus tôt) comme pèredes autres. Ainsi nous construisons toujours la liste des régions découverteslors du balayage mais nous relions également à l’aide de l’arbre les régionsqui ont été fusionnées lors du parcours.

A la fin du balayage de l’image, nous avons donc maintenant des régionsqui ont été fusionnées. Mais ces régions ont toujours des brins dans la carte.Aussi nous parcourons toute la carte et nous changeons la région d’apparte-nance de chaque brin des régions fusionnées en leur affectant la région pèredans l’arbre union-find. Nous parcourons ensuite la liste de toutes les régionsen supprimant toutes celles qui ne sont pas racine d’un arbre union-find, c’està dire toute les régions qui ont été fusionnées parce qu’elles n’interviennentplus dans le modèle.

Nous avons à présent une carte et une liste de régions identique (à l’éti-quette près) à ce qui aurait été obtenu par l’utilisation de l’algorithme origi-nal. Nous appliquons donc la construction de l’arbre d’inclusion sur la listedes régions fournie.

Avec l’ajout de ces traitements dans l’algorithme d’extraction, nous pou-vons maintenant travailler avec des images qui ne sont pas labélisées.

3.3.2 Ajout de la présegmentation

L’algorithme d’extraction, dans sa version originale, utilise l’égalité entrelabels afin de savoir si deux voxels sont dans une même région (i.e. si deuxvoxels ont un même label, ils sont dans une même région). La modification

48


1 2 1

2

1

2

33

9

V1 V2 V3

V4 V5 V6

V7 V8 V9

V1 V2 V3

V4 V5 V6

V7 V8 V9

1 2 1

2

1

2

33

9

V1 V2 V3

V4 V5 V6

V7 V8 V9

1 2 1

2

1

2

33

9

V1 V2 V3

V4 V5 V6

V7 V8 V9

1 2 1

2

1

2

33

9

A B C D

Fig. 3.2 – Algorithme de présegmentation avec un seuil fixé à 1. (A) Imageoriginale en niveau de gris. (B) Nous effectuons le balayage de gauche àdroite et de bas en haut. (C) Il ne reste qu’un voxel pouvant appartenir àdeux régions différentes. Nous fusionnons donc ces régions. (D) Il reste uneface interne, représentée ici en pointillé. Cette face ne devrait pas exister etpourtant elle reste car il n’était pas prévu que les deux premiers voxels soientdans la même région puisque leur écart est trop important.

présentée section 3.3.1 change cette règle par : si deux voxels ont la mêmecouleur et sont dans une même composante 2-connexe alors ils appartiennentà une même région.

Pour présegmenter, c’est à dire effectuer une première segmentation surl’image, visant à regrouper dans de même région les voxels ayant des couleurstrès proches, nous avons modifié cette règle. A présent, deux voxels sont dansune même région si il existe un chemin 2-connexe les reliant tel qu’entre deuxvoxels consécutifs la différence de niveau de gris soit inférieur ou égal à unseuil.

En fonction du seuil, nous pouvons mettre plusieurs modes d’importationsd’une image en place. Si le seuil est négatif, l’écart ne sera jamais inférieurau seuil. Chaque voxel sera donc sa propre région. A l’inverse, si le seuil esttrès grand alors tous les voxels seront dans la même région. Enfin si le seuilest égal à zéro, nous nous retrouvons dans le cas de l’algorithme d’extractiond’une image déjà segmentée.

En tenant compte de cette modification, l’algorithme d’extraction modifiépour prendre en compte des images quelconques ne fonctionne pas dans tousles cas.

Il peut en effet, y avoir apparition de faces internes dans notre modèle. Lafigure 3.2, nous montre un cas dans lequel le problème se pose. Nous avonsdéterminé le seuil de présegmentation à un. Si deux voxels voisins n’ont qu’unniveau de gris de différence, alors ils sont dans la même région. Nous pouvonsainsi parcourir toute l’image. Lors du parcours le voxel (i) en bas à gauche et

49

3.4. RÉSULTATS

le voxel (j) qui est à sa droite sont dans deux régions différentes. Cependant,comme il existe un chemin entre i et j qui passe uniquement par des voxelsdont l’écart des niveaux de gris deux à deux est égal au seuil ces voxels sontdans la même région. Ainsi après le parcours de toute l’image, nous nousapercevons que i et j sont dans la même région. Le problème est que nousavons déjà construit la face qui sépare i et j représentée dans la figure 3.2 Den pointillé. Cette face que nous qualifions d’interne ne correspond pas auprincipe de minimalité de la carte.

Nous sommes ici dans le même cas que lors de la fusion de régions. Nousavons des faces internes qu’il faut supprimer ce qui sera fait après le balayagecomplet de l’image.

Nous terminons donc le balayage de toute la carte. Puis, dans un parcourssupplémentaire de la carte, nous détectons toutes les faces internes. Nouspouvons les identifier car les brins qui les composent sont tels que pour chaquebrin b d’une face interne, β3(b) appartient à la même région. Il n’y a pasd’autres brins validant cette formule. Nous marquons donc toutes les facesinternes. Aucune modification de l’arbre d’inclusion n’est nécessaire puisqueà ce moment, l’arbre n’est pas encore construit. Il ne nous reste qu’à utiliserl’algorithme 5 de suppression des faces internes qui va se charger de supprimertoutes les faces précédemment détectées de la carte et de minimiser s’il y abesoin.

Nous disposons à présent d’une fonction d’extraction de la carte topolo-gique d’une image quelconque que nous pouvons présegmenter afin de dimi-nuer le nombre de régions dans la première segmentation et diminuer par lamême occasion la taille de la carte topologique en mémoire.

3.4 RésultatsNous présentons maintenant des résultats de segmentations obtenues à

l’aide le l’algorithme 9.La figure 3.3 A montre la carte extraite à l’aide de l’algorithme d’extrac-

tion en présegmentant une coupe d’un cerveau. La présegmentation à poureffet de rassembler tous voxels ayant une petite différence de couleur dansune seule et même région. Nous observons dans cette image les brins de lacarte. Nous voyons que la région centrale est très étendue alors qu’au niveaudu crane, l’image est très segmentée. Nous appliquons donc notre algorithmeavec un critère arbitraire obtenu par tâtonnement. Nous observons figure3.3 B le résultat de cette segmentation. Nous distinguons clairement que lenombre de régions de la carte a diminué et que le bord du crane, même s’ilest encore sur-segmenté, comporte beaucoup moins de régions.

50

3.4. RÉSULTATS

A B

Fig. 3.3 – Segmentation d’une coupe d’un cerveau 128x128. (A) Avant lasegmentation. (B) Après la segmentation. Le nombre de région a visiblementdiminué.

La figure 3.4 A présente la même coupe de cerveau en couleurs réelles.Dans la figure 3.4 B, chaque région de l’image s’est vu attribuer une cou-leur différente. Nous appelons cette représentation, la vue en fausse couleur.L’image de la figure 3.4 C présente le résultat en fausse couleur de la préseg-mentation. La figure 3.4 D, E présente le résultat de la présegmentation envraie et fausse couleur.

Nous avons lancé notre algorithme sur une image 3D simple afin d’observerle résultat de la segmentation sur celle-ci. Les figures 3.5 A, B, C présententles 3 représentations de l’image 3D. En premier l’intervoxel, en second lacarte topologique et en dernier l’image 3D en vraie couleur.

Les figures 3.5 D, E, F montrent les différentes représentation de la mêmeimage après avoir segmenté cette image. le critère est choisi là encore arbi-trairement afin de ne plus obtenir que deux régions distinctes.

51

3.4. RÉSULTATS

A B C

D E

Fig. 3.4 – Résultat de la segmentation sur la coupe d’un cerveau 128x128.(A) Image originale. (B) Image originale en fausse couleur (chaque régionpossède une couleur différente). (C) Image en fausse couleur issue de la pré-segmentation. (D) Image résultat. (E) Image résultat en fausse couleur.

A B C

D E F

Fig. 3.5 – Segmentation dans une image 3D “test”. (A,B,C) Intervoxel, carteet image originale. (D,E,F) Intervoxel, carte et image résultat de la fusion.

52

Conclusion et perspectives

Dans ce mémoire, nous avons présenté un algorithme de fusion de régionsdans la carte topologique. L’opération prend en paramètre un nombre quel-conque de régions formant une composante 2-connexe et les fusionne. Cetalgorithme conserve les propriétés du modèle et notamment sa minimalité. Ila une complexité linéaire en fonction du nombre de brins de la carte ce quia été vérifié en pratique dans nos expérimentations.

Nous avons également vu un algorithme d’extraction et de présegmenta-tion d’une image quelconque permettant d’obtenir une première segmenta-tion de l’image. Cela nous permet d’appliquer d’autres opérations par la suiteen étant moins gêné par la taille en mémoire de la carte. Il s’agit d’une mo-dification de l’algorithme de base permettant d’extraire la carte d’une imagelabélisée. Cet algorithme généralise l’extraction initiale qui est maintenantobtenue par l’utilisation d’un seuil égal à zéro.

Enfin nous avons mis en oeuvre l’opération de fusion dans un algorithmede segmentation par approche bottom-up. Cette opération utilise comme cri-tère l’erreur quadratique afin de juger de l’homogénéité des régions. Nousavons appliqué l’algorithme de segmentation à diverses images et notam-ment des images issues du monde médical. La complexité de l’algorithme desegmentation dépends du nombre de régions de la carte et, à cause de lafusion, du nombre de brins.

Nous souhaitons à présent étudier de nouveaux critères de segmentation.L’approche proposée dans ce document n’est basée que sur la couleur etne se sert pas vraiment des informations topologiques portées par la carte.Nous pensons que de nouveaux critères topologiques qui, mélangés à d’autrecritères, permettraient sans doute de proposer des résultats plus pertinent.Nous avons également commencé à étudier un critère différent qui se base surla notion de contraste. Notre algorithme de segmentation étant générique, il

53

est possible de changer de critère de segmentation très facilement.Durant nos expérimentations, nous avons observé que l’ordre de parcours

joue un rôle dans la segmentation produite. Nous sommes intéressés parl’étude de méthodes de segmentation différentes permettant de s’affranchirdu rôle joué par cet ordre de parcours.

Nous serions aussi intéressé par l’ajout d’approches différentes comme lasegmentation région top-down ou les approches mixte. L’étude d’algorithmede lignes de partage des eaux en trois dimensions dans la carte topologiqueest également une piste sur laquelle nous souhaitons travailler.

Enfin, la représentation de la hiérarchie de partition, qui sert de base àde nombreux algorithmes de segmentation serait un ajout intéressant dansla carte topologique de part les informations supplémentaires qu’elle apportetel que par exemple l’historique des partitions.

54

Bibliographie

[1] G. Damiand and P. Lienhardt. Removal and contraction for n-dimensional generalized maps. In Discrete Geometry for Computer Ima-gery, number 2886 in Lecture Notes in Computer Science, pages 408–419,Naples, Italy, november 2003.

[2] G. Damiand and P. Resch. Topological map based algorithms for 3d imagesegmentation. In Discrete Geometry for Computer Imagery, number 2301in Lecture Notes in Computer Science, pages 220–231, Bordeaux, France,april 2002.

[3] R. Marfil, L. Molina-Tanco, A Bandera, Rodriguez J.A., and Sandoval F.Pyramid segmentation algorithms revisited. Pattern Recognition, 39(8),2006.

[4] R. Tarjan. Efficiency of a good but not linear set union algorithm. Journalof the ACM, 22(2) :215–225, 1975.

55

Documents

Segmentation d’images 3D à l’aide de la carte …xlim-sic.labo.univ-poitiers.fr/publications/files/publi2184.pdf · thode de segmentation région, trois grandes familles qui