clusters. A small region is grouped with its most similar 
neighbour expressed by the t-score according Eq.( 12). 
4.3.3 Stage IIc: Removal of Insignificant Regions 
The aim of Stage IIc is to remove elongated regions which 
are due to mixed pixels at the region borders. Removal of 
regions solely based on size is insufficient to perform this 
task. In Lemmens (1991) it is shown that an appropriate 
measure to describe the significance of a sliver polygon is 
the quotient of the area size A of the region and the stan- 
dard deviation of the area c4, which is a z-score. Accord- 
ing a one-sided z-test a 97.596 confidence leads to the test 
statistic: A < 1.96 04, to accept the assumption that the 
region is insignificant. The size of a region is here simply 
the number of pixels. 
(Ibid) further shows that if we may assume that all co- 
ordinates are uncorrelated, than: 
n 
o2 702 Ga — yai)? (zia — Sy (13) 
i=] 
where ((zi,y;),? = 1,..,n) are the coordinates of the 
border pixels of the region and 9? the variance of the co- 
ordinates of the border pixels, which should be known a 
priori. In Stage IIc we have implemented the above ap- 
proach. It has to be emphasized that the variance of the 
coordinates should not be interpreted here as a physical 
meaningful measure, but as a measure that expresses the 
desired minimal extension of the regions. 
5 Implementation Considerations 
5.1 A Feasible Computer Implementation 
Here we treat an implementation that uses no a priori 
knowledge about initial regions. We start examining the 
image in one of its corners, in particular the left-upper cor- 
ner, but any other corner would be appropriate. Conse- 
quently the left-upper corner pixel (1,1) is the first, initial 
region, receiving label 1. So, we have to predict 41(1,2) 
from g(1,1) according Eq.( 4). If the prediction g1(1,2) is 
sufficiently close to the actual value g(1, 2), then pixel (1.2), 
receives label 1, else it receives label 2. Suppose label 1 is 
assigned to pixel (1,2). Next, pixel (1,3) is predicted from 
pixels (1, 1) and (1,2). In this way the predictor moves over 
the image with step size of one pixel. 
= 
  
| 
1 | | | 
i-4 i-3 i-2 i - 1 | 
Fig. 1 Sampling and truncation of the predictor r(p,q) — 
ezp[— ((p?4-q?)/2.?)1/] The function is truncated after i—3, 
since there the weights are becoming insignificantly small, g; 
1s estimated from g;_1, g;_, and gi-1, according the sampled 
weights. 
796 
Hn ——Á— n 
uae .0067 |.0111 mt .0015 ns 
.0015/.0183/.0821 |.1353 |.0821 |.0183 |.001 
.0067|.0821|.3679 |.6065 |.3679 |.0821 — 
gm - 
= .0111 | 
mom mI 
  
! 
  
  
  
  
  
  
  
  
  
Fig. 2 Kernel of the predictor for w — 1. 
The prediction elements (p,q) of Eq.( 4), can be pre- 
computed and stored in a half plane kernel, as shown in 
fig. 2. The kernel is truncated if its elements are becoming 
insignificant small, e.g. Etrune = 0.01, which is 1% of the 
maximum value of r(p,q) : r(0,0) = 1. The values of the 
elements of the predictor are entirely determined by w and 
the predictor size by Etrune Note that the kernel in fig. 2 is 
just an example. 
w < 1 yields a small predictor, making the prediction 
sensitive to local grey value anomalies. The grey value of 
the same cbject may change gradually, when moving from 
the one side to the other side. A large predictor is not able 
to handle such gradual grey value changes. Our experi- 
ments showed that the value of w may vary freely whitin 
the range [1.5 - 5], without affecting the final segmentation. 
To remove phantom, small and insignificant regions pro- 
duced by Stage I, in Stage II iteratively two regions are 
compared on similarity, according the t-score Eq.( 10). The 
merging of two regions, affects the statistical properties of 
the joined region and hence the t-score of the new region 
and its adjacent regions. To make the merging process or- 
der independent, first the t-scores of all adjacent regions 
are determined. Next the two regions which have the low- 
est t-score are merged. The statistics of the new region are 
computed and for all the former neighbours of the former 
two regions t-scores are computed. Next the table is traced 
from the beginning to the end again to find the smallest 
t-score. This process is repeated until no t-score exceeds 
the critical value anymore. 
5.2 Example 
We demonstrate our procedure by an example. Fig. 3 shows 
a scene with six regions. This scene is recorded as a 162 
image in the grey value range [0 — 100]. Fig. 4 shows a 
part of it. Additionally, for orientation purposes the region 
boundaries are drawn and the predictor is superimposed to 
predict pixel (8, 11). 
5.2.1 Stage I: The Prediction Stage 
The four adjacent pixels (8, 10), (7, 10), (7, 11) and (7, 12), 
all are part of different regions, 8,5,6 and 3 respectively. 
The variance of the noise is estimated from the rectangle 
with corners (2, 11) and (6, 15) yielding o, — 2.26. The pre- 
diction equation Eq.( 4) results in the figures summarized 
in table. 1. 
  
k | 9) (8,11) XQ) |z-score Ho 
8 9.75 0.8196 | 1.21 | accepted 
5 76.71 0.7967 | 36.49 | rejected 
6 
3 
  
  
  
  
  
  
  
  
89. 0.8532 | 39.93 | rejected 
80.15 0.8243 | 37.12 | rejected 
Table 1 
1: 
pi 
sh 
so 
Fig 
tio 
ad) 
(8, 
gio