BistEntropyRefine and FinalHuffmanCost

445 views
Skip to first unread message

Ritwik Ghosal

unread,
Dec 14, 2023, 12:43:16 PM12/14/23
to WebP Discussion
Hi

I was going through the  bit_cost algo and found out two functions BitsEntropyRefine() and FinalHuffmanCost().

In the first one, there are some floating point numbers multiplied with the sum and the entropy field of the bits_entropy structure. 
e.g, for one of the instances the reason given is : " Two symbols, they will be 0 and 1 in a Huffman code. Let's mix in a bit of entropy to favor good clustering when distributions of these are combined".

What is being described here??

And in the other function, FinalHuffmanCOst() , some similar floating point numbers are multiplied to several fields of the "stats" structure. (structure containing the information about the zero/nonzero , >/<= 3 - length' streaks).

will be great help to know the reasons behind the floating point numbers.

Cheers!  

Vincent Rabaud

unread,
Dec 18, 2023, 9:37:59 AM12/18/23
to webp-d...@webmproject.org
Symbols follow statistics that are stored in histogram (called
population in the code).
There is a theoretical entropy for that histogram but it does not take
into account how the symbol will be stored: it will not be stored
using its perfect entropy (that is computed in
VP8LBitsEntropyUnrefined), but through a Huffman tree which will give
it a slightly different entropy.
That is where those functions are useful: they try to get a better
estimate of the final entropy, knowing that it will be stored in a
Huffman tree.
BitsEntropyRefine tries to compare to the best case scenario (all
symbols have the same probability) which we know we cannot beat. The
"mixing" with entropy is empirical.
FinalHuffmanCost takes into account some empirical observation that
some trees with some properties (e.g. several streaks of 0), are
easier to encode than others.
> --
> 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/c3b250c1-9c4c-4d3e-ab95-88c0110b36c3n%40webmproject.org.
Reply all
Reply to author
Forward
0 new messages