Image Segmentation - Bezier and Splines in Image Processing and Machine Vision - page 46

e i l ( u, v )= g ( u, v )

− s pp ( u, v ) , i =1 , 2 , ··· k dl =1 , 2 , ··· ,N i .

Each of these error surface patches is approximated locally using a fixed or
variable order polynomial. A schematic description of variable order local
surface approximation is given below.
Algorithm local approx ( input image, th, a , q, p )
begin
step 1: find the most dispersed region, Ω k in the input image; find
the residual error surface for it with respect to order q ;
step 2: find p using the Algorithm global approx ( Ω k , th, a , p );
step 3: if p

q , a pre-assigned positive integer then goto step 4 else
assign an index for the region and return p;
step 4: stop;
end ;
To summarize, this scheme is a two stage process. In stage 1, first deter-
mine a threshold. This threshold partitions an image into two subimages, F 01
and F 02 . Determine the order of a polynomial minimizing unweighted least
square error for approximating a subimage F 01 . If the order of the polynomial
is less than a predefined order, say, q then accept the partition F 01 ,elsedo
a local correction for one or more regions. Local correction is always with
respect to the global surface of order q. If the global approximation together
with local correction(s) is all right, then accept the subimage, F 01 , else com-
pute a new threshold to subdivide F 01 into F 011 and F 012 . The process goes on
subdividing the subimages hierarchically until all of them are approximated
by global approx and local approx . The same is also true for F 02 . The segmen-
tation algorithm may produce some small isolated patches. After the partition
of the entire image, all single pixel and small regions or patches are merged
to the neighboring regions depending on some criteria, which are described
in section 2.4.5. Note that all approximations in stage 1 are unweighted, i.e.,
W ( i, j )=1

≥

i, j in approximation algorithms. In stage 2, for encoding one
can approximate the subimages minimizing a weighted least square error with
a polynomial of the same order as determined in stage 1. The same order can
be used because the order (global and also local) of a subimage or the nature
of approximation is not expected to change due to merging of small regions.
However, one can once again find the order of approximation before encoding.

∀

2.4.5 Merging of Small Regions

Merge is always used for better segmentation. Obviously, small noninformative
regions are merged to nearby regions. Two issues are raised: which regions are
to be merged and where are they to be merged. In order to detect regions of
small size for possible merge to one of its neighboring regions, a merge index
is often very helpful. Consider a merge index, MI, as the ratio of a measure
of within region interactions to that of between regions interactions. Assume
that for a nontrivial region, the within region interaction should be more than