Image Processing Reference
In-Depth Information
Theorem 5.5. If (a,b) ∈R
ul
, then either D 6 D
o
or D > D
o
[42].
Proof: First let us prove that if (a,b) ∈ R
ul
, then the following hold: (A)
D
Y
6 D
Y
or D
Y
> D
Y
and (B) D
X
6 D
o
X
or D
o
X
> D
o
X
.
If both a and b are less (or greater) than a
o
and b
o
, respectively, then it is
trivial to see that D
X
6 D
o
X
and D
Y
6 D
Y
(or D
o
X
> D
o
X
and D
Y
> D
Y
).
So we have another case to settle here where one of a or b is less than
a
o
or b
o
and the other is greater. Without any loss of generality, let us take
b
l
< b < b
o
and a
u
> a > a
o
. We prove that D > D
o
. Let us first assume the
converse of D
Y
> D
Y
i.e., ∃i⌊b
(1 −i
2
/a
2
)⌋ < y
i
. Now, if E ∩E
o
= (x
′
,y
′
)
and E ∩E
ul
= (x
′′
,y
′′
), then from Lemma 5.2, we get x
′′
> x
′
> i. But then
⌊b
l
(1 −i
2
/a
u
) which
contradicts the definition of b
l
and no such i can exist. Hence, D
Y
> D
Y
.
Now assume the converse of D
X
> D
o
X
, i.e., there exists some j, such that
(1 −i
2
/a
u
)⌋
(1 −i
2
/a
2
)⌋ < y
i
. So, b
l
< y
i
/
6
⌊b
(1 − j
2
/b
2
)⌋ < x
j
= r, say. Clearly, (x
j
,j) ∈ H(E(a,b)) and ⌊b
⌊a
(1 −
r
2
/a
2
)⌋ < j. Again y
r
> j as r = x
j
. Therefore, there exists one r, such that
⌊b
(1−r
2
/a
2
)⌋ < y
r
, which contradicts D
Y
> D
Y
. Hence, D
X
> D
o
X
. Thus,
D 6 D
o
if a < a
o
and b > b
o
and D > D
o
otherwise.
€
A reconstruction algorithm from the digitization is now available. We
present it in the next subsection.
5.3.2 The Reconstruction Algorithm
A simple binary-search-like algorithm, similar to the one used for circles
in [157], is presented in Algorithm 9 to find a pair of a and b such that
D(E(a,b)) = D
o
.
Algorithm 9: Reconstruction of Ellipse
Algorithm Reconstruct Ellipse
Input: Digitization D
o
Output: A pair of a,b such that D(E(a,b)) = D
o
Method:
1. b = (b
l
+ b
u
)/2;a = (a
l
+ a
u
)/2;a
L
= a
l
;a
R
= a
u
2. while D = D
o
do
begin if D 6 D
o
then begin a
L
= a; a = (a + a
R
)/2;end
else begin a
R
= a;a = (a
L
+ a)/2; end;
end;
3. write (a,b);
End Reconstruct Ellipse
The justification of the algorithm follows from Theorem 5.5. The algorithm
