Surfaces discrètes définition extraction et géométrie
29
pages
Français
Documents scolaires
2005
Le téléchargement nécessite un accès à la bibliothèque YouScribe Tout savoir sur nos offres
29
pages
Français
Documents scolaires
2005
Le téléchargement nécessite un accès à la bibliothèque YouScribe Tout savoir sur nos offres
Publié par
Date de parution
01 avril 2005
Nombre de lectures
85
Langue
Français
Poids de l'ouvrage
2 Mo
Niveau: Secondaire, Collège, Troisième
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
Voir
- 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
Publié par
Date de parution
01 avril 2005
Nombre de lectures
85
Langue
Français
Poids de l'ouvrage
2 Mo
Surfaces discrètes : dénition, extraction et géométrie
Jacques-Olivier Lachaud lachaud@labri.fr 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:Zn •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 imagesNnont une complexité enO(Nn−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(Rn). ⇒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 dansR2alorsR2Ja 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 (JordanBrouwer).Touten−1-pseudo-variété fermée dans Rnest 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 surZnles resultats classiques de topologie ?
3
•on ne disposea priorini d’une topologie, ni d’une décomposition simpliciale ou cellulaire. •Topologies surZn 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 deRnengrille 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 deZn(pixel en 2D, voxel en 3D) •objet: partie deZn •ωnadjacence 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(Zn, ρ)
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 “interpixelCn: 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 deZn(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 deZ3 •[Morgenthaler,Rosenfeld 81] [Malgouyres97] Denition 6 (Surface).S⊂Z3est unesurfacessiSsépareZ3en deux com-posantes 6-connexes (séparation) et tout voxel deSest 6-adjacent à chaque com-posante deZ3S(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 deZ3[Malgouyres96]
5
Figure 3: dénition locale d’une surfaceSdeZ3:∀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⊂Zn×Znest une surface de Jordanssi toutωn-chemin deII(S)versIE(S)traversS. Denition 8 (Paire de Jordan forte).SoitIune image binaire surZn. 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 pourZ2.(4,4)non. 3D:(26,6),(6,26)sont des paires de Jordan forte pourZ3.(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 cellulaireCn. LeborddeOest le sous-ensemble des cellules deCl(O)dont l’étoiletouche le complémentaire deCl(O)dansCn. 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:Z3→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)∈R3|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.28= 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
