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.
Search WWH ::




Custom Search