SEGMENTATION OF REMOTE SENSING IMAGES WITH A LAYERED GRAPH NETWORK
Herbert Jahn
Head of Department
German Aerospace Research Establishment (DLR)
Institue for Space Sensor Technology
Germany
Commission Ill, Working Group 3
KEYWORDS: Image Analysis, Vision Networks, Segmentation, Edge Preserving Smoothing
ABSTRACT
A Layered Graph Network (LGN) for image segmentation is presented. In the LGN a graph representation of images is
used. In such a Pixel Adjacency Graph (PAG) a segment is considered as a connected component. To define the PAG the
layers of the network are divided into regions, and inside the regions the image is represented by sub-graphs consisting of
sub-segments (nodes) which are connected by branches if they are adjacent. The connection of sub-segments is control-
led by a special adjacency criterion which depends on the mean grey values of the sub-segments and their standard
deviations. This way, the sub-segments of a layer | are merges of sub-segments of layer |-1 (the sub-segments of layer 0
are the pixels). The grey value averaging over the sub-segments is edge preserving and becomes more and more global
with increasing number of the network layer. Bridge connections between the segments are prevented by the special
regional structure of the network layers. The LGN can be understood as a special ,neural" vision network. It is applied
here to the segmentation of remote sensing images with good success.
1. INTRODUCTION
Image segmentation as one of the oldest problems in
image processing and computer vision is, despite of
various attempts to solve it (Haralick, 1985), not yet solved
satisfactorily. Having in mind the huge capability of the
human visual system, highly parallel and pipelined compu-
tation seems to be necessary for success in this field.
According to (Uhr, 1980) parallel-serial layered architec-
tures are best suited for image analysis. In this sense, a
new Layered Graph Network (LGN) was developed (Jahn,
1996), which is presented and applied to the processing of
remote sensing images.
Segmentation is understood here as "partial segmentation"
in the sense of (Levine, 1985), i.e. the found segments do
not necessarily correspond to the objects in the picture,
but only to more or less homogeneous regions, which are
the basis for the subsequent process of "complete seg-
mentation", where segments correspond to objects. Cru-
cial for this purpose is the definition of the partial
segments, which according to (Pavlidis, 1977) must have
a certain uniformity and which part the image into disjoint
nonempty subsets. Looking at certain segments in outdoor
scenes, e.g. the foliage of a tree, it becomes obvious that
segments can have a complicated structure with many
holes inside. Because of shading and other effects, also
non-closed edges can be part of a segment.
To cope with such structures a graph representation of
images (Pavlidis, 1977) seems adequate. In such a graph
a segment is considered as a connected component. To
define the graph each pixel must have a connection to
some (0,...,4) pixels of its four-neighborhood, e.g. as a
node adjacency list. Analogous to the Region Adjacency
360
International Archives of Photogrammetry and Remote Sensing. Vol. XXXI, Part B3. Vienna 1996
Graph (RAG) one could call such a graph a Pixel Adja-
cency Graph (PAG). Crucial for the construction of the
graph is the criterion of adjacency of two (4-neighboured)
pixels. If this criterion depends only on the gray value dis-
tribution of some local neighborhood of the pixels then,
because of noise, many bridges between visually separate
segments will occur, and the inherent image structure will
be destroyed. Averaging over sub-segments is needed,
and this can be accomplished by a special layered struc-
ture which will be presented in this paper.
The structure is similar to the well-known pyramid struc-
ture, but with the differences that, first, each layer repre-
sents a graph and averaging is carried out over the
connected components of these graphs and that, second,
the number of sub-segments of layer 1-1 belonging to a
segment of layer | is not fixed.
The criterion of adjacency of pixels or sub-segments used
here depends on the standard deviation of the gray values
of neighboured pixels or sub-segments. Therefore one can
generate segments corresponding to image regions with
slightly varying and noisy gray value distribution.
It is essential that the LGN presented here does not use
any a priori information about objects or segments in the
images being processed. It is not tailored to a special class
of images and should be applicable to a big diversity of
images. Furthermore, it is essential that no pixels (and no
sub-segments in the higher layers of the network) are
distinguished from the others. There are no seed points as
in some other merging methods (region growing) and thus
the sub-segment formation in the network layers can be
highly parallelized which is necessary for efficient compu-
tation. Of course, the simulation of the network on a con-
ventional von Neumann machine is very non-efficient and
can be used only for demonstration of the ability of the
method.
In. secti
Results
given in
Let the i
pixels (i
2n To
(ij) and
(14,4) or
ded wh
appropr
(i,j) and
will be c
graph is
where e
a segme
nent of 1
in the cl
interpre
method
ture to I
(i,j) and
their gre
Here F
gray va
(444. T
tion: Th
and (i4,j
gray val
proporti
sure, wl
of the gi
To sim
pixel (i,j
in the 8-
Here, t1
The thre
ifthe gr
are con
In orde
inspecti
screen ;
into acc
minate |
