[pt] Este trabalho apresenta um método para extração de malhas poligonais adaptativas em multi-resolução, a partir de objetos volumétricos. As principais aplicações da extração de malhas estão ligadas à área médica, dinâmica de fluidos, geociências, meteorologia, dentre outras. Nestas áreas os dados podem ser representados como objetos volumétricos. Nos dados volumétricos as informações estão representadas implicitamente, o que dificulta o processamento direto dos objetos que se encontram representados dentro do volume. A extração da malha visa obter uma representação explícita dos objetos, de modo a viabilizar o processamento dos mesmos. O método apresentado na tese procura extrair a malha a partir de processos de Simplicação e Refinamento. Durante a simplificação é extraída uma representação super amostrada do objeto (na mesma resolução do volume inicial), a qual é simplificada de modo a se obter uma malha base ou malha grossa, em baixa resolução, porém contendo a topologia correta do objeto. A etapa de refinamento utiliza a transformada de distâ ncia para obter uma representação da malha em multi-resolução, ou seja, a cada instante é obtida uma malha de maior resolução que vai se adaptando progressivamente à geometria do objeto. A malha final apresenta uma série de propriedades importantes, como boa razão de aspecto dos triângulos, converge para a superfície do objeto, pode ser aplicada tanto a objetos com borda quanto a objetos sem borda, pode ser aplicada tanto a superfície conexas quanto a não conexas, dentre outras. / [en] This work presents a method for extracting multiresolution adaptive polygonal meshes, from volumetric objects. Main aplications of this work are related to medical area, fluid dynamics, geosciences, metheorology and others. In these areas data may be represented as volumetric objects. Volumetric datasets are implicit representations of objects, so it s very dificult to apply directly any process to these objects. Mesh extraction obtains an explicit representation of the objetc, such that it s easier to process directly the objects. The presented method extracts the mesh from two main processes: Simplification and Refinement. The simplification step extracts a supersampled representation of the object (in the same volume resolution), and simplifies it in such a way to obtain a base mesh (or coarse mesh), in a low resolution, but containing the correct topology of the object. Refinement step uses the distance transform to obtain a multiresolution representation of the mesh, it means that at each instant it s obtained an adaptive higher resolution mesh. The final mesh presents a set of important properties, like good triangle aspect ratio, convergency to the object surface, may be applied as to objects with boundary and as to objects with multiple connected components, among others properties.

Diese Dissertation befasst sich mit der sensorgeführten Regelung von Industrierobotern zur Konturverfolgung. Beispiele dafür sind das robotergestützte Nähen, Entgraten oder das Auftragen von Dichtmasse entlang von Schweißnähten. Beim Nähen und Entgraten müssen während der Verfolgung der Kontur bestimmte Kontaktkräfte an möglicherweise nachgiebigen Werkstücken eingehalten werden. Dabei ist es in modernen Fertigungsprozessen wichtig, die Bewegung des Roboters mit wenig Einrichtaufwand vorzugeben. Dazu werden Sensorsysteme eingesetzt, die Bildinformationen und Kraftmessungen verarbeiten, um den Roboter mit gewünschter Kontaktkraft entlang sichtbarer Konturen eines Werkstückes zu führen. Der Fokus dieser Arbeit ist die Fusion der Sensordaten, um die Vorteile der einzelnen Sensoren in einer Aufgabe zu vereinen. Es werden Messwerte eines Kraft-Momenten Sensors, einer Kamera, eines Beschleunigungssensors und der kartesischen Position und Orientierung des Roboters verwendet. Zuerst wird die Berechnung der kartesischen Roboterposition untersucht. Es wird ein Beobachter vorgestellt, um unter Verwendung eines Beschleunigungssensors die Präzision des Positionssignales zu erhöhen. Anschließend wird das Kamerasystem untersucht und ein Verfahren vorgestellt, um Geschwindigkeit, Position und Orientierung des robotergeführten Werkzeuges entlang der Kontur vorzugeben. Danach wird auf die Ermittlung von Kontaktkräften eingegangen, wobei die Kompensation von Trägheitskräften mittels Beschleunigungssensoren untersucht wird. Der letzte Abschnitt befasst sich mit der Verbindung von bildgestützter Konturverfolgung und Kraftregelung an nachgiebigen Werkstücken. Durch die Nachgiebigkeit des Werkstückmaterials verformt sich die Kontur bei Kontakt. Durch bildgestützte Konturverfolgung wird eine Anpassung an diese Verformung vorgenommen -- somit besteht über die Verformbarkeit des Werkstückes eine Kopplung zwischen den beiden Regelkreisen. Diese Kopplung wird gelöst, indem auf Basis eines dynamischen Modells der Umgebung eine Kompensation der Werkstückverformung berechnet wird. Die Modellparameter zur Kompensation werden durch online Identifikation ermittelt. / This thesis focuses on the sensor-guided control of industrial robots for contour-following. Examples include the robot-guided sewing, grinding or the application of sealant along weld seams. Grinding and sewing require a certain contact force while following a countour of a workpiece, whereas the worpieces might be compliant. Modern production processes require a fast and simple way to set up the motion of the robot for the required task. Therefore sensor systems are used, which process visual and tactile information to guide the tool at a desired contact force along visible contours of a workpiece. The focus of this work is the fusion of sensor data, used to benefit from the advantages of each of the individual sensors in one control scheme. I combine the measurements of a force-torque sensor, a camera, an acceleration sensor and of the Cartesian position of the robot. First, I introduce details on the calculation of the Cartesian robot position. I present an observer-based structure that uses an acceleration sensor to improve the precision of the robot position signal. Then, I analyze the camera system and present a control structure that adapts the position, orientation and velocity of the robot-guided tool along the contour. Thereafter, I show details of force measurement, whereas I compensate for inertial forces using an acceleration sensor. The last chapter addresses the combination of visual contour-following and force control on compliant workpieces. Under a certain contact force, the workpiece deforms due to its compliance. The position and orientation then is adapted to this deformed contour by visual control -- hence, there is a coupling between force and visual control. This coupling is solved by compensating for workpiece deformation using a dynamic model of the environment. The environmental parameters for compensation are identified online.

Image coding is studied, with the work consisting of two distinct parts. Each part focuses on different coding paradigm. The first part of the research examines subband coding of images. An optimization-based method for the design of high-performance separable filter banks for image coding is proposed. This method yields linear-phase perfect-reconstruction systems with high coding gain, good frequency selectivity, and certain prescribed vanishing-moment properties. Several filter banks designed with the proposed method are presented and shown to work extremely well for image coding, outperforming the well-known 9/7 filter bank (from the JPEG-2000 standard) in most cases. Several families of perfect reconstruction filter banks exist, where the filter banks in each family have some common structural properties. New filter banks in each family are designed with the proposed method. Experimental results show that these new filter banks outperform previously known filter banks from the same family. The second part of the research explores normal meshes as a tool for image coding, with a particular interest in the normal-mesh-based image coder of Jansen, Baraniuk, and Lavu. Three modifications to this coder are proposed, namely, the use of a data-dependent base mesh, an alternative representation for normal/vertical offsets, and a different scan-conversion scheme based on bicubic interpolation. Experimental results show that our proposed changes lead to improved coding performance in terms of both objective and subjective image quality measures.

Heterogeneous Objects are engineered with multiple materials to achieve multiple functionalities like high hardness, high toughness and low structural weight. Heterogeneous objects are increasingly used to achieve multiple and often conflicting behaviour within a single object. Developing heterogeneous objects needs computational model for design, analysis and manufacturing. The computational model should map the geometry of the object with the material composition. The most general model is the volume based model that decomposes the geometry exhaustively into simple elements and defines the material distribution over these elements. This approach can model a wide range of objects. However, defining material distribution needs manual intervention to select these elements for material continuity, and to segment or subdivide them for better material approximation. Volume based representation is quite large in size and is cumbersome to edit, query or reuse. Feature based approaches have been proposed to address some of these issues. However, current art can model only limited class of Heterogeneous Objects that includes simple material distribution over complex geometry or complex material distribution over simple geometry. The thesis presents a new method to overcome these limitations. The method, a hybrid of volume based and feature based approaches, allows the user to define the complex material distribution over complex geometries intuitively and represent the same. The complex material distribution is modelled using material reference entities that may be mixed-dimensional, inclusive of non-manifold entities. It uses Medial Axis Transform for automated segmentation of these entities into independent regions, where the material distribution can be intuitively prescribed starting from the entity and terminating at the medial axis. The spatial variation of the material is captured by a parameterized distance field from the material reference entities. It develops new constructive operators to build a complex heterogeneous object model that allows the reuse of the existing heterogeneous object models, automates handling of material continuity, and controls the gradation of the material in the interface of the constituent heterogeneous objects. Constructions using these operators can be geometry driven or material driven i.e. the geometric form controls the material distribution or the material distribution is independent of the geometric form. The proposed representation can be adaptively meshed for generation of mesh in the direction of gradation of the material for finite element analysis and process planning for additive manufacturing. An iso-material contour representation has been proposed for process planning of Heterogeneous Object Models. This avoids the stair case effect by depositing material in the direction of material gradation, and avoids over-deposition or under-deposition due to frequent start and stop of the nozzles. The proposed method has been implemented to show that it can model wide range of heterogeneous objects and can be integrated with additive manufacturing.

Diese Arbeit befaßt sich mit der Koppelung von Vertex-Modellen an die planaren $\phi^4$-Zufallsgraphen des Zugangs zur Quantengravitation über dynamische Polygonifizierungen. Das betrachtete System hat eine doppelte Bedeutung, einerseits als die Koppelung einer konformen Feldtheorie mit zentraler Ladung $C=1$ an zweidimensionale Euklidische Quantengravitation, andererseits als Anwendung von geometrischer, "annealed" Unordnung auf ein prototypisches Modell der statistischen Mechanik. Da das Modell mit Hilfe einer großangelegten Reihe von Monte Carlo Simulationen untersucht wird, müssen entsprechende Techniken für die Simulation von dynamischen Quadrangulierungen bzw. die dualen $\phi^4$-Graphen entwickelt werden. Hierzu werden verschiedene Algorithmen und die dazugehörigen Züge vorgeschlagen und hinsichtlich ihrer Ergodizität und Effizienz untersucht. Zum Vergleich mit exakten Ergebnissen werden die Verteilung der Koordinationszahlen bzw. bestimmte Analoga davon konstruiert. Für Simulationen des $F$-Modells auf $\phi^4$-Zufallsgraphen wird ein Ordnungsparameter für den antiferroelektrischen Phasenübergang mit Hilfe einer Plakettenspindarstellung formuliert. Ausführliche "finite-size scaling"-Analysen des Kosterlitz-Thouless-Phasenübergangs des $F$-Modells auf dem Quadratgitter und auf Zufallsgraphen werden vorgestellt und die Positionen der jeweiligen kritischen Punkte sowie die dazugehörigen kritischen Exponenten werden bestimmt. Die Rückreaktion des Vertex-Modells auf die Zufallsgraphen wird in Form der Koordinationszahlverteilung, der Verteilung der "Baby-Universen" und dem daraus resultierenden String-Suszeptibilitäts-Exponenten sowie durch die geometrische Zweipunktfunktion analysiert, die eine Schätzung der intrinsischen Hausdorff-Dimension des gekoppelten Systems liefert. / In this thesis, the coupling of ice-type vertex models to the planar $\phi^4$ random graphs of the dynamical polygonifications approach to quantum gravity is considered. The investigated system has a double significance as a conformal field theory with central charge $C=1$ coupled to two-dimensional Euclidean quantum gravity and as the application of a special type of annealed connectivity disorder to a prototypic model of statistical mechanics. Since the model is analyzed by means of large-scale Monte Carlo simulations, suitable simulation techniques for the case of dynamical quadrangulations and the dual $\phi^4$ random graphs have to be developed. Different algorithms and the associated update moves are proposed and investigated with respect to their ergodicity and performance. For comparison to exact results, the co-ordination number distribution of the dynamical polygonifications model, or certain analogues of it, are constructed. For simulations of the 6-vertex $F$ model on $\phi^4$ random graphs, an order parameter for its anti-ferroelectric phase transitions is constructed in terms of a "plaquette spin" representation. Extensive finite-size scaling analyses of the Kosterlitz-Thouless point of the square-lattice and random graph $F$ models are presented and the locations of the critical points as well as the corresponding critical exponents are determined. The back-reaction of the coupled vertex model on the random graphs is investigated by an analysis of the co-ordination number distribution, the distribution of "baby universes" and the string susceptibility exponent as well as the geometric two-point function, yielding an estimate for the internal Hausdorff dimension of the coupled system.

La chaîne des Alpes est encore en formation. Sa sismicité étant modérée, la déformation actuelle y est soit faible, soit en grande partie asismique. Pour mieux comprendre la tectonique actuelle du sud du Jura et du nord des Alpes occidentales, nous utilisons des comparaisons de nivellements pour obtenir les mouvements verticaux actuels et de triangulations pour mesurer les mouvements horizontaux. Les déplacements verticaux reflètent principalement la tectonique actuelle de la région, ceux liés au rebond post-glaciaire étant négligeables. La bonne correlation entre la répartition des tendances régionales des mouvements verticaux et la position des principales rampes de chevauchement montre que les déplacements verticaux traduisent l'activité de ces accidents. Pour estimer les taux de déplacement horizontal sur ces rampes, une inversion d'un profil de taux de déplacement vertical est réalisée. On obtient une vitesse de déplacement de 6 mm/an sur le chevauchement crustal de Belledonne, de 4mm/an sur le chevauchement de socle du Jura interne (Haute Chaîne) sur le soubassement du Jura externe et de 4 mm/an pour le déplacement de la couverture du Jura externe sur ce soubassement. Dans la région étudiée, le chevauchement crustal le plus externe est donc localisé entre Jura interne et Jura externe. Ce résultat est conforté par la comparaison de triangulations réalisée. Cette dernière a nécessité le développement de différents tests statistiques (test de Fischer, ellipses de confiance, calcul d'erreur sur les tenseurs de taux de déformation) qui établissent tous la présence d'une déformation importante et significative dans le Jura externe. Celle-ci est caractérisée par les tenseurs de taux de déformations qui montrent une compression proche de la direction E-W et un taux de raccourcissement de 5 mm/an. La déformation horizontale des Bauges apparaît très faible au regard de la précision des mesures. Cependant, le déplacement d'un point, au nord d'Annecy, indique une forte extension E-W de la cluse d'Annecy, résultat qui demande à être confirmé. Ainsi, par deux méthodes indépendantes, il est établi que le Jura est le front actuellement actif de la partie nord des Alpes occidentales. La déformation du Jura est caractérisée par le jeu du chevauchement du socle du Jura interne sur le Jura externe avec une vitesse de 4 à 5 mm/an.

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.

Given a set of n points P ⊂ R2, the Delaunay graph of P for a family of geometric objects C is a graph defined as follows: the vertex set is P and two points p, p' ∈ P are connected by an edge if and only if there exists some C ∈ C containing p, p' but no other point of P. Delaunay graph of circle is often called as Delaunay triangulation as each of its inner face is a triangle if no three points are co-linear and no four points are co-circular. The dual of the Delaunay triangulation is the Voronoi diagram, which is a well studied structure. The study of graph theoretic properties on Delaunay graphs was motivated by its application to wireless sensor networks, meshing, computer vision, computer graphics, computational geometry, height interpolation, etc. The problem of finding an optimal vertex cover on a graph is a classical NP-hard problem. In this thesis we focus on the vertex cover problem on Delaunay graphs for geometric objects like axis-parallel slabs and circles(Delaunay triangulation). 1. We consider the vertex cover problem on Delaunay graph of axis-parallel slabs. It turns out that the Delaunay graph of axis-parallel slabs has a very special property — its edge set is the union of two Hamiltonian paths. Thus, our problem reduces to solving vertex cover on the class of graphs whose edge set is simply the union of two Hamiltonian Paths. We refer to such a graph as a braid graph. Despite the appealing structure, we show that deciding k-vertex cover on braid graphs is NP-complete. This involves a rather intricate reduction from the problem of finding a vertex cover on 2-connected cubic planar graphs. 2. Having established the NP-hardness of the vertex cover problem on braid graphs, we pursue the question of improved fixed parameter algorithms on braid graphs. The best-known algorithm for vertex cover on general graphs has a running time of O(1.2738k + kn) [CKX10]. We propose a branching based fixed parameter tractable algorithm with running time O⋆(1.2637k) for graphs with maximum degree bounded by four. This improves the best known algorithm for this class, which surprisingly has been no better than the algorithm for general graphs. Note that this implies faster algorithms for the class of braid graphs (since they have maximum degree at most four). 3. A triangulation is a 2-connected plane graph in which all the faces except possibly the outer face are triangles, we often refer to such graphs as triangulated graphs. A chordless-NST is a triangulation that does not have chords or separating triangles (non-facial triangles). We focus on the computational problem of optimal vertex covers on triangulations, specifically chordless-NST. We call a triangulation Delaunay realizable if it is combinatorially equivalent to some Delaunay triangulation. Characterizations of Delaunay triangulations have been well studied in graph theory. Dillencourt and Smith [DS96] showed that chordless-NSTs are Delaunay realizable. We show that for chordless-NST, deciding the vertex cover problem is NP-complete. We prove this by giving a reduction from vertex cover on 3-connected, triangle free planar graph to an instance of vertex cover on a chordless-NST. 4. If the outer face of a triangulation is also a triangle, then it is called a maximal planar graph. We prove that the vertex cover problem is NP-complete on maximal planar graphs by reducing an instance of vertex cover on a triangulated graph to an instance of vertex cover on a maximal planar graph.

No description available.

Diese Dissertation befasst sich mit der sensorgeführten Regelung von Industrierobotern zur Konturverfolgung. Beispiele dafür sind das robotergestützte Nähen, Entgraten oder das Auftragen von Dichtmasse entlang von Schweißnähten. Beim Nähen und Entgraten müssen während der Verfolgung der Kontur bestimmte Kontaktkräfte an möglicherweise nachgiebigen Werkstücken eingehalten werden. Dabei ist es in modernen Fertigungsprozessen wichtig, die Bewegung des Roboters mit wenig Einrichtaufwand vorzugeben. Dazu werden Sensorsysteme eingesetzt, die Bildinformationen und Kraftmessungen verarbeiten, um den Roboter mit gewünschter Kontaktkraft entlang sichtbarer Konturen eines Werkstückes zu führen. Der Fokus dieser Arbeit ist die Fusion der Sensordaten, um die Vorteile der einzelnen Sensoren in einer Aufgabe zu vereinen. Es werden Messwerte eines Kraft-Momenten Sensors, einer Kamera, eines Beschleunigungssensors und der kartesischen Position und Orientierung des Roboters verwendet. Zuerst wird die Berechnung der kartesischen Roboterposition untersucht. Es wird ein Beobachter vorgestellt, um unter Verwendung eines Beschleunigungssensors die Präzision des Positionssignales zu erhöhen. Anschließend wird das Kamerasystem untersucht und ein Verfahren vorgestellt, um Geschwindigkeit, Position und Orientierung des robotergeführten Werkzeuges entlang der Kontur vorzugeben. Danach wird auf die Ermittlung von Kontaktkräften eingegangen, wobei die Kompensation von Trägheitskräften mittels Beschleunigungssensoren untersucht wird. Der letzte Abschnitt befasst sich mit der Verbindung von bildgestützter Konturverfolgung und Kraftregelung an nachgiebigen Werkstücken. Durch die Nachgiebigkeit des Werkstückmaterials verformt sich die Kontur bei Kontakt. Durch bildgestützte Konturverfolgung wird eine Anpassung an diese Verformung vorgenommen -- somit besteht über die Verformbarkeit des Werkstückes eine Kopplung zwischen den beiden Regelkreisen. Diese Kopplung wird gelöst, indem auf Basis eines dynamischen Modells der Umgebung eine Kompensation der Werkstückverformung berechnet wird. Die Modellparameter zur Kompensation werden durch online Identifikation ermittelt. / This thesis focuses on the sensor-guided control of industrial robots for contour-following. Examples include the robot-guided sewing, grinding or the application of sealant along weld seams. Grinding and sewing require a certain contact force while following a countour of a workpiece, whereas the worpieces might be compliant. Modern production processes require a fast and simple way to set up the motion of the robot for the required task. Therefore sensor systems are used, which process visual and tactile information to guide the tool at a desired contact force along visible contours of a workpiece. The focus of this work is the fusion of sensor data, used to benefit from the advantages of each of the individual sensors in one control scheme. I combine the measurements of a force-torque sensor, a camera, an acceleration sensor and of the Cartesian position of the robot. First, I introduce details on the calculation of the Cartesian robot position. I present an observer-based structure that uses an acceleration sensor to improve the precision of the robot position signal. Then, I analyze the camera system and present a control structure that adapts the position, orientation and velocity of the robot-guided tool along the contour. Thereafter, I show details of force measurement, whereas I compensate for inertial forces using an acceleration sensor. The last chapter addresses the combination of visual contour-following and force control on compliant workpieces. Under a certain contact force, the workpiece deforms due to its compliance. The position and orientation then is adapted to this deformed contour by visual control -- hence, there is a coupling between force and visual control. This coupling is solved by compensating for workpiece deformation using a dynamic model of the environment. The environmental parameters for compensation are identified online.