Effective implementation of fast convolution
This is an effective implementation of 2d convolution using the Fourier transform combined together with over-save and over-add approaches. In general, a standard convolution computed in spatial domain is a time consuming process. Vice versa, the computation in frequency domain is space-intensive. The aim of our implementation is to find a solution that is able to perform the convolution over large data (both signal and kernel) in a reasonably short time while using a limited amount of memory.
The implementation first splits the kernel and signal into the same large rectangular tiles and subsequently performs the convolution in frequency domain over these smaller memory blocks. The splitting process is based on the overlap-add method and overlap-save methods that chop kernel and signal, respectively.
The current implementation works in two dimensions, but the best use of this approach can be expected when handling the large data in three or more dimensions (currently in progress). There is no constrain put on the kernel properties. It works well with separable as well as with non-separable kernels. For large data and non-separable kernels, it performs even better than the standard „conv2“ function. You can try our implementation by running the script „example.m“.
Cite As
Matous Dvorak (2024). Effective implementation of fast convolution (https://www.mathworks.com/matlabcentral/fileexchange/70458-effective-implementation-of-fast-convolution), MATLAB Central File Exchange. Retrieved .
Svoboda D. Efficient Computation of Convolution of Huge Images. In Giuseppe Maino; Gian Luca Foresti. Image Analysis and Processing - ICIAP 2011. LNCS 6978, Part I. Berlin, Heidelberg: Springer-Verlag, 2011. p. 453-462, 10 pp. ISBN 978-3-642-24084-3.
MATLAB Release Compatibility
Platform Compatibility
Windows macOS LinuxCategories
Tags
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!Discover Live Editor
Create scripts with code, output, and formatted text in a single executable document.