Combinatorial and Experimental Methods for Approximate Point Pattern  Matching

Combinatorial and Experimental Methods for Approximate Point Pattern Matching

0.00 Avg rating0 Votes
Article ID: iaor201113540
Volume: 38
Issue: 1
Start Page Number: 59
End Page Number: 90
Publication Date: Jan 2004
Journal: Algorithmica
Authors: , , ,
Keywords: computers: information
Abstract:

Point pattern matching is an important problem in computational geometry, with applications in areas like computer vision, object recognition, molecular modeling, and image registration. Traditionally, it has been studied in an exact formulation, where the input point sets are given with arbitrary precision. This leads to algorithms that typically have running times of the order of high‐degree polynomials, and require robust calculations of intersection points of high‐degree surfaces. We study approximate point pattern matching, with the goal of developing algorithms that are more efficient and more practical than exact algorithms. Our work is motivated by the observation that in practice, data sets that form instances of pattern matching problems are noisy, and so approximate formulations are more appropriate. We present new and efficient algorithms for approximate point pattern matching in two and three dimensions, based on approximate combinatorial distance bounds on sets of points, and via the use of methods from combinatorial pattern matching. We also present an average‐case analysis and a detailed empirical study of our methods.

Reviews

Required fields are marked *. Your email address will not be published.