Efficient Methods for continuous and discrete shape analysis [Elektronische Ressource] / vorgelegt von Frank R. Schmidt

Frank R. Schmidt

Sujets

• Informatik

Informations

• Publié par: rheinische_friedrich-wilhelms-universitat_bonn
• Publié le: 01 janvier 2010
• Nombre de lectures: 27
• Langue: English
• Poids de l'ouvrage: 2 Mo

Extrait

Efficient Methods for
Continuous and Discrete
Shape Analysis
Dissertation
zur
Erlangung des Doktorgrades (Dr. rer. nat.)
der
Mathematisch-Naturwissenschaftlichen Fakult¨at
der
Rheinischen Friedrich-Wilhelms-Universit¨at Bonn
vorgelegt von
Dipl.-Math. Frank R. Schmidt
aus Bonn
Bonn, 2010Angefertigt mit Genehmigung der
Mathematisch-Naturwissenschaftlichen Fakult¨at
der Rheinischen Friedrich-Wilhelms-Universita¨t Bonn
1. Gutachter: Prof. Dr. D. Cremers
2. Gutachter: Prof. Dr. M. Clausen
Tag der Promotion: 12. November 2010
iiSummary
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 prob-
lem of shape acquisition. To simplify this very challenging prob-
lem, numerous researchers have incorporated prior knowledge into
the acquisition of shapes. We will present the first approach to ac-
quire 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.
Inordertoanalyzeshapes,itisnotonlyimportanttoacquireshapes,
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 dis-
tance 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
iiian orbifold. The shortest path will provide us with a shape morph-
ing, i.e., a continuous transformation from one shape into another.
Secondly, weaddresstheproblemofshape matching thatfindscorre-
sponding 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
solvethisproblemviaagradientdescentapproachthatsubsequently
shortensthelength ofapathonthegiven manifold. Duringourrun-
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 byN shape points, most Computer Vision methods needed
a cubic run-time. We will provide two approaches how to reduce
2this worst-case complexity to O(N log(N)). One approach exploits
the planarity of the involved graph in order to efficiently computeN
2shortestpathinagraphofO(N )vertices. Theotherapproachcom-
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-timeof arecently developed graphcut approachby anempirical
factor of 2–4.
ivAcknowledgments
First of all, Iwould like to expressmy gratitude to Prof. D. Cremers
for supervising my dissertation and for introducing me into the field
ofComputerVision. Boththewiderangeofresearchtopicsdiscussed
in his group and the amount of time that Prof. D. Cremers spend
with me personally, discussing different approaches and techniques
provided a stimulating and productive environment for my thesis.
Secondly,IwanttothankProf. M.Clausenforservingasanexternal
referee for my thesis. Furthermore, I want to thank the committee
members of the disputation, namely Prof. D. Cremers, Prof. M.
Clausen, Prof. R. Klein and Prof. M. Rumpf.
Iwant tothankanumberofpeoplewhocontributedtothiswork. In
particular there is E. To¨ppe and F. Barthel who collaborated with
me during their diploma thesis, the graph cut implementation for
shapematchingandpartsofthepresentedshapeacquisition method
evolved from joint work. I want to thank all the other members of
our group for providing a unique atmosphere, namely T. Brox, T.
Pock, T. Schoenemann, K. Kolev and U. Schlickewei. In particular,
I want to thank B. Goldlu¨cke, C. Nieuwenhuis, F. Steinbru¨cker, M.
Klodt, E. To¨ppe and M. Oswald for proofreading the manuscripts
and for providing helpful comments.
Then there is the group of M. Clausen with whom I conducted very
fruitful discussions. Especially I like to thank F. Kurth, M. Mu¨ller,
vR. Bardeli and T. Ro¨der.
AspecialthankgoestomembersoftheHausdorff Center for Mathe-
matics inBonn. Inparticular,IthankS.Hainz,J.Mu¨ller,B.Berkels
and B. Wirth for the discussions on several mathematical topics.
I want to thank a number of researchers for hospitality and stimu-
lating discussions during various visits at other institutes. First of
all this is the vision group at the University of Western Ontario who
hosted me at two stays of one week and one month. In particular
I want to thank Y. Boykov, O. Veksler and A. Delong for the great
time and the intense discussion that we conducted. Then, there is
the Technical University at Eindhoven who hosted me for a stay of
two weeks. I enjoyed the collaboration with D. Farin very much and
I profited immensely from his experience in the fields of real-time
programming.
A great thanks goes to the organizers of the SIAM Conference of
Imaging Science 2008 for letting me present the convex shape ac-
quisition method. I also like to thank IPAM for hosting me at their
workshop on Graph Cuts and Related Discrete or Continuous Op-
timization Problems. I also would like to thank the image group
at the DIKU in Copenhagen for their organization of the summer
school 2008.
Finally, I would like to thank my parents, my brother and my sister
for their invaluable support of my research.
viContents
1 Introduction 1
1.1 Shapes . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Continuous versus Discrete Methods . . . . . . . . . . 4
1.3 Related Work . . . . . . . . . . . . . . . . . . . . . . . 6
1.4 Contribution . . . . . . . . . . . . . . . . . . . . . . . 8
2 Shape Acquisition 11
2.1 Classical Shape Acquisition Methods . . . . . . . . . . 12
2.2 Stochastic Shapes . . . . . . . . . . . . . . . . . . . . . 17
2.3 Knowledge-driven Shape Acquisition . . . . . . . . . . 25
2.4 Global Optimization . . . . . . . . . . . . . . . . . . . 29
2.4.1 Convex Optimization for Deformations . . . . . 30
2.4.2 Lipschitz Optimization for Transformations . . 34
2.5 Tracking Walking People . . . . . . . . . . . . . . . . . 38
22.6 Limitation of L -distances . . . . . . . . . . . . . . . . 42
3 Shape Morphing 44
vii3.1 Shape Spaces as Orbifolds . . . . . . . . . . . . . . . . 47
3.2 Geodesics on Submanifolds . . . . . . . . . . . . . . . 58
3.3 Path-Shortening Method . . . . . . . . . . . . . . . . . 63
3.3.1 Geodesics in a Finite Dimensional Space . . . . 64
3.3.2 Geodesics on the Preshape Space . . . . . . . . 68
3.3.3 Geodesics on the Shape Space . . . . . . . . . . 69
3.4 Comparing Different Approaches . . . . . . . . . . . . 73
3.4.1 Contour Based vs. Region Based Approach . . 73
3.4.2 Path-Shortening Method vs. Shooting Method 77
3.5 Limitations of Morphings . . . . . . . . . . . . . . . . 80
4 Shape Matching 85
4.1 Pseudo-Metrical Shape Spaces. . . . . . . . . . . . . . 87
4.2 Shape Features . . . . . . . . . . . . . . . . . . . . . . 91
4.2.1 Integral Curvature Computation . . . . . . . . 92
4.2.2 Inner Shape Context . . . . . . . . . . . . . . . 95
4.3 Discrete Approaches . . . . . . . . . . . . . . . . . . . 97
4.4 Dynamic Time Warping . . . . . . . . . . . . . . . . . 97
4.4.1 Efficient Shortest Cyclic Paths on a Torus . . . 100
4.4.2 Experimental Comparisons . . . . . . . . . . . 109
4.5 Shape Matching as Graph Cut Problem . . . . . . . . 111
4.5.1 Efficient Planar Graph Cuts . . . . . . . . . . . 115
4.5.2 Efficient ShapeMatching viaPlanarGraphCuts121
4.6 Shape Clustering . . . . . . . . . . . . . . . . . . . . . 122
4.6.1 LEMS Database . . . . . . . . . . . . . . . . . 123
viii4.6.2 MPEG7 Database . . . . . . . . . . . . . . . . 124
5 Conclusion 127
5.1 Summary . . . . . . . . . . . . . . . . . . . . . . . . . 127
5.2 Future Work . . . . . . . . . . . . . . . . . . . . . . . 132
Bibliography 134
ixChapter 1
Introduction
1.1 Shapes
Describing, measuring and comparing the shape of objects is very
popularinavarietyofdifferentdisciplines. Evenoneofthefirstdoc-
umented form of human communication, namely the cave paintings
during the stone age, reduced the described objects to a monochro-
1maticshape . Sincethen,humansstrovetoimprovethevisualization
of the objects that they encountered. But even in modern society,
theshaperepresentationinformofapaper-cuttingisstillpresent. It
reflects the fact that every person is able to recognize a given object
even if color information is completely ignored. In fact, it has been
believed that all relevant features of a given object are encoded by
its shape. If we want to teach a computer not