Numerical Geometry of Non-Rigid Shapes (eBook)

Foreword 7
About the Authors 8
Preface 10
Introduction 20
Similarity of non-rigid shapes 22
Correspondence problems 25
A landscape of problems 26
Notes 28
A Taste of Geometry 29
Basic terms in metric geometry and topology 29
Isometries 31
Length spaces 35
Manifolds 38
Embedded surfaces 39
Curvature and the second fundamental form 44
Intrinsic view on geometry of surfaces 47
Bending and rigidity 49
Intrinsic invariants 52
Suggested reading 55
Problems 55
Notes 57
Discrete Geometry 59
Point clouds and sampling 59
Farthest point sampling 61
Voronoi tessellation 64
Centroidal Voronoi sampling and the Lloyd-Max algorithm 66
Connectivity 70
Delaunay tessellation 71
Triangular meshes 72
Local feature size and curvature-dependent sampling 75
Approximation quality 79
Suggested reading 81
Software 81
Problems 81
Notes 82
Shortest Paths and Fast Marching Methods 84
The shortest path problem 84
Dijkstra's shortest path algorithm 86
Fast marching methods 88
Fast marching on parametric surfaces 98
Marching even faster 100
Parallel distance computation 102
Minimal geodesics 104
Suggested reading 106
Software 107
Problems 107
Notes 108
Numerical Optimization 109
Local versus global optimization 109
Optimality conditions 110
Unconstrained optimization algorithms 113
The quest for a descent direction 116
Preconditioning 120
Let Newton be! 121
Truncated Newton 122
Quasi-Newton algorithms 123
Non-convex optimization 124
Constrained optimization 126
Penalty and barrier methods 128
Augmented Lagrangian method 130
Suggested reading 132
Software 132
Problems 132
Notes 134
In the Rigid Kingdom 135
Moments of joy, moments of sorrow 136
Iterative closest point algorithms 141
Enter numerical optimization 144
Rigid correspondence 147
Suggested reading 149
Software 149
Problems 149
Notes 150
Multidimensional Scaling 152
Isometric embedding problem 153
Multidimensional scaling 157
SMACOF algorithm 158
Second-order methods 161
Variations on the stress theme 163
Multiresolution methods 168
Multigrid MDS 171
Vector extrapolation 175
A trouble with topology 179
Suggested reading 180
Software 181
Problems 182
Notes 182
Spectral Embedding 183
Classic MDS 184
Local methods 187
The Laplace-Beltrami operator 190
To hear the shape of the drum 192
Discrete Laplace-Beltrami operator 194
Suggested reading 198
Software 198
Problems 198
Notes 199
Non-Euclidean Embedding 201
Spherical embedding 201
Generalized multidimensional scaling 206
Representation issues 208
Geodesic distance computation 211
Minimization of the generalized stress 212
Multiresolution encore 216
Suggested reading 217
Software 217
Problems 218
Notes 218
Isometry-Invariant Similarity 219
Equivalence, similarity, and distance 219
Embedding distance 221
Gromov-Hausdorff distance 222
Intrinsic symmetry 225
Suggested reading 228
Problems 228
Partial Similarity 230
Recognition by parts 231
Paretian approach to partial similarity 234
Scalar partial similarity 237
Fuzzy approximation 239
Extrinsic partial similarity 242
Intrinsic partial similarity 243
Not only size matters 245
Suggested reading 249
Problems 249
Notes 251
Non-rigid Correspondence and Calculus of Shapes 252
Intrinsic parameterization 253
An image processing approach 254
Minimum distortion correspondence 257
Texture mapping and transfer 259
Morphing 262
Guaranteed self-intersection free morph 267
Calculus of shapes 268
Suggested reading 271
Software 271
Problems 272
Notes 272
Three-dimensional Face Recognition 273
Some terminology 275
A retrospective 276
Isometric model of facial expressions 280
Expression-invariant face recognition 281
Comparison of photometric properties 285
Suggested reading 287
Notes 287
Epilogue 288
Solutions of Selected Problems 289
Software 302
Notation 305
Acronyms 307
Glossary 309
References 314
Subject Index 334
Author Index 341