How conv2 works?

40 vues (au cours des 30 derniers jours)
Jiayun Liu
Jiayun Liu le 1 Déc 2022
Commenté : Walter Roberson le 1 Déc 2022
I am trying to do filter some images with low pass filters and currently I am using conv2 to convolve a 2D image with a 1D filter function. I am wondering how does matlab perform the convolution? Is it doing 1D convolution to each row of the image and uses a for loop to loop through all the rows? The reason I am asking this is that I am trying to find out if there is a faster way to do the convolution.
  1 commentaire
Bruno Luong
Bruno Luong le 1 Déc 2022
Modifié(e) : Bruno Luong le 1 Déc 2022
There are 2 faminlies of algorithms for convolution
  • straighforward sliding sum of main array x flipped kernel
  • Use DFT/FFT and perform in the convolution in Fourier domain which is multiplication element wise. This methods is very efficient especially when the kernel size is medium or large (> 10 x 10)
Furthermore if the kernel is seperable In 2D (rectangular kernel, isotropic Gaussien), the convolution can be performed as two succesive 1D convolution along column/row or row/column.
It seems MATLAB uses straighforward sliding sum of flipped kernel. I'm not sure if it detects separability and do another branching of successive 1D.
In all branch the algorithm can be easily implemented in multi-threadings, which is the case of MATLAB conv/conv2.

Connectez-vous pour commenter.

Réponses (1)

Walter Roberson
Walter Roberson le 1 Déc 2022
conv2 does conv() and then transposes the result and does a second conv() and then transpose back.
Each conv() step operates over the first dimension.
The internal implementation of conv() is not well documented to the public. However if you happen to look in the right places then there is mention that in some cases, conv() decomposes the kernel into steps that are easier to vectorize and then combines the results.
  5 commentaires
Bruno Luong
Bruno Luong le 1 Déc 2022
Modifié(e) : Bruno Luong le 1 Déc 2022
The code conv2 and convn is no longer mfiles, but builtin. At some point in the pass those code are mfiles.
It sounds like what Walter describes is (2) successive 1D convolutions where there is a loop on working dimensions and for each loop
  • the working dimension is permuted to the first dimension
  • do 1D convolution along the 1st dimension
  • swap back first dimension to the working dimension
This kind of implementation is often use for separable operator, not only for convolution, but also for example for filtering, inear/spline gridded nd interpolation, etc...
But he would eventually explain exactly to you the sentense he wrote.
Walter Roberson
Walter Roberson le 1 Déc 2022
Doing a high performance convolution is more difficult than it seems at first. It is easy to say that in theory it is just a bunch of multiplications and additions, but because of the sliding window, you have to worry about the details of how values are read from memory into the processor. And if you can detect symmetry in the kernel then you can potentially reduce the number of multiplications (which are expensive by comparison)

Connectez-vous pour commenter.

Catégories

En savoir plus sur Statistics and Linear Algebra dans Help Center et File Exchange

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Translated by