PHOTOGRAMMETRIC ENGINEERING & REMOTE SENSING
January 2014
71
PHOTOGRAMMETRIC ENGINEERING & REMOTE SENSING
January 2014
71
Abstract
A fast hierarchical segmentation method (
FHS
) for high-reso-
lution remote sensing (
HR
) image is proposed in the paper.
FHS
is completely unsupervised. It is characterized by two aspects.
First, the hierarchical segmentation process is accelerated
by the improved linear nearest neighbor graph (
LNNG
) model
and the segment tree model. It runs faster than other existing
hierarchical segmentation methods, and can produce multi-
resolution segmentations in time linear to the image size.
Second, an adaptive edge penalty function is introduced to
formulate the merging criterion, serving as a semantic factor.
A set of QuickBird, WorldView, and aerial images is used to
test the proposed method. The experiments show that the
multi-resolution segmentations produced by
FHS
can represent
objects at different scales very well. Moreover, the adaptive
edge penalty function helps to remove meaningless weak
edges within objects, enclosing the relation between segments
and real-world objects.
Introduction
Since the within-class variability is increased in high-
resolution remote sensing (
HR
) images, object-based image
analysis (
OBIA
) has become the principle method to handle
them (Blaschke, 2010). Image segmentation is to partition the
image into a set of spatially contiguous regions. The seg-
mented regions are viewed as image objects, which serve as
the basis for
OBIA
.
In
HR
images, different objects can emerge at various
scales. For example, detailed objects such as trees and houses
emerge at finer scales, and main structures such as forests
and urban areas are identified at coarser scales. Hence, image
segmentation should be able to produce multi-scale seg-
ments and form the segment hierarchy for successive analysis
(Beaulieu and Goldberg, 1989). Moreover, in the hierarchy,
multi-scale objects at the same location should be nested
(Benz
et al.
, 2004).
Among various segmentation methods (Pal and Pal, 1993;
Cheng
et al.
, 2001; Yang and Kang, 2009; Dey
et al.
, 2010),
the hierarchical method is a good choice for constructing the
image object hierarchy for an
HR
image. It follows the stepwise
optimization rule and has strong constraint for the optimiza-
tion problem (Beaulieu and Goldberg, 1989). The hierarchi-
cal segmentation method can produce not just one, but a
sequence of partitions, forming the segment hierarchy: in ini-
tial segmentations, detailed objects are preserved, while only
Department of Geographic Information Science and Jiangsu
Provincial Key Laboratory of Geographic Information Science
and Technology, Nanjing University, NO. 163, Xianlin Road,
Nanjing 210023, China (
.
Photogrammetric Engineering & Remote Sensing
Vol. 80, No. 1, January 2014, pp. 71–80.
0099-1112/14/8001–71/$3.00/0
© 2014 American Society for Photogrammetry
and Remote Sensing
doi: 10.14358/PERS.80.1.71
main structures remain in latter segmentations. Moreover,
as the coarser segments in latter segmentations are produced
by merging adjacent regions in former ones, the multi-scale
segments are nested. Hence, the hierarchical segmentation
method is widely used for segmenting color images (Haris
et al.
, 1998; Arbeláez
et al.
, 2011),
HR
images (Trias-Sanz
et al.
,
2008; Gaetano
et al.
, 2009; Li
et al.
, 2010) and
SAR
images
(Yu and Clausi, 2007; Carvalho
et al.
, 2010).
However, hierarchical segmentation is time-consuming
due to the search of the most similar pair of adjacent regions
within the whole image domain. In order to save the segmen-
tation time, Kurita (1995) proposed to store dissimilarities
of all the pairs of adjacent regions in a heap, rather than in a
list, making the complexity decreased from
P
to log(
P
), where
P
was the number of adjacent region pairs. Beaulieu (1990)
chose to store the best neighbor of each region in a list. Then,
the length of the list was reduced to
N
, where
N
is equal to the
number of regions. In the work of Haris
et al
. (1998), the near-
est neighbor graph (
NNG
) was introduced, in which only the
distance between mutual best neighbors was added in a heap.
The height of heap was further reduced, but it had to scan a
second-order neighborhood. A region growing engine (
SEGEN
)
was proposed by Gofman (2006), in which the best neighbor
of each segment was recorded in a priority queue.
SEGEN
need
not scan the second-order neighborhood, but the queue height
was larger than that of
NNG
.
In other works, different features, such as spectral homo-
geneity, shape (Baatz and Schäpe, 2000), texture (Ryherd and
Woodcock, 1996; Hu
et al.
, 2005), and structural features
(Pesaresi and Benediktsson, 2001; Akçay and Aksoy, 2008),
have been used for remote sensing image segmentation.
However, it is still difficult to define suitable feature with
semantic meaning for
HR
image. The feature of edge strength
was adaptively integrated in the region growing process as
a semantic factor by Yu and Clausi (2008). The graduated
increase edge penalty (
GIEP
) was proposed, and the results
were appealing. But in their work, the edge penalty served as
the parameter of spatial context model in the framework of
Markov random field (
MRF
), and the incremental schedule was
just determined to be experimentally satisfactory.
The objective of this paper is twofold. First, the linear
nearest neighbor graph (
LNNG
) model is proposed to acceler-
ate the hierarchical segmentation process. The segment tree
model is adopted to represent the segment hierarchy, which
Fast Hierarchical Segmentation of High-
Resolution Remote Sensing Image with Adaptive
Edge Penalty
Xueliang Zhang, Pengfeng Xiao, and Xuezhi Feng
