News for hackers. Stuff that matters.
Re:Pillow-SIMD – Fast, production-ready image resize for x86 by vadiml on Thursday July 06, 2017 @05:02PM (#14713932)
Great work and great article. One question though: Did you consider to replace convolution based filters by FFT based ones ?
Re:Pillow-SIMD – Fast, production-ready image resize for x86 by liuliu on Thursday July 06, 2017 @08:49PM (#14715175)
Lanczos or Gaussian are separable filters. That reduces computation considerably.
Re:Pillow-SIMD – Fast, production-ready image resize for x86 by stagger87 on Thursday July 06, 2017 @05:28PM (#14714117)
For small filter sizes, convolution is going to be faster than an FFT approach. Plus, correct me if I'm wrong, but you need to perform a convolution for every output pixel where the filter kernel is different for each convolution (Sampling the lanczos filter at different points depending on the resample ratio), which would really slow down an FFT approach.
Re:Pillow-SIMD – Fast, production-ready image resize for x86 by pishpash on Thursday July 06, 2017 @05:37PM (#14714168)
Beyond the mismatched signal size, the FFT approach creates circular convolutions, which is not what you want in images. You'd need windowing or a larger effective signal size, and pay the cost of conversions back and forth.
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.
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).