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

131–140 of 303 posts

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

#131

Post by demute »

kortex wrote: post #122
sam0x17 wrote: post #115

Earlier quoted context omitted.

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.

CIE XYZ is complete.

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

#132

Post by willvarfar »

st_goliath wrote: post #110

Out of curiosity, I modified the benchmark program to simply toss the pixel data into lz4/lz4hc for comparison (patch file: https://paste.debian.net/1220663/ ). I'm actually quite impressed how the resulting size is a little bit smaller than lz4hc (actually not even that far away from libpng), while the encoding speed is quite close to lz4, despite seemingly not having as many hacks and tweaks under the hood to get t…

I believe (from quick code inspection) that the symmetry in encode/decode performance for QOI is because it has to generate the hash-table on decode too.

Normal fast encoders use some kind of hash table or search to find matches, but encode the offset of the match in the source rather than in the table. QOI is encoding the offset into the table, which gives much shorter offsets but means the decoder has to maintain the table too.

(The slow PPM compressors etc do maintain the same table in both encoder and decoder, and have symmetrical encode/decode performance too. See http://www.mattmahoney.net/dc/text.html)

Its not really in the spirit of of QOI to add the complexity, but I'd imagine allowing the encoder to specify how big the hash table was would be only a small tweak, and encoding literal blocks instead of pixel-by-pixel will improve handling input that QOI can't compress better.

I would be curious to know if planar helps or hinders. Perhaps even see what QOI makes of YUV etc. And I want to see 'heat maps' of encoded images, showing how cheap and expensive parts of them are, and which block type gets used. Yeah, going a bit beyond the spirit of QOI :D

And from looking at the code I'm a bit confused how 3-channel is handled for literals because the alpha still looks like it gets encoded. Would have to walk through the code to understand that a bit better. Is it going to deref off the end of the source RGB image? Etc.

(People interested in compression may be interested in the go-to forum for talking about it https://encode.su/threads/3753-QOI-(Quite-OK-Image-format)-l...)

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

#133

Post by renonce »

So it looks like the algorithm diffs neighbouring pixels, assume that the difference is likely to be small, and encodes the difference in 1, 2, 3 or 4 bytes. It does this without complex things like huffman trees and therefore got a major improvement in performance while approaching the compression ratio of zlib. That's interesting.

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

#134

Post by selcuka »

wwalexander wrote: post #119

Are there compression algorithms that take longer than O(n)? My impression is that even two-pass encoding is O(n) with a large constant factor in front of it, but I’ve never actually thought this much about it.

Some LZ variants such as LZ77 and LZW are O(n), but LZH, for example, is O(n*logn) because of Huffman encoding. I agree that O(n) is not revolutionary, but the simplicity of this algorithm makes it faster to execute.

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

#135

Post by bob1029 »

This is very impressive work.

One thing I did recognize after my last trip into the rabbit hole - JPEG can be the fastest format by orders of magnitude if you are using an appropriate encoder. The project mentions 20x-50x speedups over PNG which are commendable, but once you throw LibJpegTurbo into the mix (it does use SIMD), you will find a substantially different equation on your hands. I can do 1080p 4:4:4 JPEG encodes in ~3ms on my workstation today.

I am not saying you should always use jpeg (some people like to keep all their original pixels around), but if you want to go really really fast you should consider it. The latency is so low with this approach that I have been looking at the feasibility of building a streaming gaming platform around it. Current status of that effort is somewhere between "holy shit it actually works" and "maybe?"

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

#136

Post by simcop2387 »

kortex wrote: post #130

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,…

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

My understanding is that this is one of the techniques that png uses (though not zstd) for doing it's xompression too. Along with I think some different strides down the image and some other stuff but I don't fully understand everything it tries. That's what optipng and friends play with for parameters to find the best settings for decomposing the image for compression.

If you look at what jpeg and similar codecs do they nearly take a DC offset out of the image because that difference then greatly reduces the range of values you have to encode which means that you need fewer bits to do so. Combine that with range or arithmatic coding and you can get decent efficency for very little work. Then with lzw, zstd, etc. You can get lots of other patterns taken out and compressed. Lossy codecs try to take out the stuff we won't see with our eyes so that the set of values to be encoded need fewer bits and it'll also make more patterns appear that can be exploited too

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

#137

Post by superjan »

sbrki wrote: post #75

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 w…

Traditional compression research usually prioritized compression ratio, so more images would fit on your floppy disks and were faster to download over 28.8k modems. It usually means increased complexity.

Png has it’s own story as it’s #1 design goal was to avoid techniques that were patented at the time. So they combined a simple set of prepasses with zip/gzip compression. There were better techniques known at the time, but the idea was that combining simple, and known patent-free solutions was the safest way to achieve a free format.

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

#138

Post by rytill »

phkahler wrote: post #95
CornCobs wrote: post #36

Earlier quoted context omitted.

Single header libraries are hugely more ergonomic and easy to use. Just get the file, #include it and you're done! Most C libraries on GitHub prefer this mode of distribution now

>> Single header libraries are hugely more ergonomic and easy to use. Just get the file, #include it and you're done! Most C libraries on GitHub prefer this mode of distribution now I find that odd. How is that significantly better than dropping 2 files into a project and #including the header? A good build system should just compile all the C or C++ files in a given place, so nothing needs to be changed other than d…

Why use two files instead of one?

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

#139

Post by lstamour »

demute wrote: post #131
kortex wrote: post #122

Earlier quoted context omitted.

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.

CIE XYZ is complete.

Isn’t that kind of like saying Real numbers are complete? Yes, it’s true, but we don’t have an infinite level of precision for each colour. So we have to, practically speaking, limit how many colours can be specified to some reasonable (and arbitrary) number, e.g. 10 million or 1 billion or more (in terms of number of colours in a colour space) and representation in digital bits. Also, since I conflated the two a bit, it is often helpful to restrict what the max range of a colour is so that you can get more useful data out of the same precision. It’s kind of like creating a dictionary to compress data, you can express more useful values with less data by choosing to display a subset of colours and by picking where the white point is for your display. These optimizations used to mean more than they do today, perhaps, but it can still take a lot of effort to transfer 10-bit or 12-bit raw pixel data at 4K resolution, 120 times a second… And it’s worth pointing out that while 8-bit is all you might need as precision for perceptually lossless HDR (with dithering), that kind of range isn’t good enough for colour editing work. It’s like starting a photo edit from the JPEG rather than the RAW file.

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

#140

Post by selcuka »

tonmoy wrote: post #81

I am not familiar with image encodings, but isn’t the idea of complexity relative? For example getting rid of Hoffman encoding and byte aligning everything may be less complex for computers, but when making energy and area efficient hardware, we may not care that much about some of these things?

For a small number of operations, sure, but when you need to compress a million, or a billion images, the performance optimisations quickly add up.
Post reply on HN