‫هللا الر ْ نمْح ِِ الرِح ِمِ‬

‫ب ِْس ِم ِ‬

‫اللهُم عن ِل ْمننا نما ي ن ْن نفعننا نوانْ نف ْعننا ِب نما عنل ْم نَتننا نو ِِ ْْ نَ ِعلْ ِما‬
 Digital Image Processing
BME 430
2- Basic calculations on pixel level

By
Prof. Nahed H. Solouma
2
 Objectives
By the end of this topic, the student should be able to:
• Understand the pixel neighborhood.
• Understand the pixel adjacency.
• Understand and apply the different types of distance
measurements.
• Understand the meaning of digital path, connected
component, boundary and a region.
• Understand the distance transform.

3
 Pixel Neighborhood
Neighbors of a pixel 𝑝(𝑥, 𝑦) (notice the colors)
Four neighbors 𝑁4 (𝑝): Eight neighbors 𝑁8 (𝑝):
(vertical + horizontal) 𝑁4 (𝑝) + 𝑁𝐷 (𝑝)
Diagonal neighbors 𝑁𝐷 (𝑝)

𝑁4 𝑝 = {𝑝 𝑥 + 1, 𝑦 , 𝑝 𝑥 − 1, 𝑦 , 𝑁𝐷 𝑝
𝑝 𝑥, 𝑦 + 1 , 𝑝(𝑥, 𝑦 − 1)} = {𝑝 𝑥 + 1, 𝑦 + 1 , 𝑝 𝑥 + 1, 𝑦 − 1 ,
𝑝(𝑥 − 1, 𝑦 + 1), 𝑝(𝑥 − 1, 𝑦 − 1)} 4
 Pixel Adjacency
The set of pixels 𝑆 that is adjacent to a pixel 𝑝 𝑥, 𝑦 is composed of its neighbors that have
graylevels in a specified range 𝑉.
There are 3 types of adjacency:
• 4-adjacency: a pixel 𝑞 is 4-adjacent to pixel 𝑝 if 𝑞 is in the set 𝑁4 (𝑝) and graylevels, of
both, are in a specified range 𝑉
• 8-adjacency: a pixel 𝑞 is 8-adjacent to pixel 𝑝 if 𝑞 is in the set 𝑁8 (𝑝) and graylevels, of
both, are in a specified range 𝑉
(a) (b) (c)

(a) An arrangement of pixels. (b) 4-adjacent

(b) Pixels that are 8-adjacent (adjacency is shown by dashed
lines; note the ambiguity).
5
 Pixel Adjacency
• m-adjacency (mixed adjacency).Two pixels 𝑝 and 𝑞 with values in the range 𝑉 are m-
adjacent if
 𝑞 is in 𝑁4 (𝑝) OR
 𝑞 is in 𝑁𝐷 (𝑝) AND the set {𝑁4 (𝑝) ∩ 𝑁4 (𝑞)} has no pixels whose values are
from V.
(a) (b) (c) (c)

(a) An arrangement of pixels.

(b) Pixels that are 8-adjacent (note the ambiguity).
(c) m-adjacency. (d) result of next runs.
Note: getting the pixel adjacency allow to detect a path between two distant pixels.
It also allows for the detection of connected areas. 6
 Connectivity
A digital path, a connected component , a region and a boundary:
• A digital path (line or curve) from pixel 𝑝 𝑎, 𝑏 to pixel 𝑞(𝑠, 𝑡) is
a sequence of distinct pixels with coordinates
𝑝 𝑥0, 𝑦0 , 𝑝 𝑥1, 𝑦1 , … , 𝑝 𝑥𝑛, 𝑦𝑛
where 𝑥0 , 𝑦0 = a, b , 𝑥𝑛 , 𝑦𝑛 = (𝑠, 𝑡) and
𝑥𝑖 , 𝑦𝑖 is adjacent to 𝑥𝑖−1 , 𝑦𝑖−1 for 1 ≤ 𝑖 ≤ 𝑛, 𝑛 + 1 is the
length of the path.
If 𝑥0 , 𝑦0 = 𝑥𝑛 , 𝑦𝑛 , then the path is a closed path or contour and
its size is 𝑛 pixels.
There are 4-path and m-path according to the used adjacency.
7
 Connectivity
A connected component: is a subset of pixels that are connected (adjacent) usually
form an object in the image. If 𝑆 ⊆ 𝑓 𝑥, 𝑦 where 𝑓(𝑥, 𝑦) is an image, then
the 2 pixels 𝑝 𝑎, 𝑏 , 𝑞 𝑠, 𝑡 are said to be connected within 𝑆 if there is a
path between them that lies entirely inside 𝑆.
A connected component in 𝑆 is a collection of connected pixels lay entirely in 𝑆.
A subset 𝑆 is called a connected set if all of its pixels are connected

A set 𝑆 with 3 connected components in the ranges

{3-5}, {0-2}, {7-13}.
Note the minimum number of pixels that can be
A set 𝑆 with 4 connected components within
considered as a component must be initially defined.
8
 Connectivity
 A region: of an image is a connected set.
• Adjacent regions: 𝑅𝑖 and 𝑅𝑗 are said to be adjacent if 𝑅𝑖 ∪ 𝑅𝑗 forms a connected
set
• Disjoint regions: regions that are not adjacent are said to be disjoint.
 Connected components and regions are used interchangeably in literatures
 Example of connected components in medical images

Left: a CT slice image of the brain,

Right: about 20 connected components (objects in the
image). Minimum component size is 100 pixels
Ref. https://itk.org/Wiki/ITK/Examples/ImageProcessing/ScalarConnectedComponentImageFilter 9
 Connectivity
A boundary: (also called the border or contour) of a region 𝑅:
 The contour, or the border of a region, is the set of pixels in the
region that have at least one neighbor from the background
 The contour is usually a closed path

Note: a region in an image is called the

foreground and its surrounding is the
background or complement

A region and its boundary: : https://www.researchgate.net/profile/Qianjin_Feng

10
 Distance Measurements
For pixels 𝑝(𝑎, 𝑏), 𝑞(𝑠, 𝑡) and 𝑧(𝑣, 𝑤), 𝐷 is a distance function or
metric if:
• 𝐷 𝑝, 𝑞 ≥ 0 𝐷 𝑝, 𝑞 = 0 iff 𝑝 𝑖𝑠 𝑞
• 𝐷 𝑝, 𝑞 = 𝐷(𝑞, 𝑝) and
• 𝐷 𝑝, 𝑧 ≤ 𝐷 𝑝, 𝑞 + 𝐷(𝑞, 𝑧)

Types of distances:
1. Euclidean distance
2. City block distance
3. Chessboard distance

11
 Distance Measurements
The Euclidean distance between 𝑝(𝑎, 𝑏) and 𝑞(𝑠, 𝑡) is defined as:
1
𝐷𝑒 (𝑝, 𝑞) = (𝑎 − 𝑠)2 +(𝑏 − 2
𝑡) 2
• The pixels have 𝐷𝑒 ≤ 𝑟 from a central pixel at 𝑝(𝑎, 𝑏) form a disc of radius 𝑟

Distance function forms a disc-shaped of radius = 50 pixels

Radius = 5 pixels Numbers along radius = 3 pixels 12

 Distance Measurements
• The distance 𝐷4 (also called city-block distance) between
𝑝(𝑎, 𝑏) and 𝑞(𝑠, 𝑡) is defined as:
𝐷4 𝑝, 𝑞 = 𝑎 − 𝑠 + 𝑏 − 𝑡

• The pixels have 𝐷4 ≤ 𝑟 from 𝑝(𝑎, 𝑏) form a diamond centered

at 𝑝(𝑎, 𝑏) as shown

Diamond-shaped
or city block
distance

13
 Distance Measurements
The distance 𝐷8 (also called chessboard distance) between 𝑝(𝑎, 𝑏) and
𝑞(𝑠, 𝑡) is defined as:
𝐷8 𝑝, 𝑞 = max( 𝑎 − 𝑠 , 𝑏 − 𝑡 )

The pixels have 𝐷8 ≤ 𝑟 from 𝑝(𝑎, 𝑏) form a square centered at

𝑝(𝑎, 𝑏) as shown.

Chessboard distance

14
 Distance Transform
 It transforms the pixels values (in an object) to their distances to
the closest boundary point.
 Usually applied to binary images and results in a graylevel image
that looks like the input image,
 Example:
Input images

Distance Transform

Reference: https://homepages.inf.ed.ac.uk/rbf/HIPR2/distance.htm 15
 Distance Transform

The distance transform is

sometimes very sensitive to
An example of applying the distance
small changes in the object.
transform to a real world image
Reference: https://homepages.inf.ed.ac.uk/rbf/HIPR2/distance.htm 16
 Assignment 2 (5 pt.)
• Write a Matlab program that initialize an 𝑚 × 𝑛 2D
array of zeros and update this array with the distance
of each cell (or pixel) from the central one. Apply the
three different methods of distance calculation to get
3 new arrays of distances.
• Solve the above assignment twice: 1) using your own
code (2.5 pts.) and 2) using Matlab built-in distance
transform method bwdist(z) (2.5 pts.)

17
Thank you

18