Re:Pillow-SIMD – Fast, production-ready image resize for x86
by homm on Thursday July 06, 2017 @05:27PM
(#14714111)
No. As I can see, no one uses FFT for image scaling. I guess because of it much slower.
[ Parent
| on HN ]
Re:Pillow-SIMD – Fast, production-ready image resize for x86
by cyphar on Thursday July 06, 2017 @10:35PM
(#14715599)
It's a bit of a misnomer to talk about a distinction between convolution and FFT. By the convolution theorem, the two are mathematically equivalent. In addition, on paper, FFT-based convolution scales much better than traditional convolution because it reduces the complexity from O(n^2) to O(n log n).
I haven't done the benchmarks for a fully optimised implementation, but comparing naive implementations you can easily tell that FFT-based is much faster (even with all of the tricks that MATLAB does to optimise sparse matrix operations).