Convolutions are essential components of many algorithms in neural networks, image processing, computer vision ... but these are also a bottleneck in terms of computations... In the python ecosystem, there are different existing solutions using numpy, scipy or tensorflow, but which is the fastest?

Just to set the problem, the convolution should operate on two 2-D matrices. We will here always consider the case which is most typical in computer vision:

  • a first matrix $A$ is the input and is typically large ($N \times N$ where $N$ is typically larger than $2^{10}=1024$),
  • a second matrix $B$ is the template and is typically smaller (say $M=128$),
  • the result of the convolution $C = A \ast B$ is padded such that it is of the same size as $A$.

    Often, you need to do that with many images on many kernels, so a method that does it on many has a bonus point.

Thanks for any hint!

PS: the goal is at some point to sum up these results in this blog post which already contains some examples...

  • Do the same. Instead of Multiplication in Frequency do Division. – Royi Sep 26 '17 at 16:19
  • 1. Test with timeit. 2. scipy's should be faster than numpy, we spent a lot of time optimizing it (real FFT method, padding to 5-smooth lengths, using direct convolution when one input is much smaller, etc.) Don't know how it compares to tensorflow. – endolith Sep 26 '17 at 21:52
  • You could also try OpenCV, which has inbuilt algorithms for that (and they are usually quite fast) docs.opencv.org/3.1.0/d4/d13/tutorial_py_filtering.html – Julian S. Sep 27 '17 at 2:09

To provide a more quantitative approach, I have made a jupyter notebook (which can be seen as a web page here.

The results can be summarized in the following plot: results for increasing sizes

In practice, I have found that scipy was always faster by a significant amount. However, it seems new alternatives are emerging and I have to include (not exhaustive): architecture specific optimizations (IPP), simplified graphs in deep-learning algorithms (such as keras or eager execution in tensorflow), and so on. Comments welcome!

  • As I said before, scipy has several optimization paths to choose the fastest method based on the input sizes and types, so it should be pretty good. (I also had some shortcuts for very small N which didn't make it into the finished PR, which I meant to re-submit later but haven't gotten around to it.) If you're doing lots of convolutions of the same size, you can use scipy.signal.choose_conv_method(in1, in2, mode='full', measure=True) to find the best method empirically. – endolith Nov 21 '17 at 16:12
  • Thanks ! This looks to be a good method to benchmark a cnovolution code beforehand. – meduz Nov 26 '17 at 15:21

It depends on the sizes of the images and the filters.
Sometimes it also depends on the filters themselves and the quality required.

Assuming all arbitrary (Namely the filters have no special property but their size, some of them are HPF, some LPF, some neither, they are not separable, no approximation is allowed, etc...) one could follow this:

  • If the filters are small in comparison to the image, usually direct computation is the way to go if the filter is used once.
  • If the filter is long or used many times for many images it is better to do it in Frequency Domain. Pay attention you need padding in order to apply linear Convolution using Frequency Domain Multiplication (Cyclic Convolution). Also try to take advantage of all data being real (The Symmetry in Frequency Domain).
  • If approximation is allowed a separable approximation of the filter may produce great speed up's.
  • If you use direct convolution utilizing Intel IPP will yield the fastest results.
  • If you use Frequency Domain then wither IPP or FFTW will yield the fastest results (In the case of FFTW you still need to do the frequency domain multiplication efficiently using IPP or hand coded code).

Those guidelines will easily get you close to your system edge regarding performance.
Usually with small kernels convolution is memory bounded operation.

Your Answer

 
discard

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.