The medial axis skeleton is a thin line graph that preserves the topology of a region. The skeleton has often been cited as a useful representation for shape description, region interpretation, and object recognition. Unfortunately, the computation of the skeleton is extremely sensitive to variations in the bounding contour. In this paper, we describe a robust method for computing the medial axis skeleton across a variety of scales. The resulting scale-space is parametric with the complexity of the skeleton, where the complexity is defined as the number of branches in the skeleton.

No description available.

In motion planning, high clearance paths are favorable due to their increased visibility and reduction of collision risk such as the safety of problems involving: human- robot cooperation. One popular approach to solving motion planning problems is the Probabilistic Roadman Method (PRM), which generates a graph of the free space of an environment referred to as a roadmap. In this work we describe a new approach to making high clearance paths when using PRM The medial axis is useful for this since it represents the set of points with maximal clearance and is well defined in higher dimensions. However it can only be computed exactly in workspace. Our goal is to generate roadmaps with paths following the medial axis of an environment without explicitly computing the medial axis. One of the major steps of PRM is local planning: the planning of motion between two nearby nodes PRMs have been used to build roadmaps that have nodes on the medial axis but so far there has been no local planner method proposed for connecting these nodes on the medial axis. These types of high clearance motions are desirable and needed in many robotics applications. This work proposes Medial Axis Local Planner (MALP), a local planner which attempts to connect medial axis configurations via the medial axis. The recursive method takes a simple path between two medial axis configurations and attempts to deform the path to fit the medial axis. This deformation creates paths with high clearance and visibility properties. We have implemented this local planner and have tested it in 2D and 3D rigid body and 8D and 16D fixed base articulated linkage environments. We compare MALP with a straight-line local planner (SL), a typical local planer used in motion planning that interpolated along a line in the planning space. Our results indicate that MALP generated higher clearance paths than SL local planning. As a result, MALP found more connections and generated fewer connected components as compared to connecting the same nodes using SL connections. Using MALP connects noes on the medial axis, increasing the overall clearance of the roadmap generated.

The Medial Axis Transform (MAT) is a powerful tool for shape analysis and manipulation. Traditional methods for working with shapes usually define shapes as boundaries between some “inside” and some “outside” region. While this definition is simple and intuitive, it does not lend itself well to the construction of algorithms for a number of seemingly simple tasks such as classification, deformation, and collision detection. The MAT is an alternative representation of shape that defines the “inside” region by its center and thickness. We present a method of constructing the MAT which overcomes a significant limitation of its use with real-world data: instability. As classically defined, the MAT is unstable with respect to the shape boundary that it represents. For data sources afflicted by noise this is a serious problem. We propose an algorithm, LSMAT, which constructs a stable least squares approximation to the MAT. / Graduate

In this thesis, we propose a new representation, which we name Interaction Bisector Surface (IBS), that can describe the general nature of spatial relationship. We show that the IBS can be applied in 3D scene analysis, retrieval and synthesis. Despite the fact that the spatial relationship between different objects plays a significant role in describing the context, few works have focused on elaborating a representation that can describe arbitrary interactions between different objects. Previous methods simply concatenate the individual state vectors to produce a joint space, or only use simple representations such as relative vectors or contacts to describe the context. Such representations do not contain detailed information of spatial relationships. They cannot describe complex interactions such as hooking and enclosure. The IBS is a data structure with rich information about the interaction. It provides the topological, geometric and correspondence features that can be used to classify and recognize interactions. The topological features are at the most abstract level and it can be used to recognize spatial relationships such as enclosure, hooking and surrounding. The geometric features encode the fine details of interactions. The correspondence feature describes which parts of the scene elements contribute to the interaction and is especially useful for recognizing character-object interactions. We show examples of successful classification and retrieval of different types of data including indoor static scenes and dynamic scenes which contain character-object interactions. We also conduct an exhaustive comparison which shows that our method outperforms existing approaches. We also propose a novel approach to automatically synthesizing new interactions from example scenes and new objects. Given an example scene composed of two objects, the open space between the objects is abstracted by the IBS. Then, an translation, rotation and scale equivariant feature called shape coverage feature, which encodes how the point in the open space is surrounded by the environment, is computed near the IBS and around the open space of the new objects. Finally, a novel scene is synthesized by conducting a partial matching of the open space around the new objects with the IBS. Using our approach, new scenes can be automatically synthesized from example scenes and new objects without relying on label information, which is especially useful when the data of scenes and objects come from multiple sources.

L'analyse d'images est devenue ces dernières années une discipline de plus en plus riche de l'informatique. La topologie discrète propose un panel d'outils incontournables dans le traitement d'images, notamment grâce à l'outil du squelette, qui permet de simplifier des objets tout en conservant certaines informations intactes. Cette thèse étudie comment certains outils de la topologie discrète, notamment les squelettes, peuvent être utilisés pour le traitement d'images de matériaux.Le squelette d'un objet peut être vu comme une simplification d'un objet, possédant certaines caractéristiques identiques à celles de l'objet original. Il est alors possible d'étudier un squelette et de généraliser certains résultats à l'objet entier. Dans une première partie, nous proposons une nouvelle méthode pour conserver, dans un squelette, certaines caractéristiques géométriques de l'objet original (méthode nécessitant un paramètre de filtrage de la part de l'utilisateur) et obtenir ainsi un squelette possédant la même apparence que l'objet original. La seconde partie propose de ne plus travailler avec des objets constitués de voxels, mais avec des objets constitués de complexes cubiques. Dans ce nouveau cadre, nous proposons de nouveaux algorithmes de squelettisation, dont certains permettent de conserver certaines caractéristiques géométriques de l'objet de départ dans le squelette, de façon automatique (aucun paramètre de filtrage ne doit être donné par l'utilisateur). Nous montrerons ensuite comment un squelette, dans le cadre des complexes cubiques, peut être décomposé en différentes parties. Enfin, nous montrerons nos résultats sur différentes applications, allant de l'étude des matériaux à l'imagerie médicale / These last years, the domain of image analysis has drastically evolved. Digital topology offer a set of tools adapted to image analysis, especially the skeletonization process (also called homotopic thinning) which can simplify input data while keeping specific information untouched. In this thesis, we focus on how digital topology, especially skeletons, can help material image analysis.The goal of a skeletonization process is to remove unnecessary information from an input, and provide a simplified object, called the skeleton, having the same characteristics than the original data. It is then possible to perform some computations on the skeleton and generalise their results to the original data. In the first part of this thesis, we propose some new tools for preserving, during skeletonization, important geometrical features of the original data, and obtain a skeleton with the same visual appearance than the input.In the second part, we present the cubical complex framework, where objects are no more made only of voxels. We propose in this framework new skeletonization algorithms, some of them preserving automatically the visual aspect of the input during the thinning process (no filtering parameter from the user is required). We then show how a skeleton, in the cubical complexes framework, can be decomposed into basic parts, and we show some applications of these algorithms to material image analysis and medical image analysis

The desktop publishing revolution of the 1980s is currently repeating itself in 3D, referred to as desktop manufacturing. Online services such as Shapeways have become available, making personalized manufacturing on cutting edge additive manufacturing (AM) technologies accessible to a broad audience. Affordable desktop printers will soon take over, enabling people to fabricate / Engineering and Applied Sciences

[pt] O eixo medial é uma descrição compacta de um objeto que preserva sua topologia e induz naturalmente uma discretização da sua forma como união de bolas. O estudo de união de bolas possui aplicações em diversas áreas da Matemática, em particular na Geometria Computacional onde se usa, por exemplo, para reconstrução de curvas e superfícies. Este trabalho pretende utilizar união de bolas para simular deformações a partir do eixo medial, apresentando conceitos e teoremas a fim de construir algoritmos para a extração do eixo medial em R3. A deformação será, então, definida por movimentos locais das bolas ao longo das direções do eixo medial. Este trabalho contém resultados com movimentos simples, em um programa que utiliza a biblioteca CGAL / [en] The medial axis is a compact description of an object that preserves its topology and naturally induces a discretisation of its forma in terms of union of balls. The study of union of balls has applications in various areas of Mathematics, in particular in Computational Geometry where it is used for curve and surface reconstruction. This work pretends to use union of balls in order to simulate deformations described on the medial axis. It introduces concepts and theorems in order to setup algorithms for medial axis extraction in R3. The deformation will thus be defined by local ball moves along the medial axis directions. This work contains results with simple movements, in a program that uses the CGAL library

[pt] O estudo computacional de uniões de bolas possui aplicações em diversas áreas da Matemática. O objetivo principal deste trabalho é propor uma simplificação de união de bolas em R2 através de um movimento que obedece as direções do eixo medial, procurando preservar os grandes elementos geométricos da união de bolas. A desconexão ou não das formas é um aspecto essencial da evolução. Em alguns casos, pode significar uma divisão importante do objeto. Em outros, pode ser indesejada, pois gostaríamos de ter uma versão conexa simplificada da forma. / [en] The computational study of unions of balls has applications in several domains of the Mathematics. The purpose of this dissertation is to propose a simplification of the union of balls in R2 through a movement that obeys the direction of the medial axis in order to simplify it, maintaining the major geometric elements of its shape. The disconnection of the shape is an essential property of the evolution. In some cases, it could mean an important division of the object. In others, it may be undesirable because we would like to have a simplified version connected of this shape.

Die Skelettextraktion ist besonders in der Formanalyse ein wichtiges Werkzeug. Im Rahmen des Forschungsprojektes ’Extraktion fertigungsrelevanter Merkmale aus 3D-Daten umformtechnischer Bauteile zur featurebasierten Fertigungsprozessgestaltung’ als Kooperationsprojekt zwischen der Professur Graphische Datenverarbeitung und Visualisierung an der Technischen Universität Chemnitz und des Fraunhofer-Institut für Werkzeugmaschinen und Umformtechnik Chemnitz wurde diese zur Featureerkennung umgesetzt. Dieses Dokument gibt zunächst Einblick in grundlegende Verfahren und Problemstellungen einer solchen Extraktion. Die Ergebnisse mehrerer Forschungsschwerpunkte, die sich aus den zu untersuchenden Massivumformteilen ergaben, werden vorgestellt. Hierbei besonders interessant ist die robuste Extraktion von Kurvenskeletten bei Bauteilen mit nicht-zylindrischer Hauptform, sowie bei Bauteilen mit Nebenformelementen. Desweiteren werden Nachverarbeitung und Auswertung des Kurvenskeletts, sowie verwandte Forschungsarbeiten und -ergebnisse diskutiert.