Le laboratoire de robotique CAOR de Mines ParisTech a mis au point une technique de numérisation 3D d'environnements extérieurs, utilisant un système mobile appelé LARA3D. Il s'agit d'une voiture équipée de capteurs de localisation (GPS, Centrale Inertielle) et de capteurs de modélisation (lidars et caméras). Ce dispositif permet de construire des nuages de points 3D denses et des images géo-référencées de l'environnement traversé. Dans le cadre de cette thèse, nous avons développé une chaîne de traitement de ces nuages de points et de ces images capable de générer des modèles 3D photo-réalistes. Cette chaîne de modélisation est composée d'une succession d'étapes avec dans l'ordre : le calcul des normales, le débruitage des données, la segmentation en zones planes, la triangulation, la simplification et la texturation. Nous avons testé notre méthode de modélisation sur des données simulées et des données réelles acquises dans le cadre du projet TerraNumerica (en environnement urbain) et du projet Divas (en environnement routier).

Nous nous sommes essentiellement intéressés à la modélisation d'objets volumétriques par des champs de distance scalaire. La distance Euclidienne d'un point a un ensemble de points représentant la frontière d'un solide, correspond à la plus petite distance (définie à partir de la norme Euclidienne) entre ce point et n'importe quel point de l'ensemble. La représentation du solide par la distance à la surface du solide est une méthode concise mais relativement puissante pour définir et manipuler des solides. Dans ce cadre, nous nous sommes intéressés à la modélisation constructive de solides, et à la façon d'implémenter les opérations ensemblistes par des fonctions afin de garantir une bonne approximation de la distance ainsi que certaines propriétés de différentiabilité, nécessaire pour plusieurs classes d'opérations ou applications sur les solides. Nous avons construit différents types de fonctions implémentant les principales opérations ensemblistes (union, intersection, différence). Ces fonctions peuvent être ensuite appliquées à des primitives, définies par la distance à la surface de la primitive, afin de construire récursivement des solides complexes, définies eux-mêmes par une approximation à la distance du solide. Ces fonctions correspondent en fait à une certaine classe de R-fonctions, obtenues en lissant les points critiques des fonctions min/max (qui sont elles mêmes des R-fonctions). Ces fonctions sont appelées Signed Approximate Real Distance Functions (SARDF). Le cadre SARDF, constitue des fonctions décrites ci-dessus et de primitives définies par la fonction distance, a été utilisé pour la modélisation hétérogène de solides. La distance, ou son approximation, à la surface du solide ou des matériaux internes est utilisée comme un paramètre pour modéliser la distribution des matériaux à l'intérieur du solide. Le cadre SARDF a principalement été implémenté comme une extension de l'interpréteur d'HyperFun et à l'intérieur de l'applet Java d'HyperFun. La modélisation constructive de solides possède de nombreux avantages qui en font un outil puissant pour la modélisation de solides. Néanmoins, la définition constructive de solides peut être fastidieuse et répétitive. Nous avons étudié différents aspects pour l'automatiser. Dans un premier temps, nous avons introduit la notion de modèles template, et proposé différents algorithmes pour optimiser la forme d'un template à différentes instances correspondant à des nuages de points, sur ou aux alentours de la surface du solide. L'idée des templates vient de l'observation que les solides traditionnellement modélisés par ordinateur peuvent être regroupés en différentes classes possédant des caractéristiques communes. Par exemple, différents vases peuvent avoir une forme commune. Cette forme générale est modélisée une seule fois, et différents paramètres gouvernant les caractéristiques de la forme sont extraits. Ces paramètres sont ensuite optimisés à l'aide d'une combinaison de méta-heuristique comme le recuit simulé ou les algorithmes génétiques avec des méthodes directes du type Newton ou LevenbergMarquardt. L'utilisation du cadre SARDF pour la définition du modèle template est préférable, car donne de meilleurs résultats avec les algorithmes d'optimisation. Nous pouvons maintenant nous demander comment le modèle template est obtenu. Une première solution est d'utiliser les services d'un artiste. Néanmoins, nous pouvons aussi réfléchir pour automatiser ce processus. Nous avons essentiellement étudié deux aspects pour répondre à cette question : la première est l'utilisation de la programmation génétique pour former un modèle constructif à partir d'un nuage de points. La deuxième solution consiste à partir d'un nuage de points segmentés et une liste de primitives optimisés à ce nuage de points segmenté, d'utiliser un algorithme génétique pour déterminer l'ordre et le type d'opérations qui peuvent être appliquées à ces primitives. Ces deux solutions ont été implémentées et leurs résultats discutés.

Au cours de ces dernières décennies, le développement de Systèmes Mobiles de Cartographie, soutenu par un progrès technologique important, est devenu plus apparent. Il a été stimulé par le besoin grandissant de collecte d'informations géographiques précises sur l'environnement. Nous considérons, au sein de cette thèse, des solutions pour l'acquisition des nuages de points mobiles de qualité topographique (précision centimétrique). Il s'agit, dans cette tâche, de mettre au point des méthodes de qualification des données, et d'en améliorer sur les erreurs systématiques par des techniques d'étalonnage et de recalage adéquates.Nous décrivons une démarche innovante d'évaluation de l'exactitude et/ou de la précision des relevés laser mobiles. Celle-ci repose sur l'extraction et la comparaison des entités linéaires de la scène urbaine. La distance moyenne calculée entre les segments appariés, étant la distance modifiée de Hausdorff, sert à noter les nuages par rapport à des références existantes. Pour l'extraction des arêtes, nous proposons une méthode de détection d'intersections entre segments plans retrouvés via un algorithme de RANSAC enrichi d'une analyse de composantes connexes. Nous envisageons également une démarche de correction de relevés laser mobiles à travers un recalage rigide fondé, lui aussi, sur les éléments linéaires. Enfin, nous étudions la pertinence des segments pour en déduire les paramètres de l'étalonnage extrinsèque du système mobile. Nous testons nos méthodes sur des données simulées et des données réelles acquises dans le cadre du projet TerraMobilita.

Avec l'évolution des dispositifs d'acquisition 3D, les nuages de points sont maintenant devenus une représentation essentielle des scènes numérisées. Les systèmes récents sont capables de capturer plusieurs centaines de millions de points en une seule acquisition. Comme plusieurs acquisitions sont nécessaires pour capturer la géométrie de scènes de grande taille, un site historique par exemple, nous obtenons des nuages de points massifs, i.e., composés de plusieurs milliards de points. Dans cette thèse, nous nous intéressons à la structuration et à la manipulation de nuages de points issus d'acquisitions générées à partir de LiDARs terrestres. A partir de la structure de chaque acquisition, des graphes, représentant chacun la connectivité locale de la surface numérisée, sont construits. Les graphes créés sont ensuite liés entre eux afin d'obtenir une représentation globale de la surface capturée. Nous montrons que cette structure est particulièrement adaptée à la manipulation de la surface sous-jacente aux nuages de points massifs, même sur des ordinateurs ayant une mémoire limitée. Notamment, nous montrons que cette structure permet de traiter deux problèmes spécifiques à ce type de données. Un premier lié au ré-échantillonnage de nuages de points, en générant des distributions de bonne qualité en termes de bruit bleu grâce à un algorithme d'échantillonnage en disques de Poisson. Un autre lié à la construction de diagrammes de Voronoï centroïdaux, permettant l'amélioration de la qualité des distributions générées, ainsi que la reconstruction de maillages triangulaires. / With the evolution of 3D acquisition devices, point clouds have now become an essential representation of digitized scenes. Recent systems are able to capture several hundreds of millions of points in a single acquisition. As multiple acquisitions are necessary to capture the geometry of large-scale scenes, a historical site for example, we obtain massive point clouds, i.e., composed of billions of points. In this thesis, we are interested in the structuration and manipulation of point clouds from acquisitions generated by terrestrial LiDARs. From the structure of each acquisition, graphs, each representing the local connectivity of the digitized surface, are constructed. Created graphs are then linked together to obtain a global representation of the captured surface. We show that this structure is particularly adapted to the manipulation of the underlying surface of massive point clouds, even on computers with limited memory. Especially, we show that this structure allow to deal with two problems specific to that kind of data. A first one linked to the resampling of point clouds, by generating distributions of good quality in terms of blue noise thanks to a Poisson disk sampling algorithm. Another one connected to the construction of centroidal Voronoi tessellations, allowing to enhance the quality of generated distributions and to reconstruct triangular meshes.

Aujourd’hui, de nouvelles technologies permettent l’acquisition de scènes 3D volumineuses et précises sous la forme de nuages de points. Les nouvelles applications ouvertes par ces technologies, comme les véhicules autonomes ou la maintenance d'infrastructure, reposent sur un traitement efficace des nuages de points à grande échelle. Les méthodes d'apprentissage profond par convolution ne peuvent pas être utilisées directement avec des nuages de points. Dans le cas des images, les filtres convolutifs ont permis l’apprentissage de nouvelles représentations, jusqu’alors construites « à la main » dans les méthodes de vision par ordinateur plus anciennes. En suivant le même raisonnement, nous présentons dans cette thèse une étude des représentations construites « à la main » utilisées pour le traitement des nuages de points. Nous proposons ainsi plusieurs contributions, qui serviront de base à la conception d’une nouvelle représentation convolutive pour le traitement des nuages de points. Parmi elles, une nouvelle définition de voisinages sphériques multi-échelles, une comparaison avec les k plus proches voisins multi-échelles, une nouvelle stratégie d'apprentissage actif, la segmentation sémantique des nuages de points à grande échelle, et une étude de l'influence de la densité dans les représentations multi-échelles. En se basant sur ces contributions, nous introduisons la « Kernel Point Convolution » (KPConv), qui utilise des voisinages sphériques et un noyau défini par des points. Ces points jouent le même rôle que les pixels du noyau des convolutions en image. Nos réseaux convolutionnels surpassent les approches de segmentation sémantique de l’état de l’art dans presque toutes les situations. En plus de ces résultats probants, nous avons conçu KPConv avec une grande flexibilité et une version déformable. Pour conclure notre réflexion, nous proposons plusieurs éclairages sur les représentations que notre méthode est capable d'apprendre. / In the recent years, new technologies have allowed the acquisition of large and precise 3D scenes as point clouds. They have opened up new applications like self-driving vehicles or infrastructure monitoring that rely on efficient large scale point cloud processing. Convolutional deep learning methods cannot be directly used with point clouds. In the case of images, convolutional filters brought the ability to learn new representations, which were previously hand-crafted in older computer vision methods. Following the same line of thought, we present in this thesis a study of hand-crafted representations previously used for point cloud processing. We propose several contributions, to serve as basis for the design of a new convolutional representation for point cloud processing. They include a new definition of multiscale radius neighborhood, a comparison with multiscale k-nearest neighbors, a new active learning strategy, the semantic segmentation of large scale point clouds, and a study of the influence of density in multiscale representations. Following these contributions, we introduce the Kernel Point Convolution (KPConv), which uses radius neighborhoods and a set of kernel points to play the role of the kernel pixels in image convolution. Our convolutional networks outperform state-of-the-art semantic segmentation approaches in almost any situation. In addition to these strong results, we designed KPConv with a great flexibility and a deformable version. To conclude our argumentation, we propose several insights on the representations that our method is able to learn.

Depuis quelques années, l’évolution des techniques d’acquisition a entraîné une généralisation de l’utilisation d’objets 3D très dense, représentés par des nuages de points de plusieurs millions de sommets. Au vu de la complexité de ces données, il est souvent nécessaire de les analyser pour en extraire les structures les plus pertinentes, potentiellement définies à plusieurs échelles. Parmi les nombreuses méthodes traditionnellement utilisées pour analyser des signaux numériques, l’analyse dite scale-space est aujourd’hui un standard pour l’étude des courbes et des images. Cependant, son adaptation aux données 3D pose des problèmes d’instabilité et nécessite une information de connectivité, qui n’est pas directement définie dans les cas des nuages de points. Dans cette thèse, nous présentons une suite d’outils mathématiques pour l’analyse des objets 3D, sous le nom de Growing Least Squares (GLS). Nous proposons de représenter la géométrie décrite par un nuage de points via une primitive du second ordre ajustée par une minimisation aux moindres carrés, et cela à pour plusieurs échelles. Cette description est ensuite derivée analytiquement pour extraire de manière continue les structures les plus pertinentes à la fois en espace et en échelle. Nous montrons par plusieurs exemples et comparaisons que cette représentation et les outils associés définissent une solution efficace pour l’analyse des nuages de points à plusieurs échelles. Un défi intéressant est l’analyse d’objets 3D acquis dans le cadre de l’étude du patrimoine culturel. Dans cette thèse, nous nous étudions les données générées par l’acquisition des fragments des statues entourant par le passé le Phare d’Alexandrie, Septième Merveille du Monde. Plus précisément, nous nous intéressons au réassemblage d’objets fracturés en peu de fragments (une dizaine), mais avec de nombreuses parties manquantes ou fortement dégradées par l’action du temps. Nous proposons un formalisme pour la conception de systèmes d’assemblage virtuel semi-automatiques, permettant de combiner à la fois les connaissances des archéologues et la précision des algorithmes d’assemblage. Nous présentons deux systèmes basés sur cette conception, et nous montrons leur efficacité dans des cas concrets. / Over the last decades, the evolution of acquisition techniques yields the generalization of detailed 3D objects, represented as huge point sets composed of millions of vertices. The complexity of the involved data often requires to analyze them for the extraction and characterization of pertinent structures, which are potentially defined at multiple scales. Amongthe wide variety of methods proposed to analyze digital signals, the scale-space analysis istoday a standard for the study of 2D curves and images. However, its adaptation to 3D dataleads to instabilities and requires connectivity information, which is not directly availablewhen dealing with point sets.In this thesis, we present a new multi-scale analysis framework that we call the GrowingLeast Squares (GLS). It consists of a robust local geometric descriptor that can be evaluatedon point sets at multiple scales using an efficient second-order fitting procedure. We proposeto analytically differentiate this descriptor to extract continuously the pertinent structuresin scale-space. We show that this representation and the associated toolbox define an effi-cient way to analyze 3D objects represented as point sets at multiple scales. To this end, we demonstrate its relevance in various application scenarios.A challenging application is the analysis of acquired 3D objects coming from the CulturalHeritage field. In this thesis, we study a real-world dataset composed of the fragments ofthe statues that were surrounding the legendary Alexandria Lighthouse. In particular, wefocus on the problem of fractured object reassembly, consisting of few fragments (up to aboutten), but with missing parts due to erosion or deterioration. We propose a semi-automaticformalism to combine both the archaeologist’s knowledge and the accuracy of geometricmatching algorithms during the reassembly process. We use it to design two systems, andwe show their efficiency in concrete cases.

La géométrie algorithmique est une discipline en pleine expansion dont l'objet est la conception d'algorithmes résolvant des problèmes géométriques. De tels algorithmes sont très utiles notamment dans l'ingénierie, l'industrie et le multimédia. Pour être performant, il est fréquent qu'un algorithme géométrique utilise des structures de données spécialisées.Nous nous sommes intéressés à une telle structure : le diagramme de Voronoï et avons proposé une généralisation de celui-ci. Ladite généralisation résulte d'une extension du prédicat du disque vide (prédicat propre à toute région de Voronoï) à une union de disques. Nous avons analysé les régions basées sur le prédicat étendu et avons proposé des méthodes pour les calculer par ordinateur.Par ailleurs, nous nous sommes intéressés aux « problèmes de placement de formes », thème récurrent en géométrie algorithmique. Nous avons introduit un formalisme universel pour de tels problèmes et avons, pour la première fois, proposé une méthode de résolution générique, en ce sens qu'elle est apte à résoudre divers problèmes de placement suivant un même algorithme.Nos travaux présentent, d'une part, l'avantage d'élargir le champ d'application de structures de données basées sur Voronoï. D'autre part, ils facilitent de manière générale l'utilisation de la géométrie algorithmique, en unifiant définitions et algorithmes associés aux problèmes de placement de formes. / Computational geometry is an active branch of computer science whose goal is the design of efficient algorithms solving geometric problems. Such algorithms are useful in domains like engineering, industry and multimedia. In order to be efficient, algorithms often use special data structures.In this thesis we focused on such a structure: the Voronoi diagram. We proposed a new generalized diagram. We have proceeded by extending the empty disk predicate (satisfied by every Voronoi region) to an arbitrary union of disks. We have analyzed the new plane regions based on the extended predicate, and we designed algorithms for computing them.Then, we have considered another topic, which is related to the first one: shape placement problems. Such problems have been studied repeatedly by researchers in computational geometry. We introduced new notations along with a global framework for such problems. We proposed, for the first time a generic method, which is able to solve various placement problems using a single algorithm.Thus, our work extend the scope of Voronoi based data structures. It also simplifies the practical usage of placement techniques by unifying the associated definitions and algorithms.

Un phénomène naturel se manifeste par des dynamiques, plus ou moins complexes, aux formes diverses et à topologie variable. Ce mouvement est induit soit par une intervention extérieure, soit par un état interne, qui induit une réorganisation de matière (une agitation ou un écoulement par exemple). CORDIS-ANIMA, système de modélisation et de simulation numérique d'objets physiques, permet par la gestion de quelques paramètres de réaliser toutes sortes de phénomènes sans connaître l'expression formelle de la physique sous-jacente à celui-ci. A l'aide de ce formalisme, nous avons réalisé des modèles de pâtes, de sable, de gel (2D et 3D), de fluides turbulents (2D) et de croissance végétales. Les calculs de simulations produisent un nuage de points matériels qui font partie intégrante de la matière simulée. Ces points n'étant pas disposés sur la surface de l'objet, il n'est dès lors pas possible de réaliser directement un rendu de la surface de cet objet. Nous avons donc mis au point des méthodes de construction volumique qui à partir des informations produites par la simulation, génèrent les indications volumiques manquantes. En étudiant les paramètres physiques des phénomènes simulés, en caractérisant les dynamiques internes révélées par les mouvements des points matériels calculés, ou encore en tentant de reproduire simplement les comportements cognitifs qui permettent à un observateur de ""deviner"" la forme d'un objet à partir d'une information de forme incomplète (i.e. un nuage de point issu de la simulation), nous avons réalisé un ensemble de techniques de construction et de rendu adaptées aux types de phénomènes simulés.

La géométrie algorithmique est une discipline en pleine expansion dont l'objet est la conception d'algorithmes résolvant des problèmes géométriques. De tels algorithmes sont très utiles notamment dans l'ingénierie, l'industrie et le multimédia. Pour être performant, il est fréquent qu'un algorithme géométrique utilise des structures de données spécialisées.Nous nous sommes intéressés à une telle structure : le diagramme de Voronoï et avons proposé une généralisation de celui-ci. Ladite généralisation résulte d'une extension du prédicat du disque vide (prédicat propre à toute région de Voronoï) à une union de disques. Nous avons analysé les régions basées sur le prédicat étendu et avons proposé des méthodes pour les calculer par ordinateur.Par ailleurs, nous nous sommes intéressés aux " problèmes de placement de formes ", thème récurrent en géométrie algorithmique. Nous avons introduit un formalisme universel pour de tels problèmes et avons, pour la première fois, proposé une méthode de résolution générique, en ce sens qu'elle est apte à résoudre divers problèmes de placement suivant un même algorithme.Nos travaux présentent, d'une part, l'avantage d'élargir le champ d'application de structures de données basées sur Voronoï. D'autre part, ils facilitent de manière générale l'utilisation de la géométrie algorithmique, en unifiant définitions et algorithmes associés aux problèmes de placement de formes.

Certaines opérations de maintenance sur sites industriels nécessitent une planification à partir de modèles numériques 3D des scènes où se déroulent les interventions. Pour permettre la simulation de ces opérations, les modèles 3D utilisés doivent représenter fidèlement la réalité du terrain. Ces représentations virtuelles sont habituellement construites à partir de nuages de points relevés sur le site, constituant une description métrologique exacte de l’environnement sans toutefois fournir une description géométrique de haut niveau.Il existe une grande quantité de travaux abordant le problème de la reconstruction de modèles 3D à partir de nuages de points, mais peu sont en mesure de fournir des résultats suffisamment fiables dans un contexte industriel et cette tâche nécessite en pratique l’intervention d’opérateurs humains.Les travaux réalisés dans le cadre de cette thèse visent l’automatisation de la reconstruction,avec comme principal objectif la fiabilité des résultats obtenus à l’issu du processus. Au vu de la complexité de ce problème, nous proposons d’exploiter des connaissances et données a priori pour guider la reconstruction. Le premier a priori concerne la compositiondes modèles 3D : en Conception Assistée par Ordinateur (CAO), les scènes industrielles sont couramment décrites comme des assemblages de primitives géométriques simples telles que les plans, sphères, cylindres, cônes, tores, etc. Nous hiérarchisons l’analyse en traitant dans un premier temps les plans et les cylindres, comme un préalable à la détection de stores. On obtient ainsi une description fiable des principaux composants d’intérêt dans les environnements industriels. Nous proposons en outre d’exploiter un certain nombre de règles régissant la manière dont ces primitives s’assemblent en un modèle CAO, basées surdes connaissances ”métier” caractérisant les scènes industrielles que nous traitons. De plus,nous tirons parti d’un modèle CAO existant d´ecrivant une scène similaire à celle que nous souhaitons reconstruire, provenant typiquement de la reconstruction antérieure d’un site semblable au site d’intérêt. Bien que semblables en théorie, ces scènes peuvent présenterdes différences significatives qui s’accentuent au cours de leur exploitation.La méthode que nous développons se fonde sur une formulation Bayésienne du problème de reconstruction : il s’agit de retrouver le modèle CAO le plus probable vis à visdes différentes attentes portées par les données et les a priori sur le modèle à reconstruire. Les diverses sources d’a priori s’expriment naturellement dans cette formulation. Pour permettre la recherche du modèle CAO optimal, nous proposons une approche basée surdes tentatives d’insertion d’objets générés aléatoirement. L’acceptation ou le rejet de ces objets repose ensuite sur l’am´elioration systématique de la solution en cours de construction. Le modèle CAO se construit ainsi progressivement, par ajout et suppression d’objets, jusqu’à obtention d’une solution localement optimale. / 3D models are often used in order to plan the maintenance of industrial environments.When it comes to the simulation of maintenance interventions, these 3D models have todescribe accurately the actual state of the scenes they stand for. These representationsare usually built from 3D point clouds that are huge set of 3D measurements acquiredin industrial sites, which guarantees the accuracy of the resulting 3D model. Althoughthere exists many works addressing the reconstruction problem, there is no solution toour knowledge which can provide results that are reliable enough to be further used inindustrial applications. Therefore this task is in fact handled by human experts nowadays.This thesis aims at providing a solution automating the reconstruction of industrialsites from 3D point clouds and providing highly reliable results. For that purpose, ourapproach relies on some available a priori knowledge and data about the scene to beprocessed. First, we consider that the 3D models of industrial sites are made of simpleprimitive shapes. Indeed, in the Computer Aided Design (CAD) field, this kind of scenesare described as assemblies of shapes such as planes, spheres, cylinders, cones, tori, . . . Ourown work focuses on planes, cylinders and tori since these three kind of shapes allow thedescription of most of the main components in industrial environment. Furthermore, weset some a priori rules about the way shapes should be assembled in a CAD model standingfor an industrial facility, which are based on expert knowledge about these environments.Eventually, we suppose that a CAD model standing for a scene which is similar to theone to be processed is available. This a priori CAO model typically comes from the priorreconstruction of a scene which looks like the one we are interested in. Despite the factthat they are similar theoretically, there may be significant differences between the sitessince each one has its own life cycle.Our work first states the reconstruction task as a Bayesian problem in which we haveto find the most probable CAD Model with respect to both the point cloud and the a prioriexpectations. In order to reach the CAD model maximizing the target probability, wepropose an iterative approach which improves the solution under construction each time anew randomly generated shape is tried to be inserted in it. Thus, the CAD model is builtstep by step by adding and removing shapes, until the algorithm gets to a local maximumof the target probability.