4).
level and shape information. The decision making
procedure for merging is similar as in last step.
But in this case, a candidate region is choosed if it
has the minimal length measure by. formula (3)
suppose it merges with region i, (we still use Fig.3
as example), compared with other regions
surrounding region i, For selected candidate
region i, it merges with region i, if the MDL
measurement after merging is smaller than the sum
of individual MDL measurements from two
regions before the merging.
We can express such procedure more rigorously in
mathematic formula as the following:
Denoting R* as the i^ region at k-stage merging
(each region under each level is uniquely and
sequentially labelled)
for each region i, in k^ merging result,
RF E RU RI
f LR/UR) LR) «I) — (9
where
R* is (k+1)™ merging result from current
regions i, and candidate region i,. After each level
of merging, labels are updated to produce a unique
and sequential label for each region. So j has not
necessarily same label value as i, in k? level.
and,
candidate region i, is decided by
LR, UR) < LR! URRY (5)
for all 1 (i, and 1 is the neighbours of i,).
removing small abnormal regions. In this step,
small abnormal regions are merged with an
adjacent larger regions. The existence of small
abnormal regions may be due to: a), there are
small objects on the big object surfaces, and these
small objects are out of our interest; b), the
existence of high-frequency noises on the image.
For this purpose, formula (5) is still used to find
most suitable big region. Sometime, several small
areas can congregate together, which make it
impossible to find a direct neighbouring big region
to merge with. Under this circumstance, algorithm
should allow current small region to jump over
neighbouring small regions to the nearest big
region.
724
5. BOUNDARY FITTING ALGORITHM
Boundary fitting, or curve fitting belongs to the problem
of shape analysis, which deals with using minimum
number of points to represent a curve under the certain
criterion for error because of data reduction. It is the core
issue in the line generalization of Cartography. Our
problem here is slightly different in the way that we have
some assumptions: 1) the boundary for a region is closed;
2), object models are known, or in other words, some
properties of shape for objects are a priori knowledge,
among other assumptions if specified by the applications.
Such assumptions or a priori knowledge will greatly
reduce the complexity of curve fitting. In the following,
we introduce our approach on optimal curve fitting of the
region boundary under the assumption that the boundary
only consists of straight line segments, and the number of
the segments is known or only has a limited number of
choice.
Under our assumptions, the number of line segments (say
N) is known beforehand (we will discuss later on how to
decide the number of line segments), remaining problem
is therefore how to determine the positions of nodes
which connect the line segments which should be as
closed as possible to the original boundary. The general
idea of our algorithm is to iteratively fix (N-1) number of
nodes, find the optimal position for the remaining node.
When the number of points in the original boundary data
is large, such iterative procedure can take quite a lot of
time. In order to speed up, we first perform the gaussian
laplacian filter to detect high curvature points, and use
these points as the candidate points for nodes. The
algorithm flow is illustrated in Fig.4 (located after the
"references"). In the following, we give the explanation
on the items in Fig.4.
* Gaussian Laplacian Filter
The Gaussian function is given by
1 n
20 = re 2% (6)
2x0
and the second derivative is equal to
2
; (7)
gg" = C(c? = t?)e 20?
where C is a constant.
Mathematically a convolution may be expressed
as:
FQ) - fo)*gG) (8)
When applying gaussian Laplacian filter g"(t) to
the region boundary, we have to calculate the
boundary curvature from boundary chain code by
the following equation:
