251 
In: Wagner W., Székely, B. (eds.): ISPRS TC VII Symposium - 100 Years ISPRS, Vienna, Austria, July 5-7, 2010, IAPRS, Vol. XXXVIII, Part 7B 
for each inventory plot based on the nDSM and LIDAR points 
(Straub et al., 2009). Further, field work was conducted for plot 
establishment and measuring coordinates. Coordinates of center 
point and four comers of each rectangular plot were measured. 
Some other parameters like azimuth and distance from the 
middle point of each sample plot to sampling tree inside the plot 
were also taken. Tree coordinates were then derived using the 
azimuth and distance from the center point of each plot using 
compass and tape. 
3.3 LIDAR Data and Pre-processing 
Full waveform laser scanner data of density (16 points m' 2 ) was 
acquired during August 2007 by TopoSys GmbH using the 
Riegl LMS-Q560 system. Important flight and system 
parameters are given by Straub et al. (2009). Both the raster 
terrain and surface models of 50 cm resolution were calculated 
using the LIDAR raw point clouds. An ‘Active Surface 
Algorithm’ implemented in the "TreesVis" - software for 
LIDAR data visualization and analysis, was used for data 
filtering and surface interpolation (Weinacker et al., 2004). A 
normalized digital surface model (nDSM) was derived by 
subtracting the digital terrain model (DTM) from the digital 
surface model (DSM) using "TreesVis" software. Raw full 
waveform LIDAR points were normalized using the DTM to 
ensure the absolute height of the object and to eliminate the 
influence of the terrain. Thus, obtained normalized raw data was 
further used in the main process for clustering. 
3.4 Orthophoto Characteristics 
RGB/NIR Optical data were collected by TopoSys GmbH in 
July 2008. Important flight and technical parameters of the 
RGB/NIR line scanner are given by Straub et al. (2009). The 
individual flight strips were rectified and georeferenced with the 
aid of DSM, which was filtered from ALS data (6-7 points m" 2 ) 
acquired at the same time with the optical data. Orthophotos 
were computed by the data provider and were delivered at 25 
cm spatial resolution. 
3.5 Data Processing 
3.5.1 Clustering by Modified ¿-means: The ¿-means treats 
each observation in the input data as an object having a location 
in the space. The objective of ¿-means algorithm is to minimize 
the total intra-cluster variance or the squared error function. In 
the algorithm, the sum of absolute differences between each 
point and its closest centre in Euclidian 3-D space is minimized. 
Each centroid is the mean of the points in that cluster. It is also 
advantageous to implement ¿-means since it uses the actual 
observations of the objects (rather than the larger set of 
dissimilarity measures), and not just their proximities unlike the 
hierarchical clustering based approaches (Gupta et al., 2010). 
The ¿-means algorithm was supervised to use the local maxima 
as external seed points to initialize the iteration, instead of 
selecting it randomly by the user, as in the case of Ko et al. 
(2009). This was done because finding the pattern of individual 
tree in natural forest conditions is very difficult by selecting ¿ 
clusters randomly using the simple ¿-means algorithm. Another 
advantage of avoiding trial and error based simple ¿-means 
approach is saving of machine memory and total run-time. The 
performance of the algorithm was improved by reducing the 
height value of the data points and external seed points by a 
half. The reason behind the reduction of height value is that it 
brings the normalized raw points as well as seed points closer in 
z-dimension and minimizes the intra-cluster variance. Thus, it 
fulfils the sole objective of the ¿-means. The reduction of the 
height to half was found empirically with trial and error based 
approach and have been kept constant for all the 7 plots studied. 
3.5.1.1 Extraction of external seed points and 
filtration of unwanted seed points: Local maxima points were 
extracted as external seed points above 5 m height from the 
nDSM image having a gray value larger than the gray value of 
all its 8 neighbors. To avoid the overflow of seed points, the 
points that were too close to each other were filtered out based 
on threshold distance. The filtered local maxima as external 
seed points in the ¿-means algorithm were finally used. The 
threshold distance, varied depending on the forest conditions. 
The plot dominated by mature or old trees requires higher 
thresholds distance because local maxima from smaller peaks 
will most likely represent only branches, hence needs to be 
eliminated. Local maxima from a younger tree’s peak will most 
likely to be a treetop, hence, need smaller threshold distance. 
The value of threshold distance for younger trees with single 
and narrow crown at the tree top was found as approximately 2- 
4 m (plots 2, 5 and 6) without any smoothing. While threshold 
distance for trees with relatively older ones having wider crown 
with more intermittent peaks at the tree top was found as 4-6 m 
(plots 1, 3, 4 and 7) with no smoothing. However, this also 
varies from dominant tree types. 
3.5.1.2 Modified ¿-means algorithm: The modified k- 
means algorithm applied to a set of 3-D vectors in the form of 
pseudo-code is given as follows. 
(i) Select normalized 3-D LIDAR points and external seed 
points above certain height (for example, above 5 m) 
(ii) For all the external seed points and that of the normalized 
LIDAR points, z = z*0.5, before initialization of the algorithm 
(iii) Set i = 1 
(iv) Select external seed points as a set of k means Cj(l), C 2 (1), 
..,C¿(1), where i = 1 in this case (mean vector for each cluster 
centre) 
(v) For each vector x„ begin computation D (x,-, C k (i), for each i 
= 1, .., k) and assign x,- to the cluster Cj with the nearest 
Euclidian distance in 3-D space (means) 
(vi) i = i++ and update the means (C y ) to get a new set Ci(z'), C 2 
(0, .-,0(0 
(vii) Repeat steps (iii) to (v) until Qfz) = C*(/ + 1) for all k 
(viii) For all the external seed points and that of the normalized 
LIDAR points, z = z/0.5 
3.5.2 3-D Reconstruction of tree clusters: Once the tree 
clusters are generated, each cluster is reconstructed in 3-D space 
using the QHull approach (Barber et al., 1996). QHull is a 
general dimension code for computing convex hulls using 
Quickhull algorithm (Berg et al., 1997). Each 3-D tree crown 
cluster is constructed with triangular surface as a 3-D convex 
polytope. The convex hull of a set of points is the smallest 
convex set containing those points. For detailed introduction 
with example codes, see the book by O'Rourke (1994). The 
main advantages of Quickhull are its output of performance 
sensitivity (in terms of the number of extreme points), reduced 
space requirements, and floating-point error handling. Thus, 3- 
D convex polytope each tree crown is shown as a 3-D object 
with a triangular surface in the case of 3-D convex polytope. 
The shape of each polytope is the representation of the 
respective tree species.