Learning Manifolds in the Wild

One of Achille's heel of image processing and manifold signal processing in particular, revolves around the difficulty of building manifolds from images thanks to the apparent suboptimal capabilities of the euclidean norm. In short, the Euclidian norm doesn't provide a good means of evaluating similarity information when images are taken in different conditions (pose, illumination etc). Today's approach provides a refreshing look at this central, but often overlooked issue, through the use of the Earth Mover’s Distance on top of keypoint descriptors. Improvement could include the use of FREAK instead of SIFT and a faster Distance computations thanks to  the structure of FREAK or otherwise (see below)

Learning Manifolds in the Wild by Chinmay Hegde, Aswin C. Sankaranarayanan, Richard Baraniuk. The abtstract reads:

Despite the promise of low-dimensional manifold models for image processing, computer vision, and machine learning tasks, their utility has been hamstrung in practice by two fundamental challenges. First, practical image manifolds are non-isometric to their underlying parameter space, while the state-of-the-art manifold modeling and learning frameworks assume isometry. Second, practical image manifolds are strongly perturbed by nuisance parameters such as illumination variations, occlusions, and clutter. In this paper, we develop new theory and practical algorithms for manifold modeling, learning, and processing that directly address these challenges. To address the isometry challenge, we show that the Earth Mover’s Distance (EMD) is a more natural metric for inter-image distances than the standard Euclidean distance and use it to establish the isometry of manifolds generated by translations and rotations of a reference image. To the best of our knowledge, this is the first rigorous result on manifold isometry for generic grayscale image familes. To address the nuisance parameter challenge, we advocate an image representation based on local keypoint features and use it to define a new keypoint articulation manifold (KAM). We employ the KAM framework on a number of real-world image datasets acquired “in the wild” to demonstrate its improved performance over state-of-the-art manifold modeling approaches. A particularly compelling application of our approach is the automatic organization of large, unstructured collections of photographs gathered from the internet.

It turns out it seems possible to compute Earth Mover's Distance faster: Sublinear Time Algorithms for Earth Mover’s Distance by Khanh Do Ba, Huy L. Nguyen, Huy N. Nguyen, Ronitt Rubinfeld. The abstarct reads:

We study the problem of estimating the Earth Mover’s Distance (EMD) between probability distributions when given access only to samples of the distribution. We give closeness testers and additive-error estimators over domains in [0; 1]d , with sample complexities independent of domain size – permitting the testability even of continuous distributions over infinite domains. Instead, our algorithms depend on the dimension of the domain space and the quality of the result required. We also prove lower bounds showing the dependencies on these parameters to be essentially optimal. Additionally, we consider whether natural classes of distributions exist for which there are algorithms with better dependence on the dimension, and show that for highly clusterable data, this is indeed the case. Lastly, we consider a variant of the EMD, defined over tree metrics instead of the usual `1 metric, and give tight upper and lower bounds.

Join our Reddit Experiment, Join the CompressiveSensing subreddit and post there !
Liked this entry ? subscribe to Nuit Blanche's feed, there's more where that came from. You can also subscribe to Nuit Blanche by Email, explore the Big Picture in Compressive Sensing or the Matrix Factorization Jungle and join the conversations on compressive sensing, advanced matrix factorization and calibration issues on Linkedin.