Image Processing Reference
In-Depth Information
(a) k = 3: η = 8.
(b) k = 4: η = 8.
(c) k = 7: η = 0.
FIGURE 7.12: Approximate regular 2k-gons for k = 3, 4, and 7 correspond-
ing to the digital circle of radius 8. An error point is a point that lies inside the
polygon but outside the digital circle [15]. Error points for k = 4 are given by
{(i,j) : {|i|,|j|} = {3,8}}. For other values of k, the corresponding errors are
η(k = 2) = 68, η(k = 3) = 18, η(k = 5) = 8, η(k = 6) = 4, and η(k > 7) = 0.
then we include the point (x,y,z + 1) in C
Z
i+1
between (x,y,z) ∈ C
Z
i+1
(x−1,y,z + 1) ∈C
Z
i+1
.
Thus, depending on Case 1 and Case 2, we detect and include the missing
voxels for S
G
. Finally, the 8-axis symmetry of digital circles [84] is used to
complete the digitally connected and irreducible surface of revolution from
Octant 1 (Fig. 7.10).
7.2.4 Number-Theoretic Approach
In this approach, certain number-theoretic concepts have been used in
designing an e
cient algorithm for the construction of the digital surface of
revolution. These number-theoretic concepts are discussed in detail in [14].
The number-theoretic algorithm is particularly useful (apropos its speed and
e
ciency) when we have to construct a large number of digital circles that are
mostly of high radii. Essentially, the algorithm is different in principle from
the algorithms that were developed in the early period of scan-conversion
[29, 52, 75, 100, 124, 165, 193], and it has also some distinguishing features
that are notably different from the ones proposed in later periods [20, 30,
101, 140, 203, 214, 218]. The work in [222] has also shown that the notion of
number theory is indeed useful for generating a large number of digital circles.
The previous algorithms essentially resort to appropriate digitization (i.e.,
computation of numeric differences) of 1st-order and 2nd-order derivatives,
which are mostly useful to analyze and solve problems involving curves and
curve segments in the Euclidean/real plane.
As shown in [14], for a radius exceeding 100 or so, the number-theoretic
technique has appreciable margin over Bresenham's algorithm [29]. Further,
