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 :
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 MumfordShah 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 runtime test, we observed a runtime 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 runtime. We will provide two approaches how to reduce
this worstcase 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
runtime of a recently developed graph cut approach by an empirical
factor of 24.
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://www.frankrschmidt.de/Publications/2010/Sch10"
}
