A triangulação de Delaunay de um conjunto de pontos é uma importante entidade geométrica cujas aplicações abrangem diversas áreas da ciência. Triangulações regulares, que podem ser vistas como uma generalização da triangulação de Delaunay, onde pesos são associados aos vértices, também têm sido aplicadas em diversos problemas como reconstrução a partir de nuvens de pontos [5], geração de malha [12], modelagem molecular [7] e muitos outros. Apesar de ser muito utilizada, a fundamentação teórica referente à triangulação regular ainda não está tão desenvolvida quanto para triangulação de Delaunay. Por exemplo, pouco se sabe a respeito da dinâmica de uma triangulação regular [22] quando os pesos associados aos vértices mudam. Este trabalho tem como objetivo principal desenvolver um arcabouço teórico e computacional que permita representar uma triangulação qualquer como uma triangulação regular. Para isso, um estudo da dinâmica das operações de flip frente à variação de pesos nos vértices deve ser realizado. Este estudo tem como base o mapeamento da triangulação em um politopo que define os possíveis pesos para os vértices. Tal politopo pode ser obtido por meio de um sistema de inequações que gera um problema de programação linear cuja solução fornece os pesos adequados. A transformação de uma triangulação qualquer em triangulação regular permite o desenvolvimento de novas técnicas de morphing entre malhas e algoritmos para modelar níveis de detalhe, sendo este mais um objetivo deste trabalho / Delaunay triangulation of a set of points is an important geometrical entity whose applications encompass a range of scientfic fields. Regular triangulations, which can be seen as a generalization of Delaunay triangulation where weights are assigned to vertices, have also been widely employed in several problems, as for example mesh reconstruction from point clouds [5], mesh generation [12] and molecular modelling [7]. In spite of their applicability, the theoretical background of regular triangulations is not so developed as the theory of Delaunay triangulation. For example, the dynamic of regular triangulation is not completely known when the vertices weights change [22]. This work aims at developing a computational and theoretical framework that allow to represent a given triangulation as a regular triangulation. In this context, an investigation into the dynamic of edge ip operations regarding changes in the vertices weight must be accomplished. This investigation is based on mapping the triangulation in a polytope that defines the space of vertices weights. Such polytope can be built from an inequation system that can be associate to a linear program problem whose solution supplies the appropriated weights. By representing a triangulation as a regular triangulation one can conceive a new mesh morphing scheme and level of detail algorithm, being this another goal of this work

Técnicas para gerar malhas triangulares ou tetraedrais a partir de imagens, ou assumem como entrada uma imagem pré-processada, ou geram uma malha sem distinguir as diferentes estruturas contidas na imagem. O pré-processamento e a ausência de estruturas bem definidas podem apresentar dificuldades na utilização das malhas geradas em algumas aplicações, tais como simulações numéricas. Neste trabalho, apresentamos uma nova técnica que elimina a necessidade do pré-processamento embutindo a segmentação dentro do processo de geração de malha. Além disto, a técnica proposta considera critérios de qualidade nas malhas geradas, mostrando-se apropriada para aplicações de simulação numérica assim como modelagem de imagens com malhas / Techniques devoted to generate triangular or tetrahedral meshes from images either take as starting point a pre-processed image or generate a mesh without distinguishing different structures contained in the image. The pre-process and the absence of well defined structures may impose difficulties in using the resulting mesh in some applications as, for example, numerical simulations. In this work, we present a new technique that aims at eliminating the need for pre-processing by building the segmentation into the mesh generation process. Furthermore, the proposed technique consider quality criteria in the generated meshes, being appropriated for applications in numerical simulation as well as in image modeling

La numérisation est un procédé qui consiste à enregistrer un objet dans un ordinateur pour pouvoir ensuite le manipuler à l'aide d'outils informatiques. Nous nous intéressons dans ce manuscrit à la numérisation d'objets tridimensionnels. Il s'agit tout d'abord d'enregistrer leur forme. De nombreuses méthodes ont été développées pour répondre à ce problème, et nous nous concentrerons sur les objets représentés par des maillages. Sur ces objets, il est alors utile de pouvoir représenter des attributs tels que la couleur, la température ou la charge électrique, selon l'application. Nous proposons deux approches complémentaires pour aborder ce problème. La première est fondée sur le placage de textures. Cette technique consiste à déplier (paramétrer) le maillage à plat sur une image dans laquelle l'attribut est stocké. Une valeur récupérée dans l'image est ainsi associée à chaque point de l'objet. Nous proposerons une méthode permettant de masquer l'artéfact des coutures qui est inhérent à cette technique. Déplier le maillage nécessite qu'il soit de bonne qualité, ce qui n'est pas toujours le cas. Nous décrivons donc également dans un second temps une approche de l'échantillonnage d'une surface via un diagramme de Voronoï restreint. Nous expliquons en particulier comment calculer efficacement un tel objet et comment l'optimiser par rapport à un critère de qualité. Ces résultats sont ensuite appliqués au problème de l'ajustement de surfaces / Digitalisation is an operation which consists in storing an object in a computer for further manipulation using data processing tools. In this document, we are interested in the digitalisation of three-dimensional objects. It is first a matter of recording the shape of the object. Many methods have been developed to address this problem, and we will focus on objects described as meshes. On such objects the storage of attributes like colour, temperature or electrical charge is often useful, depending on the application. We will describe two complementary approaches to deal with this issue. The first one relies on texture mapping. This technique consists in unfolding ? parametrising ? the mesh on a flat image in which the attribute is stored. A value recovered from the image can therefore be associated with each point of the object. We will describe a method which hides the seam artifact, commonly encountered using this technique. Unfolding the mesh demands that its quality be good, which is not always the case. We thus secondly describe a surface sampling method based on a restricted Voronoï diagram. We especially detail how to efficiently compute such an object and how to optimise it with respect to some quality measure. These results are then applied to the surface fitting problem

Robert Delaunay (1885-1941) est l’un des artistes français les plus présents à Berlin à l’aube de la Première guerre mondiale. Avec l’aide de Herwarth Walden (1878-1941), directeur de la revue et galerie Der Sturm, l’artiste acquiert rapidement une solide réputation dans la capitale allemande, où il expose une quarantaine de toiles au cours de la seule année 1913, tandis qu’il diffuse abondamment ses propres textes théoriques et ceux de ses amis Guillaume Apollinaire (1880-1918) et Blaise Cendrars (1887-1961). Le peintre français suscite bientôt l’engouement de certains artistes berlinois, nombreux à l’avoir rencontré lors de ses deux voyages en Allemagne avant la guerre. Pour une large partie de la recherche, ce succès s’expliquerait par un « malentendu productif » : les artistes de la capitale allemande auraient détourné l’œuvre de Delaunay dans un sens germanique, appréciant sa peinture pour des raisons étrangères à ses intentions initiales. Contestant cette hypothèse – variante de celle, pluriséculaire, de l’incompatibilité par nature des goûts allemands et français – nous proposons d’envisager la réception berlinoise de Delaunay dans une perspective micro-historique, en nous intéressant au regard porté sur lui par trois artistes : Ludwig Meidner (1884-1966), Lyonel Feininger (1871-1956) et Bruno Taut (1880-1936). Après avoir mis en exergue les discours possiblement « entendus » par ceux-ci autour de l’œuvre du peintre français en Allemagne, nous nous intéressons à la trajectoire individuelle de chacun d’entre eux, mettant en évidence la profondeur des liens qui unissent finalement les avant-gardes désignées sous les termes d’orphisme et d’expressionnisme. / Robert Delaunay (1885-1941) is among the French artists that are the most involved in Berlin at the dawn of the World War I. Thanks to Herwarth Walden (1878-1941), who is the director of the magazine and the gallery Der Sturm, the artist quickly earns a solid reputation in the German capital city where he exhibits around forty paintings in 1913 alone, while widely circulating his own theoretical texts as well as those of his friends Guillaume Apollinaire (1880-1918) and Blaise Cendrars (1887-1961). The French painter soon spurs the interest of some Berlin artists, many of whom have met him during his two trips to Germany before the war. For an extensive part of the research, this success could be explained by a “working misunderstanding”: the artists of the German capital city supposedly twisted Delaunay’s work in a Germanic sense, appreciating his painting for reasons that were not related to his initial intents. We contest this hypothesis – which is a variant of the centuries-old hypothesis that states a natural incompatibility between German and French tastes – we suggest to consider the Berlin welcome of Delaunay in a micro-historical perspective by focusing on three artist’s point of view about him: Ludwig Meidner (1884-1966), Lyonel Feininger (1871-1956) and Bruno Taut (1880-1936). After underlining the speeches they possibly “heard” surrounding the French painter’s work in Germany, we focus on each artist’s individual path, showcasing the depths of the links that join actually the avant-gardes that are coined under the terms of orphism and expressionism.

Técnicas para gerar malhas triangulares ou tetraedrais a partir de imagens, ou assumem como entrada uma imagem pré-processada, ou geram uma malha sem distinguir as diferentes estruturas contidas na imagem. O pré-processamento e a ausência de estruturas bem definidas podem apresentar dificuldades na utilização das malhas geradas em algumas aplicações, tais como simulações numéricas. Neste trabalho, apresentamos uma nova técnica que elimina a necessidade do pré-processamento embutindo a segmentação dentro do processo de geração de malha. Além disto, a técnica proposta considera critérios de qualidade nas malhas geradas, mostrando-se apropriada para aplicações de simulação numérica assim como modelagem de imagens com malhas / Techniques devoted to generate triangular or tetrahedral meshes from images either take as starting point a pre-processed image or generate a mesh without distinguishing different structures contained in the image. The pre-process and the absence of well defined structures may impose difficulties in using the resulting mesh in some applications as, for example, numerical simulations. In this work, we present a new technique that aims at eliminating the need for pre-processing by building the segmentation into the mesh generation process. Furthermore, the proposed technique consider quality criteria in the generated meshes, being appropriated for applications in numerical simulation as well as in image modeling

A triangulação de Delaunay de um conjunto de pontos é uma importante entidade geométrica cujas aplicações abrangem diversas áreas da ciência. Triangulações regulares, que podem ser vistas como uma generalização da triangulação de Delaunay, onde pesos são associados aos vértices, também têm sido aplicadas em diversos problemas como reconstrução a partir de nuvens de pontos [5], geração de malha [12], modelagem molecular [7] e muitos outros. Apesar de ser muito utilizada, a fundamentação teórica referente à triangulação regular ainda não está tão desenvolvida quanto para triangulação de Delaunay. Por exemplo, pouco se sabe a respeito da dinâmica de uma triangulação regular [22] quando os pesos associados aos vértices mudam. Este trabalho tem como objetivo principal desenvolver um arcabouço teórico e computacional que permita representar uma triangulação qualquer como uma triangulação regular. Para isso, um estudo da dinâmica das operações de flip frente à variação de pesos nos vértices deve ser realizado. Este estudo tem como base o mapeamento da triangulação em um politopo que define os possíveis pesos para os vértices. Tal politopo pode ser obtido por meio de um sistema de inequações que gera um problema de programação linear cuja solução fornece os pesos adequados. A transformação de uma triangulação qualquer em triangulação regular permite o desenvolvimento de novas técnicas de morphing entre malhas e algoritmos para modelar níveis de detalhe, sendo este mais um objetivo deste trabalho / Delaunay triangulation of a set of points is an important geometrical entity whose applications encompass a range of scientfic fields. Regular triangulations, which can be seen as a generalization of Delaunay triangulation where weights are assigned to vertices, have also been widely employed in several problems, as for example mesh reconstruction from point clouds [5], mesh generation [12] and molecular modelling [7]. In spite of their applicability, the theoretical background of regular triangulations is not so developed as the theory of Delaunay triangulation. For example, the dynamic of regular triangulation is not completely known when the vertices weights change [22]. This work aims at developing a computational and theoretical framework that allow to represent a given triangulation as a regular triangulation. In this context, an investigation into the dynamic of edge ip operations regarding changes in the vertices weight must be accomplished. This investigation is based on mapping the triangulation in a polytope that defines the space of vertices weights. Such polytope can be built from an inequation system that can be associate to a linear program problem whose solution supplies the appropriated weights. By representing a triangulation as a regular triangulation one can conceive a new mesh morphing scheme and level of detail algorithm, being this another goal of this work

Les travaux présentés et discutés dans cette thèse ont pour objectif de proposer plusieurs solutions au problème de l’analyse et du clustering de nuages de points en basse dimension. Ces solutions s’appuyent sur l’analyse de triangulations de Delaunay. Deux types d’approches sont présentés et discutés. Le premier type suit une approche en trois-passes classique: 1) la construction d’un graphe de proximité contenant une information topologique, 2) la construction d’une information statistique à partir de ce graphe et 3) la suppression d’éléments inutiles au regard de cette information statistique. L’impact de différentes measures sur le clustering ainsi que sur la reconnaissance de caractères est discuté. Ces mesures s’appuyent sur l’exploitation du complexe simplicial et non pas uniquement sur celle du graphe. Le second type d’approches est composé d’approches en une passe extrayant des clusters en même temps qu’une triangulation de Delaunay est construite. / This thesis aims at proposing and discussing several solutions to the problem of low-dimensional point cloudanalysis and clustering. These solutions are based on the analysis of the Delaunay triangulation.Two types of approaches are presented and discussed. The first one follows a classical three steps approach:1) the construction of a proximity graph that embeds topological information, 2) the construction of statisticalinformation out of this graph and 3) the removal of pointless elements regarding this information. The impactof different simplicial complex-based measures, i.e. not only based on a graph, is discussed. Evaluation is madeas regards point cloud clustering quality along with handwritten character recognition rates. The second type ofapproaches consists of one-step approaches that derive clustering along with the construction of the triangulation.

Dans cette thèse, nous exploitons les outils de la théorie des probabilités et de la géométrie stochastique pour analyser des algorithmes opérant sur les tessellations. Ce travail est divisé entre deux thèmes principaux, le premier traite de la navigation dans une tessellation de Delaunay et dans son dual, le diagramme de Voronoï avec des implications pour les algorithmes de localisation spatiales et de routage dans les réseaux en ligne. Nous proposons deux nouveaux algorithmes de navigation dans la triangulation de Delaunay, que nous appelons Pivot Walk et Cone Walk. Pour Cone Walk, nous fournissons une analyse en moyenne détaillée avec des bornes explicites sur les propriétés de la pire marche possible effectuée par l'algorithme sur une triangulation de Delaunay aléatoire d'une région convexe bornée. C'est un progrès significatif car dans l'algorithme Cone Walk, les probabilités d'utiliser un triangle ou un autre au cours de la marche présentent des dépendances complexes, dépendances inexistantes dans d'autres marches. La deuxième partie de ce travail concerne l'étude des propriétés extrémales de tessellations aléatoires. En particulier, nous dérivons les premiers et derniers statistiques d'ordre pour les boules inscrites dans les cellules d'un arrangement de droites Poissonnien; ce résultat a des implications par exemple pour le hachage respectant la localité. Comme corollaire, nous montrons que les cellules minimisant l'aire sont des triangles. / In this thesis, we leverage the tools of probability theory and stochastic geometry to investigate the behavior of algorithms on geometric tessellations of space. This work is split between two main themes, the first of which is focused on the problem of navigating the Delaunay tessellation and its geometric dual, the Voronoi diagram. We explore the applications of this problem to point location using walking algorithms and the study of online routing in networks. We then propose and investigate two new algorithms which navigate the Delaunay triangulation, which we call Pivot Walk and Cone Walk. For Cone Walk, we provide a detailed average-case analysis, giving explicit bounds on the properties of the worst possible path taken by the algorithm on a random Delaunay triangulation in a bounded convex region. This analysis is a significant departure from similar results that have been obtained, due to the difficulty of dealing with the complex dependence structure of localized navigation algorithms on the Delaunay triangulation. The second part of this work is concerned with the study of extremal properties of random tessellations. In particular, we derive the first and last order-statistics for the inballs of the cells in a Poisson line tessellation. This result has implications for algorithms involving line tessellations, such as locality sensitive hashing. As a corollary, we show that the cells minimizing the area are triangles.

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.

Cette thèse explore divers aspects des cartes aléatoires par l'étude de trois modèles. Dans un premier temps, nous examinons les propriétés d’une mesure définie sur l’ensemble des triangulations de Delaunay planaires comportant n sommets, qui est un modèle de cartes où les arêtes sont décorées par des angles. Nous montrons ainsi que la mesure est égale à la mesure de Weil-Petersson sur l’espace des modules des surfaces de Riemann planaires marquées. Sont aussi montrées deux propriétés de la mesures, premiers pas d'une étude de la limite continue de ce modèle. Dans un deuxième temps, nous définissons des fonctions de corrélations sur les graphes de Strebel planaires isopérimétriques à n faces, qui sont des cartes métriques trivalentes. Les périmètres des faces sont fixés. Nous recourons au théorème de Kontsevich pour calculer les fonctions de corrélations en termes de nombres d’intersection de classes de Chern sur l’espace des modules des surfaces de Riemann. Pour la fonction à une face marquée, la limite des grandes cartes est examinée via l’approximation du point-selle, pour différents régimes du périmètre de la face marquée, et nous déduisons le régime où le comportement de la fonction de corrélation n’est pas trivial. Les fonctions de corrélations peuvent être calculées de manière systématique par la récurrence topologique. Partant, nous calculons la courbe spectrale de notre modèle, ce qui nous permet de montrer qu’il existe une courbe spectrale critique. Nous déduisons de cette courbe critique que la limite continue des graphes de Strebel isopérimétriques est un modèle minimal de type (3,2), habillé par la théorie de Liouville. Cela correspond bien à la gravité pure. Enfin, nous abordons la question des symétries dans le modèle d’Ising sur cartes aléatoires. Certaines fonctions de corrélations de ce modèle comptent le nombre de cartes bicolores avec des faces marquées, les bords, ayant des conditions aux bords mixtes, calculées par récurrence à partir de la courbe spectrale du modèle. Nous prouvons ici que, pour des courbes spectrales génériques, les fonctions de corrélations des cartes à un bord mixte sont symétriques par rotation et par inversion du bord mixte. Nous décrivons ensuite les conséquences de telles symétries, suggérant une possible reformulation du modèle en termes de chaînes de spins. / This thesis explore several aspects of random maps through the study of three models. First, we examine the properties of a measure defined on the set of planar Delaunay triangulations with n vertices, a model in which the edges of the maps are decorated with angles. We show that the measure is the Weil-Petersson volume form on the moduli space of planar Riemann surfaces having n marked points. Two other properties, first steps toward the continuous limit study of the model, are also shown. Second, we define correlation functions on isoperimetric planar Strebel graphs with n faces, which are trivalent maps whose edges are decorated by positive lengths, and whose faces have a fixed perimeter. Kontsevich's theorem allows us to compute the correlation functions in terms of the intersection numbers of Chern classes of moduli space of Riemann surfaces. The continuous limit of the one-point function is computed in different regimes for the perimeter of the marked face via the saddle-point approximation. We identify the regime in which the behaviour of the one-point function is not trivial. The correlation functions can be computed in a systematic way by the Topological Recursion. To do so, we compute the spectral curve of the model, and show that there exists a critical spectral curve. We deduce from the latter that the continuous limit of isoperimetric Strebel graphs is a (3,2) minimal model dressed by Liouville theory: it corresponds to pure gravity. Last, we address the problem of symmetries in the Ising model on random maps. Some correlation functions of this model count the bi-colored maps with marked faces having mixed boundary conditions. They are computed via a recursive formula and the spectral curve of the model. We prove here that the correlation functions of maps with one mixed boundary, computed from the recursive relation with generic spectral curve, are invariant under rotation and inversion of the mixed boundary. We describe the consequences of such symmetries, suggesting a possible reformulation of the model in terms of spin chains.