PA170 Digital Geometry
Lecture 08: Digital Straightness and Convexity
Martin Maˇska (xmaska@fi.muni.cz)
Centre for Biomedical Image Analysis
Faculty of Informatics, Masaryk University, Brno
Autumn 2023
Motivation: Straightness in 2D Digital Spaces
A digital arc is considered straight if it corresponds to the digitization of a straight line
segment
The recognition of digital straight line segments and decomposition of digital arcs into
such segments play crucial roles in many applications such as the estimation of
curve length or the simplification of shapes
A straight line and its digitization Four straight line segments and their digitization
2/19
DIGITAL RAYS
Digital Rays as Binary Words
Let γα,β = {(x, αx + β) : 0 ≤ x < ∞, 0 ≤ α ≤ 1} be a real ray with the slope α and
intercept β. Its grid-intersection digitization R(γα,β) is called a digital ray, and it
corresponds to a sequence of grid points (n, In) ∈ Z2:
R(γα,β) = Iα,β = {(n, In) : n ≥ 0 ∧ In = αn + β + 0.5 }
Digital rays can be represented as binary words iα,β over the {0, 1} alphabet where
iα,β(n) = In+1 − In, n ≥ 0, zeros correspond to horizontal steps, and ones correspond
to diagonal steps
4/19
Word Theory Terminology and Notation
A word defined over an alphabet A is a sequence of elements of A
The set of all words defined over A is denoted as A
The set of all infinite words over A is denoted as A∞
A word v ∈ A is called a factor of a word u ∈ A iff there exist words v1 ∈ A and
v2 ∈ A such that u = v1vv2
An integer k ≥ 1 is called a period of a word u = a0a1 . . . an−1 if ai = ai+k
(i = 0, . . . , n − 1 − k)
An infinite word w ∈ A∞ is called periodic if it is of the form w = v∞ for some
nonempty finite word v ∈ A
An infinite word w ∈ A∞ is called eventually periodic if it is of the form w = uv∞ for
some nonempty finite words u, v ∈ A
An infinite word w ∈ A is called aperiodic if it is not eventually periodic
5/19
Digital Rays: Terminology and Theory
Digital rays are right infinite binary words
Digital straight lines (DSLs) are infinite binary words in both directions
Digital straight line segments (DSSs) are finite binary words
DSSs are nonempty finite factors of digital rays
A finite or infinite 8-arc is called irreducible iff its set of grid points does not remain
8-connected after removing a nonendpoint from it
A digital ray is called rational if α is rational and irrational if α is irrational
Connectivity: A digital ray is an irreducible 8-arc
Self-similarity: For irrational α, Iα,β uniquely determines both α and β. For rational
α, Iα,β uniquely determines α, and β is determined up to an interval
Periodicity: Rational digital rays are periodic and irrational digital rays are aperiodic
6/19
CHARACTERIZATION OF DIGITAL
STRAIGHT LINE SEGMENTS
Offline and Online DSS Recognition Algorithms
Many linear DSS recognition algorithms have been introduced
Offline algorithms decide whether a finite binary word u ∈ {0, 1} is a DSS
Online algorithms sequentially read a finite binary word u ∈ {0, 1} and determine
the highest k ≥ 0 such that u(0), . . . , u(k) is a DSS, but u(0), . . . , u(k + 1) is not
Remark: Linear online algorithms produce digital arc decomposition in linear time,
whereas linear offline algorithms carry out this decomposition in quadratic time.
8/19
Tangential Lines
Let u be an 8-arc of length n and G(u) = {p0, p1, . . . , pn−1} be the assigned set of
grid points such that p0 = (0, 0) and u connects p0 with pn−1 via a sequence of
horizontal and diagonal steps through p1, . . . , pn−2
u is a DSS iff G(u) lies on or between two parallel lines with a distance apart that is
less 1 (measured in the vertical direction)
9/19
Chord Property
Let u be an irreducible 8-arc of length n and G(u) = {p0, p1, . . . , pn−1} be the
assigned set of grid points such that p0 = (0, 0) and u connects p0 with pn−1 via a
sequence of horizontal and diagonal steps through p1, . . . , pn−2
G(u) satisfies the chord property iff for any two different points p, q ∈ G(u) and any
point r on the real line segment between p and q, there exists a grid point t ∈ G(u)
such that d8(r, t) < 1
u is a DSS iff G(u) satisfies the chord property
10/19
Syntactic Characterization: Preliminaries
Let u = (u(i))i∈I (I ⊆ Z) be a word over N
A digit k ∈ N is called singular in u iff k appears in u and, for all i ∈ I such that i − 1
and i + 1 are in I, if u(i) = k, u(i − 1) = k and u(i + 1) = k
A digit k ∈ N is called nonsingular in u iff k appears in u and is not singular in u
u is reducible iff u contains no singular digit or any factor of u that contains only
nonsingular digits is finite
Let u be reducible, and let R(u) be one the following:
The length of u if u is finite and contains no singular digit; or
The word that results from u by replacing all of its factors of nonsingular digits in u that
are between two singular digits in u by their run lengths, and by deleting all other digits
from u; or
The digit d if u = d∞
Recursive application of this reduction operation R produces a sequence of reducible
words u0, u1, . . . where u0 = u and ui+1 = R(ui), i ≥ 0
What is the sequence of reducible words after recursive application of R on
u =11011101110111011110111011101111011101110111101110111011110111011101110111101110111011110111?
11/19
Syntactic characterization of DSLs and DSSs
A two-sided infinite 8-arc u is a DSL iff u0 = u, u1, . . . (where ui+1 = R(ui), i ≥ 0) are
reducible words and satisfy the following two conditions:
L1 There are at most two different digits d and e in ui, and, if there are two,
|d − e| = 1
L2 If there are two different digits in ui, at least one of them is singular.
Let u be a finite 8-arc, and l(u) and r(u) be the run lengths of nonsingular digits to
the left of the first singular digit and to the right of the last singular digit in u. u is a
DSS iff u = u0 satisfies L1 and L2, and any sequence ui = R(ui−1) satisfies L1 and
L2 as well as the following:
S1 If ui contains only one digit d or two different digits d and d + 1,
l(ui−1) ≤ d + 1 and r(ui−1) ≤ d + 1
S2 If ui contains two different digits d and d + 1 and d is nonsingular in ui,
ui starts with d if l(ui−1) = d + 1 and ends with d if r(ui−1) = d + 1
Is u =11011101110111011110111011101111011101110111101110111011110111011101110111101110111011110111 a DSS?
12/19
DIGITAL CONVEXITY
Convex Sets and Convex Hulls
M ⊆ S is called convex if, for any distinct p, q ∈ M, the straight line segment between
p and q is contained in M
Any intersection of convex subsets of S is a convex set
The intersection C(M) of all of the convex subsets of S that contain M is called the
convex hull of M
14/19
Digitally Convex Sets
A digital set is convex if it is obtained as the digitization of a convex set
The Gauss digitization of a convex set M ⊆ R2 may not be 8-connected
The cross digitization of a convex set M ⊆ R2 is always simply 8-connected
A set ∅ = S ⊆ Z2 is called digitally convex iff there exists a convex set M ⊆ R2, the
cross digitization of which is S
Gauss digitization of a convex set Cross digitization of a convex set
15/19
Digitally Convex Sets: Properties
A finite set M ⊆ Z2 is digitally convex iff any of the following is true:
M satisfies the chord property
For all p, q ∈ M, at least one DSS with p and q as endpoints is contained in M
For p, q, r ∈ M, all of the grid points in the triangle pqr are in M
Any grid point on the real line segment between two grid points of M is also in M
A digitally convex set The 2nd property The 3rd property The 4th property
16/19
Border Segments: Digital Convexity Test
The Euclidean convex hull C(M) of any M ⊆ Z2 is a convex polygon with vertices that
are all 4-border pixels of M
If M is simply 8-connected, 4-border tracing visits all of the 4-border pixels of M
sequentially
The vertices of C(M) partition the sequence of border pixels into subsequences that
start and end at successive vertices of C(M)
These subsequences are called border segments of M
A digitally convex set Its border segments A digitally nonconvex set Its border segments
Digital convexity test: A finite proper simply 8-connected subset M of Z2 is digitally convex
iff every border segment of M is a DSS 17/19
Convex Completion
S is called a digitally convex completion of M ⊆ Z2 iff S contains M and is digitally
convex, and S \ U is not digitally convex for any U ⊆ S \ M
A digitally nonconvex set Its convex completion
18/19
Take-Home Messages
Digital rays can be represented as right infinite binary words
Digital straight lines can be represented as two-sided infinite binary words
Digital straight line segments are nonempty finite factors of digital rays
Digital straight line segments can be characterized using the tangential lines, chord
property, or syntactic analysis
Digitally convex sets are the cross digitization counterparts of real convex sets
Border segments of simply 8-connected digital sets can efficiently be exploited to
check whether these sets are digitally convex
19/19