Image Manifolds which are Isometric to Euclidean Space

Recently, the Isomap procedure [10] was proposed as a new way to recover a low-dimensional parametrization of data lying on a low-dimensional submanifold in high-dimensional space. The method assumes that the submanifold, viewed as a Riemannian submanifold of the ambient high-dimensional space, is isometric to a convex subset of Euclidean space. This naturally raises the question: what datasets can reasonably be modeled by this condition? In this paper, we consider a special kind of image data: families of images generated by articulation of one or several objects in a scene—for example, images of a black disk on a white background with center placed at a range of locations. The collection of all images in such an articulation family, as the parameters of the articulation vary, makes up an articulation manifold, a submanifold of L². We study the properties of such articulation manifolds, in particular, their lack of differentiability when the images have edges. Under these conditions, we show that there exists a natural renormalization of geodesic distance which yields a well-defined metric. We exhibit a list of articulation models where the corresponding manifold equipped with this new metric is indeed isometric to a convex subset of Euclidean space. Examples include translations of a symmetric object, rotations of a closed set, articulations of a horizon, and expressions of a cartoon face.

The theoretical predictions from our study are borne out by empirical experiments with published Isomap code. We also note that in the case where several components of the image articulate independently, isometry may fail; for example, with several disks in an image avoiding contact, the underlying Riemannian manifold is locally isometric to an open, connected, but not convex subset of Euclidean space. Such a situation matches the assumptions of our recently-proposed Hessian Eigenmaps procedure, but not the original Isomap procedure.

Authors and Affiliations

1. Department of Statistics, Stanford University, 390 Serra Mall, Stanford, CA, 94305-4065, USA

   David L. Donoho

2. Google, Inc., 1600 Amphithatre Parkway, Mountain View, CA, 94043

   Carrie Grimes

Corresponding author

Correspondence to Carrie Grimes.

This work has been partially supported by National Science Foundation grant DMS 00-72661, and by DARPA Applied and Computational Mathematics Program.

David L. Donoho is Anne T. and Robert M. Bass Professor in the Humanities and Sciences at Stanford University. He received his A.B. in Statistics at Princeton University where his thesis adviser was John W. Tukey and his Ph.D. in Statistics at Harvard University, where his thesis adviser was Peter J. Huber. He is a member of the US National Academy of Sciences and of the American Academy of Arts and Sciences. According to the Institute for Scientific Information, he was the most cited author in the Mathematical Sciences for 1991–2000.

Carrie Grimes is a Senior Research Scientist in the Search Quality group at Google, Inc. in Mountain View, CA. She received her A.B. in Anthropology/Archaeology at Harvard University in 1998 where her thesis advisor was William Fash, and her Ph.D. in Statistics at Stanford University in 2003 where her thesis advisor was David L. Donoho.

Reprints and permissions