Image Processing Reference
In-Depth Information
finds one suitable a for a fixed b. Actually the choice of this b is arbitrary so
long as b
l
< b < b
u
. Finally we prove that the algorithm terminates.
Theorem 5.6. Given D
o
, algorithm Reconstruct Ellipse terminates with a
and b such that D
o
= D(E(a,b)) [41].
Proof: Since the value of b is held constant, two situations are possible de-
pending on whether b < b
o
or b > b
o
. We first consider the former. Without
any loss of generality, we assume that at an arbitrary iteration step we have
D 6 D
o
. Hence, the new a will be a
′
= (a + a
R
)/2. Note that a
l
< a
′
< a
u
.
Two cases can arise here.
Case 1: D
′
= D(E(a
′
,b)) 6 D
o
.
Clearly, D 6 D
′
6 D
o
. Hence D
′
does not match D
o
at most, at those
components where D and D
o
differ. Since in this way a
′
can be monotonically
increased, there must exist some a
′
such that D
′
matches D
o
in at least one
component more than D. Eventually then, D
′
will converge to D
o
.
Case 2: D
′
> D
o
.
Clearly, D
′
′′
′′
> D
o
> D. Consider the last iteration with a
where D
> D
o
.
′
′′
′
′′
From the algorithm a
. Again, similar to Case 1,
the number of matches can be argued to gradually increase culminating in the
convergence.
Now if b > b
o
, from Theorem 5.5, we will always get D > D
o
and keep
on decrementing a (actually a → a
l
). Since D(E(a
l
,b)) < D
o
, eventually we
shall get an a where D = D
o
.
Hence, the algorithm terminates with a correct estimation.
< a
and D
o
6 D
6 D
€
As the above argument holds for any (a,b) ∈ R
ul
, it is easy to see that
there exists an a (or b) for an arbitrary b,b
l
< b < b
u
(or a,a
l
< a < a
u
) such
that D = D
o
.
5.3.3 The Domain Theorem
In this section, we show that a variation of the iteration equations helps
to compute the domain of D
o
, of which R
ul
is a tight bound. We present it in
the next theorem after necessary lemmas.
Lemma 5.7. The following hold [41]:
(A) a
l
< a < a
u
if and only if b
∗
l
(a) < b
∗
u
(a) where b
∗
l
(a) = max
i
(y
i
/
(1−
i
2
/a
2
)) and b
∗
(1−i
2
/a
2
)).
u
(a) = min
i
((y
i
+ 1)/
∗
∗
∗
(B) b
l
< b < b
u
if and only if a
l
(b) < a
u
(b) where a
l
(b) = max
i
(x
i
/
(1−
i
2
/b
2
)) and a
∗
(1−i
2
/b
2
)).
u
(b) = min
i
((x
i
+ 1)/
€
Theorem 5.7. (The Domain Theorem) The domain Domain(D
o
) of all pos-
sible values of (a,b) parameters to give reconstruction is given by the following
