Kernel Convolutions
The foundation concept for processing, manipulating, and transforming images is Kernels and convolution process. Almost all techniques such as feature extraction and filters depend on performing one or more kernel convolutions on an image. Knowledge of the kernels and convolution techniques can help you to understand, and implement pre-processing techniques that improve operations such as edge detection, sharpening and blurring images, and image filters more broadly.
This note covers the foundations of kernel and the convolution process and demonstrates some examples of the results of performing convolutions.
What is a Kernel
A kernel is a square matrix of weights, often much smaller than the image it is applied to, that is used to perform a convolution. An example of a kernel can be:
Identity Kernel: $\begin{pmatrix} 0 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 0 \end{pmatrix} $
Edge Detection Kernek: $\begin{pmatrix} -1 & -1 & -1 \\ -1 & 8 & -1 \\ -1 & -1 & -1 \end{pmatrix} $
What is a Convolution?
A convolution is the weighted sum of the product of an image to a convolution kernel.
Suppose we have a 2D Matrix and a kernel below and we are trying to convolve the 2D matrix
$$ A = \begin{pmatrix} 1 & 1 & 3 & 5 & 1 \\ 3 & 2 & 5 & 2 & 3 \\ 2 & 7 & 6 & 1 & 4 \\ 1 & 1 & 7 & 2 & 3 \\ 4 & 2 & 5 & 3 & 6 \end{pmatrix}, k_{3x3} = \begin{pmatrix} 1 & 1 & 1 \\ 1 & 1 & 1 \\ 1 & 1 & 1 \end{pmatrix} $$
To perform a convolution, the kernel slides against the image and compute the weighted sum and replace the center element/pixel with the weighted sum. More practically, to compute convolution for coordinate $(2, 2)$, we execute the following operation:
$$ \begin{pmatrix} 1 & 1 & 3 & 5 & 1 \\ 3 & \textbf{2} & 5 & 2 & 3 \\ 2 & 7 & 6 & 1 & 4 \\ 1 & 1 & 7 & 2 & 3 \\ 4 & 2 & 5 & 3 & 6 \end{pmatrix} * \begin{pmatrix} 1 & 1 & 1 \\ 1 & 1 & 1 \\ 1 & 1 & 1 \end{pmatrix} $$
$$ \begin{pmatrix} \textbf{(1)1} & \textbf{(1)1} & \textbf{(1)3} & 5 & 1 \\ \textbf{(1)3} & \textbf{(1)2} & \textbf{(1)5} & 2 & 3 \\ \textbf{(1)2} & \textbf{(1)7} & \textbf{(1)6} & 1 & 4 \\ 1 & 1 & 7 & 2 & 3 \\ 4 & 2 & 5 & 3 & 6 \end{pmatrix} = \begin{pmatrix} 1 & 1 & 3 & 5 & 1 \\ 3 & \textbf{30} & 5 & 2 & 3 \\ 2 & 7 & 6 & 1 & 4 \\ 1 & 1 & 7 & 2 & 3 \\ 4 & 2 & 5 & 3 & 6 \end{pmatrix} $$
Notice that the new value for coordinate $(2,2)$ is now $3$ which is the weighted sum of the image and kernel matrix about point $(2, 2)$ More specifically:
$$ A_{(2,2)} = [(1)1 + 1(1) + 1(3) + 1(3) + 1(2) + 1(5) + 1(2) + 1(7) + 1(6)] = 30 $$.
A full convolution runs across all points of the matrix and performs this calculation. For points on the edge like $(1,1), (1,2)$, we can often ignore missing neighbors, or in some operations, we can create padding and set the values weights equal to zero. Applying a convolution of the full image, the resulting image is therefore:
$$ \begin{pmatrix} 1 & 1 & 3 & 5 & 1 \\ 3 & 2 & 5 & 2 & 3 \\ 2 & 7 & 6 & 1 & 4 \\ 1 & 1 & 7 & 2 & 3 \\ 4 & 2 & 5 & 3 & 6 \end{pmatrix} * \begin{pmatrix} 1 & 1 & 1 \\ 1 & 1 & 1 \\ 1 & 1 & 1 \end{pmatrix} = \begin{pmatrix} 7 & 15 & 18 & 19 & 11 \\ 16 & 30 & 32 & 30 & 16 \\ 16 & 34 & 33 & 33 & 15 \\ 17 & 35 & 34 & 37 & 19 \\ 8 & 20 & 20 & 26 & 14 \end{pmatrix} $$
Edge Points
A question we may have at this point is how do we convolve the image on edge coordinates, i.e. coordinates that don't have full neighbors in a $3x3$ matrix. For example, coordinate $(1,1)$ only has 3 neighbors. There are many approaches to solving this. Most common is to ignore non-existent neighbors which is the approach we have taken above. However, other approaches such as using constants and padding can be used depending on the desired outcome of the convolution.
Convolution in Python
We can implement a convolution easily in Python using the scipy.ndimage class. Let's demonstrate the above operation in Python
import numpy as np
from scipy import ndimageA = np.array([ [1, 1, 3, 5, 1],
[3, 2, 5, 2, 3],
[2, 7, 6, 1, 4],
[1, 1, 7, 2, 3],
[4, 2, 5, 3, 6]])
kernel = np.ones(shape=(3,3))ndimage.convolve(A, kernel, mode='constant')array([[ 7, 15, 18, 19, 11],
[16, 30, 32, 30, 16],
[16, 34, 33, 33, 15],
[17, 35, 34, 37, 19],
[ 8, 20, 20, 26, 14]])