Centre de documentation
scientifique

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

Public [article]  inISPRS Annals of the Photogrammetry, Remote Sensing and Spatial Information Sciences > vol V-2-2020 (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 IGN] données lidar [Termes IGN] données localisées 3D [Termes IGN] géomètrie algorithmique [Termes IGN] informatique en nuage [Termes IGN] semis de points [Termes IGN] Spark [Termes IGN] traitement de semis de points [Termes 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 : UGE-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]

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 / Métral, Claudine 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 IGN] géomètrie algorithmique [Termes IGN] informatique en nuage [Termes IGN] jeu de données [Termes IGN] mémoire d'ordinateur [Termes IGN] reconstruction d'objet [Termes IGN] semis de points [Termes IGN] Spark [Termes 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

Arrangements 2D pour la cartographie de l’espace public et des transports / Murat Yirci (2016)  

Public Titre : Arrangements 2D pour la cartographie de l’espace public et des transports Type de document : Thèse/HDR Auteurs : Murat Yirci, Auteur ; Nicolas Paparoditis , Directeur de thèse ; Mathieu Brédif , Encadrant Editeur : Champs/Marne : Université Paris-Est Marne-la-Vallée UPEM Année de publication : 2016 Importance : 209 p. Format : 21 x 30 cm Note générale : bibliographie Thèse présentée pour obtenir le grade de docteur de Université Paris-Est, École Doctorale MSTIC Sciences et Technologies de l’Information Géographique, 2016 Langues : Anglais (eng) Descripteur : [Vedettes matières IGN] Applications SIG [Termes IGN] accessibilité [Termes IGN] algorithme génétique [Termes IGN] calcul d'itinéraire [Termes IGN] classification ascendante hiérarchique [Termes IGN] courbe de Bézier [Termes IGN] diagramme de Voronoï [Termes IGN] graphe [Termes IGN] modèle conceptuel de données localisées [Termes IGN] modélisation 3D [Termes IGN] navigation pédestre [Termes IGN] objet géographique [Termes IGN] partition des données [Termes IGN] piéton [Termes IGN] primitive géométrique [Termes IGN] SIG 2D [Termes IGN] triangulation de Delaunay Index. décimale : THESE Thèses et HDR Résumé : (auteur) Cette thèse porte sur le développement facilité d’applications de cartographie et de transport, plus particulièrement sur la génération de réseaux piétonniers pour des applications telles que la navigation, le calcul d’itinéraires, l’analyse d’accessibilité et l’urbanisme. Afin d’atteindre ce but, nous proposons un modèle de données à deux couches qui cartographie l’espace public dans une hiérarchie d’objets géospatiaux sémantisés. A bas niveau, la géométrie 2D des objets géospatiaux est représentée par une partition planaire, modélisée par une structure topologique d’arrangement 2D. Cette représentation permet des traitements géométriques efficaces et efficients, ainsi qu’une maintenance et une validation aisée au fur et à mesure des éditions lorsque la géométrie ou la topologie d’un objet sont modifiées. A haut niveau, les aspects sémantiques et thématiques des objets géospatiaux sont modélisés et gérés. La hiérarchie entre ces objets est maintenue à travers un graphe dirigé acyclique dans lequel les feuilles correspondent à des primitives géométriques de l’arrangement 2D et les noeuds de plus haut niveau représentent les objets géospatiaux sémantiques plus ou moins agrégés. Nous avons intégré le modèle de données proposé dans un framework SIG nommé StreetMaker en complément d’un ensemble d’algorithmes génériques et de capacités SIG basiques. Ce framework est alors assez riche pour générer automatiquement des graphes de réseau piétonnier. En effet, dans le cadre d’un projet d’analyse d’accessibilité, le flux de traitement proposé a permis de produire avec succès sur deux sites un graphe de réseau piétonnier à partir de données en entrées variées : des cartes vectorielles existantes, des données vectorielles créées semi-automatiquement et des objets vectoriels extraits d’un nuage de points lidar issu d’une acquisition de cartographie mobile. Alors que la modélisation 2D de la surface du sol est suffisante pour les applications SIG 2D, les applications SIG 3D nécessitent des modèles 3D de l’environnement. La modélisation 3D est un sujet très large mais, dans un premier pas vers cette modélisation 3D, nous nous sommes concentrés sur la modélisation semi-automatique d’objets de type cylindre généralisé (tels que les poteaux, les lampadaires, les troncs d’arbre, etc) à partir d’une seule image. Les méthodes et techniques développées sont présentées et discutées. Note de contenu : Introduction 1 - Planar Partions 2 - Object-based GIS Modelling 3 - Generic Algorithms 4 - StreetMaker - A Generic GIS Framework 5 - Pedestrian Network Generation 6 - 3D Generalized Cylinder Modelling from a Single Image Conclusion Numéro de notice : 21591 Affiliation des auteurs : LASTIG MATIS (2012-2019) Thématique : GEOMATIQUE Nature : Thèse française Note de thèse : thèse de doctorat : Sciences et Technologies de l’Information Géographique : Paris-Est : 2016 Organisme de stage : MATIS (IGN) nature-HAL : Thèse DOI : sans En ligne : https://theses.hal.science/tel-01531580 Format de la ressource électronique : URL Permalink : https://documentation.ensg.eu/index.php?lvl=notice_display&id=90623

Single-image interactive 3D generalized cylinder modeling / Murat Yirci (2016)  

Public Titre : Single-image interactive 3D generalized cylinder modeling Type de document : Article/Communication Auteurs : Murat Yirci, Auteur ; Mathieu Brédif , Auteur ; Nicolas Paparoditis , Auteur Editeur : Saint-Mandé : Institut national de l'information géographique et forestière - IGN (2012-) Année de publication : 2016 Projets : 1-Pas de projet / Métral, Claudine Conférence : JFIG 2016, 29èmes Journées Française d’Informatique Graphique de l'AFIG, du GdR IG-RV du CNRS et du Chapitre Français d’EG 30/11/2016 02/12/2016 Grenoble France Proceedings IEEE Importance : 4 p. Format : 21 x 30 cm Note générale : bibliographie Langues : Anglais (eng) Descripteur : [Vedettes matières IGN] Traitement d'image [Termes IGN] filtrage numérique d'image [Termes IGN] incertitude géométrique [Termes IGN] modèle géométrique de prise de vue [Termes IGN] profondeur Résumé : (auteur) Projective texturing is a commonly used image based rendering technique that enables the synthesis of novel views from the blended reprojection of nearby views on a coarse geometry proxy approximating the scene. When scene geometry is inexact, aliasing artefacts occur. This introduces disturbing artefacts in applications such as street-level immersive navigation in mobile mapping imagery, since a pixel-accurate modelling of the scene geometry and all its details is most of the time out of question. The filtered blending approach applies the necessary 1D low-pass filtering on the projective texture to trade out the aliasing artefacts at the cost of some radial blurring. This paper proposes extensions of the filtered blending approach. Firstly, we introduce Integral Radial Images that enable constant time radial box filtering and show how they can be used to apply box-filtered blending in constant time independently of the amount of depth uncertainty. Secondly, we show a very efficient application of filtered blending where the scene geometry is only given by a loose depth interval prior rather than an actual geometry proxy. Thirdly, we propose a silhouette-aware extension of the box-filtered blending that not only account for uncertain depth along the viewing ray but also for uncertain silhouettes that have to be blurred as well. Numéro de notice : C2016-062 Affiliation des auteurs : LASTIG MATIS (2012-2019) Thématique : IMAGERIE Nature : Communication nature-HAL : ComAvecCL&ActesPubliésNat DOI : sans En ligne : https://hal.science/hal-02551493 Format de la ressource électronique : URL Permalink : https://documentation.ensg.eu/index.php?lvl=notice_display&id=96339

2D arrangement-based hierarchical spatial partitioning: an application to pedestrian network generation / Murat Yirci (2013)  

Public contenu dans Proceedings of the Sixth ACM SIGSPATIAL International Workshop on Computational Transportation Science / Craig A. Knoblock (2013)   Titre : 2D arrangement-based hierarchical spatial partitioning: an application to pedestrian network generation Type de document : Article/Communication Auteurs : Murat Yirci, Auteur ; Mathieu Brédif , Auteur ; Julien Perret , Auteur ; Nicolas Paparoditis , Auteur Editeur : New York [Etats-Unis] : Association for computing machinery ACM Année de publication : 2013 Projets : iSpace&Time / Brédif, Mathieu Conférence : IWCTS 2013, 6th ACM SIGSPATIAL International Workshop on Computational Transportation Science 05/11/2013 08/11/2013 Orlando Floride - Etats-Unis Proceedings ACM Projets : Terra Mobilita / Brédif, Mathieu Importance : pp 31 - 36 Format : 21 x 30 cm Note générale : bibliographie Langues : Anglais (eng) Descripteur : [Vedettes matières IGN] Bases de données localisées [Termes IGN] algorithme génétique [Termes IGN] connexité (graphes) [Termes IGN] données vectorielles [Termes IGN] information sémantique [Termes IGN] modèle conceptuel de données localisées [Termes IGN] partition des données [Termes IGN] partitionnement [Termes IGN] squelettisation [Termes IGN] théorie des graphes Résumé : (auteur) This paper addresses the creation and maintenance of partitions of city surfaces for mapping and transportation applications. It proposes a hierarchical spatial surface partitioning, encoding the spatial partition with a 2D arrangement and structuring a generic hierarchy of semantic objects with a directed acyclic graph (DAG), in which the leaves point to the partition elements (polygonal regions, line strings, points). Semantic objects such as buildings, sidewalks and roads are described by grouping other objects and partition elements with their semantic relationships. In the proposed generic data model, geometry and spatial relationships of the semantic objects are respectively described by the geometry and topology of the planar partition. The proposed geometric data structure for creating and maintaining this partition is a 2D arrangement. In addition, the hierarchical object model encodes the thematic and semantic relationships between the objects. Besides the data model, methods and algorithms are discussed for leveraging existing vector datasets to create and maintain such partitions. These partitions are then fit to further processing and analysis using computational geometry and graph theory algorithms. For this purpose, three application-wise generic algorithms were integrated into our system called Streetmaker: two skeleton operators for centerline generation (straight skeleton and medial axis) and connectivity graphs for itinerary calculations. Moreover, specific algorithms can be integrated into Streetmaker for specific applications. We demonstrated an example usage of this framework for generating static obstacle avoiding pedestrian network graphs. The representation of the network graph and the process used to generate it, can be considered as the second contribution of our work besides the proposed data model. Numéro de notice : C2013-004 Affiliation des auteurs : LASTIG MATIS (2012-2019) Thématique : GEOMATIQUE Nature : Communication DOI : 10.1145/2533828.2533843 En ligne : http://dx.doi.org/10.1145/2533828.2533843 Format de la ressource électronique : URL article Permalink : https://documentation.ensg.eu/index.php?lvl=notice_display&id=80064