TR2010-045

Fast Directional Chamfer Matching


    •  Liu, M.-Y.; Tuzel, C.O.; Veeraraghavan, A.N.; Chellappa, R., "Fast Directional Chamfer Matching", IEEE Conference on Computer Vision and Pattern Recognition (CVPR), June 2010.
      BibTeX Download PDF
      • @inproceedings{Liu2010jun,
      • author = {Liu, M.-Y. and Tuzel, C.O. and Veeraraghavan, A.N. and Chellappa, R.},
      • title = {Fast Directional Chamfer Matching},
      • booktitle = {IEEE Conference on Computer Vision and Pattern Recognition (CVPR)},
      • year = 2010,
      • month = jun,
      • url = {http://www.merl.com/publications/TR2010-045}
      • }
  • Research Area:

    Computer Vision


TR Image

We study the object localization problem in images given a single hand-drawn example or a gallery of shapes as the object model. Although many shape matching algorithms have been proposed for the problem over the decades, chamfer matching remains to be the preferred method when speed and robustness are considered. In this paper, we significantly improve the accuracy of chamfer matching while reducing the computational time from linear to sublinear (shown empirically). Specifically, we incorporate edge orientation information in the matching algorithm such that the resulting cost function is piecewise smooth and the cost variation is tightly bounded. Moreover, we present a sublinear time algorithm for exact computation of the directional chamfer matching score using techniques from 3D distance transforms and directional integral images. In addition, the smooth cost function allows to be bound the cost distribution of large neighborhoods and skip the bad hypotheses within. Experiments show that the proposed approach improves the speed of the original chamfer matching upto an order of 45x, and it is much faster than many state of art techniques while the accuracy is comparable.