L'Équipe Imagerie et Structures Discrètes organise la
8ième conférence DGCI (Discrete Geometry for Computer Imagery)
à l'ESIEE en 1999
English version
Équipe Imagerie et Structures Discrètes
L'Équipe Imagerie et Structures Discrètes organise la
8ième conférence DGCI (Discrete Geometry for Computer Imagery)
à l'ESIEE en 1999
| Les chercheurs-enseignants : | Les chercheurs doctorants : |
|
|
| Nos thèmes de recherche : | Notre galerie d'applications : |
| Analyse d'images 3D Analyse d'images 2D |
Coopérations:
Un point simple est un point d'un objet dont l'enlèvement ne modifie pas la topologie de l'objet. Cette notion est à la base de tous les algorithmes permettant d'analyser une image selon des critères topologiques. Nous avons proposé une condition nécessaire et suffisante permettant de caractériser les points simples dans une maille cubique 3D. Plus concise et plus facile à évaluer que les caractérisations précédentes, cette caractérisation nécessite uniquement la recherche de deux nombres de composantes connexes que nous avons appelés nombres topologiques. Outre la caractérisation des points simples, les nombres topologiques permettent d'effectuer une classification des points selon leurs caractéristiques topologiques locales. Ainsi, il est possible de détecter les points qui ont localement les mêmes caractéristiques topologiques que des points de courbes, de surfaces, des points d'intersection de surfaces, de courbes... Nous avons également proposé plusieurs façon de calculer ces deux nombres topologiques; par exemple, nous avons montré qu'on peut calculer ces deux nombres en détectant la présence de certaines configurations dans le voisinage du point considéré.
Il est possible d'utiliser 4 types de voisinage dans une maille cubique. Ces 4 types de voisinage permettent de vérifier le théorème de Jordan en 3D (une surface fermée sépare l'espace en deux régions). Nous avons introduit la notion de voisinage géodésique d'un point. Cette notion nous a permis d'étendre notre caractérisation pour ces 4 types de voisinage.
Un algorithme de squelettisation réduit un objet sans changer sa topologie. Pour cela on enlève des points de l'objet qui sont simples (pour ne pas changer sa topologie, voir paragraphe précédent) et qui satisfont certaines conditions dites "géométriques". En 3 dimensions le choix des conditions géométriques permet de réduire l'objet en des surfaces (on a alors un squelette surfacique) ou bien en des courbes (on a un squelette curviligne). Contrairement au cas 2D, il n'existe que peu d'algorithmes de squelettisation en 3D. Certains sont des algorithmes non valides (ils changent, dans certaines configurations, la topologie de l'objet), d'autres s'appuient sur une condition suffisante mais pas nécessaire pour caractériser les points simples; il s'ensuit que le squelette obtenu est composé de points inutiles.
Nous proposons un algorithme parallèle de squelettisation 3D qui s'appuie sur les deux nombres topologiques présentés ci-dessus. Ces deux nombres permettent de détecter les points simples et de disposer de conditions géométriques conduisant à un squelette surfacique ou curviligne. Notre algorithme utilise une décomposition en sous-mailles de la maille cubique initiale. Une propriété fondamentale de notre algorithme est sa complétude: il ne reste plus de points indésirables dans les squelettes obtenus. A notre connaissance, cet algorithme est le premier algorithme parallèle de squelettisation 3D qui soit complet.
Par définition, on peut enlever un point simple sans modifier la topologie d'un objet. Cependant la suppression en parallèle de points simples peut changer la topologie d'un objet. En 2 dimensions, certaines approches ont été proposées pour résoudre ce problème. Cependant ces approches ne sont plus valables dans un espace à trois dimensions. A travers la notion de point P-simple, nous proposons une stratégie générale pour enlever des points en parallèle sans changer la topologie. Cette notion de point P-simple correspond a une notion d'homotopie forte: un ensemble Y est fortement homotope à un ensemble X, si Y est inclus dans X et si pour tout Z, tel que Y inclus dans Z et Z inclus dans X, Z est homotope à X. Dans ce cas X \ Y est constitué de points P-simples.
Nous avons proposé une caractérisation des points P-simples qui peut être effectuée en un temps linéaire. Le problème que nous avons résolu était à priori exponentiel, ce résultat est donc tout à fait inespéré.
Nous avons utilisé la notion d'homotopie forte pour proposer une nouvelle approche des surfaces simples dans une maille cubique. Soit X un sous-ensemble de Z3, tel que le complémentaire de X soit composé de deux composantes connexes A et B. On dira que X est une surface forte si X union A et X union B sont respectivement fortement homotopes à A et B. Nous avons montré que les notions de surfaces discrètes proposées dans la littérature sont des surfaces fortes. La réciproque n'est cependant pas vraie, les surfaces fortes pourraient ainsi étendre la notion de surface simple.
Nous avons proposé un algorithme de fermeture de trous dans une image 3D. Un trou dans un objet en 3D n'est pas une région de l'espace, il n'est donc pas possible d'utiliser, comme en 2D, des algorithmes de recherche de composantes connexes pour fermer des trous 3D. En se basant sur les études que nous avons faites sur la topologie de Z3, nous proposons une méthode pour fermer des trous dans un objet 3D. Cette méthode peut être implantée en un temps linéaire. A notre connaissance, il s'agit de la première méthode pour résoudre ce problème.
Nous avons transposé les méthodes que nous avons développées sur des images binaires 2D et 3D à des images en niveaux de gris. Nous avons défini la topologie d'une fonction dont le domaine est Z2 et proposé plusieurs notions de noyau homotopique pour une telle fonction. Nous avons défini des opérateurs de régularisation sur de tels noyaux. Ceci nous a permis de segmenter des images en niveaux de gris sans utiliser le moindre paramètre. Les premiers résultats de cette nouvelle approche de la segmentation semblent ainsi très prometteurs.
Responsable de ces pages : Michel Couprie