Efficient Methods for Continuous and Discrete Shape Analysis
PhD thesis from Faculty of Mathematics and Natural Sciences, University of Bonn, Germany - Nov 2010
Download the publication: 2.3 MB
Share the publication: 
When interpreting an image of a given object, humans are able to
abstract from the presented color information in order to really
see the presented object. This abstraction is also known as
shape. The concept of shape is not defined exactly in
Computer Vision and in this work, we use three different forms of
these definitions in order to acquire and analyze shapes. This
work is devoted to improve the efficiency of methods that solve
important applications of shape analysis.
The most important problem in order to analyze shapes is the problem of shape acquisition. To simplify this very challenging problem, numerous researchers have incorporated prior knowledge into the acquisition of shapes. We will present the first approach to acquire shapes given a certain shape knowledge that computes always the global minimum of the involved functional which incorporates a Mumford-Shah like functional with a certain class of shape priors including statistic shape prior and dynamical shape prior.
In order to analyze shapes, it is not only important to acquire shapes, but also to classify shapes. In this work, we follow the concept of defining a distance function that measures the dissimilarity of two given shapes. There are two different ways of obtaining such a distance function that we address in this work. Firstly, we model the set of all shapes as a metric space induced by the shortest path on an orbifold. The shortest path will provide us with a shape morphing, i.e., a continuous transformation from one shape into another. Secondly, we address the problem of shape matching that finds corresponding points on two shapes with respect to a preselected feature.
Our main contribution for the problem of shape morphing lies in the immense acceleration of the morphing computation. Instead of solving partial resp. ordinary differential equations, we are able to solve this problem via a gradient descent approach that subsequently shortens the length of a path on the given manifold. During our run-time test, we observed a run-time acceleration of up to a factor of 1000.
Shape matching is a classical discrete problem. If each shape is dis- cretized by N shape points, most Computer Vision methods needed a cubic run-time. We will provide two approaches how to reduce this worst-case complexity to O(N^2 log(N)). One approach exploits the planarity of the involved graph in order to efficiently compute N shortest path in a graph of O(N^2) vertices. The other approach com- putes a minimal cut in a planar graph in O(N log(N)). In order to make this approach applicable to shape matching, we improved the run-time of a recently developed graph cut approach by an empirical factor of 2-4.
The most important problem in order to analyze shapes is the problem of shape acquisition. To simplify this very challenging problem, numerous researchers have incorporated prior knowledge into the acquisition of shapes. We will present the first approach to acquire shapes given a certain shape knowledge that computes always the global minimum of the involved functional which incorporates a Mumford-Shah like functional with a certain class of shape priors including statistic shape prior and dynamical shape prior.
In order to analyze shapes, it is not only important to acquire shapes, but also to classify shapes. In this work, we follow the concept of defining a distance function that measures the dissimilarity of two given shapes. There are two different ways of obtaining such a distance function that we address in this work. Firstly, we model the set of all shapes as a metric space induced by the shortest path on an orbifold. The shortest path will provide us with a shape morphing, i.e., a continuous transformation from one shape into another. Secondly, we address the problem of shape matching that finds corresponding points on two shapes with respect to a preselected feature.
Our main contribution for the problem of shape morphing lies in the immense acceleration of the morphing computation. Instead of solving partial resp. ordinary differential equations, we are able to solve this problem via a gradient descent approach that subsequently shortens the length of a path on the given manifold. During our run-time test, we observed a run-time acceleration of up to a factor of 1000.
Shape matching is a classical discrete problem. If each shape is dis- cretized by N shape points, most Computer Vision methods needed a cubic run-time. We will provide two approaches how to reduce this worst-case complexity to O(N^2 log(N)). One approach exploits the planarity of the involved graph in order to efficiently compute N shortest path in a graph of O(N^2) vertices. The other approach com- putes a minimal cut in a planar graph in O(N log(N)). In order to make this approach applicable to shape matching, we improved the run-time of a recently developed graph cut approach by an empirical factor of 2-4.
Images and movies
BibTex references
@PhdThesis\{Sch10,
author = "Schmidt, Frank R.",
title = "Efficient Methods for Continuous and Discrete Shape Analysis",
school = "Faculty of Mathematics and Natural Sciences, University of Bonn, Germany",
month = "Nov",
year = "2010",
url = "http://frank-r-schmidt.de/Publications/2010/Sch10"
}