o(l-1,m) is the standard deviation of the mean gray values 
<g>(I-1,m’) of segments m' € N, (m) , and N, (m) is the 8- 
neighbourhood of segment m. 
Using (6), for each sub-segment m of level l-1 in a region 
Reg(l,k1,k2) the adjacent sub-segments which belong to 
the same region Reg(l,k1,k2) can be identified and stored 
in a node adjacency list NAL(I,m). NAL(I,m) defines a new 
graph of level I. Again, all connected components of this 
special region adjacency graph can be labeled by integers 
label(l,m). Using Lab(l-1,i,j) and label(lm), the new 
function Lab(l,i,j) can be generated by a simple updating 
procedure. This process can be applied recursively from 
layer to layer, and in layer |l=Imax the final segmentation is 
obtained. 
Figures 5b-c display these processing steps in the three 
layers 1=1,2,3 for the 8x8-image of fig. 1a (letter i with 
noise point). Adjacent pixels are connected by lines which 
are equivalent to the branches connecting the nodes of the 
graph. The regions are marked by dashed lines. Fig. 5b 
shows the PAG for I=1 with 25 segments. The PAG for |=2 
(fig. 5c) has 11 connected components, and there are 4 
segments as the final result (fig. 5d). 
(6) is only an example for a possible adjacency criterion. 
Other criteria are permitted and even necessary. Experi- 
ments with various images have shown that the criterion 
(6) gives sometimes (if shading is substantial) bad results 
if the sub-segments are too large. Better results are obtai- 
ned if inclined planes f(m,i,j)=ari+b'j+c are fitted to the gray 
values inside sub-segments m of level |max-1 with more 
than nga pixels (for smaller sub-segments we use 
f(m,1,j)=<9>(max-1,mM)). Now, sub-segments M], m» of 
level \max-1 are adjacent, if there exist two 4-neighbours 
(dp) em and (i,,j,) e m, with 
fan, is) Far af) | St ax) - (8) 
(8) is applied without a partition of layer max into regions 
Reg([max-K1;k2), Or, with other words, Reg(lmax-K1;k2) is 
the whole image plane. This ensures that the final seg- 
ments are not confined to squared regions. 
In general, the visibility of gray value differences of neigh- 
boured segments depends on their brightness. This can be 
taken into account if t5-values are used which depend on 
f(my.i1.j1) and f(my,iy jo). First experiments with 
ly (4 2) = 00, (9) 
if 
max (f(m,, iy 4), (n,, 545) ).« 70 
or (10) 
min gon, i171) , J (m,, 1512)) » 200 
gave encouraging results. (9) and (10) express the fact 
that (on a computer screen or paper) segments cannot be 
discriminated visually if they are both very dark or very 
bright. 
Many experiments with various images have shown that in 
many cases a big number of very small segments will be 
generated. Some of them are important and can be seen 
clearly but others are not visible at all. This is caused by 
    
International Archives of Photogrammetry and Remote Sensing. Vol. XXXI, Part B3. Vienna 1996 
the up to now used adjacency criteria, which do not take 
into account the size of the segments. Small segments 
become better visible if the size increases. One can take 
this into account if one uses a size dependend adjacency 
criterion in an additional layer lmax*1 for small segments 
m with less than n, pixels. Such a segment m will be eli- 
minated by merging with a bigger segment m' from its 4- 
neighbourhood if its mean gray value <g>(lmax:M) differs 
from neighboured gray values of m' less than t3/npix (m). 
Here, nyix (m) is the number of pixels of segment m and t5 
is a further threshold. 
The generated PAG of level l4, 1 is the preliminary seg- 
mentation result which is presented here. Further layers of 
the LGN with other adjacency criteria taking into account 
not only gray value and size but also shape and spatial 
arrangement of sub-segments should be investigated in 
the future in order to segment textures and recognize 
objects. 
For display of the segmentation results (for = max+1) it is 
useful to define a function 9rean(i,j) with the constant value 
«g? (lia * 1, m) in every point (i,j) of a segment m. Such a 
dmean - image shows the segmentation of the original 
image gij (segments have constant gray level), and it often 
resembles the original image very much. Then the gmegn - 
image can be used as a (edge preserving) smoothed ver- 
sion of the original image dij But it must be stressed that 
the final result is expressed by the function Lab(i,j) 
(=Lab(l,4x+1.i,j)) which assigns the segment number to 
each pixel (i,j) of a segment. Therefore, a segment can be 
characterized by all of its pixels (i,j) with gray values gi j- 
Therefore, no information is lost and various segment fea- 
tures can be calculated which can be used in higher layers 
of the network for texture segmentation and object 
recognition. 
3. Results 
For demonstration of the ability of the method the LGN 
was simulated on a conventional serial computer (486 PC 
or SUN workstation) using the IDL language. À number of 
experiments with simulated and real world images was 
carried out in order to identify useful thresholds t4(l) and 
ta(l). It turned out that t4(l) = 0.6...0.65 (| = 1,...,Imac1) 
and to(l) 2 5...7 (I = 1.....\mao With Imax = 5 gave best 
results. Sub-segments of level lygc1 with more than 
Nmin = 32 pixels were fitted by inclined planes f(m,i,j) used 
in (8). For the elimination of small segments with less than 
ng=5 pixels t3=30 is a good threshold value. The following 
results were obtained by using these parameter values. 
Figure 1a shows a 128 x 128 Mars image. The image was 
segmented with t,=0.6, t2=5 (without (9), (10)). The result 
(fig.1b) shows 803 segments. After the elimination of small 
segments only 367 segments are left (fig.1c). There is no 
visible difference between figures 1b and 1c. Essential 
small details (e.g. small craters) are retained. Fig.1d 
shows the 3 biggest segments. 
A 128 x 128 LANDSAT TM image (fig.2a) was segmented 
using the parameters t4 = 0.6, to = 5 (again without (9), 
  
   
  
   
   
   
   
   
   
     
   
   
   
    
    
  
   
   
   
   
   
   
   
   
   
    
   
     
   
   
  
   
   
   
   
   
    
   
    
     
    
   
   
   
    
   
    
   
    
  
10). T 
segmen 
segmen 
sufficier 
The 10 | 
the com 
The ime 
1170.6 € 
of smal 
Taking 
left (fig. 
adequa 
is not s 
must b 
once ac 
best de 
The foi 
t,=0.65 
2301 se 
eliminai 
ments : 
and hoy 
segmer 
gest se 
ground. 
Haralicl 
Technic 
Jahn, F 
schen F 
Jahn, F 
Graph | 
press) 
Levine, 
Hill, Ne 
Pavlidis 
ger-Vel 
Uhr, L., 
Conce[ 
Compu