Image Processing Reference
In-Depth Information
Lemma 3.2. Using the equations of Theorem 3.6, we can see that g and h
may be defined so that y
g
= m
l
g + c
u
and y
h
+ 1 = m
l
h + c
u
. Then, g > h
[38].
€
This lemma defines a relation between two support (extreme) grid points
that define the bounds m
l
and c
u
. In the context of m
l
and c
u
these points
are denoted as (g,y
g
) and (h,y
h
+ 1). A similar pair of support points for m
u
and c
l
are referred to as (h
′
,y
h
′
+ 1) and (g
′
,y
g
′
). For the D
o
in Example 3.1,
g = 4,g
′
= 1,h = 0, and h
′
= 3.
Theorem 3.7. If for any L : y = mx+c,D = D(L) = D
o
then, m
l
< m < m
u
and c
l
< c
o
< c
u
. In other words, Domain(D
o
) ⊆ R
ul
[38].
€
The previous theorem states that R
ul
indeed contains the domain of D
o
.
Before proving the tightness of the rectangle, we explore one more property
of their bounds.
Definition 3.4. Digitization D of a straight line L : y = mx + c is said to
be less than or equal to D
o
(denoted as D ≤ D
o
) if and only if, ∀i,0 ≤ i ≤
n,⌊mi + c⌋≤ y
i
= ⌊m
o
i + c
o
⌋ . D ≥D
o
is defined similarly.
€
Theorem 3.8. If m
l
< m < m
u
and c
l
< c < c
u
, then either D ≤ D
o
or
D ≥ D
o
[38].
€
The above theorem directly leads us to a binary search-like algorithm to
estimate an m (or c) given a c (or m) in R
ul
once the tightness of the rectangle
R
ul
is established. In doing so, we need the following definition.
Definition 3.5. The (c,m)-bounds: m
l
,c
u
,m
u
,c
l
are defined to be consistent
if and only if m
l
< m
u
and c
l
< c
u
.
€
Note that the following theorem uses the fact that the chain code under
standard situation contains 0s and 1s only.
Theorem 3.9. If (c,m)-bounds are consistent, then there exists at least one
pre-digitized line L, such that D(L) = D
o
. [38].
Proof: First we highlight two simple properties of the lines L
lu
: y = m
l
x+c
u
and L
ul
: y = m
u
x + c
l
. Let L
lu
and L
ul
intersect at M = (x,y) (Fig. 3.6).
Then:
Property 1: 0 < x≤ n.
Property 2: There exists no grid point in the open triangles ABM and
MDE.
Note that these properties directly follow from the consistency of the
bounds.
From the above properties, we can say that y
i
= ⌊m
l
i+c
u
⌋,x≤ i < n and
y
i
= ⌊m
u
i + c
l
⌋,0 < i < x. Thus, if we draw a straight line FG(y = mx + c)
through M (Fig. 3.6), then y
i
= ⌊mi+c⌋ if i = x. Now two cases may arise. If
