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 Année de publication : 2020 Projets : IQmulus / Métral, Claudine Conférence : ISPRS 2020, Commission 2, virtual Congress, Imaging today foreseeing tomorrow 31/08/2020 02/09/2020 Nice (en ligne) France Annals Commission 2 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, Sciences de l'information et de la communication : Paris-Est : 2020 Organisme de stage : LaSTIG (IGN) nature-HAL : Thèse DOI : sans 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 Année de publication : 2019 Projets : 1-Pas de projet / Conférence : ISPRS Geospatial Week 2019 10/06/2019 14/06/2019 Enschede Pays-Bas Open access Annals 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 Editeur : New-York : IEEE Computer society Année de publication : 2019 Projets : 1-Pas de projet / Conférence : Big Data 2019, IEEE International Conference on Big Data 09/12/2019 12/12/2019 Los Angeles Californie - Etats-Unis Proceedings IEEE 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

Markov random field for combined defogging and stereo reconstruction / Laurent Caraffa (2018)

Public Titre : Markov random field for combined defogging and stereo reconstruction Type de document : Article/Communication Auteurs : Laurent Caraffa , Auteur ; Jean-Philippe Tarel, Auteur Editeur : Philadelphie : Society for Industrial and Applied Mathematics SIAM Année de publication : 2018 Conférence : IS 2018, SIAM conference on imaging science 05/06/2018 08/06/2018 Bologne Italie Open Access Abstracts Langues : Anglais (eng) Descripteur : [Vedettes matières IGN] Traitement d'image [Termes descripteurs IGN] brouillard [Termes descripteurs IGN] champ aléatoire de Markov [Termes descripteurs IGN] reconstruction d'image Résumé : (auteur) Stereo reconstruction serves many outdoor applications, and thus sometimes faces difficulties with foggy weather. However, fog provides depth cues for far away objects. By taking advantages of both stereo and fog cues, stereo reconstruction in fog can be improved. We propose a Markov Random Field modelfor this problem. The proposed model is tested on synthetic images and it shows that improved results can be achieved on both stereo reconstruction and visibility restoration. Numéro de notice : C2018-098 Affiliation des auteurs : LaSTIG MATIS+Ext (2012-2019) Thématique : IMAGERIE/INFORMATIQUE Nature : Communication nature-HAL : ComSansActesPubliés-Unpublished DOI : sans Permalink : https://documentation.ensg.eu/index.php?lvl=notice_display&id=96508

Optimisation de formes en sciences de l'ingénieur : Méthodes et applications, ch. 5. Optimisation de fonction pseudo-booléennes / Laurent Caraffa (2018)  

Permalink

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

Permalink

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