**Algorithmes d'analyse géométrique de surfaces** Stage de recherche =============================================================================== Ce stage de recherche - se déroulera au laboratoire [LIRIS](https://liris.cnrs.fr/) (bât. Nautibus sur la campus de la Doua, Villeurbanne) - entre Février et Juillet 2020 (6 mois environ) - sous la direction de [Tristan Roussillon](http://perso.liris.cnrs.fr/tristan.roussillon), à contacter pour demander plus de précisions et candidater. - Il sera financé par l'agence national de la recherche (ANR) dans le cadre du projet [PARADIS](http://perso.liris.cnrs.fr/tristan.roussillon/paradis.html). A l'issue du stage, l'étudiant aura découvert la recherche par la recherche et sera monté en compétence en 3D, geométrie algorithmique, arithmétique, ainsi qu'en programmation. En travaillant avec [DGtal](https://dgtal.org/) en tant qu'utilisateur et développeur, il aura acquis en plus une pratique de la programmation incluant tests unitaires, documentation, intégration continue, etc. L'étudiant pourra aussi candidater à une bourse de thèse dans la continuité de son stage, sur un sujet proche et dans le même projet. Contexte =============================================================================== Les volumes 3D proviennent de différentes sources : segmentation d'images acquises par tomographie ou imagerie par résonance magnétique, simulation numérique de processus physiques, éditeurs basés _voxels_, etc. Nous nous intéressons ici à la géométrie des *surfaces digitales* qui délimitent les volumes 3D (Fig. [snow]). ![ [^syntax] Figure [snow]: Interface "glace-air" d'une image d'un microéchantillon de neige.](SnowE2_DigitalData.png width="400px" ) Manipuler ces données sans les transformer permet d'utiliser des structures de données spatiales efficaces de type _octree_, de réaliser simplement des opérations de construction solide, de faire des calculs en nombre entier et exacts, etc. Un inconvénient, en revanche, est sa pauvre géométrie, puisqu'à n'importe quelle résolution, une surface digitale est faite d'éléments de surface carrés parallèles à l'un des axes. Or, de nombreuses tâches en informatique graphique, vision par ordinateur, analyse d'images 3D nécessitent une géométrie plus riche : rendu, déformation de surface pour la simulation ou le suivi, prise de mesures précises, etc. Pour réaliser ces tâches et bénéficier en même temps des avantages précédents, il est nécessaire d'ajouter des données estimées, comme une direction *normale*, en chaque élément de surface (Fig. [normal]). Pour estimer une normale pertinente, il est nécessaire de résumer la géométrie de la surface dans un voisinage autour de chaque élément de surface. Il existe de nombreuses méthodes, dont la plupart ont au moins un paramètre qui contrôle la taille du voisinage et ne s'adapte pas à la géométrie locale. Certaines de ces méthodes sont d'ailleurs implémentées dans la bibliothèque [DGtal](https://dgtal.org/), que le candidat sera amené à utiliser. ![ [^syntax] Figure [normal]: Directions normales estimées sur une surface digitale.](normal.png width="300px" ) Objectifs =============================================================================== Nous souhaitons travailler sur un voisinage adaptatif qui est celui d'un morceau plan de surface. Dans cette optique, le défi n'est pas tant de reconnaître un morceau de plan, que de savoir quel morceau de surface donner aux algorithmes de reconnaissance. Une option consiste à utiliser un algorithme de type _plane-probing_ qui décide à la volée où travailler pour faire croître un morceau de plan ajusté à la surface par construction (voir Fig. [pattern] et [#LPR19,#LPR17,#LPR16b,#LPR16a]). ![ Figure [pattern]: Morceau de plan discret sur une surface digitale et sa normale estimée comme étant la normale du triangle calculé. ](pattern.gif width="300px") Un premier objectif consiste à étudier, à la fois expérimentalement et théoriquement, la localité des algorithmes précédents : est-ce qu'on peut prédire l'éloignement maximal au point de départ ? quel est le plus petit morceau de plan sur lequel l'algorithme retourne exactement la normale du plan ? etc. De par la nature des algorithmes, ces questions relèvent à la fois de l'arithmétique (transformations unimodulaires, réduction de bases dans un réseau de points) et de la géométrie algorithmique (critère de Delaunay). Un autre objectif consiste à éprouver, à la fois expérimentalement et théoriquement, la capacité de ses algorithmes à produire des résultats qui représente au mieux la géométrie de la surface digitale sous-jacente : est-ce qu'il est toujours possible de recouvrir toute la surface en lançant les algorithmes précédents de partout ? pour une surface convexe, retrouve-t-on les facettes de son enveloppe convexe ? pour une surface quelconque, peut-on construire un maillage plus compact mais tout aussi représentatif ? etc. Pour cette dernière question, l'implémentation pourra être faite en C++ et, dans ce cas, donner lieu à une contribution dans la bibliothèque [DGtal](https://dgtal.org/). Références ================================================================================ [#LPR19]: T. Roussillon, J.-O. Lachaud. [Digital Plane Recognition with Fewer Probes](https://hal.archives-ouvertes.fr/hal-02087529). 21st IAPR International Conference on Discrete Geometry for Computer Imagery, Mar 2019. [#LPR17]: J.-O. Lachaud, X. Provençal, T. Roussillon. [Two Plane-Probing Algorithms for the Computation of the Normal Vector to a Digital Plane](https://hal.archives-ouvertes.fr/hal-01621516). Journal of Mathematical Imaging and Vision, Vol. 59, No. 1, p.23 – 39, Sep 2017. [#LPR16b]: J.-O. Lachaud, X. Provençal, T. Roussillon. [Computation of the normal vector to a digital plane by sampling signicant points](https://hal.archives-ouvertes.fr/hal-01621492). 19th IAPR International Conference on Discrete Geometry for Computer Imagery, Apr 2016. [#LPR16a]: J.-O. Lachaud, X. Provençal, T. Roussillon. [An output-sensitive algorithm to compute the normal vector of a digital plane](https://hal.archives-ouvertes.fr/hal-01294966). Journal of Theoretical Computer Science Vol. 624, p.73–88, Apr 2016. [^syntax]: Données de neige acquises par 3SR Lab et CEN/CNRM - GAME URA 1357/Météo-France - CNRS, [projet DigitalSnow](https://projet.liris.cnrs.fr/dsnow/), merci à David Coeurjolly pour les images.