Surfaces discrètes définition extraction et géométrie
29 pages
Français

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

-

Le téléchargement nécessite un accès à la bibliothèque YouScribe
Tout savoir sur nos offres
29 pages
Français
Le téléchargement nécessite un accès à la bibliothèque YouScribe
Tout savoir sur nos offres

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

Informations

Publié par
Date de parution 01 avril 2005
Nombre de lectures 60
Langue Français
Poids de l'ouvrage 2 Mo

Extrait

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 importantsurfaces 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(Nn1). 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 unen1-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 pourn3 –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 toutm1-simplexe est face d’exactement deuxm-simplexes. –Les pseudo-variétés sont séparantes Theorem 3 (Jordan–Brouwer).Touten1-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:{uO, u ρ-adjacent àO} Bord extérieurd’un objetO:{v ρO, v-adjacent àO} espace “interpixel”Cn: grille cellulaire de dimensionn spel = cube unité. Un de dimensionn surfel: unen1-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).SZ3est 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:uS, 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ωnZn×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 dimn1 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 dimensionn1.  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 unen1-(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 dimensionn2. 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:Z3R 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
  • Accueil Accueil
  • Univers Univers
  • Ebooks Ebooks
  • Livres audio Livres audio
  • Presse Presse
  • BD BD
  • Documents Documents