Object recognition requires that you know when two shapes are 'similar'. But what does similar mean? The mathematician says: make the set of all (two dimensional, three dimensional or higher) shapes into the points of an infinite-dimensional space and then put a metric on this space reflecting what 'similar' means. The background image is supposed to suggest this construction: here a certain set of eggs with varying shapes are each put in its own pigeon-hole. If, for example, our 'shapes' are taken to be open subsets of Euclidean space with smooth boundaries, then this space will be a Banach or Frechet manifold, but a highly non-linear one. The question of finding the right mathematical model for the space of such shapes is not unlike moduli problems and I tried to get a grip on this as soon as I looked at vision problems.
Around 2004 I met Peter Michor and found that he had systematically developed the foundations of differential geometry of such infinite dimensional spaces. This seemed to be the right tool for studying the above spaces of shapes. Since then, we have been studying various Riemannian metrics on them and their associated completions; the geodesics in these metrics and the curvature of the space; examples and applications to object recognition.
Abstract
The Earth Mover's Distance (EMD) between two weighted point sets (point distributions) is a distance measure commonly used in computer vision for color-based image retrieval and shape matching. It measures the minimum amount of work needed to transform one set into the other one by weight transportation. We study the following shape matching problem: Given two weighted point sets A and B in the plane, compute a rigid motion of A that minimizes its Earth Mover's Distance to B. No algorithm is known that computes an exact solution to this problem. We present simple FPTASs and polynomial-time (2+ε)-approximation algorithms for the minimum Euclidean EMD between A and B under translations and rigid motions. Earth Movers Distance