Foundations and Trends® in Computer Graphics and Vision > Vol 5 > Issue 3–4

Geodesic Methods in Computer Vision and Graphics

Gabriel Peyré, Ceremade, UMR CNRS 7534, Université Paris-Dauphine, Place de Lattre de Tassigny, France, peyre@ceremade.dauphine.fr Mickael Péchaud, DI École Normale Supérieure, France, mickael.pechaud@normalesup.org Renaud Keriven, IMAGINE-LIGM, École des Ponts ParisTech, France, keriven@imagine.enpc.fr Laurent D. Cohen, Ceremade, UMR CNRS 7534, Université Paris-Dauphine, Place de Lattre de Tassigny, France, cohen@ceremade.dauphine.fr
 
Suggested Citation
Gabriel Peyré, Mickael Péchaud, Renaud Keriven and Laurent D. Cohen (2010), "Geodesic Methods in Computer Vision and Graphics", Foundations and Trends® in Computer Graphics and Vision: Vol. 5: No. 3–4, pp 197-397. http://dx.doi.org/10.1561/0600000029

Published: 08 Dec 2010
© 2010 G. Peyré, M. Péchaud, R. Keriven and L. D. Cohen
 
Subjects
Shape,  Image and video processing
 
 
Download article
 
In this article:
1. Theoretical Foundations of Geodesic Methods
2. Numerical Foundations of Geodesic Methods
3. Geodesic Segmentation
4. Geodesic Sampling
5. Geodesic Analysis of Shape and Surface
References

Abstract

This monograph reviews both the theory and practice of the numerical computation of geodesic distances on Riemannian manifolds. The notion of Riemannian manifold allows one to define a local metric (a symmetric positive tensor field) that encodes the information about the problem one wishes to solve. This takes into account a local isotropic cost (whether some point should be avoided or not) and a local anisotropy (which direction should be preferred). Using this local tensor field, the geodesic distance is used to solve many problems of practical interest such as segmentation using geodesic balls and Voronoi regions, sampling points at regular geodesic distance or meshing a domain with geodesic Delaunay triangles. The shortest paths for this Riemannian distance, the so-called geodesics, are also important because they follow salient curvilinear structures in the domain. We show several applications of the numerical computation of geodesic distances and shortest paths to problems in surface and shape processing, in particular segmentation, sampling, meshing and comparison of shapes. All the figures from this review paper can be reproduced by following the Numerical Tours of Signal Processing.

http://www.ceremade.dauphine.fr/~peyre/numerical-tour/

Several textbooks exist that include description of several manifold methods for image processing, shape and surface representation and computer graphics. In particular, the reader should refer to [42, 147, 208, 209, 213, 255] for fascinating applications of these methods to many important problems in vision and graphics. This review paper is intended to give an updated tour of both foundations and trends in the area of geodesic methods in vision and graphics.

DOI:10.1561/0600000029
ISBN: 978-1-60198-396-1
212 pp. $99.00
Buy book
 
ISBN: 978-1-60198-397-8
212 pp. $200.00
Buy E-book
 
Table of contents:
1. Theoretical Foundations of Geodesic Methods
2. Numerical Foundations of Geodesic Methods
3. Geodesic Segmentation
4. Geodesic Sampling
5. Geodesic Analysis of Shape and Surface
References

Geodesic Methods in Computer Vision and Graphics

Geodesic methods are now a standard tool in computer vision and graphics. They offer a unifying framework to describe the local geometry of images, surfaces and higher dimensional datasets. Fast and efficient algorithms compute geodesic distances to a set of points and shortest paths between points. This paves the way towards powerful methods to solve many important problems in vision and graphics such as image segmentation, surface meshing and shapes comparison.

Geodesic Methods in Computer Vision and Graphics is an extended review of this emerging field and features the following: The mathematical foundations underlying these methods are explained in a clear and theoretically sound way; State of the art algorithms to compute shortest paths are thoroughly discussed; Several fields of application are reviewed, including medical imaging segmentation, 3-D surface sampling and shape retrieval. This book is of interest to students and researchers in computer vision and graphics who wish to understand the foundations and the recent developments in this area.

 
CGV-029