“Möbius voting for surface correspondence” by Lipman and Funkhouser

  • ©Yaron Lipman and Thomas (Tom) A. Funkhouser




    Möbius voting for surface correspondence



    The goal of our work is to develop an efficient, automatic algorithm for discovering point correspondences between surfaces that are approximately and/or partially isometric.Our approach is based on three observations. First, isometries are a subset of the Möbius group, which has low-dimensionality — six degrees of freedom for topological spheres, and three for topological discs. Second, computing the Möbius transformation that interpolates any three points can be computed in closed-form after a mid-edge flattening to the complex plane. Third, deviations from isometry can be modeled by a transportation-type distance between corresponding points in that plane.Motivated by these observations, we have developed a Möbius Voting algorithm that iteratively: 1) samples a triplet of three random points from each of two point sets, 2) uses the Möbius transformations defined by those triplets to map both point sets into a canonical coordinate frame on the complex plane, and 3) produces “votes” for predicted correspondences between the mutually closest points with magnitude representing their estimated deviation from isometry. The result of this process is a fuzzy correspondence matrix, which is converted to a permutation matrix with simple matrix operations and output as a discrete set of point correspondences with confidence values.The main advantage of this algorithm is that it can find intrinsic point correspondences in cases of extreme deformation. During experiments with a variety of data sets, we find that it is able to find dozens of point correspondences between different object types in different poses fully automatically.


    1. Allen, B., Curless, B., and Popovic, Z. 2003. The space of human body shapes: reconstruction and parameterization from range scans. In SIGGRAPH ’03: ACM SIGGRAPH 2003 Papers, ACM Press, New York, NY, USA, 587–594. Google ScholarDigital Library
    2. Anguelov, D., Srinivasan, P., Pang, H., Koller, D., Thrun, S., and Davis, J. 2004. The correlated correspondence algorithm for unsupervised registration of nonrigid surfaces. In NIPS, vol. 17, 33–40.Google ScholarDigital Library
    3. Anguelov, D., Srinivasan, P., Koller, D., Thrun, S., Rodgers, J., and Davis, J. 2005. Scape: shape completion and animation of people. ACM Trans. on Graphics 24, 3, 408–416. Google ScholarDigital Library
    4. Audette, M. A., Ferrie, F. P., and Peters, T. M. 2000. An algorithmic overview of surface registration techniques for medical imaging. Medical Image Analysis 4, 3, 201–217.Google ScholarCross Ref
    5. Ballard, D. H. 1981. Generalizing the hough transform to detect arbitrary shapes. Pattern Recognition 13, 2, 111–122.Google ScholarCross Ref
    6. Berg, A. C., Berg, T. L., and Malik, J. 2005. Shape matching and object recognition using low distortion correspondence. In IEEE Computer Vision and Pattern Recognition (CVPR). Google ScholarDigital Library
    7. Besl, P. J., and McKay, N. D. 1992. A method for registration of 3-d shapes. IEEE Trans. Pattern Anal. Mach. Intell. 14, 2, 239–256. Google ScholarDigital Library
    8. Botsch, M., and Sorkine, O. 2008. On linear variational surface deformation methods. IEEE Transactions on Visualization and Computer Graphics 14, 1, 213–230. Google ScholarDigital Library
    9. Bronstein, A., Bronstein, M., and Kimmel, R. 2006. Generalized multidimensional scaling: A framework for isometryinvariant partial surface matching. Proceedings of the National Academy of Science, 1168–1172.Google Scholar
    10. Bronstein, A. M., Bronstein, M. M., and Kimmel, R. 2007. Calculus of non-rigid surfaces for geometry and texture manipulation. IEEE Trans. Visualization and Computer Graphics 13, 5, 902–913. Google ScholarDigital Library
    11. Bronstein, A. M., Bronstein, M. M., and Kimmel, R. 2008. Numerical Geometry of Non-Rigid Shapes. Springer. Google ScholarDigital Library
    12. Brown, B. J., and Rusinkiewicz, S. 2007. Global non-rigid alignment of 3-d scans. ACM Trans. Graph. 26, 3, 21. Google ScholarDigital Library
    13. Chui, H., and Rangarajan, A. 2003. A new point matching algorithm for non-rigid registration. Comput. Vis. Image Underst. 89, 2–3, 114–141. Google ScholarDigital Library
    14. Desbrun, M., Meyer, M., Schrder, P., and Barr, A. H. 2002. Discrete differential-geometry operators for triangulated 2-manifolds. Springer-Verlag, 35–57.Google Scholar
    15. Eckstein, I., Pons, J., Tong, Y., Kuo, C., and Desbrun, M. 2007. Generalized Surface Flows for Mesh Processing. In Symposium on Geometry Processing, 183–192. Google ScholarDigital Library
    16. Elad, A., and Kimmel, R. 2003. On bending invariant signatures for surfaces. IEEE Trans. Pattern Anal. Mach. Intell. 25, 10, 1285–1295. Google ScholarDigital Library
    17. Eldar, Y., Lindenbaum, M., Porat, M., and Zeevi, Y., 1997. The farthest point strategy for progressive image sampling.Google Scholar
    18. Funkhouser, T., and Shilane, P. 2006. Partial matching of 3d shapes with priority-driven search. In Symposium on Geometry Processing. Google ScholarDigital Library
    19. Gelfand, N., Mitra, N. J., Guibas, L. J., and Pottmann, H. 2005. Robust global registration. In Symposium on Geometry Processing. Google ScholarDigital Library
    20. Giorgi, D., Biasotti, S., and Paraboschi, L., 2007. SHREC:SHape REtrieval Contest: Watertight models track, http://watertight.ge.imati.cnr.it/.Google Scholar
    21. Gold, S., Rangarajan, A., Ping Lu, C., and Mjolsness, E. 1998. New algorithms for 2d and 3d point matching: Pose estimation and correspondence. Pattern Recognition 31, 957–964.Google ScholarCross Ref
    22. Hormann, K., Lvy, B., and Sheffer, A. 2007. Mesh parameterization: Theory and practice. In ACM SIGGRAPH Course Notes. Google ScholarDigital Library
    23. Huang, Q., Adams, B., Wicke, M., and Guibas, L. J. 2008. Non-rigid registration under isometric deformations. In Proc. of Eurographics Symposium on Geometry Processing 2008 (SGP), 1149–1458. Google ScholarDigital Library
    24. Jain, V., Zhang, H., and van Kaick, O. 2007. Non-rigid spectral correspondence of triangle meshes. International Journal on Shape Modeling 13, 1, 101–124.Google ScholarCross Ref
    25. Jin, M., Wang, Y., Yau, S.-T., and Gu, X. 2004. Optimal global conformal surface parameterization. In VIS ’04: Proceedings of the conference on Visualization ’04, IEEE Computer Society, Washington, DC, USA, 267–274. Google ScholarDigital Library
    26. Johnson, A., and Hebert, M. 1999. Using spin-images for efficient multiple model recognition in cluttered 3-D scenes. IEEE PAMI 21, 5, 433–449. Google ScholarDigital Library
    27. Kraevoy, V., and Sheffer, A. 2006. Mean-value geometry encoding. International Journal of Shape Modeling 12, 1.Google ScholarCross Ref
    28. Li, H., Sumner, R. W., and Pauly, M. 2008. Global correspondence optimization for non-rigid registration of depth scans. In Symposium on Geometry Processing. Google ScholarDigital Library
    29. Lipman, Y., Sorkine, O., Levin, D., and Cohen-Or, D. 2005. Linear rotation-invariant coordinates for meshes. ACM Trans. Graph. 24, 3, 479–487. Google ScholarDigital Library
    30. Lowe, D. 2004. Distinctive image features from scale-invariant keypoints. International Journal of Computer Vision 60, 2, 91–110. Google ScholarDigital Library
    31. Mitra, N. J., Guibas, L., and Pauly, M. 2007. Symmetrization. In ACM Transactions on Graphics (SIGGRAPH), vol. 26. Google ScholarDigital Library
    32. Ovsjanikov, M., Sun, J., and Guibas, L. 2008. Global intrinsic symmetries of shapes. In Eurographics Symposium on Geometry Processing, vol. 27. Google ScholarDigital Library
    33. Pauly, M., Mitra, N. J., Giesen, J., Gross, M., and Guibas, L. 2005. Example-based 3D scan completion. In Symposium on Geometry Processing, 23–32. Google ScholarDigital Library
    34. Pinkall, U., and Polthier, K. 1993. Computing discrete minimal surfaces and their conjugates. Experimental Mathematics 2, 15–36.Google ScholarCross Ref
    35. Polthier, K. 2005. Computational aspects of discrete minimal surfaces. Global Theory of Minimal Surfaces, Proc. of the Clay Mathematics Institute 2001 Summer School, David Hoffman (Ed.), CMI/AMS.Google Scholar
    36. Praun, E., and Hoppe, H. 2003. Spherical parametrization and remeshing. ACM Trans. Graph. 22, 3, 340–349. Google ScholarDigital Library
    37. Rubner, Y., Tomasi, C., and Guibas, L. J. 2000. The earth mover’s distance as a metric for image retrieval. Int. J. Comput. Vision 40, 2, 99–121. Google ScholarDigital Library
    38. Rusinkiewicz, S., and Levoy, M. 2001. Efficient variants of the ICP algorithm. In 3-D Digital Imaging and Modeling, 145–152.Google Scholar
    39. Sheffer, A., Gotsman, C., and Dyn, N. 2004. Robust spherical parameterization of triangular meshes. Computing 72, 1–2, 185–193. Google ScholarDigital Library
    40. Springer, G. 1981. Introduction to Riemann Surfaces. AMS Chelsea Publishing.Google Scholar
    41. Sumner, R., and Popovic, J. 2004. Deformation transfer for triangle meshes. ACM Trans. on Graphics (SIGGRAPH) 23, 3, 399–405. Google ScholarDigital Library
    42. Wang, S., Jin, M., and Gu, X. D. 2007. Conformal geometry and its applications on 3d shape matching, recognition, and stitching. IEEE Trans. Pattern Anal. Mach. Intell. 29, 7, 1209–1220. Member-Yang Wang and Member-Dimitris Samaras. Google ScholarDigital Library
    43. Zeng, W., Zeng, Y., Wang, Y., Yin, X., Gu, X., and Samaras, D. 2008. 3d non-rigid surface matching and registration based on holomorphic differentials. The 10th European Conference on Computer Vision (ECCV). Google ScholarDigital Library
    44. Zhang, H., Sheffer, A., Cohen-Or, D., Zhou, Q., van Kaick, O., and Tagliasacchi, A. 2008. Deformation-driven shape correspondence. Comput. Graph. Forum 27, 5, 1431–1439.Google ScholarDigital Library

ACM Digital Library Publication: