1. Segmentation of laser points into the tree stem and major 
individual branches (and at the same time removal of points 
that do not belong to these tree elements). This phase is 
executed in the 3D raster (voxel) domain, and is described 
in detail in this paper. 
N 
Fitting of 3D geometrical primitives, e.g cylinders, to the 
segmented point sets. This takes place in the (x,y,z) 
point cloud domain, where points are labeled on the ba- 
sis of the results in the first phase. It is described in 
[Pfeifer and Gorte, 2004]. 
2 VOXEL DOMAIN 
Analysis for tree reconstruction from terrestrial laser point clouds 
described in this paper is performed in the 3-dimensional raster 
domain, which is a discrete 3-dimensional space with elements 
called voxels. 
Conceptually, a 3D raster data set records voxel values only, since 
the voxel locations are defined implicitly by the position of a 
voxel in the data set. This is in contrast to a vector data set, where 
point locations (coordinates) are recorded explicitly, in addition 
to values and other kinds of information, such as topology. In 
our implementation, however, voxels with value 0 (usually the 
vast majority) are not stored on disk, which in turn requires that 
locations of non-zero voxels are stored explicitly. 
Within a 3D raster different 3-dimensional phenomena can be 
represented, with different meanings attached to voxel values. In 
the simplest raster representation of laser points the voxel value 
range may be limited to 0 (this voxel is empty) and I (it contains 
laser points). 
The overall purpose of raster processing during tree reconstruc- 
tion is to segment the set of points into different trees (if appro- 
priate), and within trees into different branches. At the end of this 
phase, therefore, each point will have obtained a unique branch 
identification number. In addition, topological information, de- 
scribing how branches are connected to each other in terms of an- 
cestors and descendants, will become available during this phase. 
3 ALGORITHM 
The algorithm has the following steps (Fig 1): 
1. Point cloud to 3D raster conversion 
3D neighborhood operations 
Skeletonization 
+ 1e 
Skeleton segmentation 
Connected component labelling 
Cn 
6. Component Separation 
7. Raster tree segmentation 
8. Point cloud segmentation (in the continuous domain) 
3.1 Point cloud to 3D raster conversion 
During this step a 3-dimensional raster space is created and all 
the laser points are transformed to voxels in that space. The most 
important parameter is spatial resolution, which denotes the size 
of a single voxel (in meter). This is the step size that is used for 
quantization of the 3D space. 
The 3D raster space is subdivided in planes, lines and columns. 
The location of a voxel is defined by a (p,1,c) coordinate triple, 
  
  
   
  
  
  
    
   
    
    
   
     
   
  
   
  
  
   
  
   
  
  
  
  
   
   
  
  
  
  
   
   
   
   
   
    
    
  
    
   
  
  
  
  
  
  
  
  
  
   
     
     
  
  
  
  
  
    
International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences, Vol XXXV, Part B5. Istanbul 2004 
points.xyz 
preselected point 
  
  
  
  
   
   
    
  
  
  
  
  
  
cloud (x,y,z) 
INF.INF 
i | 
makeplc | Header | 
au 7 | info | 
points.plc skeleton.plc 
| rasterized points skel3d — skeleton |. doccomp 
(p.l,c value) | (p.L6,1) 
| vi cc.pic 
filter connected 1 
components | 
segskel.plc ,c,compnbr) | 
SC ntresitilesitmhmaneibia deal : 
| je 
donear | skeleton : | 
[tete segnes | septrees 
segpoints.pic 
segmented raster- 
dolabel ized points 
| (plesegnbr) — | treel.plc 
: single tree 
segpoints.xyz skeleton | |]. 
segmented point (ple) || | 
cloud - J 
X,y,z,segnbr l e bs 
(xy gooey treeN.plc 
  
  
  
Figure 1: Raster processing work flow. The arrows represent pro- 
cessing steps, labelled by the names of the corresponding rou- 
tines. 
where p, / and ¢ are integer numbers [0, 1,2,...]. The number of 
planes, lines and columns depends on the chosen resolution and 
on the minimum and maximum z, y and x-coordinates (respec- 
tively) that occur in the laser point cloud (Fig. 2). It is useful to 
specify the thickness of a layer of empty voxels to surround the 
whole block, to ensure that neighborhood operators (see below) 
do not expand outside the voxel space. 
columns 
lines 
  
   
  
  
Figure 2: Voxel space with (x,y,z) and (p,/.c) coordinate sys- 
tems 
The choice of a suitable resolution is based on conflicting require- 
ments, concerning: 
Laser point density: Points belonging to a single tree should 
form a connected set of voxels — or at least a set that can be 
made connected in subsequent processing steps. With a too 
fine resolution (small voxel size), holes will appear that may 
Inte 
Spa 
Dur 
use 
eno 
Acc 
surf 
inte 
actu 
the 
VOX! 
32 
A ftc 
ope 
erat 
filte 
[Sve 
[Ser 
The 
thre« 
Noi: 
Rep 
"illi