Introduction

With the recent development of computer graphic techniques, 3-dimensional (3D) applications based on the point cloud data have become increasingly popular within the computer-generated virtual and actual worlds (Bucksch et al. 2010; Kim et al. 2013; Lindberg 2016). Although many large and simple structured objects can be conveniently scanned using the powerful and increasingly available scanners (Urbach 2014; Maltamo et al. 2016), there are few efficient and simple studies on the complex topology of natural trees. Trees are a common but vital part of the natural environment, and the research on trees is beneficial to other fields and applications, such as forestry, environmentology and ecosystems (Aiteanu and Klein 2014; Wang et al. 2016; Kandare et al. 2017; Lamb et al. 2018). Unlike other vegetation models, tree models, which often consists of irregular leaves, a trunk and many densely intricate branches, are very difficult to handle in actual practice (Huang et al. 2013; Mikita et al. 2016). In addition to the complexity of tree models, different types of trees are of different characteristics. Therefore, computing the skeleton models based on the point cloud trees is a great challenge for forestry and agriculture research topic (Zhang et al. 2016a, 2016b; Su et al. 2011). In mathematics, a tree skeleton is a subset of the one-dimensional skeleton’s medial axis without endpoints. To comply with the concept, the research subject of this work is the point cloud data of the natural trees. Compared with the grid model, the skeleton reconstruction of a point cloud tree is more difficult due to the limited information, the diversity and uncertainty of a trees’ structure, and the fact that the point cloud tree has a more complex topology inside (Livny et al. 2010; Wang et al. 2014). Although many skeleton extraction methods have been studied over recent decades (Shlyakhter et al. 2001; Lidayov et al. 2016; Djuricic et al. 2016; Xie et al. 2016), there are few papers on this specific problem. Amenta et al. and others proposed a geometric method based on the Voronoi map (Amenta et al. 2001; Amenta et al. 1998). This method can process the point cloud data directly. However, the proposed method is sensitive to noisy data and may easily deform the real skeleton. Verrost.et.al and other researchers also proposed a level-set-based method (Dong et al. 2015); however, this method is impractical, sensitive to noise, susceptible to the missing details. Furthermore, when there is a vacancy in the model, this method can achieve unsatisfactory performance. In addition, there are other tree skeletonized methods, but the existing methods are either too too complicated to practice or to produce unsatisfactory reconstructed results.

In this paper, we propose a simple but efficient skeleton reconstruction method for point cloud trees, named as force field driven tree skeleton extracting method. A brief description of the proposed method is provided as follows. To make the point cloud tree slightly cleaner, the hierarchical subdivision to the original point cloud trees spaces is firstly proposed. Then the split-level of the trees’ applied space is considered in each layers, and a simplified representation of the feature points for the tree model is then established under the neighbor relationships. The point cloud-based tree’s feature points is then confirmed using the Gauss clustering (Zhou et al. 2014, 2015). After that, the feature points in the peripheral are connected by the geodesic distance. To get the initial skeleton, the surface geodesic lines are compressed into the tree model by applying a visible repulsive force field. Ultimately, the final skeleton is acquired by polishing the initial skeleton according to a threshold setting.

There are two main contributions of this work:

  • We propose a novel and efficient combinational approach, which can be used to accurately extract the tree skeleton from the point cloud data ;

  • We first use the force field model to process the point cloud data, and all the data can be put together without a mesh map. Experimental results confirm the superiority of the proposed approach.

Compared with the existing state-of-the-art methods, the proposed method can better process the point cloud tree model, which is of complex topology. A point cloud tree skeleton reconstructed by the proposed technique can better satisfy the centrality and continuity definitions due to the lack of a rigid mathematical definition of a linear skeleton.

Material and methods

Laser scanning

Laser scanning was undertaken in March 2014 using a Leica Scanstation C10 scanner (Leica Geosystem AG, Heerbrugg, Switzerland) with a dual-axis compensator and high-resolution camera. The Field-of-View (Horizontal × Vertical) is setting as 360 × 370. The Scan-Rate is setting as up to 50,000 points/second, and the Type is setting as pulsed.

Simplified representation

Together with the advancement of the precision for the laser scanner in recent years, the scale of the point cloud data has also been increasing. The order for magnitude is typically on the order for hundreds to thousands, which makes it difficult to process the original data. Because trees have complex topologies, the new technique can simplify point cloud trees while retaining the details and reducing the computational burden. As shown in Fig. 1, in this paper, we make a survey to two kinds of trees, named as Michelia and Cherry.

Fig. 1
figure 1

Primitive point cloud models. aMichelia, and b the branches and trunk of Michelia. cCherry tree, and d branches and trunk of Cherry. We used a ground laser radar to obtain the primitive point cloud models. These models were then separated into branches and leaves using the Gaussian mixture method, and the research in this work is based on the branches

Full size image

Hierarchical subdivision

Hierarchical subdivision plays an important role in point cloud data simplification, since it can subdivide all hierarchies of the point clouds to a hierarchical structure (Eckart et al. 2016). To achieve this goal, we use the hierarchical bounding box to process all the hierarchies of a subdivision. Due to the uncertainty of the space position, shape and thickness of the living branches, it is very difficult to accurately separate the living stands. Even in the same space plane, different thickness of the stems also requires different layered parameters. In addition, in the same branch, from the bottom to the different position of the layered parameters also need to remain inconsistent. Therefore, considering the real situation of the point cloud trees, we choose the OBBTree as a hierarchical bounding box in this work (Gottschalk et al. 1996). Although the OBBTree has a greater space complexity, it is more applicable than the other bounding boxs on the reconstruction of point cloud trees. Furthermore, it can better manage the topology relationship between genus and irregularities. Based on the OBBTree, to make the point cloud tree slightly cleaner, an points-half algorithm and section-termination method are selected, which can be described as the following steps:

  1. 1.

    Points-half algorithm;

  2. 2.

    The points-half algorithm halves the half-plane for the vertical face of the plane intersected between the long axis of the directed bounding box and the centroid passes through the leaf node. The computational time of this algorithm is only relevant to the quantity of the point clouds. Therefore, one main advantage of the point-half algorithm is that the short computation time. We improve this algorithm by clustering the Euclidean distance among point clouds using the following four steps:

    • Set an arbitrary point and set KD − Tree of P;

    • Cluster P based on the KD − Tree;

    • Divide P into Pl and Pr based on the Euclidean distance;

    • Divide P into Pl and Pr based on the above mentioned point-half algorithm.

  3. 3.

    Section-termination. There are two ways to determine the section-termination: the first one is based on the quantity of points, and the other one is based on the node’s maximum error (Lidayov et al. 2016).

Using the node’s sequence for magnitude, it is easy to miss the small branches because of differing degrees of the thickness and length. Thus, to solve this problem, we use the node’s maximum error to carry out a section-termination scheme. To control the number of the nodes and lower the space complexity, this work sets an error to judge the weight, which can be expressed as follows:

$$ \begin{array}{l} R=\mathit{det}~M-\alpha(trace~M)^{2} \end{array} $$
(1)
$$ \begin{array}{l} \mathit{det}~M=\alpha OBB A_{1}+(1-\alpha)V_{1} \end{array} $$
(2)
$$ \begin{array}{l} trace~M=\alpha OBB V_{1}+(1-\alpha)A_{1} \end{array} $$
(3)

where V1 and A1 represent the OBB’s tangent plane projected area and volume, respectively. And α is the weight coefficient, which is established as 1.2 in this study. The quantity of tree model fragments confirms the precision of the final model. A larger number of fragments n makes the tree’s skeleton more precise. However, the use of the complex algorithm requires a greater time investment. Based on the premise of unchangeable topology and an unreformable skeleton, the quantity n should be as small as possible. This study selects n = 200 with respect to the actual hierarchical structure of the point cloud tree models. As shown in Fig. 2, we show the results of the hierarchical subdivision algorithm, in which Fig. 2a is the point cloud tree model that we use the hierarchical bounding box of OBBTree to construct and Fig. 2b demonstrates the point cloud model after hierarchical subdivision algorithm.

Fig. 2
figure 2

Results of the hierarchical subdivision algorithm. a we use the hierarchical bounding box of OBBTree to construct the point cloud tree model and b the point cloud model after hierarchical subdivision algorithm

Full size image

Feature extraction

On the definitions, feature points of a point cloud model are the points that can directly affect the topology of the real tree, such as the saddle points and peripheral points. From the perspective of pure mathematics, these points are mainly the extreme value points of the objective function. After segmenting the tree model, this study proposes an modified algorithm for the features based on the Gauss clustering, which is described in references (Chu et al. 2016; Liao et al. 2016). To further simplify the model, the first step is going to eliminate the featureless points of the neighborhood using the Gauss clustering map. Then, a multi-angle analysis of the remaining points is performed to find possible feature points.

Given a set of point clouds of a tree, P = p1,p2,...,pn ∈ R3×n, assume that Np is a neighbor k of p, Ip is the index assemble of Np, and T is k(k − 1) assembles of vertex p:

$$ \begin{array}{l} T=\{{\Delta}_{ij}\triangle(p, p_{i}, p_{j})\mid i\neq j~\text{and}~i,j\in I_{p}\} \end{array} $$
(4)

The normal-vector of triangle Δij with vertex p:

$$ \begin{array}{l} n_{ij}=\bar{pp_{i}}\times\bar{pp_{j}} \end{array} $$
(5)

The Gauss map of Np maps T onto sphere S2 with a center p:

$$ \begin{array}{l} G_{P}:T\mapsto S^{2},~~{\Delta}_{ij}\mapsto X_{ij}:=P+n_{ij}/\parallel n_{ij}\parallel \end{array} $$
(6)

Because the assembly of data points constituted by Gauss clustering is a spherical surface, the data are mutually symmetric. This study uses the distance metric of the normal vector’s included angle

$$ \begin{array}{l} d(x_{ij},x_{jk})=\min\{d_{g}(x_{ij},x_{jl}), d_{g}(x_{ij},x_{lk})\} \end{array} $$
(7)
$$ \begin{array}{l} d_{g}(x_{ij},x_{lk})=\arccos(<n_{ij},n_{lk}>) \end{array} $$
(8)

where i, j, k, l ∈ Ip, and dg are the Euclidean distance between point xij and xkl point in the Gaussian sphere. We use a hierarchical cluster, as each point is a cluster object. Then, closer points are combined. The distance between inhomogeneities is the average distance between different classes.

$$ \begin{array}{l} D_{c}(S_{1},S_{2})=\frac{1}{\mid S_{1}\mid \cdot \mid S_{1} \mid} \sum\limits_{x\in S_{1}} \sum\limits_{y\in S_{2}} d(x,y) \end{array} $$
(9)

Here, we set a threshold to estimate and calculate the distance of the distance in homogeneity. Clustering is stopped when the numerical value exceeds the threshold. The threshold is set as \(\sigma \in [0,\frac {1}{2}]\). The result will remove a few points, and the remaining points are analyzed as follows:

  1. 1.

    The point is featureless if it clusters in the same category;

  2. 2.

    The point is a feature point if it has a surplus of 2,3 or 4.

If the number is greater than 4, then this point is featureless because the number of surface features of the camber is typically less than 4. In the experiment, all feature points can be detected within the threshold. This approach may lead to the false detection of feature points if σ is overly large and makes clusters of classifications. It is also easy about falsely detecting when σ is not sufficiently large, and the number of the species increases excessively. As shown in Figs. 3 and 4, we give a brief description to the results of the described feature extraction method, and make a resultant comparison between the described feature extraction method and the the conventional Gauss clustering method. As we can see from Fig. 4, not only can our modified method can not only simplify the point cloud model better but it can also maintain the original topology.

Fig. 3
figure 3

Feature points of the point cloud tree. aMichelia and bCherry

Full size image
Fig. 4
figure 4

Different simplified methods on Cherry. a and b are based on our modified method, in which the threshold in(a) is 0.15 and the threshold in b is 0.3, c and d are based on the conventional Gauss clustering

Full size image

Confirming the initial skeleton

We use geodesic curves to connect the feature points to obtain the initial tree’s skeleton. The geodesic’s definition of differential geometry is that for each arbitrary curve Γ on the curved surface, the geodesic curvature of the point of the Γ equals 0. We refer to Γ as the geodesic of curved surface H. This is similar to the definition of the space plane; the geodesic is the shortest line of two points of a curved surface. This study uses PCG arithmetic based on reference to calculate the geodesic of point cloud-based trees. Assume a point cloud camber S(u,v) formed by the feature points of each hierarchy. Find any point p(u0,v0) on the camber. Set p(u0,v0) as the origin of a right-handed coordinated system, with the other coordinate axes representing the normal vector N of S(u,v) at p(u0,v0). The main directions are T1 and T2, and the origin is P(U0,V0). ki is the curvature of Ti. Thus, the quadratic approximation of (o,o,d) to the origin’s squared-distance d2 is

$$ \begin{array}{l} F_{d}^{+}(x_{1},x_{2},x_{3})=\frac{d}{d+\mid \rho_{1} \mid}{x_{1}^{2}}+\frac{d}{d+\mid \rho_{2} \mid}{x_{2}^{2}}+{x_{3}^{2}} \end{array} $$
(10)

where

$$ \begin{array}{l} \rho_{1}=\frac{1}{k_{1}},~~ \rho_{2}=\frac{1}{k_{2}} \end{array} $$
(11)

where rho1 is the reciprocal for curvature k1 and rho2 is the reciprocal for curvature k2. Thus, the objective function is

$$ \begin{array}{l} F_{s}=\int{\mid c(t)\mid^{2}~dt} \end{array} $$
(12)

From the above, the calculation of the geodesic consists of the following five steps:

  1. 1.

    Take any two points of the obtained feature points. Determine the activity curve c(t) of the B-spline by the shortest path algorithm of the bidirectional dijkstra based on the map (Balzer and Vincze 2016; Su et al. 2016);

  2. 2.

    Mark all points on c(t) as s(k). Find all of s(k)’s petals on the point cloud;

  3. 3.

    The structure of the objective function is

    $$ \begin{array}{l} F = \sum\limits_{k = 1}^{N} {F_{d}^{k}}(L_{k}(d_{1} + c_{1},(d_{2} + c_{2}),...,(d_{N} + c_{N})))+\!\lambda F_{s}; \end{array} $$
    (13)
  4. 4.

    Apply least squares to solve the new activity curve of F;

  5. 5.

    Repeat steps 2 through 4 until the expected threshold is satisfied.

Successively connect the points near the geodesic distance to obtain the surface skeleton s = si of the model, where i = 1,2,...,k. Figure 5 gives the master drawing of the initial skeleton for Michelia and Cherry.

Fig. 5
figure 5

Linking the geodesic curves for the surface for initial skeleton. We link all points located on the surface to obtain the initial surface skeleton. aMichelia and bCherry

Full size image

Reconstruction

The previous results in the last chapter do not satisfy the requirement of centrality, because the initial tree skeleton in surfaces is distributed among the surfaces of the tree branches and trunk. In this chapter, we use a visible reaction force field algorithm to place the initial skeleton connecting line of the surface with the inside. In the reference, Wu et al. propose the extraction technique of a grid model-based skeleton and achieved promising results. However, this method can only be used for a simple topology.

Definition of force field

Assume that a point a on the tree surface of the skeleton model is visible to the other point b, then can be marked as \(\vec {ab}\). Thherefore, the visible set of surface skeleton s is V (x), which can be defined as

$$ \begin{array}{l} V(x)=\{v_{i}\mid \vec{v_{i}x},v_{i}\in s\} \end{array} $$
(14)

where x is all points on the surface skeleton of the tree model. Then, we define x as the visible counter-force:

$$ \begin{array}{l} F_{R}(x)=\sum\limits_{v_{i}\in v(x)}F(\parallel v_{i}-x\parallel)\cdot(v_{i}-x) \end{array} $$
(15)

where F(r) = r− 2 is the potential function.

Visibleset of points

The visible set of the tree’s point clouds is comprised of points x on the surface of the skeleton model, where x is the center of the sphere. To simplify the problem, we only consider the intersecting line of x and m in the tree model. Thus, this question is equivalent to the question on the uniform distribution of m points of a unit sphere. We use the particle system method to solve this question. The point of the center of the unit sphere is connected to m points of the surface to obtain m uniformly distributed lines. The experiment results demonstrate that the efficacity is optimal when m = ∣T(P)∣/10, where T(P) is the number of leaf nodes of OBBTree formed by P.

Interpolation of the skeleton

First, we translate pi (arbitrary point on the surface of the skeleton) into a certain distance to the negative direction of the normal. Then, the iteration is performed as follows:

$$ \begin{array}{l} p_{i + 1}=p_{i}+F_{z}(F_{R}(p_{i})\times e) \end{array} $$
(16)

where e is the pushing distance and Fz is the normalization function. The iteration will be stopped when the following condition is satisfied:

$$ \begin{array}{l} F_{R}(p_{i + 1})\geq F_{R}(p_{i}) \end{array} $$
(17)

From the above steps, we can obtain an initial inside skeleton of the point cloud tree. Figure 5 demonstrates the initial inside skeleton, and from Fig. 6 we can see that the obtained skeleton can mainly satisfy the requirements of centrality and maintain the original topology of the naturally grown trees.

Fig. 6
figure 6

Initial contraction of the tree skeleton. Due to different thicknesses of different parts to the stems, the node cannot achieve the desired shrinkage results

Full size image

Skeleton smoothing

Through the above steps, the final obtained skeleton often needs to be further addressed. Therefore, in this subsection, we smooth the obtained initial skeleton. We connect any two lines of the skeleton vivi+ 1 and vi+ 1vi+ 2. If the angle between the two lines is greater than the threshold, then we use vi+ 1 = (vi + vi+ 2)/2 to replace vi+ 1 to achieve the desired smoothing result. Figure 7 give a process schematic of this subsection.

Fig. 7
figure 7

Skeleton smoothing. a is it’s skeleton and b is smoothing result

Full size image

Results and discussion

Experimental results

All experiments in this work are carried out on an AMD E-350 Processor 1.06GHZ CPU, 4GB personal computer. The algorithm has been verified using two naturally grown trees, which are the flowering Cherry and Michelia. The experimental results demonstrate the efficiency and effectiveness of skeleton reconstruction using the proposed method in this work. The results, shown in Fig. 8, indicate that the branches of the skeleton generally satisfy the axis definition requirements. The fact that Michelia has a relatively large distance between branches, it may cause the threshold value to be insufficiently set, and may subsequently result in the skeleton to breaking for the case of fine branches, necessitating further processing. These questions must be resolved in the subsequent processing. After the skeleton is smoothed, we obtain a clear tree skeleton with satisfactory centricity and robustness. The algorithm is simple and feasible, and it has a strong generalization and practicality.

Fig. 8
figure 8

Final tree skeleton of Michelia and Cherry. Upon smoothing the initial skeleton, we obtain a tree skeleton that satisfies centricity and robustness. aMichelia, bCherry tree

Full size image

Table 1 illustrates that time complexity and space complexity to a greater degree within our algorithm than in skeleton extraction algorithms, regardless of whether the simple point clouds data model or large point cloud data model is used. Table 2 illustrates that the bulk of the time expenditure of this algorithm was spent on the compression of the skeleton model surface, with the pretreatment and post-treatment comprising approximately 35% of the total time. Table 3 illustrates that although the accuracy of the layered algorithm based on the OBB Tree is weaker than the Sphere of Tree method, in the actual experiment, the OBB Tree space complexity is relatively low. Thus, in this article, our adoption was based on the OBB Tree method.

Table 1 Data of the point cloud model level segmentation subtree
Full size table
Table 2 Efficiency analysis
Full size table
Table 3 Efficiency analysis of different sectioning methods
Full size table

Discussion

The skeleton extraction of point cloud trees is one of the basic research contents in forestry visualization process. In this work, we propose a novel combinational approach to reconstruct tree skeletons based on the point cloud data, in which the force field model is firstly used to extract tree skeleton. In addition to the simple combination, some used methods such as hierarchical subdivision method and feature extraction method have been improved in this paper. The results of experiment on real trees show that the method presented in this paper can achieve satisfactory results and is of strong practicability and extensibility.

It is a basic research topic to obtain parameter information of forest trees from terrestrial laser scanner point cloud data (Ducey and Astrup 2013; Kankare et al. 2016). The point cloud tree skeleton obtained in this work can be used as input for future research, for example, to simulate the interaction between trees and environment in the natural environment. It also has many advantages to study the trees by the terrestrial laser scanner point cloud data (Burt et al. 2013). Specifically: firstly, collecting point cloud data by terrestrial laser scanner greatly improves the efficiency of this method. In this paper, our research object is a single tree, so in the data acquisition process, we only need 2-3 people in about 3-hours to complete the data collection. Secondly, we can get more detailed feature information from point cloud data, such as tree height, breast diameter, and even volume value, etc. Therefore, the details of every branch are obvious, which helps us to make the skeleton of the tree. Thirdly, the point cloud data is three-dimensional data, compared to two-dimensional data, three-dimensional data is more conducive to the response of the study of the overall characteristics of the object.

However, nothing is perfect. There are also many disadvantages of using terrestrial laser scanner to acquire point cloud data (Deliormanli et al. 2014; Wallace et al. 2016). First, in the process of data collection, terrestrial laser scanner has higher environmental requirements, inclement weather and other environmental factors will limit the use of terrestrial laser scanner. Therefore, the use of terrestrial laser scanner has been limited to a certain extent. Second, compared with obtaining two-dimensional photos, three-dimensional point cloud data acquisition instrument is more expensive, and the processing flow of three-dimensional point cloud data is more complicated and time-consuming than that of a two-dimensional plane photo. Although the ground laser radar has the above shortcomings, it is still a superior tool when it comes to practical application, especially compared to the airborne or spaceborne laser scanners.

The advantage of the method proposed in this paper is that the force field and point cloud geodesic are fused, and that the method of point cloud layered processing is combined (Fig. 2). In addition, after layered processing of point cloud data, we use feature extraction method to remove redundant information between different layers, which can improve the efficiency and precision of point cloud processing (Fig. 3). After that, we use the visible force field to compress the surface geodesic of the point cloud data, and finally obtain the final point cloud tree skeleton after the skeleton smooth operation. The skeleton of most branches can be obtained by the method of this paper, but some twigs can not be treated well because the number of dots on the slender stems is small, and the method presented in this paper will be removed as a noise point. In order to solve certain practical application limitations, subsequent use can be considered to be a separate processing of thin stems, and other branches of the skeleton to be spliced to complete the skeleton extraction process of all trees.

Conclusions

Forest visualization technology has always been an important research topic in the field of experts and scholars at home or abroad. In this work, ground 3D laser scanning technology is applied to tree model-building and parameter extraction with some success. However, there are still some technical problems that must be resolved. In future works, the following aspects must be addressed:

  • Laser scanning has some limitations in that it could easily be affected by the weather and terrain. In addition, when the density is large or underground vegetation is dense, trees can interfere with each other, and vegetation cover will affect the quality of the scanning point cloud. This is the main reason for large errors in measurable factors, such as tree height and crown breadth measurements. To achieve high-quality scanned effects, the sample should both have the general morphological characteristics of trees and also be convenient to scan.

  • This research applies to deciduous trees. Evergreen trees cannot be reasonably addressed because it is difficult to distinguish the branches from the leaves, hindering the establishment of the branches of the point cloud model. However, we can consider building the complete contour model of the canopy to obtain crown-type parameters.

  • In the pretreatment stage, we must use cyclone separating to separate the branches and leaves. Although this step is advantageous to the subsequent parameter extraction, it increases the duration of the early modeling work. Thus, we must prove that the algorithm can automatically recognize different branches, which will simplify the process. Additionally, since the combination of this algorithm with multiscale solution thought may improve reconstruction, this is a future direction of study.