HEVC Bypass Arithmetic Coding

[rudyb]

Hi,
Why do we do bypass-arithmetic coding in HEVC?,

I can see that arithmetic coding adds coding efficiency in the case of the encoding with the Context Update due to continuous probability update. However, I cannot see that why bypass coding adds any coding efficiency!

If we treat the probability of the bins being fixed and equal (p(0) = 0.5, p(1) = 0.5), then isn't it that the binary sequence, going into the bypass-arithmetic coding will not get altered since every bin has the same (0.5) probability? Then why do we even need bypass arithmetic coding?

[LoRd_MuldeR]

Not all bins are coded using an estimated probability (i.e. context coded). Bins can also be coded assuming equal probability of 0.5 (i.e. bypass coded). As a result, bypass coded bins avoid the feedback loop for the context selection. In addition, the arithmetic coding is also simpler and faster for bypass coded bins, as the division of the range into subintervals can be done by a shift, rather than a look up table which is required for the context coded bins. Thus multiple bypass bins can be processed concurrently in the same cycle at lower power and area cost than context coded bins.The number of context coded bins was significantly reduced for syntax elements such as motion vectors and coefficient levels. For these syntax elements, the first few bins (i.e. the most significant bins) were context coded, and the remaining bins were bypass coded. For instance, in AVC, the first bins of the motion vector difference were context coded. For HEVC, it was determined that only the first two bins had to be context coded. Similarly, the number of context coded bins for each coefficient level was reduced from 14 in AVC to either 1 or 2 (depending on the number of coefficients per 4x4 block) in HEVC.

http://www.rle.mit.edu/eems/wp-content/uploads/2013/11/sze_sips_2013.pdf

[rudyb]

Thanks but my question is slightly a different one. Because what I am thinking is that if there are equal probable bins (0.5), then if we have a sequence that goes inside arithmetic coder, then the sequence should not really be changing if all the bin are equal-probable (p(0) = 0.5, p(1) = 0.5)

what I am thinking is like the following:

e.g.
http://www.babaians.com/hevc/bypass_encoder.png

So, then why cannot we just bypass the "bypass arithmetic coder" completely?

[LoRd_MuldeR]

Arithmetic coding encodes a series of symbols (in case of CABAC a series of bits) as a single value. It starts with an interval, usually 0.0 to 1.0. This interval is subdivided into several segments. There will be as many segments as there are symbols (in case of CABAC there are only two segments). And the "width" of each segment is proportional to the probability of the corresponding symbol (i.e. the more likely a symbol occurs, the "wider" its segment will be). Now, you look what symbol you actually got (in CABAC either "0" or "1"), select the corresponding segment and make that segment your new interval. Then, whatever interval you have now, you again subdivide it in the same way as before. And then you again select the segment that corresponds to the next symbol. And so on. You simply repeat these steps, again and again, until all symbols (or bits) have been encoded. Finally, you take an arbitrary number that lies within the final interval. This will be your final result/output!

So, in each step of CABAC, you have to subdivide your current interval into two segments: one segment that corresponds to a "0" bit and one that corresponds to a "1" bit. Now, for some bits (or "bins") CABAC uses a context model to estimate the probability of each symbol (i.e. the "width" of each segment is proportional to the estimated symbol probability), while for the other bits it simply assumes a probability of 50% for both symbols (i.e. both segments have identical size). The latter is what they call "bypass" mode. To my understanding, the "bypass" mode is merely a speed hack, because dividing the current interval into two equal-sized segments is much faster than employing a context model. Also for some (most?) bits using a context model wouldn't improve compression anyway, because they tend to be equally distributed. For these bits the "bypass" mode can be used without hurting compression. As quoted above, HEVC significantly reduced the number of context coded bins.

[rudyb]

You are EXACTLY right, and you are pointing to the same thing as I am. That is exactly what I am saying too. Take your sequence, if it is a 1 put it in [0.5 1] interval, then change the interval and encode the next bin, if it is a 1 do the same thing, it is a zero change the interval to [0 0.5], and .....
If you keep doing the same thing, and at the end, whatever arbitrary number that it resulted in, you just try to decode it back and, it will result in the exact original same sequence as your input.
And the reason is obvious, because along changing the interval, you always changed it equally to either [0 0.5] or [0.5 1].
Because, I think the only factor that will cause a change in the output sequence to be different than the input sequence is the fact that we are dividing the probabilities to a NON-equal cases (which is not the case for bypass-encoder).

That is why I am saying, why do we even need the bypass encoder. What I am thinking is that whatever we feed into the bypass-encoder block, we gonna get the same thing back, then why do we even need a bypass-encoder? why do we need to divided into equal probable intervals, when we know it is not gonna change the sequence!!!

Look at this example:
Imagine that I want to encode sequence "1001", based on arithmetic coding, this sequence (final interval) is encoded as the decimal number 0.5625
Assuming equal-probability

http://www.babaians.com/hevc/bypass_encoder2.png

Now, similarly, if I take the number in the final range (which happens to 0.562), and try to find the binary equivalence of it, it will result back to "1001"....

What I am trying to say, is that no matter how long you pick the sequence, and no matter how narrow the interval gets, as long as it is divided into two equal ranges, then your output sequence is the same as your input sequence.

Then what I am wondering, is why do we even bother going through the hassle of "bypass-arithmetic coding"

Obviously the output pattern will change if we go through the Context-based arithmetic coding.

[LoRd_MuldeR]

If you start with [0,1] and if you assume that the first bit is "bypass" coded and if the first bit is a '0', then your new interval would be [0,0.5] (for a '1' it would be [0.5,1] instead). And if that was the last symbol in the input sequence, you could now output any number inside the 0.0 to 0.5 range as the final result. Of course, you would pick the one that can be represented with the smallest number of bits. If, instead, you need to encode one more symbol and if the next symbol is again "bypass" coded and if it is a '0' again, then your new interval would now be [0,0.25] (for a '1' it would be [0.25,0.5] instead). Now, if that was your last symbol in the input sequence, you could output any number inside the 0.0 to 0.25 range as your final result. Once again you would pick the one that can be represented with the smallest number of bits. And so on...

Furthermore, I think it's not like either all of your bits are "bypass" coded or all of your bits are context coded. Instead, each syntax element is first converted into a sequence of bits, called "bins". This process is called "binarization". The result of the binarization process (string of bits) represents the input for the arithmetic coder. And, to my understanding, it's quite possible some of these bins (bits) are context coded, while the remaining bins (bits) are "bypass" coded. It's a mix of both modes.

[rudyb]

You are exactly right. Your example falls exactly aligned with my understanding, and even the picture that I included above reiterates around your exact point. But what I am saying is that is there any explanation that why are we use bypass coding?
Would you agree with the picture that I drew? I believe it restates the same thing as you are saying? If you agree with the above picture, then you should also see that output bins will be the same as the input bins.
I agree with you on the context adaptive arithmetic coding part of it. I also agree that part of the syntax passes through the Context-Adaptive arithmetic coding, and part of the same syntax may pass through the bypass-coding. What bothers me is that I cannot justify the reason that why do we even need the bypass coding !

Because remember that what we are feeding into the bypass arithmetic coder, is already binarized. And binarization block happens prior to the arithmetic encoder block. So, what I don't understand is that we already made a binarized sequence based on different symbol coding techniques (e.g. TU/Exp-Golomb...), so why are we passing a set of binary numbers into a block (bypass arithmetic coder) that doesn't change any of the pattern of the binary data???

[LoRd_MuldeR]

What I am trying to say, is that no matter how long you pick the sequence, and no matter how narrow the interval gets, as long as it is divided into two equal ranges, then your output sequence is the same as your input sequence.

Then what I am wondering, is why do we even bother going through the hassle of "bypass-arithmetic coding"

Obviously the output pattern will change if we go through the Context-based arithmetic coding.

I think that's the point. "Your output sequence is the same as your input sequence" only works as long as all bins are "bypass" code. But in practice every syntax element probably has at least a few context-coded bins too.

[foxyshadis]

A bypass coder exists because the worst case for any kind of compression algorithm is to expand the data, and even achieving no compression just wastes CPU cycles. Better to just bypass the compression if you know that you won't get any compression, on average. Some algorithms, like LZMA2, do this by sacrificing a tiny bit of compression potential to signal bypass; in HEVC, it's hardcoded in the decoder instead. If you can correctly model what always is and isn't compressible, placing the signalling in the decoder is optimum.

[rudyb]

But Why would it expand the data if there were no bypass encoder? If we already know bypass encoder doesn't change the number of bins, so leaving it there or removing it should not affect the length of the data. I am not sure if I follow the reasoning that how the bypass coder helps NOT to expand the data, if it doesn't change the sequence of bins that it processes!?

[LoRd_MuldeR]

Some bits tend to be equally distributed. So for these bits, coding them with a context, doesn't give you any extra compression (compared to assuming fixed probabilities of 0.5 for both cases, aka "bypass" mode), but requires extra computation. Spending extra computation for no real benefit is a bad idea, especially when CABAC tends to be slow anyway. That's why they only use context modeling for those bits where it actually helps. In other words: the "bypass" mode is a speed hack.

Also I think CABAC does not need any signaling for "bypass" coded bits anyway. That's because each syntax element is converted into a sequence of bits, called "bins", first. And then the standard defines which bin uses "bypass" mode and which one doesn't. But if you stored the "bypass" bins 1:1, i.e. without using the arithmetic coder at all, then each "bypass" bin would cost exactly one bit. With the arithmetic coder, it may cost less than one bit. It's a property of arithmetic coding that a symbol's bit cost doesn't need to be an integer number of bits (as opposed to, e.g., Huffman). Yes, if all bits were "bypass" coded we would end up with the original 1:1 bit sequence again. But not all bins are "bypass" coded, right?

[pieter3d]

The reason you encode bypass bins at all (as opposed to stuffing them in the bitstream directly) is to keep the flow of the arithmetic process going. Coding a bin (that is not bypass) means you are producing (on average) fractional bits, so there isn't just a good place to add a bit to the bitstream.

[rudyb]

I see this makes sense. Thanks for explanation.

[foxyshadis]

But Why would it expand the data if there were no bypass encoder?

That's just the way compression works; any algorithm that can compress some data must also expand some other data, like already-compressed or random data. Generally algorithms are designed to signal that and then store the data uncompressed, so they only expand a few bits or bytes; that's how zlib and lzma work, carrying a flag in every header to mark pathological data. BZip kind of forgot that, or didn't want to waste a header flag, and in the worst case can expand random data up to 25%. If you bypass that check in a custom zlib or lzma codec, they show similar worst-cases.

Huffman and Arithmetic coding are literally unbounded in a truly pathological case; given a set of starting probabilities, you can design a stream where each bin is the least likely, and since real probabilities aren't exact, the output will keep expanding with each bin.

This is pretty esoteric, though, and in AVC without bypass it'd only amount to an extra bit here and there. The real purpose is mostly a combination of speed hack and keeping known random junk from polluting the statistics, saving that for more predictable data.