[backprojection]

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?

[lcrs]

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...

[tlarkworthy]

Yeah I imagine an fft solution is not the best due to non-mathmatical reasons. Kinda annoying as it was all worked out decades ago