OpenCV: computational efficiency of filter2D function
If I want to perform kernel image convolution in OpenCV I can use the function filter2D
. Another option is to create my own filter using for loops like in this post .
Will filter2D be faster than the code provided in the post? If so, what makes it faster?
I tried looking at the code for filter2d but couldn't figure it out. I am new to openCV and any help in this regard is appreciated.
source to share
Most of OpenCV is actually much faster than the naive approach! For convolutions, they often use one of these two fundamental optimizations:
-
Divisible convolution. Uses the "associative convolution property" for certain types of kernels. For the kernel
M-by-N
andP-by-Q
naive approachM*N*P*Q
. If the kernel is separable, you can do it inM*N(P+Q)
. It's huge! You will notice that the OpenCV filter2d source uses this whenever possible. More on this. -
Convolution theorem ... This optimization is even better, but it's a little more complicated. Basically: convolution in the spatial domain is equivalent to point multiplication in the frequency domain. This means that if you put your image and kernel through an FFT, your convolution can go from quadratic (naive) time complexity to O (n log n)! Check out the convolution theorem on Wikipedia
source to share
Filter2d is effective when your filter size is small and faster than the message you provided. However, as the kernel grows, the execution time increases dramatically.
In fact, there are many implementations that are much faster than OpenCV, including recursion and integral image based implementations.
The basic idea of a recursive implementation is that a 2D convolution can be split into multiple 1D convolutions, and a 1D convolution can be written as recursion. just google about recursive guassian filter or recursive convolution.
Alternatively, you can decompose the kernel and implement convolution using multiple integral images. just google about kernel integral image or cosine integral image.
In any case, the execution time will not increase with the kernel size. Thus, these implementations are much more efficient than OpenCV filter2d when your kernel is large.
Understanding a recursive or integral image implementation requires some mathematical background for signal processing.
If implementation efficiency is your first concern, you better study them and write filter2d yourself. If not, just use opencv filter2d, remembering to avoid the big kernel.
source to share