The International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences. Vol. XXXVII. Part B4. Beijing 2008 
This problem can be overcome by Watershed segmentation, 
which often produces more stable segmentation results and 
continuous segment boundaries (Gonzalez and Woods, 2002). 
Watershed segmentation is based on the interpretation of a 
digital image as a topographic surface, with the grey values 
representing heights; the segmentation tries to determine image 
regions as the catchment areas of local image minima. The 
boundaries of these regions correspond to watersheds in the 
topographic surface. For a segmentation that delivers regions of 
homogeneous grey values, the actual watershed segmentation 
has to be applied to a gradient image, which has to be smoothed 
to achieve stable results (Gonzalez and Woods, 2002). As a 
matter of fact, an image representing the homogeneity value H 
as defined in Equation 1 can be used as the basis for 
segmentation, with the parameter of the Gaussian kernel 
defining the degree of smoothing. 
c) d) 
Figure 2. a) IKONOS RGB image of Bhutan with a resolution 
of 1 m; b) Homogeneity image H (inverted for 
readability), using = 1. c) Results of classification: 
homogeneous (red), edge (green); point-like (blue), d): 
Connected components of homogeneous pixels. 
Figure 3 shows the results achieved for a watershed 
segmentation of the image in Figure 2a using two different 
smoothing parameters . In both cases the advantage of 
watershed segmentation is obvious: it delivers segments with 
closed and relatively smooth boundaries. However, the left 
image shows a gross over-segmentation. The segment 
boundaries a human operator would choose are all there, but 
there are too many segments. On the other hand, in the 
segmentation on the right some important image structures have 
been merged due to the smoothing of the homogeneity image. 
In order to overcome these problems, we propose an iterative 
segmentation strategy. First, watershed segmentation is applied 
with a low degree of smoothing, which results in a strong over 
segmentation. Second, a region adjacency graph is generated, 
which represents the image on a symbolic level and also 
contains important attributes both of the image segments and 
their boundaries. Third, neighbouring regions are merged based 
on a similarity of attributes and the significance of their 
separation. 
2.2 Region Adjacency Graph 
After the initial watershed segmentation, a Region Adjacency 
Graph (RAG) is generated. The nodes of the RAG are the 
homogeneous segments, whereas its edges represent the 
neighbourhood relations: two segments S, and Sj with i * j are 
connected by an edge ey in the RAG if there is at least one 
boundary pixel in the segmentation that is neighbour both to 5, 
and to Sj. 
a) = 3 b) =8 
Figure 3. Watershed segmentation of the image in Figure 2a 
based on the homogeneity image H (Equation 1) for 
two values of the smoothing scale 
When the RAG is constructed, the attributes of both its nodes 
(the segments) and its edges are determined. A segment Shas 
both geometric attributes, namely the number of pixels assigned 
to the segment, the minimum and maximum coordinates, and 
the centre of gravity of the segment, and radiometric attributes, 
namely the average grey level vector g‘ avg = E(g') and the 
covariance matrix Q' gg of the grey levels. Finally, an overall 
measure var‘ of the noise level inside the segment is determined 
as the trace of Q' gg : var' = trace)Q' gg ). In order to make the 
computation of g'^ and Q' gg robust with respect to outliers next 
to the segment boundary, grey level vectors that are close to the 
segment boundary are excluded from the computation. 
However, all grey level vectors are used for the computation if 
a segment is so small that all its pixels are within such a 
distance from its boundary that they would thus be excluded. 
An edge ey in the RAG represents a neighbourhood relation 
between two segments S, and Sj and, thus, also the boundary 
between these regions. Note that the boundary between two 
segments may consist of one or more sequences of boundary 
pixels. That is why each edge in the RAG contains a set of 
connected boundary pixel chains that are extracted from the 
label image representing the segmentation results. Furthermore, 
the boundary pixels have a 2D extent in the digital image, i.e. 
the area covered by these pixels. Thus, an edge ey also has an 
average grey level vector and a covariance matrix of grey levels, 
computed from the grey levels of all the boundary pixels 
separating S, and Sj. Finally, a measure Ty for the strength of the 
boundary is determined as the percentage of boundary pixels 
for which the homogeneity measure H (Equation 1) is larger 
than the threshold H max that would be used for edge extraction. 
In this context, it is advisable to re-compute H using a relatively 
small value for the smoothing parameter , e.g. = 0.7. Ty 
can be interpreted as the percentage of edge pixels contained in 
the boundary separating the two segments S, and Sj. It will be