Vous êtes ici : Accueil » Kiosque » Annonce

Identification

Identifiant: 
Mot de passe : 

Mot de passe oublié ?
Détails d'identification oubliés ?

Annonce

16 mai 2019

Reconstruction de surface étanche nD à large échelle avec Spark/Hadoop


Catégorie : Doctorant


Reconstruction de surface étanche nD à large échelle avec Spark/Hadoop

Avec l'augmentation croissante des volumes des nuages de points produits par des acquisitions Lidar ou par corrélation dense d'images, la problématique du passage à l'échelle des différents algorithmes / traitement de ces données est devenue incontournable. C'est dans ce cadre que le développement à l'IGN d'un algorithme de reconstruction de surface étanche, passant à l'échelle sur une plateforme Spark/Hadoop.

Le passage à l'échelle de la reconstruction de surface est un enjeu crucial dans le domaine de l'information géographique où d'une part la représentation de la géométrie des scènes historiquement en 2.5D (MNE/MNT) est progressivement remplacée par une représentation sous forme d'un maillage en vraie 3D permettant d'intégrer des données aériennes obliques et des données acquises au sol, et d'autre part les volumes de données d'observation deviennent gigantesques au fur et à mesure que la résolution augmente. Ces maillages peuvent ensuite servir de nombreuses applications de la simulation à la visualisation en passant par la reconstruction de modèles structurés de villes.

Le sujet de thèse proposé s'attaque à ces verrous sur trois axes :

- La parallélisation/distribution des calculs sera étudiée pour chacune des étapes de l'algorithme de façon à préserver les garanties de la méthode non distribuée.

- Adapter des méthodes d'apprentissage sur des données 3D à large echelle.

- Généralisation du problème en dimension quelconque.

Profil attendu : Titulaire d’un Master 2 ou d’un diplôme d’ingénieur en informatique : géométrie algorithmique, apprentissage, optimisation, Big Data. Bonne maitrise de la programmation C++ et de l'anglais scientifique.

 

Reconstruction de surface étanche nD à large échelle avec Spark/Hadoop

IGN - UMR LaSTIG - Equipe ACTE
73 avenue de Paris 94165 Saint Mandé

 

Contexte

Avec l'augmentation croissante des volumes des nuages de points produits par des acquisitions Lidar ou par corrélation dense d'images, la problématique du passage à l'échelle des différents algorithmes / traitement de ces données est devenue incontournable. Par exemple, l'IGN coordonne la constitution du jeu de données PANAME comprenant notemment 20Go de Lidar aérien ( milliards de points) et 2,5To de Lidar terrestre (80 jours d'acquisition, milliards de points) sur la ville de Paris, ainsi qu'un volume encore beaucoup plus important d'images aériennes et terrestres sur la même zone permettant de produire des volumes encore supérieurs par photogrammétrie.

D'autre part, la communauté scientifique propose des benchmarks de traitement de nuages de points (sémantisation, segmentation, reconstruction) sur des nuages de points de plus en plus volumineux tels que Semantic3D [1] et S3DIS [2] pour la sémantisation et TankAndtemple[3] pour la reconstruction 3D. La réponse à ces enjeux scientifiques nécessite de développer des méthodes dédiés et de proposer des structures de données adaptées, et/ou de repenser des méthodes et structures de données existantes de façon à les adapter à des architectures distribuées.

Si cette démarche peut être relativement facile sur des traitements très locaux comme certains filtrages, d'autres, comme la reconstruction de surface étanche, impliquent un critère global qui rend cette démarche beaucoup plus complexe, en particulier si l'on veut garantir que certaines propriétés de la méthode simple soient préservées sur la méthode distribuée. Par exemple l'étanchéité de la surface reconstruite dans le cas de la reconstruction est une propriété très importante (pour la simulation et dans une moindre mesure la visualisation). Plus généralement, de nombreuses méthodes de traitement des nuages de points s'appuyent sur une optimisation pour lesquelles il est difficile de garantir que la version répartie préservera l'optimalité de la solution produite.

C'est dans ce cadre que le développement à l'IGN d'un algorithme de reconstruction de surface étanche, passant à l'échelle sur une plateforme Spark/Hadoop a été développé fondé sur [4] . Cet algortithme se décompose en 5 étapes:

 

Si le problème de la distribution de la triangulation de Delaunay a été résolu avec succès, certaines étapes comme la coupe de graphe (qui est un problème d'optimisation global) sont approximées localement et ne permettent donc pas de garantir une optimalité globale une fois distibuées. D'autre part, la gestion de la dimention temporelle des nuages traités n'est pas prise en compte. Les nuages de points présentent souvent une redondance (recouvrements) d'information acquises à des instants différents. Enfin, la méthode est difficile à paramétrer et l'adaptation de ce paramétrage à la typologie de la scène est difficile, problème encore renforcé sur des grands volumes de données couvrant des zones très vastes et donc souvent hétérogènes.

Le passage à l'échelle de la reconstruction de surface est un enjeu crucial dans le domaine de l'information géographique où d'une part la représentation de la géométrie des scènes historiquement en 2.5D (MNE/MNT) est progressivement remplacée par une représentation sous forme d'un maillage en vraie 3D permettant d'intégrer des données aériennes obliques et des données acquises au sol, et d'autre part les volumes de données d'observation deviennent gigantesques au fur et à mesure que la résolution augmente. Ces maillages peuvent ensuite servir de nombreuses applications de la simulation à la visualisation en passant par la reconstruction de modèles structurés de villes.

 

Objectifs et programme de travail

Le sujet de thèse proposé s'attaque à ces verrous sur trois axes.

 

Parallélisation

La parallélisation/distribution des calculs sera étudiée pour chacune des étapes de l'algorithme de façon à préserver les garanties de la méthode non distribuée. Cette distribution pourra s'appuyer sur des bibliothèques existantes telles que GraphX (déjà utilisé à l'IGN). Plus généralement, nous chercherons à utiliser le paradigme Map/Reduce particulièrement bien adapté à la distibution des traitements qui nous intéressent, enutilisant la technologies Spark/hadoop avec stockage HDFS, car elle permet de répartir les données sur une grille de calcul et de distribuer les traitements intelligemment sur les noeuds disponibles.

La thèse tirera profit du partenariat entre l'IGN et l’ISC-PIF (l’Institut des systèmes complexe d’île de France) qui dispose d’une plateforme Spark/Hadoop. La thèse proposée permettra donc de renforcer l'interaction entre l'équipe ACTE et plus généralement l'UMR LaSTIG et l'ISC-PIF, mais aussi d'approfondir une problématique de recherche encore très peu explorée. La thèse permettra aussi de valoriser le jeu de données PANAME puisque l'un de ses objectifs ambitieux est de produire une surface étanche à partir de ces données extrèmement massives.

Actuellement, Laurent Caraffa travaille avec Maziyar Panahi, administrateur des systèmes informatiques, réseaux et télécommunications de l'ISC-PIF, afin d'intégrer les algorithmes courants de triangulation et de reconstruction de surface à la plateforme Multivac de l'ISC-PIF. Le doctorant devra donc, dans un premier temps, prendre en main cette plateforme et les technologies associées.

 


Apprentissage et sémantique

Pour chacune des étapes mentionnées ci dessus, le doctorant évaluera l'utilisation de méthodes modernes d'apprentissage afin d'ajuster automatiquement (et possiblement localement) le paramétrage de la méthode initiale afin de l'adapter à la typologie/sémantique de la scène reconstruite. La disponibilité de benchmarks de reconstruction nous permettra de nous appuyer sur une vérité terrain précieuse pour la supervision de cet apprentissage.

Les méthodes développées actuellement en reconstruction de surfaces 3D sont fondées sur des a-priori simples tel que chercher une surface minimum. Ces a-priori, comme la surface minimum ne fonctionnent correctement que dans certains cas (surfaces très régulières comme le sol naturel ou les routes). Cependant, certains objets complexes nécessitent plus de connaissances. Les méthodes proposant des a-priori plus complexes existent déjà, cependant, comme l'explique [6], l'optimisation de fonctions pseudo booléennes associée introduit une grande complexité lors de l'optimisation, ce qui est un verrou majeur au passage à l'échelle.

Ces dernières années ont montré que grâce aux approches Deep learning, il est possible de proposer des modèles complexes mais aussi d'inférer efficacement une solution grâce notamment aux avancées significatives des méthodes d'optimisation avec l'implantation sur GPU. Ces méthodes, principalement développées pour les images ces dernières années, sont maintenant utilisées en reconstruction 3D. Certes sur des petites scènes, mais compte tenu de l'engouement suscité par ces méthodes, il est fortement probable qu'elles deviennent fonctionnelles à grande échelle. Parallèlement à cela, les très bons résultats obtenus par Loïc Landrieu[7] sur la segmentation sémantique de points par Deep Learling ont poussé l'équipe à accentuer les recherches sur cet axe. Un facteur limitant actuellement est le surcoût dû à la lecture des donnés pour l'apprentissage supervisé. L'utilisation de l'architecture HDFS ainsi que les recentes APIs développées en Spark pour l'apprentissage profond comme BigDL[8] sont une perspective intéressante à explorer.

 


Généralisation en dimension quelconque

Pour la prise en compte du temps, la reconstruction d'une hyper surface en 4D est une possibilité très intéressante à explorer. L'ensemble des étapes du calcul out-of-core de la triangulation de Delaunay ou de la distribution sur le Cloud est généralisable en dimension quelconque. L'ensemble des perspectives telle qu'une reconstruction 3D + temps, 3D + échelle est donc maintenant fortement envisageable. Ceci est d'autant plus envisageable que l'algorithme passe à l'échelle. Un tuilage dans l'espace temps étant indispensable pour espérer pouvoir traiter des scènes conséquentes du fait de la prise en compte des dimensions supplémentaires. Nous disposons donc actuellement d'un cadre de développement optimal pour poursuivre les recherches dans cette direction.

 

Environnement technique

C++, CGAL, Meshlab, Linux, Spark/Hadoop.

 

Profil attendu

Titulaire d’un Master 2 ou d’un diplôme d’ingénieur en informatique : géométrie algorithmique, apprentissage, optimisation, Big Data. Bonne maitrise de la programmation C++ et de l'anglais scientifique.

 

Direction/encadrement

Directeur de thèse: Bruno VALLET bruno.vallet@ign.fr
Encadrant IGN: Laurent CARAFFA laurent.caraffa@ign.fr

 

Contrat doctoral

Le contrat doctoral d’une durée de trois ans (à partir de septembre/octobre 2019) ouvre droit à une rémunération d’environ 1680 euros brut (hors contribution aux frais de transports). Le contrat doctoral peut inclure pour l’ensemble de la durée de la thèse un service complémentaire d’enseignement, de diffusion de l’information scientifique et technique, de valorisation ou d’expertise.

 

Candidature

Les candidatures sont à envoyer par mail aux contacts ci-dessus et doivent inclure :

  1. un CV ;
  2. une lettre de motivation adaptée au sujet proposé ;
  3. un relevé de notes des dernières années d’étude ;
  4. l’avis du directeur de master (ou de la personne responsable du diplôme donnant l’équivalence du master) ;
  5. le cas échéant des lettres de recommandations.

 

Bibliographie

 

1
T. Hackel, N. Savinov, L. Ladicky, J. D. Wegner, K. Schindler, and M. Pollefeys, ``SEMANTIC3D.NET: A new large-scale point cloud classification benchmark,'' in ISPRS Annals of the Photogrammetry, Remote Sensing and Spatial Information Sciences, vol. IV-1-W1, pp. 91-98, 2017.

 

2
I. Armeni, A. Sax, A. R. Zamir, and S. Savarese, ``Joint 2D-3D-Semantic Data for Indoor Scene Understanding,'' ArXiv e-prints, Feb. 2017.

 

3
A. Knapitsch, J. Park, Q.-Y. Zhou, and V. Koltun, ``Tanks and temples: Benchmarking large-scale scene reconstruction,'' ACM Transactions on Graphics, vol. 36, no. 4, 2017.

 

4
L. Caraffa, M. Brédif, and B. Vallet, ``3d watertight mesh generation with uncertainties from ubiquitous data,'' 2016.
Available at http://lcaraffa.net/blog/posts/article-2016ACCV-wasure.html.

 

5
J. Demantké, C. Mallet, N. David, and B. Vallet, ``Dimensionality based scale selection in 3d lidar point cloud,'' International Archives of Photogrammetry, Remote Sensing and Spatial Information Sciences (IAPRS), Laserscanning. Calgary, Canada, August, 2011.

 

6
E. Boros and P. L. Hammer, ``Pseudo-boolean optimization,'' Discrete Appl. Math., vol. 123, pp. 155-225, Nov. 2002.

 

7
L. Landrieu and M. Simonovsky, ``Large-scale point cloud semantic segmentation with superpoint graphs,'' CoRR, vol. abs/1711.09869, 2017.

 

8
J. Dai, Y. Wang, X. Qiu, D. Ding, Y. Zhang, Y. Wang, X. Jia, C. Zhang, Y. Wan, Z. Li, J. Wang, S. Huang, Z. Wu, Y. Wang, Y. Yang, B. She, D. Shi, Q. Lu, K. Huang, and G. Song, ``Bigdl: A distributed deep learning framework for big data,'' CoRR, vol. abs/1804.05839, 2018.

 

Dans cette rubrique

(c) GdR 720 ISIS - CNRS - 2011-2019.