COMP 3317 Computer Vision
Tutorial 2
TA: Lyu Zhengyao
1
In This Tutorial
o About Me
o Review on Digital Image Processing
o Exercises on Digital Image Processing
o Reminders on Assignment_1
2
v About Me
• Name : Lyu Zhengyao
• Office : CB 411, Chow Yei Ching Building
• Email : [email protected]
• Consultation Hours : Tuesday, 2 pm – 4 pm
3
v Concepts
Ø Digital image
Sampling Spatial resolution Sampling checkerboards
Quantization Gray-level resolution False contouring
Ø Basic relationships between pixels
Neighbors Adjacency Path Connectivity Distance
N4 4-adjacent 4-path Connected component Euclidean distance
N8 8-adjacent 8-path Connected set City-block distance (D4 distance)
ND m-adjacent m-path Chessboard distance (D8 distance)
Dm distance
4
v Concepts
Ø Sampling checkerboards
5
v Concepts
Ø False contouring
6
v Questions
o Down-sampling of an image will not cause contour artifacts in an image.
o A binary image always has lower spatial resolution than an 8-bit gray scale
image.
o An 8-bit image has always higher size than a 2-bit image.
o Which type of resolution depends on Nyquist sampling theory?
o An 8-bit image is represented by a 4-bit per pixel display. Which operation
will be applied to the input image in order to be able to be displayed?
✶ Nyquist sampling theory : A bandlimited continuous-time signal can be sampled and perfectly reconstructed
from its samples if the waveform is sampled over twice as fast as it's highest frequency component.
𝑓! > 2𝑓"#$ 7
v Questions
✓ o Down-sampling of an image will not cause contour artifacts in an image.
✘ o A binary image always has lower spatial resolution than an 8-bit gray scale
image.
✘ o An 8-bit image has always higher size than a 2-bit image.
o Which type of resolution depends on Nyquist sampling theory?
Spatial resolution
o An 8-bit image is represented by a 4-bit per pixel display. Which operation
will be applied to the input image in order to be able to be displayed?
Quantization
✶ Nyquist sampling theory : A bandlimited continuous-time signal can be sampled and perfectly reconstructed
from its samples if the waveform is sampled over twice as fast as it's highest frequency component.
𝑓! > 2𝑓"#$ 8
Ø Neighbors of a pixel
p p p
N4 (p) ND (p) N8 (p)
N4 (p) ∪ ND (p)
q ∈ N4 (p) q ∈ N8 (p)
q ∈ ND (p) q ∈ N8 (p)
9
Ø Adjacency
4-adjacent q ∈ N4 (p) 8-adjacent
4-adjacent
m-adjacent
8-adjacent q ∈ N8 (p)
8-adjacent m-adjacent
m-adjacent q ∈ N4 (p) , or
q ∈ ND (p) and N4 (p) ∩ N4 (q) is empty
ü Mixed adjacency is a modification of 8-adjacency,
and is introduced to eliminate the ambiguities that may result from using 8-adjacency.
q q
0 1 1 0 1 1
0
p1 0 0
p
1 0
0 0 1 0 0 1
8-adjacent m-adjacent
10
Ø Path
4-path
8-path ü Depending on the type of adjacency
m-path
Ø Connectivity
• For any pixel p in S, the set of pixels in S that are
connected to p, is a connected component of S.
• If S has only one connected component, then S is
called a connected set.
11
2 1 2
In this case, pixels having a distance from (x, y) that is less than2or equal to som
Ø Distance example, the pixels with distance ≤ 2 from (x, y) (the center point) form the follo
The pixels with = 1 are the 4-neighbors of (x, y).
2
Euclidean distance The distance (called the chessboard distance) between p and2q is
1 defined
2 as
𝑫𝒆 = 𝒙−𝒔 𝟐 + 𝒚−𝒕 𝟐
2 1 0 1 2
𝑫( 𝟒, ) = max(| − |, | − |)
2 1 2
City-block distance (D4 distance)
In this case, the pixels with distance from (x, y) less than or equal2 to some value
𝑫 𝟒 = with
pixels 𝒙 − 𝒔distance
+ 𝒚 −≤𝒕2 form the following contours of constant distance:
The pixels with = 1 are the 4-neighbors of (x, y).
Chessboard distance (D8 distance) 2 2 2 2 2
The distance (called the chessboard distance) between p 2
and1 q 1is defined
1 2 as
𝑫𝟖 = 𝐦𝐚𝐱 𝒙 − 𝒔 , 𝒚 − 𝒕
𝑫𝟖 2 1 0 1 2
Dm distance ( , )=2 max(|
1 1 1− 2 |, | − |)
• length of the shortest m-path between 2 pixels 2 2 2 2 2
In this case, the pixels with distance from (x, y) less than or equal to some value
pixels
The with
pixels with = 1≤
distance 2 form
are the following
the 8-neighbors contours
of the pixel atof(x,
constant
y). distance:
Note that the and 2 2 2 of2any
distances between p and q are independent 2
12 paths th
2 of
distances involve only the coordinates of the points. In the case 1 m-adjacency,
1 1 2 how
v Exercise - 1
Ø Consider the two image subsets, S1 and S2 , shown in the following figure.
For V = {1}, determine whether these two subsets are
a) 4-adjacent,
b) 8-adjacent,
S1 S2
c) m-adjacent. 0 0 0 0 0 0 0 1 1 0
1 0 0 1 0 0 1 0 0 1
1 0 0 1 0 1 1 0 0 0
0 0 1 1 1 0 0 0 0 0
0 0 1 1 1 0 0 1 1 1
13
v Exercise - 1
Ø Consider the two image subsets, S1 and S2 , shown in the following figure.
For V = {1}, determine whether these two subsets are
a) 4-adjacent,
S1 and S2 are NOT 4-adjacent,
because q is not in the set N4 (p) S1 S2
b) 8-adjacent, 0 0 0 0 0 0 0 1 1 0
S1 and S2 are 8-adjacent, 1 0 0 1 0 0q1 0 0 1
because q is in the set N8 (p)
1 0 0 1 0 1 1 0 0 0
c) m-adjacent. p
0 0 1 1 1 0 0 0 0 0
S1 and S2 are m-adjacent,
0 0 1 1 1 0 0 1 1 1
because q is in the set ND (p) and
the set N4 (p) ∩ N4 (q) is empty.
14
v Exercise - 2
Ø Consider the image subset shown below.
Let V = {1,2} be the set of gray-level values used to define adjacency.
Find the shortest 4-Path, 8-Path, and m-Path between pixel p and q.
q
3 1 2 1
2 2 0 2
1 2 1 1
1 0 1 2
p
15
v Exercise - 2
Ø Consider the image subset shown below.
Let V = {1,2} be the set of gray-level values used to define adjacency.
Find the shortest 4-Path, 8-Path, and m-Path between pixel p and q.
ü 4-Path : q ü 8-Path : ü m-Path :
q q
3 1 2 1 3 1 2 1 3 1 2 1
2 2 0 2 2 2 0 2 2 2 0 2
1 2 1 1 1 2 1 1 1 2 1 1
1 0 1 2 1 0 1 2 1 0 1 2
p p p
ü length = 6 ü length = 4 ü length = 6
✧ You can have other answers with the SAME shortest length. 16
v Exercise - 3
Ø Consider the image subset shown below.
Let V = {0, 1} be the set of gray-level values used to define adjacency.
Q1 : find the number of connected componets if
a) 4-adjacent,
b) 8-adjacent, 3 3 2 1
c) m-adjacent, 0 2 0 2
Is considered.
1 2 1 1
3 0 1 2
17
v Exercise - 3
Ø Consider the image subset shown below.
Let V = {0, 1} be the set of gray-level values used to define adjacency.
Q1 : find the number of connected componets if
a) 4-adjacent,
b) 8-adjacent, 3 3 2 1
c) m-adjacent, 0 2 0 2
Is considered.
1 2 1 1
3 0 1 2
18
v Exercise - 3
Ø Consider the image subset shown below.
Let V = {0, 1} be the set of gray-level values used to define adjacency.
Q1 : find the number of connected componets if
a) 4-adjacent,
b) 8-adjacent, 3 3 2 1
c) m-adjacent, 0 2 0 2
Is considered.
1 2 1 1
3 0 1 2
19
v Exercise - 3
Ø Consider the image subset shown below.
Let V = {0, 1} be the set of gray-level values used to define adjacency.
Q1 : find the number of connected componets if
a) 4-adjacent,
b) 8-adjacent, 3 3 2 1
c) m-adjacent, 0 2 0 2
Is considered.
1 2 1 1
3 0 1 2
20
v Exercise - 3
Ø Consider the image subset shown below.
Let V = {0, 1} be the set of gray-level values used to define adjacency.
Q2 : Compute the following distance between pixel p and q :
a) Euclidean distance,
b) City-Block Distance (D4 distance),
3 3 2 1
c) Chessboard Distance (D8 distance),
0 2 0 2
d) Dm distance, p
(x, y) 1 2 1 1 q
3 0 1 2 (s, t)
21
v Exercise - 3
Ø Consider the image subset shown below.
Let V = {0, 1} be the set of gray-level values used to define adjacency.
Q2 : Compute the following distance between pixel p and q :
a) Euclidean distance, 0 1 2 3
b) City-Block Distance (D4 distance),
3 3 2 1
c) Chessboard Distance (D8 distance),
0 2 0 2
d) Dm distance, p
(x, y) 1 2 1 1 q
ü 𝑫𝒆 = 𝒙−𝒔 𝟐 + 𝒚−𝒕 𝟐
3 0 1 2 (s, t)
= 𝟎−𝟑 𝟐 + 𝟏−𝟐 𝟐
= 𝟏𝟎 22
v Exercise - 3
Ø Consider the image subset shown below.
Let V = {0, 1} be the set of gray-level values used to define adjacency.
Q2 : Compute the following distance between pixel p and q :
a) Euclidean distance, 0 1 2 3
b) City-Block Distance (D4 distance),
3 3 2 1
c) Chessboard Distance (D8 distance),
0 2 0 2
d) Dm distance, p
(x, y) 1 2 1 1 q
ü 𝑫𝟒 = 𝒙 − 𝒔 + 𝒚 − 𝒕 3 0 1 2 (s, t)
= 𝟎−𝟑 + 𝟏−𝟐
=𝟒
23
v Exercise - 3
Ø Consider the image subset shown below.
Let V = {0, 1} be the set of gray-level values used to define adjacency.
Q2 : Compute the following distance between pixel p and q :
a) Euclidean distance, 0 1 2 3
b) City-Block Distance (D4 distance),
3 3 2 1
c) Chessboard Distance (D8 distance),
0 2 0 2
d) Dm distance, p
(x, y) 1 2 1 1 q
ü 𝑫𝟖 = 𝐦𝐚𝐱 𝒙 − 𝒔 , 𝒚 − 𝒕 3 0 1 2 (s, t)
= 𝐦𝐚𝐱 𝟎 − 𝟑 , 𝟏 − 𝟐
=𝟑
24
v Exercise - 3
Ø Consider the image subset shown below.
Let V = {0, 1} be the set of gray-level values used to define adjacency.
Q2 : Compute the following distance between pixel p and q :
a) Euclidean distance, 0 1 2 3
b) City-Block Distance (D4 distance),
3 3 2 1
c) Chessboard Distance (D8 distance),
0 2 0 2
d) Dm distance, p
(x, y) 1 2 1 1 q
(consider V for the shortest m-path)
3 0 1 2 (s, t)
ü 𝑫𝒎 = 𝟓
25
v Assignment - 1
Ø Topic
• Digital Image Processing (lecture 2)
• A written assignment
Ø Submission
• Please submit your answer (a PDF File) to Moodle by the deadline.
• Will be available to you on Feb 1, 2024 (Thursday)
• Deadline : 23:59, Feb 7, 2024 (Wed)
• We DO NOT accept any late submission.
26
Ø Check Deadlines
Ø Download assignment sheets / Submit your answers
27
Ø If you have any questions about Assignment 1, we encourage you to post your question(s)
in the corresponding discussion forum on HKU Moodle.
28
