Scalable real-time volumetric surface reconstruction

Abstract

We address the fundamental challenge of scalability for real-time volumetric surface reconstruction methods. We design a memory efficient, hierarchical data structure for commodity graphics hardware, which supports live reconstruction of large-scale scenes with fine geometric details. Our sparse data structure fuses overlapping depth maps from a moving depth camera into a single volumetric representation, from which detailed surface models are extracted. Our hierarchy losslessly streams data bidirectionally between GPU and host, allowing for unbounded reconstructions. Our pipeline, comprised of depth map post-processing, camera pose estimation, volumetric fusion, surface extraction, and streaming, runs entirely in real-time. We experimentally demonstrate that a shallow hierarchy with relatively large branching factors yields the best memory/speed tradeoff, consuming an order of magnitude less memory than a regular grid. We compare an implementation of our data structure to existing methods and demonstrate higher-quality reconstructions on a variety of large-scale scenes, all captured in real-time.

References

1. Alliez, P., Cohen-Steiner, D., Tong, Y., and Desbrun, M. 2007. Voronoi-based variational reconstruction of unoriented point sets. In Proc. SGP 2007, vol. 257, Eurographics, 39--48.
2. Amanatides, J., and Woo, A. 1987. A fast voxel traversal algorithm for ray tracing. In Proc. Eurographics, vol. 87, 3--10.
3. Besl, P., and McKay, N. 1992. A method for registration of 3-D shapes. IEEE Trans. PAMI 14, 2, 239--256.
4. Bolitho, M., Kazhdan, M., Burns, R., and Hoppe, H. 2007. Multilevel streaming for out-of-core surface reconstruction. In Proc. SGP 2007, vol. 257, Eurographics, 69--78.
5. Chang, C., Chatterjee, S., and Kube, P. R. 1994. A quantization error analysis for convergent stereo. In Proc. ICIP 94, vol. 2, IEEE, 735--739.
6. Chen, Y., and Medioni, G. 1992. Object modelling by registration of multiple range images. Image and vision computing 10, 3, 145--155.
7. Chien, C., Sim, Y., and Aggarwal, J. 1988. Generation of volume/surface octree from range data. In Proc. CVPR 98, IEEE, 254--260.
8. Connolly, C. 1984. Cumulative generation of octree models from range data. In Proc. ICRA 84, vol. 1, IEEE, 25--32.
9. Crassin, C., Neyret, F., Lefebvre, S., and Eisemann, E. 2009. GigaVoxels: Ray-guided streaming for efficient and detailed voxel rendering. In Proc. I3D 2009, ACM, 15--22.
10. Cui, Y., Schuon, S., Chan, D., Thrun, S., and Theobalt, C. 2010. 3D shape scanning with a time-of-flight camera. In Proc. CVPR 2010, IEEE, 1173--1180.
11. Curless, B., and Levoy, M. 1996. A volumetric method for building complex models from range images. In Proceedings of SIGGRAPH 96, Annual Conference Series, 303--312.
12. Frisken, S., Perry, R., Rockwood, A., and Jones, T. 2000. Adaptively sampled distance fields: a general representation of shape for computer graphics. In Proceedings of SIGGRAPH 2000, Annual Conference Series, 249--254.
13. Fuhrmann, S., and Goesele, M. 2011. Fusion of depth maps with multiple scales. ACM Trans. Graph. 30, 6 (December), 148:1--148:8.
14. Greene, N., Kass, M., Miller, G., et al. 1993. Hierarchical z-buffer visibility. In Proceedings of SIGGRAPH 93, Annual Conference Series, 231--238.
15. Henry, P., Krainin, M., Herbst, E., Ren, X., and Fox, D. 2010. RGB-D mapping: Using depth cameras for dense 3D modeling of indoor environments. In Proc. ISER, vol. 20, 22--25.
16. Higuchi, K., Hebert, M., and Ikeuchi, K. 1995. Building 3-d models from unregistered range images. Graphical models and image processing 57, 4, 315--333.
17. Hilton, A., Stoddart, A., Illingworth, J., and Windeatt, T. 1996. Reliable surface reconstruction from multiple range images. Computer Vision (Proc. ECCV 96), 117--126.
18. Hilton, A., Stoddart, A. J., Illingworth, J., and Windeatt, T. 1998. Implicit surface-based geometric fusion. Computer Vision and Image Understanding 69, 3, 273--291.
19. Hoppe, H., DeRose, T., Duchamp, T., McDonald, J., and Stuetzle, W. 1992. Surface reconstruction from unorganized points. In Computer Graphics, vol. 26, 71--78.
20. Hornung, A., Wurm, K. M., Bennewitz, M., Stachniss, C., and Burgard, W. 2013. OctoMap: An efficient probabilistic 3D mapping framework based on octrees. Autonomous Robots 34, 3, 189--206.
21. Izadi, S., Kim, D., Hilliges, O., Molyneaux, D., Newcombe, R., Kohli, P., Shotton, J., Hodges, S., Freeman, D., Davison, A., et al. 2011. KinectFusion: real-time 3D reconstruction and interaction using a moving depth camera. In Proc. UIST 2011, ACM, 559--568.
22. Kazhdan, M., Bolitho, M., and Hoppe, H. 2006. Poisson surface reconstruction. In Proc. SGP 2006, vol. 256, Eurographics, 61--70.
23. Laine, S., and Karras, T. 2010. Efficient sparse voxel octrees. In Proc. I3D 2010, ACM, 55--63.
24. Levoy, M., Pulli, K., Curless, B., Rusinkiewicz, S., Koller, D., Pereira, L., Ginzton, M., Anderson, S., Davis, J., Ginsberg, J., et al. 2000. The digital michelangelo project: 3D scanning of large statues. In Proceedings of SIGGRAPH 2000, Annual Conference Series, 131--144.
25. Lorensen, W., and Cline, H. 1987. Marching cubes: A high resolution 3d surface construction algorithm. In Computer Graphics, vol. 21, 163--169.
26. Musialski, P., Wonka, P., Aliaga, D., Wimmer, M., van Gool, L., Purgathofer, W., Mitra, N., Pauly, M., Wand, M., Ceylan, D., et al. 2012. A survey of urban reconstruction. In Proc. Eurographics 2012 STARs, Eurographics, 1--28.
27. Newcombe, R., and Davison, A. J. 2010. Live dense reconstruction with a single moving camera. In Proc. CVPR 2010, IEEE, 1498--1505.
28. Newcombe, R., Lovegrove, S. J., and Davison, A. J. 2011. DTAM: Dense tracking and mapping in real-time. In Proc. ICCV 2011, IEEE, 2320--2327.
29. Newcombe, R. A., Izadi, S., Hilliges, O., Molyneaux, D., Kim, D., Davison, A. J., Kohli, P., Shotton, J., Hodges, S., and Fitzgibbon, A. 2011. KinectFusion: Real-time dense surface mapping and tracking. In Proc. ISMAR, IEEE, 127--136.
30. Nguyen, C., Izadi, S., and Lovell, D. 2012. Modeling Kinect sensor noise for improved 3D reconstruction and tracking. In Proc. 3DIMPVT 2012, IEEE, 524--530.
31. Osher, S., and Fedkiw, R. P. 2003. Level set methods and dynamic implicit surfaces. Applied mathematical science. Springer, New York, N.Y.
32. Parker, S., Shirley, P., Livnat, Y., Hansen, C., and Sloan, P.-P. 1998. Interactive ray tracing for isosurface rendering. In Proc. Visualization 98, IEEE, 233--238.
33. Pollefeys, M., Van Gool, L., Vergauwen, M., Verbiest, F., Cornelis, K., Tops, J., and Koch, R. 2004. Visual modeling with a hand-held camera. IJCV 2004 59, 3, 207--232.
34. Pollefeys, M., Nistér, D., Frahm, J., Akbarzadeh, A., Mordohai, P., Clipp, B., Engels, C., Gallup, D., Kim, S., Merrell, P., et al. 2008. Detailed real-time urban 3D reconstruction from video. IJCV 2008 78, 2, 143--167.
35. Potmesil, M. 1987. Generating octree models of 3d objects from their silhouettes in a sequence of images. Computer Vision, Graphics, and Image Processing 40, 1, 1--29.
36. Roth, H., and Vona, M. 2012. Moving volume KinectFusion. In Proc. BMVC 2012, BMVA Press, 112.1--112.11.
37. Rusinkiewicz, S., Hall-Holt, O., and Levoy, M. 2002. Real-time 3D model acquisition. ACM Trans. Graph. 21, 3 (July), 438--446.
38. Seitz, S., Curless, B., Diebel, J., Scharstein, D., and Szeliski, R. 2006. A comparison and evaluation of multi-view stereo reconstruction algorithms. In Proc. CVPR 2006, vol. 1, IEEE, 519--528.
39. Stückler, J., and Behnke, S. 2012. Robust real-time registration of RGB-D images using multi-resolution surfel representations. In Proc. ROBOTIK 2012, VDE, 1--4.
40. Szeliski, R. 1993. Rapid octree construction from image sequences. CVGIP Image Understanding 58, 23--23.
41. Thrun, S., Burgard, W., Fox, D., et al. 2005. Probabilistic Robotics. MIT Press, Cambridge, MA.
42. Turk, G., and Levoy, M. 1994. Zippered polygon meshes from range images. In Proceedings of SIGGRAPH 94, Annual Conference Series, 311--318.
43. Weise, T., Wismer, T., Leibe, B., and Van Gool, L. 2009. In-hand scanning with online loop closure. In Proc. ICCV 2009 Workshops, IEEE, 1630--1637.
44. Wheeler, M., Sato, Y., and Ikeuchi, K. 1998. Consensus surfaces for modeling 3D objects from multiple range images. In Proc. ICCV 98, IEEE, 917--924.
45. Whelan, T., Kaess, M., Fallon, M., Johannsson, H., Leonard, J., and McDonald, J. 2012. Kintinuous: Spatially extended KinectFusion. In Proc. RSS Workshop on RGB-D: Advanced Reasoning with Depth Cameras.
46. Zach, C., Pock, T., and Bischof, H. 2007. A globally optimal algorithm for robust TV-L1 range image integration. In Proc. ICCV 2007, IEEE, 1--8.
47. Zeng, M., Zhao, F., Zheng, J., and Liu, X. 2013. Octree-based fusion for realtime 3d reconstruction. Graphical Models 75, 3 (May), 126--136.
48. Zhou, K., Gong, M., Huang, X., and Guo, B. 2011. Data-parallel octrees for surface reconstruction. IEEE Trans. Visualization and Computer Graphics 17, 5, 669--681.

Index Terms

• Applied computing

  • Document management and text processing

    • Document capture

      • Document scanning

      • Graphics recognition and interpretation

• Computing methodologies

  • Computer graphics

    • Image manipulation