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 TR2010-045 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 = {}
      • }
  • 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.


  • Related News & Events

    •  NEWS   MERL researcher, Oncel Tuzel, gives keynote talk at 2016 International Symposium on Visual Computing
      Date: December 14, 2015 - December 16, 2015
      Where: Las Vegas, NV, USA
      Research Area: Machine Learning
      • MERL researcher, Oncel Tuzel, gave a keynote talk at 2016 International Symposium on Visual Computing in Las Vegas, Dec. 16, 2015. The talk was titled: "Machine vision for robotic bin-picking: Sensors and algorithms" and reviewed MERL's research in the application of 2D and 3D sensing and machine learning to the problem of general pose estimation.

        The talk abstract was: For over four years, at MERL, we have worked on the robot "bin-picking" problem: using a 2D or 3D camera to look into a bin of parts and determine the pose, 3D rotation and translation, of a good candidate to pick up. We have solved the problem several different ways with several different sensors. I will briefly describe the sensors and the algorithms. In the first half of the talk, I will describe the Multi-Flash camera, a 2D camera with 8 flashes, and explain how this inexpensive camera design is used to extract robust geometric features, depth edges and specular edges, from the parts in a cluttered bin. I will present two pose estimation algorithms, (1) Fast directional chamfer matching--a sub-linear time line matching algorithm and (2) specular line reconstruction, for fast and robust pose estimation of parts with different surface characteristics. In the second half of the talk, I will present a voting-based pose estimation algorithm applicable to 3D sensors. We represent three-dimensional objects using a set of oriented point pair features: surface points with normals and boundary points with directions. I will describe a max-margin learning framework to identify discriminative features on the surface of the objects. The algorithm selects and ranks features according to their importance for the specified task which leads to improved accuracy and reduced computational cost.
    •  NEWS   CVPR 2010: 8 publications by C. Oncel Tuzel, Tim K. Marks, Yuichi Taguchi, Srikumar Ramalingam, Michael J. Jones and Amit K. Agrawal
      Date: June 13, 2010
      Where: IEEE Conference on Computer Vision and Pattern Recognition (CVPR)
      MERL Contacts: Michael Jones; Tim Marks
      • The papers "Optimal Coded Sampling for Temporal Super-Resolution" by Agrawal, A.K., Gupta, M., Veeraraghavan, A.N. and Narasimhan, S.G., "Breaking the Interactive Bottleneck in Multi-class Classification with Active Selection and Binary Feedback" by Joshi, A.J., Porikli, F.M. and Papanikolopoulos, N., "Axial Light Field for Curved Mirrors: Reflect Your Perspective, Widen Your View" by Taguchi, Y., Agrawal, A.K., Ramalingam, S. and Veeraraghavan, A.N., "Morphable Reflectance Fields for Enhancing Face Recognition" by Kumar, R., Jones, M.J. and Marks, T.K., "Increasing Depth Resolution of Electron Microscopy of Neural Circuits using Sparse Tomographic Reconstruction" by Veeraraghavan, A., Genkin, A.V., Vitaladevuni, S., Scheffer, L., Xu, S., Hess, H., Fetter, R., Cantoni, M., Knott, G. and Chklovskii, D., "Specular Surface Reconstruction from Sparse Reflection Correspondences" by Sankaranarayanan, A., Veeraraghavan, A.N., Tuzel, C.O. and Agrawal, A.K., "Fast Directional Chamfer Matching" by Liu, M.-Y., Tuzel, C.O., Veeraraghavan, A.N. and Chellappa, R. and "Robust RVM regression using sparse outlier model" by Mitra, K., Veeraraghavan, A. and Chellappa, R. were presented at the IEEE Conference on Computer Vision and Pattern Recognition (CVPR).