How do convolutions become matrix multiplications?

I know this question may not be very relevant to programming, but if I don't understand the theory behind image processing I'll never be able to implement something in practice.

If I got it right Gaussian filters are convolved with an image for noise reduction since they compute a weighed average of a pixel's neighborhood and they are very useful in edge-detection, since you can apply a blur and derive the image at the same time by simply convolving with the derivative of a Gaussian function.

But can anyone explain me, or give me some references on how are they computed?

E.g. Canny's edge detector talks about a 5x5 Gaussian filter, but how did they get those particular numbers? And how did they go from a continuous convolution to a Matrix multiplication?

migrated from stackoverflow.comMar 16 '13 at 15:17

This question came from our site for professional and enthusiast programmers.

For this operation to work, you need to imagine that your image is reshaped as a vector. Then, this vector is multiplied on its left by the convolution matrix in order to obtain the blurred image. Note that the result is also a vector the same size as the input, i.e., an image of the same size.

Each row of the convolution matrix corresponds to one pixel in the input image. It contains the weight of the contributions of all the other pixels in the image to the blurred counterpart of the considered pixel.

Let's take an example: box blur of size $3 \times 3$ pixels on an image of size $6 \times 6$ pixels. The reshaped image is a column of 36 elects, while the blur matrix has size $36 \times 36$.

• Let's init this matrix to 0 everywhere.
• Now, consider the pixel of coordinates $(i,j)$ in the input image (not on its border for simplicity). Its blurred counterpart is obtained by applying a weight of $1/9$ to itself and each of its neighbours at the positions $(i-1,j-1); (i-1,j), (i-1,j+1),\ldots,(i+1,j+1)$.
• In the column vector, the pixel $(i,j)$ has the position $6*i + j$ (assuming lexicographic ordering). we report the weight $1/9$ in the $(6i+j)$-th line of the blur matrix.
• Do the same with all other pixels.

A visual illustration of a closely related process (convolution + subtraction) can be found on this blog post (from my personal blog).

• a link is dead. – gauteh Sep 4 '15 at 11:31
• Hi, could you update the link? – Royi Aug 21 '18 at 7:28

For applications to images or convolution networks, to more efficiently use the matrix multipliers in modern GPUs, the inputs are typically reshaped into columns of an activation matrix that can then be multiplied with multiple filters/kernels at once.

Check out this link from Stanford's CS231n, and scroll down to the section on "Implementation as Matrix Multiplication" for details.

The process works by taking all the local patches on an input image or activation map, the ones that would be multiplied with the kernel, and stretching them into a column of a new matrix X through an operation commonly called im2col. The kernels are also stretched to populate the rows of a weight matrix W so that when performing the matrix operation W*X, the resulting matrix Y has all the results of the convolution. Finally, the Y matrix must be reshaped again by converting the columns back into images by an operation typically called cal2im.

• This is a very good link, thanks! However it is good practice to add the important extracts from the link into the answer, this way the answer is valid even if the link breaks. Please consider editing your answer to get it accepted! – Matteo Feb 23 '17 at 18:27

Convolution in Time domain equals matrix multiplication in the frequency domain and vice versa.

Filtering is equivalent to convolution in the time domain and hence matrix multiplication in the frequency domain.

As for the 5x5 maps or masks, they come from discretizing the canny/sobel operators.

• I don't agree with the fact that filtering is a convolution in the frequency domain. The kind of filters we are talking about here are convolutions in the spatial domain (that is to say, element-wise multiplication by the filter response in the frequency domain). – pichenettes Mar 16 '13 at 16:51
• Thanks for correcting what I wrote. I made a subsequent edit. I guess I should double-check my answers before posting. However, the majority of my answer still stands. – Naresh Mar 17 '13 at 4:15
• The Fourier transform does indeed turn convolutions into multiplications (and vice versa). However, they are pint wise multiplications, while the question is about matrix-vector multiplications that are obtained by reshaping the images. – sansuiso Mar 17 '13 at 16:34
• I did mention how discretizing the operators is the reason for the 5x5 matrices obtained for the canny/sobel operators. – Naresh Mar 17 '13 at 17:49