RK 
of images is 
the PAG the 
consisting of 
ts is control- 
eir standard 
ıts of layer 0 
more global 
the special 
It is applied 
Pixel Adja- 
iction of the 
eighboured) 
ay value dis- 
pixels then, 
ally separate 
structure will 
is needed, 
yered struc- 
ramid struc- 
layer repre- 
ut over the 
hat, second, 
longing to a 
ments used 
gray values 
fore one can 
regions with 
n. 
oes not use 
nents in the 
special class 
| diversity of 
xels (and no 
letwork) are 
ed points as 
ng) and thus 
yers can be 
ient compu- 
rk on a con- 
efficient and 
ty of the 
method. 
In section 2 the method is explained in more detail. 
Results demonstrating the power of the approach are 
given in section 3. 
2. The PAG and the LGN Structure 
Let the image be represented by an image region of N x N 
pixels (i,j) (i,j = 0,...,N-1) with the gray values gij and N = 
2^ To constitute the PAG we consider each image point 
(ij) and its 4-neighbours (i*1,j), (i-1,)), (i,j+1), (ij-1). Be 
(i4,j4) one of the 4-neighbours of (i,j). Then it must be deci- 
ded whether (i4,j4) is adjacent to (ij) or not by using an 
appropriate criterion. If they are adjacent then the points 
(i,j) and (14,4) (which correspond to the nodes of the graph) 
will be connected by a branch. A suitable description of the 
graph is given by the node adjacency list (Pavlidis, 1977) 
where every node (i,j) has a list of its adjacent nodes. Now 
a segment of the image is defined as a connected compo- 
nent of the graph. Such a kind of graph definition was used 
in the clustering of dot patterns (Jahn, 1986), and one can 
interprete the segmentation method presented here as a 
method of clustering the data. Crucial for the graph struc- 
ture to be generated is the criterion of adjacency of points 
(i,j) and (i4,j4). Node (ij) and node (i44) are adjacent, if 
their gray values fulfill the condition 
S nas V) 
Here F is some adaptive threshold which depends on the 
gray values in some neighbourhood of the points (i,j) and 
(i4,j4). To specify F we start with the following considera- 
tion: The visual separation of two neighboured pixels (i,j) 
and (i4,j4) is more difficult if there is a big variation of the 
gray values in their neighbourhood. Therefore F should be 
proportional to a measure of this variation. A simple mea- 
sure, which gives good results, is the standard deviation c 
of the gray values in a neighbourhood N of (i,j) and (i4,j4). 
To simplify the computation, it is useful to attach to each 
pixel (i,j) a value Gj.j- It turned out that the computation of © 
in the 8-neighbourhood N, of (ij) is sufficient. Therefore, 
E= 1,841,057 3 - (2) 
Here, t1 is a threshold, and 
m pas 1 
ST oO : (3) 
The threshold (2) which increases with noise but vanishes 
if the grey values in the 8-neighbourhoods of (i,j) and (i1,j1) 
are constant is not sufficient. 
In order to assess the segmentation results by visual 
inspection using a computer screen, the properties of this 
screen and that of the human visual system must be taken 
into account. Looking at such a screen one can not discri- 
minate pixels with 
8; — e = ly : (4) 
International Archives of Photogrammetry and Remote Sensing. Vol. XXXI, Part B3. Vienna 1996 
In general, the threshold to depends on the brightness (see 
below). Now, combining (2) and (4), the adjacency crite- 
rion for level | = 1 is 
META SMAXTO(G FLU ILS : (S) 
In principle, one could apply the adjacency criterion (5) to 
the whole image. Then one would obtain a graph in one 
step (i.e. without a layered processing structure). But this 
has the drawback that only local information contributes to 
the graph and no sufficient noise reduction takes place. 
Single noisy image points then can connect visually sepa- 
rate segments, and one generally obtains too large seg- 
ments. In graph theory such connections between 
connected components are called bridges. 
To avoid (or to minimize the number of) such bridges, 
averaging over adequate regions is necessary, and this 
can be done using a layered processing structure. In order 
to generate such a layered structure one divides the image 
ij = 0,1,.,N-1 (N » 2 in every layer (or level) | 
(I=1,...,Imax) into sub-regions Reg(l,k4 ko) each contai- 
ning 2lx 2 image points: 
Reg(lk4,k2) (k4, ko= 0,21): 2k4<i< 2(k4 +1) -1 
2lko xj x 2lko *1) -1 
Figures 5b,c,d show the regional partition (marked by 
dashed lines) for | = 1,2,3 and N=8 (n = 3). 
Let's consider first the layer 121. Applying (1) to all pixels 
inside a 2 x 2 region Reg(1,k4,k2) one can attach to every 
pixel (i,j) a node adjacency list NAL(1,i,j) which contains all 
pixels from the same region which are adjacent to the pixel 
(ij). In the image plane i,j = 0,...,N-1 the node adjacency 
list NAL defines a graph with N5eg(1) connected compon- 
ents or sub-segments. Using the NAL, the sub-segments 
can be labeled using a graph traversal algorithm, e.g. 
depth first traversal (Pavlidis, 1977). In the result of this 
procedure each image point (i,j) obtains a label Lab(1,i,j) 
(i,j = 0,...,N-1). All points (i,j) with Lab(1,i,j) = m belong to 
the same segment m. Now, as a feature, the mean gray 
value <g>(1,m) can be assigned to the sub-segment m. 
Now we consider network layers (levels) | 22,3,... . Input 
elements are the sub-segments m 7 0,1,..., Neea(l-1)-1 of 
level |-1 with the features «g»(l-1,m). Sub-segments can 
be adjacent if they belong to the same region Reg(l, k4,k2) 
and if they are ‘4-neighbours’. Generalizing (5), the adja- 
cency of two segments m4 and mo now is defined by 
Kg (- 1,m) - (0-1, m)| 
6 
€ MAX (t, (0) e [49 (—- 1, m) ;m € N(m,, m.) ]. t4 (J) f 
Here the standard deviation 
c[(g U-1,m);meN(m,, m,)] ofthe values 
<g>(l-1,m) is given by 
6 [(g) (!- 1, m) m e N (m,,m,)] 
(7) 
[Ss (/- 1, m) +0 (4-1, m,)]. 
N=