Hacker News Reader

Comment by PaulHoule | Hacker News Reader

I've definitely learned a lot about these problems from the viewpoint of art and graphic design. When using Pillow I convert to linear light with high dynamic range and work in that space.

One pet peeve of mine is algorithms for making thumbnails, most of the algorithms from the image processing book don't really apply as they are usually trying to interpolate between points based on a small neighborhood whereas if you are downscaling by a large factor (say 10) the obvious thing to do is sample the pixels in the input image that intersect with the pixel in the output image (100 in that case.)

That box averaging is a pretty expensive convolution so most libraries usually downscale images by powers of 2 and then interpolate from the closest such image which I think is not quite perfect and I think you could do better.

View on HN

If you downscale by a factor of 2 using bandlimited resampling every time, followed by a single final shrink, you'll theoretically get identical results to a single bandlimited shrinking operation. Of course real world image resampling kernels (Lanczos, cubic, magic kernel) are very much truncated compared to the actual sinc kernel (to avoid massive ringing which looks unacceptable in images), so the results won't be mathematically perfect. And linear/area-based resampling is even less mathematically optimal, although they don't cause overshoot.

Isn't this generally addressed by applying a gaussian blur before downsizing? I know this introduces an extra processing step, but I always figured this was necessary.

That's an even more expensive convolution since you're going to average 100 or so points for each of those 100 points!

Practically people think that box averaging is too expensive (pretty much it is like that Gaussian blur but computed on fewer output points.)

Box filtering should be pretty cheap; it is separable, and can be implemented with a moving average. Overall just a handful of operations per pixel.

Gaussian blur can be pretty cheap too using an IIR approximation[1]. It's separable also either way.

[1]: https://www.intel.com/content/dam/develop/external/us/en/doc...

I played a little with FFT Gaussian blur. It uses the frequency domain, and so does not have to average hundreds of points, but rather transforms the image and the blur kernel into the frequency domain. There it performs a pointwise multiplication and transforms the image back. It's way faster than the direct convolution.

Having to process 100 source pixels per destination pixel to shrink 10x seems like an inefficient implementation. If you downsample each dimension individually you only need to process 20 pixels per pixel. This is the same optimization used for Gaussian blur.

> If you downsample each dimension individually you only need to process 20 pixels per pixel.

If you shrink 10x in one direction, then the other, then you first turn 100 pixels into 10, before turning 10 pixels into 1. You actually do more work for a non-smoothed shrink, sampling 110 pixels total.

To benefit from doing the dimensions separately, the width of your sample has to be bigger than the shrink factor. The best case is a blur where you're not shrinking at all, and that's where 20:1 actually happens.

If you sampled 10 pixels wide, then shrunk by a factor of 3, you'd have 100 samples per output if you do both dimensions at the same time, and 40 samples per output if you do one dimension at a time.

Two dimensions at the same time need width^2 samples

Two dimensions, one after the other, need width*(shrink_factor + 1) samples

You're right, I got confused. I was think of Gaussian blur, where the areas to process overlap heavily. Here there's zero overlap.

Reply on news.ycombinator.com