Image Processing Reference
In-Depth Information
To prove the correctness of the algorithm Construct D
Y
, we require the
following equivalence relation:
(i,y
i
) ∈D
Y
if and only if x
r+1
< i 6 x
r
, where r = y
i
.
(If part): Let x
r+1
< i 6 x
r
. We show that (i,y
i
) ∈ D. As i 6 x
r
, and
x
r
6 f
x
(r), we get i 6 f
x
(r). So, f
y
(i) > f
y
(f
x
(r)) = r, which means that
y
i
6 f
y
(i).
Again, x
r+1
6 i− 1 and x
r+1
> f
x
(r + 1)− 1. So, i− 1 > f
x
(r + 1) − 1.
In other words, i > f
x
(r + 1). Hence, f
y
(i) < f
y
(f
x
(r + 1)) = r + 1. That is,
y
i
> f
y
(i)−1.
Thus, f
y
(i)−1 < y
i
6 f
y
(i). So, y
i
= ⌊f
y
(i)⌋ and (i,y
i
) ∈ D
Y
.
Therefore, to generate D
Y
one needs to produce all (i,r) pairs satisfying
x
r+1
+ 1 6 i 6 x
r
, 0 6 r < n− 1 where (x
r
,r) ∈ D
X
. This is performed in
the nested for loops in the algorithm Construct D
Y
. Hence, the algorithm is
correct.
(Only if part), We need to show that x
r+1
< i 6 x
r
. Assume that x
r+1
> i.
From the definition of D
X
- digitization, x
r+1
6 f
x
(r + 1). Combining the
two inequalities, we get i 6 f
x
(r + 1), which implies that f
y
(i) > f
y
(f
x
(r +
1)) = r + 1 as M(f
y
,x) =
′
D
′
. Again, as (i,y
i
) ∈ D
Y
by assumption, we get
f
y
(i) < (y
i
+ 1) = r + 1. This means (r + 1) 6 f
y
(i) < r + 1, a contradiction.
Hence x
r+1
< i.
Now assume x
r
< i. From the definition of D
X
-digitization, f
x
(r) − 1 <
x
r
6 i− 1. Because of the monotonicity of the function f
y
, f
y
(f
x
(r)) = r >
f
y
(i). But r = y
i
is an integer and hence y
i
= r > ⌊f
y
(i)⌋ = y
i
. Contradiction.
Therefore, x
r
> i.
€
We can also easily separate out the sets D
X
and D
Y
from I(f). So while
I(f) may be obtained experimentally from the acquired image data, it su
ces
to carry out the theoretical analysis using D
X
and D
Y
only. We note that the
digitization for a one-parameter curve can be analogously defined.
5.5.2 One-Parameter Class
As already mentioned, the equation of the curve is given by f(x,y,a) =
0, which may be rewritten as x = f
x
(y,a),y = f
y
(x,a), and a = f
a
(x,y).
Henceforth we shall denote the original value of a by a
o
, and D
o
will denote the
digitization of f(x,y,a
o
) = 0, i.e., D
o
= D(f(x,y,a
o
)). For ease of analysis,
let us consider one particular monotonicity matrix, which is given in Table
5.3. In this case, x
i
= ⌈f
x
(i,a
o
)⌉ and y
i
= ⌊f
y
(i,a
o
)⌋. Using the properties of
⌊.⌋ and ⌈.⌉ functions, we can write,
f
x
(i,a
o
) 6 x
i
< f
x
(i,a
o
) + 1 and
f
y
(i,a
o
)−1 < y
i
6 f
y
(i,a
o
).
As f
a
is decreasing in x,
