A Computational Introduction to Digital Image Processing, 2nd Edition

The Fourier Transform 159

MATLAB/Octave

>> N = length(a);

>> C = conv(a,[b,b])

>> C(N:2

*

N-1)

ans =

60 66 68 66

which is exactly what we obtained above. Python works very similarly, using the command

convolve

:

Python

In: a = [1,2,3,4]

In: b = [5,6,7,8]

In: convolve(a,b)

Out: array([ 5, 16, 34, 60, 61, 52, 32])

In: convolve(a,b+b,’valid’)[:-1]

Out: array([60, 66, 68, 66])

The importance of convolution is the convolution theorem, which states:

Suppose x and y are vectors of equal length. Then the DFT of their circular convolu tion

x ∗y is equal to the element-by-element product of the DFTs of

x

and

y

.

So if Z, X, Y are the DFTs of z = x ∗ y, x and y, respectively,