[daala] Curious about progress of codec

[Jean-Marc Valin]

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:
https://github.com/xiph/daala/commit/39debe04
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
merged:
https://github.com/xiph/daala/commit/3cd606c24af
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.

Cheers,

	Jean-Marc