PA170 Digital Geometry
Lecture 02: Digitization
Martin Maˇska (xmaska@fi.muni.cz)
Centre for Biomedical Image Analysis
Faculty of Informatics, Masaryk University, Brno
Autumn 2023
Motivation: Transformation of a Continuous Set to a Discrete Set
Digitization of a real disk D
Digitization of a real line L
2/25
Digital Geometric Figures
A connected set of grid points is called a digital geometric figure (e.g., digital line,
digital square, digital disk, or digital sphere), if there exists a (continuous) geometric
figure of the same kind, which has that set as its digitization
3/25
Example: Convergence of Estimators
A real disk D of unit diameter has the area A(D) = π
4 and the perimeter P(D) = π
The area of a digitized disk converges toward the area of the real disk with an
increasing grid resolution h:
lim
h→∞
A(digh(D)) = A(D) =
π
4
The perimeter of a digitized disk does not converge toward the perimeter of the real
disk:
lim
h→∞
P(digh(D)) = 4
h = 1 h = 5 h = 10 h = 17
4/25
DIGITIZATION MODELS
Look into History
C.F. Gauss (1777 – 1855) C. Jordan (1838 – 1922)
Source: https://mathshistory.st-andrews.ac.uk/
6/25
Gauss Digitization
Gauss studied the measurement of the area of a planar set S ⊂ R2 by counting the
grid points (i, j) ∈ Z2 contained in S
The Gauss digitization Gh(S) of a planar set S on a 2D grid of resolution h is the
union of the grid squares (2-cells) with center points in S
d = 1 grid unit d = 5 grid units d = 10 grid units d = 17 grid units
8×8 grid squares 16×16 grid squares 32×32 grid squares 512×512 grid squares
7/25
Gauss Digitization: Properties
The Gauss digitization Gh(S) of any nonempty bounded set S ⊂ R2 is the union of a
finite number of simple isothetic polygons
Different sets can have identical Gauss digitizations
The same sets after a rigid transformation can have different Gauss digitizations
An original disk The disk shifted to the right The disk shifted to the left
8/25
Jordan Digitization
Originally defined for 3D grids only as Jordan used such grids to estimate the
volumes of subsets of R3
The inner Jordan digitization J−
h (S) of a planar set S on a 2D grid of resolution h is
the union of the grid squares (2-cells) that are completely contained in S
The outer Jordan digitization J+
h (S) of a planar set S on a 2D grid of resolution h is
the union of the grid squares (2-cells) that have nonempty intersection with S
Inner (gray 2-cells) and outer (gray and green 2-cells) Jordan digitizations of a centered disk
9/25
Jordan Digitization: Examples
Inner
8×8 grid squares 16×16 grid squares 32×32 grid squares 512×512 grid squares
Outer
8×8 grid squares 16×16 grid squares 32×32 grid squares 512×512 grid squares
10/25
Jordan Digitization: Properties
The inner and outer Jordan digitizations J−
h (S) and J+
h (S) of any nonempty bounded
set S ⊂ R2 are the unions of finite numbers of simple isothetic polygons
The outer Jordan digitization J+
h (S) of a connected set S is always a single
connected isothetic polygon or polyhedron. However, it does not preserve simple
connectedness because it can create holes
A real roll-like object S The outer Jordan digitization of S
11/25
Relationships between Gauss and Jordan Digitizations
Both digitization models are broadly used to digitize 2D and 3D sets
They produce the same digitizations for:
Empty set: J−
h (∅) = Gh(∅) = J+
h (∅) = ∅
Euclidean n-space Rn
(n ∈ {2, 3}): J−
h (Rn
) = Gh(Rn
) = J+
h (Rn
) = Rn
Finite unions of n-cells in nD (n ∈ {2, 3})
The obtained digitizations are ordered by inclusion:
J−
h (S) ⊆ Gh(S) ⊆ J+
h (S) for any S ⊆ R2
(S ⊆ R3
)
12/25
Grid-Intersection Digitization
Neither Gauss nor inner Jordan digitization is appropriate for the digitization of 1D
sets (curves). Outer Jordan digitization is appropriate but grid-intersection digitization
is the preferred choice for curves
The grid-intersection digitization R(γ) of a planar curve γ is the set of all grid points
with closest Euclidean distances to the intersection points of γ with the grid lines
In case an intersection point is of the same distance from two grid points, either both
grid points are added to R(γ) or one of them is chosen based on a predefined rule
13/25
Grid-Intersection Digitization
Neither Gauss nor inner Jordan digitization is appropriate for the digitization of 1D
sets (curves). Outer Jordan digitization is appropriate but grid-intersection digitization
is the preferred choice for curves
The grid-intersection digitization R(γ) of a planar curve γ is the set of all grid points
with closest Euclidean distances to the intersection points of γ with the grid lines
In case an intersection point is of the same distance from two grid points, either both
grid points are added to R(γ) or one of them is chosen based on a predefined rule
14/25
Grid-Intersection Digitization
Neither Gauss nor inner Jordan digitization is appropriate for the digitization of 1D
sets (curves). Outer Jordan digitization is appropriate but grid-intersection digitization
is the preferred choice for curves
The grid-intersection digitization R(γ) of a planar curve γ is the set of all grid points
with closest Euclidean distances to the intersection points of γ with the grid lines
In case an intersection point is of the same distance from two grid points, either both
grid points are added to R(γ) or one of them is chosen based on a predefined rule
15/25
Grid-Intersection Digitization
Neither Gauss nor inner Jordan digitization is appropriate for the digitization of 1D
sets (curves). Outer Jordan digitization is appropriate but grid-intersection digitization
is the preferred choice for curves
The grid-intersection digitization R(γ) of a planar curve γ is the set of all grid points
with closest Euclidean distances to the intersection points of γ with the grid lines
In case an intersection point is of the same distance from two grid points, either both
grid points are added to R(γ) or one of them is chosen based on a predefined rule
16/25
Grid-Intersection Digitization
Neither Gauss nor inner Jordan digitization is appropriate for the digitization of 1D
sets (curves). Outer Jordan digitization is appropriate but grid-intersection digitization
is the preferred choice for curves
The grid-intersection digitization R(γ) of a planar curve γ is the set of all grid points
with closest Euclidean distances to the intersection points of γ with the grid lines
In case an intersection point is of the same distance from two grid points, either both
grid points are added to R(γ) or one of them is chosen based on a predefined rule
17/25
Digitized Grid=Intersection Sequence
An ordered sequence of grid points in R(γ) is called a digitized grid-intersection
sequence ρ(γ) of γ
Such a sequence can be represented by a chain code
Remark: Chain codes can also represent object borders (typically obtained by a
border tracing algorithm)
18/25
DOMAIN DIGITIZATIONS
Preliminaries
We want to define a framework for a general class of digitization models in nD
Let Πcube = (x1, . . . , xn) : max
1≤i≤n
|xi| ≤ 1
2 be a n-cell centered at o = (0, . . . , 0):
Let ∅ = Πσ ⊆ Πcube, and consider its translates Πσ(q) = {q + p : p ∈ Πσ} centered at
grid points q ∈ Zn as the domains of influence:
Obviously, Πcube(q) is the n-cell cq centered at q
20/25
σ-Digitization
The inner σ-digitization dig−
σ (S) of a set S ⊆ Rn is the union of all cq such that Πσ(q)
is contained in S:
cq ⊆ dig−
σ (S) iff Πσ(q) ⊆ S
The outer σ-digitization dig+
σ (S) of a set S ⊆ Rn is the union of all cq such that Πσ(q)
intersects S:
cq ⊆ dig+
σ (S) iff Πσ(q) ∩ S = ∅
If Πσ = Πcube, dig−
cube = J− (inner Jordan digitization) and
dig+
cube = J+ (outer Jordan digitization)
If Πσ = {o}, dig+
σ = dig−
σ = G (Gauss digitization)
If Πσ = {(x1, . . . , xn) : ∃i.(1 ≤ i ≤ n ∧ xi = 0) ∧ max
1≤i≤n
|xi| ≤ 1
2 )},
dig+
σ = R (grid-intersection digitization)
21/25
DIGITIZATION OF STRAIGHT LINES
Bresenham’s Algorithm for Line Digitization
A standard routine in computer graphics, which builds on top of the grid-intersection
digitization model
Check out a demo at http://bert.stuy.edu/pbrooks/graphics/demos/BresenhamDemo.htm
23/25
Bresenham’s Algorithm (First Octant, Nonnegative Slope)
Task: Draw a digital line with a nonnegative slope between two points, (xs, ys) and
(xe, ye), in the first octant
Pseudocode of the algorithm
1 Initialize constants: dx = xe − xs, dy = ye − ys, b0 = 2 ∗ dy, b1 = 2 ∗ (dy − dx)
2 Initialize variables: x = xs, y = ys, err = 2 ∗ dy − dx
3 while x ≤ xe
Draw (x, y) as a digital line element
x = x + 1
if err < 0
err = err + b0
else
y = y + 1
err = err + b1
Complexity: The algorithm runs in O(xe − xs) and involves basic assignment, arithmetic,
and conditional operations only
24/25
Take-Home Messages
Digital geometric figures (shapes) are sets of grid points obtained by digitizing their
continuous counterparts
1D sets (curves) are digitized using the grid-intersection digitization model
2D and 3D sets are digitized using the Gauss or Jordan digitization models
Domain digitization defines a general digitization model
The Bresenham algorithm digitizes lines using the grid-intersection digitization model
25/25