Computing correspondences or maps between shapes is one of the oldest problems in Computer Graphics and Geometry Processing with a wide range of applications from deformation transfer, statistical shape analysis, to co-segmentation and exploration among a myriad others. A good map is supposed to be continuous, as-bijective-as-possible, accurate if there are ground-truth corresponding landmarks given, and lowdistortionw.r.t. different measures, for example as-conformal-as-possible to preserve the angles. This thesis contributes to the area of non-rigid shape matching and map space exploration in Geometry Processing. Specifically, we consider the discrete setting, where the shapes are discretized as amesh structure consisting of vertices, edges, and polygonal faces. In the simplest case, we only consider the graph structure with vertices and edges only. In this thesis, we design algorithms to compute soft correspondences between discrete shapes. Specifically, (1)we propose different regularizers, including orientation-preserving operator and the Resolvent Laplacian Commutativity operator, to promote the shape correspondences in the functional map framework. (2) We propose two refinement methods, namely BCICP and ZoomOut, to improve the accuracy, continuity, bijectivity and the coverage of given point-wisemaps. (3)We propose a tree structure and an enumeration algorithm to explore the map space between a pair of shapes that can update multiple high-quality dense correspondences.

Today, soft body simulations are essential for a wide range of applications. They are for instance used for medical training in virtual reality and in video games to simulate clothes and hair. These kinds of interactive applications rely on real-time simulations, which entails very strict requirements. The simulation has to be fast enough and must never break, regardless of what deformation might occur. Two methods that perform well with regard to these requirements are the position-based dynamics (PBD) method and the shape matching method. Even though these methods have been used for years, it is still unclear when you should use either method. This thesis has compared the two methods with regard to the mentioned requirements. More specifically, the thesis has evaluated the performance of the simulation loop as well as the simulated objects’ ability to restore their shape after deformation. The performance results clearly show that the PBD method is the fastest. But the results of the simulated objects’ ability to restore their shape were not as conclusive. Overall, the PBD method seemed to perform the best again, but there were cases the method could not handle. Although the shape matching method performed slightly worse, it did manage to restore the shape of every deformed object. In conclusion, for most applications, the PBD method is likely the better option, but if the application relies on the fact that simulated objects can restore their shape, then the shape matching method may be preferable. / Idag är simulering av mjuka kroppar viktiga för en mängd olika tillämpningar. De används exempelvis för medicinsk träning i virtuell verklighet och i datorspel för att simulera kläder och hår. Dessa typer av interaktiva applikationer förlitar sig på realtidssimuleringar, vilket medför många stränga krav. Simuleringen måste vara tillräckligt snabb och får aldrig gå sönder, oavsett vad för slags deformation som kan uppstå. Två metoder som presterar bra med avseende på dessa krav är position-based dynamics (PBD) och shape matching. Trots att dessa metoder har använts i många år, så är det fortfarande oklart när vilken metod är mest lämplig. Denna avhandling har jämfört de två metoderna med hänsyn till de nämnda kraven. Mer specifikt har avhandlingen utvärderat metodernas prestanda samt de simulerade objektens förmåga att återställa sin form efter deformation. Resultaten för prestanda visar tydligt att PBD-metoden är snabbast. Men resultaten av de simulerade objektens förmåga att återställa sin form var inte lika enhälliga. Sammantaget verkade PBD-metoden prestera bäst igen, däremot fanns det fall som metoden inte kunde hantera. Fastän shape matching metoden presterade något sämre, så lyckades den återställa formen för varje deformerat objekt. Sammanfattningsvis, för de flesta applikationer är PBD-metoden troligen det bättre alternativet, men om applikationen förlitar sig på att de simulerade objekten kan återställa sina former, så kan shape matching metoden vara att föredra.

The modern engineering design process includes computer software packages that require approximations to be made when representing geometries. These approximations lead to inherent discrepancies between the design geometry of a part or assembly and the corresponding manufactured geometry. Further approximations are made during the analysis portion of the design process. Manufacturing defects can also occur, which increase the discrepancies between the design and manufactured geometry. These approximations combined with manufacturing defects lead to discrepancies which, for high precision parts, such as jet engine compressor blades, can affect the modal analysis results. In order to account for the manufacturing defects during analysis, mesh morphing is used to morph a structural finite element analysis mesh to match the geometry of compressor blades with simulated manufacturing defects. The mesh morphing process is improved by providing a novel method to convert heteromorphic shape matching within Sculptor to homeomorphic shape matching. This novel method is automated using Java and the NX API. The heteromorphic to homeomorphic conversion method is determined to be valid due to its post-mesh morphing maximum deviations being on the same order as the post-mesh morphing maximum deviations of the ideal homeomorphic case. The usefulness of the automated heteromorphic to homeomorphic conversion method is demonstrated by simulating manufacturing defects on the pressure surface of a compressor blade model, morphing a structural finite element analysis mesh to match the geometry of compressor blades with simulated manufacturing defects, performing a modal analysis, and making observations on the effect of the simulated manufacturing defects on the modal characteristics of the compressor blade.

The role of digital humans in product design and assessment is ever increasing. Accurate digital human models are used to provide feedback on virtual prototypes of products, thus reducing costs and shortening the design cycle. An essential part of product assessment in the virtual world is the ability of the human model to interact correctly and naturally with the product model. This involves reaching, grasping and manipulation. This work addresses the difficult problem of grasp planning for digital humans. We develop a semi-interactive system for synthesizing grasps based on the object's shape, and implement this system for SantosTM, the digital human developed at the Virtual Soldier Research Program at the University of Iowa. The system is composed of three main parts: First, a shape matching module that creates an initial power grasp for the object based on a database of pre-calculated grasps. Second, an optimization based module provides control of the fingertip locations. This can be used to synthesize precision grasps under the user's guidance. Finally, a grasp quality module provides feedback about the grasp's mechanical stability. The novelty of our approach lies in the fact that it takes into consideration the upper body posture when planning the grasp, so the whole arm and the torso are involved in the grasp.

This dissertation addresses a number of inter-related and fundamental problems in computer vision. Specifically, we address object discovery, recognition, segmentation, and 3D pose estimation in images, as well as 3D scene reconstruction and scene interpretation. The key ideas behind our approaches include using shape as a basic object feature, and using structured prediction modeling paradigms for representing objects and scenes. In this work, we make a number of new contributions both in computer vision and machine learning. We address the vision problems of shape matching, shape-based mining of objects in arbitrary image collections, context-aware object recognition, monocular estimation of 3D object poses, and monocular 3D scene reconstruction using shape from texture. Our work on shape-based object discovery is the first to show that meaningful objects can be extracted from a collection of arbitrary images, without any human supervision, by shape matching. We also show that a spatial repetition of objects in images (e.g., windows on a building facade, or cars lined up along a street) can be used for 3D scene reconstruction from a single image. The aforementioned topics have never been addressed in the literature. The dissertation also presents new algorithms and object representations for the aforementioned vision problems. We fuse two traditionally different modeling paradigms Conditional Random Fields (CRF) and Random Forests (RF) into a unified framework, referred to as (RF)^2. We also derive theoretical error bounds of estimating distribution ratios by a two-class RF, which is then used to derive the theoretical performance bounds of a two-class (RF)^2. Thorough experimental evaluation of individual aspects of all our approaches is presented. In general, the experiments demonstrate that we outperform the state of the art on the benchmark datasets, without increasing complexity and supervision in training. / Graduation date: 2011 / Access restricted to the OSU Community at author's request from May 12, 2011 - May 12, 2012

Shape description is an important problem in computer vision because most vision tasks that require comparing or matching visual entities rely on shape descriptors. In this thesis, two novel shape descriptors are proposed, namely Intersection Consistency Histogram (ICH) and Global Binary Patterns (GBP). The former is based on a local regularity measure called Intersection Consistency (IC), which determines whether edge pixels in an image patch point towards the center or not. The second method, called Global Binary Patterns, represents the shape in binary along horizontal, vertical, diagonal or principal directions. These two methods are extensively analyzed on several databases, and retrieval and running time performances are presented. Moreover, these methods are compared with methods such as Shape Context, Histograms of Oriented Gradients, Local Binary Patterns and Fourier Descriptors. We report that our descriptors perform comparable to these methods.

The similarity between two shapes is typically calculated by measuring how well the properties and the spatial organization of the primitives forming the shapes agree. But, when this calculations are done independent from the context, i.e. the whole set of shapes in the experiments, a priori significance to the primitives is assigned, which may cause problematic similarity measures. A possible way of using context information in similarity measure between shape A and shape B is using the category information of shape B in calculations. In this study, shapes are represented as depth-1 shape trees and the dissimilarity between two shapes is computed by using an approximate tree matching algorithm. The category information is created as the union of shape trees that are in the same category and this information guides the matching process between a query shape and a shape whose category is known.

La capture du mouvement est un défi majeur dans le cadre de la modélisation d'objets articulés. Ce problème implique la recherche de correspondances entre objets vus dans des images différentes. On propose trois approches pour résoudre ce problème basé sur des techniques de vision par ordinateur et la théorie spectrale des graphes. La première consiste à modéliser une scène 3D à l'aide d'une collection de points. On propose deux extensions de l'algorithme de Lucas-Kanade pour tracker des caractéristiques de manière efficace et pour estimer le "scene-flow". La deuxième approche basée sur la théorie spectrale des graphes cherche à établir des correspondances entre des objets représentés par des graphes. Finalement on s'intéresse au problème de segmentation qui soit cohérente dans le temps et notre approche est basée sur une méthode de clustering spectral appliquée à une séquence temporelle.

La création et la compréhension des déformations de surfaces sont des thèmes récurrent pour le traitement de géométrie 3D. Comme les surfaces lisses peuvent être représentées de multiples façon allant du nuage ​​de points aux maillages polygonales, un enjeu important est de pouvoir comparer ou déformer des formes discrètes indépendamment de leur représentation. Une réponse possible est de choisir une représentation flexible des surfaces déformables qui peut facilement être transportées d'une structure de données à une autre.Dans ce but, les "functional map" proposent de représenter des applications entre les surfaces et, par extension, des déformations comme des opérateurs agissant sur des fonctions. Cette approche a été introduite récemment pour le traitement de modèle 3D, mais a été largement utilisé dans d'autres domaines tels que la géométrie différentielle, la théorie des opérateurs et les systèmes dynamiques, pour n'en citer que quelques-uns. Le principal avantage de ce point de vue est de détourner les problèmes encore non-résolus, tels que la correspondance forme et le transfert de déformations, vers l'analyse fonctionnelle dont l'étude et la discrétisation sont souvent mieux connues. Cette thèse approfondit l'analyse et fournit de nouvelles applications à ce cadre d'étude. Deux questions principales sont discutées.Premièrement, étant donné deux surfaces, nous analysons les déformations sous-jacentes. Une façon de procéder est de trouver des correspondances qui minimisent la distorsion globale. Pour compléter l'analyse, nous identifions les parties les moins fiables du difféomorphisme grâce une méthode d'apprentissage. Une fois repérés, les défauts peuvent être éliminés de façon différentiable à l'aide d'une représentation adéquate des champs de vecteurs tangents.Le deuxième développement concerne le problème inverse : étant donné une déformation représentée comme un opérateur, comment déformer une surface en conséquence ? Dans une première approche, nous analysons un encodage de la structure intrinsèque et extrinsèque d'une forme en tant qu'opérateur fonctionnel. Dans ce cadre, l'objet déformé peut être obtenu, à rotations et translations près, en résolvant une série de problèmes d'optimisation convexe. Deuxièmement, nous considérons une version linéarisée de la méthode précédente qui nous permet d'appréhender les champs de déformation comme agissant sur la métrique induite. En conséquence la résolution de problèmes difficiles, tel que le transfert de déformation, sont effectués à l'aide de simple systèmes linéaires d'équations. / Creating and understanding deformations of surfaces is a recurring theme in geometry processing. As smooth surfaces can be represented in many ways from point clouds to triangle meshes, one of the challenges is being able to compare or deform consistently discrete shapes independently of their representation. A possible answer is choosing a flexible representation of deformable surfaces that can easily be transported from one structure to another.Toward this goal, the functional map framework proposes to represent maps between surfaces and, to further extents, deformation of surfaces as operators acting on functions. This approach has been recently introduced in geometry processing but has been extensively used in other fields such as differential geometry, operator theory and dynamical systems, to name just a few. The major advantage of such point of view is to deflect challenging problems, such as shape matching and deformation transfer, toward functional analysis whose discretization has been well studied in various cases. This thesis investigates further analysis and novel applications in this framework. Two aspects of the functional representation framework are discussed.First, given two surfaces, we analyze the underlying deformation. One way to do so is by finding correspondences that minimize the global distortion. To complete the analysis we identify the least and most reliable parts of the mapping by a learning procedure. Once spotted, the flaws in the map can be repaired in a smooth way using a consistent representation of tangent vector fields.The second development concerns the reverse problem: given a deformation represented as an operator how to deform a surface accordingly? In a first approach, we analyse a coordinate-free encoding of the intrinsic and extrinsic structure of a surface as functional operator. In this framework a deformed shape can be recovered up to rigid motion by solving a set of convex optimization problems. Second, we consider a linearized version of the previous method enabling us to understand deformation fields as acting on the underlying metric. This allows us to solve challenging problems such as deformation transfer are solved using simple linear systems of equations.

Depuis quelques années, l’évolution des techniques d’acquisition a entraîné une généralisation de l’utilisation d’objets 3D très dense, représentés par des nuages de points de plusieurs millions de sommets. Au vu de la complexité de ces données, il est souvent nécessaire de les analyser pour en extraire les structures les plus pertinentes, potentiellement définies à plusieurs échelles. Parmi les nombreuses méthodes traditionnellement utilisées pour analyser des signaux numériques, l’analyse dite scale-space est aujourd’hui un standard pour l’étude des courbes et des images. Cependant, son adaptation aux données 3D pose des problèmes d’instabilité et nécessite une information de connectivité, qui n’est pas directement définie dans les cas des nuages de points. Dans cette thèse, nous présentons une suite d’outils mathématiques pour l’analyse des objets 3D, sous le nom de Growing Least Squares (GLS). Nous proposons de représenter la géométrie décrite par un nuage de points via une primitive du second ordre ajustée par une minimisation aux moindres carrés, et cela à pour plusieurs échelles. Cette description est ensuite derivée analytiquement pour extraire de manière continue les structures les plus pertinentes à la fois en espace et en échelle. Nous montrons par plusieurs exemples et comparaisons que cette représentation et les outils associés définissent une solution efficace pour l’analyse des nuages de points à plusieurs échelles. Un défi intéressant est l’analyse d’objets 3D acquis dans le cadre de l’étude du patrimoine culturel. Dans cette thèse, nous nous étudions les données générées par l’acquisition des fragments des statues entourant par le passé le Phare d’Alexandrie, Septième Merveille du Monde. Plus précisément, nous nous intéressons au réassemblage d’objets fracturés en peu de fragments (une dizaine), mais avec de nombreuses parties manquantes ou fortement dégradées par l’action du temps. Nous proposons un formalisme pour la conception de systèmes d’assemblage virtuel semi-automatiques, permettant de combiner à la fois les connaissances des archéologues et la précision des algorithmes d’assemblage. Nous présentons deux systèmes basés sur cette conception, et nous montrons leur efficacité dans des cas concrets. / Over the last decades, the evolution of acquisition techniques yields the generalization of detailed 3D objects, represented as huge point sets composed of millions of vertices. The complexity of the involved data often requires to analyze them for the extraction and characterization of pertinent structures, which are potentially defined at multiple scales. Amongthe wide variety of methods proposed to analyze digital signals, the scale-space analysis istoday a standard for the study of 2D curves and images. However, its adaptation to 3D dataleads to instabilities and requires connectivity information, which is not directly availablewhen dealing with point sets.In this thesis, we present a new multi-scale analysis framework that we call the GrowingLeast Squares (GLS). It consists of a robust local geometric descriptor that can be evaluatedon point sets at multiple scales using an efficient second-order fitting procedure. We proposeto analytically differentiate this descriptor to extract continuously the pertinent structuresin scale-space. We show that this representation and the associated toolbox define an effi-cient way to analyze 3D objects represented as point sets at multiple scales. To this end, we demonstrate its relevance in various application scenarios.A challenging application is the analysis of acquired 3D objects coming from the CulturalHeritage field. In this thesis, we study a real-world dataset composed of the fragments ofthe statues that were surrounding the legendary Alexandria Lighthouse. In particular, wefocus on the problem of fractured object reassembly, consisting of few fragments (up to aboutten), but with missing parts due to erosion or deterioration. We propose a semi-automaticformalism to combine both the archaeologist’s knowledge and the accuracy of geometricmatching algorithms during the reassembly process. We use it to design two systems, andwe show their efficiency in concrete cases.