language: en

Geometric Matching under Noise: Combinatorial Bounds and Algorithms

Piotr Indyk Rajeev Motwani Suresh Venkatasubramanian
Department of Computer Science Stanford University
Stanford, CA 94305
{indyk,rajeev,suresh}@cs.stanford.edu

Abstract The geometric point set matching problem in 2 and 3 dimensions is a well-studied problem with application to areas such as computer vision and pattern recognition, computational chemistry and other fields such as cartography and computer animation. The basic problems can be formulated as follows. Given some choice of a space of transformations and a similarity measure d(P; Q) for two point sets P and Q in Euclidean space. Problem 1 (Pattern Matching (PM)) Given point sets P and Q, where jP j = k and jQj = n with k n, and an * &gt; 0, find a transformation T for which d(T (P ); Q) * or return none if no such T exists. Problem 2 (Largest Common Point-set (LCP)) Given point sets P and Q, where jP j = m and jQj = n, K &gt; 0 and * &gt; 0, find a transformation T and a set P 0 P of size jP 0 j K such that jd(T (P 0 ); Q)j * or return none if no such T and P 0 exist. We restrict T to the space of rigid Euclidean translations and rotations. The similarity measures of interest to us are: the exact metric 1 d E (P; Q) (binary-valued, requiring each point in P to be mapped to a point in Q); the Hausdorff metric d H (P; Q) (maximum over all points in P of the distance to the nearest point in Q); and, the matching metric d M (bottleneck matching distance). A detailed study of this set of problems was initiated by Alt, Mehlhorn, Wagener, and Welzl [AMWW88]. In this seminal work, they propose a suite of algorithms for the exact and matching metrics. More recent work led to improved bounds for pattern matching and LCP under the exact metric. The problem of estimating the minimum Hausdorff distance between two point sets in 2 and 3 dimensions has been studied extensively. Clearly, any real application of such algorithms has to deal with the presence of noise in data, requiring the algorithms to perform matching within the limits of some reasonable noise model. In fact, our interest in these problems arose during an attempt to implement such algorithms for applications in computer vision and in computational biology and chemistry, particularly rational drug design [FKL + 97]. We discovered that noise present in real data rendered most known algorithms inoperative. In hindsight, this is not surprising for, as noted in the survey by Alt and Guibas [AG96], these algorithms are likely to be "difficult to implement and numerically unstable due to the necessary computation of intersections of complex algebraic surfaces." Worse still, they have unacceptably high running times: for example, even in R 2 , LCP under the matching metric requires O(n 8 ) time, although under additional restrictions on noise regions the running times can be

[This research is supported in part by a grant from Pfizer Central Research. Supported by NSF Award CCR-9357849, with matching funds from IBM, Mitsubishi, Schlumberger Foundation, Shell Foundation, and Xerox Corporation. Supported by an Alfred P. Sloan Research Fellowship, an IBM Faculty Partnership Award, an ARO MURI Grant DAAH04-96-1-0007, and NSF Young Investigator Award CCR-9357849, with matching funds from IBM, Mitsubishi, Schlumberger Foun dation, Shell Foundation, and Xerox Corporation.]

[1 We use the term "metric" only for convenience; formally, none of the above measures satisfy all the properties of a metric.]