Svoboda | Graniru | BBC Russia | Golosameriki | Facebook

research-article

Point registration via efficient convex relaxation

Authors:

Shahar Kovalsky,

Yaron LipmanAuthors Info & Claims

ACM Transactions on Graphics (TOG), Volume 35, Issue 4

Article No.: 73, Pages 1 - 12

https://doi.org/10.1145/2897824.2925913

Published: 11 July 2016 Publication History

Abstract

Point cloud registration is a fundamental task in computer graphics, and more specifically, in rigid and non-rigid shape matching. The rigid shape matching problem can be formulated as the problem of simultaneously aligning and labelling two point clouds in 3D so that they are as similar as possible. We name this problem the Procrustes matching (PM) problem. The non-rigid shape matching problem can be formulated as a higher dimensional PM problem using the functional maps method. High dimensional PM problems are difficult non-convex problems which currently can only be solved locally using iterative closest point (ICP) algorithms or similar methods. Good initialization is crucial for obtaining a good solution.

We introduce a novel and efficient convex SDP (semidefinite programming) relaxation for the PM problem. The algorithm is guaranteed to return a correct global solution of the problem when matching two isometric shapes which are either asymmetric or bilaterally symmetric.

We show our algorithm gives state of the art results on popular shape matching datasets. We also show that our algorithm gives state of the art results for anatomical classification of shapes. Finally we demonstrate the power of our method in aligning shape collections.

Supplementary Material

ZIP File (a73-maron-supp.zip)

Supplemental files.

Download
215.19 KB

MP4 File (a73.mp4)

Download
101.02 MB

References

[1]

Anguelov, D., Srinivasan, P., Koller, D., Thrun, S., Rodgers, J., and Davis, J. (2005). SCAPE: shape completion and animation of people. In ACM Transactions on Graphics (TOG), volume 24, pages 408--416. ACM.

Digital Library

[2]

Aubry, M., Schlickewei, U., and Cremers, D. (2011). The wave kernel signature: A quantum mechanical approach to shape analysis. In Computer Vision Workshops (ICCV Workshops), 2011 IEEE International Conference on, pages 1626--1633. IEEE.

[3]

Babai, L., Grigoryev, D. Y., and Mount, D. M. (1982). Isomorphism of graphs with bounded eigenvalue multiplicity. In Proceedings of the Fourteenth Annual ACM Symposium on Theory of Computing, STOC '82, pages 310--324, New York, NY, USA. ACM.

Digital Library

[4]

Belkin, M. and Niyogi, P. (2003). Laplacian eigenmaps for dimensionality reduction and data representation. Neural computation, 15(6):1373--1396.

Digital Library

[5]

Berg, A. C., Berg, T. L., and Malik, J. (2005). Shape matching and object recognition using low distortion correspondences. In Computer Vision and Pattern Recognition, 2005. CVPR 2005. IEEE Computer Society Conference on, volume 1, pages 26--33. IEEE.

Digital Library

[6]

Besl, P. and McKay, N. (1992). A method for registration of 3d shapes. IEEE Transactions on Pattern Analysis and Machine Intelligence, 14(2):239--256.

Digital Library

[7]

Bogo, F., Romero, J., Loper, M., and Black, M. J. (2014). FAUST: Dataset and evaluation for 3D mesh registration. In Computer Vision and Pattern Recognition (CVPR), 2014 IEEE Conference on, pages 3794--3801. IEEE.

Digital Library

[8]

Boyer, D. M., Lipman, Y., Clair, E. S., Puente, J., Patel, B. A., Funkhouser, T., Jernvall, J., and Daubechies, I. (2011). Algorithms to automatically quantify the geometric similarity of anatomical surfaces. Proceedings of the National Academy of Sciences, 108(45):18221--18226.

[9]

Bronstein, A. M., Bronstein, M. M., and Kimmel, R. (2006). Generalized multidimensional scaling: A framework for isometry-invariant partial surface matching. Proceedings of the National Academy of Sciences of the United States of America, 103(5):1168--1172.

[10]

Brown, B. J. and Rusinkiewicz, S. (2007). Global non-rigid alignment of 3-d scans. ACM Transactions on Graphics (TOG), 26(3):21.

Digital Library

[11]

Chen, Q. and Koltun, V. (2015). Robust nonrigid registration by convex optimization. In Proceedings of the IEEE International Conference on Computer Vision, pages 2039--2047.

Digital Library

[12]

Dym, N. and Lipman, Y. (2016). Exact recovery with symmetries for procrustes matching. Technical report.

[13]

Eldar, Y., Lindenbaum, M., Porat, M., and Zeevi, Y. Y. (1997). The farthest point strategy for progressive image sampling. Image Processing, IEEE Transactions on, 6(9):1305--1315.

Digital Library

[14]

Fischler, M. A. and Bolles, R. C. (1981). Random sample consensus: a paradigm for model fitting with applications to image analysis and automated cartography. Communications of the ACM, 24(6):381--395.

Digital Library

[15]

Fukuda, M., Kojima, M., Murota, K., and Nakata, K. (2000). Exploiting sparsity in semidefinite programming via matrix completion I: General framework. SIAM J. on Optimization, 11(3):647--674.

Digital Library

[16]

Gelfand, N., Mitra, N. J., Guibas, L. J., and Pottmann, H. (2005). Robust global registration. In Proceedings of the Third Eurographics Symposium on Geometry Processing, SGP '05, Aire-la-Ville, Switzerland, Switzerland. Eurographics Association.

Digital Library

[17]

Giorgi, D., Biasotti, S., and Paraboschi, L. (2007). Shape retrieval contest 2007: Watertight models track. SHREC competition, 8.

[18]

Gower, J. C. and Dijksterhuis, G. B. (2004). Procrustes problems, volume 3. Oxford University Press Oxford.

[19]

Grone, R., Johnson, C. R., Sá, E. M., and Wolkowicz, H. (1984). Positive definite completions of partial Hermitian matrices. Linear algebra and its applications, 58:109--124.

[20]

Huang, Q., Wang, F., and Guibas, L. (2014). Functional map networks for analyzing and exploring large shape collections. ACM Trans. Graph., 33(4):36:1--36:11.

Digital Library

[21]

Jain, V., Zhang, H., and Van Kaick, O. (2007). Non-Rigid Spectral Correspondence of Triangle Meshes. International Journal of Shape Modeling, 13:101--124.

[22]

Kendall, D. G. (1984). Shape manifolds, Procrustean metrics, and complex projective spaces. Bulletin of the London Mathematical Society, 16(2):81--121.

[23]

Kezurer, I., Kovalsky, S. Z., Basri, R., and Lipman, Y. (2015). Tight relaxation of quadratic matching. Computer Graphics Forum, 34(5):115--128.

[24]

Kim, V. G., Lipman, Y., and Funkhouser, T. (2011). Blended intrinsic maps. ACM Transactions on Graphics, 30(4):1.

Digital Library

[25]

Leordeanu, M. and Hebert, M. (2005). A spectral technique for correspondence problems using pairwise constraints. In Computer Vision, 2005. ICCV 2005. Tenth IEEE International Conference on, volume 2, pages 1482--1489. IEEE.

Digital Library

[26]

Li, H., Sumner, R. W., and Pauly, M. (2008). Global correspondence optimization for non-rigid registration of depth scans. In Computer Graphics Forum, volume 27, pages 1421--1430. Wiley Online Library.

Digital Library

[27]

Lipman, Y. and Funkhouser, T. (2009). Möbius voting for surface correspondence. In ACM Transactions on Graphics (TOG), volume 28, page 72. ACM.

Digital Library

[28]

Luo, Z.-Q., Ma, W.-k., So, A. M.-C., Ye, Y., and Zhang, S. (2010). Semidefinite relaxation of quadratic optimization problems. Signal Processing Magazine, IEEE, 27(3):20--34.

[29]

Mémoli, F. and Sapiro, G. (2004). Comparing point clouds. In Proceedings of the 2004 Eurographics/ACM SIGGRAPH Symposium on Geometry Processing, SGP '04, pages 32--40, New York, NY, USA. ACM.

Digital Library

[30]

Mitteroecker, P. and Gunz, P. (2009). Advances in geometric mor-phometrics. Evolutionary Biology, 36(2):235--247.

[31]

MOSEK (2015). The MOSEK optimization toolbox for MATLAB manual. Version 7.1 (Revision 49).

[32]

Nguyen, A., Ben-Chen, M., Welnicka, K., Ye, Y., and Guibas, L. (2011). An optimization approach to improving collections of shape maps. Computer Graphics Forum, 30(5):1481--1491.

[33]

Ovsjanikov, M., Ben-Chen, M., Solomon, J., Butscher, A., and Guibas, L. (2012). Functional maps: a flexible representation of maps between shapes. ACM Transactions on Graphics (TOG), 31(4):30.

Digital Library

[34]

Ovsjanikov, M., Mérigot, Q., Mémoli, F., and Guibas, L. (2010). One point isometric matching with the heat kernel. In Computer Graphics Forum, volume 29, pages 1555--1564. Wiley Online Library.

[35]

Ovsjanikov, M., Sun, J., and Guibas, L. (2008). Global intrinsic symmetries of shapes. In Computer Graphics Forum, volume 27, pages 1341--1348. Wiley Online Library.

Digital Library

[36]

Pinkall, U. and Polthier, K. (1993). Computing discrete minimal surfaces and their conjugates. Experimental mathematics, 2(1):15--36.

[37]

Pokrass, J., Bronstein, A. M., Bronstein, M. M., Sprechmann, P., and Sapiro, G. (2013). Sparse modeling of intrinsic correspondences. Computer Graphics Forum, 32(2 PART4):459--468.

[38]

Poljak, S., Rendl, F., and Wolkowicz, H. (1995). A recipe for semidefinite relaxation for (0, 1)-quadratic programming. Journal of Global Optimization, 7(1):51--73.

[39]

Rusinkiewicz, S. and Levoy, M. (2001). Efficient variants of the ICP algorithm. Proceedings Third International Conference on 3-D Digital Imaging and Modeling, pages 145--152.

[40]

Rustamov, R. M. (2007). Laplace-Beltrami eigenfunctions for deformation invariant shape representation. In Proceedings of the Fifth Eurographics Symposium on Geometry Processing, SGP '07, pages 225--233, Aire-la-Ville, Switzerland, Switzerland. Eurographics Association.

Digital Library

[41]

Saunderson, J., Parrilo, P. A., and Willsky, A. S. (2014). Semidefinite descriptions of the convex hull of rotation matrices. arXiv preprint arXiv:1403.4914.

[42]

Singer, A. and Wu, H.-T. (2012). Vector diffusion maps and the connection laplacian. Communications on Pure and Applied Mathematics, 65(8):1067--1144.

[43]

Tam, G. K., Cheng, Z.-Q., Lai, Y.-K., Langbein, F. C., Liu, Y., Marshall, D., Martin, R. R., Sun, X.-F., and Rosin, P. L. (2013). Registration of 3D point clouds and meshes: a survey from rigid to nonrigid. Visualization and Computer Graphics, IEEE Transactions on, 19(7):1199--1217.

Digital Library

[44]

Tevs, A., Bokeloh, M., Wand, M., Schilling, A., and Seidel, H.-P. (2009). Isometric registration of ambiguous and partial data. In Computer Vision and Pattern Recognition, 2009. CVPR 2009. IEEE Conference on, pages 1185--1192. IEEE.

[45]

Van Kaick, O., Zhang, H., Hamarneh, G., and Cohen-Or, D. (2011). A survey on shape correspondence. In Computer Graphics Forum, volume 30, pages 1681--1707. Wiley Online Library.

[46]

Waki, H., Kim, S., Kojima, M., and Muramatsu, M. (2006). Sums of squares and semidefinite programming relaxations for polynomial optimization problems with structured sparsity. SIAM Journal on Optimization, 17:218--242.

Digital Library

[47]

Wand, M., Chang, W., Li, H., Mitra, N., Pauly, M., and Rusinkiewicz, S. (2011). Computing correspondences in geometric data sets tutorial. http://resources.mpi-inf.mpg.de/deformableShapeMatching/EG2011_Tutorial/.

[48]

Wei, L., Huang, Q., Ceylan, D., Vouga, E., and Li, H. (2015). Dense Human Body Correspondences Using Convolutional Networks.

[49]

Yang, J., Li, H., and Jia, Y. (2013). Go-ICP: Solving 3D Registration Efficiently and Globally Optimally. 2013 IEEE International Conference on Computer Vision, pages 1457--1464.

Digital Library

[50]

Zeng, Y., Wang, C., Wang, Y., Gu, X., Samaras, D., and Paragios, N. (2010). Dense non-rigid surface registration using high-order graph matching. In Computer Vision and Pattern Recognition (CVPR), 2010 IEEE Conference on, pages 382--389. IEEE.

[51]

Zhao, Q., Karisch, S. E., Rendl, F., and Wolkowicz, H. (1998). Semidefinite programming relaxations for the quadratic assignment problem. Journal of Combinatorial Optimization, 2(1):71--109.

[52]

Zuffi, S. and Black, M. J. (2015). The stitched puppet: A graphical model of 3D human shape and pose. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 3537--3546.

Cited By

Lim HKim BKim DMason Lee EMyung H(2024)Quatro++International Journal of Robotics Research10.1177/0278364923120765443:5(685-715)Online publication date: 1-Apr-2024
https://dl.acm.org/doi/10.1177/02783649231207654
Dang ZWang LGuo YSalzmann M(2024)Match Normalization: Learning-Based Point Cloud Registration for 6D Object Pose Estimation in the Real WorldIEEE Transactions on Pattern Analysis and Machine Intelligence10.1109/TPAMI.2024.335519846:6(4489-4503)Online publication date: Jun-2024
https://doi.org/10.1109/TPAMI.2024.3355198
She RKang QWang STay WZhao KSong YGeng TXu YNavarro DHartmannsgruber A(2024)PointDifformer: Robust Point Cloud Registration With Neural Diffusion and TransformerIEEE Transactions on Geoscience and Remote Sensing10.1109/TGRS.2024.335128662(1-15)Online publication date: 2024
https://doi.org/10.1109/TGRS.2024.3351286
Show More Cited By

Index Terms

Point registration via efficient convex relaxation
1. Computing methodologies
  1. Computer graphics
    1. Shape modeling
      1. Shape analysis

Recommendations

Convex relaxations for nonconvex quadratically constrained quadratic programming: matrix cone decomposition and polyhedral approximation

We present a decomposition-approximation method for generating convex relaxations for nonconvex quadratically constrained quadratic programming (QCQP). We first develop a general conic program relaxation for QCQP based on a matrix decomposition scheme ...
Separable Relaxation for Nonconvex Quadratic Integer Programming: Integer Diagonalization Approach

We present in this paper an integer diagonalization approach for deriving new lower bounds for general quadratic integer programming problems. More specifically, we introduce a semiunimodular transformation in order to diagonalize a symmetric matrix and ...
An alternative perspective on copositive and convex relaxations of nonconvex quadratic programs
Abstract
We study convex relaxations of nonconvex quadratic programs. We identify a family of so-called feasibility preserving convex relaxations, which includes the well-known copositive and doubly nonnegative relaxations, with the property that the ...

Comments

Information & Contributors

Information

Published In

ACM Transactions on Graphics Volume 35, Issue 4

July 2016

1396 pages

ISSN:0730-0301

EISSN:1557-7368

DOI:10.1145/2897824

Issue’s Table of Contents

Copyright © 2016 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 11 July 2016

Published in TOG Volume 35, Issue 4

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

89
Total Citations
View Citations
1,202
Total Downloads

Downloads (Last 12 months)55
Downloads (Last 6 weeks)2

Reflects downloads up to 03 Aug 2024

Other Metrics

View Author Metrics

Citations

Cited By

Lim HKim BKim DMason Lee EMyung H(2024)Quatro++International Journal of Robotics Research10.1177/0278364923120765443:5(685-715)Online publication date: 1-Apr-2024
https://dl.acm.org/doi/10.1177/02783649231207654
Dang ZWang LGuo YSalzmann M(2024)Match Normalization: Learning-Based Point Cloud Registration for 6D Object Pose Estimation in the Real WorldIEEE Transactions on Pattern Analysis and Machine Intelligence10.1109/TPAMI.2024.335519846:6(4489-4503)Online publication date: Jun-2024
https://doi.org/10.1109/TPAMI.2024.3355198
She RKang QWang STay WZhao KSong YGeng TXu YNavarro DHartmannsgruber A(2024)PointDifformer: Robust Point Cloud Registration With Neural Diffusion and TransformerIEEE Transactions on Geoscience and Remote Sensing10.1109/TGRS.2024.335128662(1-15)Online publication date: 2024
https://doi.org/10.1109/TGRS.2024.3351286
Wang ZXu XYao YLi NLiu Y(2024)OKR-Net: Overlapping Keypoints Registration Network for Large-Scale LiDAR Point CloudsIEEE Robotics and Automation Letters10.1109/LRA.2023.33426709:2(1254-1261)Online publication date: Feb-2024
https://doi.org/10.1109/LRA.2023.3342670
Liao YDi YZhu KZhou HLu MZhang YDuan QLiu J(2024)Local feature matching from detector-based to detector-free: a surveyApplied Intelligence10.1007/s10489-024-05330-354:5(3954-3989)Online publication date: 1-Mar-2024
https://dl.acm.org/doi/10.1007/s10489-024-05330-3
Damelin S(2024)ReferencesNear Extensions and Alignment of Data in ℝ n10.1002/9781394196814.biblio(149-156)Online publication date: 21-Jan-2024
https://doi.org/10.1002/9781394196814.biblio
Yan DWang WLi SSun PDuan WLiu S(2023)A Speedy Point Cloud Registration Method Based on Region Feature Extraction in Intelligent Driving SceneSensors10.3390/s2309450523:9(4505)Online publication date: 5-May-2023
https://doi.org/10.3390/s23094505
Magnet ROvsjanikov M(2023)Scalable and Efficient Functional Map Computations on Dense MeshesComputer Graphics Forum10.1111/cgf.1474642:2(89-101)Online publication date: 23-May-2023
https://doi.org/10.1111/cgf.14746
Lu FChen GLiu YZhang LQu SLiu SGu RJiang C(2023)HRegNet: A Hierarchical Network for Efficient and Accurate Outdoor LiDAR Point Cloud RegistrationIEEE Transactions on Pattern Analysis and Machine Intelligence10.1109/TPAMI.2023.328489645:10(11884-11897)Online publication date: 12-Jun-2023
https://dl.acm.org/doi/10.1109/TPAMI.2023.3284896
Zhang YSun ZZeng ZLam K(2023)Partial Point Cloud Registration With Deep Local FeatureIEEE Transactions on Artificial Intelligence10.1109/TAI.2022.32015054:5(1317-1327)Online publication date: Oct-2023
https://doi.org/10.1109/TAI.2022.3201505
Show More Cited By

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents