Huffman trees are an easy way to outperform PNG

[iamgreaser]

Where QOI performs well, adding Huffman trees makes it outperform even libpng. The bad news: It makes encoding the image a 2-pass operation (decoding remains 1-pass), so you either have to store the whole result in memory, or encode the raw QOI image twice (once to get frequencies per input byte, and once more to do the actual encoding).

Did some experiments with 2+n Huffman trees, where n is the number of channels in the image (so, 5 or 6 trees).

The format I'm doing here replaces one byte in the header ("hoif" instead of "qoif" - H being short for "Huffman" but also so one could call it "Hardly OK Image Format"), adds 1 extra byte of header after the usual QOI header (I might want to extend this if I take this seriously), then the rest of the image is compressed as if it's a full command stream (including the 8-byte footer).

Note that my prototype is written entirely in Python, so I cannot give a fair performance analysis (it can take a few seconds to compress a large image).

Consider the command list here:

# QOI_OP_INDEX 00iiiiii
# QOI_OP_DIFF  01rrggbb
# QOI_OP_LUMA  10gggggg rrrrbbbb
# QOI_OP_RGB   11111110 rrrrrrrr gggggggg bbbbbbbb
# QOI_OP_RGBA  11111111 rrrrrrrr gggggggg bbbbbbbb aaaaaaaa
# QOI_OP_RUN   11nnnnnn

• The first byte uses the command tree.
• If we are using QOI_OP_LUMA, the second byte goes to the luma byte tree.
• If we are using QOI_OP_(RGB|RGBA), then each byte goes to the tree for the respective channel in the per-channel trees.

Currently, the trees are placed in this order, as 256 bytes where each byte indicates the bit length for that input byte for a canonical Huffman tree:

• command tree
• luma byte tree
• red tree
• green tree
• blue tree
• alpha tree (only if RGBA)

From qoi_test_images.zip, we get these results for photos:

 652383  kodim10.qoi
 593463  kodim10.png
 500083  kodim10.hoi

 675251  kodim23.qoi
 557596  kodim23.png
 519130  kodim23.hoi

1521134  wikipedia_008.qoi
1344960  wikipedia_008.png
1291391  wikipedia_008.hoi

As for RGBA... well, it doesn't quite get to PNG levels (QOI doesn't fare well when the alpha channel isn't mostly 0x00 and 0xFF) but it does still improve the ratio:

 519653  dice.qoi
 349827  dice.png
 411231  dice.hoi

[dumblob]

Thinking about this I am sure the performance could be made really good - the absolute worst case seems to be 2*qoi_time. Which is still much faster then other contenders. So IMHO performance of this approach is not an issue.

What is important though is how much better this could improve upon PNG. PNG does generally not have a good compression. So I think to make hoi appealing, it would need to outperform PNG by a significant margin basically in all cases. IMHO the numbers above are not yet exactly there. I would expect from huffman a tiny little more :wink:.

Thoughts?

[oscardssmith]

well this ever beat qoif+lz4? as far as I understand that does the same thing

[dumblob]

Theoretically the compression could be very similar. But the speed of huffman encoding should be much higher I guess.

[oscardssmith]

Have you tested? LZ4 is ridiculously fast.

[dumblob]

No, I have not tested hoi (because I would need to rewrite it to C for which I do not have any time). I saw some numbers of LZ4 + qoi from others and I just guess hoi would be non-negligibly faster.