Image Processing Reference
In-Depth Information
ADSS may occur, which are approximately collinear, and therefore may be
combined together to form a single segment.
Let L
(k)
j
j
1
be the maximal (ordered) subset of the ADSS starting from
L
(k)
j
1
−j
1
+ 1
segments in A
k
are combined together to form a single straight line segment
starting from the start point of L
(k)
j
1
that conforms to some approximation criterion. Then these j
2
and ending at the end point of L
(k)
j
2
.
This procedure is repeated for all such maximal subsets of A
k
in succession to
obtain the polygonal approximation (in case C
k
is a closed curve) or polychain
approximation (in case C
k
.
In this algorithm, depending on the approximation criterion, we have used
a greedy method of approximating the concerned curve C
k
is open), namely P
k
, corresponding to C
k
starting from the
very first ADSS in A
k
. Determination of a minimal set of DSS (and a minimal
set A
k
is known to be
computationally intensive [115, 180]; thus for real-time applications, a near-
optimal but speedy solution is often preferred rather than the optimal one.
k
of ADSS, thereof) corresponding to a given curve C
4.3.1 Approximation Criterion
There are several variants of approximation criteria available in the lit-
erature [183]. These algorithms were tested with two variants of the approx-
imation measures using area deviation by Wall and Danielsson [210], which
are realizable in a purely integer domain subject to few primitive operations
only. The approximation criterion is defined with respect to the approximation
parameter or error tolerance, denoted by τ, as follows.
4.3.1.1 Cumulative Error
Let L
(k)
j
j
1
, be an ordered subset of A
k
as discussed above. Then under
the cumulative error criterion C
P
−j
1
+ 1 in number) in A
k
are replaced by a single straight line segment starting from the start point of
L
(k)
j
1
, the ADSS (j
2
and finishing at the end point of L
(k)
j
2
, if:
△
j
2
−1
X
s(L
(k)
j
1
), e(L
(k)
), e(L
(k)
s(L
(k)
j
1
), e(L
(k)
j
2
)
6 τd
⊤
j
2
)
(4.10)
j
j=j
1
where, s(L
(k)
j
) and e(L
(k
j
) represent the respective start point and the end
point of the ADSS L
(k
j
, etc. The start point of L
(k
j
coincides with the end
point of the preceding ADSS, if any, in A
k
, and the end point of L
(k
j
coincides
with the succeeding one, if any. In Eq. 4.10, |△(p,q,r)| denotes twice the
magnitude of area of the triangle with vertices p = (x
p
,y
p
), q = (x
q
,y
q
), and
r = (x
r
,y
r
), and d
⊤
(p,q) the maximum isothetic distance between two points
p and q. Since all these points are in two-dimensional digital space, the above
measures are computable in the integer domain as shown in the following
equations.
d
⊤
(p,q) = max{|x
p
−x
q
|,|y
p
−y
q
|}
(4.11)
