Convolution-algoritms.Filters!
Hi.
There is one problem : I want realise Gauss Blur - filter with Gauss-kernel.
To do this i must calculate univariate covolution (kernel size - 7 points for example, small kernel) and data point(>=1000 pixels). Calculationn takes a lot of time,so i need more fast algorithms for convolution with small(!!!) kernel.
(For example in PhotoShop this colculation quite fast)
Is there any ideas...?
Thanks!
[429 byte] By [
HolyNick] at [2007-11-19 10:49:22]
# 1 Re: Convolution-algoritms.Filters!
Once I created m-file in Matlab for applying convolution filters (for image processing classes at my uni), and after that I wanted to convert it to c++ code. I remember 2 things: I could not find by myself better algorithm than moving mask from pixel to pixel and sumimng up all pixels under the mask one by one. However, I found out that one should avoid nested for loops. I remember that I was copying all values covered by the mask to linear vector, and used sum to get new value of pixel. This gave me ~20% boost. About more optimizations, the only thing which came to my mind was to rewrite parts of code in assembly, what I even started to do, but did not finish.
And one more thing: remember to test timings in 'release mode', because performance is VERY decreased in DEBUG.
Hob
Hobson at 2007-11-10 3:50:33 >
# 2 Re: Convolution-algoritms.Filters!
2 Hobson:
Uhm...i thought about it. Thanks. I read about ' Vinograd' ,( which
are spesially for small kernels) algorithms , but do not understand how to realize it....emm... (and even do not understand sense of his methods.)
# 3 Re: Convolution-algoritms.Filters!
Just found this: http://www.filtermeister.com/tutorials/blur01.html
May be useful
Hob
Hobson at 2007-11-10 3:52:40 >
# 4 Re: Convolution-algoritms.Filters!
2 Hobson: Thanks. But I've alredy done this optimization - make horisontal pass,and then vertical pass.(for Gauss kernel) . Thereare problems with nested loops in my current algorithms. But i think ~20% winnig will not enough.
For example : burring time(in Photoshop)/blurring time(in my algthm) ~ 8 !
Maybe all sense in assembler optimization...
# 5 Re: Convolution-algoritms.Filters!
2 Hobson:
o..there is another feature in this article...
# 6 Re: Convolution-algoritms.Filters!
Yes, there are 3 parts of this tutorial, but links to following parts are rather hardly visible... I should have given you a link right to 3rd part. Hope it helps you
Hob
Hobson at 2007-11-10 3:55:38 >
# 7 Re: Convolution-algoritms.Filters!
2 Hobson: heh...that guy very sly;)) In 3 part il consider kernel with equally
ellements and say that is easy to optimise;)
But kernel always have different values.;)
# 8 Re: Convolution-algoritms.Filters!
(ps: not always but usually)
# 9 Re: Convolution-algoritms.Filters!
I thought that for gaussian blur mask is filled with ones, but maybe thats just some special case, I am not an expert with image processing.
Anyway, did part 3 of this tutorial improve your performance?
Hob
Hobson at 2007-11-10 3:58:40 >
# 10 Re: Convolution-algoritms.Filters!
2 Hobson:
Gauss kernel consist of values of Gauss function ( exp(-x^2/2*sigma^2) . If you want make low freq Gauss filter you do convolution kernel with signal(image pixels). If kernel consist of ones it easy to optimise but this is not suit for my work.
# 11 Re: Convolution-algoritms.Filters!
Is the gaussian blur applied per channel (e.g. one for red, one for G and 1 for B) or does it take a function of the 3?
If it is the first, and you consider a channel of 8 bits max (which is common for jpeg) you can maybe precalculate the 256 values of your gauss function in an array ; then to apply the function to a channel you get the value from a simple call to values[i], 'exp' being expensive...
Just a suggestion as I'm not an expert in this.
regards
# 12 Re: Convolution-algoritms.Filters!
Why don't you try apply the filters in the frequency domain? To do this you have to Fourier transform the image, then multiply the Fourier with the filter frequency function and finally re-tranfsofm the result to have it in the spatial domain. Frequency domain filtering is generally faster than filtering in space (or time for audio signals) domain.
Regards,
Theodore
# 13 Re: Convolution-algoritms.Filters!
To be more accurate:
Convolution in the spatial domain requiers M^2 * N^2 complexity, where N is image size and M is filter size.
Filtering in the spatial domain requiers:
- 2 FFTs (one for image: 2N^2 * logN and one for the filter: 2M^2 * logM).
- one matrix multiplication (element by element): N^2
- 1 IFFT of the result: 2N^2 * lonN.
The fft of the filter has to be resized to NxN, but resizing has no complexity
Thus, the total complexity of frequency domain 2-D filtering is:
4N^2*logN + 2M^2*logM + N^2.
I have made a graph using matlab that shows the complexities for different M and N values. Particullarly, I have chosen N to varay from 10 to 1000 and M to take values 3, 7 and 15.
RED lines represent the complexity of the freq. domain filtering and
BLUE lines represent the complexity of the spatial domain filtering.
As you can probably see, there is only one red line: this is NOT an error, but it implies that freq. domain filtering is not affected by M (not for small changes of M). This is another pro of the freq. domain filtering. Also, it is obvious that freq. domain filtering is slower ONLY in the 1st case (M = 3).
