5
$\begingroup$

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.

The question is: is FFT the fastest way? If now, which is? Consider both GPU and CPU implementations

If it is not: is there algorithm capable of separating a non-separable kernel (in aproximated way, logically)?

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

Improve this question
$\endgroup$
6
  • 1
    $\begingroup$ 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. $\endgroup$
    – Cris Luengo
    Commented Mar 23, 2019 at 22:26
  • $\begingroup$ 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 $\endgroup$
    – Pedro Henrique Monforte
    Commented Mar 23, 2019 at 22:31
  • $\begingroup$ 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. $\endgroup$
    – Cris Luengo
    Commented Mar 23, 2019 at 22:34
  • $\begingroup$ "Convolution with a rectangular filter of uniform weights (non-weighted average filter) can be computed trivially in O(n)" is this using Integral Image? $\endgroup$
    – Pedro Henrique Monforte
    Commented Mar 24, 2019 at 3:59
  • $\begingroup$ 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). $\endgroup$
    – Cris Luengo
    Commented Mar 24, 2019 at 4:15

1 Answer 1

Reset to default
2
$\begingroup$

In your case, since you have multiple images while you have a given set of kernels the DFT based Correlation would be the best fit.

Pay attention that the DFT Based Convolution / Correlation Is Equivalent to Convolution / Correlation with Periodic / Circular Boundary Conditions.
It means that if you need different boundary conditions (Like padding with Nearest Neighbor) then it means you need to pad the image large enough so the cyclic effect won't hurt you.

In that case you might be better doing, given enough memory, what's being don in DNN.
Apply the Correlation / Convolution with Matrix Multiplication.

Matrix Multiplication is so optimized in our days that even if its complexity is higher, in real world it is faster in many cases.
So you build the Convolution Matrix (You can even chain them) and the images matrix and multiply. I can show a MATLAB Example.

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 (No longer maintained), 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.

Good reference - Algorithms for Efficient Computation of Convolution by Karas Pavel and Svoboda David.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ I think Chainer isn't developed anymore. $\endgroup$
    – Eric Johnson
    Commented Apr 17, 2022 at 14:55
  • $\begingroup$ Indeed, it is in maintenance mode. Well, PyTorch is basically the development path of PyTorch. $\endgroup$
    – Royi
    Commented Apr 17, 2022 at 15:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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