As a clarifier, I want to implement cross-correlation, but the machine learning literature keeps referring to it as convolution so I will stick with it.

I am trying to implement image convolution using linear algebra. After looking around on the internet and thinking about it, I could come up with two possible solutions for that.

The first one: Create an appropriate Toeplitz-like matrix out of the kernel as it is described here.

The second one: Instead of the filter, modify the input in a way that it will store the values used by specific kernel operations in column vectors. Then the kernel -layed out in a row vector- should be multiplied by the matrix that holds the modified input like so

enter image description here

My question: Lets assume I have a grayscale image of 960x720 pixels and a kernel of size 3x3.

In the first solution that would create a massive circulant matrix out of the kernel (with a size of 960 * 720 * 958 * 718, in the case of stride=1), with about 10^11 elements.

In the second solution, the modified input would have about 10^6 elements (958 * 718 * kernel-size).

I think it is clear that the second option is so much quicker to compute, am I missing something, did I miss calculate something? The literature keeps referring to Toeplitz matrices when it comes to this problem but I just can not see the second solution to have anything in common with them. Does the matrix in the second one have a specific name?

Is the second one the way to go if I want to implement image convolution? Is there a more efficient solution or a mathematical trick perhaps?

  • 3
    $\begingroup$ Toeplitz matrices are used for mathematical purposes, to study mathematical properties of convolution. It does not mean that using a Toeplitz approach is implementation-efficient $\endgroup$
    – Nikos M.
    Dec 10, 2021 at 19:06


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.