3

Learning Objectives
This chapter focuses on two-
dimensional convolution and correla-
tion. Convolution and correlation are the
basic operations of most image-analysis
systems. Step by step approaches to
two-dimensional convolution and cor-
relation through the graphical method,
matrix method and Z-transform meth-
od are given through suitable examples
in this chapter. After completing the
Convolution and
chapter, the reader should be familiar
with the following concepts:
computation of 2D convolution and Correlation
correlation through graphical
method
computation of 2D convolution and
correlation through Z-transform
Determination of 2D convolution and
correlation through matrix method
significance of 2D convolution and
correlation

3.1 INTRODUCTION
Convolution and correlation operations are basically used to extract information from images. Convolution
and correlation are basically linear and shift-invariant operations. The term linear indicates that a pixel is
replaced by the linear combination of its neighbours. The term shift invariant indicates that the same operation
is performed at every point in the image.
 Convolution and Correlation 85

Convolution is basically a mathematical operation where each value in the output is expressed as the
sum of values in the input multiplied by a set of weighting coefficients. Depending upon the weighting
coefficients, convolution operation is used to perform spatial domain low-pass and high-pass filtering of the
image. An image can be either smoothened or sharpened by convolving the image with respect to low-pass
and high-pass filter mask respectively. This principle is widely used in the construction of the image pyramid.
Convolution has a multitude of applications including image filtering, image enhancement, image restora-
tion, feature extraction and template matching.
The two-dimensional discrete convolution between two signals x[n1, n2] and h[n1, n2] is given by
∞ ∞
y[n1 , n2 ] = ∑ ∑ x( k1 , k2 )h( n1 − k1 , n2 − k2 ) (3.1)
k1=−∞ k2 =−∞

2D convolution can be represented as a sequence of two 1D convolutions only if the signals are separable.
Convolution can be performed either in the spatial domain or in the frequency domain.

3.2 2D CONVOLUTION THROUGH GRAPHICAL METHOD

In this section, the two-dimensional convolution is performed through graphical anaysis. The basic operations
involved in 2D convolution are folding, shifting and addition operations. The step-by-step approach to 2D
convolution through the graphical method is illustrated below:

Example 3.1 The input matrix x(m, n) and h(m, n). Perform the linear convolution between these two
matrices.

⎛1⎞⎟
⎛4 5 6⎞⎟ ⎜⎜ ⎟
x (m , n ) = ⎜⎜⎜ ⎟⎟ h (m , n ) = ⎜⎜⎜1⎟⎟⎟
⎝7 8 9⎟⎠ ⎜ ⎟⎟⎟
⎜⎝1⎠

Solution The indices of the given input matrices are given below:
⎛( 0,0 )⎞⎟
⎜⎜ 1 ⎟
⎛( 0,0 ) ( 0 ,1) ( 0 ,2 )⎞ ⎜⎜ ⎟⎟
⎜⎜ 4 5 6 ⎟⎟⎟ ⎜⎜ (1,0 ) ⎟⎟⎟
x( m, n) = ⎜⎜ ⎟ h( m, n) = ⎜⎜ 1 ⎟⎟⎟
⎜⎜ (1,0 ) (1,2) ⎟ ⎜⎜
⎜⎝ 7
(11
,)
⎟⎟⎟ ⎟
⎜⎜( 2,0 )⎟⎟
8 9 ⎠
⎜⎜ 1 ⎟⎟⎟
⎜⎝ ⎟⎠

Determining the dimension of the resultant matrix The dimension of the resultant matrix depends
upon the dimension of the input matrices, x(m, n) and h(m, n).The dimension of x(m, n) is 2 × 3
(two rows and three columns). The dimension of h(m, n) is 3 × 1 (three rows and one column).
The resultant matrix dimension is calculated as

⎧
⎪ ( No. of rows of x( m, n) + No. of rows of h( m, n) −1)
⎪
⎪
⎪
Dimension of reslutant matrix = ⎨ ×
⎪
⎪
⎪
⎩ ( No. of columns of x( m, n) + No. of columns of h( m, n) −1)
⎪
Dimension of resultant matrix = (2 + 3 − 1) × (3 + 1 − 1) = 4 × 3
86 Digital Image Processing

The resultant matrix y(m, n) of size 4 × 3 is given as

⎛ y ( 0, 0 ) y(0, 1) y(0, 2)⎞⎟
⎜⎜ ⎟
⎜⎜ y(1, 0) y(1, 1) y(1, 2) ⎟⎟⎟
y( m, n) = ⎜⎜ ⎟⎟
⎜⎜ y( 2, 0) y( 2, 1) y( 2,, 2)⎟⎟
⎜⎜ ⎟⎟
⎜⎝ y(3, 0) y(3, 1) y(3, 2) ⎠⎟

The graphical representation of x(m, n) is shown below:

x(m, n)
n

n=2 6 9
n=1 5 8
n=0 4 7
m
m=0m=1
Here, the encircled element is the origin. The graphical representation of h(m, n) and it’s folded version,
h(−m, −n) are given below:
h(m, n) h (−m, −n)
n n

1 1 1 1 1 1
m m
m=0 m=1 m=2 m = −2 m = −1 m = 0
1. To determine the value of y(0, 0)
The common values of x(m, n) and h(−m, −n) are multiplied and then added to get the value of y (0, 0).
The shaded circle indicates the common area between the two signals.

x (m, n) h(−m, −n)

n n

n=2 6 9 0 0
n=1 5 8 0 0
n=0 4 7 1 1 1 0
m m
m=0m=1 m = −2 m= −1 m = 0 m = 1

The value y(0, 0) is obtained as y(0, 0) = 4 × 1 = 4.

2. To determine the value of y(0,1)
Now the signal h(−m, −n) is shifted along the ‘n’ axis by one unit to get h(−m, 1−n) and x(m, n) is unal-
tered. The common value between the two signals is multiplied and then added to get y (0, 1).
 Convolution and Correlation 87

x (m, n) h (−m, 1−n)

n n

n=2 6 9 0 0
n=1 5 8 1 1 1 0

n=0 4 7 0 0 0 0
m m
m=0 m=1 m = −2 m = −1 m = 0 m = 1

The value of y(0, 1) is given as y(0, 1) = 5 × 1 = 5.

3. To determine the value of y(0, 2)
The value of h(−m, −n) is shifted by two units along the ‘n’ axis to get h(−m, 2−n). Then, the common
values between x (m, n) and h(−m, 2−n) are multiplied and then added to get y(0, 2).

x(m, n) h (−m, 2−n)

n n

n=2 6 9 1 1 1 0
n=1 5 8 0 0
n=0 4 7 0 0
m m
m=0 m=1 m = −2 m = −1 m = 0 m = 1

The resultant value of y(0, 2) is y(0, 2) = 6 × 1 = 6.

If we do one more shift of h(−m, −n) along the ‘n’ axis then there is no common value between
x(m, n) and h(−m, 3−n) so that the resultant value will be zero which is not illustrated here.
4. To determine the value of y(1, 2)
Here, h(−m, 2−n) is shifted along the ‘m’ axis to one unit towards right to get h(1−m, 2−n). Then the
common values between x(m, n) and h(1−m, 2−n) are multiplied and added to get y (1, 2).

x (m, n) h (1−m, 2−n)

n n

n=2 6 9 1 1 1
n=1 5 8 0 0
n=0 4 7 0 0
m m
m=0 m=1 m = −1 m = 0 m = 1

The final value of y (1, 2) = 6 × 1 + 9 × 1 = 15.

88 Digital Image Processing

5. To determine the value of y(1, 1)

Now the value of h(1−m, 2−n) is shifted down along the ‘n’ axis to get h(1−m, 1−n). The common
values between x(m, n) and h(1−m, 1−n) are multiplied and added to get y(1, 1).
x(m, n) h (1−m, 1−n)
n n

n=2 6 9 0 0
n=1 5 8 1 1 1
n=0 4 7 0 0
m m
m=0 m=1 m = −1 m = 0 m = 1

The value of y(1, 1) is obtained as y(1, 1) = 5 × 1 + 8 × 1 = 13.

6. To determine the value of y(1, 0)
Next, the value of h(1−m, 1−n) is shifted down along the ‘n’ axis by one unit to get h(1−m, −n) and
it is multiplied with x(m, n) and then added to get y(1, 0).

x (m, n) h(1−m, −n)

n n

n=2 6 9 0 0
n=1 5 8 0 0

n=0 4 7 1 1 1
m m
m=0 m=1 m = −1 m = 0 m = 1

There are two coincide values. Therefore, the result y(1, 0) = 4 × 1 + 7 × 1 = 11.
7. To determine the value of y(2, 0)
The signal h(1−m, −n) is shifted along the ‘m’ axis towards right by one unit to get h(2−m, −n). The
common value between the signals x(m, n) and h(2−m, −n) is multiplied and then added to get y(2, 0).

x(m, n) h (2−m, −n)

n n

n=2 6 9 0 0
n=1 5 8 0 0
n=0 4 7 1 1 1
m m
m=0 m=1 m=0 m=1m=2

The resultant value of y(2, 0) = 4 × 1 + 7 × 1 = 11.

 Convolution and Correlation 89

8. To determine the value of y(2, 1)

The signal h(2−m, −n) in the previous step is then shifted up along the ‘n’ axis by one unit to get
h(2−m, 1−n). This signal is multiplied with x(m, n) and added to get y(2, 1).

x(m, n) h (2−m, 1−n)

n n

n=2 6 9 0 0
n=1 5 8 10 1 1
n=0 4 7 0 0
m m
m=0 m=1 m=0 m=1m=2

The value y (2, 1) is obtained as y(2, 1) = 5 × 1 + 8 × 1 = 13.

9. To determine the value of y(2, 2)
The signal h(2−m, 1−n) is then shifted up by one unit along the ‘n’ axis to get h(2−m, 2−n). This
signal h(2−m, 2−n) is multiplied with x(m, n) and added to get y(2, 2).

x(m, n) h (2−m, 2−n)

n n

n=2 6 9 01 1 1
n=1 5 8 0 0
n=0 4 7 0 0
m m
m=0 m=1 m=0 m=1m=2

The resultant value y(2, 1) = 6 × 1 + 9 × 1 = 15.

10. To calculate the value of y(3, 2)
The signal h(2−m, 2−n) is shifted along the m-axis towards right by one unit to get h(3−m, 2−n). The
common values are multiplied and added to get y(3, 2).

x (m, n) h (3−m, 2−n)

n n

n=2 6 9 0 1 1 1
n=1 5 8 0 0
n=0 4 7 0 0
m m
m=0 m=1 m=0m=1m=2 m=3

The value of y(3, 2) = 9 × 1 = 9.

90 Digital Image Processing

11. To determine the value of y(3, 1)

x (m, n) h (3−m, 1−n)

n n

n=2 6 9 0 0
n=1 5 8 0 1 1 1
n=0 4 7 0 0
m m
m=0 m=1 m=0m=1m=2 m=3
y(3, 1) = 8 × 1 = 8.
12. To calculate the result of y(3, 0)
Finally the signal h(3−m, 1−n) is shifted down by one unit along the ‘n’ axis to get h(3−m, −n).
This signal is multiplied with x(m, n) and then added to get y(3, 0).

x (m, n) h (3−m, −n)

n n

n=2 6 9 0 0
n=1 5 8 0 0
n=0 4 7 0 1 1 1
m m
m=0 m=1 m=0m=1m=2 m=3
The value of y(3, 0) = 7 × 1 = 7.
The resultant values obtained from steps 1 to 12 are given below:

y(0, 0) = 4 y(0, 1) = 5 y ( 0, 2) = 6
y(1, 2) = 15 y(1, 1) = 13 y(1, 0) = 11
y( 2, 0) = 11 y( 2, 1) = 13 y( 2, 1) = 15
y(3, 2) = 9 y(3, 1) = 8 y(3, 0) = 7

Substituting the above values in the corresponding positions in the matrix and graphic form, the
resultant matrix is obtained as

y(m, n)
n
y(0, 0) y(0, 1) y(0, 2)
n=2 X X X X y(1, 0) y(1, 1) y(1, 2)
n=1 X X X X y(m, n) =
y(2, 0) y(2, 1) y(2, 2)
n=0 X X X X
m y(3, 0) y(3, 1) y(3, 2)
m=0 m=1m=2 m=3
 Convolution and Correlation 91

The final result in graphical and matrix representations is given below.

y(m, n)
n 4 5 6

n=2 6 15 15 9 11 13 15
y(m, n) =
n=1 5 13 13 8 11 13 15

n=0 4 11 11 7 7 8 9
m
m = 0m = 1m = 2 m = 3

Graphical representation Matrix representation

Example 3.2 Perform the linear convolution between the two matrices x(m, n) and h(m, n) given
below.

⎛ 1 2 3⎞⎟ ⎛1 1⎞⎟
⎜⎜ ⎟⎟ ⎜⎜ ⎟
x (m , n ) = ⎜⎜4 5 6⎟⎟ h (m , n ) = ⎜⎜1 1⎟⎟⎟
⎜
⎜⎜ ⎟
⎟ ⎜
⎜⎜ ⎟⎟
⎝7 8 9⎟⎠ ⎝1 1⎟⎠

Solution The indices of the given input matrices are shown below.

⎛( 0,0 ) ( 0 ,1) ( 0 ,2 )⎞ ⎡ ( 0,0 ) ( 0 ,1) ⎤

⎜⎜ 1
⎜⎜ 2 3 ⎟⎟⎟ ⎢ 1 1 ⎥
⎟ ⎢ ⎥
⎜⎜ (1,0 ) (11
,) (1,2) ⎟⎟⎟ ⎢ (1,0 ) , )⎥
(11
x( m, n) = ⎜⎜ 4 5 6 ⎟⎟⎟ h( m, n) = ⎢⎢ 1 1 ⎥⎥
⎜⎜ ⎟ ⎢ ( 2,0 )
⎜⎜( 2,0 ) ( 2,1) ( 2,,2)⎟⎟ ( 2,1) ⎥
⎢ ⎥
⎜⎜ 7 8 9 ⎟⎟⎟ ⎢ 1 1 ⎥
⎜⎝ ⎟⎠ ⎢⎣ ⎥⎦

Determining the dimension of the resultant matrix The dimension of the resultant matrix depends
on the dimensions of the input matrices, x(m, n) and h(m, n).The dimension of x(m, n) is 3 × 3 (three rows
and three columns). The dimension of h(m, n) is 3 × 2 (three rows and two columns). Therefore, the
resultant matrix dimension is calculated as

⎧
⎪ ( No. of rows of x( m, n) + No. of rows of h( m, n) −1)
⎪
⎪
Dimension of reslutant matrix = ⎪
⎨ ×
⎪
⎪
⎪
⎩ ( No. of columns of x( m, n) + No. of columns of h( m, n) −1)
⎪

Dimension of resultant matrix = (3 + 3 − 1) × (3 + 2 − 1) = 5 × 4

92 Digital Image Processing

The resultant matrix, y(m, n) of size 5 × 4 is given as

⎛ y ( 0, 0 ) y(0, 1) y(0, 2) y(0, 3)⎞⎟
⎜⎜ ⎟
⎜⎜ y(1, 0) y(1, 1) y(1, 2) y(1, 3) ⎟⎟⎟
⎜⎜ ⎟⎟
y( m, n) = ⎜⎜ y( 2,, 0) y( 2, 1) y( 2, 2) y( 2, 3)⎟⎟
⎜⎜ ⎟⎟
⎜⎜ y(3, 0) y(3, 1) y(3, 2) y(3, 3) ⎟⎟⎟
⎜⎜ ⎟
⎝ y( 4, 0) y( 4, 1) y( 4, 2) y( 4, 3)⎟⎠

The graphical representation of x (m, n) is shown below:

x(m, n)
n

n=2 3 6 9

n=1 2 5 8

n=0 1 4 7
m
m=0 m=1 m=2

The graphical representation of h(m, n) and it’s folded version, h(−m, −n) are given below:
h(m, n) h(−m, −n)
n n

n=1 1 1 1 1 1 1 n=0
m
n=0 1 1 1 1 1 1 n = −1
m
m=0 m=1 m=2 m = −2 m = −1 m = 0
1. To determine the value of y(0, 0) The signal h(m, n) is folded in the ‘m’ and ‘n’ axes to get h(−m, −n).
On multiplying the common values of x(m, n) with h(−m, −n) and then adding, we get y(0, 0).
x (m, n) h(−m, −n)
n n
n=2 3 6 9 0 0 0 n=2
n=1 2 5 8 0 0 0 n=1

n=0 0 0 1 4 7 1 1 1 0 0 n=0
m m
0 0 0 1 1 1 n = −1

m = −2 m = −1 m = 0 m = 1 m = 2 m = −2 m = −1 m = 0
The value of y(0, 0) = 1 × 1 = 1.
 Convolution and Correlation 93

2. To determine the value of y(0, 1) Next, the signal h(−m, −n) is shifted along the ‘n’ axis towards up
by one unit to get h(−m, 1−n). From the signal x(m, n) and h(−m, 1−n) we get the output y(0, 1).

x (m, n) h(−m, 1−n)

n n

n=2 3 6 9 0 0 0 n=2
n=1 0 0 2 5 8 1 1 1 0 0 n=1
n=0 0 0 1 4 7 1 1 1 0 0 n=0
m m
n = −1
m = −2 m = −1 m = 0 m = 1 m = 2 m = −2 m = −1 m = 0 m = 1 m = 2
The output y(0, 1) = 1 × 1 + 2 × 1 = 3.
3. Finding the value of y(0, 2) The signal h(−m, 2−n) is obtained by shifting the sigal h(−m, 1−n)
along the ‘n’ axis by one unit.

x (m, n) h(−m, 2−n)

n n

n=2 0 0 3 6 9 1 1 1 0 0 n=2
n=1 0 0 2 5 8 1 1 1 0 0 n=1
n=0 1 4 7 0 0 0 n=0
m m
n = −1
m = −2 m = −1 m = 0 m = 1 m = 2 m = −2 m = −1 m = 0 m = 1 m = 2

The signal y(0, 2) is obtained by multiplying the common elements of x(m, n) with h(−m, 2−n) and
then added to get y(0, 2) = 2 × 1 + 3 × 1 = 5.
4. Finding the value of y(0, 3) The signal h(−m, 3−n) is obtained by shifting the signal h(−m, 2−n)
along the ‘n’ axis by one unit. The value y(0, 3) is obtained from x(m, n) and h(−m, 3−n) which is
illustrated below.
x(m, n) h(−m, 3−n)
n n
0 0 0 1 1 1

n=2 0 0 3 6 9 1 1 1 0 0 n=2
n=1 2 5 8 0 0 n=1
n=0 1 4 7 0 0 0 n=0
m m
n = −1
m = −2 m = −1 m = 0 m = 1 m = 2 m = −2 m = −1 m = 0 m = 1 m = 2
The value y(0, 3) = 3 × 1 = 3.
94 Digital Image Processing

5. Finding the value of y(1, 3) The signal h(1−m, 3−n) is obtained by shifting h(−m, 3−n) along ‘m’
axis by one unit towards the right. The values that are common to the signal h(1−m, 3−n) and x(m, n)
are multiplied and then added to get y(1, 3).
x (m, n) h(1−m, 3−n)
n n
0 0 0 1 1 1

n=2 0 3 6 9 1 1 1 0 n=2
n=1 2 5 8 0 0 0 n=1

n=0 1 4 7 m m 0 0 0 n=0
n = −1
m = −1 m = 0 m = 1 m = 2 m = −2 m = −1 m = 0 m = 1 m = 2
The value y(1, 3) = 3 × 1 + 6 × 1= 9.
6. Finding the value of y(1, 2) The signal h(1−m, 2−n) is obtained from h(1−m, 3−n) by shifting
it down along the ‘n’ axis by a factor of one. The signal h(1−m, 2−n) is multiplied with x(m, n) and
then added to get y(1, 2).
x(m, n) h(1−m, 2−n)
n n

n=2 0 3 6 9 1 1 1 0 n=2
n=1 0 2 5 8 1 1 1 0 n=1

n=0 1 4 7 0 0 0 n=0
m m
n = −1
m = −1 m = 0 m = 1 m = 2 m = −2 m = −1 m = 0 m = 1 m = 2
The value y(1, 2) = 3 × 1 + 6 × 1 + 2 × 1 + 5 × 1 = 16.
7. Finding the value of y(1, 1) The signal h(1−m, 1−n ) is obtained from h(1−m, 2−n) by shifting it
down along the ‘n’ axis by a factor of one. The common values between the two signals are indicated
by shaded circle. The values in the shaded circles are multiplied and then added to get y(1, 1).
x(m, n) h(1−m, 1−n)
n n

n=2 3 6 9 0 0 0 n=2

n=1 0 2 5 8 1 1 1 0 n=1
n=0 0 1 4 7 1 1 1 0 n=0
m m
n = −1
m = −1 m = 0 m = 1 m = 2 m = −2 m = −1 m = 0 m = 1 m = 2
The value y(1, 1) = 2 × 1 + 5 × 1 + 1 × 1 + 4 × 1 = 12.
 Convolution and Correlation 95

8. Finding the value of y(1, 0) The signal h(1−m, −n) is obtained from h(1−m, 1−n) by shifting it
down along the ‘n’ axis by a factor of one. The signal h(1−m, −n) is multiplied with x(m, n) and then
it is added to get y (1, 0).

x (m, n) h(1−m, −n)

n n

n=2 3 6 9 0 0 0 n=2
n=1 2 5 8 0 0 0 n=1

n=0 0 1 4 7 1 1 1 0 n=0
m m
n = −1 0 1 4 1 1 1 n = −1
m = −1 m = 0 m = 1 m = 2 m = −2 m = −1 m = 0 m = 1 m = 2

The value y (1, 0) = 1 × 1 + 4 × 1 = 5.

9. Finding the value of y(2, 0) The signal h(2−m, −n) is obtained from h(1−m, −n) by shifting it
right along the ‘m’ axis by a factor of one. The signal h(2−m, −n) is multiplied with x(m, n) and then
it is added to get y (2, 0).
x (m, n) h(2−m, −n)
n n

n=2 3 6 9 0 0 0 n=2
n=1 2 5 8 0 0 0 n=1

n=0 1 4 7 1 1 1 n=0
m m
n = −1 0 0 1 1 1 n = −1
m=0m=1m=2 m = −2 m = −1 m = 0 m = 1 m = 2
The value y (2, 0) = 1 × 1 + 4 × 1 + 7 × 1 = 12.
10. Finding the value of y(2, 1) The signal h(2−m, 1−n) is obtained by shifting h(2−m, −n) along
the ‘n’ axis by a factor of one. The common values between x(m, n) with h(2−m, 1−n) are shown
by shaded circles. The output signal y (2, 1) is obtained by multiplying the common values and then
adding the resultant values.
x (m, n) h(2−m, 1−n)
n n
n=2 3 6 9 0 0 0 n=2

n=1 2 5 8 1 1 1 n=1
n=0 1 4 7 1 1 1 n=0
m m
n = −1 n = −1
m=0 m=1 m=2 m = −2 m = −1 m = 0 m = 1 m = 2
The value y (2, 1) = 1 × 1 + 4 × 1 + 7 × 1 + 2 × 1 + 5 × 1 + 8 × 1= 27.
11. Finding the value of y(2, 2) The signal h(2−m, 2−n) is obtained by shifting h(2−m, 1−n) along
the ‘n’ axis by a factor of one.
96 Digital Image Processing

x (m, n) h(2−m, 2−n)

n n
n=2 3 6 9 1 1 1 n=2

n=1 2 5 8 1 1 1 n=1
n=0 1 4 7 0 0 0 n=0
m m
n = −1 n = −1
m=0m=1m=2 m = −2 m = −1 m = 0 m = 1 m = 2

The resultant signal y(2, 2) = 3 × 1 + 6 × 1 + 9 × 1 + 2 × 1 + 5 × 1 + 8 × 1= 33.

12. Finding the value of y(2, 3) The signal h(2−m, 3−n) is obtained by shifting h(2−m, 2−n) along
the ‘n’ axis by a factor of one. The common values between x(m, n) and h(2−m, 3−n) is multiplied
and then added to get y(2, 3).

x(m, n) h(2−m, 3−n)

n n
0 0 0 1 1 1

n=2 3 6 9 1 1 1 n=2
n=1 2 5 8 0 0 0 n=1

n=0 1 4 7 m m 0 0 0 n=0
n = −1 n = −1
m=0m=1m=2 m = −2 m = −1 m = 0 m = 1 m = 2

The value y(2, 3) = 3 × 1 + 6 × 1 + 9 × 1 = 18.

13. Finding the value of y(3, 3) The signal h(3−m, 3−n) is obtained by shifting the signal h(2−m, 3−n)
along the m-axis towards right by a factor of one.

x (m, n) h(3−m, 3−n)

n n
0 0 0 1 1 1

n=2 3 6 9 0 0 1 1 1 n=2

n=1 2 5 8 0 0 0 n=1

n=0 1 4 7 m m 0 0 0 n=0
n = −1 n = −1
m = 0 m = 1m = 2 m=0 m=1 m=2 m=3m=4

The resulatant value y(3, 3) = 6 × 1 + 9 × 1 = 15.

14. To determine the value of y(3, 2) The signal h(3−m, 2−n) is obtained by shifting down the signal
h(3−m, 3−n) along the n-axis by a factor of one. The common values are multiplied and then added
together to get y(3, 2).
 Convolution and Correlation 97

x(m, n) h(3−m, 2−n)

n n

n=2 3 6 9 0 0 1 1 1 n=2
n=1 2 5 8 0 0 1 1 1 n=1
n=0 1 4 7 m m 0 0 0 n=0
n = −1 n = −1
m = 0 m = 1m = 2m = 3 m=0 m=1 m=2 m=3m=4

The value y(3, 2) = 6 × 1 + 9 × 1 + 5 × 1 + 8 × 1 = 28.

15. Finding the value of y(3, 1) The signal h(3−m, 1−n) is obtained by shifting down the signal
h(3−m, 2−n) along the n-axis by a factor of one. The common values are multiplied and then added
together to get y(3, 1).

x (m, n) h(3−m, 1−n)

n n

n=2 3 6 9 0 0 0 n=2

n=1 2 5 8 0 0 1 1 1 n=1

n=0 1 4 7 0 m m 0 1 1 1 n=0
n = −1 n = −1
m = 0 m = 1m = 2 m = 3m = 4 m = 0 m = 1 m = 2 m = 3m = 4

The value of y(3, 1) = 5 × 1 + 8 × 1 + 4 × 1 + 7 × 1 = 24.

16. Finding the value of y(3, 0) The signal h(3 −m, −n) is obtained by shifting down the signal
h(3−m, 1−n) along the n-axis by a factor of one. The common values are multiplied and then added
together to get y(3, 0).
x(m, n) h(3−m, 0−n)
n n

n=2 3 6 9 0 0 0 n=2

n=1 2 5 8 0 0 0 n=1

n=0 1 4 7 0 0 1 1 1 n=0
m m
n = −1 0 0 0 1 1 1 n = −1
m = 0 m = 1m = 2 m = 3m = 4 m = 0 m = 1m = 2 m = 3 m = 4
The value y(3, 0) is given by y(3, 0) = 4 × 1 + 7 × 1 = 11.
17. Finding the value of y(4, 0) The signal h(4−m, −n) is obtained by shifting the signal h(3−m, −n)
along the m-axis towards the right by a factor of one. The common values are multiplied and then added
together to get y(4, 0).
98 Digital Image Processing

x (m, n) h(4−m, −n)

n n

n=2 3 6 9 0 0 0 n=2
n=1 2 5 8 0 0 0 n=1

n=0 1 4 7 0 0 m m 0 0 1 1 1 n=0
n = −1 0 0 0 1 1 1 n = −1
m = 0 m = 1m = 2m = 3 m = 4 m=0 m=1 m=2 m=3 m=4
The resultant value y(4, 0) = 7 × 1 = 7.
18. To determine the value of y(4, 1) The signal h(4−m, 1−n) is obtained by shifting up the signal
h(4−m, −n) along the n-axis by a factor of one. The common values are multiplied and then added
together to get y(4, 1).

x(m, n) h(4−m, 1−n)

n n

n=2 3 6 9 0 0 0 n=2

n=1 2 5 8 0 0 0 0 1 1 1 n=1
n=0 1 4 7 0 0 m m 0 0 1 1 1 n=0
n = −1
m = 0 m = 1m = 2m = 3m = 4 m=0 m=1 m=2 m=3 m=4

The value y(4, 1) = 8 × 1 + 7 × 1= 15.

19. Finding the value of y(4, 2) The signal h(4−m, 2−n) is obtained by shifting up the signal h(4−m, 1−n)
along the n-axis by a factor of one. The common values are multiplied and then added together to
get y(4, 2).

x (m, n) h(4−m, 2−n)

n n

n=2 3 6 9 0 0 0 0 1 1 1 n=2
n=1 2 5 8 0 0 0 0 1 1 1 n=1
n=0 1 4 7 m m 0 0 0 n=0
n = −1
m=0m=1 m=2m=3 m=4 m=0 m=1 m=2 m=3 m=4
The value y(4, 2) = 8 × 1 + 9 × 1 = 17.
20. Finding the value of y(4, 3) The signal h(4−m, 3−n) is obtained by shifting up the signal h(4−m, 2−n)
along the n-axis by a factor of one. The common values are multiplied and then added together to
get y(4, 3).
 Convolution and Correlation 99

x (m, n) h(4−m, 3−n)

n n
0 0 0 1 1 1

n=2 3 6 9 0 0 0 0 1 1 1 n=2

n=1 2 5 8 0 0 0 n=1
n=0 1 4 7 0 0 0 n=0
m m
n = −1
m=0 m=1 m=2 m=3 m=4 m=0 m=1 m=2 m=3 m=4
The value y(4, 3) = 9 × 1 = 9.
The resultant values obtained from steps 1 to 20 are given below:
y(0, 0) = 1 y(0, 1) = 3 y ( 0, 2) = 5 y(0, 3) = 3
y(1, 3) = 9 y(1, 2) = 16 y(1, 1) = 12 y(1, 0) = 5
y( 2, 0) = 12 y( 2, 1) = 27 y( 2, 1) = 33 y( 2, 3) = 18
y(3, 3) = 15 y(3, 2) = 28 y(3, 1) = 24 y(3, 0) = 11
y( 4, 0) = 7 y( 4, 1) = 15 y( 4, 1) = 17 y( 4, 3) = 9
Substituting the above values in the corresponding positions in the given matrix and graphic
form, we can get the resultant values.
n y(m, n)
y(0, 0) y(0, 1) y(0, 2) y(0, 3)
n=3 X X X X X
y(1, 0) y(1, 1) y(1, 2) y(1, 3)
n=2 X X X X X
y(m, n) = y(2, 0) y(2, 1) y(2, 2) y(2, 3)
n=1 X X X X X
y(3, 0) y(3, 1) y(3, 2) y(3, 3)
n=0 X X X X X
m y(4, 0) y(4, 1) y(4, 2) y(4, 3)

m=0 m=1m=2m=3 m=4

The final result in the graphical and matrix forms are given below:

y(m, n)
n

n=3 3 9 18 15 9 1 3 5 3
n=2 5 16 33 28 17 5 12 16 9
n=1 3 12 27 24 15 y(m, n) = 12 27 33 18
n=0 1 5 12 11 7 1 24 28 15
m
m=0 m=1m=2m=3m=4 7 15 17 9

Graphical representation Matrix representation