Image Processing Reference
In-Depth Information
FIGURE 5.2: Digitization of a circle with r
o
= 9.7, where (9,3) defines r
l
and (9,4) defines r
u
(Example 5.2).
Reprinted from
CVGIP: Graphical Models and Image Processing
, 54(5)(1992), S. Chattopadhyay et al., Parameter Es-
timation and Reconstruction of Digital Conics in Normal Positions, 385-395, Copyright (1992), with permission
from Elsevier.
It is immediately evident that r
l
6 r
o
< r
u
.
Theorem 5.1. r
l
6 r < r
u
if and only if D(C(r)) = D
o
. In other words,
Domain(D
o
) = [r
l
,r
u
).
Proof: The proof follows from the definitions of r
l
and r
u
.
€
Example 5.2. Let r
o
= 9.7. So, D
o
X
= D
Y
= {9,9,9,9,8,8,7,6,5,3}.
Clearly, r
l
=
√
√
(9
2
+ 3
2
) =
(9
2
+ 4
2
) =
97 =
9.8489, and any C(r) with r lying between 9.4868 and 9.8489 will have the
same digitization. The situation is shown in Fig. 5.2.
r
l
and r
u
can be interpreted geometrically too. Let A be the farthest point
from origin O in D
o
. Then r
l
= OA. A circle with radius r
l
has the same
digitization as D
o
. Any circle with r < r
l
misses the point A from D(C(r)).
Note that r
l
is expressible as a sum of two perfect squares. Now to find r
u
search for the least integer greater than r
l
that can be expressed as the sum of
the squares of two integers i and j. Set the sum to r
u
= i
2
+ j
2
. So any circle
with r > r
u
includes the point (i,j) extra in H(C(r)) with respect to H(C(r
o
))
where H(C(r)) denotes the set of grid points contained in a canonical circle
of radius r. As r
u
is the least such number, a continuous dilation of the circle
C(r) from r = r
l
first hits a grid point (i,j). Hence, for all r, r
l
6 r < r
u
we have D = D
o
. The situation is depicted in Fig. 5.2, for example, with the
point (i,j) marked with a dot. Note that none of 91, 92, 93, 94, 95, 96 can be
expressed as a sum of two squares.
90 = 9.4868 and r
u
=
