Numerical Geometry of Non-rigid Shapes

by Bronstein, Alexander M.; Bronstein, Michael M.; Kimmel, Ron

• ISBN13: 9780387733005
• ISBN10: 0387733000
• Format: Hardcover
• Copyright: 2008-10-14
• Publisher: Springer-Nature New York Inc

Summary

Deformable objects are ubiquitous in the world surrounding us, on all levels from micro to macro. The need to study such shapes and model their behavior arises in a wide spectrum of applications, ranging from medicine to security. In recent years, non-rigid shapes have attracted growing interest, which has led to rapid development of the field, where state-of-the-art results from very different sciences - theoretical and numerical geometry, optimization, linear algebra, graph theory, machine learning and computer graphics, to mention several - are applied to find solutions.This book gives an overview of the current state of science in analysis and synthesis of non-rigid shapes. Everyday examples are used to explain concepts and to illustrate different techniques. The presentation unfolds systematically and numerous figures enrich the engaging exposition. Practice problems follow at the end of each chapter, with detailed solutions to selected problems in the appendix. A gallery of colored images enhances the text.This book will be of interest to graduate students, researchers and professionals in different fields of mathematics, computer science and engineering. It may be used for courses in computer vision, numerical geometry and geometric modeling and computer graphics or for self-study.

Table of Contents

Foreword	p. VII
About the Authors	p. IX
Preface	p. XI
Introduction	p. 1
Similarity of non-rigid shapes	p. 3
Correspondence problems	p. 6
A landscape of problems	p. 7
Notes	p. 9
A Taste of Geometry	p. 11
Basic terms in metric geometry and topology	p. 11
Isometries	p. 13
Length spaces	p. 17
Manifolds	p. 20
Embedded surfaces	p. 21
Curvature and the second fundamental form	p. 26
Intrinsic view on geometry of surfaces	p. 29
Bending and rigidity	p. 31
Intrinsic invariants	p. 34
Suggested reading	p. 37
Problems	p. 37
Notes	p. 39
Discrete Geometry	p. 41
Point clouds and sampling	p. 41
Farthest point sampling	p. 43
Voronoi tessellation	p. 46
Centroidal Voronoi sampling and the Lloyd-Max algorithm	p. 48
Connectivity	p. 52
Delaunay tessellation	p. 53
Triangular meshes	p. 54
Local feature size and curvature-dependent sampling	p. 57
Approximation quality	p. 61
Suggested reading	p. 63
Software	p. 63
Problems	p. 63
Notes	p. 64
Shortest Paths and Fast Marching Methods	p. 67
The shortest path problem	p. 67
Dijkstra's shortest path algorithm	p. 69
Fast marching methods	p. 71
Fast marching on parametric surfaces	p. 81
Marching even faster	p. 83
Parallel distance computation	p. 85
Minimal geodesics	p. 87
Suggested reading	p. 89
Software	p. 90
Problems	p. 90
Notes	p. 91
Numerical Optimization	p. 93
Local versus global optimization	p. 93
Optimality conditions	p. 94
Unconstrained optimization algorithms	p. 97
The quest for a descent direction	p. 100
Preconditioning	p. 104
Let Newton be!	p. 105
Truncated Newton	p. 106
Quasi-Newton algorithms	p. 107
Non-convex optimization	p. 108
Constrained optimization	p. 110
Penalty and barrier methods	p. 112
Augmented Lagrangian method	p. 114
Suggested reading	p. 116
Software	p. 116
Problems	p. 116
Notes	p. 118
In the Rigid Kingdom	p. 119
Moments of joy, moments of sorrow	p. 120
Iterative closest point algorithms	p. 125
Enter numerical optimization	p. 128
Rigid correspondence	p. 131
Suggested reading	p. 133
Software	p. 133
Problems	p. 133
Notes	p. 134
Multidimensional Scaling	p. 137
Isometric embedding problem	p. 138
Multidimensional scaling	p. 142
SMACOF algorithm	p. 143
Second-order methods	p. 146
Variations on the stress theme	p. 148
Multiresolution methods	p. 153
Multigrid MDS	p. 156
Vector extrapolation	p. 160
A trouble with topology	p. 164
Suggested reading	p. 165
Software	p. 166
Problems	p. 167
Notes	p. 167
Spectral Embedding	p. 169
Classic MDS	p. 170
Local methods	p. 173
The Laplace-Beltrami operator	p. 176
To hear the shape of the drum	p. 178
Discrete Laplace-Beltrami operator	p. 180
Suggested reading	p. 184
Software	p. 184
Problems	p. 184
Notes	p. 185
Non-Euclidean Embedding	p. 187
Spherical embedding	p. 187
Generalized multidimensional scaling	p. 192
Representation issues	p. 194
Geodesic distance computation	p. 197
Minimization of the generalized stress	p. 198
Multiresolution encore	p. 202
Suggested reading	p. 203
Software	p. 203
Problems	p. 204
Notes	p. 204
Isometry-Invariant Similarity	p. 205
Equivalence, similarity, and distance	p. 205
Embedding distance	p. 207
Gromov-Hausdorff distance	p. 208
Intrinsic symmetry	p. 211
Suggested reading	p. 214
Problems	p. 214
Partial Similarity	p. 217
Recognition by parts	p. 218
Paretian approach to partial similarity	p. 221
Scalar partial similarity	p. 224
Fuzzy approximation	p. 226
Extrinsic partial similarity	p. 229
Intrinsic partial similarity	p. 230
Not only size matters	p. 232
Suggested reading	p. 236
Problems	p. 236
Notes	p. 238
Non-rigid Correspondence and Calculus of Shapes	p. 239
Intrinsic parameterization	p. 240
An image processing approach	p. 241
Minimum distortion correspondence	p. 244
Texture mapping and transfer	p. 246
Morphing	p. 249
Guaranteed self-intersection free morph	p. 254
Calculus of shapes	p. 255
Suggested reading	p. 258
Software	p. 258
Problems	p. 259
Notes	p. 259
Three-dimensional Face Recognition	p. 261
Some terminology	p. 263
A retrospective	p. 264
Isometric model of facial expressions	p. 268
Expression-invariant face recognition	p. 269
Comparison of photometric properties	p. 273
Suggested reading	p. 275
Notes	p. 275
Epilogue	p. 277
Solutions of Selected Problems	p. 279
Software	p. 293
Notation	p. 297
Acronyms	p. 299
Glossary	p. 301
References	p. 307
Subject Index	p. 327
Author Index	p. 335
Table of Contents provided by Ingram. All Rights Reserved.