A Fast and Accurate Algorithm for Matching Images Using Hilbert Scanning Distance with Threshold Elimination Function

Sei-ichiro KAMATA
Haijiang TANG

IEICE TRANSACTIONS on Information and Systems   Vol.E89-D    No.1    pp.290-297
Publication Date: 2006/01/01
Online ISSN: 1745-1361
DOI: 10.1093/ietisy/e89-d.1.290
Print ISSN: 0916-8532
Type of Manuscript: PAPER
Category: Pattern Recognition
point pattern matching,  Hausdorff distance,  Hilbert curve,  Hilbert scanning distance,  threshold elimination function,  

Full Text: PDF(1.1MB)>>
Buy this Article

To find the best transformation between a "model" point set and an "image" point set is the main purpose of point pattern matching. The similarity measure plays a pivotal role and is used to determine the degree of resemblance between two objects. Although some well-known Hausdorff distance measures work well for this task, they are very computationally expensive and suffer from the noise points. In this paper, we propose a novel similarity measure using the Hilbert curve named Hilbert scanning distance (HSD) to resolve the problems. This method computes the distance measure in the one-dimensional (1-D) sequence instead of in the two-dimensional (2-D) space, which greatly reduces the computational complexity. By applying a threshold elimination function, large distance values caused by noise and position errors (e.g. those that occur with feature or edge extraction) are removed. The proposed algorithm has been applied to the task of matching edge maps with noise. The experimental results show that HSD can provide sufficient information for image matching within low computational complexity. We believe this sets a new direction for the research of point pattern recognition.

open access publishing via