Unintuitive Huffman Tree Constraints for Webp Lossless

[Alec Rohloff]

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]

Hi,

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

[1] https://bugs.chromium.org/p/webp/issues/entry?template=Defect+report+from+user

[Jyrki Alakuijala]

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.