System and methods for fast and scalable 2D convolutions and cross-correlations for processing image databases and videos on CPUs

1. A maximum throughput method for computing 2D convolutions, comprising the steps of finding the optimal value for N that maximizes throughput:

receiving an image of arbitrarily large size, and a convolution kernel of size Q×Q;

decomposing the image into block sizes P×P;

computing fast convolutions of each image block with the convolution kernel;

storing an output in N×N blocks wherein N≥P+Q−1;

calculating the throughput as a function of a number of output pixels N×N over the execution time of each block to obtain a result;

combining results using an overlap-and-add method to compute a final output image; and

determining an optimal size N that provides the maximum throughput among all considered block sizes.

2. The method according to claim 1 , wherein the step of computing fast convolutions of each image block further comprises the steps of:

receiving an image block of size P×P and the convolution kernel of size Q×Q;

pre-allocating memory N×N;

using vector operations to zero-pad and copy the image block, the convolution kernel, and the output, wherein N≥P+Q−1;

computing a 2D FFT of the zero-padded kernel only once and storing the result for all subsequent image blocks;

computing a 2D FFT of the zero-padded image block;

computing a product of the 2D FFTs using vector multiplication operations;

computing an inverse 2D FFT of the product; and

cropping an output image block to N×N using vector operations.

3. The method according to claim 2 , wherein the pre-allocated memory is larger than a minimum required for computing linear convolutions.

4. The method according to claim 1 , wherein the image is from a large image database or a database including videos of large image sizes.