Image Processing Reference
In-Depth Information
length of the corresponding interval. As r increases su
ciently, the top runs
also increase in length, whose interval searching would, therefore, be improved
by constraining the concerned intervals using both the upper and the lower
limits.
In order to find the exact value of λ(j−1), a binary search has been used.
The binary search assumes the minimum value (lower limit) as 1 and the
maximum value (upper limit) as λ(j) + 1 to start with, for finding λ(j − 1).
The binary search is performed on the Look-Up-Table, implemented in the
form of a 1-dimensional array, namely square[ ], which contains the square S
n
of each integer n = 0,1,2,...,N, where N
2
is the largest square not exceeding
the maximum value R of radius r. For example, for R = 1000, N (and the
size of the Look-Up-Table, thereof) equals 31.
It may be noted that, the binary search procedure incorporated in Algo-
rithm DCR is a modified one, based on these requirements, from the conven-
tional one found in the literature [131]. In accordance with the conventional
procedure, one has to check at first whether the middle element (m in this case)
equals the search key, failing which, one between two other checks (smaller or
greater) is performed. This modification is introduced (Steps 7-10) to reduce
the number of comparisons in each iteration of the inner while loop.
A demonstration of the algorithm DCR for r = 106 is graphically shown in
Fig. 7.14 until a run of unit length is found. For each row, the binary search is
illustrated by circular dots, where each dot corresponds to the middle element
(m) of the respective sub-array (square[s..t]). It may be noticed that, m in
Algorithm DCR (Step 6) denotes the abscissa (vertical) line x = m − 1 in
Fig. 7.14. As the binary search associated with a particular row proceeds and
converges to produce the final run of the corresponding row, the respective
dots have gradually been darkened to depict the effect of the run length finding
procedure. The end of a run at each row is emphasized by highlighted abscissa
lines passing through the endpoint of that run for visual clarity. For instance,
for the topmost row, m starts with 53, followed by 26, 13, and so on, until
s = t = 11; hence m finally becomes 11, thereby yielding the run length equal
to 11. Similarly, for the next row, since the start values of s and t are 11 and
23, respectively, the subsequent values of m are 17, 20, 19, and (finally) 18,
which makes the corresponding run length to 18−11 = 7. Thus, the run length
of a particular row (y = j) is given by the cumulative run length up to that
row minus the preceding cumulative run length, which is realized by the func-
tion include run (i,s−i,j) in Step 6 of the algorithm. The square numeric
code of a circle with radius 106 in the first octant, therefore, turns out to be
11,7,5,5,3,3,3,3,2,2,2,3,1,2,2,2,1,2,1,2,1,1,2,1,1,1,2,1,1,1,1,1, which
can be compressed to 11,7,5
2
,3
4
,2
3
,3,1,2
3
,1,2,1,2,1
2
,2,1
3
,2,1
5
, which,
in turn, can be used to easily derive the chain code representation of the
circular arc.
Implementation of the Look-Up-Table, as mentioned above, avoids
floating-point operations at any stage, such as the square root operation to
find the run for j = r in other existing algorithms, e.g., [222]. Also, the above
