Image Processing Reference
In-Depth Information
7.2.4.1
Algorithm DCS (Digital Circle Using Squares)
An algorithm for construction of digital circles can be designed, therefore,
based on (the number of) square numbers in the intervals
I 0 = [0,r−1],
I 1 = [r,3r−3],
I 2 = [3r−2,5r−7], ...,
I k = [(2k−1)r−k(k−1),(2k + 1)r−k(k + 1)−1], ....
The length of the first interval I 1 is greater than that of I 0 by r − 2, as
given by Eq. 7.4. More interestingly, for k > 1, the length of each interval
I k+1 is less than that of I k by 2, which is a constant. Hence, in the algorithm
DCS, using square numbers, we search for the number of perfect squares in
each interval I k ,k > 0, which, in turn, gives the number of grid points with
ordinate r −k. The following theorem contains the above facts and findings
in a concise way.
Theorem 7.1. The squares of abscissae of grid points lying on C 1 (o,r) and
having ordinate r−k, lie in the interval [u k ,v k := u k + l k
−1], where u k and
l k are given as follows.
u k−1 + l k−1
if k > 1
u k =
(7.5)
0
if k = 0
8
<
: l k−1
−2
if k > 2
l k =
2r−2
if k = 1
(7.6)
r
if k = 0
The proof follows from Lemma 7.2 and Lemma 7.3.
Using Theorem 7.1, therefore, the algorithm DCS (Digital Circle using
Squares) is designed as shown in Algorithm 16. It may be noted that the
(i + 1)th square number S i+1 = (i + 1) 2 can be obtained easily (without
using any multiplication) from the previous square number S i = i 2 , since
S i+1 = (i + 1) 2 = S i + 2i + 1, which is equivalent to adding a “gnomon”
[192]. This is incorporated in Algorithm DCS (Steps 5-7), where the gnomon
addition of 2i + 1 is realized by adding i with the previous square s, fol-
lowed by adding an incremented value (i + +) of i, in order to optimize the
primitive arithmetic operations. It is evident that, in Step 4, the procedure
include 8 sym points (i,j) includes the set of eight symmetric grid points,
namely, {(±x,±y) : {x}∪{y} = {i,j}}, in C Z (o,r).
7.2.4.2
Run Length Properties of Digital Circles
Using elementary tricks of number theory and mathematical induction, we
have the following lemma.
Search WWH ::




Custom Search