Structuration du nuage de points, reconstruction 3D

La structuration permet de rendre les méthodes de segmentation qui suivent plus simples, plus rapides, plus efficaces,. . . Les structures généralement introduites sont de plusieurs types : partitionnement en grille, maillage et triangulation, croûte, -forme, arbre, graphe, squelette, etc. Partitionnement en grille L’espace et le nuage de points peuvent être divisés en quadrillage régulier, ce qui donne les baquets (buckets) [Gou97], ou, lorsque la taille est petite, les voxels [Alg95]. Il est également possible de s’adapter un peu plus aux données par des partitions adaptatives de type quadtree(2D), octree(3D) [YS99, WSI98, PDH+97], ou k-d trees . Le principe de ces structures est de prendre en compte la densité de points pour créer des cellules plus petites dans les régions denses. L’octree préserve une régularité dans la structure mais avec des nombres de points différents dans chaque cellules, alors que le k-d tree divise chaque cellule en laissant le même nombre de points de chaque côté. Ces structures ne donnent pas vraiment d’indication sur les surfaces présentes, mais peuvent toutefois être utiles pour accélérer l’accès aux points d’un nuage. Ceci s’avère en particulier intéressant pour optimiser les algorithmes faisant intervenir la recherche de voisins. Bien entendu, ceci requiert de redéfinir des algorithmes qui exploitent ces structures. Maillages, triangulations Tout d’abord, on peut effectuer une triangulation 3D des points (c’est-à-dire produire des tétraèdres). La triangulation de Delaunay (2D, 3D ou nD) constitue désormais un classique en géométrie algorithmique [PS85, BY95, Lem97]. Dans notre cas, les points se trouvant sur des surfaces, nous nous intéressons davantage aux méthodes de maillage surfacique. Suivant [Bes99], on peut classer les différentes méthodes de construction de maillage surfacique suivant les types de données au départ :

– maillage sur une image 2,5D [GB96] ,

– fusion de maillages de plusieurs vues 2,5D [WSI98, HI97, HSIW96, MY95, SL95, RAS97],

– maillage à partir de points 3D [Alg95, HDD+92, ABK98, ST92, GM97, Guy95, TM98].

En ce qui concerne la construction de maillage à partir de points 3D, la méthode de Hoppe et al. [HDD+92] est une référence fréquemment citée et employée de construction de maillage à partir de points 3D. Notons que cette méthode a été appliquée à des scènes où les points sont sur une seule surface, fermée, et que les points sont uniformément répartis sur cette surface (Figure 2.2). Ce sont des conditions idéales, rarement vérifiées en pratique, pour lesquelles la plupart des algorithmes de construction de maillages produisent un bon résultat [ABK98]. On peut s’attendre à ce que cette méthode ne donne pas les résultats escomptés lorsque la surface est ouverte et que la densité de points n’est plus uniforme. D’autre part, la triangulation de Delaunay en 2D peut s’étendre simplement au cas du maillage de surfaces en 3D du moment que l’on a une indication de la topologie de la surface. En effet, si l’on sait que la surface peut se projeter sur un plan, et que ce plan est connu, il suffit de réaliser une triangulation de Delaunay sur le plan que l’on projette sur la surface. C’est le principe de construction de maillage utilisé dans plusieurs logiciels, dont 3Dipsos et Imageware Surfacer (EDS). Notons que l’on peut faire de même avec un cylindre, une sphère, etc. Ceci suppose que l’on connaisse le type de surface, ce qui n’est bien entendu pas toujours le cas au départ ! Remarquons également que l’on peut construire une triangulation surfacique en prenant comme surface de projection le plan tangent au nuage de points (avec le centre d’inertie). Ici intervient alors la taille du voisinage utilisé (soit une taille fixe, soit un nombre de voisins).

TRAITEMENTS «BAS NIVEAU» DES DONNÉES 3D (SANS MODÈLES)

Sur un nuage de points 3D La méthode de R. McLaughlin et Alder décrite ci avant a également été appliquée au cas 3D (cf. [McL00]), pour l’extraction de courbes (chaînettes) ou de surfaces. Le maillage 3D permet de faire à peu près comme dans le cas 2,5D : on peut estimer (même grossièrement) les normales, les courbures, etc. et ainsi faire une classification des points suivant ces informations. Aussi la plupart des auteurs utilisent-ils, plus ou moins explicitement, une structure de maillage au préalable de la phase de segmentation proprement dite. Hoppe et al. effectuent d’abord une construction de maillage avec la méthode introduite dans [HDD+92], et dont il a été fait référence précédemment (adaptée au cas d’un seul objet). Ensuite, Hoppe et al. [HDD+94] construisent une fonction lisse par morceaux ainsi que des arêtes et des jonctions à l’aide de surfaces de subdivision. Fisher et al. [FFE97] utilisent la même méthode pour construire un maillage. Ensuite, les angles entre normales voisines sont estimés afin de classer les zones élémentaires en «plan, arête et courbe». Un exemple de scène segmentée est donné figure 2.9 (noter l’absence de segmentation entre cylindre et plan latéraux lors de la première phase). FIG. 2.9 – Pièce «BAe»(U Edinburgh) Wu et Levine [WL95, WL97] simulent la répartition d’une charge électrique sur le maillage pour dégager les minima de convexité, qu’ils utilisent pour segmenter un objet en parties convexes (part segmentation). Les scènes utilisées dans les exemples donnés par les auteurs sont cependant relativement simples. Chaine et Bouakaz [Cha00, CB00] estiment les normales et dégagent des zones connexes par rapport à leurs orientations. Ceci fournit une segmentation initiale. Celle-ci est complétée par une méthode de fusion de régions (Figure 2.10). Appliquée aux images de [HJBJ+96], cette méthode a donné des résultats comparables et s’est avérée plus rapide que UE, WSU et USF, moins rapide que UB.

Enfin, les méthodes de décomposition d’un nuage de points en composantes -connexes [Gou97, PTVF92b] ou en groupements (clusters) [CM98] peuvent aussi être considérées comme des méthodes de segmentation particulières. Dans [Gou99, Gou97], l’estimation des centres de courbure permet de passer du problème de la segmentation entre cylindre et tore telle que sur la figure 2.13 au problème de la segmentation des centres de courbures en segments de droite et cercles. Cette segmentation est faite à l’aide de la valeur de la courbure minimale : les centres correspondant au cylindre ont une courbure minimale nulle. Notons toutefois que la courbure minimale seule n’est pas idéale pour faire cette segmentation car des points sur le tore peuvent aussi avoir une courbure minimale nulle [Gou97, p. 67]. Cependant, une difficulté de cette approche réside à mon avis dans l’estimation des courbures (bruitée et lente). La méthode de Medioni et al. [GM97, Guy95, TM98] permet de construire, en même temps que les surfaces les plus probables, les courbes les plus probables étant donné l’ensemble (peu dense) de points. Aussi peut on trouver les arêtes en même temps que le maillage de l’objet (dans l’exemple de la figure 2.11, la méthode permet d’extraire les points correspondant à la jonction entre la cacahuète et le plan). FIG. 2.11 – Tensorvoting de U Southern California. Reconstruction de surfaces et de jonctions Un test du programme TensorVoting, téléchargé depuis le site de U Southern California, a montré que le temps d’exécution croît rapidement avec le nombre de points initiaux : sur un nuage de 5000 points («pipe.dat») comprenant deux cylindres concentriques (Figure 2.12), la reconstruction des surfaces des deux cylindres a pris 7 min environ (résultat : 28210 triangles) sur PC Pentium III. D’autre part, ce programme a été testé sur la scène «coude» (Figure 2.13), avec également 5000 points. Notons tout d’abord que cette scène ne peut pas être segmentée par cette méthode, car la jonction entre les deux primitives est lisse. Par contre, il paraissait intéressant de tester la reconstruction de la surface formée par le cylindre et le tore. Les surfaces reconstruites par l’algorithme, qui apparaissent à droite de la figure 2.14, ne forment clairement pas une représentation correcte du coude.

TRAITEMENTS DES DONNÉES 3D À BASE DE MODÈLES

Modèles déformables On peut également classer les courbes et surfaces de niveaux (level set), ou modèles déformables (par EDP) dans les surfaces implicites. On trouve dans cette catégorie les notions de contours actifs, snakes, . . . Ces modèles sont notamment utilisés en imagerie médicale [HFG00]. Surfaces définies par des critères géométriques On peut par exemple définir les primitives vues au chapitre 1 à l’aide de caractérisations géométriques : le plan peut être défini par un produit scalaire constant, le cylindre par une distance constante (par rapport à un axe), le tore également par une distance constante (par rapport à un cercle), etc. Ceci donne lieu dans le cas général à des équations implicites non-polynomiales (voir chapitre 4 et annexe A). Remarque Ceci n’est guère employé dans la littérature. L’une des raisons est peut-être que ceci contraint à définir un type de modèle par primitive recherchée. Une autre raison est que cette approche est simple pour les surfaces simples, pour lesquelles on peut définir analytiquement la distance exacte. Toutefois, plusieurs auteurs ont souligné l’intérêt d’utiliser le plus tôt possible le type précis de primitive que l’on cherche à extraire [LMM98, LMM97, FFE97]).

Surfaces paramétrées Le domaine de la Conception Assistée par Ordinateur (CAO) utilise abondamment des définitions paramétrées pour les surfaces, comme par exemple les splines, les b-splines, et les NURBS. Ces surfaces sont des surfaces d’interpolation satisfaisant certaines contraintes de régularité [Lau72]. Elles sont le plus souvent définies par des points de contrôle, sur lesquels on peut faire un ajustement [Con96]. Les splines sont parfois utilisées pour la segmentation [Lei93]. Objets catalogués Les modèles utilisés peuvent être, comme en reconnaissance d’objets, des modèles d’objets parmi un ensemble fini et connu (c’est-à-dire un catalogue). Par exemple, le système Artisan de Carnegie Mellon University [JH97, JHOH97] (voir site Internet dont l’adresse est donnée en annexe) utilise des modèles de vannes. Modèles CAO plus complexes Parmi les modèles plus complexes, on trouve la b-rep (pour boundary representation), c’està- dire représentation par frontières, que l’on peut construire à partir d’une scène déjà segmentée [FEF97, HGB98b, HGB98a, HGB95] ; les modèles CSG (constructive solid geometry, représentation par volume et opérations ensemblistes ; ou encore des modèles CAO articulés [WFAR99, AFRW97].