Automatic Reconstruction of Tree Skeletal Structures from Point Clouds

ACM Transactions on Graphics (Proceedings SIGGRAPH ASIA 2010)

Yotam Livny 1     Feilong Yan 1      Matt Olson 2      Baoquan Chen 1      Hao Zhang 2      Jihad El-Sana 3 

1Shenzhen Institutes of Advanced Technology, Chinese Academy of Sciences, China
2School of Computing Science, Simon Fraser University, Canada
3Department of Mathematics and Computer Science, Ben-Gurion University of the Negev


Figure 1:A scene of five trees automatically reconstructed by our algorithm. The images show a photo of the scene, point cloud, reconstructed
trees, and textured models with leaves. The insets show the ability of our method to handle overlapping crowns and missing data..



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 heart 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 that we can reconstruct multiple overlapping trees simultaneously without segmentation. We demonstrate the effectiveness and robustness of our approach on many real examples.



Figure 2: A tree with thin and dense branches (left). This tree has been scanned from the right side, therefore point density is higher on the right than on the left (middle). Our reconstruction is data dependent – the right side of the output is more accurate than the left.


Figure 3: Reconstruction results for trees of different types. The tall tree has a large gap at its base due to occlusion from a passing car. Thebush data has low quality because the plant is only 0:5 meters tall.


Figure 4: A large urban scene with more than 10 million points, about 200,000 of which capture 20 trees. The trees are of various types, some with low-quality captures. We highlight tree samples, colored by height (top); however, note that trees are not pre-segmented from the rest of the data. Our method automatically reconstructs the 20 trees (bottom) in about 30 minutes.












We thank the anonymous reviewers for their valuable suggestions. This work was supported in part by National Natural Science Foundation of China (NSFC) for Distinguished Young Scholar, National Natural Science Foundation of China (60902104), National High-tech R&D Program of China (2009AA01Z302), CAS Visiting Professorship for Senior International Scientists, CAS Fellowship for Young International Scientists, Shenzhen Science and Technology Foundation (GJ200807210013A),Lynn and William Frankel Center for Computer Sciences and the Tuman Fund, and the Natural Sciences and Engineering Research Council of Canada (No. 611370). Finally, we acknowledge the scanning team of Shenzhen Institute of Advanced Technology (SIAT) for their effort during acquisition and processing of trees data.



@ARTICLE{VccTree 2010,
  title = {Automatic Reconstruction of Tree Skeletal Structures from Point Clouds},
  author = {Yotam Livny and Feilong Yan and Matt Olson and Baoquan Chen and Hao Zhang and Jihad El-sana},
  journal = {ACM Transactions on Graphics (Proceedings of SIGGRAPH Asia 2010)},
  volume = {29},
  issue = {6},
  pages = {151:1-151:8},
  year = 2010