Efficient reconstruction of nonrigid shape and motion from real-time 3D scanner data

ABSTRACT

We present a new technique for reconstructing a single shape and its nonrigid motion from 3D scanning data. Our algorithm takes a set of time-varying unstructured sample points that capture partial views of a deforming object as input and reconstructs a single shape and a deformation field that fit the data. This representation yields dense correspondences for the whole sequence, as well as a completed 3D shape in every frame. In addition, the algorithm automatically removes spatial and temporal noise artifacts and outliers from the raw input data. Unlike previous methods, the algorithm does not require any shape template but computes a fitting shape automatically from the input data. Our reconstruction framework is based upon a novel topology-aware adaptive subspace deformation technique that allows handling long sequences with complex geometry efficiently. The algorithm accesses data in multiple sequential passes, so that long sequences can be streamed from hard disk, not being limited by main memory. We apply the technique to several benchmark datasets, significantly increasing the complexity of the data that can be handled efficiently in comparison to previous work.

REFERENCES

• 1: Adams, B., Ovsjanikov, M., Wand, M., Seidel, H.-P., and Guibas, L. J. 2008. Meshless modeling of deformable shapes and their motion. In ACM SIGGRAPH/Eurographics Symposium on Computer Animation.
• 2: Ahmed, N., Theobalt, C., Roessl, C., Thrun, S., and Seidel, H.-P. 2008. Dense correspondence finding for parametrization-free animation reconstruction from video. In Proceedings of the Conference on Computer Vision and Pattern Recognition (CVPR).
• 3: Brett Allen , Brian Curless , Zoran Popović, Articulated body deformation from range scan data, Proceedings of the 29th annual conference on Computer graphics and interactive techniques, July 23-26, 2002, San Antonio, Texas
• 4: Brett Allen , Brian Curless , Zoran Popović, The space of human body shapes: reconstruction and parameterization from range scans, ACM SIGGRAPH 2003 Papers, July 27-31, 2003, San Diego, California
• 5: Anguelov, D., Koller, D., Srinivasan, P., Thrun, S., Pang, H.-C., and Davis, J. 2005. The correlated correspondence algorithm for unsupervised registration of nonrigid surfaces. In Proceedings of the Conference on Advances in Neural Information Processing Systems (NIPS ).
• 6: Dragomir Anguelov , Praveen Srinivasan , Daphne Koller , Sebastian Thrun , Jim Rodgers , James Davis, SCAPE: shape completion and animation of people, ACM SIGGRAPH 2005 Papers, July 31-August 04, 2005, Los Angeles, California
• 7: Anuar, N. and Guskov, I. 2004. Extracting animated meshes with adaptive motion estimation. In Proceedings of the Vision, Modeling and Visualization Conference. 63--71.
• 8: Oscar Kin-Chung Au , Chiew-Lan Tai , Ligang Liu , Hongbo Fu, Dual Laplacian Editing for Meshes, IEEE Transactions on Visualization and Computer Graphics, v.12 n.3, p.386-395, May 2006 [doi>10.1109/TVCG.2006.47]
• 9: Avriel, M. 2003. Nonlinear Programming: Analysis and Methods. Dover Publishing.
• 10: Paul J. Besl , Neil D. McKay, A Method for Registration of 3-D Shapes, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.14 n.2, p.239-256, February 1992 [doi>10.1109/34.121791]
• 11: Mario Botsch , Mark Pauly , Markus Gross , Leif Kobbelt, PriMo: coupled prisms for intuitive surface modeling, Proceedings of the fourth Eurographics symposium on Geometry processing, June 26-28, 2006, Cagliari, Sardinia, Italy
• 12: Botsch, M., Pauly, M., Wicke, M., and Gross, M. 2007. Adaptive space deformations based on rigid cells. Comput. Graph. Forum 26, 3, 339--347.
• 13: Mario Botsch , Olga Sorkine, On Linear Variational Surface Deformation Methods, IEEE Transactions on Visualization and Computer Graphics, v.14 n.1, p.213-230, January 2008 [doi>10.1109/TVCG.2007.1054]
• 14: Rodrigo L. Carceroni , Kiriakos N. Kutulakos, Multi-View Scene Capture by Surfel Sampling: From Video Streams to Non-Rigid 3D Motion, Shape and Reflectance, International Journal of Computer Vision, v.49 n.2-3, p.175-214, September-October 2002 [doi>10.1023/A:1020145606604]
• 15: Joel Carranza , Christian Theobalt , Marcus A. Magnor , Hans-Peter Seidel, Free-viewpoint video of human actors, ACM SIGGRAPH 2003 Papers, July 27-31, 2003, San Diego, California
• 16: Chang, W. and Zwicker, M. 2008. Automatic registration for articulated shapes. Comput. Graph. Forum 27, 5.
• 17: James Davis , Diego Nehab , Ravi Ramamoorthi , Szymon Rusinkiewicz, Spacetime Stereo: A Unifying Framework for Depth from Triangulation, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.27 n.2, p.296-302, February 2005 [doi>10.1109/TPAMI.2005.37]
• 18: Edilson de Aguiar , Carsten Stoll , Christian Theobalt , Naveed Ahmed , Hans-Peter Seidel , Sebastian Thrun, Performance capture from sparse multi-view video, ACM Transactions on Graphics (TOG), v.27 n.3, August 2008
• 19: Fong, P. and Buron, F. 2005. High-Resolution three-dimensional sensing of fast deforming objects. In Proceedings of the IEEE/RSI International Conference on Intelligent Robots and Systems, (IROS). 1606--1611.
• 20: Fries, T.-P. and Matthies, H. G. 2003. Classification and overview of meshfree methods. Tech. rep., TU Brunswick, Germany Nr. 2003-03.
• 21: Jin Huang , Xiaohan Shi , Xinguo Liu , Kun Zhou , Li-Yi Wei , Shang-Hua Teng , Hujun Bao , Baining Guo , Heung-Yeung Shum, Subspace gradient domain mesh deformation, ACM Transactions on Graphics (TOG), v.25 n.3, July 2006
• 22: Qi-Xing Huang , Bart Adams , Michael Wand, Bayesian surface reconstruction via iterative scan alignment to an optimized prototype, Proceedings of the fifth Eurographics symposium on Geometry processing, July 04-06, 2007, Barcelona, Spain
• 23: Huang, Q.-X., Adams, B., Wicke, M., and Guibas, L. J. 2008. Non-Rigid registration under isometric deformations. Comput. Graph. Forum 27, 5.
• 24: König, S. and Gumhold, S. 2007. Image-Based motion compensation for structured light scanning of dynamic scenes. In EG Workshop on Dynamic 3D Imaging (Dyn3D '07).
• 25: Li, H., Sumner, R. W., and Pauly, M. 2008. Global correspondence optimization for non-rigid registration of depth scans. Comput. Graph. Forum 27, 5.
• 26: Gerard Medioni , Mi-Suen Lee , Chi-Keung Tang, Computational Framework for Segmentation and Grouping, Elsevier Science Inc., New York, NY, 2000
• 27: MESA. 2009. http://www.mesa-imaging.ch.
• 28: Niloy J. Mitra , Simon Flöry , Maks Ovsjanikov , Natasha Gelfand , Leonidas Guibas , Helmut Pottmann, Dynamic geometry registration, Proceedings of the fifth Eurographics symposium on Geometry processing, July 04-06, 2007, Barcelona, Spain
• 29: M. Müller , R. Keiser , A. Nealen , M. Pauly , M. Gross , M. Alexa, Point based animation of elastic, plastic and melting objects, Proceedings of the 2004 ACM SIGGRAPH/Eurographics symposium on Computer animation, August 27-29, 2004, Grenoble, France [doi>10.1145/1028523.1028542]
• 30: Nealen, A., Müller, M., Keiser, R., Boxerman, E., and Carlson, M. 2005. Physically based deformable models in computer graphics. In Eurographics '05 STAR Reports, 71--94.
• 31: Sang Il Park , Jessica K. Hodgins, Capturing and animating skin deformation in human motion, ACM Transactions on Graphics (TOG), v.25 n.3, July 2006
• 32: Mark Pauly , Richard Keiser , Bart Adams , Philip Dutré , Markus Gross , Leonidas J. Guibas, Meshless animation of fracturing solids, ACM Transactions on Graphics (TOG), v.24 n.3, July 2005
• 33: Pekelny, Y. and Gotsman, C. 2008. Articulated object reconstruction and markerless motion capture from depth video. Comput. Graph. Forum (Proceedings of the Eurographics EG'08) 27, 2, 4.
• 34: PMD. 2009. http://www.pmdtec.com.
• 35: Peter Sand , Leonard McMillan , Jovan Popović, Continuous capture of skin deformation, ACM Transactions on Graphics (TOG), v.22 n.3, July 2003
• 36: Andrei Sharf , Dan A. Alcantara , Thomas Lewiner , Chen Greif , Alla Sheffer , Nina Amenta , Daniel Cohen-Or, Space-time surface reconstruction using incompressible flow, ACM Transactions on Graphics (TOG), v.27 n.5, December 2008
• 37: Alla Sheffer , Vladislav Kraevoy, Pyramid Coordinates for Morphing and Deformation, Proceedings of the 3D Data Processing, Visualization, and Transmission, 2nd International Symposium, p.68-75, September 06-09, 2004 [doi>10.1109/3DPVT.2004.99]
• 38: Jonathan R Shewchuk, An Introduction to the Conjugate Gradient Method Without the Agonizing Pain, Carnegie Mellon University, Pittsburgh, PA, 1994
• 39: Lin Shi , Yizhou Yu , Nathan Bell , Wei-Wen Feng, A fast multigrid algorithm for mesh deformation, ACM Transactions on Graphics (TOG), v.25 n.3, July 2006
• 40: Xiaohan Shi , Kun Zhou , Yiying Tong , Mathieu Desbrun , Hujun Bao , Baining Guo, Mesh puppetry: cascading optimization of mesh deformation with inverse kinematics, ACM SIGGRAPH 2007 papers, August 05-09, 2007, San Diego, California
• 41: Jonathan Starck , Adrian Hilton, Spherical Matching for Temporal Correspondence of Non-Rigid Surfaces, Proceedings of the Tenth IEEE International Conference on Computer Vision, p.1387-1394, October 17-20, 2005 [doi>10.1109/ICCV.2005.229]
• 42: Robert W. Sumner , Johannes Schmid , Mark Pauly, Embedded deformation for shape manipulation, ACM SIGGRAPH 2007 papers, August 05-09, 2007, San Diego, California
• 43: Robert W. Sumner , Matthias Zwicker , Craig Gotsman , Jovan Popović, Mesh-based inverse kinematics, ACM Transactions on Graphics (TOG), v.24 n.3, July 2005
• 44: Süssmuth, J., Winter, M., and Greiner, G. 2008. Reconstructing animated meshes from time-varying point clouds. Comput. Graph. Forum 27, 5, 1469--1476.
• 45: Demetri Terzopoulos , John Platt , Alan Barr , Kurt Fleischer, Elastically deformable models, Proceedings of the 14th annual conference on Computer graphics and interactive techniques, p.205-214, August 1987
• 46: Kiran Varanasi , Andrei Zaharescu , Edmond Boyer , Radu Horaud, Temporal Surface Tracking Using Mesh Evolution, Proceedings of the 10th European Conference on Computer Vision: Part II, October 12-18, 2008, Marseille, France [doi>10.1007/978-3-540-88688-4_3]
• 47: Michael Wand , Philipp Jenke , Qixing Huang , Martin Bokeloh , Leonidas Guibas , Andreas Schilling, Reconstruction of deforming geometry from time-varying point clouds, Proceedings of the fifth Eurographics symposium on Geometry processing, July 04-06, 2007, Barcelona, Spain
• 48: Weise, T., Leibe, B., and Gool, L. V. 2007. Fast 3D scanning with automatic motion compensation. In IEEE Conference on Computer Vision and Pattern Recognition (CVPR'07).
• 49: Stephan Würmlin , Edouard Lamboray , Oliver G. Staadt , Markus H. Gross, 3D Video Recorder, Proceedings of the 10th Pacific Conference on Computer Graphics and Applications, p.325, October 09-11, 2002
• 50: Weiwei Xu , Kun Zhou , Yizhou Yu , Qifeng Tan , Qunsheng Peng , Baining Guo, Gradient domain editing of deforming mesh sequences, ACM SIGGRAPH 2007 papers, August 05-09, 2007, San Diego, California
• 51: Zhang, L., Curless, B., and Seitz, S. M. 2003. Spacetime stereo: Shape recovery for dynamic scenes. In IEEE Computer Society Conference on Computer Vision and Pattern Recognition, 367--374.
• 52: Li Zhang , Noah Snavely , Brian Curless , Steven M. Seitz, Spacetime faces: high resolution capture for modeling and animation, ACM SIGGRAPH 2004 Papers, August 08-12, 2004, Los Angeles, California
• 53: Kun Zhou , Jin Huang , John Snyder , Xinguo Liu , Hujun Bao , Baining Guo , Heung-Yeung Shum, Large mesh deformation using the volumetric graph Laplacian, ACM Transactions on Graphics (TOG), v.24 n.3, July 2005
• 54: C. Lawrence Zitnick , Sing Bing Kang , Matthew Uyttendaele , Simon Winder , Richard Szeliski, High-quality video view interpolation using a layered representation, ACM SIGGRAPH 2004 Papers, August 08-12, 2004, Los Angeles, California
• 55: Matthias Zwicker , Hanspeter Pfister , Jeroen van Baar , Markus Gross, Surface splatting, Proceedings of the 28th annual conference on Computer graphics and interactive techniques, p.371-378, August 2001 [doi>10.1145/383259.383300]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.7 Three-Dimensional Graphics and Realism
          Subjects: Animation

Additional Classification:
  I. Computing Methodologies
  I.4 IMAGE PROCESSING AND COMPUTER VISION
      I.4.8 Scene Analysis
          Subjects: Surface fitting

General Terms:
Algorithms, Measurement

Keywords:
Deformation modeling, animation reconstruction, digital geometry processing, surface reconstruction