Convolutional Neural Networks Conv (CNN): Correlation or Convolution?

The name Convolutional Neural Networks (CNN) suggests that they use the convolution operation, but in the usual way to describe CNN, it is correlation that it’s using. However convolution and correlation can be interchanged through a simple rotation operation. So the name Convolutional Neural Networks is also justified. This post demonstrates these in Python code examples.

import numpy as np
from scipy.ndimage.filters import correlate, convolve

How does correlation work

1d case

First, randomly generate a vector:

a = np.random.randint(5, size=10)
a
array([4, 0, 2, 1, 3, 4, 0, 3, 4, 0])

Pick a kernal and do correlation:

f = [2, 1]
correlate(a, f, mode='constant', cval=0.0)
array([ 4,  8,  2,  5,  5, 10,  8,  3, 10,  8])

This is how it works under the hood:

result = []
for i in range(len(a)-1):
    result.append(a[i]*f[0] + a[i+1]*f[1])
result
[8, 2, 5, 5, 10, 8, 3, 10, 8]

2d case

First, randomly generate an array. We can think of this as a channel of an image.

a = np.random.randint(10, size=36).reshape(6, -1)
a
array([[4, 6, 1, 4, 5, 3],
       [9, 0, 7, 3, 3, 8],
       [2, 6, 9, 3, 2, 0],
       [7, 0, 4, 7, 4, 8],
       [5, 3, 5, 0, 6, 0],
       [9, 1, 0, 2, 4, 2]])

Randomly pick a kernal and do correlation:

f = np.random.randint(3, size=9).reshape(3, -1)
f
array([[2, 2, 1],
       [0, 2, 1],
       [2, 2, 2]])
correlate(a, f, mode='constant', cval=0.0)
array([[32, 45, 26, 39, 41, 28],
       [48, 62, 71, 52, 45, 36],
       [42, 68, 60, 61, 62, 46],
       [40, 55, 64, 66, 38, 32],
       [47, 49, 31, 44, 58, 36],
       [32, 23, 18, 24, 22, 16]])

This is how it works under the hood. We can see this is the usual way CNN is described.

for i in range(1, a.shape[0]-1):
    rslt = []
    for j in range(1, a.shape[1]-1):
        rslt.append((a[i-1:i+2, j-1:j+2] * f).sum())
    print(rslt)
[68, 42, 52, 42]
[58, 78, 48, 60]
[30, 50, 54, 38]
[48, 36, 46, 48]

How does convolution work

1d case

First, randomly generate a vector:

a = np.random.randint(5, size=10)
a
array([2, 1, 3, 3, 1, 3, 2, 3, 4, 1])

Pick a kernal and do convolution:

f = [2, 1]
convolve(a, f, mode='constant', cval=0.0)
array([ 4,  7,  9,  5,  7,  7,  8, 11,  6,  1])

This is how it works under the hood:

rslt = []
for i in range(len(a)-1):
    rslt.append(a[i]*f[1] + a[i+1]*f[0])
print(rslt)
[10, 4, 0, 6, 11, 4, 6, 5, 1]

2d case

First, randomly generate an array. We can think of this as a channel of an image.

a = np.random.randint(10, size=36).reshape(6, -1)
a
array([[1, 9, 7, 8, 8, 2],
       [6, 7, 7, 2, 8, 9],
       [5, 2, 3, 7, 4, 8],
       [1, 4, 3, 8, 5, 5],
       [9, 5, 5, 3, 6, 4],
       [2, 8, 9, 9, 9, 5]])

Randomly pick a kernal and do convolution:

f = np.random.randint(3, size=9).reshape(3, -1)
f
array([[1, 1, 0],
       [2, 1, 2],
       [2, 0, 0]])
convolve(a, f, mode='constant', cval=0.0)
array([[32, 39, 50, 48, 45, 27],
       [45, 52, 51, 59, 46, 33],
       [28, 39, 36, 50, 62, 21],
       [27, 28, 49, 41, 57, 19],
       [37, 56, 55, 53, 44, 21],
       [28, 40, 49, 57, 45, 23]])

This is how it works under the hood:

for i in range(1, a.shape[0]-1):
    rslt = []
    for j in range(1, a.shape[1]-1):
        rslt.append(
            a[i-1, j-1] * f[2, 2] +\
            a[i-1, j] * f[2, 1] + \
            a[i-1, j+1] * f[2, 0] + \
            a[i,j-1] * f[1, 2] +\
            a[i,j] * f[1, 1] +\
            a[i,j+1] * f[1, 0] +\
            a[i+1,j-1] * f[0, 2] +\
            a[i+1,j] * f[0, 1] +\
            a[i+1, j+1] * f[0, 0]
        )
    print(rslt)
[52, 51, 59, 46]
[39, 36, 50, 62]
[28, 49, 41, 57]
[56, 55, 53, 44]

How are correlation and convolution related

In fact the two operations are related through a simple rotation operation of the kernal. This is why CNN can use “Convolution” in its name.

f_rot180 = np.rot90(f, 2)
f_rot180
array([[0, 0, 2],
       [2, 1, 2],
       [0, 1, 1]])

Compare the correlation result with that of the convolution above.

correlate(a, f_rot180, mode='constant', cval=0.0)
array([[32, 39, 50, 48, 45, 27],
       [45, 52, 51, 59, 46, 33],
       [28, 39, 36, 50, 62, 21],
       [27, 28, 49, 41, 57, 19],
       [37, 56, 55, 53, 44, 21],
       [28, 40, 49, 57, 45, 23]])

Equivalently (correlation from scratch):

for i in range(1, a.shape[0]-1):
    rslt = []
    for j in range(1, a.shape[1]-1):
        rslt.append((a[i-1:i+2, j-1:j+2] * f_rot180).sum())
    print(rslt)
[52, 51, 59, 46]
[39, 36, 50, 62]
[28, 49, 41, 57]
[56, 55, 53, 44]

Further reading:

• https://youtu.be/ACU-T9L4_lI?t=1724
• http://setosa.io/ev/image-kernels/
• https://github.com/fastai/courses/blob/master/deeplearning1/nbs/convolution-intro.ipynb
• https://stackoverflow.com/questions/37969197/math-behind-scipy-ndimage-convolve

Code is here: https://github.com/yang-zhang/yang-zhang.github.io/blob/master/ds_math/cnn_correlation_convolution.ipynb