gion 
in peak 
e model 
10ise 
ling the 
cost of 
ropy for 
omalous 
1. 
mula to 
hat each 
straight 
ation is 
nt to the 
gue that 
ntensity 
ise the 
> range 
o apply 
simply 
le curve 
urve. In 
tape as 
poses a 
line, its 
1 states 
e chord 
s-board 
10where 
ider the 
roperty 
jy their 
optimal 
nents is 
shape is 
2) 
ipe of a 
undary 
; on the 
> chord 
m, : number of outliers 
D,D,: number of pixels along x and y direction 
of the image 
In accordance with (1), we also use 4 items encoding the 
shape of regions. For the points on the curve which meet 
the chord condition, no additional coding is needed as far 
as the nodes specifying the straight line segments are 
known, so first item in this case is zero. The second item 
in (2) is the number of bits describing the outliers. If the 
boundary is encoded in Freeman chain code, 3 bits is 
required to store each pixel (for 8 directions). But if we 
store the edges between the pixels instead of pixels 
themselves, only 2 bits is necessary (for 4 directions) 
(Such way of representing the boundary allows us to 
depict closed region, single line as well as point). The 
third term is in the same meaning as equation (1). The 
final component is used for the coding of nodes 
connecting straight line segments. 
Finally, the total information required to describe a region 
considering intensity and shape is the sum of L, and L,, 
namely, 
Lcd Ly (3) 
4. REGION GROWING ALGORITHM 
The region growing algorithms in the literature can be 
classified into three categories: pure merging, pure 
splitting. and split-and-merge schemes. In the first 
scheme, the picture is first divided into many small 
primitive regions (even pixels) which are then merged to 
form larger regions on the basis of certain homogenous 
criterion. In contrast, a pure split method views the entire 
image as the initial segmentation. Then, it successively 
splits each current segment into if the segment is not 
homogenous enough. In split-and-merge scheme, the 
efficiency of processing is improved by first partitioning 
the image into square subregions and then splitting them 
further if they are not homogeneous. Afterward, a 
merging process is applied to those adjacent segments that 
satisfy some uniformity criterion. Pyramid quad structures 
is often employed as the basic data structure. A detailed 
implementation on split-and-merge scheme can be found 
in [Chen]. 
root node 
lowest level 
Fig.2 
In order to implement our philosophy, quad tree structure 
723 
is not quite valid because we consider that the splitting 
and merging in this data structure is usually not carried 
out on where the real object region boundary occurs. 
When we want to interactively include the shape as one 
important component of region uniformity, we have to 
find out a data structure which can describe each region 
more directly. Therefore, "N-node tree" has been 
developed in our current algorithm. An example of "N- 
node tree" is illustrated in Fig.2 . 
One can view "N-node tree" as a generalization of quad 
tree data structure in the sense that while number of 
children under a node in quad tree is fixed to 4, the "N- 
node tree" decides the number of children according to 
the number of small regions from which the big region 
merges. In Fig.2, the lowest level of the tree is actually 
the original image pixels which is indexed from left to 
right, up to down on the image, and the top level or root 
node represents the whole image. The intermediate levels 
of the tree describes the segmentation results at different 
stages. One node on each level represents a complete 
region which has a unique and sequential label on this 
level. The original image and the segmented regions can 
be corresponded via tracing through the "N-node tree". In 
practice, a label image, which has the same size as the 
original image, is created and is valued by its 
corresponding label in order to facilitate the indexing. 
The whole segmentation procedure is carried out in 4 
phases: 
1). forming lowest level of the tree. It is a simple 
indexing which puts original raster image pixel 
into the lowest level of the tree. 
fim 
bd 
Fig.3 
2) initial merging based on statistical test on image 
intensity. It is a traditional method used in split- 
and-merge algorithm, which examine the merging 
result with the previous small regions using 
statistical method to decide whether such merging 
is good or not. The decision making for merging 
is shown in Fig.3. For region i,, in order to find 
the neighbour region to merge with, all the regions 
surrounding region i, should be examined and the 
one having most closed uniformity with region i, 
is selected as candidate region to merge with 
(say,e.g. region i,). If uniformity measurement of 
region i, and i, is within certain threshold, these 
two regions are merged to form big region. This 
step can be regarded as providing hypothesis for 
possible homogeneous regions. 
3). adaptive merging based on MDL, combining grey