A New Image Matching Algorithm for Change Detection using Hilbert Curve

Paper number

IAC-05-B1.P.04

Author

Mr. Li Tian, Waseda Universiy, Japan

Coauthor

Mr. Sei-ichiro Kamata, Waseda Universiy, Japan

Coauthor

Mr. Yoshifumi Ueshige, Japan

Coauthor

Mr. Yoshimitsu Kuroki, Japan

Year

2005

Abstract

Finding significant change in high resolution sensed image is an important task in maintaining GIS database. After extraction of feature points from a sensed image and a reference image, the feature points matching is a pivotal key in change detection. In general, given two point sets, find the minimum or maximal value of some measuring distances under the (affine) transformation. Because of the measurement errors and some outlying points, it is important that the measuring distances should be robust. Recently, a well–known robust measuring distance called the (partial) Hausdorff distance is widely used in feature points matching. It is more efficient than other conventional methods and has been applied in many fields. Although it is a reliable similarity measure, it is also a computational task. 
 In this paper, we present a new algorithm using Hilbert curve in order to resolve the computational complexity problem. Hilbert curve is a space filling curve. It has been studied, and many attractive features have been utilized in many applications for years. For a search image including both the feature points of a sensed image and a reference image, a Hilbert curve is chosen to convert the 2-D search area into a 1-D sequence of points. For each point of sensed image, a simple search to find the nearest point of the reference image can be utilized in the 1-D Hilbert scanned point sequence, and then calculate the Euclidean nom distance between the two matching points. Because of the characteristic of Hilbert curve, it is easy to understand that: if the distance of two matching points in the search image is small, the distance of them in the 1-D Hilbert scanned points sequence would also be small except in a few extreme points. At last, we select part of the ranked distances and calculate the average in order to reduce the extreme distance values which can be treated as noise. Eventually, the distance of our algorithm is relevant to the Hausdorff distance and it follows the change of Hausdorff distance: if the Hausdorff distance is small, the distance of our algorithm is also small. Therefore, our algorithm is also suitable for matching but has less computational complexity than the algorithms using Hausdorff distance.

Abstract document

IAC-05-B1.P.04.pdf

Manuscript document

IAC-05-B1.P.04.pdf (🔒 authorized access only).

To get the manuscript, please contact IAF Secretariat.