Cabac

[rooofa]

Helllooo.. I am doing the implementation of Entropy Coding of H.264 (CAVLC & CABAC)... I finished the CAVLC... its fine.. But I have a problem understanding the CABAC because i think different papers says different things or i cant understand correctly...
So what i ask if any one have a resource that will make me understand the CABAC to be able to implement it... and i dont understand the standard beacuse it explains on C and am using Java....
Thank you

[akupenguin]

The standard explains it in flow charts. There's no C, and only a tiny bit of pseudo-code.

[rooofa]

Look I am really in a hurry to implement and the examples are a very good way to make me understand.. i need some papers that contain examples... if that is possible

[neuron2]

There is an explanation and example in section 6.5.4 of the AVC e-book that you can find at the library of my web site.

http://neuron2.net/library/avc/H.264.And.MPEG-4.Video.Compression.Video.Coding.For.Next.Generation.Multimedia.pdf

Also, see here:

http://www.rgu.ac.uk/files/h264_cabac.pdf

[rooofa]

Thank you for the articles it really helped... but one thing that i cannot understand is the Context Modeling.. if anyone here implemented before or know a general idea about it.. i really need to know simple steps to implement it...

[neuron2]

The standard defines the context models to be used for each syntax element.

[rooofa]

yea i saw that thank you.... but I didnt study Entropy before... i dont understand what really happens after binarization (General Understanding)...
so if anyone can briefly tell me what happens after Binarization that would be nice...

[neuron2]

I suggest you get a good understanding of BAC (binary arithmetic coding) first. Then read this:

http://lts4www.epfl.ch/teaching/ic/repository/01218195.pdf

[rooofa]

I guess you are right about the BAC... but I cant find a straight paper discussing the subject in details... Anyone have a paper or article that will make me understand the Binary Arithmetic Coding.....
Thank you guyss....

[rooofa]

Anyone know links of papers for BAC.. Binary Arithmetic Coding?

[neuron2]

http://www-users.rwth-aachen.de/Eric.Bodden/files/ac/ac_en.pdf

It's easy to find stuff like that with Google.

[rooofa]

Thank you for the article.. my problem with Google that I found many papers talking about many things in arithmetic coding so i thought someone read something before would help me to use it to make the CABAC

[rooofa]

Hello guys, i guess i am having problems implementing the cabac... anyone implemented it before can help here??

What i 100% understand is that if the input a non-binary value it is binarized by several ways(which i implemented).. after that each bin of it goes to have a model for it.

their are 4 types to choose the context model... i think

from this point there is problems.. i need a breif way to know what to do ( not a paper :) )...

ex: take the bin.. do that.. do that... do that... do that...
thats all...

Thank you..

[neuron2]

There's sample code corresponding to the algorithm explanation at the link I gave you. Just fire it up in a debugger and you can go step-by-step through the process.

[rooofa]

there is no sample code in the CABAC paper, there is only a code explaining the UEGk.
If you just can answer me that question please in simple english :)
What are the steps of context modeling, starting from output of binarization to input of BAC?

[neuron2]

In the last link I gave you there is full source code for BAC.

For full CABAC, you can look at the source code for x264.

With the papers, the specification, and source code, you should have all you need.

[rooofa]

where is that?

[neuron2]

http://www-users.rwth-aachen.de/Eric.Bodden/files/ac/ac_en.pdf

The last section is called:

"A reference implementation in C++"

It also points you to:

http://ac.bodden.de

which has useful visualizations and other resources. If you don't "get it" from all that, I don't know what else to offer.

You can easily find the x264 project and source code using Google.

[rooofa]

I guess i gonna see it...
but i want to ask a question that may solve things to me:

Questions:
as far as now
- mvd value is binarized and after that each bin value goes to have a context.
ex: 11110
- the mvd (syntax element) have context in table 9-15
1 1 1 1 0
43 44 45 46 47
?? whats next

what if the value of bin0 is 40 bin 1 will be 41 or 43

what if there is to bin 8 and the table only has till 53 and bin8 is 56 for example

[neuron2]

Encode each bin. The selected context model (for each bin) supplies two probability estimates: the probability that
the bin contains “1” and the probability that the bin contains “0”. These estimates determine the two
sub-ranges that the arithmetic coder uses to encode the bin.

I think your best bet is to look at the x264 source code. You might also PM akupenguin and ask him to chime in here.

[akupenguin]

Before starting to encode or decode a slice, use tables 9-12 through 9-24 to initialize the probability values of all the contexts. Then those tables aren't used for the rest of the coding process. And while 9-12 though 9-24 are separated by the type of syntax element they apply to, they're logically just one huge table of all the contexts, and an implementation doesn't care about the separation between tables.

So, you're coding mvd[y].
Table 9-25 says the contexts for mvd[y] are 47..53, and says the binarization process is UEG3 (section 9.3.2.3)
Table 9-30 says the context increment for bin0 is 0, 1, or 2 (i.e. absolute context numbers 47, 48, or 49) (depending on the mvd of the neighboring blocks, section 9.3.3.1.1.7), and the context increments for bins 1, 2, 3 are 3, 4, 5 respectively, and all further bins have context increment 6. So bin8 also uses context 53.

[rooofa]

thats so great..

just a breif of what i understand...
first i ll see what type of syntax element i have, second i go to table 9-25 to see which row in main table to use (which contain the m and n thing) which for example found in table 9-15... then i go to table 9-30 to see what is bin0, bin1....bin8 system and their corresponding values under in table.
and then? :) did i finish the context model operation or not?

[rooofa]

hello again... guys i guess the subject is complicated and this is my graduation project.. i am really lost in cabac.. i implemented cavlc and still have to implement the cabac.. :) i guess its so difficult..

i ll tell you what i know.. and if anyone would help me with good information that would be great...

I finished the binarization process, for now the unary and TU, so any non-binary value will enter will be binarized...
after that for example i have 11110..

what i know:

1- i need to what type syntax element so that i can decide which table to go... and from table 9-24.. i will know what are the context for this type.. like the mvd[y] from 47..53
2- i ll go to table 9-30 and check what binarization type to use for this type and the sequence of bins..

Is this correct?
What is the m and n in the table?
What is cabac_init_idc?
What to do next?

[neuron2]

Did you look at the x264 source code? There's a full implementation of CABAC encoding in there.

[rooofa]

understanding the concept and the system in english is more important now than understanding the implementation.. plus source code in c and i am implementing it with java.. and am not so good in c.. so i better understand whats going on and then start to implement....
do u know anything that whould help?

[neuron2]

You've been given everything you need to understand the concepts. Nobody is going to "implement" it in English for you. Maybe you should invest some time in understanding C syntax (which is not so different from Java). Then you'll be able to see how the x264 implementation maps to the concepts. The code is a definitive, unambiguous embodiment of the concepts.

You could simply port the x264 implementation to Java and be done with it. :)

[rooofa]

I guess i will use the source code as the helper... where is is then?

[neuron2]

Try using Google as I suggested to find the x264 encoder project. You really need to learn to use Google productively. Nobody likes having to spoon feed people.

I will give you this link to the JVT reference software, which also contains a reference implementation of CABAC (in the lencod\src):

http://iphome.hhi.de/suehring/tml/download/

[rooofa]

i saw that code since i started implementing and since i dont have time to learn c, i didnt consider it as help.

did anyone made the cabac before?

[neuron2]

did anyone made the cabac before? I pointed you to two implementations.

[rooofa]

i just need to ask questions of things i dont understand...

i need someone who made it before so it can help me!!! i dont need implementations or source codes thank you

[rooofa]

I dont understand the algorithm of UEGk and FL Binarization..
I need an example of both..
Thank you

[rooofa]

another question:
1- for example the syntax element mb_type its binarization type is U, but U has input an integer value to be able to make the binarization, so for example mb_type what is the corresponding value to it so it can enter the Binarization process?

[neuron2]

mb_type is a number (whose meaning is defined by the standard). What is the problem?

[rooofa]

mb_tybe is a syntax element... as far as i know...
which table in the standard it refrence the number

[neuron2]

Search for mb_type in the spec. You'll find it.

I know, you don't have time. :)

[rooofa]

no i do.. but i have a point that i miss....
i know now all the steps... but the missing point is what value to send to the binarization if its type is TU or U...
Is it an input from the user?
mb_type value=3 or 4...etc
or what?

[neuron2]

mb_type is a number whose meaning is defined in the spec. E.g., table 7-11 for I slices, mb_type numbers are given in the left column and the meaning of those numbers is the other columns.

The actual value will be determined by what the encoder algorithm used when encoding that macroblock.

[rooofa]

see i didnt know that.. cause i am only doing the entropy coding.....
as far as i know the syntax elements that will be my input.. are the only listed in table 9-11 (mvd_l0[ ][ ][ 1 ], coded_block_flag....etc)... i need a table that contains the opposite values of those types.. nothing more.

[neuron2]

What do you mean by "the opposite values of those types"?

The spec defines the possible values of all syntax elements.

[rooofa]

input of my implementation is syntax element, and slice type... i get the binarization type.. but U and TU expect an integer input.. so i dont know what to send there (depending on syntax element that came in)...

[neuron2]

If you are just implementing a CABAC encoder and not the part of the encoder that feeds the CABAC encoding, then you can just choose random values that are legal for each syntax element.

But your output bitstream is going to have to be spec compliant overall if the decoder is to be able to parse the bitstream correctly. What exactly are the requirements for your graduation project?

[rooofa]

to implemenet the cabac encoder... based only on the entropy coding part.. i dont have to go to other parts..

thats good point about knowing the range of values of each syntax element.... how is that possible?

[neuron2]

thats good point about knowing the range of values of each syntax element.... how is that possible? By reading the specification.

[rooofa]

ok put that aside for now...
question for FL binarization:

if S=2 X=2
By putting S inside ceil(log2S) result=1.
meaning that a minimum 1 bit to present 2. so Binarization of 2 is "10" normally?