Un problème toujours d'actualité est la reconstruction automatique de la surface d'une scène à partir du flot d'images prises par une caméra en mouvement. Il se résout en général en deux étapes : le calcul de la géométrie où les poses de la caméra et un nuage épars de points 3D de la scène sont simultanément estimés, et un calcul de stéréo dense qui permet d'obtenir une surface en estimant la profondeur de tous les pixels. L' approche que nous proposons se distingue des précédentes en cumulant les caractéristiques suivantes. La surface est une 2-variété, ce qui est utile pour les traitements ou utilisations ultérieurs. Elle est calculée directement à partir du nuage épars donné par la première étape, afin d'éviter la seconde étape coûteuse et pour obtenir une modélisation compacte d'une scène complexe. Le calcul est incrémental afin d'avoir un résultat pendant la lecture de la vidéo. Le principe est le suivant. A chaque itération, de nouveaux points 3D sont estimés et insérés dans une triangulation de Delaunay 3D. Celle-ci partitionne l'espace en tétraèdres vides et pleins grâce à l'information de visibilité également fournie par la première étape. On met aussi à jour une seconde partition en tétraèdres intérieurs et extérieurs dont le bord est la 2-variété recherchée. Sous certaines hypothèses, et contrairement à la seule méthode précédente ayant les même propriétés et hypothèses, la complexité d'une itération est bornée. Notre méthode a été expérimentée sur des séquences synthétiques et réelles, dont une séquence longue de 2;5 km prise en milieu urbain avec une caméra omnidirectionnelle. La qualité du résultat est proche de celle obtenue par la méthode globale (non incrémentale) qui a servi d'inspiration, mais le temps de calcul ne permet pas actuellement une utilisation en-ligne sur un PC standard. On a aussi étudié l'intérêt d'ajouter des contours dans le processus de reconstruction. / The automatic reconstruction of a scene surface from images taken by a moving camera is still an active research topic. This problem is usually solved in two steps : first estimate the camera poses and a sparse cloud of 3D points using Structure-from-Motion, then apply dense stereo to obtain the surface by estimating the depth for all pixels. Compared to the previous approaches, ours accumulates the following properties. The output surface is a 2-manifold, which is useful for applications and postprocessing. It is computed directly from the sparse point cloud provided by the first step, so as to avoid the second and time consuming step and to obtain a compact model of a complex scene. The computation is incremental to allow access to intermediary results during the processing. The principle is the following. At each iteration, new 3D points are estimated and added to a 3D Delaunay triangulation; the tetrahedra are labeled as free-space or matter thanks to the visibility information provided by the first step. We also update a second partition of outside and inside tetrahedra whose boundary is the target 2-manifold. Under some assumptions, the time complexity of one iteration is bounded (there is only one previous method with the same properties, but its complexity is greater than that). Our method is experimented on synthetic and real sequences, including a 2:5 km. long urban sequence taken by an omnidirectional camera. The surface quality is similar to that of the batch method which inspired us. However, the computations are not yet real-time on a commodity PC. We also study the use of contours in thereconstruction process.

La modélisation géométrique d'objets fabriqués par l'homme à partir de données 3D est l'un des plus grands défis de la vision par ordinateur et de l'infographie. L'objectif à long terme est de générer des modèles de type CAO de la manière la plus automatique possible. Pour atteindre cet objectif, des problèmes difficiles doivent être résolus, notamment (i) le passage à l'échelle du processus de modélisation sur des données d'entrée massives, (ii) la robustesse de la méthodologie contre des mesures d'entrées erronés, et (iii) la qualité géométrique des modèles de sortie. Les méthodes existantes fonctionnent efficacement pour reconstruire la surface des objets de forme libre. Cependant, dans le cas d'objets fabriqués par l'homme, il est difficile d'obtenir des résultats dont la qualité approche celle des représentations hautement structurées, comme les modèles CAO. Dans cette thèse, nous présentons une série de contributions dans ce domaine. Tout d'abord, nous proposons une méthode de classification basée sur l'apprentissage en profondeur pour distinguer des objets dans des environnements complexes à partir de nuages de points 3D. Deuxièmement, nous proposons un algorithme pour détecter des primitives planaires dans des données 3D à différents niveaux d'abstraction. Enfin, nous proposons un mécanisme pour assembler des primitives planaires en maillages polygonaux compacts. Ces contributions sont complémentaires et peuvent être utilisées de manière séquentielle pour reconstruire des modèles de ville à différents niveaux de détail à partir de données 3D aéroportées. Nous illustrons la robustesse, le passage à l'échelle et l'efficacité de nos méthodes sur des données laser et multi-vues stéréo sur des scènes composées d'objets fabriqués par l'homme. / Geometric modeling of man-made objects from 3D data is one of the biggest challenges in Computer Vision and Computer Graphics. The long term goal is to generate a CAD-style model in an as-automatic-as-possible way. To achieve this goal, difficult issues have to be addressed including (i) the scalability of the modeling process with respect to massive input data, (ii) the robustness of the methodology to various defect-laden input measurements, and (iii) the geometric quality of output models. Existing methods work well to recover the surface of free-form objects. However, in case of manmade objects, it is difficult to produce results that approach the quality of high-structured representations as CAD models.In this thesis, we present a series of contributions to the field. First, we propose a classification method based on deep learning to distinguish objects from raw 3D point cloud. Second, we propose an algorithm to detect planar primitives in 3D data at different level of abstraction. Finally, we propose a mechanism to assemble planar primitives into compact polygonal meshes. These contributions are complementary and can be used sequentially to reconstruct city models at various level-of-details from airborne 3D data. We illustrate the robustness, scalability and efficiency of our methods on both laser and multi-view stereo data composed of man-made objects.

L’évolution de la reconstruction de surface de l’Au(111) sous contrainte-déformation a été étudiée dans le cadre d’une approche, à la fois expérimentale par microscopie à effet tunnel sous environnement ultra-vide couplée à un dispositif en compression, et numériquement par simulations en dynamique moléculaire. Dans un premier temps, nous avons étudié l’interaction entre les marches atomiques (vicinales ou traces de glissement) et la reconstruction. Nous avons notamment montré expérimentalement une forte dépendance de la longueur de la reconstruction avec la largeur des terrasses, en très bon accord avec les simulations atomistiques. Nous avons démontré de manière quantitative que ce comportement provenait de la relaxation des contraintes de surface, à la fois le long et perpendiculairement aux marches atomiques. Par la suite, nous avons montré que l’apparition d’une trace de glissement, résultant de l’émergence d’une dislocation à la surface, induit une réorganisation de la reconstruction, caractérisée par la formation d’un motif en forme de U. Nous avons par ailleurs observé expérimentalement la présence de décrochements le long de la trace. Les simulations ont confirmé que ces décrochements étaient corrélés avec la modification de la reconstruction. Dans un second temps, l’étude s’est axée sur l’évolution de la reconstruction en chevrons sous contrainte-déformation appliquée. Les observations expérimentales ont montré qu’une contrainte de compression macroscopique était à l’origine d’une modification de la structure en chevrons. Les simulations en dynamique moléculaire ont permis d’analyser l’influence de l’orientation de la contrainte sur les dislocations perçant la surface. Nous avons montré qu’une réorganisation irréversible de la structure en chevrons a lieu, se caractérisant par l’annihilation des dislocations perçant la surface et la suppression de la structure en chevrons. / The evolution of the surface reconstruction of the Au(111) under stress-strain has been studied in the context of an experimental approach, both by tunneling microscopy under ultra-vacuum environment coupled to a compression device, and numerically by molecular dynamics simulations. At first, we studied the interaction between atomic steps (vicinal or slip traces) and reconstruction. In particular, we showed experimentally a strong dependence of the length of the reconstruction with the width of the terraces, in very good agreement with the atomistic simulations. We have quantitatively demonstrated that this behavior is originated from the release of surface stress, both along and perpendicular to the atomic steps. Subsequently, we have shown that the appearance of a slip traces, resulting from the emergence of dislocations at the surface, induce a reorganization of the reconstruction, characterized by the formation of a U-shaped pattern. We also observed experimentally the presence of kinks along the trace. The simulations confirmed that these kinks are correlated with the modification of the reconstruction. At last, the study focused on the evolution of the chevron pattern under applied stress-strain. Experimental observations have shown that a macroscopic compressive strain involved a modification of the herringbone structure. Molecular dynamics simulations allowed to analyze the influence of stress orientation on surface threading dislocations. We have shown that an irreversible reorganisation of the herringbone structure takes place, characterized by the annihilation of the surface threading dislocations and the removal of the herringbone structure.

La majorité des algorithmes de reconstruction de surface sont optimisés pour s'appliquer à des données de haute qualité. Les résultats obtenus peuvent alors être inutilisables si les données proviennent de solutions d'acquisition bon marché. Notre première contribution est un algorithme de reconstruction de surfaces à partir de données de stéréo vision. Il combine les informations liées aux points 3D avec les images calibrées afin de combler l'imprécision des données. L'algorithme construit une soupe de triangles 3D à l'aide des images calibrées et à l'issue d'une phase de prétraitement du nuage de points. Pour épouser au mieux la surface de la scène, on contraint cette soupe de triangle 3D à respecter des critères de visibilité et de photo-consistance. On calcule ensuite un maillage à partir de la soupe de triangles à l'aide d'une technique de reconstruction qui combine les triangulations de Delaunay contraintes et le raffinement de Delaunay. Notre seconde contribution est un algorithme qui construit, à partir d'un nuage de points 3D échantillonnés sur une surface, un maillage de surface qui représente fidèlement les arêtes vives. Cet algorithme génère un bon compromis entre précision et complexité du maillage. Dans un premier temps, on extrait une approximation des arêtes vives de la surface sous-jacente à partir du nuage de points. Dans un deuxième temps, on utilise une variante du raffinement de Delaunay pour générer un maillage qui combine les arêtes vives extraites avec une surface implicite obtenue à partir du nuage de points. Notre méthode se révèle flexible, robuste au bruit; cette méthode peut prendre en compte la résolution du maillage ciblé et un champ de taille défini par l'utilisateur. Nos deux contributions génèrent des résultats efficaces sur une variété de scènes et de modèles. Notre méthode améliore l'état de l'art en termes de précision.

L'acquisition de modèles 3D des scènes réelles trouve son utilité dans de nombreuses applications pratiques, comme l'archivage numérique, les jeux vid eo, l'ingénierie, la publicité. Il existe principalement deux méthodes pour acqu érir un modèle 3D: la reconstruction avec un scanner laser (méthode active) et la reconstruction à partir de plusieurs photographies d'une même scène prise dans des points de vues différents (méthode passive). La méthode passive, ou la stéréo multi-vues est en revanche plus flexible, facile à mettre en oeuvre avec une grande précision, et surtout moins couteuse que la méthode active. Cette thèse s'attaque au problème de la reconstruction de stereo multi-vues à grande échelle . Nous améliorons des méthodes précédentes et les assemblons pour créer une chaine de stereo multi-vues efficace tirant parti de l'accélération des cartes graphiques. La chaîne produit des maillages de qualité à partir d'images de haute résolution, ce qui permet d'atteindre les meilleurs scores dans de nombreuses évaluations. Aux plus grandes échelles, nous développons d'une part des techniques de type diviser-pour-régner pour reconstruire des morceaux partiaux de la scène. D'autre part, pour combiner ces résultats séparés, nous créons une nouvelle méthode qui fusionne rapidement des centaines de maillages. Nous réussissons à reconstruire de beaux maillages urbains et des monuments historiques précis à partir de grandes collections d'images (environ 1600 images de 5M Pixel).

Cette thèse introduit une nouvelle approche pour la reconstruction de surface à partir d'acquisitions de nuages de points. Cette approche construit un complexe cellulaire à partir du nuage de points puis formule la reconstruction comme un problème d'étiquetage binaire des cellules de ce complexe sous un ensemble de contraintes de visibilité. La résolution du problème se ramène alors au calcul d'une coupe minimale s-t permettant d'obtenir efficacement une surface optimale d'après ces contraintes. Dans la première partie de cette thèse, l'approche est utilisée pour la reconstruction générique de surface. Une première application aboutit à un algorithme très robuste de reconstruction de surface à partir de nuages denses issus d'acquisitions laser. Une seconde application utilise une variante de cet algorithme au sein d'une chaîne de photo-modélisation en combinaison avec un raffinement variationnel photométrique. La chaîne complète est adaptée à la reconstruction de scènes de grande échelle et obtient d'excellents résultats en terme de complétude et de précision des reconstructions. La seconde partie de cette thèse considère le problème de la reconstruction directe de modèles géométriques simples à partir de nuages de points. Un algorithme robuste est proposé pour décomposer hiérarchiquement des nuages de points denses en formes issues d'un ensemble restreint de classes de formes. Lorsque que cet ensemble de classes est réduit aux plans seulement, la reconstruction de modèles de très faible complexité est possible. Une extension à d'autres classes de formes échange cet avantage contre la gestion de nuages de points plus difficiles.

Au cours des dernières années, la capacité de la technologie LiDAR à capturer des informations détaillées sur la structure des forêts a attiré une attention croissante de la part de la communauté des écologues et des forestiers. Le LiDAR terrestre, notamment, apparaît comme un outil prometteur pour recueillir les caractéristiques géométriques des arbres à une précision millimétrique.Cette thèse étudie la reconstruction de surface à partir de nuages de points épars et non structurés, capturés en environnement forestier par un LiDAR terrestre. Nous proposons une suite d’algorithmes dédiés à la reconstruction de modèles d’attributs de placettes forestières : le sol etla structure ligneuse des arbres (i.e. troncs et branches principales). En pratique, nos approches modélisent le problème par des surfaces implicites construites à partir de fonctions à base radiale pour faire face à la forte hétérogénéité spatiale du nuage de points Lidar terrestre. / In recent years, the capacity of LiDAR technology to capture detailed information about forests structure has attracted increasing attention in the field of forest science. In particular, the terrestrial LiDAR arises as a promising tool to retrieve geometrical characteristics of trees at a millimeter level.This thesis studies the surface reconstruction problem from scattered and unorganized point clouds, captured in forested environment by a terrestrial LiDAR. We propose a sequence of algorithms dedicated to the reconstruction of forests plot attributes model: the ground and the woody structure of trees (i.e. the trunk and the main branches). In practice, our approaches model the surface with implicit function build with radial basis functions to manage the homogeneity and handle the noise of the sample data points.

La 3D s'impose comme un nouveau média dont l'adoption généralisée passe par la conception d'outils, accessibles au grand public, de création et de manipulation de formes tridimensionnelles quelconques. Les outils actuels reposent fortement sur la modélisation sous-jacente des formes, généralement surfacique, et sont alors peu intuitifs ou limitatifs dans l'expressivité offerte à l'utilisateur.Nous souhaitons, dans ces travaux, définir une approche ne présentant pas ces défauts et permettant à l'utilisateur de se concentrer sur le processus créatif. En nous inspirant de l'utilisation séculaire de l'argile, nous proposons une approche modélisant la matière sous forme lagrangienne.Une forme est ainsi décrite par un système de particules, où chaque particule représente un petit volume du volume global.Dans ce cadre lagrangien, la méthode Smoothed Particle Hydrodynamics (SPH) permet l'approximation de grandeurs physiques en tout point de l'espace. Nous proposons alors une modélisation de matériaux à deux couches, l'une décrivant la topologie et l'autre décrivant la géométrie du système global.La méthode SPH permet, entre autres, d'évaluer la densité de matière. Ceci nous permet de définir une surface implicite basée sur les propriétés physiques du système de particules pour redonner un aspect continu à la matière.Ces matériaux peuvent alors être manipulés au moyen d'interactions locales reproduisant le maniement de la pâte à modeler, et de déformations globales. L'intérêt de notre approche est démontrée par plusieurs prototypes fonctionnant sur des stations de travail standard ou dans des environnements immersifs. / 3D is emerging as a new media. Its widespread adoption requires the implementation of userfriendly tools to create and manipulate three-dimensional shapes. Current softwares heavily rely on underlying shape modeling, usually a surfacic one, and are then often counter-intuitive orlimiting. Our objective is the design of an approach alleviating those limitations and allowing the user to only focus on the process of creating forms. Drawing inspiration from the ancient use of clay,we propose to model a material in a lagrangian description. A shape is described by a particles system, where each particle represents a small fraction of the total volume of the shape. In this framework, the Smoothed Particle Hydrodynamics method enables to approximate physical values anywhere in space. Relying on this method, we propose a modeling of material with two levels, one level representing the topology and the other one describing local geometry of the shape.The SPH method especially enables to evaluate a density of matter. We use this property todefine an implicit surface based on the physical properties of the particles system to reproduce the continuous aspect of matter. Those virtual materials can then be manipulated locally through interactions reproducing the handling of dough in the real world or through global shape deformation. Our approach is demonstrated by several prototypes running either on typical desktop workstation or in immersive environment system.

Ce mémoire présente une méthode de reconstruction de la surface d’un pare-brise à partir d’une image observée au travers de celui-ci. Cette image est déformée, car les rayons lumineux traversant le pare-brise subissent deux réfractions : une de chaque côté du verre. La déformation de l’image est dépendante de la forme du pare-brise, c’est donc cette donnée qui est utilisée pour résoudre le problème. La première étape est la construction d’un champ de vecteurs dans l’espace ambiant à partir des déviations des rayons lumineux passant par le pare-brise. Elle repose sur la loi de la réfraction de Snell-Descartes et sur des hypothèses simplificatrices au sujet de la courbure et de l’épaisseur du pare-brise. Le vecteur en un point de ce champ correspond à une prédiction du vecteur normal à la surface, sous l’hypothèse que celle-ci passe par le point en question. La deuxième étape est de trouver une surface compatible avec le champ de vecteurs obtenu. Pour y arriver, on formule un problème de minimisation où la donnée minimisée est la différence entre les vecteurs normaux à la surface et ceux construits à partir des mesures du système d’inspection. Il en résulte une équation d’Euler-Lagrange non linéaire à laquelle on impose des conditions de Dirichlet. Le graphe de la solution à ce problème est alors la surface recherchée. La troisième étape est une méthode de point fixe pour résoudre l’équation d’Euler-Lagrange. Elle donne une suite d’équations de Poisson linéaires dont la limite des solutions respecte l’équation non linéaire étudiée. On utilise le théorème du point fixe de Banach pour obtenir des conditions suffisantes d’existence et d’unicité de la solution, qui sont aussi des conditions suffisantes pour lesquelles la méthode de point fixe converge. / This Master’s thesis presents a method for the reconstruction of a windshield surface using an image observed through it. This image is distorted because the light rays passing through the windshield undergo two refractions : one on each side of the glass. The distortion depends on the windshield shape and therefore this data is used to solve the problem. The first step is the construction of a vector field in the ambient space, from the deviations of the light rays passing through the windshield. This step relies on the Snell-Descartes refraction law and on simplifying assumptions regarding the curvature and thickness of a windshield. A vector at a point of this field corresponds to a prediction of the surface normal vector at this point, under the hypothesis that this point lies on the surface. The second step is to find a surface that is compatible with the obtained vector field. For this purpose, a minimisation problem is formulated for which the minimized variable is the difference between the surface normal vector and the one deduced from the system’s measurements. This leads to a nonlinear Euler- Lagrange equation for which the Dirichlet boundary conditions are imposed. The graph of the solution is the desired surface. The third step is a fixed-point method to solve the Euler- Lagrange equation. At the center of this method is a sequence of linear Poisson equations, each giving an approximating solution. It is shown that the limit of this sequence of solutions respects the original nonlinear equation. The Banach fixed-point theorem is used to get sufficient existence and uniqueness conditions, that are also sufficient conditions under which the proposed fixed-point method converges.

L'utilisation de grands télescopes rend de plus en plus nécessaire l'emploi de l'optique adaptative qui permet de corriger l'effet de la turbulence atmosphérique. Toutefois cette technique est limitée par le nombre de sources de référence. L'étoile laser permet de pallier ce manque en créant artificiellement une source lumineuse, que l'on peut placer à volonté sur la voûte céleste, au-dessus des couches turbulentes. Or, par cette technique, on ne mesure que les déformations des images mais pas leur déplacement qui est pourtant l'effet le plus important. L'étoile laser polychromatique propose de le corriger également, à partir de la différence chromatique du tilt atmosphérique. Cette mesure différentielle nécessite une grande précision et sa faisabilité n'avait pas encore été démontrée. Pour cela, j'ai conçu et réalisé une expérience dénommée MaTilD (Manipulation de Tilt Différentiel). Le signal à mesurer étant très faible, j'ai développé deux traitements distincts : i) l'estimation des angles d'arrivée par mesure du centre de gravité des images, ii) l'estimation du tilt de la surface d'onde par ajustement d'un modèle sur les images. Le premier traitement m'a permis de mettre en évidence l'existence du chromatisme du tilt. Mais la précision obtenue est inférieure à ce que prédit l'étude théorique que j'en ai faite. Le but du second algorithme est donc d'améliorer cette précision en s'affranchissant d'une partie des limitations de la mesure du centre de gravité : fenêtrage, chevauchement des images, sensibilité élevée au bruit, ... On est alors dans le cadre général de la minimisation de fonctions non-linéaires dans un espace multidimensionnel (typiquement plusieurs dizaines de paramètres). J'ai contribué au développement et aux tests d'une méthode permettant de réduire significativement le nombre de dimensions de cet espace.