he geometric
h and similar
anning in the
es are locally
are captured.
je entire tree.
heights is an
' the different
the irregular
ching), which
the often poor
of terrestrial
- independent
-, capable of
rfaces is now
nstruction of
canning data.
ular structure
ection 2.1 the
n Section 2.2
collection of
section 3. In
vironment
e information
h, and ii) the
ward manner
he branches),
in forestry.
econstruction
aser scanning
t time (a few
on the surface
er. In Fig. 1a
point density
less and less
1adow effects
age of higher
ie. chances of
adius. There-
ill be covered
Figure 1: Point cloud of one scan. To improve visual appearance,
the point cloud has been thinned out by averaging points in a
10x10x10cm® raster. The scanner was positioned on the right
side of the image in the background (not shown), yielding a view
on the inner side of the trunks.
less dense with “laser points”, making reconstruction in the above
described manner difficult or even impossible. The evergreen fo-
liage of coniferous trees can be very dense and presents another
difficulty. A view to the tree top becomes almost impossible. An-
other difficulty in scanning trees is caused by the wind. It makes
branches move, again depending on their size, but small branches
can move a few centimeters (e.g. 5cm) given only a light breeze.
Finally, onc last problem is the registration (relative orientation) of
scans from different positions to each other. The ICP algorithms
(Besl and McKay, 1992) or variants for orienting two scans to
cach other require that the same object is covered in both scans.
Due to shadow effects this overlapping coverage is naturally given
only at the trunk. This allows for horizontal alignment in the trunk
region but rotation around the vertical axis and positioning along it
remain problematic. As there are no natural tie-points (no natural
sharp corners), artificial targets have to be used as tie-points. In
planimetry it is possible to spread the tie-points over the complete
scene, but due to practical limitations it is very difficult to place
tie-points higher than e.g. 3m. This leads to an extrapolation of
orientation information in the zenith direction.
Summing up, the environmental conditions under which the mea-
surements are performed, cannot be controlled well, rendering the
reconstruction of a tree with all its branches from laser scanning
data a difficult, if not impossible task. Thus, an alternative recon-
struction method will be presented as well, not giving information
on individual branches, but aiming at reconstructing the outer hull
of a tree.
2.2 Reconstruction methodology
The principle idea exploited in the reconstruction is that branches
are described as right circular cylinders. This model deviates from
reality in two aspects. First, the cross-section is in most cases not
circular, but of a more general form. Branches growing sideways
115
International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences, Vol XXXV, Part B5. Istanbul 2004
tend to have a more elliptical cross-section due to gravity, while
other influences, e.g. wind, make the cross-sections even more
complicated. Second, the axis of a branch is not a straight line,
but curved. This already shows, that modelling of trees is a
challenging task. The choice taken here was to — first — ignore
the deviation of the cross-section from the circular form, and —
second - to fit cylinders piecewise to branches, so that the cylinder
axis can adopt locally to a curved branch. The first decision was
also influenced by the low point coverage of branches, typically
only 50% or less of a cross-section is covered with points, and
by the expectation that a fewer number of parameters would be
easier to estimate from the data. The second decision of piecewise
approximation allows to fit multiple cylinders to one branch, cach
in a restricted area. Approximation values from one branch to the
next can easily be generated, if these areas are made to overlap.
As mentioned above, especially for coniferous trees the recon-
struction of an outer hull is needed. Choosing a convex hull is
not a good choice, because it contradicts to the behavior of trees.
Environmental forces, e.g. competition with neighboring trees
for sunlight, lead to different horizontal extents of the foliage in
different levels. The methodology applied here is that the outer
hull is reconstructed slice-wise for horizontal levels. In these dif-
ferent height levels the recorded points on the foliage determine
the circumference of the hull.
3 ALGORITHMS FOR TREE RECONSTRUCTION
In the following a collection of algorithms is presented which are
used for the tree reconstruction.
3.1 Normal estimation
For each given point its surface normal vector provides additional
information that can be used in the subsequent steps. Assuming
that the point coverage on the measured surfaces is dense enough,
the normal vector can be estimated from the point and its nearest
neighbors. We used the k nearest neighbors (ANN, 2003) to each
point and fit a plane to these points by minimizing the sum of
squares of orthogonal distances between the points and the plane.
The normal n is the eigenvector to the smallest eigenvalue A, of:
TP Ut Sf
Ami od ed ()
A‘ An = An,
Xk EL Zk
The values zi, yi, Zi are the coordinates reduced to the barycenter
of the k points. The r.m.s.e. of this adjustment is \/As/(k — 3)
(for a proof see e.g. (Shakarji, 1998)).
The value k was set to 40, and given a minimal point spacing (in
one scan) of 3mm, this corresponds to an area of 2cm diameter.
Naturally, point coverage gets lower in higher parts of the tree,
corresponding to bigger areas used for normal estimation. An
average fitting accuracy below 2cm was achieved for points on the
tree surface. This value is larger than the measurement accuracy
of the laser scanner used, because of the roughness of the trees.
3.2 Removal of *wrong' points
During the normal vector computation for the given points filter-
ing of points can be performed simultaneously. Single measure-
ment errors typically lead to points ‘hanging’ in mid-air without
neighbors in close proximity. This can be caused, for example,
by measuring ranges to surfaces outside of the uniqueness range
