In: Wagner W., Szekely, B. (eds.): ISPRS TC VII Symposium - 100 Years ISPRS, Vienna, Austria, July 5-7, 2010, IAPRS, Vol. XXXVIII, Part 7B 
253 
Tree species 
R Tree % 
E Tree (E+NE) % 
Scots pine 
13.9 
86.4 
Norway spruce 
2.2 
42.9 
Douglas fir 
1.6 
60.0 
Hornbeam 
9.5 
66.7 
Cherry 
23.7 
40.0 
Oak 
24.3 
45.5 
Red Oak 
0.9 
33.3 
European Beech 
21.1 
47.8 
Black Locust 
0.6 
100.0 
Linden 
0.9 
33.3 
Silver Birch 
0.3 
100.0 
Sycamore Maple 
0.9 
33.3 
Table 5. % distribution of‘Exact’ (E) +‘Nearly Exact’ (NE) tree 
tops together and corresponding reference tree tops (R_Tree). 
The species-wise distribution of the two accuracy determining 
validation classes (E+NE) gives a meaningful insight while 
assessing the accuracy. It is evident from Table 5 that the higher 
fractions of acceptable tree tops were detected for the evergreen 
Scots pine (86.4%). The detection of‘Exact’ and ‘Nearly Exact’ 
tree tops is for few minor deciduous species like Black locust 
and Silver birch is highest (100%), while that of the other minor 
deciduous species like Red oak, Linden and Sycamore maple 
are 33.3% each. Average detection of ‘Exact’ and ‘Nearly 
Exact’ tree tops were found for the two other minor evergreen 
species, Norway spruce (42.9%) and Douglas fir (60%). 
Acceptable tree tops (E+NE) for Oak, Cherry, European beech 
and Hornbeam, which are the four major deciduous tree species 
in the study plots, are 45.5%, 40%, 47.8% and 66.7%, 
respectively. An overall 57.4% of trees were automatically 
detected together in the ‘Exact’ and ‘Nearly Exact’ validation 
class among the 7 test plots by applying the modified k-means 
algorithm. It is clear from the Table 5 that modified algorithm 
yielded higher amount of ‘Exact’ (E) and ‘Nearly Exact’ (NE) 
tree tops for evergreen coniferous trees despite the fact that it 
constitutes only 17.7% of total tree cover among all the 7 study 
plots. The percentage fraction of the sum of the tree top points 
in ‘Exact’ and ‘Nearly Exact’ validation classes among all the 7 
test plots for the evergreen coniferous and deciduous trees are 
78.6% and 47.1%, respectively. More than 80% Scots pines 
were detected in all the study plots by applying the algorithm. 
This may be due to their dominance in the upper canopy layer. 
By applying supervised ¿-means approach, the number of trees 
to be extracted was decided by the number of external seed 
points used during the initialization of the ¿-means, which, in 
turn, is dependent on the distance threshold. During the 
investigation, it was found that the distance threshold is a forest 
dependent parameter. For example, the plot dominating with 
trees of wider canopies requires higher distance threshold 
because local maxima from smaller peaks will most likely 
represent only branches, hence needs to be eliminated. Whereas, 
local maxima from a peak in a plot containing trees with small 
canopies will most likely to be a treetop, hence requires 
comparatively smaller distance threshold. 
Approximate shape of the individual tree crown was represented 
in the form of 3-D convex polytope. The convex polytopes were 
computed from the delineated clusters using QHull approach 
(Barber et al., 1996). Two examples of European beech and 
Scots pine from plot 6 containing clusters and the respective 3- 
D convex polytopes have been represented below in Figure 6 
and 7, respectively. The European beech and Scots pine in the 
given examples are roughly 17 m and 26 m in height. The 
canopy cover and density played a vital role in computing the 
geometrical shape of the two tree species. 
Figure 6. Cluster and convex polytope of a European beech 
Figure 7. Cluster and convex polytope of a Scots pine 
5. CONCLUSIONS 
Traditional ¿-means generates arbitrarily bad grouping of 
objects due to random seed selection procedure and repeated 
run of the algorithm after cluster analysis to meet the fitness 
criteria. The algorithm yields comparatively fair results by 
partitioning the LIDAR data after seeding is done externally and 
the height value of the LIDAR points are scaled down to half 
before initialization of the process (Gupta et al., 2010). There is 
an obvious advantage of the modified approach over the simple 
¿-means or hierarchical based clustering (Gupta et al., 2010) or 
other approaches using ¿-means for single tree extraction by 
other investigators (Morsdorf et al., 2003; 0rka et al., 
2009).The formulation of validation method and classes were 
crucial in determining the accuracy. 
The multi-tier, mixed tree species distribution with varying age 
groups, low crown diameter and dense canopy closure were big 
challenge for the algorithmic performance in single tree 
extraction for different tree species. The average producer’s and 
user’s accuracies among all the plots are 55.7% and 41.3%, 
respectively. From Table 4 it is evident that the performance of 
the algorithm is average in such forest conditions. It was 
observed that higher accuracies are tending to occur if the trees 
in plot are at nearly same height and when there are fewer tree 
species, as in the case of plot 6. The results show that the 
algorithm for the upper tier trees worked better as compared to 
the trees lying beneath it. Further algorithmic improvement and 
more investigation in varying forest conditions will be done to 
obtain better accuracies in the future.