mic 
r in 
rval 
‚the 
ted, 
the 
n be 
hing 
are 
inge 
the 
tor 
is 
ind 
els 
> as 
the 
the 
Vi- 
ike 
Le. 
the 
ing 
ove 
ıt a 
rey 
gh- 
led. 
ove 
lary 
igh 
and 
also 
the 
inct 
ear 
1di- 
the 
age 
of 
the 
neighbouring points) of line/edge is above a certain 
threshold, the line/edgeis preserved (i.e. not replaced by 
the average for smoothing). 
Because smoothing with averages given in real values 
which have to be rounded off, therefor, it converges 
slowly in repeated applications of conditional smoothing, 
a better alternative is to take the median values of 
adjacent pixels instead of the average value. The Condi- 
tional Rankorder Operator has been developed according 
to this principle, which increases the rate of convergence 
[Mulder & Sijmons, 1984]. 
Based on the idea of conditional smoothing, this 
improved alternative method for line/edge feature 
enhancement is the following: If we use a 3x3 operator, 
the input subimage array is defined with linear index k: 
  
  
  
Li 2} 3 
subimage [k] k = 4l. 51..6 
7| 8| 9 
  
  
  
  
  
subimage [5] is the central pixel grey value, then the 9 
values (0-255) of subimage are sorted into array rank[r] 
with r=1 the lowest value, r=5 the median value and r=9 
the highest value in rank[r]. 
General algorithm: 
do for all samples I, J 
get 3x3 subimage at I, J and its 8 adjacent pixels 
sort subimage [1...9] into rank [1...9] 
IF ABS(subimage [5] - rank [r]) «threshold 
THEN subimage [5] =rank [r] 
ELSE subimage [5] =subimage [5] 
repeat the algorithm (the old output is the new input) 
until the result converges to stable output values. If we 
select r-5 (i.e. the median value), it is the Conditional 
Median Rankorder Operator. This operator has the 
property of noise removal and it will converge segments 
(thick line also) to their median value (i. e. rank [5]) but 
still keeps every kind of line/edgefeatures. 
The condition on the difference between the central pixel 
value and the median value can be interpreted as an 
estimate of a Laplacian in a noisy environment. Estima- 
tion of a Laplacian in this way approximates that of the 
method of polynomial surface fitting for finding second 
order differences in a noisy subimage [Haralick, 1984]. 
The Conditional Rankorder Operator takes the neigh- 
bourhood lower value (e.g. use rank [2] instead of rank 
[5]) as the "relative" low pass filter to remove noise but 
shrink the high grey value and then take the neighbour- 
hood higher value (e. g. rank [8]) with the same number 
of iterations to expand (restore) the high value to the 
proper size [Sijmons, 1986]. The conditional rankorder 
operator can smooth the region inside the edges and 
remove the noise, but the linear features are enhanced 
(their original intensity have been changed), for matching 
purpose, it is better that all linear features keep their 
original grey value without any change. 
3. IMAGE SEGMENTATION AND 
BOUNDARY DETECTION 
AT] 
3.1 Image segmentation by region growing schemes 
There are several image segmentation techniques, some 
of them are for general purpose and some are designed 
for specific classes of images. These techniques can be 
classed as : (a) Single linkage region growing schemes, 
(b) Hybrid linkage region growing schemes, (c) Centroid 
linkage region growing schemes (d) Split and merge 
schemes, (e) Measurement space guided spatial cluster- 
ing, and (f) Spatial clustering schemes. (a) are the 
simplest and most prone to the unwanted region merge 
errors; (b) and (c) are better in this regard; (d) is not as 
subject to an unwanted region error, but it suffers large 
memory usage and excessively blocky region boundaries; 
(e) tends to avoid both the merge errors and blocky 
problems because of its primary reliance on measurement 
space, but the regions produced are not smoothly 
bounded, and they often have holes, giving the effect of 
salt and pepper noise. (f) may be better in this regard. (b) 
appear to offer the best compromise between having 
smooth boundaries and few unwanted region merges 
[Haralick & Shapiro,1985]. 
Before starting the Hybrid linkage region growing 
schemes, we scan the image pixel by pixel with a 3x3 
patch, if the intensity of the pixels in the patch is the 
same, we use that patch as a "seed" for region growing. 
Starting with each seed, the neighbour pixels are checked 
and merged into a region if it is in a homogeneous area. 
Before region growing, all pixels are assigned by label 0. 
During the pixel merge, pixel i of region R wants to 
check pixel j whether it can be merged or not,the deci- 
sion is made by the condition: 
grey(i) - grey(j) <T, T =K /ag (1) 
where K is a experimental value (e.g. K=30),ag is the 
average gradient of grey value of 8 neighbour of pixel j, 
if the condition is met, pixel j is marked a label as a 
indication that this pixel belongs to region R. If some 
small region exist among big region or inside the big 
region, we merge this small region as it is not good for 
region matching. 
3.2 Boundary detection 
After segmentation, all pixels are labelled, we scan the 
whole image pixel by pixel with a 3x3 window. Within 
the window, if only one neighbourhood pixel (in horizon- 
tal direction) of central pixel has same label, this central 
pixel is the boundary pixel, or if only one neighbourhood 
pixel (in vertical direction) of central pixel has same 
label, this central pixel is the boundary pixel also. Then, 
we get the map of the region boundary. 
4. REGION MATCHING BY 
RELAXATION PROCESS 
4.1 Boundary description and comparison 
Before region matching, the shape of region needs to 
quantify for comparison, the w-s curve is a good method 
for shape description [Baruch & Loew,1988]. According 
to the slop between two pixels on the boundary, the