tanbul 2004
STRUCTURING LASER-SCANNED TREES
USING 3D MATHEMATICAL MORPHOLOGY
Ben Gorte and Norbert Pfeifer
Section of Photogrammetry and Remote Sensing, TU Delft, Kluyverweg 1, 2629HS, The Netherlands
{b.g.h.gorte,n.pfeifer} @Ir.tudelft.nl
Commission V, Working Group 2
KEY WORDS: Laser scanning, Reconstruction, Forestry, Segmentation, Virtual Reality
ABSTRACT:
The task addressed in this paper is 3D modelling and reconstruction of (real world) trees on the basis of terrestrial laser scans.
To identify the structure of a tree in terms of stem and branches, an algorithm has been designed in 3D voxel space, based on a selection
of basic and advanced 2D raster (image) processing algorithms, transferred into the 3D domain. The selection includes filtering,
mathematical morphology, skeletonization, connected component labeling and shortest route computation.
1 INTRODUCTION
The purpose of the paper is to analyse point clouds of terrestrial
laser scans that are recorded inside a production forest. The pur-
pose is to reconstruct trees in 3D, in order to measure lengths
and thicknesses of the tree stem and of the main branches, to es-
timate the corresponding wood volumes. (In the remainder we
will not mention the stem anymore explicitely, but only speak of
branches).
Reconstruction of real world trees on the basis of terrestrial laser
scans allows to automate the estimation of forest wood mass for
valuation purposes. Also to make ecological assessments detailed
knowledge of tree structures is considered helpful in forestry.
Several authors report modelling from laser scans, but
these are usually made with airborne scanners and provide
rough estimates of tree canopies, albeit over large areas
[Pyysalo and Hyyppae, 2002, Sun, 2000]. Using 2D video and
2.5D laser pulse range measurements, [Clark, 2002] builds a 3D
model ofa tree stem by combining multiple vantage points. In our
paper we will build the model from 3D measurements directly.
Datasets were provided by the Institute for Forest Growth in
Freiburg, Germany. One plot (i.e. one location in a forest) is
captured by one or more positionings of the laser scanner. The
datasets are oriented relative to each other (i.e. registered). The
data is captured with Zoller+Frohlich laser scanners and provided
in the form of point clouds (sequence of (x,z, y)-triples).
A tree to be reconstructed is scanned from all sides by locating the
scanner at a number of viewpoints around the tree and merging
the resulting scans into a single point cloud. Because of the nature
of laser scanning, it may be expected that the coordinates of the
reflected points are located at the surfaces of the branches. Scans
are taken during the winter season when the trees are without
leaves.
At the final stage of the reconstruction process a cylinder fitting
process is carried out for each of the significant branches: a cylin-
der is fitted through those points that are at the surface of a par-
ticular branch. Before this is possible, however, it is necessary to
have a rough idea which points belong to that particular branch,
in other words to know the initial subset of points that should be
involved in the fitting process. This process itself will be able to
identify erroneous points (that do not fit) within the initial subset,
and possibly to add points to the subset that are in the vicinity and
fit on the same cylinder.
The crucial point in the above is to find the initial subset of points
for each branch. This is the problem addressed in this paper.
We are presenting an algorithm that subdivides (segments) a laser
point cloud of a tree into subsets that correspond to main branches
(those that have a significant amount of wood). Besides, points
that do not seem to correspond to any main branch are identified
as noise.
The algorithm segments a point cloud according to branches and
at the same time identifies how the branches are connected to
each other. As a result, a "tree" data structure is constructed,
which represents the topology of the branches within a tree.
Basically, the task of the algorithm boils down to detecting elon-
gated, cylindrical structures in a point cloud. However, in general
point cloud segmentation can be considered a difficult subject, es-
pecially in presence of the before-mentioned noise, in addition to
gaps within branches (missing points, e.g. caused by occlusions
by other branches) and varying point densities (as a result of vary-
ing distance from the scanner). To establish the topology between
branches on the basis of point clouds is an unsolved problem as
well.
Therefore we decided to perform this part of the analysis in the 3-
dimensional raster domain. Connectivity and neighborhood rela-
tions between voxels in a 3D raster can be established much eas-
ier than between the original (x,y,z)-points, using morphologi-
cal operations, which are well-known from 2D image processing.
Their extension to the 3D raster domain is described here. When
defining connectivity in 3D, a choice has to be made between
6, 18 and 26-adjacency, depending on the number of voxels that
are considered neighbors of a voxel: only those with a common
face, also those with a common edge, or even also the ones with
a common corner.
The 3D reconstruction is done in several steps. After converting
the point cloud to 3D raster, closing and opening are applied to
close gaps and holes, and to remove isolated points, respectively.
Next, 3D skeletonisation is applied, which (temporarily) reduces
the stem and branches to single voxel thickness. Then, Dijk-
stra's minimum spanning tree algorithms ensures that the skele-
ton from the previous step becomes a tree in the data structuring
sense. Topology can now be established, in which the stem and
the braches obtain unique IDs. Finally, 3D distance transform is
applied to assign to each point in the original set the ID of the
nearest branch. As a result, the points are grouped by ID accord-
ing to the tree structure.
Summarizing, the reconstruction process has two phases:
