Unintuitive Huffman Tree Constraints for Webp Lossless

349 views
Skip to first unread message

Alec Rohloff

unread,
Aug 22, 2022, 3:07:29 PMAug 22
to WebP Discussion
While trying to hand-write lossless Webp files, I ran into an issue that it took me many hours to figure out what was going on.

When specifying normal code length prefix codes for G, R, B, A, and Displacement, it appears that Webp requires you to specify more code lengths than you necessarily use, so that the resulting canonical Huffman tree contains all the codes needed to make it "balanced". I'm new to Huffman encoding, so I might be using these terms wrong, so here's an example:

e.g. if your image only has 3 possible B values, webp is unable to decode the image if you only specify code lengths (2, 3, 3), which should expand to the following:
"00"
"010"
"011"

This appears to be illegal because the set is missing all its counterparts that begin with 1.

So instead, you must specify code lengths (2, 3, 3, 3, 3, 3, 3), which expands to:
"00"
"010"
"011"
"100"
"101"
"110"
"111"

Is there a technical or mathematical reason that Webp applies this constraint?
It seems like Webp ought to know how to construct a balanced huffman tree even when the unused branches aren't explicitly specified in the image file.

Would it be possible to add an explanation of this constraint to the documentation?

James Zern

unread,
Aug 22, 2022, 4:58:22 PMAug 22
to WebP Discussion
Hi,

Could you file a bug [1] please? This will help track any updates to the code or documentation.

Jyrki Alakuijala

unread,
Aug 23, 2022, 2:15:52 PMAug 23
to webp-d...@webmproject.org
A canonical prefix code is a method of encoding an optimal prefix tree.

An optimal prefix tree does not have empty values even when length-limited and otherwise manipulated like we do in our encoder -- with the exception of having only one symbol, which is covered in Simple Code Length Code.

--
You received this message because you are subscribed to the Google Groups "WebP Discussion" group.
To unsubscribe from this group and stop receiving emails from it, send an email to webp-discuss...@webmproject.org.
To view this discussion on the web visit https://groups.google.com/a/webmproject.org/d/msgid/webp-discuss/fc25941d-d48c-4aee-abd0-c9c5526cf485n%40webmproject.org.
Reply all
Reply to author
Forward
0 new messages