QOI: Lossless Image Compression in O(n) Time • Hacker News Board

Re: QOI: Lossless Image Compression in O(n) Time

#121

Post by kaetemi » Wed, Nov 24, 2021, 3:13 PM UTC

sam0x17 wrote: post #115

jiggawatts wrote: post #23

I know you don't like "design by committee" and overly complex formats. Also, the compression algorithm itself is somewhat independent of the "container format" that it's used with. However, if I may make a suggestion: If you do end up rolling your own container format for any reason, always include a way to store the colour space of the image! Treating RGB images as arrays of bytes without further tags is like treat…

I've never understood the need for color profiles on images themselves. On monitors and displays, sure, those vary, but why allow people to specify a color profile on an image, thus making images no longer a ground truth for pixel value? It seems like the main use case is dealing with images that already have color profiles. What is the point?

Because your pixels need to transform from the image color profile to the display color profile.

By default this all falls back to sRGB, which is not the "ground truth pixel value" you may be assuming it is.

Re: QOI: Lossless Image Compression in O(n) Time

#122

Post by kortex » Wed, Nov 24, 2021, 3:20 PM UTC

sam0x17 wrote: post #115

jiggawatts wrote: post #23

I know you don't like "design by committee" and overly complex formats. Also, the compression algorithm itself is somewhat independent of the "container format" that it's used with. However, if I may make a suggestion: If you do end up rolling your own container format for any reason, always include a way to store the colour space of the image! Treating RGB images as arrays of bytes without further tags is like treat…

I've never understood the need for color profiles on images themselves. On monitors and displays, sure, those vary, but why allow people to specify a color profile on an image, thus making images no longer a ground truth for pixel value? It seems like the main use case is dealing with images that already have color profiles. What is the point?

No single color space is complete. Each has trade-offs. I would actually say that color profiles help get closer to ground truth, that is, rendering intent.

Re: QOI: Lossless Image Compression in O(n) Time

#123

Post by mzs » Wed, Nov 24, 2021, 3:21 PM UTC

j-pb wrote: post #45

tda wrote: post #28

Earlier quoted context omitted.

I was about to post the same idea about a locality preserving pixel order. I was thinking about hilbert curves, never heard of z-curves. Would be nice to see if/how that affects the compression ratios. How surprising that a few simple principles can give quite a good image format

After making the edit, I saw that someone made the same suggestion on twitter! Hilbert curves have slightly better locality than Z-curves, but Z-Curves are trivial to produce. If you have a N dimensional space over unsigned integers, then you can place each point on a one dimensional Z-Curve by interleaving their bits into a new integer. So for any point (X, Y) in the X-Y coordinates of an image the Z-Curve coordinat…

Do you have a link to discussions about QOI on twitter?

Re: QOI: Lossless Image Compression in O(n) Time

#124

Post by lifthrasiir » Wed, Nov 24, 2021, 3:22 PM UTC

bonzini wrote: post #58

lifthrasiir wrote: post #8

tl;dr: 00xxxxxx - copy (x+1)-th last EXPLICITLY ENCODED pixel (i.e. ignoring repeats) 010xxxxx - repeat the last pixel x+1 times 011xxxxx xxxxxxxx - repeat the last pixel x+33 times 10rrggbb - copy the last pixel and adjust RGB by (r-1, g-1, b-1) 110rrrrr ggggbbbb - copy the last pixel and adjust RGB by (r-15, g-7, b-7) 1110rrrr rgggggbb bbbaaaaa - copy the last pixel and adjust RGBA by (r-15, g-15, b-15, a-15) 1111R…

> 00xxxxxx - copy (x+1)-th last EXPLICITLY ENCODED pixel (i.e. ignoring repeats)- Not exactly. It's "copy the last pixel color for which (r^g^b^a)&63 == x".

Oh you are right, I only took a cursory look at the header file and thought the hashing is only used to speed up the lookup.

Re: QOI: Lossless Image Compression in O(n) Time

#125

Post by kortex » Wed, Nov 24, 2021, 3:29 PM UTC

WaitWaitWha wrote: post #102

I am going to be the fly in this ointment. I appreciate the premise to develop this, and the science that comes with it. I cannot tell if the author is writing in jest or serious when he is rude to the historical work that was done before him, yet relies on. It comes across as hubris with no floor to hold him up. Today's genius is often questioned and found to be a fool of tomorrow, and a bit of grace goes a long way…

Have you seen codecs? I've recently been exploring this space and there is not one corner of this universe that isn't a lurking Lovecraftian horror.

Un-compressed formats like BMP are sane I guess but most of those are wrapped in crufty, sparsely documented container formats. Ogg is decent but even it takes quite the deep dive to even begin wrangling it.

Re: QOI: Lossless Image Compression in O(n) Time

#126

Post by amelius » Wed, Nov 24, 2021, 3:29 PM UTC

mkl wrote: post #107

amelius wrote: post #73

Earlier quoted context omitted.

Yes, also store the DPI. In general, allow arbitrary key-value pairs to be stored.

> Yes, also store the DPI. I don't think that's a good idea. Most images, like photos and screenshots, don't have physical dimensions. Some image tools like to put in bogus default DPI values that are guaranteed to be wrong, and it can be a bit of pain.

How else would you reproduce images at exactly the right size? Without DPI, the format would be useless for many scientific purposes.

But I get your worries. As a compromise, DPI could be optional.

Re: QOI: Lossless Image Compression in O(n) Time

#127

Post by w-m » Wed, Nov 24, 2021, 3:30 PM UTC

rocqua wrote: post #114

I immediately thought of a use-case for (a modified version of) this: raw compression in cameras. Currently Sony has two options. Uncompressed raw that is huge, or lossy compressed raw that is half the size. They probably chose those options because throughput when shooting quickly matters a lot, so something like PNG would slow down shooting too much. I imagine a blazingly fast halfway decent compression algorithm w…

I don't think this method fits camera raws particularly well. The real world is noisy, so it becomes very unlikely that you would ever hit the two most compressible methods of QOI, (1) pixel value repeat or (2) index into one of the previous 64 pixels. QOI works really well for 8-bit screenshots, with lots of pixel-values repetitions. No such luck in noisy 14-bit real-world images.

Also, this format was designed to be as simple as possible, and is byte-aligned, only handles 8-bit RGBA. You would need a different design for 12/14-bit RGB or RGBG (Bayer).

Re: QOI: Lossless Image Compression in O(n) Time

#128

Post by vintermann » Wed, Nov 24, 2021, 3:39 PM UTC

janandonly wrote: post #7

Waawh, one would think (certainly, I personally thought) that all the _simple_ compression algorithms would have been discovered and build by now...

Well, this is a combination of simple approaches which have all been used before, though put together in a nice way. And it's not benchmarked against modern formats like lossless webp or jpeg-xl.

Re: QOI: Lossless Image Compression in O(n) Time

#129

Post by jiri » Wed, Nov 24, 2021, 3:42 PM UTC

This code is nice for RGB, but what about YUV420 format? There should be even more efficient way to store image in YUV420 (takes half bytes than RGB 888), and most images (JPEGs, direct cameras output in Android etc) are already in YUV420. I wonder if auther has tried YUV420 already and failed for any reason ...

Re: QOI: Lossless Image Compression in O(n) Time

#130

Post by kortex » Wed, Nov 24, 2021, 3:43 PM UTC

Super cool work! I was also mucking around with codecs last week. I got some surprisingly good results from delta encoding each channel separately and then zstandard compression. Dirt simple, crazy fast.

One trap to be aware of when profiling image codecs is not knowing the provenance of the test images. Many images will have gone through one or more quantization steps. This can lead to impressive compression ratios, but if you compare with the results on raw, unquantized imagery, it's less of a slam dunk.

That said, PNG is a really low bar to clear, both in terms of speed and compression ratio. Even really image-naive compression algorithms tend to be within a factor of 2 in resulting compressed size. You tend to get diminishing returns. 10% vs 20% is twice as efficient, but starting with a 10MB file, 1 vs 2 MB file sizes isn't a huge delta. (yes I know there are domains where this matters, don't @ me).