Paper Reading: (2015) SimpleTree —An Efficient Open Source Tool to Build Tree Models from TLS Clouds
Published:
Original paper: Hackenberg, Jan, et al. “SimpleTree—an efficient open source tool to build tree models from TLS clouds.” Forests 6.11 (2015): 4245-4294. https://doi.org/10.3390/f6114245
This is a record of the reading process, aimed at personal learning, reading and writing practicing.
- 1 Introduction
- 1.1 Related Work
- 1.1.1 Methods in Computational Forestry producing QSMs of the Branching Structure
- 1.1.2 Methods in Computer Vision producing QSMs of the Branching Structure
- 1.1.3 Further Open Source Tree Modelling Software and Point Cloud Processing Libraries
- 1.2 Relevance of the Presented Work in the State of the Art
- 1.3 Structure of the Manuscript
- 1.1 Related Work
- 2 Software—SimpleTree
- 3 Software—Comparison Method Raumonen et al. (2013)
- 4 Data Sets
- 5 Results
- 6 Discussion
- 7 Outlook
- 8 Conclusion
Abstract
- An open source tool named SimpleTree, capable of modelling highly accurate cylindrical tree models from terrestrial laser scan point clouds, is presented and evaluated.
- All important functionalities, accessible in the software via buttons and dialogues, are described including the explanation of all necessary input parameters.
1 Introduction
The proposed approach results in geometrical models describing the complete above-ground woody tree components in an hierarchical order. Such models can be referred to as Quantitative Structure Models (QSMs). [8–11]
The SimpleTree method described here produces topologically ordered cylinder parameters (size, orientation) for all branches resolved by the LiDAR data, which can be of the order of thousands of branches per tree.
1.1 Related Work
\[AGB = a \times DBH^b \quad (1)\]Yao et al. [25] predict AGB on plot level utilizing the Diameter at Breast Height (DBH) as an input variable for the following allometric equation:
1.1.1 Methods in Computational Forestry producing QSMs of the Branching Structure
- In Côté et al. [42] TLS points are subdivided into wood and foliage components.
- Then Dijkstra’s algorithm is applied on the wood points to calculate a skeleton representing the stem and the major branches.
- To reconstruct the thinner branching structure, high occurrences of foliage are detected in voxel space. Those voxels are called attractors and are connected to the main skeleton in an iterative routine.
- Radii for cylinder estimations from the final skeleton are estimated from the pipe model theory [43].
- Finally, foliage is added to the models.
1.1.2 Methods in Computer Vision producing QSMs of the Branching Structure
Here the idea of using sphere-surface cuts with point clouds of trees is utilized. This idea is based on Jayaratna [66] in the field of computer vision.
1.1.3 Further Open Source Tree Modelling Software and Point Cloud Processing Libraries
- Computree [70] is an open source platform utilizing TLS clouds.
- Some of the algorithms implemented in Computree are described in detail in Othmani et al. and Ravaglia et al. [71,72].
- The Computational Geometry Algorithms Library [73] offers geometric algorithms for the computation of Voronoi diagrams, α-shapes, convex hulls and other structures.
- Both the Point Cloud Library (PCL) [74] and the Sorted Pulse Data software Library (SPDLib) [75] give access to methods specialized in the processing of LiDAR point clouds.
1.2 Relevance of the Presented Work in the State of the Art
QSMs though have the beneficial potential to model also AGB distributions within a single tree individual, see Section 6.
1.3 Structure of the Manuscript
- Section 2 describes the functionalities of the presented software. SimpleTree results are compared to the results of the software tool relying on Raumonen et al. [49].
- In Section 3 this comparison method is described.
- The utilized data sets are presented in Section 4.
- In Section 5 results of AGB estimations of both software tools are given.
- The results are discussed and interpreted in Section 6, leading to Section 8 where the relevance of the tool is debated.
- An outlook of possible future work is given in Section 7.
2 Software—SimpleTree
- The presented version of software SimpleTree is written in C++.
- The PCL library [74] provides efficient functions for the implementation of the method. PCL’s mathematical operations are based on the linear algebra library Eigen [79]. k-nearest neighbour searches are performed by the Fast Library for Approximate Nearest Neighbours (FLANN) [80]. PCL also ships with its own visualization library based on VTK (the Visualization Toolkit) [81].
2.1 Filter and Clustering Routines
Methodname (a, b) is here-on a wild-card for a method with name Methodname, utilizing input parameters a and b.
- Radius Outlier Removal (r, k) [83], Statistical Outlier Removal (sdMult, k) [83], Voxel Grid Filtering (cellsize) [83]
- Curvature Filtering (min1, max1, min2, max2, min3, max3):
- A PCA is performed for each point’s neighbourhood. \(\lambda_1\), \(\lambda_2\), and \(\lambda_3\) denote the normalized Eigenvalues for each point. For all \(\lambda_1\), minimum \(\text{min}\) and maximum \(\text{max}\) value are computed. \(\text{min}_1\) and \(\text{max}_1\) are percentage numbers. A point is considered an outlier if its \(\lambda_1\) is smaller than \(\text{min} + (\text{max} - \text{min})/100 \times \text{min}_1\) or larger than \(\text{min} + (\text{max} - \text{min})/100 \times \text{max}_1\). \(\lambda_2\) and \(\lambda_3\) are processed in the same manner. The thresholds are adjusted with a slider, and before the removal-confirmation, all noise points are marked via transparency and colourisation in real time according to the slider values (Figure 3).
- 对于每个点的邻域执行主成分分析(PCA)。\(\lambda_1\)、\(\lambda_2\) 和 \(\lambda_3\) 表示每个点的归一化特征值。对于所有 \(\lambda_1\),计算最小值 \(\text{min}\) 和最大值 \(\text{max}\)。\(\text{min}_1\) 和 \(\text{max}_1\) 是百分比数。如果一个点的 \(\lambda_1\) 小于 \(\text{min} + (\text{max} - \text{min})/100 \times \text{min}_1\) 或大于 \(\text{min} + (\text{max} - \text{min})/100 \times \text{max}_1\),则认为它是一个异常值。\(\lambda_2\) 和 \(\lambda_3\) 以相同的方式处理。阈值随滑块调整,在移除确认之前,根据滑块值实时通过透明度和着色标记所有噪声点(图3)。
- Algorithm: Principal components analysis (PCA)
- Intensity Filtering (min, max)
- Crop Sphere / Crop Box (radius)
- Euclidean Clustering (clusterTolerance, minPts, numCluster) [83]
- A simple but fast spatial clustering operation is applied. The output cloud will contain the numCluster largest clusters containing at least minPts points. If only a smaller number of clusters exists, numCluster is set automatically to this number. Points are separated into two clusters if the distance between the closest point pair exceeds clusterTolerance. This operation is faster than the Density-Based Spatial Clustering of Applications with Noise (DBSCAN) [84], which was used in Hackenberg et al. [10,12].
- 应用了一个简单但快速的空间聚类操作。输出云将包含至少包含minPts个点的numCluster个最大的聚类。如果存在较小数量的聚类,则numCluster会自动设置为该数量。如果最近点对之间的距离超过clusterTolerance,则将点分成两个聚类。此操作比密度基空间聚类与噪声应用(DBSCAN)[84]更快,后者在Hackenberg等人的研究中使用[10,12]。
- Algorithm: Euclidean Clustering
2.2 Tree Modeling
- Stem Point Detection [10] ()
- Spherefollowing Method [10,12] (sphereMultiplier, epsClusterStem, epsClusterBranch, epsSphere, minPtsRansacStem, minPtsRansacBranch, minPtsClusterStem, minPtsClusterBranch, minRadiusSphereStem, minRadiusSphereBranch)
- Parameter Optimization (iterations, criterion, seeds)
- Allometric improvement (a, b, fac, minRad)
- Crown Computation (α)
2.3 Point Cloud Processing
- Iterative Closest Point (ICP) (β) [74,89]
- Merge ()
2.4 Output Data
- Cloud To Model Distance
- Single Value Tree Parameters
- This file contains the entries for the total tree volume and the stem volume. Solid volume is the volume of all compartments with a diameter larger 7 cm. The tree’s height and its length are included, as well as the DBH and the root diameter at lowest z-coordinate. The stem volume from the root up to the first branch and the stem volume up to the crown base are printed with additionally the crown base height. The crown volume and the crown surface from the convex hull crown model and lastly the crown projection area are additional output parameters. In Hackenberg et al. [12] more detailed definitions on various output parameters are given.
- Complete Cylinder Model
3 Software—Comparison Method Raumonen et al. (2013)
- Comparison.
4 Data Sets
- to estimate biomass.
5 Results
- the results of estimation and comparision.
6 Discussion
6.1 The Benefit of Open Source
- The Computree [70] platform is written in C++ and supports PCL usage.
- Due to the strict modularization, efficient integration of other methods is possible.
- Such a symbioses reduces the amount a single scientist has to perform by itself.
6.2 The Benefit of QSMs
- Stem curves can be extracted efficiently from the results models, as can be seen in Figure 18. This stem curve is not validated on ground truth data, but shows a strong natural pattern.
- Additionally the branches of the same target tree have been binned according to the height of their base. The utilized bin width here is half a meter, within a bin the volume of all contained branches was summed up. In Figure 19 only three major whorls are visible, the height of the first whirl can be defined as the crown base. (don’t quiet understand yet)
- A time series analysis utilizing SimpleTree is in preparation by Sheppard et al. [97].
- Sheppard, Jonathan, et al. “Terrestrial laser scanning as a tool for assessing tree growth.” iForest: Biogeosciences and Forestry 10.1 (2017): 172-179. https://doi.org/10.3832/ifor2138-009
7 Outlook
- Bad input parameters though lead to undesirable models. We conclude that the most beneficial way to estimate high accurate models is to create an artificial intelligence (AI) to support the threshold setting for sensitive methods like ours.
- The proposed optimization method is a brute force one. Literature reports optimization algorithms such as the downhill simplex method published in Nelder et al. [98] or other methods described in Press et al. [99]. Libraries like Scipy [100] provide implementations of those methods.
8 Conclusion
- The public availability of the source code allows the recompilation of the program on different Operating Systems with a C++ compiler. The recommended system for using SimpleTree is Ubuntu Linux, but it has also been successfully compiled on Windows 7.