Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

QOI: Lossless Image Compression in O(n) Time

phoboslab.org

Post reply on HN
Print view View original

71–80 of 303 posts

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

#71

Post by IshKebab »

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

Yeah I don't think there are any new ideas here. RLE, differential encoding and dictionary encoding have all existed for decades.

The interesting thing is that it comes close to PNG.

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

#73

Post by amelius »

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…

Yes, also store the DPI.

In general, allow arbitrary key-value pairs to be stored.

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

#74

Post by h4kor »

ur-whale wrote: post #38
giorgioz wrote: post #24

>I can almost picture the meeting of the Moving Picture Experts Group where some random suit demanded there to be a way to indicate a video stream is copyrighted. And thus, the copyright bit flag made its way into the standard and successfully STOPPED MOVIE PIRACY BEFORE IT EVEN BEGAN. This bit made me laugh out loud :D

> This bit made me laugh out loud :D Yeah, it's funny, until you actually go read the MPEG spec. documentation. Then any and all inklings of laughter will very quickly evaporate.

What does it say about these bits?

I'm currently tinkering around with mp3s and wondered how many "useless" bits are in each frame.

I wonder if they are ever used to trace distributors of pirated music, similar to yellow dots in printers.

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

#75

Post by sbrki »

Very nice.

Regarding the comments about complexity of existing formats - I agree, with the exception of PNG. In terms of complexity, QOI is very similar to PNG filtering phases, i.e. when you strip primary compression phase (Huffman coding) from PNG.

Also, I admire how the author combined a lot of common and cool tricks into QOI:

- Block tags form a sort of a prefix code, making it easy to differentiate block types with differing sizes

- Look-back array is used (common trick from LZW family)

- Delta-coding is used when storing pixel diffs

- In the end, if nothing else works, full pixel value is written

Also, the fact that everything is byte aligned is very appreciated.

This is a breath of fresh air and really impressive how good performance (both processing and size reduction) this gets with so little (very readable!) C.

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

#76

Post by minus7 »

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.

FLIF has been superseded[1] by JPEG XL, which, in my very limited testing, performed better (speed and compression-wise; libjxl) than FLIF.

Interesting though that FLIF 0.4 was released 3 days ago. I haven't checked out that new release (and won't), but the previous one wasn't great code and was a pain to use (ended up using its CLI instead of the lib). We ended up going back to PNG because of interoperability and speed. I haven't looked at libjxl's API yet.

Edit: 8605KB in 11.5s with libjxl, so it's not actually better than FLIF 0.4 (7368KB in 23.9s)

[1]: https://flif.info/#update

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

#77

Post by pornel »

cyber_kinetist wrote: post #47
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.

I know games tend to assume color spaces from context, and do other hacky things like reusing alpha for height maps or RGB for vector coordinates.

But this approach is a source of endless conflict with image processing tooling, because nobody except the game author knows what the channels mean. Game developers keep complaining about image processing tools doing anything other than bytes-in-bytes-out on that data (e.g. clearing "unused" alpha or treating RGB as human-perceptible colors), because it breaks the unstated assumptions.

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

#78

Post by tda »

SkeuomorphicBee wrote: post #63

Really cool encoding, it is a bit incredible that such simple rules can archive such good results. It is so interesting that if the image have few colors, method #2 alone (An index into a previously seen pixel) encodes the whole image into an indexed colour space (with the hash table becoming the pallet). Ive seen already some comments recommending adding some vertical locality by tiling, Hilbert order, or Z order. I…

nice idea, I think it is somewhat more in line with the keep it simple option, as I e.g. have no idea what a hilbert curve for an arbitrary size rectangle looks like. And you still get compression for x and y directions (though no run length encoding the vertical, perhaps a further addition).

I quite like this approach of defining a few compression methods, see which one works best, and apply that one. I used a similar strategy for time series compression where I would take a chunk of data, apply z few different compression algorithms on it (RLE, delta RLE, etc) and just keep which ever one was smallest. Of course here it is done on a per pixels basis, and I used arbitrary size chunks. The latter is trivial to parallelize. Same could be applied here though, split the image in half and compress both parts independently

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

#80

Post by adgjlsfhk1 »

Why not separate the format for RGB vs RGBA based on a header? Since images will never have both RGB and RGBA pixels, you would be able to get an extra few percent encoding by using different (and conflicting) tags for the two types of images. For example you could have QOI_COLOR_RGB which would use a 5 byte tag and QOI_DIFF24_RBG could store 7 bit differences for 2 colors and 6 bit differences for the other color. For RGBA, you could do something similar for the two tags that are RGB specific.
Post reply on HN