Automatic 3d free form shape matching using the graduated assignment algorithm.

Yonghuai Liu

Research output: Contribution to journalArticlepeer-review

31 Citations (SciVal)
192 Downloads (Pure)


Three-dimensional free form shape matching is a fundamental problem in both the machine vision and pattern recognition literatures. However, the automatic approach to 3D free form shape matching still remains open. In this paper, we propose using k closest points in the second view for the automatic 3D free form shape matching. For the sake of computational efficiency, the optimised k-D tree is employed for the search of the k closest points. Since occlusion and appearance and disappearance of points almost always occur, slack variables have to be employed, explicitly modelling outliers in the process of matching. Then the relative quality of each possible point match is estimated using the graduated assignment algorithm, leading the camera motion parameters to be estimated by the quaternion method in the weighted least-squares sense. The experimental results based on both synthetic data and real images without any pre-processing show the effectiveness and efficiency of the proposed algorithm for the automatic matching of overlapping 3D free form shapes with either sparse or dense points.
Original languageEnglish
Pages (from-to)1615-1631
Number of pages17
JournalPattern Recognition
Issue number10
Early online date14 Mar 2005
Publication statusPublished - 01 Oct 2005


  • 3D free form shape
  • automatic matching
  • k closest points
  • graduated assignment
  • optimised k-D tree
  • time complexity
  • space complexity


Dive into the research topics of 'Automatic 3d free form shape matching using the graduated assignment algorithm.'. Together they form a unique fingerprint.

Cite this