— doccomp
onents
compnbr) |
trees
resent pro-
nding rou-
number of
plution and
es (respec-
is useful to
irround the
see below)
dinate sys-
ing require-
tree should
that can be
With a too
ar that may
International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences, Vol XXXV, Part B5. Istanbul 2004
cause problems later. When the resolution is too coarse,
on the other hand, it will happen many times that several
laser points get transformed into a single voxel. Then, these
points are indistinguishable in the voxel space and details
like small branches may be lost. Furthermore, different
branches (or trees) may get connected, i.e. pass through the
same voxel or through neighboring voxels. This may cause
errors when building topology in a later stage. It should
be noted that the laser point density decreases with the dis-
tance to the scanner, and therefore is not uniform over the
3D space. This further complicates the choice for an opti-
mal resolution.
Space and time: The number of voxels in a 3D raster increases
with the 3rd power of the resolution (when expressed
in voxels/distance) and may easily become impracticable
when resolution is chosen too fine. Memory capacity prob-
lems may occur in software that needs random access within
the 3D space. Smart implementations might prevent this sit-
uation in many cases, but not always. Moreover, processing
times usually increase with the 3rd power of the resolution
as well.
During experiments, resolution between 2 cm and 5 cm were
used. 2 cm seems to preserve the details of the tree accurately
enough, although this should be further investigated.
According to the laser scanning model, laser points occur on the
surface of objects (trees). After rasterization, only voxels that ae
intersected by the tree-air surface will have non-zero values. The
actual voxel value assigned is the number of points falling inside
the cube in (x,y,z)-space corresponding to a voxel. Therefore, a
voxel value can be regarded as a point density measure.
3.2 3D neighborhood operators
After transferring the laser points to a 3D raster, neighborhood
operators are applied to enhance the data. The neighborhood op-
erators are 3D extensions of 2D raster operators, such as linear
filtering (convolution), distance transforms [Borgefors, 1996],
[Svensson and Borgefors, 2002] and mathematical morphology
[Serra, 1985].
The purpose of enhancement using neighborhood operators is
threefold:
Noise reduction: In the context of tree reconstruction, isolated
laser points, or isolated small groups of adjacent laser
points, can be considered noise. Neighborhood operations
are able to reduce this kind of noise.
Repairing gaps caused by occlusions: The software provides
morphological dilation and erosion with user-defined struc-
turing elements (Fig. 3). Closing (dilation followed by ero-
sion) is used to fill small holes and gaps between laser
point, which may be caused by branches occluding other
branches. The maximum size of the holes and gaps that can
be repaired in this way is controlled by the structuring el-
ement size, and is also related to the chosen resolution in
the previous step. By using different shapes of structuring
elements it is possible to indicate a preferred direction for
the closing, for example to connect points above each other
rather than points at the same height.
Filling ‘hollow’ trees: Laser points are located on tree surfaces
rather than inside trees. Initially, trees are hollow. How-
ever, we are going to extract the skeleton (see 3.3), allow-
ing to reveal the topology within the tree. Hollow trees
have to be filled, by a second morphological closing (Fig.
4). The structuring element size is given by the maximum
trunk thickness expected in a given raster resolution. The
Figure 3: 3D Filter kernels and structuring elements
structuring element should be oriented horizontally, since
filling is needed mostly in the (vertical) trunk.
This should work well when points are located completely
around the tree, as was the intention of recording the scene
from four different viewpoints. This would also reduce the
above-mentioned occlusion problems. Unfortunately, the
four datasets from the different scanner positionings could
not be properly co-registered. Therefore, they had to be
processed one by one, which limits the application of this
hollow tree filling method.
Figure 4: 2D illustration of dilation and erosion to fill *hollow?
trees. From left to right: input cross-section; dilation; erosion;
filled cross section.
3.3 Skeletonization
The next step in tree reconstruction is skeletonization, the reduc-
tion of the thickness of tree trunks and branches to one voxel.
After that, it will be possible to identify different branches and
reveal topological relations between them.
Skeletonization is done by iteratively removing voxels from the
outside of objects, up to the point where only a single-voxel
wide linear structure is left. Strictly speaking, this is line skele-
tonization, which is to be distintuished for surface skeletoniza-
tion, where volumes to are reduced to surfaces of single-voxel
thickness. At that point, removal of one more voxel would cause
a branch to break (be separated into disconnected parts), assum-
ing 26-adjacency.
Skeletonization has been a difficult problem in 2D and even
more so in 3D, but nowadays various solutions can be found
in literature [Borgefors et al, 1999], [Lohou and Bertrand, 2001],
[Palágyi et al, 2001], [Telea and Vilanova, 2003]. Skeletoniza-
tion algorithms iteratively ‘peel’ layers from the outside of ob-
jects, and some approaches can be subdivided according to the
number of subiterations within each iteration. This number can
be 6, 8 or 12, depending on whether a cubic object to be skele-
tonized would be 'attacked' from the faces, corners or edges,
respectively. For this project we implemented an 8-subiteration
method, described by [Palágyi and Kuba, 1999], which shows ex-
cellent performance.
3.4 Skeleton segmentation
The next step finds the structure of the tree as represented by
the skeleton, in terms of branches and junctions that connect
