An Efficient Approximation Algorithm for Point Pattern Matching Under Noise

Details An Efficient Approximation Algorithm for Point Pattern Matching Under Noise An Efficient Approximation Algorithm for Point Pattern Matching Under Noise

2005-06-07

arxiv.org/abs/cs/0506019v4

Computer Science

Computer Vision and Pattern Recognition

18 pages

Scientific paper

Point pattern matching problems are of fundamental importance in various areas including computer vision and structural bioinformatics. In this paper, we study one of the more general problems, known as LCP (largest common point set problem): Let $\PP$ and $\QQ$ be two point sets in $\mathbb{R}^3$, and let $\epsilon \geq 0$ be a tolerance parameter, the problem is to find a rigid motion $\mu$ that maximizes the cardinality of subset $\II$ of $Q$, such that the Hausdorff distance $\distance(\PP,\mu(\II)) \leq \epsilon$. We denote the size of the optimal solution to the above problem by $\LCP(P,Q)$. The problem is called exact-LCP for $\epsilon=0$, and \tolerant-LCP when $\epsilon>0$ and the minimum interpoint distance is greater than $2\epsilon$. A $\beta$-distance-approximation algorithm for tolerant-LCP finds a subset $I \subseteq \QQ$ such that $|I|\geq \LCP(P,Q)$ and $\distance(\PP,\mu(\II)) \leq \beta \epsilon$ for some $\beta \ge 1$. This paper has three main contributions. (1) We introduce a new algorithm, called {\DA}, which gives the fastest known deterministic 4-distance-approximation algorithm for \tolerant-LCP. (2) For the exact-LCP, when the matched set is required to be large, we give a simple sampling strategy that improves the running times of all known deterministic algorithms, yielding the fastest known deterministic algorithm for this problem. (3) We use expander graphs to speed-up the \DA algorithm for \tolerant-LCP when the size of the matched set is required to be large, at the expense of approximation in the matched set size. Our algorithms also work when the transformation $\mu$ is allowed to be scaling transformation.

Affiliated with

Also associated with

No associations

Rating

An Efficient Approximation Algorithm for Point Pattern Matching Under Noise does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with An Efficient Approximation Algorithm for Point Pattern Matching Under Noise, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and An Efficient Approximation Algorithm for Point Pattern Matching Under Noise will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-535180