Image Processing Reference
In-Depth Information
Algorithm 17: Algorithm DCR Using Run Length Properties in Part
(See Text for Explanation).
Algorithm DCR (
INT
r)
1.
INT
i ← 0, j ← r, s ← 0, w ← r −1, t ← r, m
2.
INT
l ← 2w
3. while (j > i)
4.
while (s < t)
5.
m ← s + t
6.
m ← m/2
7.
if (w 6 square[m])
8.
t ← m
9.
else
10.
s ← m + 1
11.
if (w < square[s])
12.
s ← s−1
13.
s ← s + 1
14.
include run (i, s−i, j)
15.
t ← 2s−i + 1
16.
i ← s
17.
w ← w + l
18.
l ← l −2
19.
j ← j −1
r > 2, is given by
λ(j) −1
2
λ(j −1) >
−1.
€
Combining Theorem 7.2 and Theorem 7.3, therefore, we obtain Eq. 7.7,
which can be used to derive the horizontal run of grid points with ordinate j−
1, from the previous run with ordinate j, for j 6 r.
λ(j) −1
2
−1 6 λ(j −1) 6 λ(j) + 1
(7.7)
The algorithm DCR (Digital Circle using Run-lengths), which incorporates
the relation between the consecutive runs, as captured in Eq. 7.7, is given in
Algorithm 17. In this algorithm, only the upper limit (λ(j) + 1) of the term
λ(j−1) has been considered for simplicity. The lower limit (
1
−1)
of λ(j−1) may be considered in a similar fashion. Since we search for λ(j−1)
in an integer interval whose upper and lower limits are computed every time
using its preceding run length, λ(j), resorting to both the limits in the run-
finding procedure is computationally effective for a su
ciently large value of
λ(j − 1). Computation of the lower (or upper) limit involves a fixed number
of operations, whereas the operations in a binary search is logarithmic on the
2
(λ(j) −1)
