National University of Sciences and

Technology (NUST)
School of Electrical Engineering and Computer Science
(SEECS)

Digital Image Processing

1 Khawar Khurshid
 Sampling
Quantization
Interpolation
2 Khawar Khurshid
 Sampling and Quantization
Sampling:
Digitization of the spatial coordinates (x,y)

Quantization:
Digitization in amplitude (also known as gray
level quantization)

• 8 bit quantization: 28 =256 gray levels

(0: black, 255: white)

• 1 bit quantization: 21 = 2 gray levels

(0: black, 1: white)

3 Khawar Khurshid
 Sampling

4 Khawar Khurshid
 Sampling

5 Khawar Khurshid
 Quantization – (Example)

Return change using only

these notes
6 Khawar Khurshid
 Quantization – (Example)

50
For Rs. 3 Return 5 45

Change you return

40
For Rs. 7 Return 5
35

For Rs. 9 Return 10

30
25

For Rs. 12 Return 10 20

15

For Rs. 23 Return 25 10

5
… … 0
0 5 10 15 20 25 30 35 40 45 50

Actual change

7 Khawar Khurshid
 Quantization – (Example)

Discrete color output

Continuous colors mapped to a

finite, discrete set of colors.

Continuous color input

8 Khawar Khurshid
 Quantization – (Example)

16 million colors

16 colors

9 Khawar Khurshid
 Sampling and Quantization

Pixel Grid

Real Image Sampled Quantized Sampled &

Quantized

10
Khawar Khurshid
 Sampling and Quantization

11
Khawar Khurshid
 Sampling and Quantization

12
Khawar Khurshid
 Sampling and Quantization

256x256 128x128 64x64 32x32

256 gray levels

16 gray levels 8 gray levels 4 gray levels Binary Image

13 Khawar Khurshid
 Interpolation

14 Khawar Khurshid
 Interpolation

Why?

• Changing Perspective
• Rotation
• Resizing
• Warping

15
Khawar Khurshid
 Interpolation

Why?

• Changing Perspective
• Rotation
• Resizing
• Warping

16
Khawar Khurshid
 Interpolation

Why?

• Changing Perspective
• Rotation
• Resizing
• Warping

17
Khawar Khurshid
 Interpolation

Why?

• Changing Perspective
• Rotation
• Resizing
• Warping

18
Khawar Khurshid
 Interpolation

Why?

• Changing Perspective
• Rotation
• Resizing
• Warping

19
Khawar Khurshid
 Nearest Neighbor Replacement

Simply Replicate the value from neighboring

pixels.
1 0 1

1 0 1
1 1 0 1 1 0
1 0 1

1 0 1
20
Khawar Khurshid
 Nearest Neighbor Replacement

Adds blocky effect.

1 1 0 0 0 1 1
1 1 0 0 0 1 1
1 0 1 1 1 1 1 1 0 0
1 1 0 1 1 1 1 1 0 0
1 0 1 1 1 1 1 1 0 0
1 1 0 0 0 1 1
1 1 0 0 0 1 1
21
Khawar Khurshid
 Interpolation
Nearest-neighbor Interpolation

22
Khawar Khurshid
 Linear Interpolation

For example: if you

wanted to know the
temperature at 12PM

but only measured it at

11AM and 1PM.

you could estimate its

value by performing a
linear interpolation:
23
Khawar Khurshid
 1-D Interpolation

Interpolation works by using known data to

estimate values at unknown points.

24
Khawar Khurshid
 1-D Interpolation

Linear Interpolation: Fit a linear function piecewise

between the points.

25
Khawar Khurshid
 1-D Interpolation

Quadratic: Fit a Quadratic Polynomial between the three

points.

26
Khawar Khurshid
 1-D Interpolation

Fitting Polynomial to data points.

27
Khawar Khurshid
 1-D Interpolation
Degree Polynomial How it looks Req. Pts.
Zero
f(x) = 0 None
Polynomial
horizontal line
0 f(x) = a0 with y-intercept 1
a0
an oblique line
1 (Linear) f(x) = a0 + a1x with y-intercept 2
a0 and slope a1
2 Parabola
f(x) = a0 + a1x + a2x2 3
(Quadratic)
4
f(x) = a0 + a1x + a2x2+
3 (Cubic) Spline
a3x3

• No. of unknowns in a polynomial of degree n-1 = n

• Select n nearest known neighbours to generate n equations
• Solve the linear system of equations to estimate the constants
• Simply put the unknown x value and interpolate the y value
28
Khawar Khurshid
 Linear Interpolation
5
|
4
|

What is the
|
3

value of y at x=
|

2.5?
2
|
1

| | | | | |
|
|

| 1 2 3 4 5

29
Khawar Khurshid
 Linear Interpolation
5
|

What is the
4
|

value of y at x=
|
3

2.5
|
2

Y= 2.5.
|
1

| | | | | |
|
|

| 1 2 3 4 5

30
Khawar Khurshid
 Linear Interpolation

• Equation of a line

y1 − y0
y= (x − x0 ) + y0
x1 − x0

• Interpolation using Linear Polynomial

– y = a0 + a1x
– Requires two unknowns
31
Khawar Khurshid
 Bi-linear Interpolation

Activity

• 3-volunteers
32
Khawar Khurshid
Bi-linear Interpolation

X1 X X2

Which point has more

influence on X ?

Khawar Khurshid
 Bi-linear Interpolation

Pixel 10 More ??? Less

200
value Influence Influence

X1=1 X = 10 X2 = 50

Calculate f(X) ?
Khawar Khurshid
 Bi-linear Interpolation

Pixel 10 More ??? Less

200
value Influence Influence

X1=1 X = 10 X2 = 50

Calculate f(X) ?
Khawar Khurshid
 Bi-linear Interpolation
Pixel value
F(X1) = 10 ??? F(X2) = 200

X1=10 X = 20 X2 = 50

𝑿𝟐−𝑿 𝑿−𝑿𝟏
F(X) = ∗ 𝑭 𝑿𝟏 + ∗ 𝑭 𝑿𝟐
𝑿𝟐−𝑿𝟏 𝑿𝟐−𝑿𝟏

F(X) = (30/40) * 10 + (10/40) * 200

Khawar Khurshid
 Bi-linear Interpolation
Pixel value
F(X1) = 10 ??? F(X2) = 200

X1=10 X = 20 X2 = 50

F(X) = (30/40) * 10 + (10/40) * 200

More Less
Influence Influence
Khawar Khurshid
Bi-linear Interpolation

• Key Points:

– Q11 = (x1, y1), Q12 = (x1, y2),

– Q21 = (x2, y1), Q22 = (x2, y2).

• Linear interpolation in the x-

direction followed by linear
interpolation in y-direction

Khawar Khurshid
 Bi-linear Interpolation

• Key Points:

– Q11 = (x1, y1), Q12 = (x1, y2),

– Q21 = (x2, y1), Q22 = (x2, y2).

• Linear interpolation in the x-

direction followed by linear
interpolation in y-direction

40
Khawar Khurshid
 Bi-linear Interpolation: homework

[Link] Khawar Khurshid

 Interpolation

Nearest Neighbor

Bi-Linear

42
Khawar Khurshid
 Interpolation

215

128

43
Khawar Khurshid
 Interpolation

44
Khawar Khurshid
 Interpolation
Cubic Interpolation

45
Khawar Khurshid
 Interpolation

46
Khawar Khurshid
 Interpolation

47
Khawar Khurshid
 Interpolation

48
Khawar Khurshid
 Interpolation

49
Khawar Khurshid
 Interpolation

50
Khawar Khurshid
 Interpolation

51
Khawar Khurshid
 Interpolation – (Comparison)

We’ll enlarge this image

by a factor of 4 …

… via bilinear interpolation

and compare it to a nearest
neighbor enlargement.

52
Khawar Khurshid
 Interpolation – (Comparison)

Original
Image

To better see what happens, we’ll look at the parrot’s eye.

53
Khawar Khurshid
 Interpolation – (Comparison)

Pixel replication Bilinear interpolation

54
Khawar Khurshid
 Interpolation – (Comparison)

Pixel replication Bilinear interpolation

55
Khawar Khurshid
 Interpolation – (Non Integer)

Zoom in on a
section for a
closer look at
the process

Example:
resize to 3/7
of the original
56
Khawar Khurshid
 Interpolation – (Non Integer)

3/7 resize

Zoom in for a
better look

57
Khawar Khurshid
 Interpolation – (Non Integer)

3/7 resize

Outlined in
blue: 7x7
pixel squares

58
Khawar Khurshid
 Interpolation – (Non Integer)

3/7 resize

In yellow: 3 pixels
for every 7 rows,
3 pixels for every
7 cols.

59
Khawar Khurshid
 Interpolation – (Non Integer)

3/7 resize

Keep the
highlighted
pixels…

60
Khawar Khurshid
 Interpolation – (Non Integer)

3/7 resize

… don’t keep
the others.

61
Khawar Khurshid
 Interpolation – (Non Integer)

3/7 resize

Copy them into

a new image.

62
Khawar Khurshid
 Interpolation – (Non Integer)

3/7 resize

Copy them into

a new image.

63
Khawar Khurshid
 Interpolation – (Non Integer)

3/7 times the

linear dimensions
of the original

64
Khawar Khurshid
 Interpolation – (Non Integer)

Original
image

Detail of
resized image

Resize to 3/7 of
the original dims.

65
Khawar Khurshid
 Interpolation – (Non Integer)

7/3 resize

Original
image
Pixels spread out … then filled in.
for a 7/3 resize …

66
Khawar Khurshid
 Interpolation – (Non Integer)

7/3 resize

Each 3x3 block … is spread out over

of pixels from a 7x7 block here
here …

Original
image Detail

67
Khawar Khurshid
 Interpolation – (Non Integer)

7/3 resize

3x3 blocks
distributed over
7x7 blocks

68
Khawar Khurshid
 Interpolation – (Non Integer)

7/3 resize

Empty pixels filled

with color from non-
empty pixel

69
Khawar Khurshid
 Interpolation – (Non Integer)

7/3 resize

Empty pixels filled

with color from non-
empty pixel

70
Khawar Khurshid
 Interpolation – (Non Integer)

Original
image
7/3 resized

71
Khawar Khurshid
 Interpolation
• Non-adaptive algorithms

– Examples
• nearest neighbour, bilinear, bicubic, spline etc.
– Depending on their complexity, these use anywhere from 0 to 256 (or more)
adjacent pixels when interpolating.
– The more adjacent pixels they include, the more accurate they can become,
but this comes at the expense of much longer processing time.
– These algorithms can be used to both distort and resize a photo

• Adaptive algorithms

– Many of these apply a different version of their algorithm (on a pixel-by-

pixel basis) when they detect the presence of an edge-- aiming to minimize
unsightly interpolation artifacts in regions where they are most apparent.

– These algorithms are primarily designed to maximize artifact-free detail in

enlarged photos, so some cannot be used to distort or rotate an image.

72
Khawar Khurshid
 End
Sampling, Quantization,
Interpolation

73 Khawar Khurshid