The International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences. Vol. XXXVII. Part B4. Beijing 2008 
1214 
According to Smet’s work [Smet et al., 2000], the efficiency of 
rainfalling watershed segmentation is superior remarkably to 
watershed algorithms based on immersion simulation. For this 
reason, the rainfalling watershed algorithm is chosen to initially 
segment an image into a set of so called sub feature units, which 
are the initial parcels with smaller sizes. 
With these sub feature units, the spectrums, shapes (area, 
perimeter, etc.) and neighbourhood topology should be recorded 
to serve the following merging processes. These are fulfilled 
with Region adjacency graph (RAG) and nearest neighbour 
graph (NNG). 
Figure 1. RNG & NNG of a parcel graph 
As illustrated in Figure 1, RAG is an undirected map which can 
be expressed as G = (V, E), in which V={1,2is the set of 
nodes, E is the set of links, and ^ v v . Every parcel is a 
node of the map, and a link exists if two nodes are neighbours. 
where, c is the band count, w c is user specified weights for 
every band (1.0 by default). 
The shape heterogeneity is the combination of compactness and 
smoothness heterogeneity: 
Given a specified RAG and its merging cost function S, its 
corresponding NNG can be expressed as G m = (V m , E m ), where 
V m is just similar to V in RAG, and E m only records the 
minimal merging cost of every node, which indicates NNG is a 
directed map. In particular, if the begin and end nodes of a link 
are superposed, there exists a cycle. NNG improves the merging 
efficiency than RAG because it obviously decreases the storage 
and calculation of links. 
2.2 MERGING CRITERION 
h , = w . x h 
shape cmpct cmpct 
+ 0-w cmpct ) x K m o,hO) 
in which compactness heterogeneity is calculated as: 
h — u 
cmpct Merge 
Merge 
~{n x 
l 
+ n, 
/, 
1 /— ' 2 
* Merge v ^1 
and smoothness heterogeneity is calculated as: 
) (4) 
Based on the sub feature units, a merge cost function integrating 
spectral heterogeneity and shape heterogeneity is designed to 
guide the merging of parcels. The use of shape is to make the 
merged parcels more regular in shapes. With experiments, the 
merging cost function is similar to [Baatz et al., 2007]: 
/ = wx h color + (1 - w) X h shape (1) 
In which w is the weight for spectral heterogeneity falling in the 
interval [0, 1]. A generally suitable weight for colour is 0.9, and 
0.1 for shape. Too large shape weight will bring unreasonable 
segmentation. 
h = tq 
smooth Merge 
fnc- (ni .L + „ 2 .L) (J) 
V Merge 0 2 
where / is the perimeter of a parcel, n is the pixels, b is the 
perimeter of its bounding box. A commonly suitable setting of 
Wcmpct IS 0.5. 
The merged parcel variance can be got with Formula 6 to avoid 
redundant calculation: 
The spectral heterogeneity is the variance of the parent parcel 
minus the sum of the variances of the two child parcels, 
weighted with their respective areas: 
h 
color 
Z W e (” Merge 17 ~ («1 f + n 2°l )) < 2 > 
(7 
Merge 
((«, -1)0-, + (n, - l)<f) !(n merge -1) 
+ n,n 2 (m,-m 2 f /(n Merge )(n Merge ~ 1) 
(6) 
where m\, m 2 are the means of the two child parcels.