ISPRS Commission III, Vol.34, Part 3A „Photogrammetric Computer Vision", Graz, 2002 
OBJECT SEGMENTATION WITH REGION GROWING AND PRINCIPAL 
COMPONENT ANALYSIS 
Marco Roggero 
Dept. of Georesource and Territory, Politecnico di Torino, C.so Duca degli Abruzzi, Torino, IT — 
roggero@atlantic.polito.it 
KEY WORDS: Principal Component Analysis, Tensorization, Region Growing, Discrete Geometry, Laser Scanning. 
ABSTRACT: 
The paper considers the problem of object segmentation and shape recognition in discrete noisy data. Two different algorithms 
combine region growing techniques with principal component analysis. The proposed algorithms are applied to a data set from 
airborne laser scanners. 
INTRODUCTION 
The problem of extracting object description from data is 
common in many scientific applications and technologies. We 
have begun this research starting from object segmentation and 
shape detection in airborne laser scanner data, and working on 
these data we have implemented my algorithms. However we 
think that some aspects of this work are of general interest, and 
may be applicable to other situations. 
Let's consider the problem of mapping single points into sets of 
points of similar properties, defining the regions within a points 
set. The algorithm proposed tries to solve the problem using 
region growing and principal component analysis. 
Region growing is probably less common than edge detection 
as a low level process, but it is applicable in multi-dimensional 
cases and in noisy environments. Principal component analysis 
is also robust to noise, and unable us to define the intrinsic 
geometric and physic properties of objects. 
HIERARCHIC REGION GROWING 
This section describes a linking mechanism which is based on 
local comparison of point properties, with reference to its 
neighbours. Points should be merged if they are near, not only 
in sense of euclidean distance, but also in terms of physical or 
geometrical properties. These properties, or point descriptors, 
are defined in the following (see "Geometrical descriptors" at 
pag. 3). 
Tree structure 
The linking algotithm start the aggregation of objects from a 
randomly extracted point, a seed, that is for example the first 
non aggregated point in the database index. This point p; is 
placed in the level 0 of a tree stucture, as shown in fig. 1, where 
each point is marked by its database pointer. Then, it is 
necessary to search the neighbourhood. Neighbourhood is 
intended now in an Euclidean sense, and this neighbourhood is 
the same used to calculate the geometric properties of the object 
at point p;. 
A - 289 
The points in the neighbourhood that match the aggregation 
criteria, are now aggregated to the object and placed at level 
l in tree structure, as a new branch of the tree. Then the 
linking algorithm continues the aggregation, starting from 
the points in the new level, and so on to the terminal 
branches. 
Terminal branches are determined by two events. The first, 
is when a point is marked as terminal (grey in the figure) if 
in its neighbourhood there aren't other non aggregated 
points. The second event is when the points in the 
neighbourhood don't match the aggregation criteria. 
The algorithm stops to aggregate the object when all the 
branches reach a terminal point; then it starts to aggregate a 
new object from a new random seed. 
  
  
  
  
Figure 1 — Tree structure. Points in the structure are marked 
by a database pointer. Point 1 is the seed; grey points are 
terminal. 
Summarizing: 
e An initial set of points are iteratively merged according 
to aggregation criteria. 
e An arbitrary seed point is choosen and compared with 
neighbouring points. 
e A region is grown from the seed point by adding 
neighbouring points that match aggregation criteria.