Robust Hausdorff distance for shape matching

Wai Pak Choi, Kin Man Lam, Wan Chi Siu

Research output: Journal article publicationConference articleAcademic researchpeer-review

1 Citation (Scopus)


The Hausdorff distance can be used to measure the similarity of two point sets. In matching the two point sets, one of them is translated, rotated and scaled in order to obtain an optimal matching, which is a computationally intensive process. In this paper, a robust line-feature-based approach for model-based recognition is presented, which can achieve good matching, even in a noisy environment or with the existence of occlusion. We propose three different ways for forming the line segments for a point set. Two of the methods are based on a fixed reference point, which are the centroid and the center of the minimal disk of the point set. The third method is based on the longest possible line segments formed within the point set. The line features extracted based on the respective line segments are insensitive to noise and can be used to determine the rotation and scale of the image point set accurately and reliably, and more importantly, 2D-2D matching algorithm can be adopted. The first 2D-matching is to compute the relative scale and orientation between the two point sets. Having rotated and scaled the image point set, the M-Estimation Hausdorff distance is applied for the second 2D-matching to measure the relative translation between the query point set and the model point set. This 2D-2D matching can greatly reduce the required memory and computation when compared to a 4D-matching. Both the performance and the sensitivity to noise of our algorithms are evaluated using simulated data. Experiments show that our 2D-2D algorithms can yield a high level of performance when determining the scale, the orientation and the similarity of two point sets.
Original languageEnglish
Pages (from-to)793-804
Number of pages12
JournalProceedings of SPIE - The International Society for Optical Engineering
Volume4671 II
Publication statusPublished - 1 Jan 2002
EventViual Communications and Image Processing 2002 - San Jose, CA, United States
Duration: 21 Jan 200223 Jan 2002


  • Hausdorff distance
  • Line features
  • Model-based recognition
  • Shape matching

ASJC Scopus subject areas

  • Electronic, Optical and Magnetic Materials
  • Condensed Matter Physics
  • Computer Science Applications
  • Applied Mathematics
  • Electrical and Electronic Engineering


Dive into the research topics of 'Robust Hausdorff distance for shape matching'. Together they form a unique fingerprint.

Cite this