Centre dedocumentation
scientifique

Provably consistent distributed Delaunay triangulation / Mathieu Brédif in ISPRS Annals of the Photogrammetry, Remote Sensing and Spatial Information Sciences, V-2 (August 2020)  

Public [article]  inISPRS Annals of the Photogrammetry, Remote Sensing and Spatial Information Sciences > V-2 (August 2020) . - pp 195 - 202 Titre : Provably consistent distributed Delaunay triangulation Type de document : Article/Communication Auteurs : Mathieu Brédif , Auteur ; Laurent Caraffa , Auteur ; Murat Yirci, Auteur ; Pooran Memari, Auteur Congrès : Congrès: ISPRS 2020, virtual Congress Imaging today foreseeing tomorrow (31 aout - 2 septembre 2020; Nice, France) , Commanditaire Année de publication : 2020 Projets : IQmulus / Brédif, Mathieu Article en page(s) : pp 195 - 202 Note générale : bibliographie Langues : Anglais (eng) Descripteur : [Vedettes matières IGN] Lasergrammétrie [Termes descripteurs IGN] données lidar [Termes descripteurs IGN] données localisées 3D [Termes descripteurs IGN] géomètrie algorithmique [Termes descripteurs IGN] informatique en nuage [Termes descripteurs IGN] semis de points [Termes descripteurs IGN] Spark [Termes descripteurs IGN] traitement de nuage de points [Termes descripteurs IGN] triangulation de Delaunay Résumé : (Auteur) This paper deals with the distributed computation of Delaunay triangulations of massive point sets, mainly motivated by the needs of a scalable out-of-core surface reconstruction workflow from massive urban LIDAR datasets. Such a data often corresponds to a huge point cloud represented through a set of tiles of relatively homogeneous point sizes. This will be the input of our algorithm which will naturally partition this data across multiple processing elements. The distributed computation and communication between processing elements is orchestrated efficiently through an uncentralized model to represent, manage and locally construct the triangulation corresponding to each tile. Initially inspired by the star splaying approach, we review the Tile\& Merge algorithm for computing Distributed Delaunay Triangulations on the cloud, provide a theoretical proof of correctness of this algorithm, and analyse the performance of our Spark implementation in terms of speedup and strong scaling in both synthetic and real use case datasets. A HPC implementation (e.g. using MPI), left for future work, would benefit from its more efficient message passing paradigm but lose the robustness and failure resilience of our Spark approach. Numéro de notice : A2020-410 Affiliation des auteurs : LaSTIG+Ext (2020- ) Autre URL associée : vers HAL Thématique : IMAGERIE/INFORMATIQUE Nature : Article nature-HAL : ArtAvecCL-RevueIntern DOI : 10.5194/isprs-annals-V-2-2020-195-2020 date de publication en ligne : 03/08/2020 En ligne : https://doi.org/10.5194/isprs-annals-V-2-2020-195-2020 Format de la ressource électronique : URL article Permalink : https://documentation.ensg.eu/index.php?lvl=notice_display&id=94979 [article]

Simplicial complexes reconstruction and generalisation of 3d lidar data in urban scenes / Stéphane Guinard (2020)  

Public Titre : Simplicial complexes reconstruction and generalisation of 3d lidar data in urban scenes Titre original : Reconstruction et généralisation de complexes simpliciaux à partir de scans lidar de scènes urbaines Type de document : Thèse/HDR Auteurs : Stéphane Guinard , Auteur ; Bruno Vallet , Directeur de thèse ; Laurent Caraffa , Encadrant Editeur : Champs/Marne : Université Paris-Est Année de publication : 2020 Note générale : bibliographie École doctorale Mathématiques, Sciences et Technologies de l'Information et de la Communication Langues : Anglais (eng) Descripteur : [Vedettes matières IGN] Lasergrammétrie [Termes descripteurs IGN] classification basée sur les régions [Termes descripteurs IGN] complexe simplicial [Termes descripteurs IGN] données lidar [Termes descripteurs IGN] données localisées 3D [Termes descripteurs IGN] optimisation (mathématiques) [Termes descripteurs IGN] reconstruction d'objet [Termes descripteurs IGN] scène urbaine [Termes descripteurs IGN] segmentation [Termes descripteurs IGN] semis de points [Termes descripteurs IGN] simplification de maillage Index. décimale : THESE Thèses et HDR Résumé : (auteur) Grâce à leur résolution et à leur accessibilité toujours meilleures, les capteurs LiDAR sont de plus en plus utilisés pour cartographier les villes. En effet, ces capteurs sont capables de réaliser efficacement des acquisitions à haut résolution, qui peuvent ensuite être utilisées pour produire des reconstructions géométriquement détaillées de scènes complexes. Cependant, une telle reconstruction nécessite d’organiser les données avec une structure de données adaptée, comme des nuages de points ou des maillages. Les nuages de points fournissent une représentation compacte des données, mais leur nature discrète empêche certaines applications telles que la visualisation ou la simulation. Les maillages permettent une représentation continue des surfaces, mais ne sont pas bien adaptés à la représentation d’objets complexes, dont le niveau de détail peut dépasser la résolution de l’acquisition. Pour remédier à ces limitations, nous proposons de reconstruire une géométrie continue uniquement lorsque suffisamment d’informations géométriques sont disponibles. Cela nous amène à créer une reconstruction mêlant triangles, arêtes et points. Nous appelons une telle collection d’objets un complexe simplicial. Dans cette thèse, nous étudions la création de modèles 3D de scènes urbaines géométriquement détaillés, basés sur des complexes simpliciaux. Nous montrons que les complexes simpliciaux sont une alternative appropriée aux maillages. En effet, ils sont rapides à calculer et peuvent être simplifiés tout en conservant une grande fidélité géométrique par rapport aux données d’entrée. Nous soutenons que les complexes simples transmettent de précieuses informations géométriques qui peuvent à leur tour être utilisées pour la sémantisation des nuages de points 3D. Nous pensons également qu’ils peuvent servir de base pour des reconstructions multi-échelles de scènes urbaines. Nous présentons d’abord un algorithme efficace pour le calcul de complexes simpliciaux à partir d’acquisitions LiDAR de scènes urbaines. Comme les complexes simpliciaux reconstruits peuvent être très lourds, ils peuvent être difficiles à traiter sur un ordinateur standard. Pour relever ce défi, nous étudions différentes approches pour les généraliser spatialement, en approximant de grandes zones géométriquement simples par des primitives simples. À cette fin, nous proposons un nouvel algorithme pour calculer des approximations planaires par morceaux de nuages de points 3D, basé sur une approche d’optimisation globale. Ensuite, nous proposons deux applications différentes des complexes simpliciaux. La première est une méthode de polygonalisation améliorant la création de modèles 3D légers mais géométriquement précis. La seconde est une méthode de classification faiblement supervisée utilisant des descripteurs 3D locaux et globaux. Numéro de notice : 17613 Affiliation des auteurs : LaSTIG (2020- ) Thématique : IMAGERIE Nature : Thèse française Note de thèse : thèse : Géographie : Paris-Est : 2020 Organisme de stage : LaSTIG (IGN) nature-HAL : Thèse date de publication en ligne : 30/09/2020 En ligne : https://tel.archives-ouvertes.fr/tel-02953672/document Format de la ressource électronique : URL Permalink : https://documentation.ensg.eu/index.php?lvl=notice_display&id=95943

Piecewise-planar approximation of large 3D data as graph-structured optimization / Stéphane Guinard in ISPRS Annals of the Photogrammetry, Remote Sensing and Spatial Information Sciences, IV-2/W5 (May 2019)  

Public [article]  inISPRS Annals of the Photogrammetry, Remote Sensing and Spatial Information Sciences > IV-2/W5 (May 2019) . - pp 365 - 372 Titre : Piecewise-planar approximation of large 3D data as graph-structured optimization Type de document : Article/Communication Auteurs : Stéphane Guinard , Auteur ; Loïc Landrieu , Auteur ; Laurent Caraffa , Auteur ; Bruno Vallet , Auteur Congrès : ISPRS Geospatial Week 2019 (10 - 14 juin 2019; Enschede, Pays-Bas), Commanditaire Année de publication : 2019 Projets : 1-Pas de projet / Article en page(s) : pp 365 - 372 Note générale : bibliographie The authors would like to acknowledge the DGA for their financial support of this work. Langues : Anglais (eng) Descripteur : [Vedettes matières IGN] Lasergrammétrie [Termes descripteurs IGN] algorithme de décalage moyen [Termes descripteurs IGN] analyse de groupement [Termes descripteurs IGN] approximation [Termes descripteurs IGN] données lidar [Termes descripteurs IGN] données localisées 3D [Termes descripteurs IGN] érosion anthropique [Termes descripteurs IGN] erreur d'approximation [Termes descripteurs IGN] extraction de traits caractéristiques [Termes descripteurs IGN] graphe [Termes descripteurs IGN] maillage [Termes descripteurs IGN] Ransac (algorithme) [Termes descripteurs IGN] semis de points [Termes descripteurs IGN] surface plane Résumé : (auteur) We introduce a new method for the piecewise-planar approximation of 3D data, including point clouds and meshes. Our method is designed to operate on large datasets (e.g. millions of vertices) containing planar structures, which are very frequent in anthropic scenes. Our approach is also adaptive to the local geometric complexity of the input data. Our main contribution is the formulation of the piecewise-planar approximation problem as a non-convex optimization problem. In turn, this problem can be efficiently solved with a graph-structured working set approach. We compare our results with a state-of-the-art region-growing-based segmentation method and show a significant improvement both in terms of approximation error and computation efficiency. Numéro de notice : A2019-592 Affiliation des auteurs : LaSTIG (2020- ) Thématique : IMAGERIE Nature : Article nature-HAL : ArtAvecCL-RevueIntern DOI : 10.5194/isprs-annals-IV-2-W5-365-2019 date de publication en ligne : 29/05/2019 En ligne : https://doi.org/10.5194/isprs-annals-IV-2-W5-365-2019 Format de la ressource électronique : URL article Permalink : https://documentation.ensg.eu/index.php?lvl=notice_display&id=94552 [article]

Tile & merge: Distributed Delaunay triangulations for cloud computing / Laurent Caraffa (2019)  

Public Titre : Tile & merge: Distributed Delaunay triangulations for cloud computing Type de document : Article/Communication Auteurs : Laurent Caraffa , Auteur ; Pooran Memari, Auteur ; Murat Yirci, Auteur ; Mathieu Brédif , Auteur Congrès : Big Data 2019, IEEE International Conference on Big Data (9 - 12 décembre 2019; Los Angeles, Californie - Etats-Unis) , Commanditaire Editeur : New-York : IEEE Computer society Année de publication : 2019 Projets : 1-Pas de projet / Importance : 7 p. Format : 21 x 30 cm Note générale : bibliographie Langues : Anglais (eng) Descripteur : [Vedettes matières IGN] Traitement d'image [Termes descripteurs IGN] géomètrie algorithmique [Termes descripteurs IGN] informatique en nuage [Termes descripteurs IGN] jeu de données [Termes descripteurs IGN] mémoire d'ordinateur [Termes descripteurs IGN] reconstruction d'objet [Termes descripteurs IGN] semis de points [Termes descripteurs IGN] Spark [Termes descripteurs IGN] triangulation de Delaunay Résumé : (auteur) Motivated by the needs of a scalable out-of-core surface reconstruction algorithm available on the cloud, this paper addresses the computation of distributed Delaunay triangulations of massive point sets. The proposed algorithm takes as input a point cloud and first partitions it across multiple processing elements into tiles of relatively homogeneous point sizes. The distributed computation and communication between processing elements is orchestrated so that each one discovers the Delaunay neighbors of its input points within the theoretical overall Delaunay triangulation of all points and computes locally a partial view of this triangulation. This approach prevents memory limitations by never materializing the global triangulation. This efficiency is due to our proposed uncentralized model to represent, manage and locally construct the triangulation corresponding to each tile. The point set is first partitioned into non-overlapping tiles, then we construct within each tile the Delaunay triangulation of the local points and a minimal set of replicated foreign points in order to capture the simplices spanning multiple tiles. Inspired by the star splaying approach for Delaunay triangulation computation/repair, communication is limited to exchanging points of potential Delaunay neighbors across tiles. Therefore, our method is guaranteed to reconstruct, within each tile, a triangulation that contains the star of its local points, as though it were computed within the Delaunay triangulation of all points. The proposed algorithm is implemented with Spark for the scheduling and C++ for the geometric computations. This allows both an optimal scheduling on multiple machines and efficient low-level computation. The results show the efficiency of our algorithm in terms of speedup and strong scaling on a classical Spark configuration with both synthetic and real use case datasets. Numéro de notice : C2019-033 Affiliation des auteurs : LaSTIG MATIS+Ext (2012-2019) Autre URL associée : vers HAL Thématique : IMAGERIE/INFORMATIQUE/MATHEMATIQUE Nature : Communication nature-HAL : ComAvecCL&ActesPubliésIntl DOI : 10.1109/BigData47090.2019.9006534 date de publication en ligne : 24/02/2020 En ligne : https://doi.org/10.1109/BigData47090.2019.9006534 Format de la ressource électronique : URL Permalink : https://documentation.ensg.eu/index.php?lvl=notice_display&id=95318

3D watertight mesh generation with uncertainties from ubiquitous data / Laurent Caraffa (2016)  

Public Titre : 3D watertight mesh generation with uncertainties from ubiquitous data Type de document : Article/Communication Auteurs : Laurent Caraffa , Auteur ; Mathieu Brédif , Auteur ; Bruno Vallet , Auteur Congrès : ACCV 2016, 13th Asian Conference on Computer Vision (20 - 24 novembre 2016; Taipei, Taiwan), Commanditaire Editeur : Berlin, Heidelberg, Vienne, New York, ... : Springer Année de publication : 2016 Collection : Lecture notes in Computer Science, ISSN 0302-9743 num. 10114 Projets : IQmulus / Brédif, Mathieu Importance : pp 377 - 391 Note générale : bibliographie Langues : Anglais (eng) Descripteur : [Vedettes matières IGN] Applications photogrammétriques [Termes descripteurs IGN] algorithme Graph-Cut [Termes descripteurs IGN] carte de confiance [Termes descripteurs IGN] distance de Hausdorff [Termes descripteurs IGN] incertitude géométrique [Termes descripteurs IGN] maille triangulaire [Termes descripteurs IGN] reconstruction d'objet [Termes descripteurs IGN] seuillage [Termes descripteurs IGN] surface imperméable [Termes descripteurs IGN] théorie de Dempster-Shafer Résumé : (auteur) In this paper, we propose a generic framework for watertight mesh generation with uncertainties that provides a confidence measure on each reconstructed mesh triangle. Its input is a set of vision-based or Lidar-based 3D measurements which are converted to a set of mass functions that characterize the level of confidence on the occupancy of the scene as occupied, empty or unknown based on Dempster-Shafer Theory. The output is a multi-label segmentation of the ambient 3D space expressing the confidence for each resulting volume element to be occupied or empty. While existing methods either sacrifice watertightness (local methods) or need to introduce a smoothness prior (global methods), we derive a per-triangle confidence measure that is able to gradually characterize when the resulting surface patches are certain due to dense and coherent measurements and when these patches are more uncertain and are mainly present to ensure smoothness and/or watertightness. The surface mesh reconstruction is formulated as a global energy minimization problem efficiently optimized with the α-expansion algorithm. We claim that the resulting confidence measure is a good estimate of the local lack of sufficiently dense and coherent input measurements, which would be a valuable input for the next-best-view scheduling of a complementary acquisition. Beside the new formulation, the proposed approach achieves state-of-the-art results on surface reconstruction benchmark. It is robust to noise, manages high scale disparity and produces a watertight surface with a small Hausdorff distance in uncertainty area thanks to the multi-label formulation. By simply thresholding the result, the method shows a good reconstruction quality compared to local algorithms on high density data. This is demonstrated on a large scale reconstruction combining real-world datasets from airborne and terrestrial Lidar and on an indoor scene reconstructed from images. Numéro de notice : C2016-024 Affiliation des auteurs : IGN (2012-2019) Thématique : IMAGERIE Nature : Communication nature-HAL : ComAvecCL&ActesPubliésIntl DOI : 10.1007/978-3-319-54190-7_23 date de publication en ligne : 12/03/2017 En ligne : http://doi.org/10.1007/978-3-319-54190-7_23 Format de la ressource électronique : URL article Permalink : https://documentation.ensg.eu/index.php?lvl=notice_display&id=84627

3D octree based watertight mesh generation from ubiquitous data / Laurent Caraffa (2015)  

Permalink

Extending α-expansion to a larger set of regularization functions / Mathias Paget (2015)  

Permalink