“Automatic reconstruction of tree skeletal structures from point clouds”
Conference:
Type(s):
Title:
- Automatic reconstruction of tree skeletal structures from point clouds
Session/Category Title: Reconstructing and editing geometry
Presenter(s)/Author(s):
Moderator(s):
Abstract:
Trees, bushes, and other plants are ubiquitous in urban environments, and realistic models of trees can add a great deal of realism to a digital urban scene. There has been much research on modeling tree structures, but limited work on reconstructing the geometry of real-world trees — even then, most works have focused on reconstruction from photographs aided by significant user interaction. In this paper, we perform active laser scanning of real-world vegetation and present an automatic approach that robustly reconstructs skeletal structures of trees, from which full geometry can be generated. The core of our method is a series of global optimizations that fit skeletal structures to the often sparse, incomplete, and noisy point data. A significant benefit of our approach is its ability to reconstruct multiple overlapping trees simultaneously without segmentation. We demonstrate the effectiveness and robustness of our approach on many raw scans of different tree varieties.
References:
1. Anastacio, F., Sousa, M. C., Samavati, F., and Jorge, J. A. 2006. Modeling plant structures using concept sketches. In Proceedings of NPAR 2006, 105–113. Google ScholarDigital Library
2. Bucksch, A., and Lindenbergh, R. 2008. Campino — a skeletonization method for point cloud processing. ISPRS journal of photogrammetry and remote sensing 63, 1, 115–127.Google Scholar
3. Bucksch, A., Lindenbergh, R., and Menenti, M. 2009. Skeltre – fast skeletonisation for imperfect point cloud data of botanic trees. In Proceedings of Eurographics Workshop on 3D Object Retrieval, 13–27. Google ScholarDigital Library
4. Chen, X., Neubert, B., Xu, Y.-Q., Deussen, O., and Kang, S. B. 2008. Sketch-based tree modeling using markov random field. ACM Trans. on Graphics 27, 5, 109–117. Google ScholarDigital Library
5. Cornea, N. D., Silver, D., and Min, P. 2007. Curve-skeleton properties, applications, and algorithms. IEEE Trans. on Visualization and Computer Graphics 13, 3, 530–548. Google ScholarDigital Library
6. Côté, J.-F., Widlowski, J.-L., Fournier, R. A., and Verstraete, M. M. 2009. The structural and radiative consistency of three-dimensional tree reconstructions from terrestrial lidar. Remote Sensing of Environment 113, 5, 1067–1081.Google ScholarCross Ref
7. Honda, H. 1971. Description of the form of trees by the parameters of the tree-like body: Effects of the branching angle and the branch length on the shape of the tree-like body. Theoretical Biology 31, 331–338.Google ScholarCross Ref
8. Lazarus, F., and Verroust, A. 1999. Extracting skeletal curves from 3D scattered data. In Proceedings of IEEE Conf. on Shape Modeling and Applications, 194–201. Google ScholarDigital Library
9. Li, G., Liu, L., Zheng, H., and Mitra, N. J. 2010. Analysis, reconstruction and manipulation using arterial snakes. In Proceedings of SIGGRAPH ASIA 2010, to appear. Google ScholarDigital Library
10. Minwoo, P., Yanxi, L., and Robert, C. 2008. Efficient mean shift belief propagation for vision tracking. In Proceedings of IEEE Conf. on CVPR, 1–8.Google Scholar
11. Neubert, B., Franken, T., and Deussen, O. 2007. Approximate image-based tree-modeling using particle flows. ACM Trans. on Graphics 26, 3, Article 71, 8 pages. Google ScholarDigital Library
12. Okabe, M., Owada, S., and Igarashi, T. 2006. Interactive design of botanical trees using freehand sketches and example-based editing. Comput. Graph. Forum 24, 3, 487–496.Google ScholarCross Ref
13. Prusinkiewicz, P., and Lindenmayer, A. 1990. The algorithmic beauty of plants. Springer-Verlag New York, Inc. Google ScholarDigital Library
14. Prusinkiewicz, P., Mündermann, L., Karwowski, R., and Lane, B. 2001. The use of positional information in the modeling of plants. In SIGGRAPH 2001: Proceedings of the 28th annual conference on Computer graphics and interactive techniques, 289–300. Google ScholarDigital Library
15. Quan, L., Tan, P., Zeng, G., Yuan, L., Wang, J., and Kang, S. B. 2006. Image-based plant modeling. ACM Trans. on Graphics 25, 3, 599–604. Google ScholarDigital Library
16. Reche-Martinez, A., Martin, I., and Drettakis, G. 2004. Volumetric reconstruction and interactive rendering of trees from photographs. ACM Trans. on Graphics 23, 3, 720–727. Google ScholarDigital Library
17. Rozenberg, G., and Salomaa, A. 1980. Mathematical Theory of L-Systems. Academic Press, Inc. Google ScholarDigital Library
18. Runions, A., Lane, B., and Prusinkiewicz, P. 2007. Modeling trees with a space colonization algorithm. In Proceedings of Eurographics Workshop on Natural Phenomena 2007, 63–70. Google ScholarDigital Library
19. Shlyakhter, I., Rozenoer, M., Dorsey, J., and Teller, S. 2001. Reconstructing 3d tree models from instrumented photographs. IEEE Computer Graphics Applicalion 21, 3, 53–61. Google ScholarDigital Library
20. Tagliasacchi, A., Zhang, H., and Cohen-Or, D. 2009. Curve skeleton extraction from incomplete point cloud. ACM Trans. on Graphics 28, 3, Article 71, 9 pages. Google ScholarDigital Library
21. Tan, P., Zeng, G., Wang, J., Kang, S. B., and Quan, L. 2007. Image-based tree modeling. In Proceedings of SIGGRAPH 2007, Article 87, 8 pages. Google ScholarDigital Library
22. Tan, P., Fang, T., Xiao, J., Zhao, P., and Quan, L. 2008. Single image tree modeling. ACM Trans. on Graphics 27, 5, 1–7. Google ScholarDigital Library
23. Wither, J., Boudon, F., Cani, M.-P., and Godin, C. 2009. Structure from silhouettes: a new paradigm for fast sketch-based design of trees. Comput. Graph. Forum 28, 2, 541–550.Google ScholarCross Ref
24. Xu, H., Gossett, N., and Chen, B. 2007. Knowledge and heuristic-based modeling of laser-scanned trees. ACM Trans. on Graphics 26, 4, Article 19, 13 pages. Google ScholarDigital Library
