Embedding Images in non-Flat Spaces

Multi-dimensional scaling is an analysis tool which transforms pairwise distances between points to an embedding of points in space which are consistent with those distances. Two recent techniques in statistical patter recognition, locally linear embedding (LLE) and Isomap, give a mechanism for finding the structure underlying point sets for which comparisons or distances are only meaningful between nearby points. We give a direct method to extend the embedding algorithm to new topologies, finding the optimal embedding of points whose geodesic distance on a surface mathes the given pairwise distance measurements. Surfaces considered include spheres, cylinders, tori, and their higher dimensional corollaries. We give examples of sets of images that come from spaces with these topologies. Using these embedding techniques, we compute pose estimates for thousands of images of an object without knowing the object model or finding corresponding points.