Image Processing Reference
In-Depth Information
Lemma 5.5. If r = x
q
+ 1, then y
r
= q − 1 where p,q,x
q
,y
p
are as defined
in Eq. 5.1 [41].
FIGURE 5.4: Proof of Lemma 5.5. “∗” ∈ E
o
and “.” ∈ E
ul
.
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.
Proof: From the definitions of D
X
and D
Y
, y
r
6 q − 1 (Fig. 5.4). Next,
let us show that x
q−1
> x
q
. In general, x
q−1
> x
q
. If x
q−1
= x
q
, then from
the definition of a
u
, (x
q
+ 1)/
(1 − (q − 1)
2
/b
l
)
or q
2
< (q − 1)
2
. This is a contradiction. So, x
q−1
> x
q
+ 1 = r. But then
y
r
> q−1. Hence, y
r
= q−1.
(1 − q
2
/b
l
) < (x
q
+ 1)/
€
Note that in Example 5.4, q = 3 and x
q
= 11. So, r = 12 and y
r
= 2.
Lemma 5.6. D(E
ul
) differs from D
o
only at point(s) like (x
q
+ 1,q) where
a
u
is (are) achieved [41].
Proof: It is easy to see that D
o
⊆ H(E
ul
) where H(E) denotes the set
of all grid points lying inside the first quadrant of an ellipse E. Consider
any (x
i
,i) ∈ D
o
X
such that (x
i
,i) ∈ D
X
(E
ul
). Now, if (x
∗
i
,i) ∈ D
X
(E
ul
),
then x
∗
i
> x
i
+ 1. But in that case either i = q and x
∗
i
= x
∗
q
= x
q
+ 1 or
i = q and x
q
> x
q
+ 1. If i = q, then the a
u
−b
l
iteration would have stopped
with a higher a
u
and lower b
l
at (x
i
+ 1,i). Hence, i = q. Next consider a
(i,y
i
) ∈ D
Y
∗
and ∈ D
Y
(E
ul
). So, there exists (i,y
∗
i
) ∈ D
Y
(E
ul
) such that
y
∗
i
> y
i
. But this contradicts the construction of b
l
. Hence, the result.
€
Now let us introduce a definition for comparing the digitization of an
arbitrary ellipse with the given digitization.
Definition 5.4. We write D
X
= D
X
(E) 6 D
o
X
iff ∀i,0 6 i 6
⌊b
o
⌋, ⌊a
(1−
i
2
/b
2
)⌋
6 x
i
where E = E(a,b) is an arbitrary ellipse for some a and b.
D
X
> D
o
X
,D
Y
6 D
Y
and D
Y
> D
Y
are defined analogously.
€
For an arbitrary ellipse E, X- and Y-digitizations are said to be consistent
iff D
X
6 D
o
X
implies D
Y
6 D
Y
and vice versa. The former case is represented
by D 6 D
o
and the latter as D > D
o
.
We prove, in the next theorem, the main result for reconstruction.