Simple algorithms for partial point set pattern matching under rigid motion

doi:10.1016/j.patcog.2006.01.003

Simple algorithms for partial point set pattern matching under rigid motion

2006-09-01

19

PRE

AI

Bhargab B. Bhattacharya

DOI：10.1016/j.patcog.2006.01.003

原文链接

原文求助

摘要

En 中文

This paper presents simple and deterministic algorithms for partial point set pattern matching in 2D. Given a set P of n points, called sample set, and a query set Q of k points (n >= k), the problem is to find a matching of Q with a subset of P under rigid motion. The match may be of two types: exact and approximate. If an exact matching exists, then each point in Q coincides with the corresponding point in P under some translation and/or rotation. For an approximate match, some translation and/or rotation may be allowed such that each point in Q lies in a predefined epsilon-neighborhood region around some point in P. The proposed algorithm for the exact matching needs O(n(2)) space and O(n(2) log n) preprocessing time. The existence of a match for a given query set Q can be checked in O(k alpha log n) time in the worst-case, where a is the maximum number of equidistant pairs of point in P. For a set of n points, a may be O(n(4/3)) in the worst-case. Some applications of the partial point set pattern matching are then illustrated. Experimental results on random point sets and some fingerprint databases show that, in practice, the computation time is much smaller than the worst-case requirement. The algorithm is then extended for checking the exact match of a set of k line segments in the query set with a k-subset of n line segments in the sample set under rigid motion in O(kn log n) time. Next, a simple version of the approximate matching problem is studied where one point of Q exactly matches with a point of P, and each of the other points of Q lie in the s-neighborhood of some point of P. The worst-case time and space complexities of the proposed algorithm are O(n(2)k(2) log n) and O(n), respectively. The proposed algorithms will find many applications to fingerprint matching, image registration, and object recognition. (c) 2006 Pattern Recognition Society. Published by Elsevier Ltd. All rights reserved.

Keyword:

point set pattern matching

approximate matching

fingerprint matching

computational geometry

algorithms

complexity

Simple algorithms for partial point set pattern matching under rigid motion

摘要

AI总结

期刊

机构

引用论文