Image Processing Reference
In-Depth Information
Algorithm 8: Algorithm MERGE-ADSS for polygonal approximation
of a sequence of ADSS in A using criterion C
max
.
Algorithm MERGE-ADSS(A, n, τ)
1. for m ← 1 to n
2.
for S ← 0, i ← 1 to (n−m−1)
3.
S ← S +△(A[m],A[m + i],A[m + i + 1])
4.
dx ←|A[m].x −A[m + i + 1].x|
5.
dy ←|A[m].y −A[m + i + 1].y|
6.
d ← max{dx, dy}
7.
if S 6 dτ
8.
delete A[m+i] from A
9.
else
10.
break
11.
m ← m + i−1
such that the isothetic distance of p from DSL passing through the end points
of L
(k
j
exceeds unity (as testified in our experiments). Although for su
ciently
long ADSS, this may not hold for the underlying conditions (c1) and (c2)
as stated in Sec. 4.2.1; however, in our experiments with real-world images,
this was found to hold. In the case of any violation, some heuristics may be
employed to find the error points and to find smaller ADSS to resolve the
problem.
4.3.2 Algorithm for Polygonal Approximation
The algorithm for polygonal approximation of a sequence of ADSS in the
set A, using the approximation criterion of Eq. 4.10, is described in Algo-
rithm 8. To take care of the criterion C
max
of Eq. 4.13, a similar procedure
may be written.
Final Time Complexity: As explained in Sec. 4.2.2, the time complexity for
extracting the ADSS in a set of digital curves, I = {C
k
}
k=1
, is given by
Θ(N
1
)+Θ(N
2
)+...+Θ(N
K
) = Θ(N), where N(= N
1
+N
2
+...+N
K
) is the
total number of points representing I. Now, in the algorithm MERGE-ADSS,
we have considered only the ordered set of vertices of the ADSS corresponding
to the curves, so that the worst-case time complexity in this stage is linear
in N. Hence, the overall time complexity is given by Θ(N) + O(N) = Θ(N),
regardless of the error of approximation τ.
4.3.3 Quality of Approximation
The goodness of an algorithm for polygonal approximation is quantified, in
general, by the amount of discrepancy between the approximate polygon(s) (or
