International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences, Vol XXXV, Part B5. Istanbul 2004 
  
Figure 5: Skeletonization. Left: rasterized points; right: skeleton 
branches. As suggested by [Palägyi, 2003] this step is based on 
Dijkstra’s algorithm, a well-known method for finding shortest 
routes in a weighted directed graph (representing, for example, a 
road network). 
First, the graph is created. Its nodes are the voxels that par- 
ticipate in the skeleton, and any pair of adjacent voxels gen- 
erates two arcs between the nodes, one in either direction (see 
Fig. 6.B, but there each pair of arcs is represented by only one 
line). Arcs are assigned weights of either 3, 4 or 5, depending on 
whether the two voxels share a face, an edge or a point respec- 
tively [Verwer, 1991]. 
A ds - 
e 
e 
  
   
Figure 6: 2D illustration of skeleton segmentation. A. input 
skeleton; B. graph nodes and edges; C. spanning tree with short- 
est distances; D. segments and topology. 
Given such a graph, Dijkstra's algorithms finds the shortest route 
to a destination node (the root!) from all other nodes in the graph. 
In our application, the lowest voxel of the tree trunk typically 
serves as the destination. The collection of shortest routes leading 
  
from anywhere to the root forms a spanning tree of the graph. 
The term ‘tree’ in the graph-theoretical sense is not chosen by 
accident: the spanning tree that we find provides a logical model 
for a tree in a rasterized laser point cloud. Any ambiguities, such 
as loops caused by falsely-connected branches, which may still 
exist after skeletonization, are resolved now (Fig. 6.C) — how 
realistic the results are depends mostly on the success of previous 
steps. 
After the algorithm finishes, each node (except the root) knows 
its parent, the next node along the shortest route to the root. By 
traversing the tree once more it is easy to find branches and their 
junctions, being nodes (voxels) that appear as a parent more than 
once. During this traversal each voxel is assigned a unique branch 
identification number. Each time a junction is found, a new iden- 
tification number is given to this voxel and to the other voxels in 
the same branch closer to the root.(Fig. 6.D). 
3.5 Connected component labeling 
A problem occurs during skeleton segmentation (3.4) if the scene 
contains several (disconnected) trees. Dijkstra's algorithm needs 
to be provided with a single root voxel, after which it will find 
shortest routes only for voxels that are connected to that root. All 
other trees will be omitted. 
To overcome this problem, conncected component labeling has to 
be applied, followed by compenent separation (3.6). Connected 
component labeling uses a slightly modified segmentation algo- 
rithm, which scans the entire voxel space, starting at the bottom 
(i.e. at the plane with the highest number). Each time an unas- 
signed voxel is encountered, Dijkstra's algorithm is started with 
that voxel as root. One tree is then traversed and all voxels in- 
volved will be assigned a label, which is unique for that tree. 
After that, the algorithm continues to scan for unassigned voxels 
etcetera, until the top of the space is reached. 
This algorithm can be regarded a general 3D connected compo- 
nent labelling, since it does not rely on the input data being skele- 
tonized trees. 
3.6 Component Separation 
[n case of a scene with multiple trees, Connected Component La- 
belling (3.5) had to be applied to label the trees uniquely. Subse- 
quently, the data set has to be subdivided into several sets, such 
that each of these contains only one tree, which can than be seg- 
mented into braches, as described in 3.4. 
During the component separation step, components are sorted ac- 
cording to descending number of voxels and output into different 
data sets one by one. It may happen that certain components do 
not contain trees, but “loose” branches or other kinds of noise. 
The user may request that only a certain number of components 
is generated, or that only components with more than a certain 
number of voxels are considered. 
3.7 Raster tree segmentation 
At this stage the skeleton has been subdivided into trees and 
branches, and each skeleton voxel has been labelled with a unique 
branch identification. Now we will label all other tree voxels ac- 
cording to the nearest skeleton label. 
There would be several ways to accomplish this by raster 
operations, such as iterative dilation or distance transform 
[Borgefors, 1996]. We use a Nearest Neighbor search algorithm, 
as it is known from database environments, where the problem 
is sometimes to find & nearest neighbors (database records) of a 
given query record, in an vector space of arbitrary dimension. 
   
Intern 
Usual 
record 
tion; t 
ality. 
In our 
skelet 
(skele 
voxels 
Figure 
mente 
38 | 
Finall: 
all the 
to see 
order 
In a ra 
sen se 
algorii 
tools, 
Scene 
[Borg 
for 
der 
[Borg 
Ga 
me