Given a growing region,
LMM
searches its locally mu-
tual best neighbor for merging, which involves not only its
neighbors, which is termed first-order neighbors, but also the
second-order neighbors that are the neighbors of the first-or-
der neighbors. If there is no mutual best neighbor, the merging
procedure stops for the growing region and turns to another
one. However,
LBM
just searches the local best neighbor for
merging among the first-order neighbors. The growing region
would not change until the minimal adjacent arc weight
exceeds the scale threshold. As shown in Figure 7, when the
growing region (
R
g
) is getting larger after several merges, its
neighbors are still small, including the locally best first-order
neighbor
R
n
1
and the second-order neighbor
R
n
2
. Since the size
of
R
g
is large, the weight of arc between
R
g
and
R
n
1
increases
according to Equation 1. Then, even though
R
n
1
is the best
neighbor of
R
g
, the best neighbor of
R
n
1
could be
R
n
2
because
the size of
R
n
2
is small. Supposing
R
n
1
is also the best neighbor
of
R
n
2
,
LMM
refuses to merge
R
g
and
R
n
1
and turns to merge the
mutual best neighbors
R
n
1
and
R
n
2
. However,
LBM
would keep
merging
R
n
1
into
R
g
. On the other hand, when
AISP
is used to
control
LBM
, since the scale parameter is increased gradually,
the merging of
R
g
and
R
n
1
could be prevented by a small-scale
parameter during the increment schedule of the scale param-
eters, and turn to merge
R
n
1
and
R
n
2
first.
The sample analysis above shows that
AISP
can prevent
LBM
from keeping merging adjacent regions into the growing
region when the arc weight is getting large, but changing the
growing region and merging other region pairs with small arc
weight first, which actually enlarges the searching range and
enhances the optimization ability for
LBM
. Hence,
AISP
can
improve the segmentation accuracy of
LBM
. Since the search-
ing range of
LMM
is larger than that of
LBM
, it can change the
growing region automatically under the constraint of local-
mutual best. Thus,
AISP
cannot improve the accuracy signifi-
cantly for
LMM
, as well as for other region growing strategies
that have stronger optimization ability than
LMM
.
Furthermore, the segmentation accuracy of
LMM
on the
control of
AISP
is compared with the multi-resolution segmen-
tation (
MRS
) method in eCognition
®
Developer 8. The spectral
weight of the two methods is set as 0.5. The supervised evalu-
ation is performed on 5 and 4 multi-scale segmentation results
for T1 and T2, respectively. The evaluation results are shown
in Table 4. The
BCE
and
D
sym
values of
LMM
+
AISP
are smaller
than those of
MRS
, and the
ARI
values of
LMM
+
AISP
are higher,
which shows the slightly better performance of
LMM
+
AISP
.
Segmentation results of T1 and T2 are presented in Figure
8 to show the visual difference further. Combined with the
accuracy map indicated by
BCE
, the segmentation difference
is clearly presented for each object. The object boundaries are
accurate for both methods and the difference mainly caused
by over- or under-segmenting certain objects.
LMM
+
AISP
tends
to describe objects as single regions better, which is resulted
from the adaptive edge penalty function as analyzed in
(Zhang
et al
., 2014).
Multi-Scale Segmentation Results
To show the effectiveness of
AISP
on producing multi-scale
segmentations as candidates of meaningful scales, four multi-
scale segmentation results of test images T3 and T4 produced
by
LMM
+
AISP
are selected by visual analysis and presented in
Figure 9.
In the fine-scale segmentation of Figure 9a, single farm-
lands and houses are discriminated. As the segmentation
scale is getting coarser, the water areas are segmented as
single regions in Figure 9b, and the trees and farmlands are
separated as large objects in Figure 9c. Finally, in Figure 9d,
the impervious area, farmlands and trees are segmented as a
few large regions at the coarse scale. In Figure 9e, the small
objects, i.e., houses, farmlands, and alleys, are separated from
each other. In Figure 9f, the houses, and farmlands with simi-
lar tone are merged into larger objects. In Figure 9g and 9h,
the large objects, such as the river, roads, forest, rural residen-
tial areas, and super objects of farmland, are represented in
the coarse segmentation result. Moreover, Figure 9 shows that
the multi-scale segments are nested.
Segmentation Time
The additional computation time when applying
AISP
to
local-mutual best region merging (
LMM
) and local best region
merging (
LBM
) on two large test images, namely T5 and T6, is
shown in Table 5. The segmentation is performed on a desktop
computer with the
CPU
of 3.2
GHz
. When
AISP
is applied, the
segmentation time of
LMM
and
LBM
is a bit longer. This is be-
cause
AISP
needs to calculate the mean arc weight at each seg-
mentation scale. The additional computational complexity of
applying
AISP
is O(
N
a
+
B
∙
N
n
), where
N
a
and
N
n
are the number
of arcs and nodes in
RAG
, and
B
is the number of arcs whose
weights are changed at each merging iteration. Furthermore,
we calculate the segmentation time of producing multi-scale
segmentations by cutting the segment tree. It only takes 0.08
sec for T5 and 0.18 sec for T6. This shows the great priority of
using the segment tree to represent multi-scale segments.
Discussion
The gradually increased scale parameters in
AISP
are calculated
based on the mean arc weight in the graph, which are dynami-
cally determined during the merging procedure and adaptive
to various images.
AISP
avoids the arbitrary setting of scale
parameters ahead of segmentation. However, it is noted that
AISP
is proposed for region growing on the basis that the scale
parameter is defined as the threshold of similarity measure be-
tween adjacent regions.
AISP
can be applied to region growing
procedure with different merging criteria. However, if other
measures, such as region size or number of regions, are defined
as the scale parameter,
AISP
cannot extend to such cases.
To form continuous increment procedure of scale param-
eters and cover meaningful scales, the normalized factor (
NF
)
is added into the scale parameter, which mainly depends on
the parameters of initial normalized factor (
NF
0
) and decreas-
ing rate (
β
).
NF
0
determines the coverage of meaningful scales.
T
able
4. S
upervised
E
valuation
R
esults
for
M
ulti
-
scale
S
egmentations
of
T
est
I
mages
T1
and
T2 P
roduced
by
lmm
+
aisp
,
and
MRS;
NR
R
epresents
the
N
umber
of
R
egions
Test
image
LMM+AISP
MRS
NR
BCE D
sym
ARI
NR
BCE D
sym
ARI
T1
740
0.734 0.627 0.290
730
0.758 0.663 0.249
519
0.677 0.566 0.354
515
0.705 0.603 0.305
315
0.595 0.489 0.456
319
0.617 0.517 0.433
198
0.562 0.459 0.504
195
0.577 0.472 0.501
133
0.547 0.423 0.536
136
0.561 0.461 0.522
T2
429
0.566 0.470 0.431
445
0.681 0.586 0.315
186
0.450 0.349 0.531
188
0.532 0.438 0.452
107
0.426 0.329 0.560
108
0.436 0.347 0.554
79
0.416 0.323 0.572
79
0.424 0.349 0.553
T
able
5. S
egmentation
T
ime
(
sec
) D
ifference
C
aused
by
AISP; T
he
S
ize
of
the
T
est
I
mages
T5
and
T6
is
2000×2000 P
ixels
and
3171 × 3000 P
ixels
,
R
espectively
Test
image
AISP
Without AISP
LMM LBM LMM LBM
T5
20.0
19.9
19.5
19.3
T6
57.0
56.0
53.5
52
PHOTOGRAMMETRIC ENGINEERING & REMOTE SENSING
June 2015
467
