1. Introduction
In this tutorial, we’ll show a matrix approach to do 2D convolution.
2. Convolution
Convolution is fundamental in signal processing, computer vision, and machine learning. It applies a filter or kernel to an input image or signal and extracts relevant features.
Typical implementations use a sliding-window operation where the kernel moves across the input image. For each placement of the kernel on the input image
, we compute the dot product of the kernel and the overlapping image pixels:
However, the kernel approach can be computationally expensive, especially for large images and kernels. An alternative is to compute convolution as matrix multiplication, which can be a more efficient approach.
3. Matrix Construction of a 2D Convolution
Let be a matrix of size
and
a
kernel. For convenience, let
.
To calculate the convolution , we need to calculate the matrix-vector multiplication
where:
-
is a
block matrix we get from the kernel
-
is a row vector with the
elements of
concatenated row by row
-
is a row vector of
elements which can be reshaped into a
matrix by splitting the row vector into
rows of
elements
3.1. How to Compute the Block Matrix?
It’s a three-step process.
First, we define the matrixes, which represent all the horizontal sliding windows for kernel row
:
with a zero row vector of size
and
the
-th element of row
, i.e. the element at row
and column
in matrix
.
stands for an empty vector.
In the second step, we complete horizontal sliding by constructing a matrix
. We define
as the horizontal concatenation of matrix blocks
:
The final step is to represent vertical window sliding. We do that by padding with zero matrices (denoted
):
All that is now left to do is compute , where
is a row-vector form of the input matrix
.
4. Example
Let’s construct the matrix for a
matrix
convolved with a
kernel
:
In this example, we have . First, we build the blocks
and
:
and get after concatenation:
The final step is to pad the matrix with blocks of zeros:
The zeros in the matrix blocks are highlighted in red, and
is exactly of the size
.
Now, let’s rewrite as
:
Finally, we multiply and
:
Since , we obtain the result of the convolution
as a
matrix by simplifying and reshaping
:
4.1. Numeric Example
Let’s say and
are:
The corresponding ,
, and
are as follows:
The result of the convolution is:
We can reshape :
5. Advantages of the Matrix Approach
Matrix multiplication is easier to compute compared to a 2D convolution because it can be efficiently implemented using hardware-accelerated linear algebra libraries, such as BLAS (Basic Linear Algebra Subprograms). These libraries have been optimized for many years to achieve high performance on a variety of hardware platforms.
In addition, the memory access patterns for matrix multiplication are more regular and predictable compared to 2D convolution, which can lead to better cache utilization and fewer memory stalls. This can result in faster execution times and better performance.
6. Conclusion
In this article, we showed how to compute a convolution as a matrix-vector multiplication. The approach can be faster than the usual one with sliding since matrix operations have fast implementations on modern computers.