Hacker News Reader

Comment by planede | Hacker News Reader

Problems with image resizing is a much deeper rabbit hole than this. Some important talking points:

1. The form of interpolation (this article).

2. The colorspace used for doing the arithmetic for interpolation. You most likely want a linear colorspace here.

3. Clipping. Resizing is typically done in two phases, once resizing in x then in y direction, not necessarily in this order. If the kernel used has values outside of the range [0, 1] (like Lanczos) and for intermediate results you only capture the range [0,1], then you might get clipping in the intermediate image, which can cause artifacts.

4. Quantization and dithering.

5. If you have an alpha channel, using pre-multiplied alpha for interpolation arithmetic.

I'm not trying to be exhaustive here. ImageWorsener's page has a nice reading list[1].

[1] https://entropymine.com/imageworsener/

View on HN

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.

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

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.

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.

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.

Yeah I was shocked at how naive this quote is:

>> The definition of scaling function is mathematical and should never be a function of the library being used.

I could just as easily say "hey, why is you NN affected by image artifacts, isn't it supposed to be robust?"

> 3. Clipping. Resizing is typically done in two phases, once resizing in x then in y direction, not necessarily in this order. If the kernel used has values outside of the range [0, 1] (like Lanczos) and for intermediate results you only capture the range [0,1], then you might get clipping in the intermediate image, which can cause artifacts.

Also, gamut clipping and interpolation[0]. That's a real rabbithole.

[0] https://www.cis.rit.edu/people/faculty/montag/PDFs/057.PDF (Downloads a PDF)

Captain D on premulitplication and the alpha channel (with regards to video): https://www.youtube.com/watch?v=XobSAXZaKJ8

Wow, points 2, 3 and 5 wouldn't have occured to me even if I tried. Thanks. I now have a mental note to look stuff up if my resizing ever gives results I'm not happy with. :)

Point 2 is the most important one, and the most egregious error. Even most browsers implement it wrong (at least the last time I checked, I confirmed it again with Edge).

Here is the most popular article about this problem [1].

Warning: once you start noticing incorrect color blending done in sRGB space, then you will see it everywhere.

[1] http://www.ericbrasseur.org/gamma.html

Browsers now 'deliberately' do it wrong, because web developers have come to rely on the fact that a 50/50 blend of #000000 and #FFFFFF is #808080

Linear RGB blending also requires >8 bit per channel for the result to avoid noticeable banding.

It is unquestionably superior though.

I'm a little bit sympathetic for doing it wrong on gradients (having said that SVG spec has an opt-in to do the interpolation in linear colorspace, and browsers don't implement it). But not for images.

Browsers (and other tools) can't even agree on the color space for some images, e.g. "Portable" Network Graphics.

I imagine that beyond just using linearized srgb using perceptually uniform colorspace such as oklab would bring further improvement. Although I suppose the effect might be somewhat subtle in most real-world images.

For downscaling, I doubt that. If you literally squint your eyes or unfocus your eyes, then colors you see will be mixed in a linear colorspace. It makes sense for downscaling to follow that.

Upscaling is much more difficult.

When image generating AIs first appeared, the color space interpolations were terribly wrong. One could see hue rainbows practically anywhere blending occurred.

Another classic: https://www.youtube.com/watch?v=LKnqECcg6Gw

Did the link go down between when you posted this and now? It now lead to http://suspendeddomain.org/index.php?host=www.ericbrasseur.o...

I'd also add speed to that list. Resizing is an expensive operation. Correctness is often traded off for speed. I've written code that deliberately ignored the conversation to a linear color space and back in order to gain speed.

A connected rabbit hole is image decoding of lossy format such as jpeg: from my experience depending on the library used (opencv vs tensorflow vs pillow) you get rgb values that varies between 1-2% of each others with default decoders.

And also (for humans at least) the rabbit hole coming from effectively displaying the resulting image : various forms of subpixel rendering for screens, various forms of printing... which are likely to have a big influence on what is "acceptable quality" or not.

Another thing I had experienced before was a document picture I used after downsizing to mandatory upload size had a character/number randomly changed (6 to b or d). Don't remember which exactly and had to convert the doc to PDF that managed it better.

Wouldn't the clipping be solved by using floating point numbers during the filtering process?

It would. It would also not accumulate quantization errors from an intermediate result. Having said that there are precedents for having the intermediate image pixels in integral values.

Here is imageworsener's article about this[1]

[1] https://entropymine.com/imageworsener/clamp-int/

I love sites like these. Had never heard of Image Worsener before. Thanks!

If you're doing interpolation you probably don't want a linear colourspace. At least not linear in the way that light works. Interpolation minimizes deviations in the colourspace you're in, so you want it to be somewhat perceptual to get it right.

Of course if you're not interpolating but downscaling the image (which isn't really an interpolation, the value at a particular position in the image does not remain the same) then you do want a linear colourspace to avoid brightening / darkening details, but you need a perceptual colourspace to minimize ringing etc. It's an interesting puzzle.

Reply on news.ycombinator.com