“Feature Matching With Bounded Distortion” by Lipman, Yagev, Poranne, Jacobs and Basri

  • ©Yaron Lipman, Stav Yagev, Roi Poranne, David W. Jacobs, and Ronen Basri

Conference:


Type:


Title:

    Feature Matching With Bounded Distortion

Session/Category Title: Surfaces, Deformation, and Correspondence

Presenter(s)/Author(s):


Moderator(s):


Abstract:


    We consider the problem of finding a geometrically consistent set of point matches between two images. We assume that local descriptors have provided a set of candidate matches, which may include many outliers. We then seek the largest subset of these correspondences that can be aligned perfectly using a nonrigid deformation that exerts a bounded distortion. We formulate this as a constrained optimization problem and solve it using a constrained, iterative reweighted least-squares algorithm. In each iteration of this algorithm we solve a convex quadratic program obtaining a globally optimal match over a subset of the bounded distortion transformations. We further prove that a sequence of such iterations converges monotonically to a critical point of our objective function. We show experimentally that this algorithm produces excellent results on a number of test sets, in comparison to several state-of-the-art approaches.

References:


    1. C. Barnes, E. Shechtman, A. Finkelstein, and D. B. Goldman. 2009. PatchMatch: A randomized correspondence algorithm for structural image editing. ACM Trans. Graph. 28, 3.
    2. S. Belongie, J. Malik, and J. Puzicha. 2002. Shape matching and object recognition using shape contexts. IEEE Trans. Pattern Anal. Mach. Intell. 24, 4, 509–522.
    3. A. C. Berg, T. L. Berg, and J. Malik. 2005. Shape matching and object recognition using low distortion correspondence. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR’05). 26–33.
    4. N. Bissantz, L. Dumbgen, A. Munk, and B. Stratmann. 2009. Convergence analysis of generalized iteratively reweighted least squares algorithms on convex function spaces. SIAM J. Optim. 19, 4, 1828–1845.
    5. D. Bommes, M. Campen, H.-C. Ebke, P. Alliez, and L. Kobbelt. 2013. Integer-grid maps for reliable quad meshing. ACM Trans. Graph. 32, 4.
    6. S. Bouaziz, A. Tagliasacchi, and M. Pauly. 2013. Sparse iterative closest point. Comput. Graph. Forum 32, 5, 1–11.
    7. A. M. Bronstein, M. M. Bronstein, and R. Kimmel. 2006. Efficient computation of isometry-invariant distances between surfaces. SIAM J. Sci. Comput. 28, 5, 1812–1836.
    8. M. Brown and D. G. Lowe. 2003. Recognising panoramas. In Proceedings of the IEEE International Conference on Computer Vision (ICCV’03). Vol. 2.
    9. T. Brox and J. Malik. 2011. Large displacement optical flow: Descriptor matching in variational motion estimation. IEEE Trans. Pattern Anal. Mach. Intell. 33, 3, 500–513.
    10. R. Chartrand and W. Yin. 2008. Iteratively reweighted algorithms for compressive sensing. In Proceedings of the IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP’08). 3869–3872.
    11. H. Chui and A. Rangarajan. 2003. A new point matching algorithm for non-rigid registration. Comput. Vis. Image Understand. 89, 2, 114–141.
    12. I. Daubechies, R. Devore, M. Fornasier, and C. S. I. Gntak. 2010. Iteratively reweighted least squares minimization for sparse recovery. Comm. Pure Appl. Math. 113, 1–38.
    13. O. Duchenne, F. Bach, I.-S. Kweon, and J. Ponce. 2011. A tensor-based algorithm for high-order graph matching. IEEE Trans. Pattern Anal. Mach. Intell. 33, 12, 2383–2395.
    14. U. Eckhardt. 1980. Webers problem and weiszfelds algorithm in general spaces. Math. Program. 18, 1, 186–196.
    15. M. Fischler and R. Bolles. 1981. Random sample consensus: A paradigm for model fitting with applications to image analysis and automated cartography. Comm. ACM 24, 6, 381–395.
    16. T. Funkhouser and P. Shilane. 2006. Partial matching of 3d shapes with priority-driven search. In Proceedings of the 4th Eurographics Symposium on Geometry Processing. 131–142.
    17. N. Gelfand, N. J. Mitra, L. J. Guibas, and H. Pottmann. 2005. Robust global registration. In Proceedings of the 3rd Eurographics Symposium on Geometry Processing.
    18. Y. Hacohen, E. Shechtman, D. B. Goldman, and D. Lischinski. 2011. Non-rigid dense correspondence with applications for image enhancement. ACM Trans. Graph. 70, 1–10.
    19. P. Heider, A. Pierre-Pierre, R. Li, and C. Grimm. 2011. Local shape descriptors: A survey and evaluation. In Proceedings of the Eurographics Workshop on 3D Object Retrieval.
    20. G. Hinton, C. Williams, and M. Revow. 1993. Adaptive elastic models for hand-printed character recognition. In Proceedings of the Conference on Neural Information Processing Systems (NIPS’93). 512.
    21. A. Jacobson, I. Baran, J. Popovic, and O. Sorkine. 2011. Bounded biharmonic weights for real-time deformation. ACM Trans. Graph. 30, 4, 1–78.
    22. B. Jian, B. Vemuri, and J. Marroquif. 2005. Robust nonrigid multimodal image registration using local frequency maps. In Information Processing in Medical Imaging, 289–301.
    23. C. L. Lawson. 1961. Contributions to the theory of linear least maximum approximations. Ph.D. thesis, University of California, Los Angeles.
    24. S. Lazebnik, C. Schmid, and J. Ponce. 2004. Semi-local affine parts for object recognition. In Proceedings of the British Machine Vision Conference (BMVC’04). Vol. 2. 959–968.
    25. S. Lazebnik, C. Schmid, and J. Ponce. 2005. A maximum entropy framework for part-based texture and object recognition. In Proceedings of the IEEE International Conference on Computer Vision (ICCV’05). Vol. 1, 832–838.
    26. M. Leordeanu and M. Hebert. 2005. A spectral technique for correspondence problems using pairwise constraints. In Proceedings of the IEEE International Conference on Computer Vision (ICCV’05). Vol. 2. 1482–1489.
    27. Y. Lipman. 2012. Bounded distortion mapping spaces for triangular meshes. ACM Trans. Graph. 31, 4, 108:1–108:13.
    28. D. G. Lowe. 2004. Distinctive image features from scale-invariant key-points. Int. J. Comput. Vis. 60, 2, 91–110.
    29. J. Montagnat, H. Delingette, and N. Ayache. 2001. A review of deformable surfaces: Topology, geometry and deformations. Image Vis. Comput. 19, 14, 1023–1040.
    30. A. Nealen, M. Muller, R. Keiser, E. Boxerman, and M. Carlson. 2006. Physically based deformable models in computer graphics. Comput. Graph. Forum 25, 4, 809–836.
    31. N. Snavely, S. M. Seitz, and R. Szeliski. 2006. Photo tourism: Exploring photo collections in 3d. In Proceedings of the Annual ACM SIGGRAPH Conference on Computer Graphics and Interactive Techniques. ACM Press, New York, 835–846.
    32. C. Strecha, W. Von Hansen, L. V. Gool, P. Fua, and U. Thoennessen. 2008. On benchmarking camera calibration and multi-view stereo for high resolution imagery. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR’08).
    33. A. Tevs, M. Bokeloh, M. Wand, A. Schilling, and H.-P. Seidel. 2009. Isometric registration of ambiguous and partial data. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR’09).
    34. T. Tuytelaars and K. Mikolajczyk. 2008. Local invariant feature detectors: A survey. Found. Trends Comput. Graph. Vis. 3, 3, 177–280.
    35. O. van Kaick, H. Zhang, G. Hamarneh, and D. Cohen-Or. 2011. A survey on shape correspondence. Comput. Graph. Forum 30, 6.
    36. A. Vedaldi and B. Fulkerson. 2014. Vlfeat vision software. http://www. vlfeat.org/.
    37. Y. Zheng and D. Doermann. 2006. Robust point matching for non-rigid shapes by preserving local neighborhood structures. IEEE Trans. Pattern Anal. Mach. Intell. 28, 4, 643–649.

ACM Digital Library Publication:


Overview Page: