The International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences. Vol. XXXVII. Part B4. Beijing 2008 
1215 
2.3 FAST PARCEL MERGING 
With the initial sub feature units and merging costing function, 
the commonly used merging schemes which can be adopted 
include the following two kinds: 
The main steps of scheme one: 
Stepl. Input the RAG (NNG) of the initial segmentation; 
Step2. Loop until some merging terminating condition is 
satisfied: 
Select the link of the minimal merging cost in the 
RAG (NNG); 
Merge the corresponding region pair into a new node, 
and delete the old pair; 
Update RAG (NNG); 
Step3. Output the merged RAG (NNG) and terminate the 
whole merging. 
The main steps of scheme two: 
Stepl. Input the RAG (NNG) of the initial segmenting; 
Step2. Loop until all nodes are merged: 
Starting from a node, search its neighbourhood nodes. 
If the merging cost is less than some threshold, merge 
them into a new node until the merging cost of the 
new node exceeds some specified merging threshold. 
Exclude these merged nodes from the following 
merging; 
Step3. Output the merged RAG (NNG) and terminate the 
whole merging. 
The advantage of the first merging scheme lies in that it can 
guarantee the current merging pair is the minimal cost one of 
the un-merged pairs, which thus indicates that it is a globe 
minimal merging cost strategy. But it has severe shortcoming of 
very low efficiency because the links of a merging node with all 
its neighbours should be rebuilt to find the minimal cost link to 
update the NNG, which is a very time-consuming business. Our 
experiments indicate that it isn’t suitable for segmenting 
remotely sensed imagery commonly with large data volume and 
with the merge cost function in section 2.2. 
The second merging scheme needs to visit the parcels only once, 
and then is of faster speed; but the problems rely in the 
selection of merging criterions. If area is selected as the control 
factor, it may cause many small parcels with distinct spectral 
difference with the neighbours to be merged compulsively. If 
the merging criterion in section 2.2 is used, it often brings a 
defect that sometimes a merge will be too greedy: it often 
merge too many unsuitable parcels because more merges will 
occasionally cause smaller merging costs, which makes the 
merging unstoppable. 
With a lot of experiments, a quick merging strategy is designed 
to merge these sub feature units in a repetitive way. It includes 
the following four steps. 
Stepl. Input the NNG of the initial segmentation of section 
2.1; 
Step2. Loop until all nodes are merged: 
Start from node A, find its pointing node B (its 
minimal merging cost node). Merge A, B if the 
merging cost of this node pair is under some specified 
threshold, and then create a new node in the output 
NNG. If exceeding the threshold, copy node A into 
the new NNG directly. In the above merging, if B has 
been merged before, (for example, into C in the new 
NNG), then A will be directly merged into C and no 
new nodes will be created. 
Step3. Re-build topology for the new NNG; 
Step4. Redo the above steps on the new NNG if the 
terminating condition hasn’t been reached; otherwise output the 
merged RAG (NNG) and complete the segmentation. 
The characteristic of the method is that we don’t remove a 
parcel from the merging list after it is merged. That’s to say that 
a parcel can be merged many times, until all the nodes are 
visited once. This merging strategy avoids the high consuming 
performances including topology rebuilding, merged node 
searching and deleting, etc. We only rebuild the topology once 
after the entire merging of an image has been accomplished. It’s 
proved that this merging strategy doesn’t decline the visual 
feeling of the segmentation, but greatly improves the algorithm 
efficiency. 
Just similar to eCognition, a scale parameter is used to control 
the merging processing. If all parcel merging costs exceed the 
power of the scale parameter, the whole merge cycle breaks and 
the segmentation is over. Through experiments, we find that the 
minimal merging cost doesn’t increase steadily with the 
merging times. It fluctuates, which means namely the latter 
merging cost sometimes maybe be lower than the former. But 
generally it will increase post after certain times of merging. 
Experiments indicate that totally after 7 to 8 iterations, the 
whole merging will be terminated. The scale parameter controls 
the iterating times, which indirectly controls the average size of 
the parcels. With changing the scales, a multiresolution 
segmentation can be realized. 
3. EXPERIMENTAL ANALYSIS 
Our algorithm is implemented with visual C++ 2003, and is 
tested on the platform of windows XP , with Pentium 4 
2.93GHz CPU, 1G memory. Because image segmentation is 
only the first step for image information extraction, over 
segmentation to some degree will not bring serious influences 
to succeeding analyses. Keeping this in mind, the evaluation of 
method precision is based on whether a method well prevents 
different ground objects from falling into same segmenting 
parcels. Several comparative experiments on different types of 
images such as SPOT-5, IKONOS with eCognition 5.0 
segmentation module are carried out. To facilitate the 
comparisons, the inputs of our method and eCognition are 
unified to the default setting of the latter: w=0.1, w c =1.0, 
Wcmpct 0.5. 
Figure 1, 2, 3 illustrate the experimental results, in which the 
left graphs are the results of eCogntion, the right are of our 
methods. Table 1 presents the comparisons of the two methods 
on segmentation precision and efficiency. 
With these proofs, it can be found that the two methods give 
similar and good segmentation in vision, and both have their 
respectively local visual worse-or-better segmenting parcels. 
Although eCognition generally produces more regular shape 
parcels, it often brings some fragmentized parcels distributing 
around the boundary of many even-tone, large-size parcels (see 
the pond in the upper-left comer of Figure 1, the river in Figure 
2 and the playground in Figure 3). Our method doesn’t have 
this kind of defects yet. In efficiency comparisons, our method 
trails eCognition. Maybe there exist two reasons that cause the 
lag: 1) with same scales, our method perhaps merges more 
times than eCognition (see the parcel number in Table 1), which 
causes more time consuming; 2) a lot of superfluous time is 
wasted on our merging steps (for example, the re-calculation of 
parcel topology), which may be improved with introducing