ISPRS Commission III, Vol.34, Part 3A ,,Photogrammetric Computer Vision", Graz, 2002 
  
An n-dimensional case 
In laser scanning applications, we find a simple n-dimensional 
example. Some laser scanners measure not only the range, but 
even radiance. This data can be considered in PCA as a 4-th 
dimension, and used by aggregation criteria exactly as the first 
three dimensions. One can find a lot of other examples in image 
processing. 
ALGORITHMS 
In this section, two different algorithms that combine region 
growing techniques and principal component analysis are 
presented. PCA is used to define the aggregation criteria and to 
describe the geometrical properties of the objects. 
The strategy implemented for object detection and 
segmentation is based on range data only, and was tested on an 
airborne laser scanner data set. The result was obtained by 
working on raw data, so we were able to take advantage of the 
full resolution potential of laser scanning. 
The two algorithms differ in PCA and in aggregation criteria, 
but they use the same hierarchic region growing technique. 
Algorithm 1 
This algorithm is based on descriptor mapping; one or more 
properties are calculated and mapped for every point in the data 
set. Then the algorithm perform the region growing with 
reference to the property map, and mark as terminal point those 
points in which is located a peak value. Is also possible to map 
different properties and compare the results. The algorithm 
performs the following steps: 
A. Calculates the descriptor for every point p; in the data set 
(descriptor mapping): 
l. atthe point p; searches a neighbourhood for other points; 
2. calculates the second order moments using the 
neighbouring points; 
writes the second order symmetric tensor at the point p; ; 
4. calculates the three real eigenvalues and the related 
eigenvectors; 
5. calculates the descriptor value (for example total static 
moment) at the point p; in the reference system defined 
by the three eigenvectors; 
6. writes the descriptor on file. 
B. Starts region growing: 
l. extracts a seed and places it in level 1 of the tree 
structure; 
2. searches a spherical neighbourhood for other points; 
3. sorts neighbouring points in function of their Euclidean 
distance from the seed; 
4. searches the distance from seed of the descriptor peak 
value, and sets d,,,, equal to this distance; 
5. marks peak value as terminal point of the tree structure; 
6. aggregates the points with distance from the seed less 
than dax and places them in level 2 of the tree; 
7. grows the region by adding neighbouring points that 
match aggregation criteria until all the branches reach a 
terminal point; 
8. when the growth of the first region stops chooses 
another seed point which does not yet belong to any 
region and starts again. 
Let’s consider the phase A, in wich the algorithm performs the 
descriptor mapping. Note that the tensor is centrated in the 
point p;, not in the centre of mass! This is beacause we need to 
calculate the value of descriptor at the point p;. 
Ww 
A- 292 
The phases B.3-6 are typical of this algorithm and solve in a 
simple way, using the non-parametric threshold value d,,,,,, 
the problem of stop growing at discontinuities. 
Time of work is 9(2n) , that is 9, (n) for descriptor 
mapping plus 9, (n) for region growing. 
  
  
  
  
  
  
  
Figure 4 — Segmentation results on a test area of 25:25 m. In 
(A) region growing was performed with a distance criterion 
only. In (B) was used the algorithm 1 and the total static 
moment as descriptor. TopoSys data set. 
Algorithm 2 
This algorithm uses PCA only in region growing 
aggregation criteria and don’t performs descriptor mapping, 
so it is faster than algorithm 1. The tensor is centred in 
centre of mass and in this reference system a nucleus is 
defined. The aggregation criteria are based on this nucleus 
and different definitions of the nucleus are possible. The 
algorithm performs the following steps: 
A. Starts region growing: 
1. extracts a seed p; and places it in level 1 of the tree 
structure; 
2. searches a spherical neighbourhood for other points; 
3. calculates the centre of mass using p; and the 
neighbouring points; 
4. calculates the second order moments with reference to 
the centre of mass, using p; and the neighbouring 
points; 
5. writes the second order symmetric tensor centred in 
the centre of mass; 
6. calculates the three real eigenvalues and the related 
eigenvectors; 
7. transforms the coordinates of p; and of the 
neighbouring points in the principal reference system; 
8. calculates the RMS coordinates in the principal 
reference system; 
9. defines a normalized elliptical nucleus (see at “Data 
distribution anisotropy"); 
10. if p; is internal at nucleus, aggregates p; and the 
neighbouring points in the nucleus; else marks p; as a 
terminal point of the tree structure. 
In the phase A.9 different definitions of the nucleus are 
possible. Time of work of this algorithm is 9(n).