Projet image 2015 : Reconstruction de surfaces implicites à partir de points orientés

De Ensiwiki
Aller à : navigation, rechercher
Reconstruction d'un visage humain
Project schedule.png
Titre du projet Reconstruction de surfaces implicites à partir de points orientés
Cadre Projets de spécialité
Page principale Projets de spécialité image

Encadrants Li Wang


Étudiants

Sujet

Reconstruction de surfaces implicites à partir de points orientés

Bunny : points orientés
Bunny : reconstruction de la surface


  • Aujourd’hui, la réalité virtuelle prend une place de plus en plus importante dans notre société, avec l’avènement de l’informatique et des nouvelles technologies qui l’utilisent. Le projet que nous considérons ici est la compréhension et l’implémentation de quelques algorithmes qui permettent d’obtenir une représentation en 3D d’un objet à partir d’un ensemble de points orientés, par exemple issus de scanners médicaux. Les points orientés, en 3D par exemple, sont les 3 coordonnées de ce points, auquel on associe un vecteur (3 coordonnées également) qui correspond à la normale à la surface en ce point-ci. Elles sont nécessaires pour reconstruire proprement la surface, notamment pour distinguer l'intérieur de l'extérieur.


  • Ce projet est concentré sur la phase qui permet de passer d'un ensemble de points orientés à une fonction indicatrice définissant la surface à représenter. La phase consistant à extraire un maillage de la surface a été faite par notre encadrant (qui est doctorant) et nous est fournie (méthode de triangulation de Delaunay, marching cubes, Voronoï, etc...).


  • Ceci permettra, à terme, d’intégrer notre code dans une bibliothèque informatique en cours de création par notre encadrant, car nous nous basons sur du code qu’il a déjà réalisé.


Objectifs

  • Tout d’abord, pourquoi ce projet ? En effet, les algorithmes que nous implémenterons sont connus et existent déjà au sein de grosses bibliothèques (comme CGAL par exemple). On fera donc cela afin d’éviter de devoir inclure des bibliothèques conséquentes, car celles-ci rajoutent beaucoup de dépendances qui alourdissent la compilation et elles obligent toute personne voulant utiliser notre programme à installer ces bibliothèques.
  • Concrètement, nous devons implémenter quelques algorithmes (trois au maximum si on a le temps), qui sont par ordre de priorité décroissante : méthode de Poisson [1], méthode MPU [2], méthode RBF [3]. Un objectif est donc de suivre les algorithmes, écrits en toutes lettres et accompagnés de formules mathématiques dans les articles de recherche fournis, pour les transcrire dans le langage de programmation utilisé, le C++.
  • Un autre objectif est de mener une comparaison sur divers critères (coûts d’exécution en temps et en espace par exemple) de ces différents algorithmes, à la fois entre eux pour notre propre implémentation, mais aussi par rapport aux implémentations déjà existantes. Ceci afin de situer notre travail et ses performances parmi la myriade de codes disponibles aujourd’hui.
  • Ces objectifs sont à atteindre (ou tout du moins à approcher le plus possible) dans un délai de 3 semaines et demie.


Exemple : reconstruction en 2D par l'algorithme de Poisson


Difficultés et dépendances potentielles

  • Un des premiers risques majeurs que l’on pourra rencontrer est le défaut de ressources nécessaires afin de réaliser notre implémentation. En effet, nous avons par exemple besoin de la création d’un réseau privé virtuel et d’un dépôt informatique commun afin de travailler en équipe, et celui-ci peut-être difficile à mettre en œuvre si nous ne disposons pas du matériel de l’Ensimag, ce qui est le cas à certains moments de la journée. De plus, les composants logiciels nécessaires à l’implémentation dans une version spécifique de C++ (ici la version 2011) ne sont pas forcément disponibles sur les machines de l’Ensimag, ce qui nous oblige à configurer tout cela et à travailler sur nos machines personnelles. En somme, il s’agit de la configuration du matériel nécessaire. Pour éviter au maximum ce risque, il faut que l’on configure dès le début tout notre matériel de travail en vue de ce projet, pour que l’on puisse programmer dans un cadre adéquat.


  • Un autre risque est la lenteur de nos algorithmes, du fait de leur conception en un temps réduit et donc de la non-optimisation de certaines fonctions. En effet, comme l’objectif est de reconstruire une surface à partir de points, alors si l’on envoie en entrée du programme un modèle contenant un trop grand nombre de points, notre algorithme sera difficilement évaluable au sens où le résultat sera obtenu en un temps trop grand. Ainsi il sera nécessaire de disposer ou de créer de nombreux tests « légers », c’est-à-dire ne contenant pas énormément de points, afin de pouvoir visualiser notre implémentation déjà sur des cas simples.


  • Enfin, un autre risque peut être la difficulté à trouver des bugs dans notre implémentation, du fait des structures de données utilisées, comme les octree par exemple. Pour éviter ce genre de problème, on devra bien moduler notre travail, l’aérer en différents fichiers, bien commenter les morceaux compliqués du code, et faire souvent des tests pour s’assurer que tout cela fonctionne et interagit bien avec les autres composantes de l’implémentation.


  • Comme dépendance, on peut citer le code fourni par notre encadrant. En effet, notre implémentation doit être conforme à ce qui a déjà été fait, car tout cela se retrouvera condensé en une bibliothèque informatique. Il est donc primordial de conserver la cohérence au sein de celle-ci, afin de satisfaire les exigences du client, qui comprennent entre autres une utilisation simple.


Organisation

Début du projet

  • Tout d'abord, nous avons lu les articles de recherche [1] et [2], afin de bien comprendre les 2 premiers algorithmes que nous aurons à implémenter. Nous en avons ensuite discuté avec notre encadrant et nous lui avons résumé ces algorithmes. Il nous confirmait ensuite notre bonne compréhension des articles. Cette étape était primordiale car nous partions de zéro en ce qui concerne l'implémentation de l'algorithme décrit, et celui-ci était explicité en anglais et avec quelques formules mathématiques. Ainsi il fallait comprendre parfaitement cela, pour que nous puissions nous concentrer sur les diverses implémentations plus ou moins compliquées et non abordées dans ces articles.

Implémentation

  • Nous avons discuté, entre membres du groupe, des structures choisies pour implémenter l'algorithme : la structure d'octree (structure d'arbre dont les nœuds non feuilles ont 8 fils) par exemple.
  • Au départ, nous étions tous sur l'algorithme de Poisson [1], dont un membre s'occuper de la construction de la structure d'octree et toutes les fonctions s'y rapportant.
  • Lorsque l'algorithme de Poisson donnait des résultats proches de ceux souhaités, un membre est resté sur la correction de cette implémentation, et les deux autres ont commencé l'implémentation de l'algorithme MPU [2]. Nous avons continué comme cela jusqu'aux derniers jours du projet.

Résultats

  • Nous pouvions créer des entrées pour nos algorithmes et en visualiser les sorties grâce au logiciel Meshlab. Il permet de générer des formes simples, de les exporter, et aussi de visualiser toute sorte de formes, tout cela en 3D. Les entrées et sorties consistent en des fichiers en .obj ou .xyz par exemple, contenant une liste de points (3 coordonnées), chacun associé à une normale (3 coordonnées).
  • Nous avons précisé si la surface a été générée par l'algorithme de Voronoï ou marching cubes, mais en augmentant le nombre de sites pour ces deux méthodes, la différence des résultats est peu visible.

Algorithme de Poisson

  • Pour cette implémentation, nous avons finalement réussi à obtenir les résultats souhaités sur toutes les formes simples, y compris un modèle de chaton simplifié. Nous avons donc la confirmation qualitative que la fonction implicite que nous avons calculée est correcte.
Setup
2 sphères : ~1200 points orientés
Setup
2 sphères : reconstruction par Poisson puis Voronoï
Setup
Tore : ~280 points orientés
Setup
Tore : reconstruction par Poisson puis Voronoï
Setup
Kitten : ~5000 points orientés
Setup
Kitten : reconstruction par Poisson puis Voronoï

Algorithme MPU

  • Pour cette implémentation, nous n'avons pas réussi à avoir des résultats convaincants dans le temps imparti. Notons tout de même qu'à part la structure d'octree qui est utilisée ici et également dans Poisson, tout le reste de l'algorithme est totalement différent de Poisson, sur le principe et sur l'implémentation.
  • Nous obtenons tout de même quelques résultats intéressants sur certaines formes simples, comme la sphère ou le tore. Mais pour un modèle plus complexe, on n'observe plus rien de ressemblant, dû certainement à une erreur dans une des étapes de l'algorithme.
Setup
Sphère : ~160 points orientés
Setup
Sphère : reconstruction par MPU puis marching cubes
Setup
Tore : ~280 points orientés
Setup
Tore : reconstruction par MPU puis marching cubes

Comparaison / Evaluation

  • Pour l'algorithme de Poisson, on a les résultats suivants pour les pics mémoire :


Depth=5, 10000 sites

Sphere 642 pts : 98.8 MB

Deux Spheres 1284 pts : 679 MB

Torus 1466 pts : 1.999 GB


Depth=6, 10000 sites

Kitten 5210 pts : 4.3 GB


Conclusion

Bilan de ce qui a été fait

  • Notre objectif principal était de comprendre et d'implémenter au moins les algorithmes de Poisson et MPU, afin de les comparer par le suite.
  • Nous avons bien compris les deux algorithmes, et nous avons réussi à obtenir ce qu'il fallait concernant l'algorithme de Poisson, bien qu'il manque d'optimisation à certains endroits. Pour MPU, l'implémentation est quasi-complète, mais elle ne renvoie pas la forme voulue sur certains cas simples, ce qui empêche donc son utilisation sur des cas réels comme le petit chat obtenu avec Poisson.

Perspectives

  • Les perspectives pour Poisson sont l'optimisation à divers endroits, notamment car il utilise beaucoup de calculs mathématiques que nous avons implémentés nous-mêmes. L'optimisation est ici très importante car plus le programme s'exécutera vite et avec moins de mémoire, plus on pourra générer des formes complexes avec beaucoup plus de points. Ainsi, comme il semble renvoyer ce à quoi on s'attendait sur les modèles que l'on a pu tester, il ne reste plus qu'à l'optimiser pour les formes plus compliquées.
  • Pour MPU, il faudrait finir l'implémentation concernant la détection et la construction des coins, comme dans un cube par exemple. Elle a été commencée mais non terminée, faute de temps. Il faudrait aussi corriger là ou les erreurs qui peuvent parfois produire des excroissances en dehors de la forme souhaitée, comme par exemple pour la reconstruction du tore montrée ci-dessus.
  • Enfin, on pourrait regarder plus en détail le code fourni pour les méthodes d'extraction de surfaces, à savoir par le diagramme de Voronoï et par marching cubes. En effet, on pourrait alors l'optimiser à notre problème et selon les différents modèles que l'on aura en entrée.

Bilans personnels

  • Ce projet nous a amené à faire ce que l'on souhaitait, à savoir implémenter, dans un langage très utilisé comme le C++, un algorithme très mathématique. Les domaines de l'informatique et des mathématiques appliquées étaient donc très sollicités et bien mélangés. De plus, ce projet était bien dans la continuité de cours que nous avions suivis (Graphique 3D et Traitement d'Image par exemple).
  • Le fait de partir de zéro concernant l'implémentation de tels algorithmes, avec pour seul support les articles de recherche, était au départ très stimulant pour nous. Cela nous a en effet appris à être très autonomes pour un projet assez long, et c'est ce que nous voulions. Cependant, nous nous sommes vite rendus compte que certains points des articles de recherche étaient assez obscurs pour nous (sans doute l'étaient-ils moins pour les chercheurs du domaine...). En effet, l'algorithme était décrit sans jamais évoquer les difficultés d'implémentation sur une machine que cela pourrait amener. Notre trop grande liberté pour cela combinée aux ambiguïtés (dues certainement à notre manque d'expérience dans ce domaine de recherche) des articles nous a finalement bien perturbés. On se rend donc compte qu'un de ces deux points (expérience dans le domaine ou cadre minimum pour l'implémentation) nécessiterait d'être amélioré afin de finir complètement un tel projet.


Références

  • [1] Michael Kazhdan, Matthew Bolitho, and Hugues Hoppe. Poisson surface reconstruction. In Proc. of the Eurographics Symposium on Geometry Processing, 2006.
  • [2] Yutaka Ohtake, Alexander Belyaev, Marc Alexa, Greg Turk, and HansPeter Seidel. Multi-level partition of unity implicits. SIGGRAPH ’03 ACM SIGGRAPH 2003 Papers, pages 463–470, 2003.
  • [3] J. C. Carr, R. K. Beatson, J. B. Cherrie, T. J. Mitchell, W. R. Fright, B. C. McCallum, and T. R. Evans. Reconstruction and representation of 3d objects with radial basis functions. SIGGRAPH ’01 Proceedings of the 28th annual conference on Computer graphics and interactive techniques, pages 67–76, 2001.