Map Synchronization: from Object Correspondences to Neural Networks

Tutorial at CVPR 2019
Sunday, June 16th, 9:00 am - 12:30 pm
201B, Long Beach Convention Center, Long Beach, CA


  • Qi-Xing Huang: Department of Computer Science, The University of Texas at Austin

  • Xiao-Wei Zhou: College of Computer Science & the State Key Laboratory of CAD&CG, Zhejiang University

  • Jun-Yan Zhu: Electrical Engineering and Computer Science Department, Massachusetts Institute of Technology

  • Ting-Hui Zhou: Electrical Engineering and Computer Science Department, University of California at Berkeley

Ehsan    Amit    Amin    Amin   


Establishing maps (e.g. pointwise correspondences) across object collections is a fundamental problem spanning many scientific domains. High-quality maps facilitating information propagation and transformation are key to applications ranging from multiview structure from motion, 3D reconstruction with partial scans, data-driven geometry completion and reconstruction, texture transfer, to comparative biology, joint data-analysis, and data exploration and organization. In the deep learning era, the concept of maps naturally extends to neural networks between different domains.

High quality object maps are generally difficult to compute. Prior work on map computation focused on optimizing maps between pairs of objects. Despite the significant progress, state-of-the-art techniques tends to hit a barrier on the quality of maps that are computed in a pairwise manner. Building upon the availability of big-data, a recent line of research considered computing many pairwise maps jointly among a collection of objects (or map synchronization). The promise of these approaches hinges upon the observation that one way to obtain a high quality pairwise map between dissimilar objects is to choose a path connecting these objects but consisting of consecutive similar shapes: maps between similar objects are typically of higher quality, and so is the resulted composed map. From a regularization perspective, joint map computation leverages the generic consistency of a network of maps among multiple objects, in which composition of maps along cycles are expected to be close to the identity map.

In this tutorial, we cover different map synchronization techniques, including the ones that are based on graph theory, the ones that are based on combinatorial optimization, and the ones that are based on modern optimization techniques such as spectral decomposition, convex optimization, non-convex optimization and MAP inference. We also cover recent techniques that jointly optimize neural networks across multiple domains. Besides optimization techniques, we will also discuss the applications of map synchronization in multi-view based geometry reconstruction (RGB images or RGBD images), jointly analysis of image collections, and 3D reconstruction and understanding across multiple domains.


  • 10:40am-10:50am: break


The intended audience are academicians, graduate students and industrial researchers who are interested in the state-of-the-art techniques for multi-view structure-from-motion, geometry reconstruction from depth-scans, dense image flows, unsupervised object discovery and joint learning of neural networks. The tutorial is self-contained.


  • Qixing Huang is an assistant professor at the University of Texas at Austin. He obtained his PhD in Computer Science from Stanford University and his MS and BS in Computer Science from Tsinghua University. He was a research assistant professor at Toyota Technological Institute at Chicago before joining UT Austin. He has also worked at Adobe Research and Google Research. Dr. Huang's research spans the fields of computer vision, computer graphics, and machine learning. In particular, he is interested in designing new algorithms that process and analyze big geometric data (e.g., 3D shapes/scenes). He is also interested in statistical data analysis, compressive sensing, low-rank matrix recovery, and large-scale optimization, which provides theoretical foundation for his research. He also received the best paper award at the Symposium on Geometry Processing 2013. He is an area chair of CVPR 2019 and ICCV 2019.

  • Xiaowei Zhou is a Research Professor in Computer Science at Zhejiang University, China. He was a postdoctoral researcher in the Computer and Information Science Department at University of Pennsylvania. His research interests are on 3D vision problems including object pose estimation, shape reconstruction, human pose estimation and image matching. His current work attempts to combine geometry, optimization and learning methods to extract both semantic and geometric information of 3D object and scene from visual data. He co-organized the Workshops on Geometry Meets Deep Learning at ECCV 2016, ICCV 2017 and ECCV 2018 respectively, and the Tutorial on 3D Object Geometry from Single Image at 3DV 2016. He also served in the program committees or as a reviewer for many top conferences and journals such as CVPR, ICCV, ECCV, PAMI and IJCV.

  • Junyan Zhu is a postdoctoral researcher at MIT CSAIL. He obtained his Ph.D. in EECS from UC Berkeley in 2017 after spending five years at CMU and UC Berkeley. He received his B.E from Tsinghua University. His research interests are in computer vision, computer graphics, and machine learning, with the goal of building machines capable of understanding and recreating our visual world. He is a recipient of Facebook Fellowship, ACM SIGGRAPH Outstanding Doctoral Dissertation Award, and David J. Sakrison Memorial Prize for outstanding doctoral research from the Berkeley EECS. He has served on Technical Paper Committee at SIGGRAPH Asia 2018 and as a guest editor of International Journal of Computer Vision. See more details at

  • Tinghui Zhou is a PhD student in the EECS department at UC Berkeley. He obtained my Masters degree in Robotics from Carnegie Mellon University, and Bachelor's degree in Computer Science from University of Minnesota. His research interests are in computer vision, computer graphics, and machine learning. He has published at all major journals and conferences of graphics and vision including four orals papers at CVPR and ECCV.

References (Partial List)
6D Poses and Dense Correspondences

  • [Arrigoni et al., 2016] F. Arrigoni, B. Rossi, A. Fusiello. Spectral synchronization of multiple views in SE(3), SIAM Journal on Imaging Sciences 9 (4), 1963-1990, 2016.

  • [Bernard et al., 2015] F. Bernard, J. Thunberg, P. Gemmar, F. Hertel, A. Husch, J. Goncalves. A Solution for Multi-Alignment by Transformation Synchronisation. IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2015. .

  • [Bernard et al., 2018] F. Bernard, J. Thunberg, J. Goncalves, C. Theobalt. Synchronisation of Partial Multi-Matchings via Non-negative Factorisations, Pattern Recognition, 2019. .

  • [Chatterjee & Govindu, 2013] A. Chatterjee and V. M. Govindu. Efficient and robust large-scale rotation averaging. In ICCV, pages 521–528. IEEE Computer Society, 2013. .

  • [Crandall et al., 2011] D. Crandall, A. Owens, N. Snavely, and D. Huttenlocher. Discrete-continuous optimization for large-scale structure from motion. In CVPR ’11, pages 3001–3008, Washington, DC, USA, 2011. IEEE Computer Society. .

  • [Eriksson et al., 2018] A. Eriksson, C. Olsson, F. Kahl, T. J. Chin. Rotation averaging and strong duality, CVPR, 2018. .

  • [Hartley et al., 2013] R. Hartley, J. Trumpf, Y. Dai and H. Li. Rotation averaging. International Journal of Computer Vision, 2013. .

  • [Wei et al. 2016] L. Wei, Q. Huang, D. Ceylan, E. Vouga and H. Li. Dense Human Body Correspondences Using Convolutional Networks. 1544--1553. 2016. .

  • [Huber & Hebert, 2001] D. F. Huber and M. Hebert. Fully automatic registration of multiple 3d data sets. Image and Vision Computing, 21:637–650, 2001. .

  • [Leonardos et al., 2017] S. Leonardos, X. Zhou, and K. Daniilidis. Distributed consistent data association via permutation synchronization. In ICRA, pages 2645–2652. IEEE, 2017. .

  • [Nguyen et al., 2011] A. Nguyen, M. Ben-Chen, K. Welnicka, Y. Ye, and L. J. Guibas. An optimization approach to improving collections of shape maps. Comput. Graph. Forum, 30(5):1481–1491, 2011. .

  • [Pachauri et al., 2013] D. Pachauri, R. Kondor, and V. Singh. Solving the multi-way matching problem by permutation synchronization. In Neural Information Processing Systems 26, pages 1860–1868, 2013. .

  • [Thunberg et al. 2017] J. Thunberg, F. Bernard, J. Goncalves, Distributed methods for synchronization of orthogonal matrices over graphs, Automatica, 80. pp. 243-252, 2017. .

  • [Wilson & Snavely, 2016] K. Wilson and N. Snavely. Robust global translations with 1DSFM. European Conference on Computer Vision. 2016. .

  • [Zach et al., 2010] C. Zach, M. Klopschitz, and M. Pollefeys. Disambiguating visual relations using loop constraints. In CVPR, pages 1426–1433. IEEE Computer Society, 2010. .

  • [Zhou et al., 2015] X. Zhou, M. Zhu, and K. Daniilidis. Multi-image matching via fast alternating minimization. In ICCV,pages 4032–4040, Santiago, Chile, 2015. IEEE Computer Society. .

Data-Driven Object/Part Discovery

  • [Huang et al., 2014] Q. Huang, F. Wang, and L. Guibas. Functional map networks for analyzing and exploring large shape collections. ACM Trans. Graph., 33(4):36:1–36:11, July 2014. .

  • [Kim et al., 2012] V. Kim, W. Li, N. Mitra, S. DiVerdi, and T. Funkhouser. Exploring collections of 3d models using fuzzy correspondences. ACM Trans. Graph., 31(4):54:1–54:11, July 2012. .

  • [Ovsjanikov et al., 2012] M. Ovsjanikov, M. Ben-Chen, J. Solomon, A. Butscher, and L. J. Guibas. Functional maps: a flexible representation of maps between shapes. ACM Trans. Graph., 31(4):30:1–30:11, 2012. .

  • [Wang et al., 2013] F. Wang, Q. Huang, and L. J. Guibas. Image co-segmentation via consistent functional maps. In ICCV, pages 849–856, 2013. .

  • [Wang et al., 2014] F. Wang, Q. Huang, M. Ovsjanikov, and L. J. Guibas. Unsupervised multi-class joint image segmentation. In CVPR, pages 3142–3149. IEEE Computer Society, 2014. .

  • [Zhou et al., 2015] T. Zhou, Y. J. Lee, S. X. Yu, and A. A. Efros. Flowweb: Joint image set alignment by weaving consistent, pixel-wise correspondences. In CVPR, pages 1191–1200. IEEE Computer Society, 2015. .

Cross-Domain Matching

  • [Yi et al., 2017] Z. Yi, H. Zhang, P. Tan, and M. Gong. Dualgan: Unsupervised dual learning for image-to-image translation. CoRR, abs/1704.02510, 2017. .

  • [Zhou et al., 2016] T. Zhou, P. Krähenbühl, M. Aubry, Q. Huang, and A. A. Efros. Learning dense correspondence via 3d-guided cycle consistency. CoRR, abs/1604.05383, 2016. .

  • [Zhu et al., 2017] J. Zhu, T. Park, P. Isola, and A. A. Efros. Unpaired image-to-image translation using cycle-consistent adversarial networks. In ICCV, IEEE Computer Society, 2017. .

  • [Hoffman et al., 2018] Judy Hoffman, E. Tzeng, T. Park, J. Zhu, P. Isola, K. Saenko, A. Efros, and T. Darrell. CyCADA: Cycle-consistent adversarial domain adaptation. In ICML, 2018. .

  • [Zhang et al., 2019] Z. Zhang, Z. Liang, L. Wu, X. Zhou, and Q. Huang. Path-invariant map networks. In CVPR, IEEE Computer Society, 2019. .

Theorectical Aspects

  • [Huang et al., 2013] Q. Huang and L. J. Guibas. Consistent shape maps via semidefinite programming. Comput. Graph. Forum, 32(5):177–186, 2013. .

  • [Wang & Singer, 2013] L. Wang and A. Singer. Exact and stable recovery of rotations for robust synchronization. Information and Inference: A Journal of the IMA, 2:145â193, December 2013. .

  • [Shen et al., 2016] Y. Shen, Q. Huang, N. Srebro, and S. Sanghavi. Normalized spectral map synchronization. In NIPS, pages 4925–4933, 2016. .

  • [Huang et al., 2017] X. Huang, Z. Liang, C. Bajaj, and Q. Huang. Translation synchronization via truncated least squares.In NIPS, 2017. .

  • [Chen & Candes, 2016] Y. Chen and E. Candes. The projected power method: An efficient algorithm for joint alignment from pairwise differences. Communications on Pure and Applied Mathematics, 2018. .

  • [Chen et al., 2014] Y. Chen, L. J. Guibas, and Q. Huang. Near-optimal joint object matching via convex relaxation. In ICML, pages 100–108, 2014. .

  • [Arrigoni et al., 2018] F. Arrigoni, A. Fusiello, B. Rossi, and P. Fragneto. Robust rotation synchronization via low-rank and sparse matrix decomposition. Computer Vision and Image Understanding, 2018. 95-113. .

  • [Zhang et al., 2019] Z. Zhang, Z. Liang, L. Wu, X. Zhou, and Q. Huang. Path-invariant map networks. In CVPR, IEEE Computer Society, 2019. .

  • [Birdal et al., 2019] T. Birdal, U. Simsekli. Probabilistic Permutation Synchronization using the Riemannian Structure of the Birkhoff Polytope., 2019.

  • [Birdal et al., 2018] T. Birdal, U. Simsekli, M. Eken, S. Ilic. Bayesian Pose Graph Optimization via Bingham Distributions and Tempered Geodesic MCMC. In NIPS 2018.