Article

Tree Branch Skeleton Extraction from Drone-Based
Photogrammetric Point Cloud
Wenli Zhang 1,*, Xinyu Peng 1, Guoqiang Cui 1, Haozhou Wang 2, Daisuke Takata 3 and Wei Guo 2,*
Information Department, Beijing University of Technology, Beijing 100022, China
Graduate School of Agricultural and Life Sciences, The University of Tokyo, Tokyo 188-0002, Japan
3 Faculty of Food and Agricultural Sciences, Fukushima University, Fukushima 960-1296, Japan* Correspondence: zhangwenli@bjut.edu.cn (W.Z.); guowei@g.ecc.u-tokyo.ac.jp (W.G.)
1
2

Abstract: Calculating the complex 3D traits of trees such as branch structure using drones/unmanned aerial vehicles (UAVs) with onboard RGB cameras is challenging because extracting branchskeletons from such image-generated sparse point clouds remains difficult. This paper proposes askeleton extraction algorithm for the sparse point cloud generated by UAV RGB images with photogrammetry. We conducted a comparison experiment by flying a UAV from two altitudes (50 m
and 20 m) above a university orchard with several fruit tree species and developed three metrics,
namely the F1-score of bifurcation point (FBP), the F1-score of end point (FEP), and the Hausdorff
distance (HD) to evaluate the performance of the proposed algorithm. The results show that the
average values of FBP, FEP, and HD for the point cloud of fruit tree branches collected at 50 m
altitude were 64.15%, 69.94%, and 0.0699, respectively, and those at 20 m were 83.24%, 84.66%, and
0.0474, respectively. This paper provides a branch skeleton extraction method for low-cost 3D digital management of orchards, which can effectively extract the main skeleton from the sparse fruit
tree branch point cloud, can assist in analyzing the growth state of different types of fruit trees, andhas certain practical application value in the management of orchards.
Keywords: unmanned aerial vehicle; tree phenotyping; open software
Citation: Zhang, W.; Peng, X.; Cui,G.; Wang, H.; Takata, D.; Guo, W.
Tree Branch Skeleton Extraction
from Drone-Based Photogrammetric
Point Cloud. Drones 2023, 7, 65.
https://doi.org/10.3390/drones702006
5
Academic Editors: Monica
Herrero-Huerta, Jose A.
Jiménez-Berni, Shangpeng Sun,
Ittai Herrmann and Diego
González-Aguilera
Received: 18 December 2022
Revised: 6 January 2023
Accepted: 8 January 2023
Published: 17 January 2023

Copyright: © 2023 by the authors. Licensee MDPI, Basel, Switzerland.
This article is an open access article
distributed under the terms and conditions of the Creative Commons Attribution (CC BY) license (https://creativecommons.org/licenses/by/4.0/).

1. Introduction
Point cloud data are commonly used to describe the 3D structure of objects and haveimportant applications in 3D reconstruction, engineering measurement, and morphological analysis, among other applications. With the widespread use of agricultural automation technology, the demands for point cloud analysis for high-throughput orchard phenotyping and growth modeling, such as plant shape, canopy structure, organ morphology, and stress response, are gradually increasing. Skeletonization is one of the essential
steps in point cloud analysis in which a three-dimensional skeleton of a tree point cloudis obtained. This step makes it easier to calculate tree height, branch length, and angle,
which comprise useful information for precise fruit tree growth management.
In the existing research on tree skeleton extraction, algorithms usually consist of twostages: firstly, skeleton points from the tree point cloud are extracted, and then skeleton
topology connections are formed from the skeleton points. The skeleton points extractionis the fundamental step of the whole process. Current research approaches to skeleton
point extraction can be broadly divided into three categories:
Graph structure-based [1–4]: a graph structure is a discrete structure consisting ofvertices and edges connecting the vertices. The skeleton of a tree-like point cloud can be
regarded as a combination of vertices and edges in a graph structure. The point cloud isconverted into a graph structure, the shortest distance from the root node to each point in
the point cloud is calculated to determine the skeleton points, and adjacent skeleton points

Drones 2023, 7, 65. https://doi.org/10.3390/drones7020065

www.mdpi.com/journal/drones

Drones 2023, 7, 65

2 of 34

are connected to form the branch skeleton. This method designs a skeleton point extraction algorithm for point clouds with a tree-like structure, which conforms to the structureof tree branches and has a good skeleton extraction effect. However, this method needs tocalculate the shortest path on the finely constructed graph structure, which causes highcomputational costs.
Generic point cloud skeleton extraction algorithms-based [5–14]: generic point cloudskeleton extraction algorithms mainly include generalized rotationally symmetric axis
(ROSA), L1-median and Laplace-based contraction (LBC). Many researchers have used
this class of algorithms for tree branch skeleton extraction. Since these algorithms have no
specific requirements on the structure of point cloud objects, they are adapted to a wider
range of point cloud skeleton extraction tasks and can be easily used for skeleton extraction of point clouds of many types of tree branches. However, such methods were notdesigned for tree point clouds, such algorithms may extract structures such as annular or
detached skeletons from point clouds, but these structures do not exist in natural tree
branches, which may not guarantee the accuracy of tree skeleton extraction.
Other point cloud skeleton extraction algorithms [15,16]: other tree skeleton extraction methods are based on nearest neighbor shrinkage or clustering to extract the skeleton,
and the skeleton points are obtained by the result of nearest neighbor shrinkage or clustering and connected to form the dendritic skeleton, and this kind of methods get betterskeleton extraction results on the point cloud model with regular shape. However, thesemethods require high quality of point clouds, and the algorithms are sensitive to parameters, which need to be finely set to obtain better skeleton extraction results.
In general, point cloud acquisition for branch skeleton extraction uses laser scanning,
multi-view reconstruction, and virtual model construction. Tree point clouds acquired using terrestrial laser scanning (TLS) or scanners have high accuracy [1–4,7–14], but this approach is expensive for large scale data acquisition for scenarios such as orchards and is
not suitable for actual orchard production. Although the use of unmanned aerial vehicle(UAV) laser scanning (ULS) to acquire point cloud has the advantages of large acquisition
range and high speed, the acquisition process is affected by airframe shaking, whichmakes it difficult to align into higher quality point cloud, and if the same quality of point
cloud as TLS is to be acquired, the cost of the acquisition equipment will increase significantly. Although the point cloud acquisition using photogrammetry [15,16] reduces thecost of laser scanning, the spatial information of tree objects needs to be strictly calibrated
when acquiring tree point cloud, and the process requires a relatively stable data acquisition environment, which limits its application in complex environmental scenarios suchas orchards. The construction of point cloud from virtual 3D models [14,17,18] is not affected by the actual acquisition environment, but the virtual point cloud often does not
represent the real 3D spatial structure of a fruit tree. In recent years, with the developmentof UAV aerial photography technology, the use of UAV equipped with RGB cameras togenerate point clouds has been widely used, which combines the advantages of ULS while
significantly reducing the equipment cost [19–21]. However, due to the limitation of theresolution of RGB cameras, the point clouds collected by this method are sparse and irregularly distributed in space, which makes fruit tree skeleton extraction challenging.
Therefore, an extraction algorithm for sparse RGB point cloud is needed to complete thefruit tree skeleton extraction task.
Meanwhile, reasonable evaluation metrics are important for verifying the performance of the tree point cloud skeleton extraction algorithms. In fruit tree growth management, parameters such as tree height, branch length, and branch angle need to be accurately calculated, and the fruit tree branch skeleton is an important basis for calculatingthese parameters. Therefore, setting reasonable metrics to evaluate the performance of theskeleton extraction algorithm is of great significance for the extension of the tree skeleton
extraction algorithm for use in scenarios such as orchards. In the evaluation work on tree
point cloud skeleton extraction, Bucksch et al. [4] graded the branches of tree branches bylength, counted the number of extracted tree branch skeletons and real branch skeletons

Drones 2023, 7, 65

3 of 34

under different length gradations, and evaluated the effectiveness of the skeleton extraction algorithm by calculating the correlation coefficient R2 between the two. This approachevaluates the performance of skeleton extraction only in terms of quantity, ignoring the
spatial information of branches. Li et al. [14] manually measured the real parameters oftree branches and calculated the F1 value (F1-Score), correlation coefficient (R2), and root
mean square error (RMSE) between the extracted tree branch skeleton parameters and thereal measured parameters to evaluate the branch skeleton structure parameters for accuracy. Fu et al. [18] proposed a quantitative evaluation of the skeleton extraction effect,
where the point cloud was generated from a virtual branch skeleton and the evaluation of
the skeleton extraction effect relied on the pre-existing virtual tree skeleton. However, thetree branch skeleton is a combination of a series of spatial curves, and drawing the curves
in 3D space by hand is often inaccurate and subjective, which affects the reliability of theevaluation results. Therefore, this evaluation method is not applicable to the skeleton extraction evaluation task of a real tree point cloud. We observed that there is no unified
standard for the evaluation of skeleton extraction algorithms at this stage, and there is aneed for evaluation metrics to verify the performance of actual tree point cloud skeleton
extraction algorithms.
In summary, in this paper, we propose a branch skeleton extraction algorithm for
UAV and photogrammetry-generated sparse RGB fruit tree point cloud and suggest evaluation metrics for tree branch point cloud to verify the performance of the algorithm proposed in this paper. The overall aims of the research were as follows.
(1) To address the problem of low accuracy of existing algorithms in skeleton extraction
for sparse point cloud data. In this paper, a spatial density-based regional point cloud
aggregation algorithm is designed to aggregate sparse tree point cloud before skeleton point extraction, and the aggregated point cloud can describe the 3D skeleton
morphology of branches, which can effectively improve the accuracy of subsequent
skeleton point extraction.
(2) To address the problem that the generic point cloud skeleton extraction algorithm isprone to broken branches and self-loops when the skeleton topology is connected,
which leads to unrealistic tree point cloud skeleton extraction results. In this paper,
we propose a skeleton topology connection method with spherical shrinkage fromthe outside to the root node, which can better adapt to the bifurcated tree structure,effectively avoiding the appearance of non-tree branch structure, and can effectively
extract the initial skeleton of tree branches.
(3) To objectively evaluate the skeleton extraction algorithm and thus verify the performance of the skeleton extraction algorithm on real tree branch point cloud. In thispaper, based on the consideration of the characteristics of tree branch structure morphology, the metrics for evaluating the accuracy of skeleton morphology: FBP (F1score of bifurcation point), FEP (F1-score of end point) and the metric for evaluating
the accuracy of skeleton topology: HD (Hausdorff distance) were designed, which
can reasonably evaluate the skeleton extraction performance of the algorithm.
(4) To release an easy-to-use software application that helps the community to test the
proposed algorithm and use it for other related applications.
2. Materials and Methods
2.1. Data Acquisition
The data set used in this experiment were acquired by an onboard RGB camera (1inch CMOS, lens FOV 84 degrees, focus length 8.8 mm, Max image size 5472 × 3648 pixels)
mounted on a low-cost industrial level UAV (DJI Phantom 4 RTK, DJI, Shenzhen, China).
The flight altitude was set to 50 m and 20 m, and both the front and side overlap in between photos were set to 80%. Synthesis of RGB point cloud was performed using DJI
Terra. All the flights were conducted at an orchard of the Institute for Sustainable Agroecosystem Services (ISAS), University of Tokyo Orchard (Tokyo, Japan) (35°44′16.0″ N,

Drones 2023, 7, 65

4 of 34

139°32′20.9″ E) on the following dates: 13 January 2022, 14 February 2022, and 4 March2022 (as shown in Figure 1a). There are multiple types of fruit trees growing in the orchard. In this paper, peach trees, persimmon trees, chestnut trees, and plum trees wereselected as experimental objects, and five fruit trees were randomly selected from eachtype of fruit tree to tag and conduct comparative experiments (as shown in the whitedashed box in Figure 1b). More details of the orchard are provided in Table 1.
Table 1. Orchard point cloud containing tree species and number of individuals.
Tree TypeApple
CherryChestnut
CitrusKiwifruit
LoquatPeach
Persimmon
Plum

Number of Individuals
17
2
86
25
15
5
51
95
46

Figure 1. Data acquisition location and orchard point cloud. (a) Point cloud collection location(35°44′16.0″ N, 139°32′20.9″ E). (b) DOM (Digital Orthophoto Map) generated from UAV images,
different color points in the map indicate the planting points of different species of fruit trees, andwhite dashed boxes and symbols in the map indicate the fruit tree objects selected for the experiment. (c) Three-dimensional view of the point cloud of the orchard. (d) Close-up view of the point
cloud of the branches of the fruit trees.

Drones 2023, 7, 65

5 of 34

2.2. General Architecture of the Algorithm
This section describes the general architecture of the algorithm in this paper, andFigure 2 shows the structure of the algorithm. The algorithm consists of the following
components.
1. Point cloud pre-processing module: this module first denoises the original branch
point cloud data, and then aggregates the sparse branch point clouds using the regional
point cloud aggregation method proposed in this study, which can form a dense point
cloud that roughly describes the morphology of the branch skeleton and prepares for thesubsequent skeleton point extraction.
2. Skeleton point extraction module: this module is based on the octree algorithm tospatially divide the clustered point cloud and extract the branch skeleton points in thedivided subspace.
3. Skeleton construction module: this module uses the spherical shrinkage based skeleton topology connection method proposed in this paper to form the thick skeleton of the
branch.
4. Branch skeleton morphology optimization module: this module fine-tunes the positioning of key points in the coarse skeleton first, and then smooths the branch coarse
skeleton to output the final fine skeleton.

Figure 2. Functional structure of point cloud skeleton extraction algorithm for fruit tree branches.

2.3. Point Cloud Pre-Processing Module

Drones 2023, 7, 65

6 of 34

To better extract the skeleton points from the original fruit tree branch point cloud,this section first denoises the original branch point cloud and then aggregates the denoised branch point cloud using a regional point cloud aggregation algorithm.
(1) Point cloud denoising processing
In this study, we used the density-based spatial clustering of applications with noise(DBSCAN) algorithm [22] to remove the anomalous points in the original point cloud. The
clustering approach is used to remove not only the anomalous outliers generated during
the synthesis of point cloud data but also the anomalous point cloud patches (classes of
reduced samples within clusters) generated during the reconstruction of point cloud data.
(2) Branch point cloud density enhancement
The branch skeleton is a series of curve combinations describing the centers of fruit
tree branches, and the skeleton points are the spatial points constituting these curves [23].
These spatial points are the centers of branch point cloud in a certain segment. Determining the centers of fruit tree branch point cloud in a certain segment of space is the focus ofskeleton point extraction. Since the branch point clouds generated by the RGB camera aresparse and not uniform, extracting the skeleton points directly from the denoised point
cloud will produce the problem of inaccurate positioning.
If the tree point cloud branches can be aggregated to the centerline region of the
branch skeleton (as shown in Figure 3a) in some way to form a higher density point cloudthat can describe the 3D curve shape of the skeleton, and then the skeleton points are
extracted from it, this can effectively improve the accuracy of skeleton point extraction.
Therefore, an algorithm for regional point cloud aggregation is proposed in this paper.
(1) Let the denoised tree branch point cloud be 𝐶 = 𝑥 , 𝑥 … 𝑥 … 𝑥 | 𝑥 ∈ 𝑅 }, andset the regional aggregation radius 𝑟, as shown in Equation (1):𝑟=∑ 𝑑𝑖𝑠𝑡(𝑥 , 𝑘 ),𝑛𝑖 ∈ [1, 𝑛](1)where 𝑘 is the 𝑘 nearest neighbor point of 𝑥 (𝑘 is determined according to the empirical value of the preparatory experiment and adjusted according to different tree species).
(2) Traverse each point 𝑥 in the point cloud, set a search region of radius 𝑟 around𝑥 , set the set of points contained in this search region as 𝑂 = 𝑥 , 𝑥 … 𝑥 … 𝑥 𝑥 ∈ 𝑅 },take the shape center 𝑐 of the point set 𝑂 , as shown in Equation (2):
𝑐 =

∑ 𝑥
,
𝑚

𝑗 ∈ [1, 𝑚](2)

As the target location for 𝑥 to move, the new point cloud set 𝐶 =𝑐 , 𝑐 … 𝑐 … 𝑐 𝑐 ∈ 𝑅 } obtained after the point cloud traversal is completed, andFigure 3b shows the process of point cloud aggregation in the region.
(3) Keeping the search radius 𝑟 constant, 𝑛 iterations of step (2) are carried out tofinally obtain the aggregated branch point cloud 𝐶 .

Drones 2023, 7, 65

7 of 34

Figure 3. Schematic diagram of regional point cloud aggregation. (a) Branch point cloud aggregation toward the skeleton centerline: the black point is the branch point cloud to be aggregated, theblue dashed line is the assumed skeleton centerline, and the gray arrow is the direction of movementof the point in the aggregation process. (b) Regional point cloud aggregation algorithm: red, orange,and green dashed lines with different colors indicate the search area of 𝑥 , blue dot 𝑐 is the target
location of 𝑥 movement.

Figure 4 shows the process of branch point cloud aggregation after n iterations (𝑛 =8). With increasing n, the distribution of the fruit tree branch point cloud gradually aggregates toward the center line of the skeleton, and since the number of points of the
branch point cloud does not change in the process, the density of the branch point cloud
gradually increases in the process of aggregation. After n iterations of iterative aggregation, the spatial distribution of branch point cloud is dense and concentrated near the center line of the branch skeleton, which can already show the three-dimensional morphology of the fruit tree branch skeleton. Extracting the skeleton points subsequently on thisbasis can effectively improve the accuracy of skeleton point positioning.

Drones 2023, 7, 65

8 of 34

Figure 4. Schematic diagram of point cloud iterative aggregation process: (a) Point cloud of fruit
tree branches after denoising. (b) Point cloud of fruit tree branches after three iterations of regional
point cloud aggregation. (c) Point cloud of fruit tree branches after five iterations of regional point
cloud aggregation. (d) Point cloud of fruit tree branches after eight iterations of regional point cloud
aggregation.

2.4. Skeleton Point Extraction Module
Skeleton point extraction involves finding spatial points that can describe the branchskeleton from the branch trunk point cloud. Since the spatial distribution of the aggregated fruit tree branch trunk point cloud can already describe the three-dimensional formof the branch skeleton, the skeleton points can be considered as the concentrated expression of the fruit tree branch trunk point cloud after aggregation in a subdivision space.
Therefore, this paper proposes a skeleton point extraction method based on subdivision
space point cloud shape center calculation, which first divides the aggregated fruit tree
branch trunk point cloud spatially, and then calculates the shape center of the point cloudin the subdivision space as the skeleton point (as the previous preparation for the construction of 2.5 section branch trunk skeleton). The specific implementation steps are as
follows.
(1) The octree based spatial partitioning
The octree algorithm [24], as one of the commonly used data structures for 3D spatial
partitioning, can accelerate spatial queries and efficiently manage 3D space. In this paper,
we first use the spatial octree structure to subspace the aggregated fruit tree branch trunk
point cloud, as shown in Figure 5.

Figure 5. Partitioning of the aggregated branch and stem point cloud using spatial octree.

𝑆 : smallest subspace divided using octree, 𝑂 : geometric center of subspace, 𝑐 :branch point cloud location in subspace, 𝑘 : skeleton points in subspace.
(2) Calculation of skeleton points in subspace
The skeleton point of the branch can be regarded as the center of the point cloud
geometry of the branch in a certain region. Considering that the center point O of theDrones 2023, 7, 65

9 of 34

subspace may have a large offset compared with the distribution of the point cloud in thespace, it could not represent the distribution of the point cloud in the subspace. Therefore,
to better reflect the representativeness of the skeleton point to the point cloud in the subspace, this paper adopts the shape center of the point cloud in the subspace as the skeleton
point k , which is defined as shown in Equation (3):
𝑘 =

∑ 𝑐
𝑛

, 𝑗 ∈ [1, 𝑛](3)where 𝑘 denotes the skeleton points calculated in each subspace, 𝑛 is the number ofpoint clouds contained in each subspace, and 𝒄𝒊𝒋 is the location of the branch point cloudin each subspace.
Calculating the point cloud shape centers as skeleton points in the subspace of theoctree subdivision can ensure that the spatial distribution of its skeleton points can betterreflect the fruit tree branch trunk morphology, which is ready for the skeleton construction in Section 2.5. Figure 6a shows the effect of spatial partitioning of the aggregatedwhole branch trunk point cloud using the octree algorithm; Figure 6b shows the extracted
fruit tree branch trunk skeleton points, and the extracted skeleton point distribution canstill better reflect the fruit tree skeleton morphology.

Figure 6. Schematic diagram of extraction of skeleton points from a spatial octree. (a) Spatial octree
partitioning of the point cloud. The black grid in the figure indicates the subspace where thebranch point cloud is located. (b) Skeleton points extracted using the spatial octree.

2.5. Skeleton Building Module
After extracting the skeleton points of fruit tree branches, the skeleton points need to
be topologically connected to form the tree branch skeleton. In previous work, the skeleton of the tree point cloud was usually obtained based on the nearest neighbor or bottomup topology connection [25], and the number of sub-branches at the bifurcation was notwell determined in the case of uneven distribution of skeleton points due to the need to
set a reasonable number of nearest neighbor skeleton points, which affects the correctnessof the extracted skeleton topology. Since the point cloud data in this paper are obtained

Drones 2023, 7, 65

10 of 34

from the reconstruction of RGB images collected by an overhead UAV, the point clouddata are sparse and contain less details of branches, which mainly reflect the main branch
structure of the fruit trees (e.g., main branches, submain branches, etc.). Therefore, toquickly construct the skeleton topology of the main branches of fruit trees, we designed aspherical shrinkage skeleton topology connection method from the outside to the root
node, which can effectively adapt to the bifurcated structure of fruit tree branches, andcan extract the key points (end points, bifurcation points) and skeleton segments (endpoint-bifurcation point, bifurcation point-bifurcation point) of the skeleton while obtaining the main skeleton of fruit tree branches.
Figure 7 shows the spherical contraction topology connection process of the local
branch skeleton, and the specific process of the algorithm is as follows.
(1) Firstly, starting from the farthest skeleton point 𝑝 , make a ball with the radius of
this point and the root node, connect this point with the nearest skeleton point 𝑝 which
is located inside the sphere shell. Following this, select the next far point 𝑝 as the starting
point, make a ball with the radius of this point and the root node, select the nearest skeleton point 𝑝 which is located inside the sphere shell to connect, and iterate the above
process to traverse all skeleton points.
(2) After all skeleton points are traversed, the 𝑑𝑖𝑣 of each skeleton point is calculated(𝑑𝑖𝑣 : the number of connections between a skeleton point and other skeleton points
around it. In this paper, we define 𝑑𝑖𝑣 = 1 for end points, 𝑑𝑖𝑣 = 2 for ordinary branchskeleton points, and 𝑑𝑖𝑣 >= 3 for bifurcation points) to extract the end points and bifurcation points in the skeleton points, and calculate each skeleton segment of the branchaccording to the connection status between the skeleton points.
(3) Due to the possible redundancy of the extracted skeleton points, there may be
shorter burr branches (skeleton segments containing fewer skeleton points) in the topologically connected skeleton. Set the threshold value 𝑙. If the skeleton segment contains
skeleton points greater than 𝑙, the skeleton segment is retained, otherwise the skeleton
segment is removed.

Figure 7. Schematic diagram of spherical contraction for skeleton topology connection. (a) Schematic diagram of the local skeleton of fruit tree branches. (b) Schematic diagram of spherical contraction for topological connection of local skeleton. Red dots are branch end points, green dots areDrones 2023, 7, 65

11 of 34

branch bifurcation points, gray arc-shaped dashed lines indicate the spherical shells where the skeleton points are located, and different colored connecting segments indicate each skeleton segment.
𝑝 -𝑝 are the skeleton points on each skeleton segment.

After the skeleton topology connection, the algorithm obtains the endpoints, bifurcation points, and the set of skeleton segments of the fruit tree branches along with the wholeskeleton. Figure 8 shows the coarse skeleton of a tree formed after the spherical shrinkage
topology connection, where red dots indicate the fruit tree branch skeleton end points,
green dots indicate the fruit tree branch skeleton bifurcation points, and different color
connection segments in the figure represent different segments of the fruit tree branchskeleton.

Figure 8. The coarse skeleton formed after topological connection.

Red dots indicate fruit tree branch skeleton endpoints, green dots indicate fruit tree
branch skeleton bifurcation points, and the connected segments of different colors in the
figure represent different segments of the fruit tree branch skeleton.
2.6. Skeleton Morphology Optimization Module
In 3D space, the real tree branch skeleton can be considered as a combination of multiple smooth spatial curves, and the two endpoints of the curves are always at the endpoints and bifurcation points of the branch skeleton. Therefore, the positions of the skeleton endpoints and bifurcation points need to be kept from moving during the smoothing
process of the skeleton. However, the algorithms commonly used for skeleton smoothing(e.g., polynomial smoothing, B spline fitting smoothing, etc.) are not adapted to the prerequisite of fixed skeleton curve endpoints and bifurcation points. Therefore, to solve thisproblem, the spatial Bezier curve [26] is chosen in this paper to perform spatial curvesmoothing on the extracted skeleton. To ensure the correctness of the optimized skeleton
morphology, the key points in the thick skeleton of the branches were first fine-tuned inthis paper before the pre-processing of the skeleton smoothing using Bezier curves (seeAppendix A: branch skeleton key point adjustment strategy).
In the extracted fruit tree branch skeleton, let a skeleton segment be 𝐵𝐻 =[𝑃 , 𝑃 , 𝑃 , … , 𝑃 ], (𝑛 is the number of skeleton points contained in the skeleton segment),
where 𝑃 is the end point (or bifurcation point) of the skeleton segment, 𝑃 is the bifurcation point of the skeleton segment, and 𝑃 and 𝑃 are used as the starting point andDrones 2023, 7, 65

12 of 34

end points, and 𝑃 , 𝑃 , … , 𝑃
as the control points of the Bezier curve, and the smoothing of this skeleton segment using an 𝑚(𝑚 = 𝑛 − 1) order spatial Bezier curve, thesmoothed curve 𝐵(𝑡) of this skeleton segment can be obtained, and the definition of 𝐵(𝑡)is shown in Equation (4):𝐵(𝑡) =𝐶 (1 − 𝑡)𝑡 𝑃 , 𝑡 ∈ [0, 1](4)

In the equation:𝐶 =𝑚!
𝑖! ∗ (𝑚 − 𝑖)!

As shown in Figure 9b, after the smoothing process of the spatial Bezier curve, thesegments of the skeleton are smoother and more natural, which can better reflect the threedimensional spatial shape of the real fruit tree branches.

Figure 9. Comparison of branch skeleton before and after smoothing. (a) Effect of fruit tree branchskeleton before smoothing. (b) Effect of fruit tree branch skeleton after smoothing.

3. Results
In this section, the proposed tree point cloud skeleton extraction algorithm is evaluated. First, evaluation metrics are designed to verify the effectiveness of the tree point
cloud skeleton extraction algorithm, and based on the evaluation metrics, the proposed
algorithm in this paper is compared with the L1-medial and the Laplacian based contraction (LBC) algorithm [6,11] for experiments. Section 3.1 introduces the metrics proposedin this paper to evaluate the effectiveness of skeleton extraction, F1-score of bifurcation
Point (FBP), F1-score of end Point (FEP), and Hausdorff distance (HD). In Section 3.2, theDrones 2023, 7, 65

13 of 34

environment of the comparison experiments and the specific comparison experimental
data and results are presented in this paper.
3.1. Evaluation Metrics
We propose FBP and FEP to evaluate the accuracy of skeleton topological connectionand HD to evaluate the accuracy of skeleton morphology. Note that the generated branch
point cloud and its extracted skeleton of different tree species are normalized in the spatial
range prior to evaluation by Equation (5):
𝑃

=

𝑥

𝑥−𝑥
−𝑥

,

𝑦

𝑦−𝑦
−𝑦

,

𝑧

𝑧−𝑧
−𝑧

(5)

] indicates the spatial range of the real fruit tree
,𝑦 ,𝑦 , 𝑧 ,𝑧where [𝑥 , 𝑥
point cloud.
The original fruit tree branch point cloud and the extracted branch skeleton are transformed into the normalized 3D space, and the evaluation of skeleton extraction in thispaper is carried out in the normalized 3D space.
3.1.1. Skeleton Topology Accuracy Metrics FBP and FEP
Branching angles are usually obtained by calculating the angles between branch bifurcation points and endpoints, while the accuracy of bifurcation point and endpoint positioning affects the topological accuracy of the fruit tree branch skeleton. Therefore, areasonable evaluation of the accuracy of bifurcation point and endpoint positioning is an
important part of the skeleton evaluation work. Since it is simpler to obtain the bifurcation
points and endpoints of branches from real branch point cloud and is not easily influenced
by subjective judgment, the spatial coordinates of these points in real branch point cloudobtained by manual labeling are used as real values to evaluate the positioning effect ofthe points of the skeleton extracted by the algorithm.
In this study, FBP is used to evaluate the extraction effect of bifurcation points of theskeleton, and the definition of FBP is shown in Equation (6):𝐹𝐵𝑃 =2 ∗ 𝑃𝐵𝑃 ∗ 𝑅𝐵𝑃
𝑃𝐵𝑃 + 𝑅𝐵𝑃

(6)

In the equation:
𝑃𝐵𝑃(𝑃𝑟𝑒𝑐𝑖𝑠𝑖𝑜𝑛 𝑜𝑓 𝐵𝑖𝑓𝑢𝑟𝑐𝑎𝑡𝑖𝑜𝑛 𝑃𝑜𝑖𝑛𝑡) =𝑅𝐵𝑃(𝑅𝑒𝑐𝑎𝑙𝑙 𝑜𝑓 𝐵𝑖𝑓𝑢𝑟𝑐𝑎𝑡𝑖𝑜𝑛 𝑃𝑜𝑖𝑛𝑡) =

𝐵𝑃
𝐵𝑁

𝐵𝑃
𝐵𝑇

where 𝐵𝑃 is the number of accurately located skeleton bifurcation points extracted by thealgorithm (set the Euclidean distance 𝑑 between the skeleton bifurcation points extracted
by the algorithm and their nearest true skeleton bifurcation points, and if 𝑑 is less than
the set threshold 𝑡, the skeleton bifurcation points are considered to be accurately located), 𝐵𝑁 is the total number of skeleton bifurcation points extracted by the algorithm,
and 𝐵𝑇 is the total number of true branch skeleton bifurcation points.
Similarly, FEP is set in this paper to evaluate the extraction effect of skeleton end
points. FEP is defined as shown in Equation (7):𝐹𝐸𝑃 =2 ∗ 𝑃𝐸𝑃 ∗ 𝑅𝐸𝑃
𝑃𝐸𝑃 + 𝑅𝐸𝑃

(7)

In the equation:
𝑃𝐸𝑃(𝑃𝑟𝑒𝑐𝑖𝑠𝑖𝑜𝑛 𝑜𝑓 𝐸𝑛𝑑 𝑃𝑜𝑖𝑛𝑡) =𝐸𝑃
𝐸𝑁

Drones 2023, 7, 65

14 of 34

𝑅𝐸𝑃(𝑅𝑒𝑐𝑎𝑙𝑙 𝑜𝑓 𝐸𝑛𝑑 𝑃𝑜𝑖𝑛𝑡) =𝐸𝑃
𝐸𝑇

where 𝐸𝑃 is the number of accurately located skeleton endpoints extracted by the algorithm (set the Euclidean distance 𝑑 between the skeleton endpoints extracted by the algorithm and their nearest real skeleton endpoints, and if 𝑑 is less than the set threshold𝑡, the skeleton endpoints are considered to be accurately located), 𝐸𝑁 is the total numberof skeleton endpoints extracted by the algorithm, and 𝐸𝑇 is the total number of realbranch skeleton endpoints.
3.1.2. Skeleton Morphological Accuracy Metric HD
To evaluate the accuracy of the skeleton morphology extracted by the algorithm, it isnecessary to evaluate the degree of fit between the extracted skeleton and the real fruit
tree. However, it is difficult and subjective to annotate the 3D skeleton from the real fruit
tree branch point cloud, which will affect the accuracy of the skeleton morphology evaluation results. Therefore, in this paper, we generated a point cloud around the extracted
skeleton and measured the morphological accuracy of the extracted skeleton by comparing the similarity between the generated fruit tree branch point cloud and the real fruit
tree branch point cloud. The HD is a measure to describe the degree of similarity between
two point sets [27], and the smaller the HD, the greater is the degree of similarity between
the two point sets; therefore, it can be used to measure the degree of similarity between
two point clouds.
To evaluate the morphological accuracy of the fruit tree branch skeleton, we set thereal branch point cloud after denoising as 𝐶 , generated the point cloud 𝐶 around thefruit tree branch skeleton by random sampling, and calculated the average of HD between
𝐶 and 𝐶 for 𝑛 times (𝑛 = 10 in this paper) as the final HD between 𝐶 and 𝐶 , which
can reduce the error caused by a single calculation. The HD between 𝐶 and 𝐶 : H(𝐶 , 𝐶 )is calculated as shown in Equation (8):𝐻 𝐶 ,𝐶=∑ 𝑚𝑎𝑥 ℎ 𝐶 , 𝐶 , ℎ 𝐶 , 𝐶𝑛(8)

In the equation:ℎ 𝐶 ,𝐶= 𝑚𝑎𝑥 𝑚𝑖𝑛 𝑃 − 𝑃ℎ 𝐶 ,𝐶= 𝑚𝑎𝑥 𝑚𝑖𝑛 𝑃 − 𝑃

∈

∈

∈

∈

Figure 10 shows the generated point cloud 𝐶 around the extracted skeleton and theoverlap effect with the real point cloud 𝐶 .

Drones 2023, 7, 65

15 of 34

Figure 10. Point cloud generation effect diagram (take a peach tree as an example). (a) Generated
point cloud around the fruit tree branch skeleton. (b) Overlap effect of generated point cloud andoriginal point cloud. The blue curve is the fruit tree branch skeleton, the black point is the original
branch point cloud 𝐶 , and the red point is the generated branch point cloud 𝐶 .

3.2. Comparison Experiments
In this section, based on the evaluation metrics proposed in Section 3.1, the algorithm
proposed in this paper is compared with the L1-medial and the LBC. Section 3.2.1 introduces the comparison experiment environment; Section 3.2.2 introduces the comparison
experiment data and results, and the analysis and discussion of the results.
3.2.1. Experimental Environment
The algorithms used for the experiments in this paper are performed on the same
computer, which is configured with an AMD Ryzen 7 4800U processor with 1.80 GHz and
16 GB running memory, and the experimental environment is a Windows 10 operating
system. This algorithm was run using python 3.7, and the GUI was developed using C++
and the Qt framework.
3.2.2. Comparison Experiments
Currently, the L1-medial and the LBC algorithm, as the most commonly used algorithms in point cloud skeleton extraction work, have been largely applied in fruit tree
skeleton extraction tasks [7–14]. Further, the existing tree point cloud skeleton extraction
work is also usually carried out based on these two algorithms. In this section, on the point
cloud of fruit tree branches generated by UAV images at 50 m and 20 m, the point cloudskeleton extraction algorithm of fruit tree branches proposed in this paper is comparedwith L1-medial and LBC, and the specific comparison experiments and experimental results are shown in Appendix B Exhibit 2-1.
(1) 50 m altitude comparison experiment
In this study, we first conducted comparative experiments on the point cloud of fruit
tree branches collected by UAV at a 50 m altitude to qualitatively evaluate the skeleton
extraction effect of fruit tree branches, and quantitatively evaluate the three algorithms interms of skeleton connection accuracy and skeleton morphology accuracy by combining
three metrics, FEP, FBP, and HD.
Figure 11 shows the visualization of the fruit tree branch skeleton extracted by thethree algorithms on the point cloud of fruit trees collected at a 50 m altitude (one tree of
each fruit tree is selected for display).

Drones 2023, 7, 65

16 of 34

Figure 11. The visualization of the fruit tree branch skeleton extracted by the three algorithms on
the point cloud of fruit trees collected at a 50 m altitude. The black points are the original fruit tree
branch point cloud, the blue curve is the skeleton extracted by the algorithm, the green points are
the bifurcation points of the fruit tree branch skeleton, and the red points are the end points of the
fruit tree branch skeleton.

From the results of the skeleton extraction in the figure, although the L1-medial andthe LBC extracted the skeleton of the fruit tree branches, the skeleton has different degrees
of defects (as shown by the orange dashed circles in Figure 11. Using the L1-medial algorithm, when processing the sparser RGB point cloud, the skeleton of some branches could
not be connected well. Due to the irregular distribution of the point cloud generated by
the RGB images, the LBC extracts a ring-like structure in the branch skeleton of fruit trees,
which does not exist in real trees, and affects the realism of the algorithm skeleton extraction effect. In contrast, the proposed algorithm extracts a more complete branch skeletonand correct topological connections, and the final extracted branch skeleton has asmoother and more natural shape due to the smoothing process of the branch skeleton in
the algorithm.
From the average values of the metrics in Table 2, the point cloud skeleton extraction
algorithm proposed in this paper has higher FBP and FEP than the other two algorithms,
reaching 64.15% and 69.94% for the four fruit trees, respectively. Meanwhile, the HD of
the extracted skeleton by the algorithm was 0.0699, which is also smaller than those of theother two compared algorithms. Furthermore, from Tables in the Appendix section, thealgorithm proposed in this paper performed the best among 47 metrics out of the total 60
metrics for 20 fruit trees. The experimental results show that the algorithm is more accurate in locating the bifurcation points and end points of the skeleton on the point cloud offruit tree branches collected at a 50 m altitude, and the point cloud generated from theskeleton extracted by the algorithm has higher similarity with the real fruit tree branch

Drones 2023, 7, 65

17 of 34

point cloud. This suggests that the skeleton of fruit tree branches extracted by the proposed algorithm has better skeleton topology and morphological accuracy, and better reflects the real morphology of fruit tree branches.
Table 2. The average values and variation of metrics for the skeleton extraction results of the threealgorithms on the branch point clouds of the four types of fruit trees generated from images collected at a 50 m and 20 m altitude (t = 0.03).
Tree_Species_Number

MetricFBP

L1-Medial
70.76%

50 m
LBC
57.60%

Proposed
83.60%

L1-Medial
60.26%

20 m
LBC
70.41%

Proposed
86.30%

L1-Medial−10.50%

Variation
LBC
13.81%

Proposed
2.71%

Average_Peach

FEP

73.63%

75.02%

83.64%

64.50%

65.41%

83.35%−9.13%−9.61%−0.29%HD
FBP

0.064758.04%

0.057458.13%

0.043374.76%

0.076268.80%

0.069870.82%

0.054684.77%

0.011510.76%

0.012413.69%

0.011310.01%

FEP

61.60%

67.36%

85.45%

70.71%

61.49%

90.04%

9.11%−5.87%

4.59%

HD
FBP

0.087833.74%

0.063
30.35%

0.058245.92%

0.099659.05%

0.068856.01%

0.052779.93%

0.011825.31%

0.005826.66%−0.0055
34.01%

FEP

42.48%

33.40%

48.54%

55.51%

44.86%

83.64%

13.03%

11.46%

35.10%HD
FBP

0.109440.72%

0.103232.43%

0.090952.31%

0.070865.38%

0.06
63.26%

0.039381.98%−0.0386
24.66%−0.0432
31.83%−0.051629.67%

FEP

60.20%

36.41%

62.12%

77.85%

52.79%

81.59%

17.65%

16.38%

19.46%HD
FBP

0.118450.82%

0.106844.63%

0.087164.15%

0.097
63.37%

0.073661.13%

0.043283.24%−0.0215
12.56%−0.0332
21.50%−0.043919.10%

FEP

59.48%

53.05%

69.94%

67.14%

56.14%

84.66%

7.67%

3.09%

14.72%

HD

0.09510.0826

0.06990.08590.06810.0474−0.0092−0.0146−0.0224

Average_Persimmon

Average_Chestnuts

Average_Plum

Average_Total

To verify the stability of the skeleton extraction algorithm under different acquisition
times, acquisition light conditions, and other environments, we collected point clouds offruit tree branches at a 50 m altitude on 13 January, 24 February, and 4 March 2022, andconducted comparative experiments, and the specific experimental results are shown in
the Appendix section following the paper (Appendix C Exhibit 3-1, Exhibit 3-2,Exhibit3-3). Appendix C Exhibit 3-4 in the Appendix of the paper show the standard deviationsof the different algorithms for each metric of the fruit trees in the three comparative experiments mentioned above. Based on the information presented in Appendix C Exhibit
3-4, we can see that the algorithm of this paper has a smaller standard deviation in theexperimental metrics compared with the L1-medial and the LBC. This indicates that thedata fluctuation of the three 50 m altitude comparison experiments of this paper’s algorithm is lower. Therefore, the algorithm proposed in this paper can maintain a good skeleton extraction effect under different fruit tree branch point cloud acquisition environments.
In summary, combining the effect of fruit tree skeleton extraction and experimental
evaluation metrics, it can be seen that in the comparison experiments of RGB point cloud
generated from images collected at a 50 m altitude, compared with the other two algorithms, the skeleton of fruit tree branches extracted by the algorithm in this paper has amore realistic 3D structure and has a better performance of evaluation metrics on most of
the fruit trees. Further, the proposed algorithm can more effectively and stably extract the
point cloud of fruit tree branches from the point cloud of fruit tree branches, and ensure
realism of the skeleton. However, we also observed that the experimental metrics of all
three algorithms on chestnut and plum trees are poor compared to the results on peachand persimmon trees. To verify the effectiveness of our algorithm on the point cloud ofchestnut and plum trees with higher quality of point cloud, we also reduced the altitudeof image acquisition to 20 m to generate a higher quality RGB point cloud.
(2) 20 m altitude comparison experiment
Figure 12 shows the visualization of the fruit tree branch skeleton extracted by thethree algorithms on the point cloud of fruit trees collected at 20 m altitude (one tree of
each fruit tree is selected for display).

Drones 2023, 7, 65

18 of 34

Figure 12. The visualization of the fruit tree branch skeleton extracted by the three algorithms on
the point cloud of fruit trees collected at 20 m altitude.

The black points are the original fruit tree branch point cloud, the blue curve is theskeleton extracted by the algorithm, the green points are the bifurcation points of the fruit
tree branch skeleton, and the red points are the end points of the fruit tree branch skeleton
As shown in the figure, compared with the point cloud of fruit tree branches collected
at 50 m, the point cloud collected by the UAV at a flight altitude of 20 m is of higher
quality, presenting a larger number of fruit tree branches and a more complex branching
structure of fruit trees. The effect of skeleton extraction shows that although the skeletons
extracted by the L1-medial and LBC can show the morphology of fruit tree branches, there
are still different degrees of broken branches and self-loops (as shown by the orange
dashed circles in Figure 12); especially in the peach and persimmon trees with more complex branch structures, the two algorithms show more skeleton topology connection errors, which affect the authenticity of the extracted fruit tree branch skeleton. Comparedwith the two comparative algorithms, the proposed algorithm extracted more completebranch skeletons and accurate topological connections in terms of the point cloud of fruit
tree images captured at an altitude of 20 m with more complex structures, although theproposed algorithm also showed local skeleton linkage errors (as shown in the graydashed circles in Figure 12).
Based on information provided in Table 2, in the comparison experiments on four
fruit trees at 20 m altitude, the average value of FBP for the proposed algorithm is 83.24%,
which is 19.87% higher than that of L1-medial and 17.11% higher than that of LBC; theaverage value of FEP is 84.66%, which is 17.52% higher than that of L1-medial and 28.52%
higher than that of LBC; the average value of HD is 0.0474, which is 0.0385 lower than thatof L1-medial algorithm and 0.0207 lower than that of LBC, which shows that the proposed

Drones 2023, 7, 65

19 of 34

model achieved the best values in all three metrics. Based on the information presented inAppendix C Exhibit 3-5 in the Appendix text, the algorithm proposed in this paper performs best in 52 metrics among 60 metrics for 20 fruit trees. It can be seen that in the point
cloud of fruit tree branches collected at a 20 m altitude, the skeleton of fruit tree branches
extracted by the algorithm proposed in this paper can still maintain better topology andmorphological accuracy compared with the L1-medial and LBC. In other words, the skeleton extracted by the proposed algorithm is more realistic in the point cloud of fruit tree
branches collected at a 20 m altitude.
(3) Analysis of experimental results at different altitudes
Figure 13 shows the average values of the experiment metrics on all fruit tree branch
point clouds generated from images collected at both altitudes, and Table 2 shows theamount of variation in the average values of the metrics for the three algorithms on thefour types of fruit trees at both altitudes.

Figure 13. The average values of metrics for the three algorithms on all fruit trees. (a) Average FBP(F1-score of bifurcation point) for the different algorithms at 50 m and 20 m. (b) Average FEP (F1score of end point) for the different algorithms at 50 m and 20 m. (c) Average HD (Hausdorff distance) for the different algorithms at 50 m and 20 m

As shown in Figure 13, with a decrease in the fruit tree point cloud collection altitude,
the average values of FBP and FEP of the three skeleton extraction algorithms on the four
fruit trees showed an increasing trend, and the average values of HD showed a decreasing
trend, which showed that the quality of the collected fruit tree branch point cloud was
improved with a reduction in the data collection altitude.
From the column of the amount of variation in Table 2, chestnut and plum trees
whose metrics performed poorly in the comparison experiment at a 50 m altitude, showedsignificant improvement in the skeleton extraction results in the comparison experimentwith images taken at a 20 m altitude. For chestnut and plum trees with sparse branches,
the improvement of fruit tree branch point cloud quality can effectively improve the accuracy of the algorithm in extracting skeleton topology and morphology. The proposed
algorithm improved the average values of FBP, FEP, and HD metrics by 34.01%, 35.10%,
and 0.0516, respectively, for the five chestnut trees, and improved the average value by
29.67%, 19.46%, and 0.0439, respectively, for the five plum trees. This indicates that the
proposed algorithm can improve the skeleton extraction effect to a greater extent withimprovement in the quality of fruit tree branch point cloud.
We also noted that the experimental metrics of peach and persimmon trees in thecomparison experiment at a 20 m altitude did not improve significantly with the improvement of point cloud quality compared with those of chestnut and plum trees, but deteriorated in some metrics (e.g., the average values of FEP and HD experimental metrics ofpeach trees). The reason for this is that although the fruit tree branch point clouds collectedDrones 2023, 7, 65

20 of 34

by lowering the UAV flight altitude to 20 m are of higher quality, the fruit tree branch
point cloud of peach and persimmon trees also present a more complex structure, and thefine branches of the fruit tree are more distinct (as shown in Figure 14). These finebranches can easily be ignored in the process of skeleton extraction, which makes the fruit
tree branch skeleton extraction more difficult.

Figure 14. Point cloud of branches of the same fruit tree collected at different altitudes.
(Tree_Peach_02 is shown as an example). (a) Point cloud of branches collected at 50 m altitude. (b)Point cloud of branches collected at 20 m altitude.

From Table 2, although the average value of FEP decreased by 0.29% and the averagevalue of HD increased by 0.0113 for peach trees for the proposed algorithm, the metrics
deteriorated less compared to that in the L1-medial and LBC algorithms. The L1-medial
algorithm reduced the FBP metric of peach tree by 10.50%, the LBC reduced the FEP metric of persimmon tree by 5.87%, and both algorithms increased the HD metric of persimmon tree by 0.0118 and 0.0058, respectively, which shows that the proposed algorithm canstill maintain a better performance in the complex fruit tree branch point cloud skeleton
extraction task compared with the two other algorithms.
4. Discussion and Conclusions
In this paper, a branch skeleton extraction algorithm is proposed for the sparse RGB
fruit tree point cloud collected by UAV, which can effectively extract the skeleton fromthe sparse fruit tree branch point cloud, approximate the 3D structure of the original fruit
tree, and more realistically reflect the branch morphology of the fruit tree. The algorithm
proposed is based on point clouds generated from images captured by UAV RGB cameras.
Compared with the method of extracting skeleton points using point cloud data collectedby devices such as LiDAR [7,8,12–14], the algorithm proposed can effectively reduce thecost of point cloud data collection while maintaining the accuracy of skeleton point extraction, such as evaluate the growth of orchard trees by analyzing the tree morphometry
using UAVs [28,29].
Combining the comparison experiments at 50 m and 20 m altitudes, it can be foundthat the algorithm proposed in this paper has better performance in terms of FBP, FEP and
HD metrics compared with L1-medial and LBC. At the same time, the results of comparison experiments at different altitudes show that for fruit trees with sparse branch structure (e.g., chestnut and plum trees), the reduction in UAV flight altitude can improve thequality of the collected fruit tree branch point cloud and improve the skeleton extraction
effect of the algorithm. However, for the more complex branch structure (e.g., peach andpersimmon trees), with a reduction in flight altitude, the UAV can collect a more complex
fruit tree branch point cloud structure, which brings challenges to the skeleton extractionof the algorithm. Therefore, when a more complex fruit tree branch structure is dealt with,whether the skeleton can be effectively extracted from the branch point cloud is an important basis to test the adaptability of the fruit tree point cloud skeleton extraction algorithm. Compared with the L1-medial and LBC, the algorithm proposed in this paper canDrones 2023, 7, 65

21 of 34

still maintain good experimental results on more complex fruit tree branch point cloud,indicating that the algorithm proposed in this paper can also adapt to the extraction taskof the skeleton of more complex fruit tree branch point cloud (Figure 15).

Figure 15. The effect of the algorithm in extracting the branch skeleton of fruit trees in an orchard
plot (the different color curves in the figure indicate the branch skeleton of each fruit tree).

As a conclusion, after the experiments and discussions in this paper, the proposed
method can effectively extract the skeleton from the point cloud of fruit tree branches
measured by UAV photogrammetry. It is undeniable that extracting the skeleton from acomplex tree branch point cloud is still a challenging task. Unlike conventional objects
with clear 3D structures, tree branches have open surfaces and complex branches, and thecollected point cloud often fails to clearly represent the tree branch morphology, causing
greater difficulties in the subsequent branch skeleton extraction. Therefore, the algorithm
proposed in this paper still has areas for improvement:
First, based on the experimental results, it can be found that the algorithm in thispaper shows advantages in fruit tree branch point cloud skeleton extraction. However,there are still some problems, such as poor performance in FEP and FBP metrics of somefruit trees in the comparison experiments. The reason for this is that the algorithm in thispaper aggregates the fruit tree branch point cloud, and the skeleton point extraction andsubsequent skeleton topology connection are performed on the aggregated point cloud,and the deviation of skeleton key point positioning occurs. In future work, optimizing thepositioning of skeleton end points by using the search method with direction and the positioning of skeleton bifurcation points by using the local density judgment can be considered.
Second, at this stage, the parameters need to be set manually during skeleton extraction. For example, the number of points and iterations of regional point cloud aggregation
will affect the point cloud aggregation and the recurrence depth of spatial octree, andsubspace point threshold will affect the extracted skeleton points, among other such issues. The parameters during skeleton extraction need to be adjusted according to the typeand height of fruit trees and other attributes, which may require some experience. It is
possible to conduct several experiments on branch point clouds of different tree species
to acquire empirical values to apply to the needs of different types of fruit trees, and also
to try to project reasonable parameter thresholds based on the projected area and space
size of fruit trees in the vertical direction.

Drones 2023, 7, 65

22 of 34

In the actual work of fruit tree morphological analysis, the extracted fruit tree skeleton can be used to calculate parameters such as branch length and branch angle (e.g., theangle between main and secondary branches, and other parameters, as shown in
Figure 16) to achieve the task of automated fruit tree morphological analysis. On the basisof the extracted fruit tree branch skeleton, phenotypic information of fruit tree canopy canbe calculated, which can be used in practical applications for tasks such as orchard canopy
cover, biomass density and carbon sequestration estimation [30–32]. In addition, the real
3D tree branch skeleton is the basis for modeling scenes of orchards and woodlands, andthe algorithm proposed in this paper can extract a realistic fruit tree branch skeleton, andthe reconstructed tree model on this basis can better restore the real 3D morphology offruit trees. Therefore, the virtual 3D model of fruit trees can be formed based on the extracted skeleton by regularized programming and mapping in future work (as shown in
Figure 17) to meet the demand for 3D visualization display of orchards and other scenes[33–36].

Figure 16. Automated calculation of fruit tree branch angles using the skeleton extraction softwarein this paper.

Figure 17. Fruit tree branch reconstruction based on the skeleton extracted by the algorithm in thispaper (persimmon tree is shown as an example). (a) Original fruit tree branch point cloud. (b) Fruit
tree branch skeleton extracted by this algorithm.
Author Contributions: W.Z., X.P. and W.G. conceived the ideas and designed the methodology;
W.Z., X.P. and W.G. implemented the technical pipeline, conducted the experiments, and analyzed

Drones 2023, 7, 65

23 of 34

the results; G.C. and H.W. investigated relevant work; D.T. provided the dataset for the experiments; all authors discussed, wrote the manuscript, and gave final approval for publication. All
authors have read and agreed to the published version of the manuscript.
Funding: This study was partially supported by the National Natural Science Foundation of China(NSFC) Program 62276009 and Japan Science and Technology Agency (JST) AIP Acceleration Research JPMJCR21U3.
Data Availability Statement: the data and executable files (EasySkeleton) used in this paper will beavailable upon request here: https://github.com/I3-Laboratory/EasySkeleton, (accessed on 17 December 2022).
Acknowledgments: The authors thank the technical staff of the Institute for Sustainable Agro-ecosystem Services (ISAS), the University of Tokyo for the field management, and Mr. Kubota for the
fruit tree’s location survey.
Conflicts of Interest: The authors declare that we have no conflicts of interest.

Appendix A. Branch and Trunk Skeleton Key Point Adjustment Strategy
Skeleton bifurcation point adjustment: as the point cloud at the bifurcation point of
the fruit tree branches is dense, the extracted skeleton bifurcation points may deviate fromthe bifurcation center of the branch point cloud. As the subsequent optimization of theskeleton morphology needs to be based on the skeleton to accurately locate the bifurcation
points of the skeleton and to better assist this process, the bifurcation points of the skeleton
need to be adjusted toward the bifurcation center of the branch point cloud by moving thebifurcation points as far as possible toward the parent branch. Since the positioning of thebifurcation points of the skeleton in 3D space cannot be adjusted by simply fitting straightlines of the skeleton segments to find the intersection points (the intersection points ofmultiple non-coplanar lines cannot be determined in 3D space). Therefore, the following
skeleton bifurcation point adjustment strategy is designed in this paper.
As shown in Figure A1, let the initial extracted coarse skeleton bifurcation point be
𝑏𝑝, the sub-branch skeleton points neighboring 𝑏𝑝 be 𝑠𝑝_1, 𝑠𝑝_2, and the parent branchskeleton point be 𝑠𝑝_𝑓, let the line between 𝑠𝑝_1 and 𝑠𝑝_𝑓 be 𝐿 , the line between 𝑠𝑝_2
and 𝑠𝑝_𝑓 be 𝐿 , and the line between 𝑏𝑝 and 𝑠𝑝_𝑓 be 𝐿 . Calculate the projection points
𝑓 and 𝑓 of 𝑏𝑝 on 𝐿 and 𝐿 , and then calculate the midpoints of the projection points
𝑓 and 𝑓 on 𝐿 as the new skeleton bifurcation points 𝑏𝑝, , and update the skeleton segments where they are located, and the adjusted skeleton bifurcation points are more reasonably located.

Drones 2023, 7, 65

24 of 34

Figure A1. Schematic diagram of skeleton bifurcation point adjustment. (a) Positioning of skeleton
bifurcation points before adjustment. (b) Positioning of skeleton bifurcation points after adjustment.

Skeleton end point adjustment: since the skeleton point extraction operation is built
on top of the aggregated fruit tree branch point cloud, the extracted skeleton endpoints
will naturally move towards the inside of the branch and cannot be positioned to the endof the fruit tree branch. To locate the skeleton endpoints accurately, it is necessary to extend the skeleton as far as possible to the endpoints of the fruit tree branch point cloud inthe vicinity of the extracted skeleton endpoints. For this purpose, the following skeleton
endpoint adjustment strategy is designed in this paper.
As shown in Figure A2, a spherical region with radius 𝑟 (empirical value) is set atthe end point 𝑒𝑝 as the center of the sphere 𝑂 , and the point set 𝐶 in which the point
cloud 𝐶 is in this region after the denoising is searched. The line where the skeleton point
𝑠𝑝 connected with the end point 𝑒𝑝 is taken as the normal 𝑙, the plane 𝛼 perpendicular
to 𝑙 and containing the end point 𝑒𝑝 is calculated, the plane 𝛼 is used to partition 𝐶 ,the set 𝐴 of points in 𝐶 that are on the opposite side from sp are separated and thepoint in 𝐴 which is farthest from ep as the adjusted skeleton endpoint 𝑒𝑝, is selected,
and ep is connected with 𝑒𝑝, , as the extension of this skeleton segment.

Figure A2. Schematic diagram of skeleton endpoint adjustment. (a) Skeleton endpoint positioning
before adjustment. (b) Skeleton endpoint positioning after adjustment.

Drones 2023, 7, 65

25 of 34

Appendix B. Overview of experimental results
Exhibit 2-1. Comparison experimental contents of fruit tree branch point cloud skeleton extraction.
Comparison Experiments
Experimental Content
Figures and Tables(1-1) Visual analysis of skeleton extraction effect at 50 m
Figure 11
altitude(1-2) Metric analysis of skeleton extraction effect at 50 m
Table 2
(1) 50 m altitude comparison experialtitude
Exhibit 1-1
ment
Appendix C Exhibit(1-3) Algorithm stability analysis (analysis of three 50 m
3-1, 3-2, 3-3 Appenaltitude experimental metrics)
dix C Exhibit 3-4(2-1) Visual analysis of skeleton extraction effect at 20 m
Figure 12
altitude(2) 20 m altitude comparison experiment(2-2) Metric analysis of skeleton extraction effect at 20 m
Table 2
altitudeExhibit 3-1
Table2(3) Analysis of experimental results at Analysis of the change of metrics from 50 m to 20 m exFigure 13
different altitudes
perimental results
Figure 14
Appendix C. The Detailed Comparative Experimental Results of This Article
The arrows in the metrics column in the attached table represent the experimental
metrics for which the algorithms in this paper performed poorly, and the bold font in each
metric represents the value of the metric corresponding to the best algorithm under thatmetric.
Exhibit 3-1: comparison experimental results of branch point cloud skeleton extraction for fruit trees collected at 50 m altitude (1).
(Comparison experiment time: 13 January 2022.)

Tree_Species_Number
Tree_Peach_01

Tree_Peach_02

Tree_Peach_03

Tree_Peach_04

Tree_Peach_05

Average_Peach

Tree_Persimmon_01

Metric

L1-Medial

LBC

Proposed

FBP
FEP
HD
FBP
FEP
HD
FBP
FEP
HD
FBP
FEP
HD
FBP
FEP
HD
FBP
FEP
HD
FBP
FEP

66.67%
42.11%
0.079081.82%
87.50%
0.089766.67%
86.96%
0.049572.00%
82.35%
0.050266.67%
69.23%
0.041070.76%
73.63%
0.064742.86%
81.82%

58.82%
72.73%
0.075676.00%
81.25%
0.039947.62%
51.67%
0.058450.00%
78.57%
0.073455.56%
90.91%
0.039857.60%
75.02%
0.057462.50%
92.31%

85.71%
82.35%
0.063185.71%
89.66%
0.035376.19%
69.57%
0.043281.48%
89.66%
0.039488.89%
86.96%
0.035483.60%
83.64%
0.043380.00%
86.49%↓↓↓

Drones 2023, 7, 65

26 of 34

Tree_Persimmon_02

Tree_Persimmon_03

Tree_Persimmon_04

Tree_Persimmon_05

Average_Persimmon

Tree_Chestnuts_01

Tree_Chestnuts_02

Tree_Chestnuts_03

Tree_Chestnuts_04

Tree_Chestnuts_05

Average_Chestnuts

Tree_Plum_01

Tree_Plum_02

Tree_Plum_03

Tree_Plum_04
Tree_Plum_05

HD
FBP
FEP
HD
FBP
FEP
HD
FBP
FEP
HD
FBP
FEP
HD
FBP
FEP
HD
FBP
FEP
HD
FBP
FEP
HD
FBP
FEP
HD
FBP
FEP
HD
FBP
FEP
HD
FBP
FEP
HD
FBP
FEP
HD
FBP
FEP
HD
FBP
FEP
HD
FBP
FEP
HD
FBP

0.104358.52%
62.50%
0.085158.82%
53.33%
0.096380.00%
34.48%
0.080950.00%
75.86%
0.072558.04%
61.60%
0.087823.16%
40.00%
0.090922.22%
47.06%
0.158233.33%
34.48%
0.059140.00%
53.33%
0.132550.00%
37.50%
0.125033.74%
42.48%
0.109436.36%
70.59%
0.084522.22%
66.67%
0.136560.00%
30.77%
0.161125.00%
71.43%
0.115460.00%

0.047955.17%
66.67%
0.077266.67%
86.96%
0.053570.59%
55.17%
0.070935.71%
35.71%
0.065858.13%
67.36%
0.063031.58%
22.22%
0.113212.50%
38.10%
0.174355.17%
47.62%
0.060512.50%
19.05%
0.095340.00%
40.00%
0.072830.35%
33.40%
0.103228.57%
52.17%
0.102354.55%
26.67%
0.103626.67%
11.11%
0.07739.52%
50.00%
0.114742.86%

0.041268.97%
87.50%
0.075085.71%
86.96%
0.046178.26%
77.42%
0.073960.87%
88.89%
0.054774.76%
85.45%
0.058246.15%
47.06%
0.064733.33%
40.67%
0.140655.17%
58.82%
0.080722.22%
46.15%
0.102372.73%
50.00%
0.066245.92%
48.54%
0.090942.86%
58.82%
0.081861.54%
66.67%
0.077057.14%
56.92%
0.099340.00%
66.67%
0.068360.00%

↓
↑

↓

↑
↓
↑

↓

↓
↑
↓

Drones 2023, 7, 65

27 of 34

Average_Plum

Average_Total

FEP
HD
FBP
FEP
HD
FBP
FEP
HD

61.54%
0.129
40.72%
60.20%
0.118450.82%
59.48%
0.095142.11%
0.136
32.43%
36.41%
0.106844.63%
53.05%
0.082661.54%
0.109
52.31%
62.12%
0.087164.15%
69.94%
0.0699

Exhibit 3-2: comparison experimental results of branch point cloud skeleton extraction for fruit trees collected at 50 m altitude (2).
(Comparison experiment time: 14 February 2022).
Tree_Species_Number
Tree_Peach_01

Tree_Peach_02

Tree_Peach_03

Tree_Peach_04

Tree_Peach_05

Average_Peach

Tree_Persimmon_01

Tree_Persimmon_02

Tree_Persimmon_03

Tree_Persimmon_04

Tree_Persimmon_05
Average_Persimmon

Metric
FBP
FEP
HD
FBP
FEP
HD
FBP
FEP
HD
FBP
FEP
HD
FBP

L1-Medial
61.54%
66.67%
0.078166.67%
85.71%
0.092763.16%
83.33%
0.048372.00%
80.00%
0.057966.67%

LBC
58.82%
72.73%
0.071676.00%
81.25%
0.041742.11%
51.67%
0.056359.26%
81.48%
0.039752.63%

Proposed
85.71%
82.35%
0.062885.71%
89.66%
0.036772.73%
66.67% ↓

FEP
HD
FBP
FEP
HD
FBP
FEP

76.92%
0.063566.01%
78.53%
0.069860.00%
95.00%

90.91%
0.037257.76%
75.61%
0.049352.94%
91.89%

86.96%
0.033284.39%
83.06%
0.042880.00%
89.47%

HD
FBP
FEP
HD
FBP
FEP
HD
FBP
FEP

0.112960.00%
68.57%
0.080553.33%
54.55%
0.127778.79%
66.67%

0.054746.67%
73.33%
0.079872.73%
86.96%
0.070675.86%
66.67%

0.045069.57%
76.47%
0.070366.67%
86.96%
0.050475.86%
90.91%

HD
FBP
FEP
HD
FBP

0.078470.00%
81.48%
0.071064.42%

0.068934.48%
35.71%
0.064656.54%

0.069460.87%
88.89%
0.050370.59%

0.045388.89%
89.66%
0.035988.89%↓↓↓↑

Drones 2023, 7, 65

28 of 34

Tree_Chestnuts_01

Tree_Chestnuts_02

Tree_Chestnuts_03

Tree_Chestnuts_04

Tree_Chestnuts_05

Average_Chestnuts

Tree_Plum_01

Tree_Plum_02

Tree_Plum_03

Tree_Plum_04

Tree_Plum_05

Average_Plum

Average_Total

FEP
HD
FBP
FEP
HD
FBP
FEP
HD
FBP
FEP
HD
FBP

73.25%
0.097223.16%
40.00%
0.101722.22%
47.06%
0.156333.33%
34.48%
0.057340.00%

70.91%
0.067731.58%
22.22%
0.1078
11.77%
42.11%
0.170855.17%
47.62%
0.061910.53%

86.54%
0.057146.15%
47.06%
0.065033.33%
40.67%
0.141855.17%
58.82%
0.079122.22%

FEP
HD
FBP
FEP
HD
FBP
FEP
HD
FBP

53.33%
0.126550.00%
37.50%
0.129333.74%
42.48%
0.112136.36%

17.39%
0.092241.67%
40.00%
0.074730.14%
33.87%
0.101528.57%

46.15%
0.108650.00%
50.00%
0.065841.38%
48.54%
0.092142.86%

FEP
HD
FBP
FEP
HD
FBP
FEP
HD
FBP
FEP
HD
FBP
FEP
HD
FBP
FEP
HD
FBP
FEP
HD

70.59%
0.086422.22%
70.59%
0.101860.00%
30.77%
0.173625.00%
71.43%
0.111360.00%
66.67%
0.170140.72%
62.01%
0.121651.22%
64.07%
0.100252.17%
0.086550.00%
37.50%
0.098737.50%
11.11%
0.0801
9.52%
50.00%
0.132042.86%
42.11%
0.138233.69%
38.58%
0.107144.53%
54.74%
0.081458.82%
0.079376.92%
66.67%
0.075057.14%
56.92%
0.098436.36%
66.67%
0.065660.00%
72.34%
0.118654.66%
64.28%
0.087462.75%
70.61%
0.0698

↓

↑
↓
↑

↓

↓
↑
↓

Exhibit 3-3: comparison experimental results of branch point cloud skeleton extraction for fruit trees collected at 50 m altitude (3).
(Comparison experiment time: 4 March 2022).

Drones 2023, 7, 65

29 of 34

Tree_Species_Number

MetricFBP

L1-Medial
76.92%

LBC
58.82%

Proposed
85.71%

Tree_Peach_01

FEP

66.67%

63.64%

82.35%

Tree_Peach_02

HD
FBP
FEP
HD
FBP

0.078683.33%
85.71%
0.088063.16%

0.069276.00%
81.25%
0.040738.10%

0.065188.00%
89.66%
0.039076.19%

Tree_Peach_03

FEP

76.92%

51.67%

69.57%HD
FBP

0.049069.57%

0.052146.15%

0.045681.48%

FEP

78.57%

85.71%

89.66%HD
FBP

0.055780.00%

0.065044.44%

0.034388.89%

FEP

80.00%

90.91%

86.96%HD
FBP

0.051274.60%

0.039252.70%

0.033384.05%

FEP

77.58%

74.64%

83.64%HD
FBP

0.066953.85%

0.053256.25%

0.043580.00%

FEP

81.82%

91.89%

89.47%HD
FBP

0.050560.00%

0.053357.14%

0.048969.57%

FEP

62.07%

75.00%

76.47%HD
FBP

0.081757.14%

0.079766.67%

0.072366.67%

FEP

60.87%

86.96%

86.96%HD
FBP

0.121378.79%

0.073968.97%

0.055775.86%

FEP

90.91%

60.00%

90.91%HD
FBP

0.097755.56%

0.068131.25%

0.068560.87%

FEP

62.86%

35.71%

88.89%HD
FBP

0.080061.07%

0.068856.06%

0.042270.59%

FEP

0.71700.69910.8654HD
FBP

0.0862
16.67%

0.068740.00%

0.057542.86%

FEP

33.33%

21.05%

66.67%HD
FBP

0.092122.22%

0.090411.77%

0.062533.33%

FEP

47.06%

40.00%

40.67%HD
FBP

0.151333.33%

0.154255.17%

0.145855.17%

FEP

34.48%

47.62%

58.82%HD
FBP

0.065640.00%

0.06859.52%

0.077622.22%

FEP

53.33%

17.39%

46.15%

HD
FBP
FEP
HD

0.118966.67%
50.00%
0.10360.079041.67%
42.86%
0.08700.097766.67%
50.00%
0.0669Tree_Peach_04

Tree_Peach_05

Average_Peach

Tree_Persimmon_01

Tree_Persimmon_02

Tree_Persimmon_03

Tree_Persimmon_04

Tree_Persimmon_05

Average_Persimmon

Tree_Chestnuts_01

Tree_Chestnuts_02

Tree_Chestnuts_03

Tree_Chestnuts_04

Tree_Chestnuts_05

↓

↓

↓

↓
↑

↓

↑
↓
↑

Drones 2023, 7, 65

30 of 34

Average_Chestnuts

Tree_Plum_01

Tree_Plum_02

Tree_Plum_03

Tree_Plum_04

Tree_Plum_05

Average_Plum

Average_Total

FBP

35.78%

31.63%

44.05%

FEP

43.64%

33.78%

52.46%HD
FBP

0.103936.36%

0.095826.09%

0.090142.86%

FEP

68.52%

50.00%

58.82%HD
FBP

0.086722.22%

0.097350.00%

0.081076.92%

FEP

66.67%

25.00%

72.34%HD
FBP

0.106060.00%

0.125231.53%

0.060957.14%

FEP

30.77%

11.11%

47.09%HD
FBP

0.141225.00%

0.07939.52%

0.087036.36%↑

FEP

71.43%

50.00%

66.67%↓HD
FBP

0.134144.44%

0.124228.57%

0.097657.14%

FEP

66.67%

42.11%

66.67%HD
FBP

0.179437.61%

0.151829.14%

0.101854.09%

FEP

60.81%

35.64%

62.32%HD
FBP

0.129552.26%

0.115542.38%

0.085763.20%

FEP

63.43%

53.49%

71.24%

HD

0.09660.08330.0692↓↓

Exhibit 3-4: standard deviation of the comparison experimental results of branch
point cloud skeleton extraction for fruit trees collected at 50 m altitude.
(Comparison experiment time: 4 March 2022).
Tree_Species_Number

MetricFBP

L1-Medial
0.0783

LBC
0.0000

Proposed
0.0000

Tree_Peach_01

FEP

0.14180.05250.0000HD
FBP

0.00040.09220.00320.00000.00130.0132FEP

0.01030.00000.0000HD
FBP

0.00240.02030.00090.04780.00190.0200FEP

0.05080.00000.0167HD
FBP

0.00060.01410.00320.06740.00130.0428FEP

0.01910.03590.0000HD
FBP

0.00400.07700.01750.05760.00260.0000

Tree_Peach_02

Tree_Peach_03

Tree_Peach_04

Tree_Peach_05

FEP

0.05550.00000.0000

Average_Peach

HD
FBP
FEP
HD
FBP

0.01120.04300.02600.00250.08680.00140.02880.00490.0041
0.04850.00120.00400.00330.00040.0000

Tree_Persimmon_01

FEP

0.07610.00240.0173HD
FBP

0.03380.00850.0036
0.05570.00390.0035FEP

0.03640.0441

0.0637

Tree_Persimmon_02

Drones 2023, 7, 65

31 of 34

Tree_Persimmon_03

Tree_Persimmon_04

Tree_Persimmon_05

Average_Persimmon

Tree_Chestnuts_01

Tree_Chestnuts_02

Tree_Chestnuts_03

Tree_Chestnuts_04

Tree_Chestnuts_05

Average_Chestnuts

Tree_Plum_01

Tree_Plum_02

Tree_Plum_03

Tree_Plum_04

Tree_Plum_05

Average_Plum

Average_Total

HD
FBP

0.00240.02810.00150.03500.00240.1100FEP

0.04050.00000.0000HD
FBP

0.01660.00700.01100.03610.00480.0139FEP

0.28310.05770.0779HD
FBP

0.01050.10320.00150.02310.00290.0000FEP

0.09550.00000.0000HD
FBP

0.00480.03190.00220.01090.00630.0241FEP

0.06330.01830.0063HD
FBP

0.00590.03750.00300.04860.00060.0190FEP

0.03850.00670.1132HD
FBP

0.00590.00000.01190.00420.00140.0000FEP

0.00000.02010.0000HD
FBP

0.00350.00000.01080.00000.00270.0000FEP

0.00000.00000.0000HD
FBP

0.00440.00000.00430.01510.00150.0000FEP

0.00000.00960.0000HD
FBP

0.00680.09620.00870.00960.00550.1177FEP

0.07220.01650.0000HD
FBP

0.01380.01180.00770.00800.00050.0228FEP

0.00670.00250.0226HD
FBP

0.00420.00000.00390.01430.00100.0000FEP

0.01190.01260.0000HD
FBP

0.00120.00000.00810.02620.00130.0888FEP

0.0226

0.06790.0328HD
FBP

0.01890.00000.0141
0.05430.00880.0000FEP

0.00000.00000.0568HD
FBP

0.01630.00000.00150.00000.00680.0210FEP

0.00000.00000.0000HD
FBP

0.01220.08980.00860.08250.01780.0165FEP

0.02960.00000.0540HD
FBP

0.02700.01800.00860.02350.00840.0123FEP

0.00920.01520.0120HD
FBP

0.00570.00750.00500.01270.00090.0071FEP

0.02490.00880.0065HD

0.00260.00100.0004

Drones 2023, 7, 65

32 of 34

Exhibit 3-5: comparison experimental results of branch point cloud skeleton extraction for fruit trees collected at 20 m altitude.
(Comparison experiment time: 4 March 2022).
Tree_Species_Number
Tree_Peach_01

Metric
FBP
FEP
HD
FBP

L1-Medial
55.56%
62.30%
0.074165.71%

LBC
59.38%
62.30%
0.075173.56%

Proposed
82.35%
81.69%
0.065181.25%

Tree_Peach_02

FEP

63.93%

65.00%

79.25%HD
FBP

0.102560.61%

0.086272.73%

0.100283.72%↑

FEP

71.11%

71.80%

71.11%↓HD
FBP

0.050351.52%

0.055770.73%

0.038792.31%

FEP

61.54%

62.34%

89.58%HD
FBP

0.090967.93%

0.054780.65%

0.033991.89%

FEP

63.64%

65.63%

95.12%HD
FBP

0.065660.26%

0.077571.41%

0.035086.30%

FEP

64.50%

65.41%

83.35%HD
FBP

0.076275.00%

0.069883.08%

0.054682.35%

Tree_Persimmon_01

FEP

75.00%

68.85%

88.57%

Tree_Persimmon_02

HD
FBP
FEP
HD
FBP

0.085561.22%
55.74%
0.126380.00%

0.061270.18%
59.26%
0.071365.39%

0.067587.50%
89.55%
0.058979.25%

FEP

81.36%

46.81%

93.55%HD
FBP

0.086063.16%

0.071360.47%

0.042480.77%

FEP

83.64%

47.83%

89.66%HD
FBP

0.093764.62%

0.083680.00%

0.039493.98%

FEP

57.83%

84.71%

88.89%HD
FBP

0.120568.80%

0.056771.82%

0.055484.77%

FEP

70.71%

61.49%

90.04%HD
FBP

0.099628.57%

0.068866.67%

0.052760.00%

FEP

38.46%

31.58%

69.57%HD
FBP

0.065966.67%

0.068662.50%

0.053266.67%

FEP

34.78%

57.14%

81.67%HD
FBP

0.100453.33%

0.070170.59%

0.0321
84.12%

FEP

66.67%

42.11%

91.74%HD
FBP

0.055466.67%

0.053250.00%

0.033694.74%

FEP

47.62%

43.48%

85.24%

HD

0.0967

0.05600.0291

Tree_Peach_03

Tree_Peach_04

Tree_Peach_05

Average_Peach

Tree_Persimmon_03

Tree_Persimmon_04

Tree_Persimmon_05

Average_Persimmon

Tree_Chestnuts_01

Tree_Chestnuts_02

Tree_Chestnuts_03

Tree_Chestnuts_04

↑

↓

↓

Drones 2023, 7, 65

33 of 34

FBP

80.00%

35.29%

94.12%

FEP

90.00%

50.00%

90.00%HD
FBP

0.040559.05%

0.052157.01%

0.048379.93%

FEP

55.51%

44.86%

83.64%HD
FBP

0.070866.67%

0.060032.00%

0.039369.57%

FEP

92.31%

57.14%

88.89%HD
FBP

0.128457.14%

0.060471.43%

0.057582.35%

FEP

75.00%

53.33%

77.78%HD
FBP

0.041558.82%

0.054484.21%

0.028572.73%

FEP

75.00%

60.00%

75.00%HD
FBP

0.110070.59%

0.100773.68%

0.044195.24%

Tree_Plum_04

FEP

70.00%

50.00%

78.26%

Tree_Plum_05

HD
FBP
FEP
HD
FBP

0.111373.68%
76.92%
0.062165.38%

0.063060.00%
43.48%
0.089364.26%

0.040790.00%
88.00%
0.045481.98%

Average_Plum

FEP

77.85%

52.79%

81.59%HD
FBP

0.097063.37%

0.073666.13%

0.043283.24%

FEP

67.14%

56.14%

84.66%

HD

0.08590.06810.0474

Tree_Chestnuts_05

Average_Chestnuts

Tree_Plum_01

Tree_Plum_02

Tree_Plum_03

Average_Total

↑

↓

↓

References

1.

Xu, H.; Gossett, N.; Chen, B. Knowledge and heuristic-based modeling of laser-scanned trees. ACM Trans. Graph. (TOG) 2007,
26, 19-es.
2. Wang, Z.; Zhang, L.; Fang, T.; Mathiopoulos, P.T.; Qu, H.; Chen, D.; Wang, Y. A structure-aware global optimization method
for reconstructing 3-D tree models from terrestrial laser scanning data. IEEE Trans. Geosci. Remote Sens. 2014, 52, 5653–5669.
3. Livny, Y.; Yan, F.; Olson, M.; Chen, B.; Zhang, H.; El-Sana, J. Automatic reconstruction of tree skeletal structures from point
clouds. In ACM SIGGRAPH Asia 2010 Papers; Association for Computing Machinery: New York, NY, USA, 2010; pp. 1–8.
4. Alexander, B.; Lindenbergh, R.; Menenti, M. SkelTre. Vis. Comput. 2010, 26, 1283–1300.
5. Andrea, T.; Zhang, H.; Cohen-Or, D. Curve skeleton extraction from incomplete point cloud. In ACM SIGGRAPH 2009 Papers;
Association for Computing Machinery: New York, NY, USA, 2009; pp. 1–9.
6. Huang, H.; Wu, S.; Cohen-Or, D.; Gong, M.; Zhang, H.; Li, G.; Chen, B. L1-medial skeleton of point cloud. ACM Trans. Graph.
2013, 32, 1–8.
7. Mei, J.; Zhang, L.; Wu, S.; Wang, Z.; Zhang, L. 3D tree modeling from incomplete point clouds via optimization and L1-MST.
Int. J. Geogr. Inf. Sci. 2017, 31, 999–1021.
8. Song, C.; Pang, Z.; Jing, X.; Xiao, C. Distance field guided $$ L_1 $$ L1-median skeleton extraction. Vis. Comput. 2018, 34, 243–
255.
9. Bin, L.; Wang, Q.; Fan, X. An Optimized L1-Medial Skeleton Extraction Algorithm. In Proceedings of the 2021 IEEE International
Conference on Industrial Application of Artificial Intelligence (IAAI), Harbin, China, 25 December 2021; IEEE: Piscataway, NJ,
USA, 2021.
10. Cao, J.; Tagliasacchi, A.; Olson, M.; Zhang, H.; Su, Z. Point cloud skeletons via laplacian based contraction. In Proceedings ofthe 2010 Shape Modeling International Conference, mAix-en-Provence, France, 21–23 June 2010; IEEE: Piscataway, NJ, USA,2010.
11. Su, Z.; Zhao, Y.; Zhao, C.; Guo, X.; Li, Z. Skeleton extraction for tree models. Math. Comp. Model. 2011, 54, 1115–1120.
12. He, G.Z. The Trees Skeleton Extraction Based on point cloud Contraction. In Applied Mechanics and Materials; Trans Tech Publications Ltd.: Wollerau, Switzerland, 2014; Volume 475.

Drones 2023, 7, 65

34 of 34

13. Wu, S.; Wen, W.; Xiao, B.; Guo, X.; Du, J.; Wang, C.; Wang, Y. An accurate skeleton extraction approach from 3D point cloudsof maize plants. Front. Plant. Sci. 2019, 10, 248.

14. Li, Y.; Su, Y.; Zhao, X.; Yang, M.; Hu, T.; Zhang, J.; Liu, J.; Liu, M.; Guo, Q. Retrieval of tree branch architecture attributes fromterrestrial laser scan data using a Laplacian algorithm. Agri. Forest Meteor. 2020, 284, 107874.

15. Jianling, Z.; Liu, J.; Zhang, M. Curve skeleton extraction via k-nearest-neighbors based contraction. Int. J. Appl. Math. Comp. Sci.
2020, 30, 123–132.

16. Lou, L.; Liu, Y.; Shen, M.; Han, J.; Corke, F.; Doonan, J.H. Estimation of branch angle from 3D point cloud of plants. In Proceed17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.

ings of the 2015 International Conference on 3D Vision, Lyon, France, 19–22 October 2015; IEEE: Piscataway, NJ, USA, 2015.
Yinxi, G.; Yang, Y.; Yang, X. Three-dimensional reconstruction of the virtual plant branching structure based on terrestrial lidar
technologies and L-system. Int. Arch. Photogram. Remote Sens. Spatial Inf. Sci. 2018, 42, 3.
Fu, L.; Liu, J.; Zhou, J.; Zhang, M.; Lin, Y. Tree skeletonization for raw point cloud exploiting cylindrical shape prior. IEEE Access
2020, 8, 27327–27341.
Dell, M.; Stone, C.; Osborn, J.; Glen, M.; McCoull, C.; Rimbawanto, A.; Tjahyono, B.; Mohammed, C. Detection of necrotic foliage
in a young Eucalyptus pellita plantation using unmanned aerial vehicle RGB photography–a demonstration of concept. Aust.
Forest. 2019, 82, 79–88.
Maimaitijiang, M.; Sagan, V.; Sidike, P.; Maimaitiyiming, M.; Hartling, S.; Peterson, K.T.; Maw, M.J.; Shakoor, N.; Mockler, T.;
Fritschi, F.B. Vegetation metric weighted canopy volume model (CVMVI) for soybean biomass estimation from unmanned
aerial system-based RGB imagery. ISPRS J. Photogram. Remote Sens. 2019, 151, 27–41.
González-Jaramillo, V.; Fries, A.; Bendix, J. AGB estimation in a tropical mountain forest (TMF) by means of RGB and multispectral images using an unmanned aerial vehicle (UAV). Remote Sens. 2019, 11, 1413.
Ester, M.; Kriegel, H.P.; Sander, J.; Xu, X. A density-based algorithm for discovering clusters in large spatial databases withnoise. Inkdd 1996, 96, 226–231.
Cornea, N.D.; Silver, D.; Min, P. Curve-skeleton properties, applications, and algorithms. IEEE Trans. Nisual. Comp. Graphics
2007, 13, 530.
Meagher, D. Geometric modeling using octree encoding. Comp. Graphics Image Process. 1982, 19, 129–147.
Francisco, Y.; Silwal, A.; Kantor, G. Visual 3d reconstruction and dynamic simulation of fruit trees for robotic manipulation. In
Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition Workshops, Seattle, WA, USA, 13–19
June 2020.
Josh, H.M.L.; Yam, Y. A skeletonization technique based on delaunay triangulation and piecewise bezier interpolation. In Proceedings of the 2007 6th International Conference on Information, Communications & Signal Processing, Singapore, 10–13 December 2007; IEEE: Piscataway, NJ, USA, 2007.
Facundo, M. Gromov-Hausdorff distances in Euclidean spaces. In Proceedings of the 2008 IEEE Computer Society Conference
on Computer Vision and Pattern Recognition Workshops, Anchorage, AK, USA, 23–28 June 2008; IEEE: Piscataway, NJ, USA,2008.
Krause, S.; Sanders, T.G.; Mund, J.P.; Greve, K. UAV-based photogrammetric tree height measurement for intensive forest 737
monitoring. Remote Sens. 2019, 11, 758.
Sun, G.; Wang, X.; Yang, H.; Zhang, X. A canopy information measurement method for modern standardized apple orchards
739 based on UAV multimodal information. Sensors 2020, 20, 2985.
Lefsky, M.A.; Cohen, W.B.; Harding, D.J.; Parker, G.G.; Acker, S.A.; Gower, S.T. Lidar remote sensing of above-ground biomass
in 741 three biomes. Glob. Ecol. Biogeogr. 2002, 11, 393–399.
Lambert, M.; Ung, C.; Raulier, F. Canadian national tree aboveground biomass equations. Can. J. For. Res. 2005, 35, 1996–2018.
Hilker, T.; van Leeuwen, M.; Coops, N.C.; Wulder, M.A.; Newnham, G.J.; Jupp, D.L.; Culvenor, D.S. Comparing canopy metrics
745 derived from terrestrial and airborne laser scanning in a Douglas-fir dominated forest stand. Trees 2010, 24, 819–832.

33. Liu, J.; Zhang, X.; Li, H.; Dai, M. Creation of tree models from freehand sketches by building 3D skeleton point cloud. In International Conference on Technologies for E-Learning and Digital Entertainment; Springer: Berlin/Heidelberg, Germany, 2010.

34. Preuksakarn, C.; Boudon, F.; Ferraro, P.; Durand, J.B.; Nikinmaa, E.; Godin, C. Reconstructing plant architecture from 3D laser
scanner data. In Proceedings of the 6th International Workshop on Functional-Structural Plant Models, Davis, CA, USA, 12–17
September 2010.
35. Guo, J.; Jiang, H.; Benes, B.; Deussen, O.; Zhang, X.; Lischinski, D.; Huang, H. Inverse procedural modeling of branching structures by inferring L-systems. ACM Trans. Graph. 2020, 39, 1–13.
36. Dobson, D.; Dong, H.; van der Horst, N.; Langhorst, L.; van der Vaart, J.; Wu, Z. Tree Reconstruction from a Point Cloud Using
an L-System. Master’s Thesis, Technische Universiteit Delft: Delft, The Netherlands, 2021.
Disclaimer/Publisher’s Note: The statements, opinions and data contained in all publications are solely those of the individual author(s) and contributor(s) and not of MDPI and/or the editor(s). MDPI and/or the editor(s) disclaim responsibility for any injury topeople or property resulting from any ideas, methods, instructions or products referred to in the content.