Topologie discrète et surfaces discrètes Extraction des surfaces discrètes

Topologie discrète et surfaces discrètes
Extraction des surfaces
Mesures géométriques
Mise en oeuvre des surfaces discrètes
Surfaces discrètes : définition, extraction et
géométrie
Jacques Olivier Lachaud
lachaud@labri.fr
LaBRI, Université Bordeaux 1
Ecole Jeunes Chercheurs, LIRMM, Montpellier, 4 8 avril
2005
Jacques Olivier Lachaudlachaud@labri.fr Surfaces discrètes : définition, extraction et géométrieTopologie discrète et surfaces discrètes
Extraction des surfaces
Mesures géométriques
Mise en oeuvre des surfaces discrètes
Plan de l’exposé
1 Topologie discrète et surfaces discrètes
2 Extraction des surfaces discrètes
3 Mesures géométriques
4 Mise en oeuvre des surfaces discrètes
Jacques Olivier Lachaudlachaud@labri.fr Surfaces discrètes : définition, extraction et géométrieTopologie discrète et surfaces discrètes Contexte, Topologie, Surfaces
Extraction des surfaces Problématiques induites par le discret
Mesures géométriques Définitions usuelles
Mise en oeuvre des surfaces discrètes Principales approches aux surfaces discrètes
Plan de l’exposé
1 Topologie discrète et surfaces discrètes
Contexte, Topologie, Surfaces
Problématiques induites par le discret
Définitions usuelles
Principales approches aux surfaces discrètes
2 Extraction des surfaces discrètes
3 Mesures géométriques
4 Mise en oeuvre des surfaces discrètes
Jacques Olivier Lachaudlachaud@labri.fr Surfaces discrètes : définition, extraction et géométrieTopologie discrète et surfaces discrètes Contexte, Topologie, Surfaces
Extraction des surfaces Problématiques induites par le discret
Mesures géométriques Définitions usuelles
Mise en oeuvre des surfaces discrètes Principales approches aux surfaces discrètes
Contexte I
Contexte : analyse d’images (2D, 3D, voire plus)
Enjeux : Identifier, Représenter, Mesurer, Caractériser,
Comparer, Indexer, Simplifier, Localiser, Visualiser les
objets ou composants de l’image
⇒ nécessite souvent d’avoir des informations/modèles
topologiques et géométriques
Les éléments et parties d’une image sont discrets (i.e. non
continus)
nEspace discret :Z
La topologie précède la géométrie
1 discrète pour l’espace
2 objets et bord d’objets / surface
3 mesures
Jacques Olivier Lachaudlachaud@labri.fr Surfaces discrètes : définition, extraction et géométrieTopologie discrète et surfaces discrètes Contexte, Topologie, Surfaces
Extraction des surfaces Problématiques induites par le discret
Mesures géométriques Définitions usuelles
Mise en oeuvre des surfaces discrètes Principales approches aux surfaces discrètes
Topologie I
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 discrètes
Quelques exemples
1 Visualisation : en 3D, on voit la surface de l’objet, pas le
volume. Permet le back 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
nbords d’objets réguliers dans des images N ont une
n−1complexité en O(N ).
Jacques Olivier Lachaudlachaud@labri.fr Surfaces discrètes : définition, extraction et géométrieTopologie discrète et surfaces discrètes Contexte, Topologie, Surfaces
Extraction des surfaces Problématiques induites par le discret
Mesures géométriques Définitions usuelles
Mise en oeuvre des surfaces discrètes Principales approches aux surfaces discrètes
Topologie II
4 Temps de calcul : transformation de calculs de volume en
calculs de surface (volume, moments, intégrales,
intersections de formes)
Jacques Olivier Lachaudlachaud@labri.fr Surfaces discrètes : définition, extraction et géométrieTopologie discrète et surfaces discrètes Contexte, Topologie, Surfaces
Extraction des surfaces Problématiques induites par le discret
Mesures géométriques Définitions usuelles
Mise en oeuvre des surfaces discrètes Principales approches aux surfaces discrètes
Surface, séparation I
Définition standard (surface plongée)
m variété (m manifold)
Une m variété est un espace topologique localement euclidien
de dimension m (homéomorphisme local).
Une surface est une n− 1 variété plongée dans l’espace
neuclidien de dimension n (R ).
⇒Peu utilisable d’un point de vue informatique.
Jacques Olivier Lachaudlachaud@labri.fr Surfaces discrètes : définition, extraction et géométrieTopologie discrète et surfaces discrètes Contexte, Topologie, Surfaces
Extraction des surfaces Problématiques induites par le discret
Mesures géométriques Définitions usuelles
Mise en oeuvre des surfaces discrètes Principales approches aux surfaces discrètes
Surface, séparation II
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 (Jordan (2D))
2 2Si J est une courbe simple dansR alorsR \ J a deux
composantes connexes de frontière commune J (l’intérieur et
l’extérieur)
Jacques Olivier Lachaudlachaud@labri.fr Surfaces discrètes : définition, extraction et géométrieTopologie discrète et surfaces discrètes Contexte, Topologie, Surfaces
Extraction des surfaces Problématiques induites par le discret
Mesures géométriques Définitions usuelles
Mise en oeuvre des surfaces discrètes Principales approches aux surfaces discrètes
Surface, séparation III
Les surfaces seront donc des parties de l’espace fines et
séparantes.
Jacques Olivier Lachaudlachaud@labri.fr Surfaces discrètes : définition, extraction et géométrieTopologie discrète et surfaces discrètes Contexte, Topologie, Surfaces
Extraction des surfaces Problématiques induites par le discret
Mesures géométriques Définitions usuelles
Mise en oeuvre des surfaces discrètes Principales approches aux surfaces discrètes
Surfaces combinatoires I
Définition combinatoire des variétés
Possible pour n≤ 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
Jacques Olivier Lachaudlachaud@labri.fr Surfaces discrètes : définition, extraction et géométrie