Image Processing Reference
In-Depth Information
1 1 1
△(p,q,r) =
x
p
x
q
x
r
y
p
y
q
y
r
(4.12)
From Eq. 4.12, it is evident that △(p,q,r) is a determinant that gives twice
the signed area of the triangle with vertices p, q, and r. Hence, the ADSS in
the given subset are merged to form a single straight line segment, say
L,
provided the cumulative area of the triangles (j
2
L as
base and the third vertices being the end points of the ADSS (excepting the
last one) in the subset L
(k)
j
j
1
, does not exceed the area of the triangle with
base
−j
1
in number), having
L (isothetic length) and height τ.
4.3.1.2
Maximum Error
With similar notations as mentioned above, using the maximum error crite-
rion C
max
, the ADSS in L
(k)
j
j
1
would be replaced by a single piece, provided
the following condition is satisfied.
△
s(L
(k)
j
1
), e(L
(k)
), e(L
(k)
s(L
(k)
j
1
), e(L
(k)
max
j
1
jj
2
−1
j
2
)
6 τd
⊤
j
2
)
(4.13)
j
The rationale of considering two such criteria are as follows. Since we
would be replacing a number of ADSS, which are almost straight, and more
importantly, are not ordinary digital curves of arbitrary patterns and arbitrary
curvatures, the end point of each ADSS makes a triangle with the replacing
segment, namely
L; wherefore the sum of the areas of triangles formed by
the end points of these ADSS in combination with the replacing line
L gives
a measure of error due to approximation of all ADSS in L
(k)
j
j
1
L. Al-
ternatively, if we are guided by the worst-case approximation, that is, if the
mostly digressing ADSS is considered to estimate the error, then the maxi-
mum of the areas of these triangles should be considered as the error measure
for approximation of worst ADSS in L
(k)
j
j
1
by
by
L.
Empirical observations as reported in [13], reveal that the above two cri-
teria are essentially similar in the sense that they produce almost identical
polygons for different digital curves for different values of the error tolerance
(i.e., τ). This is quite expected as far as the output is concerned.
As mentioned earlier in Sec. 4.3, to construct a polygonal approximation
we consider the start point of the first ADSS (i.e., L
(k)
j
1
), and the end point of
the last ADSS (i.e., L
(k)
j
2
). This can by justified as follows.
Fact 1. The sum (for criterion C
P
) or the maximum (for criterion C
max
) of
the isothetic distances of the end points of each ADSS from the replacing line
L
never exceeds the specified error tolerance τ. This follows easily on expansion
of the left hand-side of the corresponding Eqns. 4.10 and 4.13, and from the
fact that the term d
⊤
s(L
(k)
j
1
),e(L
(k)
j
2
)
represents the isothetic length of
L.
Fact 2. Since each ADSS L
(k)
j
is approximately a DSS, we consider ∄p ∈ L
(k)
j
,
