Image Processing Reference
In-Depth Information
chain code. Using the nearest upper support and nearest lower support of
the convex hull of D, Kim and Anderson devised an algorithm to compute a
polygon so that any CSLS inside that polygon is a pre-image of D.
3.1.2 Number Theoretic Characterization and Domain of
DSLS
The structure of straight strings (which are chain codes of DSLSs) is also
closely related to the number theoretical properties of the slope of that straight
line. Dorst introduced a convenient diagrammatic representation, called a
spirograph, for a CSLS to study the structure of a straight string [77]. We
discuss here a closed form algebraic characterization of DSLSs [78] invented
by Dorst and Smeulders. They considered the chain code of a CSLS, C, ob-
tained by the OBQ digitization of a straight line y = mx + c from x = 0 to
x = n, where 0 ≤ m < 1 and 0 ≤c < 1.
The main theorem of [78] is stated below.
Theorem 3.5. The chain code of a straight line segment C in the standard
situation can be mapped bijectively onto the quardruple (n,q,p,s) defined by
n = the number of elements in C
q = min
k
{k ∈{1,2,..,n}|k = n or ∀i ∈{1,2,..,n−k} : C
i+k
= C
i
}
q
p =
C
i
i=1
s ∈ {0,1,2,...,q−1} and ∀i ∈{1,2,...,q} :
C
i
= ⌊(p/q)(i−s)⌋−⌊(p/q)(i−s−1)⌋
where C
i
is the i-th element of C.
€
Intuitively, q represents the periodicity of the given chain code of a DSLS.
p
q
represents the best rational approximation of the slope and s denotes the
phase shift and arises due to the intercept c.
The proof of this theorem is quite elaborate and employs involved algebraic
and number theoretic manipulations. Thus, the proof is not discussed in this
topic and can be found in [78, 76].
As an example, consider the DSLS of the CSLS given by
√
2
x +
1
y =
2
from x = 0 to x = 9.
The DSLS has the chain code 101110111. Its periodicity q is 4, the number
of 1's in a period, p, is 3, and phase shift equivalent s is 1. See Fig. 3.3 for an
illustration.
Thus, a straight string is represented by a unique 4-tuple (n,q,p,s) without
