Comment by nyanpasu64 | Hacker News Reader

Comment by nyanpasu64 | Hacker News Reader

Parent Full thread

Any convolution kernel is equivalent to a FFT (aside from wrapping effects). The advantage of using a convolution kernel (instead of a hand-painted FFT mask) is that it's purely local and doesn't cause halftone dots in one area of the image to affect the rest, and is faster than a full-image FFT (which is O(N log N) in both the width and height).

A halftone dot whose size/shape changes gradually across the image acts like slow PWM in a pulse wave, changing the relative amplitudes of the harmonics (but not their locations). However, steep discontinuous changes can have nastier effects (which aren't handled well by either a convolution kernel or FFT).

I suspect it's possible to handle edges better than a FFT using a specialized algorithm, but I don't know if it's possible without inordinate runtimes, and if the end result is significantly better than a FFT or not.

(Also, FFTs won't work as well for non-uniform hand-drawn halftones, like the charming https://upload.wikimedia.org/wikipedia/commons/a/ac/Julemoti....)

I think often the FFT is used to actually speed up convolution, it isn't slower than computing convolution of your kernel shifted to every pixel position.

https://en.wikipedia.org/wiki/Convolution#Fast_convolution_a...

> [FFT] isn't slower than computing convolution of your kernel shifted to every pixel position.

For a fixed kernel size and sufficiently large images, full-image FFT is slower than naive convolution because FFT scales by O(n log n) by the image size, while naive convolution only scales by O(n) in terms of the image size. This can be avoided by using blocked FFT instead of full-image FFT:

> If one sequence is much longer than the other, zero-extension of the shorter sequence and fast circular convolution is not the most computationally efficient method available.[13] Instead, decomposing the longer sequence into blocks and convolving each block allows for faster algorithms such as the overlap–save method and overlap–add method.[14] A hybrid convolution method that combines block and FIR algorithms allows for a zero input-output latency that is useful for real-time convolution computations.[15]

I see, I wasn't thinking about kernels much smaller than the image itself. So, if you don't use blocked FFT, it only makes sense to use FFT convolution when your kernel size is > log n?

You may be right, but I think in practice, people use direct convolution for small kernels, and FFT convolution for large kernels (blocked FFT if the signal is substantially longer than the kernel). I didn't look into the math behind this intuition though.

Reply on news.ycombinator.com