<html>
  <head>
    <meta content="text/html; charset=utf-8" http-equiv="Content-Type">
  </head>
  <body bgcolor="#FFFFFF" text="#000000">
    Regarding using probability distribution from the last I-frame, I
    have meant remembering probability distribution at the end of this
    I-frame (not updated further) - additional buffer which is updated
    every I-frame, P-frames use it as the initial probability
    distribution.<br>
    But sure, this is memory cost (a few kilobytes) as trade-off for
    ratio.<br>
    <br>
    Regarding memory trade-off for rANS, encoder needs a buffer just to
    reverse order - you can use a general memory of encoder for this
    purpose.<br>
    The size of this buffer is given by a chosen size of data block
    (usually is fixed), the cost is 2-3 bits of loss per block -
    completely negligible for a few kilobyte buffer.<br>
    From the other side, range coding is a few times more costly for
    software decoding. From hardware perspective, multiplications also
    require energy, and increase the number of cycles per symbol - needs
    increasing frequency (energy).<br>
    <br>
    Here is entire rANS decoding step for 32bits, 16 bit renormalization
    (can be reduced to e.g. 6bit x 10bit -> 16bit multiplication with
    4bit renormalization):<br>
    <br>
    <pre>s =symbol(x & mask);         // SIMD to find s such that CDF[s] <= (x & mask) < CDF[s+1]
x = (CDF[s+1] - CDF[s]) * (x >> n) + (x & mask) - CDF[s];
if (x < 2^16) x = x << 16 + read16bits();     // renormalization

The only branch can be changed to

b = (x < 2^16); 
x = x << (y << 4) + (*stream) >> ((1 xor b) << 4);
stream += b;
</pre>
    Good to hear that you plan to finally fix optimized initial
    probability distributions and rate for separate IDs - sure, it
    should be done after deciding everything else.<br>
    <br>
    Cheers,<br>
    Jarek <br>
    <br>
    <br>
    On 16/04/27 18:19, Jean-Marc Valin wrote:<br>
    <span style="white-space: pre;">> On 04/27/2016 09:14 AM, Jarek Duda wrote:
>> Regarding starting every frame with flat distribution, I believe
>> you still use non-I-frames: which require some I-frame for
>> decoding. So maybe at least start with the probability distribution
>> from this recent required I-frame?

> OK, so here's what happens in a practical videoconferencing
> situation. You're sending I-frames at (e.g.) 15 second interval, but
> 5sec after an I-frame, you lose a packet for a P-frame. It means you
> have to "conceal" (guess) what was in that packet and make up
> something plausible on the screen (obviously not perfect), then you
> decode the next P-frames and any "error" you did in the concealment
> gets spread around as the motion vectors carry them away. It's not
> pretty, but you can still figure out what's going on, and if a big
> change happens you can still see what's happening.

> Now, with what you're suggesting, everything that happens after the
> loss is completely undecodable and you have no idea what's going on.
> In that case, the decoder has no choice but to completely freeze the
> image for 10 seconds until the next I-frame. That's why people don't
> rely (or at least want to have the option of not relying) on anything
> from previous frames for entropy decoding.

>> Another option is varying rate - start with e.g. rate=2,3 for some 
>> number of symbols to quickly get out of the terrible flat
>> distribution, then rise it to e.g. 5 for more subtle adaptation to
>> local situation.

> This has *always* been what we've done. The adaptation on the first 
> symbols is very fast because we accumulate probabilities starting
> from very small flat values. For example, we would initialize a PDF
> with a value of 32 for each symbol and every time we encode a symbol,
> we boost the corresponding bin by 128. The flat distribution really
> doesn't stay around for long. In the case where the probability
> distribution has to always sum to a power of two, then I have a way
> to adjust the adaptation rate to have the same behaviour as the
> accumulation I described.

>> However, still the looking best approach here is to choose
>> separate optimal initial distribution for each ID - just average
>> over sample videos and fix these probabilities in the codec
>> standard.

> As I said, we might do that someday... but it's a *lot* of work
> (that you have to redo frequently) for a small gain.

>> Also, it seems beneficial to separately optimize 'rate' for each ID
>> and again fix it in the standard.

> Also, on the TODO list.

>> A separate suggestion is to take a look at sequences from your data
>> - here is example from single frame of you sample for ID=0: 
>> "00114044010001001404441000010010000000000000000000000100000000000000000000000000000000000000000000000000"
>>
>>
>> </span><br>
    It clearly suggests we have two very different behaviors here - it
    would<br>
    <span style="white-space: pre;">>> be beneficial to split it into at least 2 separate IDs.

> What you saw was basically the symbol that says whether a superblock
> of the image was well predicted or if we need to code something. It's
> going to be different for every clip and since it's one of the first
> symbols being coded, there isn't much "context" to use for it. In
> this particular case, adapting faster helps. In other clips it
> doesn't.

>> Good to hear that you have not only switched to accurate entropy
>> coder, but also to exponential forgetting, which is much better at
>> adapting to local situation. Also you don't longer need the costly
>> non-power-of-two denominator.

> Well, we're still investigating all options. The non-power-of-two
> code always had exponential forgetting (but it was in steps, which is
> less accurate, but also suffers from less rounding issues so it's
> about as good). We now also have a way of making the overhead very
> small even for non-power-of-two without using divisions. So the
> jury's still out -- both options are viable, including dozens of
> variants and combinations.

>> For power-of-two denominator, standard range coder needs two 
>> multiplications per symbol, rANS only one, has simpler multi-bit 
>> renormalization and allows for further optimizations - leading to
>> ~3x faster/cheaper (software) decoding (also reducing frequency of
>> hardware decoder) - here are optimized implementations: 
>> <a class="moz-txt-link-freetext" href="https://github.com/jkbonfield/rans_static">https://github.com/jkbonfield/rans_static</a> The inconvenience is
>> indeed that encoder needs a buffer for backward encoding within a
>> data block (e.g. a frame or its part) - additional a few kilobyte
>> buffer in costly video encoder seems negligible (?).

> Well, these days multiplier hardware is actually cheaper than memory 
> (you'll need a lot more than a few kB to cover the worst case).

> Cheers,

> Jean-Marc

> </span><br>
    <br>
    <br>
    -- <br>
    dr JarosÅ‚aw Duda<br>
    Institute of Computer Science and Computer Mathematics,<br>
    Jagiellonian University, Cracow, Poland<br>
    <a class="moz-txt-link-freetext" href="http://th.if.uj.edu.pl/~dudaj/">http://th.if.uj.edu.pl/~dudaj/</a><br>
    ega<br>
  </body>
</html>