Image Processing Reference
In-Depth Information
4.1.2 Periodicity
As mentioned and exemplified in the previous section, a DSL can be rep-
resented as a word w of infinite length built from the chain-code alphabet
A = {0,1,...,7}. The infinite word w is periodic if w = v
ω
, for some basic
segment v ∈A
∗
{ǫ}. For example, w = ...00010001000100010001... is peri-
odic with v = 0001; we can set also 0010 as the period for w as it is an infinite
word, but that is not important; what matters here is that w is periodic and
its period is |v| = 4. Studies on such periodicity related to digital straightness
date back to 1970s. The following theorem is important in this context.
Theorem 4.1 (Brons [34]). Rational digital rays are periodic and irrational
digital rays are aperiodic.
€
Note that a rational (irrational) digital ray implies the DSL corresponding
to a real ray with rational (irrational) slope. As evident from Theorem 4.1, the
problem of periodicity or aperiodicity becomes crucial while determining the
digital straightness of a digital curve segment. In case a DSS is a part of DSL
with irrational slope, the period can never be found; and even if the slope is
rational, the DSS may not be su
ciently long in comparison with the period
so as to accommodate a basic segment of the DSL. Further, the character-
ization of the basic segment is also quite important. The following theorem
provides some clue to address the aforesaid problems using the properties of
self-similarity in a word of finite or infinite length.
Theorem 4.2 (Freeman [87]). The chain-code sequence of a DSS or DSL
should have the following three properties:
F1: At most two types of elements (chain codes) can be present, and these
can differ only by unity, modulo 8;
F2: One of the two element values always occurs singly;
F3: Successive occurrences of the element occurring singly are as uniformly
spaced as possible.
€
The properties in Theorem 4.2 were illustrated by examples and based
on heuristic insights. Further, Property F3 is not precise enough for a formal
proof [160]. Nevertheless, it explicates how the composition of a straight line in
the digital space resembles that in the Euclidean space as far as the evenness
(Section 4.1) in distribution of its constituting points is concerned. A few
examples are given below to clarify the idea.
1. 101012100 is not a DSS, since F1 fails (three elements are present).
2. 01101000 is not a DSS, since F2 fails (none of 0 and 1 occurs singly).
