Image Processing Reference
In-Depth Information
m
l
< m
o
< m
u
implies c
k+
l
< c
o
< c
k+
u
.
Hence, c
l
< c
o
< c
u
and m
l
< m
o
< m
u
for all k ≥ 0.
The convergence of the iterative scheme is proved again by induction on
k. We first show that for all k ≥ 0, c
k+1
l
≥ c
l
and m
k+1
≤m
u
. The inductive
u
basis holds for k = 0. As,
c
l
= max
i
−m
u
.i) ≥y
0
= c
l
{y
i
{(y
i
+ 1−c
l
)/i) ≤ ((y
n
−y
0
) + 1)/n≤ (n + 1)/n = m
u
.
It is easy to see that,
(i)c
k+1
l
m
u
= min
i
≥ c
l
implies m
k+2
u
≤ m
k+1
u
for k ≥ 0,and
(ii)m
k+1
u
≤m
u
implies c
k+2
≥ c
k+1
l
for k ≥ 0.
l
Hence,
≤c
k+1
l
c
l
≤ c
l
≤ c
l
≤ c
l
≤ ...c
l
... < c
o
and
m
u
≥m
u
≥m
u
≥m
u
≥...m
u
≥ m
k+1
u
... > m
o
.
= c
k
′
+1
l
′
≥ k, c
k
′
l
′
Now, if we get any k so that ∀k
,k
, then there exists some
j, so that ∀j
′
,j
′
≥ j,m
j
′
u
= m
j
′
+
u
. In this case, the iteration ends at a fixed
point. Otherwise, it forms a non-decreasing (or non-increasing) sequence upper
bounded (lower bounded) by a constant value. Hence, the limit always exists
and lim
k→∞
c
l
= c
l
and lim
k→∞
m
u
= m
u
. Numerically, we can compute c
l
and m
u
by selecting a small quantity ǫ > 0 and terminating when c
l
−c
k−1
l
< ǫ
and m
k−1
u
−m
u
< ǫ.
Similarly, we can prove that lim
k→∞
m
l
= m
l
and lim
k→∞
c
u
= c
u
.
Hence, part (a). Part (b) actually follows from the first inductive proof
and part (a).
€
Example 3.1. Let n = 4 and D
o
be ( 0,1,1,1,2 ) corresponding to the line
L
o
: y = 0.4x + 0.6.
The convergence of c
l
, c
u
, m
l
, and m
u
can be verified. It may be observed
that while c
u
and m
l
attain fixed points after only one iteration, c
l
and m
u
form monotone sequences. It can be checked that max
i
−m
u
.i) occurs at
{y
i
{(y
i
+ 1 − c
l
)/i) occurs at i = 3,y
i
= 1.
Thus, c
l
and m
u
follow the mutually recursive equations: c
l
= 1−m
k−1
i = 1 and y
i
= 1. Similarly, min
i
and
u
m
u
= (2−c
k−1
)/3.
u
3.2.2 Reconstruction of a DSLS
We first show that the rectangle (say R
ul
) defined on the c − m plane
by the points (c
u
,m
l
) and (c
l
,m
u
) as diagonally opposite vertices, properly
contains the domain of D
o
. Subsequently, it is shown that R
ul
is the smallest
such rectangle, and if R
ul
= φ, then there exists at least one continuous line
L such that D{L} = D
o
. This we state in the following theorems.