Surfaces discrètes définition extraction et géométrie

Jacques-Olivier Lachaud

Description

Niveau: Secondaire, Collège, Troisième

• mémoire


• exposé

Surfaces discrètes : définition, extraction et géométrie Jacques-Olivier Lachaud Ecole Jeunes Chercheurs, LIRMM, Montpellier, 4-8 avril 2005 Abstract Dans ce cours introductif, nous présenterons les problématiques liées aux sur- faces discrètes, c'est-à-dire des ensembles fins et séparants dans un espace discret. Nous nous limiterons ici aux espaces discrets sous-ensemble de la grille régulière de dimension quelconque. Dans un premier temps, nous présentons les spécificités du discret puis nous introduisons les grandes approches aux surfaces discrètes. Dans un deuxième temps, nous montrons le lien fort entre isosurfaces et surfaces discrètes puis nous montrons différents algorithmes pour extraire les surfaces dis- crètes par suivi sur la surface. Dans un troisième temps, nous présentons quelques estimateurs géométriques discrets qui utilisent la notion de voisinage sur la surface pour approcher normales, aire, plan tangent, etc. Nous terminons en proposant une mise en œuvre efficace de ces algorithmes par codage des cellules discrètes et utilisation de la topologie algébrique. 1

• espace discret


• pseudo-variétés


• problématiques


• topologie


• décomposition cellulaire de rn en grille cellulaire


• transformation de calculs de volume en calculs de surface


• surface discrète

Sujets

• Mathématiques
• Troisième
• Mémoire
• Exposé
• Lachaud
• Espace discret
• Topologie

Informations

• Publié par: profil-vyan-2012
• Date de parution: 01 avril 2005
• Nombre de lectures: 85
• Langue: Français
• Poids de l'ouvrage: 2 Mo

Extrait

Surfaces discrètes : dénition, extraction et géométrie

Jacques-Olivier Lachaud [e-mail] Ecole Jeunes Chercheurs, LIRMM, Montpellier, 4-8 avril 2005

Abstract Dans ce cours introductif, nous présenterons les problématiques liées aux sur- faces discrètes, c’est-à-dire des ensembles ns et séparants dans un espace discret. Nous nous limiterons ici aux espaces discrets sous-ensemble de la grille régulière de dimension quelconque. Dans un premier temps, nous présentons les spécicités du discret puis nous introduisons les grandes approches aux surfaces discrètes. Dans un deuxième temps, nous montrons le lien fort entre isosurfaces et surfaces discrètes puis nous montrons différents algorithmes pour extraire les surfaces dis- crètes par suivi sur la surface. Dans un troisième temps, nous présentons quelques estimateurs géométriques discrets qui utilisent la notion de voisinage sur la surface pour approcher normales, aire, plan tangent, etc. Nous terminons en proposant une mise en œuvre efcace de ces algorithmes par codage des cellules discrètes et utilisation de la topologie algébrique.

1

Plan de l’exposé

Contents 1 Topologie discrète et surfaces discrètes 1 1.1 Contexte, Topologie, Surfaces . . . . . . . . . . . . . . . . . . . . . 1 1.2 Problématiques induites par le discret . . . . . . . . . . . . . . . . . 3 1.3 Dénitions usuelles . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.4 Principales approches aux surfaces discrètes . . . . . . . . . . . . . . 5 2 Extraction des surfaces discrètes 8 2.1 Imagerie volumique, Isosurfaces . . . . . . . . . . . . . . . . . . . . 8 2.2 Dualité Isosurfaces et Surfaces discrètes . . . . . . . . . . . . . . . . 11 2.3 Calcul du graphe de surface . . . . . . . . . . . . . . . . . . . . . . . 14 3 Mesures géométriques 17 3.1 Cadre de travail . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 3.2 Estimation de la normale . . . . . . . . . . . . . . . . . . . . . . . . 18 3.3 Estimation de l’aire ; aire élémentaire . . . . . . . . . . . . . . . . . 20 3.4 Autres mesures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 4 Mise en oeuvre des surfaces discrètes 22 4.1 Problématiques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 4.2 Cellules et coordonnées dans l’espace de Khalimsky . . . . . . . . . 23 4.3 Topologie algébrique . . . . . . . . . . . . . . . . . . . . . . . . . . 23 4.4 Implémentation efcace en dimension arbitraire . . . . . . . . . . . . 26

1 Topologie discrète et surfaces discrètes 1.1 Contexte, Topologie, Surfaces Contexte •Contexte : analyse d’images (2D,3D, voire plus) •Enjeux : Identier, Représenter, Mesurer, Caractériser, Comparer, Indexer, Sim- plier, Localiser, Visualiser lesobjetsoucomposantsde l’image ⇒nécessitesouventd’avoir des informations/modèles topologiques et géométriques •Les éléments et parties d’une image sontdiscrets(i.e. non continus) –Espace discret:Z n •La topologie précède la géométrie 1. topologie discrète pour l’espace

2. objets et bord d’objets / surface 3. mesures Topologie Topologie: étude des lieux sans tenir compte des déformations continues •Caractérise localement ou globalement les objets •les bords de volume et les surfaces jouent un rôle très important⇒surfaces dis- crètes •Quelques exemples 1. Visualisation : en 3D, on voit la surface de l’objet, pas le volume. Permet leback-face culling 2. Géométrie : normales, courbures, aire sont des mesures de surface 3. Complexité mémoire : diminuée d’un ordre de grandeur (les bords d’objets réguliers dans des imagesN n ont une complexité enO(N n−1 ). 4. Temps de calcul : transformation de calculs de volume en calculs de surface (volume, moments, intégrales, intersections de formes) Surface, séparation •Dénition standard (surface plongée) m-variété (m-manifold) Unem-variété est un espace topologique localement euclidien de dimensionm (homéomorphisme local). Unesurfaceest unen−1-variété plongée dans l’espace euclidien de dimension n(R n ). ⇒Peu utilisable d’un point de vue informatique. •Autre caractéristique : séparation de l’espace en deux parties. Intuitivement, le bord d’un objet sépare l’objet du reste de l’espace. Theorem 1 (Jordan (2D)).SiJest une courbe simple dansR 2 alorsR 2 Ja deux composantes connexes de frontière communeJ(l’intérieur et l’extérieur)

Les surfaces seront donc des parties de l’espace nes et séparantes.

2

Figure 1: Pseudo-variété obtenu par pincement d’un octaèdre

Surfaces combinatoires •Dénition combinatoire des variétés –Possible pourn≤3 –Pas dans le cas général –Restriction à des conditions nécessaires •Pseudo-variétés combinatoires –n-simplexe : ensemble den+1éléments appelés sommets (point, segment, triangle, tétraèdre, . . . ) –Complexe simplicial: ensemble de simplexes avec des relations d’incidence signées –Forte connexité: les simplexes maximaux sont connectés par face Denition 2 (Pseudo-variété fermé).Unm-complexe simplicial forte- ment connexe est unem-pseudo-variété ferméssi toutm−1-simplexe est face d’exactement deuxm-simplexes. –Les pseudo-variétés sont séparantes Theorem 3 (Jordan–Brouwer).Touten−1-pseudo-variété fermée dans R n est orientable, sépare l’espace en deux domaines dont elle est le bord commun. –Toute triangulation d’une variété est une pseudo-variété

1.2 Problématiques induites par le discret Problématiques liées au discret Pourquoi ne peut-on utiliser surZ n les resultats classiques de topologie ?

3

•on ne disposea priorini d’une topologie, ni d’une décomposition simpliciale ou cellulaire. •Topologies surZ n –des topologies de Hausdorff (comme l’espace euclidien)pas –topologies d’Aleksandroff : l’intersection d’un nombrequelconqued’ouverts est un ouvert –pas d’homéomorphisme local avec un espace euclidien •Décomposition cellulaire deR n engrille cellulaire –chaque cube de dimensionnest un pixel/voxel de l’image –supportpartielpour dénir des surfaces discrètes –bord d’ensemble den-cubes ne sont pasen généraldes variétés (ni même des pseudo-variétés)

⇒nouvelles dénitions des surfaces discrètes 1.3 Dénitions usuelles Dénitions usuelles de topologie discrète Denition 4 (Espace discret, objet, adjacence).Espace discret :Z×. . .×Z(nfois) •spel: élément deZ n (pixel en 2D, voxel en 3D) •objet: partie deZ n •ω n adjacence de spels: 2 spels sontω n -adjacents si leurdistance blocest égale à 1. Dénitions usuelles de topologie discrète II Denition 5 (Graphe d’adjacence, espace interpixel).•autres adjacence(s) de spels: relationsρ⊃ω n . •Graphe deρ-adjacence: graphe(Z n , ρ)

4

Figure 2: 3D : adjacences par face (6-)=ω 3 , arête (18-), sommet (26-) du voxel

•Bord intérieurd’un objetO:{u∈O, u ρ-adjacent àO} •Bord extérieurd’un objetO:{v∈ ρO, v-adjacent àO} •espace “interpixel”C n : grille cellulaire de dimensionn spel = cube unité. Un de dimensionn •surfel: unen−1-face commune à deuxn-cubes •surfel: (équivalent) un arc du graphe d’adjacenceω n 1.4 Principales approches aux surfaces discrètes Principales approches aux surfaces discrètes •On peut dénir unesurface discrètecomme 1. sous-ensemble deZ n (i.e. des spels) 2. arcs du graphe d’adjacence (i.e. des surfels) 3. complexe cellulaire (desi-cellules,i < n) •Toutes ces dénitions cherchent à garantir unthéorème de Jordandiscret. Surfaces = sous-ensemble deZ 3 •[Morgenthaler,Rosenfeld 81] [Malgouyres97] Denition 6 (Surface).S⊂Z 3 est unesurfacessiSsépareZ 3 en deux com- posantes 6-connexes (séparation) et tout voxel deSest 6-adjacent à chaque com- posante deZ 3 S(ensemble n). • et surfaces représentables de la même façon, structures de objetsAvantages : données simples, algos de suivi possibles •Problèmes : 1. (Pratique) les bords d’objets discrets ne sont pas en général des surfaces. 2. (Théorique) Pas de caractérisation locales des surfaces deZ 3 [Malgouyres96]

5

Figure 3: dénition locale d’une surfaceSdeZ 3 :∀u∈S, les 26-voisins deudansS forment une quasi-courbe 18-connexe

Figure 4: Surface de surfels, intérieur et extérieur immédiat

Surface = arcs du graphe d’adjacence •[Liu, Artzy, Frieder, Herman, Webster, Gordon, Udupa, Kong] •un surfel est un arc orienté du graphe d’adjacenceω n (i.e. un couple de spels), une surfaceSest un ensemble de surfels •intérieur immédiatII(S)={u|(u, v)∈S}. •extérieur immédiatIE(S)={v|(u, v)∈S}. •Surfaces de Jordan et paires de Jordan Denition 7 (Surface de Jordan[Herman92]).S⊂ω n ⊂Z n ×Z n est une surface de Jordanssi toutω n -chemin deII(S)versIE(S)traversS. Denition 8 (Paire de Jordan forte).SoitIune image binaire surZ n . Une paire d’adjacence{κ, λ}est une paire de Jordan forte ssi toutesurface frontière entre uneκ-composante de 1-spels et uneλ-composante de 0-spels est de Jordan. –2D:(8,4),(4,8)sont des paires de Jordan forte pourZ 2 .(4,4)non. –3D:(26,6),(6,26)sont des paires de Jordan forte pourZ 3 .(6,6)non. –nD: il existe des paires de Jordan fortes[Herman92,Udupa94,Lachaud00]

6

Figure 5: Surface de Jordan

Figure 6: ObjetO, Fermeture deO, Bord deO

•Les frontières / bords d’objets sont donc séparants (et n par dénition) •algorithmes de suivi de surface ennD •à des espaces discrets non régulierscadre très générique extensible [Herman98]

Surface = complexe cellulaire dimn−1 •Topologie combinatoire[Kovalevsky89, Latecki96] Denition 9 (Bord d’un objet).SoitCl(O)lafermetured’un objetOdans la grille cellulaireC n . LeborddeOest le sous-ensemble des cellules deCl(O)dont l’étoiletouche le complémentaire deCl(O)dansC n . C’est un complexe polyédrique fortement connexe de dimensionn−1. • beaucoupIntérêts : de structures de haut niveau dénies sur la grille cellulaire. Cartes topologiques[Braquelaire, Brun, Damiand, Desbarats, Domenger, Fio- rio], pyramides combinatoires[Brun,Kropatsch], bloc complexes[Kovalevsky] •Problèmes : les bords n’ont pas forcément la propriété de séparation •Images bien-composée[Latecki97]: Image qui ne comportent pas certaines con- gurations Toutes les connexités sont équivalentes

7

Figure 7: Les bords dènis comme complexes cellulaires ne sont pas des variétés en général

Figure 8: Congurations interdites dans les images bien-composées

Theorem 10.Tout bord d’un objet dans une image bien-composée est unen−1- (pseudo)variété fermée (ie. surface de Jordan) •: comment transformer une image mal-composée en image bien-composéeProblème ? Ce n’est pas un traitement local.

Conclusion partielle Les deux dernières approches sont clairement plus adaptées. 1. On retrouve des surfaces qui sont effectivement des ensembles ns séparants de l’espace. On dispose d’algorithmespour extraire desbords d’objetspar suivi, en garantissant certaines propriétés. 2. On dispose de toutes les cellules de la grille régulière. On peut donc facilement dénir des complexes cellulaires, des surfaces comme ensembles de surfels, des contours de surfaces comme ensemble de cellules de dimensionn−2. On peut aussi utiliser des resultats de topologie combinatoire. La grille cellulaire contient tous les éléments des espaces discrets (spels, surfels).

2 Extraction des surfaces discrètes 2.1 Imagerie volumique, Isosurfaces Imagerie volumique

8

Figure 9: (a) Coupes, (b) Rendu volumique, (c) Isosurfacess= 0.1et (d)s= 0.3

Figure 10: Tomodensitométrie (scanner X) : coupes, isosurface

•Imagerie 3D : scanner X, IRM, TEP, échographies 3D, microscopie confocale. FonctionI:Z 3 →R •Visualisation par coupes, Rendu volumique[Levoy, . . . ]: illustratif mais pas de mesures quantitatives •Isosurface: lieux des points de même valeur parI Denition 11 (Isosurface).Isosurfacede valeursdansI:{(x, y, z)∈R 3 |I(x, y, z) = s}. C’est une 2-variété siIest sufsamment régulière

Calcul des isosurfaces par Marching-cube •Algorithme duMarching-cube[Lorensen,Cline 87] d’une sur-: reconstruction face linéaire par morceaux par examen de tous les blocs de 8 voxels de l’image •Dans chaque bloc, chaque voxeluest classé intérieur ou extérieur selonI(u)≥ s.2 8 = 256congurations possibles réduites à 15 par symmétries •Sur une arète(u, v),I(u)< s,I(v)≥s, sommettplacé à l’estimationI(t) =s. ⇒Surface triangulée approchant l’isosurfacesdeI

9

Figure 11: Angiographie RM : coupes, rendu volumique, isosurface

Figure 12: Microscopie confocale : coupes, isosurfaces, reconstruction par modèle dèformable

Figure 13: Congurations classiques et triangles associés

10