Image Processing Reference
In-Depth Information
polychain(s)) and the original set of digital curves. There are several measures
to assess the approximation of a curve C
k
, such as
(i) compression ratio CR = N
k
/M
k
, where N
k
is the number of points in
C
k
and M
k
is the number of vertices in the approximate polygon P
k
;
(ii) the integral square error (ISE) between C
k
and P
k
.
Since there is always a trade-off between CR and ISE, other measures may
also be used [97], [184], [187]. These measures, however, may not always be
suitable for some intricate approximation criterion. For example, the figure
of merit [187], given by FOM = CR/ISE, may not be suitable for comparing
approximations for some common cases, as shown in [183]. In [208], the per-
centage relative difference, given by ((E
approx
−E
opt
)/E
opt
) × 100, has been
used, where E
approx
is the error incurred by a suboptimal algorithm under
consideration, and E
opt
the error incurred by the optimal algorithm, under
the assumption that same number of vertices are produced by both the algo-
rithms. Similarly, one may use two components, namely fidelity and e
ciency,
given by (E
opt
/E
approx
)×100 and (M
opt
/M
approx
)×100, respectively, where
M
approx
is the number of vertices in the approximating polygon produced
by the suboptimal algorithm and M
opt
is the same produced by the optimal
algorithm subject to same E
approx
as the suboptimal one [183].
The algorithm presented here is not constrained by the number of vertices
M
k
of the output polygon P
k
, and therefore, the measures of approximation
where M
k
acts as an invariant, are not applicable. Instead, we have considered
the error of approximation, namely τ, as the sole parameter in our algorithm,
depending on which, the number of vertices M
k
corresponding to P
k
will
change. A high value of τ indicates a loose or slacked approximation, whence
the number of vertices M
k
decreases automatically, whereas a low value of
τ implies a tight approximation, thereby increasing the number of vertices
in the approximate polygon. Hence, in accordance with the usage of τ in
both the methods, one based on criterion C
and the other on C
max
, the
total number of vertices M = M
1
+ M
2
+ ... + M
K
in a set of approximate
polygons {P
P
}
k=1
corresponding to the input set of digital curves, namely
k
}
k=1
, versus τ, provides the necessary quality of approximation. Since
the total number of points lying on all the points in I characterizes (to some
extent) the complexity of I, we consider the compression ratio (CR) as a
possible measure of approximation.
Another measure of approximation is given by how much a particular point
(x,y) ∈C
I = {C
k
y) is
the point in P
k
corresponding to p = (x,y) in I, then for all points in I, this
measure is captured by the variation of the number of points with isothetic
deviation d
⊥
with respect to d
⊥
, where the (isothetic) deviation from p to
∈I has deviated in the corresponding polygon P
k
. If
p = (
x,
k
p
is given by
dev
⊥
(p →
p) = min{|x−
x|,|y−
y|}.
(4.14)
Further, since dev
⊥
(p →
p) depends on the chosen value of τ in our algorithm,
the fraction of the number of points in I with deviation d
⊥
varies plausibly
