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