There is also blur by fft. This way you get nlogn performance in the number of pixels. All unrelated to sigma and the size of your blur kernel.
Optimizing Gaussian blurs on a mobile GPU
11–20 of 24 posts
Re: Optimizing Gaussian blurs on a mobile GPU
#12The page isn't loading for me but I will chime in with an image smoothing optimization trick I've used. If you don't need an exact Gaussian blur you can approximate it very efficiently using integral images: http://en.wikipedia.org/wiki/Summed_area_table
The more "boxes" you use in your sliding window (analogous to a convolution kernel), the better you can approximate a Gaussian kernel. If you're using a big Gaussian kernel on a big image then integral images can result in a large reduction in the number of operations performed and thus potentially enable a big speed-up.
Re: Optimizing Gaussian blurs on a mobile GPU
#13FFTs where designed for this http://en.m.wikipedia.org/wiki/Convolution_theorem
I'm surprised this isn't even mentioned in the article. I guess there are issues with boundary effects, but those can be overcome in a variety of ways.
Also, if your convolution kernel is short enough, you can beat an FFT. So, in 2D with an NxN image, an FFT filter will have a complexity of about (N^2 + N^2 Log N). If your kernel is KxK, then direct convolution will be (N^2 K^2), so you have to compare Log N with K^2. But keep in mind 1.) these are asymptotic complexities the coefficients matter 2.) K may or may not depend on N 3.) FFTs are may have larger memory requirements, although you may be able to get away with in-place FFTs, and you don't have to explicitly compute the FFT of the gaussian - you can work that out analytically (you should get another gaussian...).
Also, as someone pointed out, the gaussian is separable, so then the complexity of the direct convolution is (K N^2).
Anyway, what are FFT libraries like for iOS? I suppose with Apples policies, you can't compile FFTW for your App?
Re: Optimizing Gaussian blurs on a mobile GPU
#14you can also downscale before blurring and upscale after blur. 4x without much noticeable difference in image quality. This gives a speed boost in two respects - less pixels and a smaller radius
Re: Optimizing Gaussian blurs on a mobile GPU
#15In addition to what was already there, I'd suggest looking at trying to operate on the whole image at a time rather than pixel-by-pixel. To take a simple blur example, a blur that samples the local pixel at 50%, and each of the top, bottom, left, and right by 12.5% is equivalent to drawing the entire image half darkened, then drawing it in each of one pixel to the left, right, up, and down at 12.5% of the original br…
On the contrary. Consider that the memory is the bottleneck when performing the blur. I understand you would create five instances of the images (50%, 12.5% Left, R, Top, B). This would worsen the bottleneck even more.
Additionally, the advantage of computing pixel by pixel is that the shader can operate massively parallel.
Re: Optimizing Gaussian blurs on a mobile GPU
#16you can also downscale before blurring and upscale after blur. 4x without much noticeable difference in image quality. This gives a speed boost in two respects - less pixels and a smaller radius
This is already mentioned in the article.
Re: Optimizing Gaussian blurs on a mobile GPU
#17Are there other blurs that are cheaper than the Gaussian but look good enough to replace it for this sort of purpose?
Re: Optimizing Gaussian blurs on a mobile GPU
#18Are there other blurs that are cheaper than the Gaussian but look good enough to replace it for this sort of purpose?
The article mentions doing multiple passes with a box blur of different sizes. The author didn't see any performance improvement, though.
Re: Optimizing Gaussian blurs on a mobile GPU
#19In addition to what was already there, I'd suggest looking at trying to operate on the whole image at a time rather than pixel-by-pixel. To take a simple blur example, a blur that samples the local pixel at 50%, and each of the top, bottom, left, and right by 12.5% is equivalent to drawing the entire image half darkened, then drawing it in each of one pixel to the left, right, up, and down at 12.5% of the original br…
On the contrary. Consider that the memory is the bottleneck when performing the blur. I understand you would create five instances of the images (50%, 12.5% Left, R, Top, B). This would worsen the bottleneck even more. Additionally, the advantage of computing pixel by pixel is that the shader can operate massively parallel.
I would think it is going to depend on your cache size. Piecewise will be better if the image can't all fit in the cache, but if the image is small enough you can fit everything in the cache.
Or, do you mean that memory is the bottleneck as in, shipping the image to the GPU's memory space?
Re: Optimizing Gaussian blurs on a mobile GPU
#20FFTs where designed for this http://en.m.wikipedia.org/wiki/Convolution_theorem
I'm surprised this isn't even mentioned in the article. I guess there are issues with boundary effects, but those can be overcome in a variety of ways. Also, if your convolution kernel is short enough, you can beat an FFT. So, in 2D with an NxN image, an FFT filter will have a complexity of about (N^2 + N^2 Log N). If your kernel is KxK, then direct convolution will be (N^2 K^2), so you have to compare Log N with K^2…
Last I played with FFT convolution it didn't end up being a win for any sane filter size, even compared to brute-force convolution with arbitrary non-separable kernels. Admittedly I was using off-the-shelf tools in Nuke, but I would imagine both their FFT and Convolve nodes are reasonably optimized.
There's an analysis of the 1D case here with some interesting cautions at the end: http://www.engineeringproductivitytools.com/stuff/T0001/PT15...