Computing Correspondences in Geometric Data Sets
teaser image: examples of rigid registration, deformable shape matching, and symmetry detection
Eurographics 2011 Tutorial 
(EG Webpage)

Will Chang
UC San Diego

Hao Li
Columbia University

Niloy Mitra
KAUST / IIT Delhi

Mark Pauly
EPFL Lausanne

Szymon Rusinkiewicz
Princeton University

Michael Wand (organizer)
Saarland University / MPI Informatik		 photograph of the presenters



Abstract
Shape registration and, more generally speaking, computing correspondence across shapes are fundamental problems in computer graphics and vision. Problems from this area show up in many different variants such as scan registration, deformable shape matching, animation reconstruction, or finding partial symmetries of objects. Computing correspondences is a main prerequisite for higher level shape processing algorithms, such as building statistical models, non-local denoising, or inverse procedural modeling. Our tutorial addresses correspondence problems in geometric shapes. We will look at the problem from two different perspectives: In the first part of our tutorial, we will motivate the problem and explain the problem structure (formal models for shape matching), its variants (partial vs. complete matching, deformable vs. rigid, etc) and specific challenges (such as noise, incomplete data, and statistical descriptions thereof). In the second part, we will look at algorithms for solving these problems, and at applications of these. Again, we will focus on the main ideas and principles. Our overall goal is to give the attendee a "coordinate system" of the field, to convey the main problem structure and the main approaches to solve the problem, as well as open questions and research challenges. Topics covered will include rigid and deformable shape matching, local and global correspondence algorithms, as well as symmetry detection and applications.


Tutorial Slides Download

Data Sets
This is a collection of publically available data sets for deformable shape matching. If you are aware of a link that is missing, drop us an email.
  • König et al.'s motion compensated structured light scans at TU Dresden: repository page.
  • Weise et al.'s motion compensated structured light scans at ETH Zürich: repository page.
  • Vlasic et al.'s data photometric acquisition resutls at MIT: repository page.
  • Bradley et al.'s markerless garmet capture at UBC: repository page.
  • Solid Works Cosmic Blob test sequence at MIT: repository page.
  • Allen et al.'s human body scans at University of Washington: repository page.
  • Sumner et al.'s deformation transfer mesh data at MIT: repository page.
  • Pekelny and Gotsman's articulated object scans: download (thanks to the authors for the permission for hosting the data).
    The data set is taken from the following publication: Yuri Pekelny and Craig Gotsman: Articulated Object Reconstruction and Markerless Motion Capture from Depth Video. Computer Graphics Forum 27(2) (Eurographics), 2008.

References
This is a collection of references mentioned during the tutorial. The list is not indented to be exhaustive, only reflecting what we talked about during the tutorial.

Local Registration / Deformation Modeling
  • Allen, B., Curless, B., Popovic, Z.: The space of human body shapes: reconstruction and parameterization from range scans. In: ACM Trans. Graphics (Proc. Siggraph 2003), pp. 587–594, 2003.
  • Brown, B., Rusinkiewicz, S.: Global non-rigid alignment of 3-d scans. In: ACM Transactions on Graphics (Proc. Siggraph 2007) 26, 3, 2007.
  • Häehnel, D., Thrun, S., Burgard, W.: An extension of the icp algorithm for modeling nonrigid objects with mobile robots. In: Proc. Int. Joint Conf. on Artificial Intelligence (IJCAI), 2003.
  • Kraevoy, V., Sheffer, A.: Cross-parameterization and compatible remeshing of 3d models. In: ACM Trans. Graph. (Proc. SIGGRAPH 2004) 23, 3, 861–869, 2004.
  • Li, H., Sumner, R.W., Pauly, M.: Global correspondence optimization for non-rigid registration of depth scans. In: Computer Graphics Forum (Proc. SGP 2008), 27, 5, 2008.
  • Sumner, R. W., Schmid, J., Pauly, M.: Embedded deformation for shape manipulation. In: ACM Trans. Graph. (Proc. SIGGRAPH 2007), 2007.

Global Registration
  • Anguelov, D., Srinivasan, P., Koller, D., Thrun, S., Rodgers, J., Davis, J.: Scape: shape completion and animation of people. In: ACM Trans. Graph. 24, 3 (Proc. Siggraph 2005), 408–416, 2005.
  • Anguelov, D., Srinivasan, P., Pang, H.-C., Koller, D., Thrun, S., Davis, J.: The correlated correspondence algorithm for unsupervised registration of nonrigid surfaces. In: Proc. Neural Information Processing Systems (NIPS), 2004.
  • Chang, W., Zwicker, M.: Automatic Registration for Articulated Shapes. In: Computer Graphics Forum (Proceedings of SGP 2008), 27, 5 2008.
  • Chang, W., Zwicker, M.: Range scan registration using reduced deformable models. In: Computer Graphics Forum (Proc. Eurgraphics 2009) 28, 2, 447–456, 2009.
  • Gelfand, N., Mitra, N. J., Guibas, L. J., Pottmann, H.: Robust global registration. In: Symposium on Geometry Processing (2005), pp. 197–206.
  • Huang, Q.-X., Adams, B., Wicke, M., Guibas, L. J.: Non-rigid registration under isometric deformations. In: Computer Graphics Forum (Proc. SGP 2008), 27, 5, 2008.
  • Huang, Q.-X., Flöry, S., Gelfand, N., Hofer, M., Pottmann, H.: Reassembling fractured objects by geometric matching. In: ACM Trans. Graphics 25, 3, 569–578, 2006.
  • Johnson, A. E., Hebert, M.: Using spin images for efficient object recognition in cluttered 3d scenes. In: IEEE Trans. Pattern Anal. Mach. Intell. 21, 433–449, 1999.
  • Leordeanu, M., Hebert, M.: A spectral technique for correspondence problems using pairwise constraints. In: International Conference of Computer Vision (ICCV), vol. 2, pp. 1482–1489, October 2005.
  • Lasowski, R., Tevs, A., Seidel, H.-P., Wand, M.: A probabilistic framework for partial intrinsic symmetries in geometric data. In: IEEE International Conference on Computer Vision (ICCV), 2009.
  • Lipman Y., Funkhouser T.: Möbius voting for surface correspondence. In: ACM Transactions on Graphics 28(3) (Proc. Siggraph) , 2009.
  • Tevs, A., Bokeloh, M., Wand, M., Schilling, A., Seidel, H.-P.: Isometric registration of ambiguous and partial data. In: Proc. IEEE Conf. on Comp. Vision and Pattern Recognition (CVPR), 2009.
  • Torresani, L., Kolmogorov, V., Rother, C.: Feature correspondence via graph matching: Models and global optimization. In: Proc. Europ. Conf. Computer Vision (ECCV), 2008.
Animation Reconstruction / Multi-Piece Reconstruction
  • Huang, Q.-X., Adams, B., Wand, M.: Bayesian surface reconstruction via iterative scan alignment to an optimized prototype. In: Proc. 5th Eurographics Symposium on Geometry Processing, 2007.
  • Huber, D., Hebert, M.: Fully automatic registration of multiple 3d data sets. In: IEEE Computer Society Workshop on Computer Vision Beyond the Visible Spectrum (CVBVS 2001), December 2001.
  • Li, H., Adams, B., Guibas, L. J., Pauly, M.: Robust single-view geometry and motion reconstruction. In: ACM Trans. Graph. 28, 5, 2009.
  • Mitra, N. J., Flory, S., Ovsjanikov, M., Gelfand, N., Guibas, L., Pottmann, H.: Dynamic geometry registration. In: Symposium on Geometry Processing, pp. 173–182, 2007.
  • Pekelny, Y., Gotsman, C.: Articulated Object Reconstruction and Markerless Motion Capture from Depth Video. Computer Graphics Forum 27(2) (Eurographics), 2008.
  • Wand, M., Adams, B., Ovsjanikov, M., Berner, A., Bokeloh, M., Jenke, P., Guibas, L., Seidel, H.-P., Schilling, A.: Efficient reconstruction of nonrigid shape and motion from real-time 3d scanner data. In:  ACM Trans. Graph. 28, 2, 2009.
  • Wand, M., Jenke, P., Huang, Q., Bokeloh, M., Guibas, L., Schilling, A.: Reconstruction of deforming geometry from time-varying point clouds. In: SGP ’07: Proceedings of the fifth Eurographics Symposium on Geometry Processing, pp. 49–58, 2007.
Acquisition
  • Davis, J., Nehab, D., Ramamoorthi, R., Rusinkiewicz, S.: Spacetime stereo: A unifying framework for depth from triangulation. In: IEEE Transactions on Pattern Analysis and Machine Intelligence (PAMI) 27, 2, 296–302, Feb. 2005.
  • Weise, T., Leibe, B., Gool, L. J. V.: Fast 3d scanning with automatic motion compensation. In: IEEE Conf. on Computer Vision and Pattern Recognition (CVPR), 2007.
  • Zitnick, C. L., Kang, S. B., Uyttendaele, M., Winder, S., Szeliski, R.: High-quality video view interpolation using a layered representation. In: ACM Trans. on Graphics 23, 3, 600–608, 2004.
  • Zhang, L., Snavely, N., Curless, B., Seitz, S. M.: Spacetime faces: high resolution capture for modeling and animation. In: ACM Trans. Graphics (Proc. Siggraph 2004), pp. 548–558, 2004.
Symmetry Detection
  • Bokeloh, M., Berner, A., Wand, M., Seidel, H.-P., Schilling, A.: Symmetry detection using line features. In: Computer Graphics Forum 28(2) (Proc. Eurographics), 2009.
  • Mitra, N., Guibas, L.J., Pauly, M.: Partial and approximate symmetry detection for 3d geometry. In: ACM Transactions on Graphics 25(3) (Proc. Siggraph),  560–568, 2006.
  • Mitra, N., Guibas, L.J., Pauly, M.: Symmetrization. In: ACM Transactions on Graphics 26(3) (Proc. Siggraph), 2007.
  • Ovsjanikov, M.,  Sun, J., Guibas, L.J.: Global Intrinsic Symmetries of Shapes. In: Computer Graphics Forum, 27(5), 1341–1348, July 2008.
  • Pauly, M., Mitra, N. J., Wallner, J., Pottmann, H., Guibas, L.J.: Discovering structural regularity in 3D geometry. In: ACM Transactions on Graphics 27, 3 (Proc. Siggraph), 2008.
  • Podolak J., Shilane P., Golovinskiy A., Rusinkiewicz S., Funkhouser T.: A planar-reflective symmetry transform for 3D shapes. In: ACM Transactions on Graphics 25(3) (Proc. SIGGRAPH), 2006.
Applications
  • Duncan, J. S., Ayache, N.: Medical image analysis: Progress over two decades and the challenges ahead. In: IEEE Transactions on Pattern Analysis and Machine Intelligence (PAMI) 22, 1, 85–106, 2000.
  • Hasler, N., Stoll, C., Sunkel, M., Rosenhahn, B., Seidel, H.-P.: A statistical model of human pose and body shape. In: Computer Graphics Forum (Proc. Eurographics 2008), Munich, Germany, Mar. 2009.
  • Sumner, R. W., Popovic, J.: Deformation transfer for triangle meshes. In: ACM Trans. Graph. (Proc. SIGGRAPH 2004) 23, 3, 399–405, 2004.

Links
  • S. Rusinkiewicz, B. Brown, M. Kazhdan: 3D Scan Matching and Registration, ICCV 2005 Short Course. Website at Princeton University.
  • W. Chang, H. Li, N. Mitra, M. Pauly, M. Wand: Geometric Registration for Deformable Shapes, Eurographics 2010 Tutorial, project page. (predecessor to this course)