1. The distribution of arc weights in different images
is various, and the change of arc weights in growing
procedure is complicated. The set of scale parameters
should capture this variety so that it can be qualified to
control the growing procedure for various images.
2. In a given image, different objects are peculiarly
presented at several scales, as shown in Figure 2. We
consider these scales as meaningful scales, which
should be covered by multi-scale segmentation results.
To ensure the coverage, the scale parameters should
increase smoothly and the increment step parameters
should be set properly.
(a)
(b)
(c)
(d)
Figure 2. Samples of meaningful segmentation scales. Objects
are severely over-segmented in (a) and under-segmented in (d).
(b) and (c) are considered as meaningful because the single
houses in (b), and the group of houses and trees in (c) are repre-
sented as single regions.
Following the above considerations,
SWSP
is extended
to adaptively increased scale parameter (
AISP
). Instead of
assigning scale parameters independently, we calculate the
scale parameter based on the mean arc weight (
w
– ) in
RAG
. In
the region growing process, the expansion of regions makes
w
–
increased according to Equation 1, resulting in increased scale
parameters adaptive to specific images and growing procedure.
However, if
w
– is assigned as the scale parameter directly,
too many regions would be merged at each scale, leading to
few scales and partial coverage of meaningful scales. Hence,
a normalized factor (
NF
k
) is added to calculate the
k
th
scale
parameter (
S
k
) as below:
S
k
=
w
– /
NF
k
.
(2)
The increment of
S
k
is jointly determined by
w
– and
NF
k
.
Generally,
w
– is increased itself in the merging procedure.
NF
k
decreases from a large number to 1 at a proper rate to form the
continuous increment of
S
k
, which helps to cover meaningful
scales entirely.
NF
k
is involved as below:
NF
k
=
NF
0
,
NF
k
–1
,
β
·
NF
k
–1
if
k
= 0
if
k
≥
1
∩
P
≥
T
P
if
k
≥
1
∩
P
<
T
P
(3)
First, it is assigned as the initial normalized factor (
NF
0
).
Then,
NF
k
(
k
≥
1) is calculated on the basis of
NF
k
-1
at the former
segmentation scale. At scale
k
− 1, if there are many merging
iterations performed,
w
– has been significantly changed, then
NF
k
is set the same as
NF
k
-1
. On the other hand, if few merging
iterations are performed at scale
k
− 1, the change of
w
– is not
significant. In this case,
NF
k
is calculated by multiplying
NF
k
-
1
with the decreasing rate (
β
, 0 <
β
<1). Hence, the number
of merging iterations at the former scale determines the
normalized factor at current scale. We define the proportion (
P
)
of the number of merging iterations to the number of regions
at the former scale. If
P
is less than the threshold (
T
P
), the
normalized factor is decreased to increase the scale parameter.
The threshold
T
P
determines where to change the value of
NF
k
. The influence of
T
P
is not as significant as the other two
parameters of
NF
0
and
β
, which determines how to change
the value of
NF
k
.
T
P
is set as 0.1 in this study because it is
small enough to form the smooth change of scale parameters.
NF
0
should be set large enough so that the scale parameter
could be small enough to cover small objects at fine scale.
In terms of the parameter
β
, a small value would accelerate
the decreasing procedure of the normalized factor, leading
to partial cover of meaningful scales. However, a large value
slows down the decreasing procedure of the normalized
factor, producing too many scales. In this study,
NF
0
and
β
are
set as 10 and 0.9, respectively. The effectiveness is analyzed
in detail in the experiments to indicate how to set the two
parameters properly.
Multi-Scale Segmentation
On the control of
AISP
, region growing is implemented on
RAG
until reaching the target scale by satisfying the smaller scale
parameters sequentially. A segmentation scale is indicated
by the serial number (
k
). If
k
is large, segments are at a coarse
scale. By contrast, a small
k
results in a fine-scale segmenta-
tion. Since it is difficult to link the scale parameters directly
to the semantics of segments, the meaningful scales for a
given application still need to be selected from the multi-
scale segmentations. To accelerate the selection process, we
introduce the segment tree to represent and export multi-scale
segmentations. The multi-scale segmentation algorithm is
described in Table 1.
T
able
1. T
he
M
ulti
-
scale
S
egmentation
A
lgorithm
on
the
C
ontrol
of
AISP
B
ased
on
the
G
raph
M
odel
and
S
egment
T
ree
Input: The region adjacency graph (RAG), the segment tree (ST).
Variables:
nl
–the number of levels in ST,
cs
–the serial number of
current scale.
Parameter: The serial number of the target scale
k.
Output: The segmentation result at scale
k
.
1) If ST is empty, assign the nodes in RAG as leaf nodes of ST, and set
cs
as 1.
Else if
nl-1<
k
, set
cs
as
nl
-1.
Else if
nl
-1
≥
k
, go to 3).
2) Repeat when
cs
≤
k
.
(2-1) Calculate the current scale parameter
S
cs
by Equation 2.
(2-2) Perform region growing controlled by
S
cs
based on the
remaining nodes in RAG at scale
cs
-1.
(2-3) Assign all the remaining nodes in RAG as the nodes at level
cs
+1 in ST.
(2-4) Set
cs
=
cs
+1.
3) Output segmentation result by cutting ST at level
k
+1.
The initial segments are the leaf nodes in the tree and the
segments at scale
S
k
are represented as the nodes at level
k
+ 1 of the tree. As
S
k
increases gradually, the segments are
getting coarser and represented by the nodes at higher level
PHOTOGRAMMETRIC ENGINEERING & REMOTE SENSING
June 2015
463
