Image Processing Reference
In-Depth Information
not algebraic in nature. Fortunately under the assumptions of monotonicity,
I(f) can also be expressed through simple algebraic expressions. To see this,
we first define another set of digital points as D from f = 0 and subsequently
prove its equivalence with I(f).
Definition 5.11. Given f, D = D(f) is a set of grid points defined as follows:
D = D
X
∪D
Y
where
′
′
D
X
= {(x
i
,i)|x
i
= ⌊f
x
(i,a,b)⌋,0 6 i 6 n}, if M(f
x
,y) =
D
′
′
= {(x
i
,i)|x
i
= ⌈f
x
(i,a,b)⌉,0 6 i 6 n}, if M(f
x
,y) =
I
D
Y
= {(i,y
i
)|y
i
= ⌊f
y
(i,a,b)⌋,0 6 i 6 m}.
€
The above expressions can be easily justified for the given monotonicity.
We can informally say that if a curve is decreasing in the first quadrant then it
bends down (or to the left) as its x-coordinate (or y-coordinate) increases. The
converse holds if the curve is increasing in the first quadrant. The following
theorem presents the equivalence between D and I(f).
Theorem 5.12. For a monotone curve f, I(f) = D(f). Moreover, the set
D
Y
can be obtained from the set D
X
and vice versa [40].
Proof: The first part of the proof directly follows from the definitions of D(f)
and I(f).
To prove the second part, we assume the MM of the curve to be the one
given in Table 5.4.
The algorithm to construct D
Y
from D
X
is presented in Algorithm 10.
Algorithm 10: To Construct D
Y
from D
X
Algorithm Construct D
Y
Input: The set D
X
= ((x
i
,i)|0 6 i 6 n).
Output: The set D
Y
.
D
Y
= {};
x
n+1
= −1;
for i= 1 to n+1 do
for j = (x
i
+ 1) to x
i−1
do
D
Y
= D
Y
∪{(j,i−1)};
D
Y
= D
Y
∪{(x
n
,n)};
End Construct D
Y
