Deformable Shape Matching

Abstract

Deformable shape matching has become an important building block inacademia as well as in industry.Given two three dimensional shapes A and B the deformation function faligning A with B has to be found.The function is discretized by a set of corresponding point pairs.Unfortunately, the computation cost of a brute-force search ofcorrespondences is exponential. Additionally, to be of any practicaluse the algorithm has to be able to deal with data coming directlyfrom 3D scanner devices which suffers from acquisition problems likenoise, holes as well as missing any information about topology.This dissertation presents novel solutions for solving shape matching:First, an algorithm estimating correspondences using a randomizedsearch strategy is shown. Additionally, a planning step dramaticallyreducing the matching costs is incorporated. Using ideas of these bothcontributions, a method for matching multiple shapes at once is shown.The method facilitates the reconstruction of shape and motion fromnoisy data acquired with dynamic 3D scanners. Considering shapematching from another perspective a solution is shown using MarkovRandom Fields (MRF). Formulated as MRF, partial as well as fullmatches of a shape can be found. Here, belief propagation is utilizedfor inference computation in the MRF. Finally, an approachsignificantly reducing the space-time complexity of belief propagationfor a wide spectrum of computer vision tasks is presented.