Back to Search
Start Over
A Simple Algorithm for Approximate Partial Point Set Pattern Matching under Rigid Motion.
- Source :
- Walcom: Algorithms & Computation (9783642114397); 2010, p102-112, 11p
- Publication Year :
- 2010
-
Abstract
- This paper deals with the problem of approximate point set pattern matching in 2D. Given a set P of n points, called sample set, and a query setQ of k points (k ≤ n), the problem is to find a match of Q with a subset of P under rigid motion (rotation and/or translation) transformation such that each point in Q lies in the ε-neighborhood of a point in P. The ε-neighborhood region of a point p<subscript>i</subscript> ϵ P is an axis-parallel square having each side of length ε and p<subscript>i</subscript> at its centroid. We assume that the point set is well-seperated in the sense that for a given ε> 0, each pair of points p, p' ϵ P satisfy at least one of the following two conditions (i) |x(p) − x(p')| ≥ ε, and (ii) |y(p) − y(p')| ≥ 3ε, and we propose an algorithm for the approximate matching that can find a match (if it exists) under rigid motion in O(n<superscript>2</superscript>k<superscript>2</superscript>(klogk + logn)) time. If only translation is considered then the existence of a match can be tested in O(nk<superscript>2</superscript> logn) time. The salient feature of our algorithm for the rigid motion and translation is that it avoids the use of intersection of high degree curves. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISBNs :
- 9783642114397
- Database :
- Complementary Index
- Journal :
- Walcom: Algorithms & Computation (9783642114397)
- Publication Type :
- Book
- Accession number :
- 76743591
- Full Text :
- https://doi.org/10.1007/978-3-642-11440-3_10