Istanbul 2004
ee trunk in a
parent and its
here shadows
1k caused oc-
tic deviations
le cylinder, 3:
m.
n distance) to
linder fitting.
ordance with
ng continues.
nother (e.g. a
er can be used
ers, but given
be set easily.
ss, the curva-
is, and finally
e selection of
termined em-
dge of forest
; in the forest
e cylinder can
'er curvatures
et to 30% of
to the curved
forward shifts
set similar to
tter results. If
(100%, ...),
ibles the good
' is stopped in
:d for the next
irection to the
:hieved with a
uter distance.
ting accuracy.
ised for fitting
.g. 10094), the
, too, because
e.g. 10cm for
International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences, Vol XXXV, Part B5. Istanbul 2004
ur
i
i
i
1
i
J
i d
i
i
Figure 3: Measure of alignedness: The distance between two
segments a and b is the mean distance of the distance of the start
and end point of either segment to the line carrying the other
segment (dotted lines). The three examples on the right side are
used to demonstrate properties of this distance measure.
Deciding if the cylinder fit is successful, is based on the r.m.s.e.
of the fit (3cm), on minimum and maximum radius of the cylinder
(5cm-50cm), maximum allowed angle deviation between con-
secutive cylinders (e.g. 3°), maximum allowed radius change in
percent (e.g. 2.5%) and maximum allowed percentage of points
within the cylinder, diminished in radius by 3o (594). Other pos-
sible measures would include checking the angular distribution of
points on the cylinder skin.
3.5 Segmentation
The algorithm of cylinder following requires a starting point in
the given point cloud which lies approximately on the branch
surface and approximate values for the cylinder axis direction, the
algorithm for cylinder fitting requires a set of points of which all
points are supposed to lie on one cylinder. Apart from segmenting
the point cloud manually into branches, and thereby choosing the
relevant branches, this can also be done automatically. (Gorte and
Pfeifer, 2004) describe a method for transforming the point cloud
into voxel space, filling the empty spaces inside the branches
with mathematical morphology (closing), and skeletonizing this
tree. Each skeleton voxel belongs to one 3D curve, representing
a branch in object space. The original point cloud is segmented
based on distance to these 3D curves in voxel space.
3.6 Clustering aligned cylinder axes
The cylinder following provides a number of cylinders, more
precisely a start and an end points and one radius for each pair
of axis points. This can be performed for many datasets, i.e.
different positionings, and for many trees within one dataset. As
mentioned above, precise registration of different scans can pose
à severe problem in forest environments, and in these cases it
makes sense to combine not the (poorly registered) point clouds,
but results ona later processing stage. An exemplary shift of 10cm
between two scans will make the cylinder fitting impossible for
the combined point cloud, but merging two stems which are 10cm
shifted apart, will still give reliable and improved results of the
radius. In order to combine the results from multiple runs of
the cylinder following within one plot, the computed axes are
combined to form individual ‘trees’. A tree is in this sense a
collection of branch elements that are aligned along each other.
For this, a measure of alignedness needs to be defined.
Given are two axes, i.c. two lines in 3D space, a and b, and a
start and an end point forming a segment on either axis, S, and
E, for axis a and Sy and Ey for axis b (see Fig. 3). The distance
d(S,, E,, Sy, E) between those two segments is defined as
d(Sa. Eu: So, Eu) = = (8.0 + Eb + Spa + Epa) (3)
1
1 |
with P/ denoting the (shortest) Euclidean distance between point
P and line l. For two segments on the same line the distance is
zero. For two segments on parallel lines the distance is equal to
the distance of the lines. For intersecting segments, the distance
grows with the length of the segments and their angle. For inter-
secting or skew lines, the distance also grows with the distance of
the segments. This means that two short segments at — more or
less — the same location but with different axis direction are still
close to each other. It is noted that this measure is not a metric,
because the triangle inequality is not fulfilled. However, this mea-
sure is invariant to congruency transformations. Additionally, the
measure is given in length units (i.e. in meters).
The algorithm for finding sets of aligned segments is a global
algorithm and computes the distance between every pair of seg-
ments. All segments, which have a distance below a threshold
value (e.g. 30cm) are considered neighbors to each other. This
threshold has to be set with the expected registration error in
mind. The grouping of aligned segments begins with choosing
the segment which has the highest number of neighbors within
this distance. In case there are multiple segments with the same
highest number of neighbors, the one segment is chosen, were the
largest distance to a neighbor is smallest. All the neighbors of this
segment form a group and are removed from the set of segments.
Then the procedure is repeated, until no segments can be grouped
anymore.
3.7 Computing continuous branch models
From applying the above algorithms of cylinder following and
possibly aligning of axes, a set of start and end point pairs with
associated radius is determined to describe one branch. These
sets are used to determine a model of a branch that is geometri-
cally continuous of order one (continuous tangent planes, yielding
smoothness). Note that the collection of cylinders obtained so far
is not even a continuous model of the branch.
To compute these improved branch models, the two end points of
all cylinders are parameterized according to their position on a 3D
line. It is sufficient to take the average direction of the individual
axes as the direction of this parameterization axis, weighting each
with the length of the segment. Each cylinder end point provides
one observation of the radius along this line.
Different models can be fitted to these observations. Assuming a
linear decrease of the radius (e.g. with height) an adjusting line is
fitted to the radius observations, parameterized over the 3D line.
Alternatively moving least squares (Lancaster and Salkauskas,
1986) can be applied to get a smooth model of radius change with
branch extent.
3.8 Hull determination
Leaf trees can be scanned for crown reconstruction ideally in the
winter half year when they bear no foliage, whereas the crowns of
coniferous trees are opaque for the laser scanner the whole year.
Therefore very little points are measured on the upper trunk.
Additionally, the separation of needles and branches in the point
cloud is even visually very hard. In Fig. 4 a detail of a scan from
a pine (one branch) is shown. For these reasons, an alternative is
necessary to determine the extent of the trec, given in the form of
an outer hull. Given the irregular structure of trees, this hull is
naturally far from being convex.
