Circles and circle-like shapes were successfully detected us-
ing line sweeping and the modified Hough transform (Figure
4). Lines were identified from each sliced bin after circle
detection. First, triangles were assigned to different groups,
based on their connectivity, i.e., two triangles were in the
same group if they shared a common edge. Second, the points
in these groups that had already been detected as circles were
excluded. The remaining triangle groups were abstracted as
lines; the start node and end node of each line were treated
as the tip point and end point of the corresponding point
group, respectively. Note that as defined by our algorithm
lines represent point clusters instead of points forming a line.
Most of the lines were found in leaf clusters, with a few at
the wood part where branches were insufficiently scanned or
grew horizontally.
Step 4 - Thresholding Circles and Lines
After the above steps had been performed, the original point
cloud was simplified to skeleton points consisting of circle
centers and line nodes. This step eliminated circles and lines
with a radius or line length smaller than a threshold
T
, set at
6 mm for the camphor tree and 1.5 cm for the magnolia and
virtual trees. The biological meaning of
T
can be interpreted
as follows. The radius or size of the trunk/branch slice should
decrease with increasing height as we trace towards the tip of
the tree from the ground. At a certain height, the size of the
branch slice (i.e.,
T
) should be small enough for only small
twigs and leaves to exist above this height. Our strategy for
extracting wood from a tree is to “break” a branch where the
size of its horizontal slice equals
T
, and only keep the parts of
size greater than
T
.
Step 5 - Extracting Skeleton Wood Points
The skeleton wood points (i.e., circle centers and line nodes
in the wood part) were disconnected from line nodes in the
leaf part after Step 4. The aim of this step is to separate the
skeleton wood points from line nodes in the leaf part auto-
matically. Dijkstra’s shortest-path algorithm (Dijkstra, 1959)
was chosen for this purpose, because of its extensive and suc-
cessful use in graph analysis (Xu
et al.
, 2007; Cote
et al
., 2009;
Livy
et al.
, 2010). Given a graph
G
= (
V
,
E
), where
V
repre-
sents the vertices and
E
represents the edges, a path is defined
as a sequence of vertices (
v
1
,
v
2
, ...,
v
n
), such that each adjacent
pair of vertices is connected by an edge. By assigning each
edge a weight
w
, the shortest-path problem can be expressed
as follows: starting from the source vertex
u
, find the path to
vertex
v
under the constraint of minimizing the weight of the
whole path (i.e., at the lowest cost). If there is no path stretch-
ing from vertex
u
to vertex
v
, the weight of this shortest path
is treated as infinite. In summary,
w u v
min w u v
v
( , )
( :
)
=
→
∞
if shortest-path exits
if is not reachable
.
(3)
Because the skeleton wood points were disconnected from
line nodes in the leaf part now, according to Equation 3, the
weight of the shortest path from the root point to any line
nodes in the leaf part should be infinite; therefore the skel-
eton wood points were extracted as follows.
First, a graph
G
= (
V
,
E
) was built. Starting from the root
point (
u
, the lowest point of the target tree), every circle
center or line node (
v
) was connected to the neighborhoods
above, within the search range of the circle radius or line
length.
Second, the shortest path to every other vertex
v
from the
root vertex
u
was calculated. For each
v
i
∈
v
: {if
w
(
u
,
v
i
) is not
∞
,
v
i
∈
N
}, where
N
represents the skeleton wood points.
Step 6 - Kd-Tree Range Searching for Wood Points
In the last step, once the skeleton wood points had been
detected, a range search was performed to find wood points.
This procedure can be described as follows. We put the
skeleton wood points into the raw point cloud of the tree
and used them as “hooks” for “hooking” other wood points.
Technically, a kd-tree object was first built to establish the
topological relationship of the point cloud consisting of both
the skeleton wood points and the raw point cloud of a tree.
Then every skeleton wood point searched its neighborhood
within the range of the search radius. A constant search range
(13 cm) was assigned to each skeleton wood point of the three
trees. After the wood points had been identified, the remain-
ing points in the raw point cloud were regarded as leaf points.
Intensity Approach to Wood-Leaf Separation
The intensity approach was also used and the results were
compared with those obtained using the geometric method.
As the virtual tree did not have intensity information, wood-
leaf separation using this approach was only applied to the
camphor and magnolia trees. Two different threshold values,
namely
t
1 and
t
2, were manually chosen for each tree. Points
of intensity >
t
1 were defined as wood points and those of in-
tensity <
t
2 were defined as leaf points (Cote
et al
., 2009). The
intensity values were standardized by setting the maximum
value at 1.0. Points with intensities simultaneously >
t
2
and
<
t
1 were omitted in the intensity approach. In order to obtain
wood-leaf separation of high accuracy, we tuned the values of
t
1 and
t
2 manually.
Results
Figure 5 shows the results for wood-leaf separation by the
geometric method, including the skeleton wood points and
the final wood points for each of the three trees. The results
for the magnolia tree and the virtual tree were first com-
pared with photographs taken during the leaf-off period.
No photograph of the camphor tree during leaf off is avail-
able, because it is evergreen. The leaf-off photograph of the
magnolia tree was taken in March 2014, and the picture of the
virtual tree was rendered using Maya
™
. A comparison of the
wood sections detected by the geometric method and those in
the photographs is shown in Figure 6. Careful visual inspec-
tion indicated that except for the twigs and fine fractions of
branches hidden in dense leaves, the first-, second-, and third-
order branches were detected with high accuracy.
The results obtained using the geometric method for the
camphor and magnolia trees were then compared with those
obtained using the intensity approach. Figure 7 shows the
results obtained using the intensity approach; the
t
1 and
t
2
values are those considered to be the best based on visual
inspection. Table 2 lists quantitative data for the wood-leaf
separation results shown in Figures 5, 6, and 7. The true wood
points and leaf points for the camphor and magnolia trees
were extracted carefully from the raw point clouds, and those
for the virtual tree were produced by scanning the wood part
and leaf part separately, using PBRT software. Note that a large
number of points with intensities in the range [
t
2,
t
1] were
omitted by the intensity approach. Nevertheless, the intensity
approach still had low accuracy compared with the geometric
method (Table 2), with the former having kappa coefficients
around 0.70 and those of the latter ranging from 0.80 to 0.90.
In the intensity approach, a number of leaf points lying at
the outmost part of the tree crown showed high intensity (Fig-
ures 7, 8, and 9) and were falsely classified as wood points.
Furthermore, a number of wood points lying inside the tree
crown had low intensities, and were falsely classified as leaf
points. The values of
t
1 and
t
2 had a significant effect on the
separation results, as shown in Figures 8 and 9; the quantity
PHOTOGRAMMETRIC ENGINEERING & REMOTE SENSING
October 2015
771
