# What is the Fastest Way Ever to Do 2D Correlation?

## Here is what i gathered so far:

• Any sliding window classification, image filtering or similar can be fastly done by a FFT (flip the signal and do convolution).

• Also, if the template/filter kernel is separable it is possible to do fast correlation by simply separating into multiple kernels and applying then sequentialy.

• I think it is possible to do fast correlation by using integral images, but I am not sure how.

## Context:

My filter is an Inner Product Detector, which is found by

$$h = R^{-1}\mu_1$$ where $$R^{-1}$$ is the autocorrelation matrix and $$\mu_1$$ is the mean of a given class.

The matrix $$R$$ is hermitian. And can be calculated by

$$\sum x^Tx$$

where $$x$$ are d-dimensional vectors and $$[.]^T$$ denotes the transpose.

Also: kernels are squares of size 21,23,25,27 or 35 Images are 128x128

• FFT is fastest iff the kernel is large enough. For small kernels a direct approach is faster. Finding a separable approximation to a non-separable kernel is quite easy with SVD, or as an optimization problem. – Cris Luengo Mar 23 '19 at 22:26
• The Kernel is about 27x27 and images are 128x128. I will perform multiple correlations with multiple kernels and I can store their fft. Also I need to convolve the square image (pixel wise) to a averaging kernel 27x27 to get the norm of the samples – Pedro Henrique Monforte Mar 23 '19 at 22:31
• Convolution with a rectangular filter of uniform weights (non-weighted average filter) can be computed trivially in O(n), for n pixels, independent of kernel size. Otherwise, if you have a specific case like it seems you do, and want to know what is fastest, run the various options and time them. Timings will differ from one system to the next. – Cris Luengo Mar 23 '19 at 22:34
• "Convolution with a rectangular filter of uniform weights (non-weighted average filter) can be computed trivially in O(n)" is this using Integral Image? – Pedro Henrique Monforte Mar 24 '19 at 3:59
• That is using the integral image but computed on the fly. Storing the integral image is only useful if you need to compute multiple convolutions for the same image, with kernels of different sizes. The uniform rectangular filter is separable, so you can compute the convolution along image rows, then columns. And such a 1D convolution can be computed as follows: given the result at point n, the result at n + 1 is computed by subtracting one input value (the one that "falls off" on the left) and adding one (the one that enters the kernel on the right). – Cris Luengo Mar 24 '19 at 4:15

By the way, even if you do it with DFT in the GPU, I suggest you do it with a DNN library (Something which utilize CUDNN, ROCm - Chainer, PyTorch, TensorFlow, MATLAB Neural Network Toolbox, Knet, etc...) since this case of multiple images (Batch) with given kernel is the case optimized in those libraries with automatic mechanism to chose between DFT based or Matrix based implementation.