[daala] Curious about progress of codec

Jean-Marc Valin jmvalin at jmvalin.ca
Sun Apr 24 17:21:23 UTC 2016

On 04/24/2016 10:43 AM, Jarek Duda wrote:
> 1) Start with a probability distribution characteristic for a given ID,
> for example a fixed parametric, eventually modified somewhere in the
> file (better behaves in the beginning and allows for more subtle
> adaptation),

Actually, all attempts at doing this so far have failed to produce
improvement over the current "horrible" flat initialization. So I
actually measured how much we lose to that flat initialization in one of
the worst cases you can have: a binary symbol where one value has
probability 1 and the other has probability 0. In that case, despite
initializing with a flat CDF, the total cost of coding N symbols is only
1 + 1/4*log2(N). So it costs (e.g.) 3 bits to code 256 symbols.
Considering that it avoids having to code an initial probability, that
overhead is pretty reasonable.

> 2) use an accurate entropy coder, like rANS in VP10,

You'll be happy to learn that we recently merged a more accurate entropy
coder for power-of-two denominators:
The accuracy is around the same as rANS and VP10, i.e. less than 0.1%
overhead. The improvement on Daala is currently small since we mostly
use non-power-of-two denominators.
We also have found a way to have an accurate coder for non-power-of-two
denominators, but it costs an extra multiply.

> 3) use adaptation with exponential forgetting to make recent symbol more
> important, like
> for (int i = 1; i < m; i++) CDF[i] -= (CDF[i] - mixCDF[i]) >> rate;
> where mixCDF is for the new part, can be tabled for symbol-wise
> adaptation such that frequencies of not used symbol will drop to the
> minimal nonzero frequency,

Well, the issue with that was the high probability floor and the
alternative you mentioned earlier (storing the LSBs separately) is a bit
expensive. Fortunately, we've come up with a better adaptation that does
not suffer from the floor problem and is still simple. The code just got
The idea is pretty simple and very similar to your code above. The only
difference is that the CDF we adapt has a denominator equal to:
(32768-number_of_symbols) so that when we add a floor of one, we're
guaranteed to have non-zero probabilities that sum to 32768.
Using that code, along with the power-of-two entropy coder, I was able
to get about 0.5% improvement on Daala (not merged).

That being said, right now we still haven't made up our mind between the
dozen or so combinations of entropy coder and adaptation variants.

> 4) Allow for varying adaptation rate - for example some ID use more
> static probability distribution, for some it is beneficial to allow
> encoder to choose one of a few possible adaptation rates.

So far, not much came out of that when testing over multiple files and
multiple rates.



More information about the daala mailing list