Image Processing Reference
In-Depth Information
Algorithm 16: Algorithm DCS.
Algorithm DCS (
INT
r)
1.
INT
i ← 0, j ← r, s ← 0, w ← r −1
2.
INT
l ← 2w
3. while (j > i) do
4.
include 8 sym points
(i, j)
5.
s ← s + i
6.
i ← i + 1
7.
s ← s + i while (s 6 w)
8.
w ← w + l
9.
l ← l −2
10.
j ← j −1
Lemma 7.4. The number of perfect squares in a closed interval [v,w] is at
most one more than the number of perfect squares in the preceding closed
interval [u,v−1] of equal length, where the intervals are taken from the non-
negative integer axis.
€
Now, from Lemma 7.3 it is obvious that the length of the interval contain-
ing the squares of abscissae (of grid points of C
1
(o,r)) with ordinate j−1, is 2
less than that corresponding to ordinate j. Even if the interval corresponding
to ordinate j − 1 had been equal in length to the preceding interval corre-
sponding to ordinate j, then from Lemma 7.4, the maximum number of grid
points with ordinate j−1 would not have exceeded one more than the number
of grid points with ordinate j. Hence we have the following theorem.
Theorem 7.2. The run length of grid points of C
1
(o,r) with ordinate j − 1
never exceeds one more than the run length of its grid points with ordinate j.
€
Theorem 7.2 provides a good and useful upper bound on the number of grid
points with ordinate j with respect to that corresponding to ordinate j − 1.
The derivation of the lower bound that we have obtained is, however, not as
so straightforward. See [14] for a detailed discussion on the lower bound. The
first useful lemma for this is as follows.
Lemma 7.5. If [u,v− 1] be the interval I
k
,k > 1, and [v,w] be the interval
of same length as [u,v−1], then the number of perfect squares in [v,w] is at
least (floor of) half the number of perfect squares less one in [u,v−1].
€
Putting together the above findings, therefore, we get the following theo-
rem, which captures the run length properties of a digital circle in a precise
form.
Theorem 7.3. If λ(j) is the run length of grid points of C
1
(o,r) with ordi-
nate j, then the run length of grid points with ordinate j−1 for j 6 r−1 and
