Image Processing Reference
In-Depth Information
∗
∗
u
(c)) of a DSLS defines a line interval in the (c,m)-
plane. Taking union of these intervals for c
l
< c < c
u
, we get a region in the
(c,m)- plane. Thus, Domain(D
o
) is a region in the (c,m)-plane.
Proof: From Theorem 3.7, Domain(D
o
) ⊆ R
ul
. Again from Lemma 3.4, for
given c,c
l
< c < c
u
, and for all m,m ∈ [m
∗
For a given c, [m
l
(c),m
l
(c),m
∗
u
(c)),(c,m) ∈ Dom(D
o
), if
m < m
∗
−c)/p for some p. In other words, y
p
> mp + c or
y
p
> ⌊mp + c⌋. Thus, m < m
∗
l
(c), then m < (y
p
l
(c) implies that (c,m) ∈ Dom(D
o
). Similarly,
m ≥ m
∗
u
(c) implies that (c,m) ∈ Dom(D
o
). Hence, for any c,c
l
< c < c
u
,
(c,m) ∈ Dom(D
o
) if and only if m ∈ [m
∗
l
(c),m
∗
u
(c)).
€
Corollary 3.2. R
ul
is the smallest rectangle in the (c,m)-space so that
Domain(D
o
) ⊆R
ul
.
€
It is observed from the construction of m
l
,c
u
,m
u
,c
l
bounds that given
any D
o
we may be able to compute them numerically. That is, if D
o
is indeed
a DSLS then the bounds m
l
,c
u
,m
u
,c
l
really exist. However, if D
o
is any
arbitrary set of 2-D digital points and not really a DSLS, Domain(D
o
) does
not exist.
In view of the above corollary, we immediately get an algorithm from
iterative refinement to test whether a given digital set is a valid digital straight
line or not.
Corollary 3.3. Domain(D
o
) is empty if and only if m
l
≥ c
u
or
both. In other words, the (m,c) bounds are consistent if and only if the digital
set D
o
satisfies the chord property.
≥ m
u
or c
l
€
We illustrate the above equivalence through a trivial yet interesting exam-
ple.
Example 3.2. Let us consider a generic digital set D = {y
i
: y
i
= i,0 ≤ i ≤
a;y
i
= a,a ≤i ≤a + b;a,b integer ≥ 1 and a + b = n}. This corresponds to a
chain code where b 0s follow a 1s.
Consider m
u
and c
l
for this set. Assuming the consistency of these bounds,
we can show that
c
l
= a(1−m
k−
u
) and m
u
= (a + 1−c
k−1
)/(a + b).
l
Solving this mutual recurrence we get,
c
l
= a(1−1/b)(1−(a/(a + b))
r
),r = ⌊k/2⌋
m
u
= (1/b) + (1−1/b)(a/(a + b))
s
,s = ⌈k/2⌉, k ≥ 0, a,b≥ 1.
Hence, c
l
= a(1 −1/b) and m
u
= 1/b.
Again from consistency c
l
< c
u
= y
0
+ 1 = 1. That is, 1/a + 1/b > 1 or
min(a,b) = 1, since a and b are integers.
Similarly, c
u
= 1 and m
l
= 1 − 1/a, if min(a,b) = 1, whereas for
min(a,b) > 1.
c
u
= a(1−1/b)−a(1−1/a−1/b)(1 + b/a)
r
,r = ⌊k/2⌋,
