Cette thèse traite de l'analyse de nuages de points 3D désorganisé et s'appuie sur deux outils : un algorithme de partitionnement efficace inspiré des C-moyennes floues d'une part, et des outils de filtrage morphologique de représentation à base de triangulation de Delaunay d'autre part. Le cadre applicatif essentiel est la navigation autonome en robotique mobile en environnement inconnu, c'est-à-dire dans modèle. Mais la méthodologie générique développée a été appliquée à d'autres types d'environnements, notamment plus structurés.

ABSTRACT Research in GIScience has identified agent-based simulation methodologies as effective in the study of complex adaptive spatial systems (CASS). CASS are characterized by the emergent nature of their spatial expressions and by the changing relationships between their constituent variables and how those variables act on the system's spatial expression over time. Here, emergence refers to a CASS property where small-scale, individual action results in macroscopic or system-level patterns over time. This research develops and executes a spatially-explicit agent based model of Muscovy Duck home range behavior. Muscovy duck home range behavior is regarded as a complex adaptive spatial system for this research, where this process can be explained and studied with simulation techniques. The general animal movement model framework presented in this research explicitly considers spatial characteristics of the landscape in its formulation, as well as provides for spatial cognition in the behavior of its agents. Specification of the model followed a three-phase framework, including: behavioral data collection in the field, construction of a model substrate depicting land cover features found in the study area, and the informing of model agents with products derived from field observations. This framework was applied in the construction of a spatially-explicit agent-based model (SE-ABM) of Muscovy Duck home range behavior. The model was run 30 times to simulate point location distributions of an individual duck's daily activity. These simulated datasets were collected, and home ranges were constructed using Characteristic Hull Polygon (CHP) and Minimum Convex Polygon (MCP) techniques. Descriptive statistics of the CHP and MCP polygons were calculated to characterize the home ranges produced and establish internal model validity. As a theoretical framework for the construction of animal movement SE-ABM's, and as a demonstration of the potential of geosimulation methodologies in support of animal home range estimator validation, the model represents an original contribution to the literature. Implications of model utility as a validation tool for home range extents as derived from GPS or radio telemetry positioning data are discussed.

SectionBuilder is an innovative finite element based tool, developed for analysis and design of composite beam cross-sections. The tool can handle the cross-sections with parametric shapes and arbitrary configurations. It can also handle arbitrary lay-ups for predefined beam cross-section geometries in a consistent manner. The material properties for each layer of the cross-section can be defined on the basis of the design requirements. This tool is capable of dealing with multi-cell composite cross-sections with arbitrary lay-ups. It has also the benefit of handling the variation of thickness of skin and D-spars for beams such as rotor blades. A typical cross-section is considered as a collection of interconnected walls. Walls with arbitrary lay-ups based on predefined geometries and material properties are generated first. The complex composite beam cross-sections are developed by connecting the walls using various types of connectors. These connectors are compatible with the walls, i.e., the thickness of the layers of the walls must match with those of the connectors at the place of connection. Cross-sections are often reinforced by core material for constructing realistic rotor blade cross-sections. The tool has the ability to integrate core materials into the cross-sections. A mapped mesh is considered for meshing parametric shapes, walls and various connectors, whereas a free mesh is considered for meshing the core materials. A new algorithm based on the Delaunay refinement algorithm is developed for creating the best possible free mesh for core materials. After meshing the cross-section, the tool determines the sectional properties using finite element analysis. This tool computes sectional properties including stiffness matrix, compliance matrix, mass matrix, and principal axes. A visualization environment is integrated with the tool for visualizing the stress and strain distributions over the cross-section.

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.

This thesis presents a complete and fully automatic method for estimating the volume of an airbag, through all stages of its inflation, with multiple synchronized high-speed cameras. Using recorded contours of the inflating airbag, its visual hull is reconstructed with a novel method: The intersections of all back-projected contours are first identified with an accelerated epipolar algorithm. These intersections, together with additional points sampled from concave surface regions of the visual hull, are then Delaunay triangulated to a connected set of tetrahedra. Finally, the visual hull is extracted by carving away the tetrahedra that are classified as inconsistent with the contours, according to a voting procedure. The volume of an airbag's visual hull is always larger than the airbag's real volume. By projecting a known synthetic model of the airbag into the cameras, this volume offset is computed, and an accurate estimate of the real airbag volume is extracted. Even though volume estimates can be computed for all camera setups, the cameras should be specially posed to achieve optimal results. Such poses are uniquely found for different airbag models with a separate, fully automatic, simulated annealing algorithm. Satisfying results are presented for both synthetic and real-world data.

Orientador: Hugo Enrique Hernandez Figueroa / Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica e de Computação / Made available in DSpace on 2018-08-09T06:26:18Z (GMT). No. of bitstreams: 1 Hsu_AtilioClaudio_M.pdf: 6986419 bytes, checksum: 5d1120daa8d4126ad4a6fd84fd5ac188 (MD5) Previous issue date: 2007 / Resumo: Nesta dissertação apresenta-se o desenvolvimento e a implementação de algoritmos para geração de malhas adaptativas de elementos triangulares, visando o estudo de problemas de propagação eletromagnética em domínios bidimensionais. Foram implementadas duas técnicas de refinamento, uma baseada no método da troca de arestas denominado Delaunay e a outra baseada na técnica de suavização de Laplace. O gerador implementado leva em conta interfaces de curvatura arbitrária e, também, pode ser facilmente integrado aos programas desenvolvidos no Departamento de Microonda e Óptica (DMO) / Abstract: This work presents the development of algorithms for adaptive mesh generation of triangular elements applicable to electromagnetic propagation problems in bidimensional domains. Several techniques were used, such as edgeflip, known as Delaunay method, and the Laplacian¿s smoothing method. The program considers arbitrary curvature interfaces and can be easily integrated to the programs created in the Department of Microwaves and Optics (DMO) / Mestrado / Telecomunicações e Telemática / Mestre em Engenharia Elétrica

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.

The paper describes basic principles of the finite element method. Further, basic properties of triangulation are discussed. The thesis is primarily focused on the Delaunay and Greedy triangulation. Greedy triangulation is simple to implement, but may not produce the optimal shape of triangles. Delaunay method is used due to its robustness in a wide range of fields especially in computer graphics. This method is relatively easy to implement and provides triangles with high quality.

Les artistes apprécient les images vectorielles car elles sont compactes et facilement manipulables. Cependant, beaucoup d’artistes expriment leur créativité en dessinant, en peignant ou encore en prenant des photographies. Digitaliser ces contenus produit des images rasterisées. L’objectif de cette thèse est de convertir des images rasterisées en images vectorielles qui sont facilement manipulables. Nous avons formulé le problème de vectorisation comme un problème de minimisation d’énergie que nous avons défini par deux termes. Le premier terme, plutôt classique, mesure la fidélité de l’image vectorielle générée avec l’image rasterisée d’origine. La nouveauté principale est le second terme qui mesure la simplicité de l’image vectorielle générée. Le terme de simplicité est global et contient des variables discrètes, ce qui rend sa minimisation difficile. Nous avons proposé deux algorithmes de vectorisation : un pour la vectorisation de croquis et un autre pour la vectorisation multicouches d’images couleurs. Ces deux algorithmes commencent par extraire des primitives géométriques (un squelette pour les croquis et une segmentation pour les images couleurs) qu’ils assemblent ensuite pour former l’image vectorielle. Dans la dernière partie de la thèse, nous proposons un nouvel algorithme qui est capable de vectoriser des croquis sans étapes préliminaires : on extrait et assemble les primitives simultanément. Nous montrons le potentiel de ce nouvel algorithme pour une variété de problèmes de vision par ordinateur comme l’extraction de réseaux linéiques, l’extraction d’objets et la compression d’images. / Artists appreciate vector graphics for their compactness and editability. However many artists express their creativity by sketching, painting or taking photographs. Digitizing these images produces raster graphics. The goal of this thesis is to convert raster graphics into vector graphics that are easy to edit. We cast image vectorization as an energy minimization problem. Our energy is a combination of two terms. The first term measures the fidelity of the vector graphics to the input raster graphics. This term is a standard term for image reconstruction problems. The main novelty is the second term which measures the simplicity of the vector graphics. The simplicity term is global and involves discrete unknowns which makes its minimization challenging. We propose two stochastic optimizations for this formulation: one for the line drawing vectorization problem and another one for the color image vectorization problem. These optimizations start by extracting geometric primitives (skeleton for sketches and segmentation for color images) and then assembling these primitives together to form the vector graphics. In the last chapter we propose a generic optimization method for the problem of geometric shape extraction. This new algorithm does not require any preprocessing step. We show its efficiency in a variety of vision problems including line network extraction, object contouring and image compression.

Image segmentation plays an important role in medical image analysis. Many segmentation algorithms exist. Most of them produce data which are more or less not suitable for further surface extraction and anatomical modeling of human tissues. In this thesis, a novel segmentation technique based on the 3D Delaunay triangulation is proposed. A modified variational tetrahedral meshing approach is used to adapt a tetrahedral mesh to the underlying CT volumetric data, so that image edges are well approximated in the mesh. In order to classify tetrahedra into regions/tissues whose characteristics are similar, three different clustering schemes are presented. Finally, several methods for improving quality of the mesh and its adaptation to the image structure are also discussed.