Bronstein / Kimmel Numerical Geometry of Non-Rigid Shapes

1. Auflage 2008
ISBN: 978-0-387-73301-2
Verlag: Springer
Format: PDF
Kopierschutz: 1 - PDF Watermark

E-Book, Englisch, 346 Seiten

Reihe: Monographs in Computer Science

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.

Autoren/Hrsg.

Bronstein, Alexander M.

Bronstein, Michael M.

Kimmel, Ron

Inhaltsverzeichnis

1;Foreword;7
2;About the Authors;8
3;Preface;10
4;Introduction;20
4.1;Similarity of non-rigid shapes;22
4.2;Correspondence problems;25
4.3;A landscape of problems;26
4.4;Notes;28
5;A Taste of Geometry;29
5.1;Basic terms in metric geometry and topology;29
5.2;Isometries;31
5.3;Length spaces;35
5.4;Manifolds;38
5.5;Embedded surfaces;39
5.6;Curvature and the second fundamental form;44
5.7;Intrinsic view on geometry of surfaces;47
5.8;Bending and rigidity;49
5.9;Intrinsic invariants;52
5.10;Suggested reading;55
5.11;Problems;55
5.12;Notes;57
6;Discrete Geometry;59
6.1;Point clouds and sampling;59
6.2;Farthest point sampling;61
6.3;Voronoi tessellation;64
6.4;Centroidal Voronoi sampling and the Lloyd-Max algorithm;66
6.5;Connectivity;70
6.6;Delaunay tessellation;71
6.7;Triangular meshes;72
6.8;Local feature size and curvature-dependent sampling;75
6.9;Approximation quality;79
6.10;Suggested reading;81
6.11;Software;81
6.12;Problems;81
6.13;Notes;82
7;Shortest Paths and Fast Marching Methods;84
7.1;The shortest path problem;84
7.2;Dijkstra's shortest path algorithm;86
7.3;Fast marching methods;88
7.4;Fast marching on parametric surfaces;98
7.5;Marching even faster;100
7.6;Parallel distance computation;102
7.7;Minimal geodesics;104
7.8;Suggested reading;106
7.9;Software;107
7.10;Problems;107
7.11;Notes;108
8;Numerical Optimization;109
8.1;Local versus global optimization;109
8.2;Optimality conditions;110
8.3;Unconstrained optimization algorithms;113
8.4;The quest for a descent direction;116
8.5;Preconditioning;120
8.6;Let Newton be!;121
8.7;Truncated Newton;122
8.8;Quasi-Newton algorithms;123
8.9;Non-convex optimization;124
8.10;Constrained optimization;126
8.11;Penalty and barrier methods;128
8.12;Augmented Lagrangian method;130
8.13;Suggested reading;132
8.14;Software;132
8.15;Problems;132
8.16;Notes;134
9;In the Rigid Kingdom;135
9.1;Moments of joy, moments of sorrow;136
9.2;Iterative closest point algorithms;141
9.3;Enter numerical optimization;144
9.4;Rigid correspondence;147
9.5;Suggested reading;149
9.6;Software;149
9.7;Problems;149
9.8;Notes;150
10;Multidimensional Scaling;152
10.1;Isometric embedding problem;153
10.2;Multidimensional scaling;157
10.3;SMACOF algorithm;158
10.4;Second-order methods;161
10.5;Variations on the stress theme;163
10.6;Multiresolution methods;168
10.7;Multigrid MDS;171
10.8;Vector extrapolation;175
10.9;A trouble with topology;179
10.10;Suggested reading;180
10.11;Software;181
10.12;Problems;182
10.13;Notes;182
11;Spectral Embedding;183
11.1;Classic MDS;184
11.2;Local methods;187
11.3;The Laplace-Beltrami operator;190
11.4;To hear the shape of the drum;192
11.5;Discrete Laplace-Beltrami operator;194
11.6;Suggested reading;198
11.7;Software;198
11.8;Problems;198
11.9;Notes;199
12;Non-Euclidean Embedding;201
12.1;Spherical embedding;201
12.2;Generalized multidimensional scaling;206
12.3;Representation issues;208
12.4;Geodesic distance computation;211
12.5;Minimization of the generalized stress;212
12.6;Multiresolution encore;216
12.7;Suggested reading;217
12.8;Software;217
12.9;Problems;218
12.10;Notes;218
13;Isometry-Invariant Similarity;219
13.1;Equivalence, similarity, and distance;219
13.2;Embedding distance;221
13.3;Gromov-Hausdorff distance;222
13.4;Intrinsic symmetry;225
13.5;Suggested reading;228
13.6;Problems;228
14;Partial Similarity;230
14.1;Recognition by parts;231
14.2;Paretian approach to partial similarity;234
14.3;Scalar partial similarity;237
14.4;Fuzzy approximation;239
14.5;Extrinsic partial similarity;242
14.6;Intrinsic partial similarity;243
14.7;Not only size matters;245
14.8;Suggested reading;249
14.9;Problems;249
14.10;Notes;251
15;Non-rigid Correspondence and Calculus of Shapes;252
15.1;Intrinsic parameterization;253
15.2;An image processing approach;254
15.3;Minimum distortion correspondence;257
15.4;Texture mapping and transfer;259
15.5;Morphing;262
15.6;Guaranteed self-intersection free morph;267
15.7;Calculus of shapes;268
15.8;Suggested reading;271
15.9;Software;271
15.10;Problems;272
15.11;Notes;272
16;Three-dimensional Face Recognition;273
16.1;Some terminology;275
16.2;A retrospective;276
16.3;Isometric model of facial expressions;280
16.4;Expression-invariant face recognition;281
16.5;Comparison of photometric properties;285
16.6;Suggested reading;287
16.7;Notes;287
17;Epilogue;288
18;Solutions of Selected Problems;289
19;Software;302
20;Notation;305
21;Acronyms;307
22;Glossary;309
23;References;314
24;Subject Index;334
25;Author Index;341