PA170 Digital Geometry
Lecture 01 – Introduction + Grids and Adjacency
Martin Maˇska (xmaska@fi.muni.cz)
Centre for Biomedical Image Analysis
Faculty of Informatics, Masaryk University, Brno
Autumn 2023
INTRODUCTION
About PA170
Lectures (Monday 14:00 – 15:40, B204)
Introduction of the basic terms and necessary theory
Exercises (Monday 16:00 – 16:50, B204)
Deeper understanding and application of the introduced terms and theory in practice
Homeworks
Irregular and voluntary, assigned at exercises
Awarded by extra points (up to 10 points)
Examination (one term before Christmas, other terms in January 2024)
Written (mandatory) and oral (voluntary) parts (up to 100 points)
Grading scheme
A: at least 91 points
B: 90 – 81 points
C: 80 – 71 points
D: 70 – 61 points
E: 60 – 51 points
F: less than 51 points
Recommended literature
R. Klette & A. Rosenfeld, Digital Geometry: Geometric Methods for Digital Picture
Analysis, Elsevier 2004 (V238 in the library at FI MU)
3/25
Digital Geometry in a Nutshell
It emerged in the second half of the 20th century
Its mathematical roots are in graph theory and discrete topology
It focuses on geometric or topologic properties of discrete sets
It often attempts to obtain quantitative information about objects by analyzing
digitized image data in which the objects are represented by such sets
4/25
Digital Images
Digital images are obtained by digitizing continuous functions
256×256 pixels 128×128 pixels 64×64 pixels 32×32 pixels
Sampling
(domain discretization)
Quantization
(co-domain discretization)
256 levels 32 levels 8 levels 2 levels
A digital image I is a discrete function, defined on a finite, regular, orthogonal grid G,
which assigns a value I(p) from a finite set of values V to each image element p ∈ G
5/25
Common Types of Digital Images
Binary Images (V = {0, 1})
The image elements with the assigned values of 1 are black and form foreground I
The image elements with the assigned values of 0 are white and form background I
Grayscale Images (V = {0, . . . , Gmax})
The elements of V are called intensities
The image elements with higher intensities correspond to lighter gray levels
The image elements with zero intensity are black and form background
Floating-Point Images (e.g., Euclidean distance maps)
Color Images (e.g., RGB or HSV)
Multi-Channel Images (e.g., microscopy or satellite images)
Tensor Images (e.g., DT-MRI)
6/25
GRIDS AND ADJACENCY
Basic Grid Models
8/25
Elements of a Grid
A grid point is an element of Z2 or Z3
A grid vertex (0-cell) is shifted by 0.5 in each direction from a grid point
A grid edge (1-cell) joins two grid vertices at Euclidean distance of 1 from each other
A grid square (2-cell) is defined by four grid edges that form a square
A grid cube (3-cell) is defined by six grid squares that form a cube in 3D
9/25
Elements of a Grid
A grid point is an element of Z2 or Z3
A grid vertex (0-cell) is shifted by 0.5 in each direction from a grid point
A grid edge (1-cell) joins two grid vertices at Euclidean distance of 1 from each other
A grid square (2-cell) is defined by four grid edges that form a square
A grid cube (3-cell) is defined by six grid squares that form a cube in 3D
Pixel (2D grids) = 2D grid point or 2-cell Voxel (3D grids) = 3D grid point or 3-cell
10/25
α-Adjacency (Aα) on 2D Grids
Two 2-cells c1 and c2 are called α-adjacent iff c1 = c2 and their intersection contains
an α-cell (α ∈ {0, 1})
Two 2D grid points p1 and p2 are called
4-adjacent iff p2 − p1 1 = 1
8-adjacent iff p2 − p1 ∞ = 1
The grid Gm,n defined by m×n 2-cells and A0 or A1 relation is isomorphic to the grid
defined by m×n 2D grid points and A8 or A4 relation, respectively
1-adjacency 4-adjacency 0-adjacency 8-adjacency
11/25
α-Adjacency (Aα) on 3D Grids
Two 3-cells c1 and c2 are called α-adjacent iff c1 = c2 and their intersection contains
an α-cell (α ∈ {0, 1, 2})
Two 3D grid points p1 and p2 are called
6-adjacent iff 0 < p2 − p1 2 ≤ 1
18-adjacent iff 0 < p2 − p1 2 ≤
√
2
26-adjacent iff 0 < p2 − p1 2 ≤
√
3
The grid Gl,m,n defined by l×m×n 3-cells and A2, A1, or A0 relation is isomorphic to
the grid defined by l×m×n 3D grid points and A6, A18, or A26 relation, respectively
6-adjacency 18-adjacency 26-adjacency
12/25
Adjacency Set and Neighborhood
Let A be a symmetric and irreflexive adjacency relation on a set S
A(p) = {q : q ∈ S ∧ qAp} is called the adjacency set of p ∈ S
N(p) = A(p) ∪ {p} is called the (smallest nontrivial) neighborhood of p ∈ S defined
by the adjacency relation A
N defines a symmetric and reflexive relation on S
A1(p) A4(p) N1(p) N4(p)
13/25
Connectedness, Paths, and Components
The reflexive and transitive closure of an adjacency relation on a set S defines a
connectedness relation on S
A path that joins p ∈ S and q ∈ S is a sequence p0, . . . , pn of elements in S such that
p0 = p, pn = q, and pi is adjacent to pi−1 (1 ≤ i ≤ n)
A set M ⊆ S is called connected iff all p, q ∈ M are joined by a path in M
Maximal connected subsets of S are called (connected) components of S
Examples of two 4-paths and one 8-path
14/25
Connectedness, Paths, and Components
The reflexive and transitive closure of an adjacency relation on a set S defines a
connectedness relation on S
A path that joins p ∈ S and q ∈ S is a sequence p0, . . . , pn of elements in S such that
p0 = p, pn = q, and pi is adjacent to pi−1 (1 ≤ i ≤ n)
A set M ⊆ S is called connected iff all p, q ∈ M are joined by a path in M
Maximal connected subsets of S are called (connected) components of S
Examples of two 4-paths and one 8-path
What is the number of 4-connected and 8-connected components?
15/25
Adjacency on Images
The number of image elements α-adjacent to an image element is (almost) always
constant over the whole grid
That number can vary for adjacency relations defined on images because not only
locations but also values of image elements are taken into consideration
16/25
(I, α)-Adjacency
Two image elements p and q of an image I are called I-equivalent iff I(p) = I(q)
Two image elements p and q of an image I are called (I, α)-adjacent iff they are
I-equivalent and α-adjacent
(I, α)-adjacency may lead to crossing difficulties (topological conflicts)
Connected components for (I, 8)-adjacency or (I, 0)-adjacency
17/25
(σ, α)-Adjacency
”Uncertainties” in image values can be modeled by a similarity relation σ on V, which
is reflexive and symmetric
Two image elements p and q of an image I are called (σ, α)-adjacent iff pAαq and
I(p)σI(q)
(σ, α)-adjacency generalizes (I, α)-adjacency and may lead to crossing difficulties
Connected components for (σ, 8)-adjacency or (σ, 0)-adjacency (pσq ⇔ |I(p) − I(q)| ≤ 2)
18/25
(α1, α2)-Adjacency
(α1, α2)-adjacency avoids topological conflicts in binary images
It considers (I, α1)-adjacency for foreground and (I, α2)-adjacency for background
Commonly used, topologically compatible α-adjacency pairs:
A8 and A4 (or A0 and A1) in 2D
A26 and A6 (or A0 and A2), and A18 and A6 (or A1 and A2) in 3D
19/25
Switch Adjacency (As, s-Adjacency)
Switch adjacency avoids topological conflicts in 2D images
A relation As on a set of 2D grid points is called switch adjacency iff it contains
4-adjacency (i.e., As ⊇ A4) and exactly one of the two diagonally adjacent pixels in
each 2×2 block of pixels:
Switch to the left Switch to the right
The states of the switches can be driven by locations and/or pixel values
Regular switching Regular switching Irregular switching
20/25
Incidence Relation
Two sets are called incident iff one of them contains the other (i.e., any set is incident
with itself)
A 3D grid vertex (0-cell) is incident with six grid edges (1-cells); a grid square (2-cell)
is incident with four grid edges; and a grid cube (3-cell) is incident with 12 grid edges
The incidence relation between all the cells defines grid cell incidence model
(incidence grid)
0-, 1-, and 2-cells Incidence graph
21/25
Paths in Incidence Grids
1-path of 2-cells 0-path of 1-cells
2-path of 3-cells 1-path of 2-cells 0-path of 1-cells
22/25
Complete Subsets in Incidence Grids
A subset M of an incidence grid is called complete iff, for any cell c such that all cells
incident with c and of higher dimensions than c are in M, we also have c ∈ M
Add the minimum number of cells to make the given subset of an incidence grid complete
23/25
Complete Subsets in Incidence Grids
A subset M of an incidence grid is called complete iff, for any cell c such that all cells
incident with c and of higher dimensions than c are in M, we also have c ∈ M
Add the minimum number of cells to make the given subset of an incidence grid complete
24/25
Summary: Commonly Used Models in Digital Geometry
25/25