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

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

#41

Post by formerly_proven » Wed, Nov 24, 2021, 12:22 PM UTC

pedrocr wrote: post #30

These kinds of formats have been somewhat explored by camera makers for their raw formats. Since the computing resources in the cameras can be quite limited there are a few formats that try to occupy this space of simplicity with still some tricks for compression. Samsung's various SRW encodings remind me most of this: https://github.com/pedrocr/rawloader/blob/a59bb78d156277781a...

Lossy RAW is sometimes even simpler than that. E.g. Nikon's old compression was just remapping values in a log-like fashion, which reduced resolution in the brightest few stops[1] to save a few bits per sample.

[1] Perception is pretty logarithmic as usual, so for a 14-bit readout, half the values represent the brightest stop and a little bit, the other half holds the other 12+ stops.

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

#42

Post by fastball » Wed, Nov 24, 2021, 12:23 PM UTC

orlp wrote: post #15

haxiomic wrote: post #4

This is impressive, I was curious if it was just better on simpler images with many duplicate pixels but it's nice to see it working well with photography too e.g. https://phoboslab.org/files/qoibench/images/wallpaper/EwZDbL... decode ms encode ms decode mpps encode mpps size kb libpng: 148.4 3995.5 55.88 2.08 12223 stbi: 161.0 1858.3 51.50 4.46 19199 qoi: 60.8 95.6 136.49 86.78 12868 I'm interested if there's a stan…

When I download that PNG file it is 10785 KB. If I re-encode it using FLIF 0.4 (to my knowledge still the best off-the-shelf lossless image compression) it is 7368 KB. That's 57% of the size of qoi, quite a lot smaller. You pay for it in encode/decode time though.

Interestingly I actually managed to shave 400kb off of that PNG by just running it through some PNG optimizers. Not great savings but were still some to be had!

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

#43

Post by chrisdew » Wed, Nov 24, 2021, 12:23 PM UTC

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…

The current encoding is complete, so no future extensions are possible.

A fix would be to change:

  110rrrrr ggggbbbb - copy the last pixel and adjust RGB by (r-15, g-7, b-7)

to:

  1100rrrr ggggbbbb - copy the last pixel and adjust RGB by (r-7, g-7, b-7)

This leaves:

  1101???? ...

available for future extensions.

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

#44

Post by KaiserPro » Wed, Nov 24, 2021, 12:25 PM UTC

> The basic ideas for video compression in MPEG are ingenious, even more so for 1993, but the resulting file format is an abomination.

can confirm.

Although the worst part is the documentation is in engineering english, so its quite hard to understand. MPEG2 is actually not as bad as you'd imagine. MPEG4 is.

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

#45

Post by j-pb » Wed, Nov 24, 2021, 12:25 PM UTC

tda wrote: post #28

j-pb wrote: post #6

> To keep things O(n) when encoding, there's only one lookup into this array. The lookup position is determined by a “hash” of the rgba value (really just r^g^b^a). Is a bit imprecise. The algorithm would still be O(n) even with a linear search through the "seen pixel array", as it is bounded by 64 length and therefore a constant factor that gets eaten by the Big-O notation. Because of this hash the algorythm seems t…

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 coordinate is X_1,Y_1,X_2,Y_2...

Which can be achieved with a bunch of bit shifts and masks, (or a bunch of wires if you happen to use it in an FPGA ^^')

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

#46

Post by willvarfar » Wed, Nov 24, 2021, 12:26 PM UTC

Yummy :)

Makes me want to experiment too.

Is there some easy corpus with nice categorization of types (drawing, painting, photo, comic, clip art etc) so we can all easily compare?

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

#47

Post by cyber_kinetist » Wed, Nov 24, 2021, 12:29 PM UTC

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 think the author's intending to use this only as a data packing format (ex. for app/game development) and not a general-purpose exchange format. If all you want to do is pack image/texture data for your game then I totally get why they assume RGBA8 storage and leave out metadata such as color space information.

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

#48

Post by wongarsu » Wed, Nov 24, 2021, 12:31 PM UTC

Is it just me, or is the compression algorithm not really less than the one in PNG? I will grant the author that if you don't need features like support for color spaces, different bit depths or interlacing you can skip the entire container format. But for reference this is the core part of png:

For each scanline write one byte for the chosen filter method, then $width pixels. There are five filter types. In type 0, write the pixels unmodified. In type 1, write the difference to the previous pixel. In type 2, write the difference to the above pixel. In type 3, write the difference to the average of the above and left pixel. In type 4, write the difference to the Paeth predictor (a simple function calculated from the above, left and left above pixel). Then compress everything with deflate.

Obviously by modern standards that isn't performant, not least because deflate sucks by modern standards. But it's simple, can be implemented in a couple lines of C (if you pull in deflate as dependency), and if you don't do exhaustive searches for the best compression it can certainly run in O(n)

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

#49

Post by pedrocr » Wed, Nov 24, 2021, 12:33 PM UTC

formerly_proven wrote: post #41

pedrocr wrote: post #30

These kinds of formats have been somewhat explored by camera makers for their raw formats. Since the computing resources in the cameras can be quite limited there are a few formats that try to occupy this space of simplicity with still some tricks for compression. Samsung's various SRW encodings remind me most of this: https://github.com/pedrocr/rawloader/blob/a59bb78d156277781a...

Lossy RAW is sometimes even simpler than that. E.g. Nikon's old compression was just remapping values in a log-like fashion, which reduced resolution in the brightest few stops[1] to save a few bits per sample. [1] Perception is pretty logarithmic as usual, so for a 14-bit readout, half the values represent the brightest stop and a little bit, the other half holds the other 12+ stops.

The simplest form is just to pack 10 or 12 bit values. There's all kinds of variations of that:

https://github.com/pedrocr/rawloader/blob/a59bb78d156277781a...

There are a few formats that use a curve and less bits. They do become lossy and doing dithering on decompress is useful to avoid banding.

The Nikon one you mention was only used very early and is decoded by decode_8bit_wtable() in that file. It's just looking up the 8 bit value in the table and then adding some randomness to prevent the banding.

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

#50

Post by londons_explore » Wed, Nov 24, 2021, 12:33 PM UTC

This is a great project, but personally I feel that there are lots of uses for uncompressed images (ie. random access, ready to render straight away), and lots of uses for well compressed lossless, but little use for 'slightly compressed' images.

The normal argument for 'slightly compressed' images is that they can be decompressed with very few CPU cycles, but the reality is that with modern platforms lossless image en/decoding is done in hardware and therefore pretty much 'free', as long as you pick lossless h264, lossless webp or lossless hevc. All of those things will also give much smaller file sizes.

In the few places where hardware decode isn't a thing (eg. the memory-constrained 8 bit microcontroller decoding the boot screen for your IoT toaster), there usually isn't a need for losslessness.