H.264 decoder inner workings

[bendagr8]

So I've looked through a lot of information on this site, and the web, but because of various things, there are a lot of gaps in what I know. I was hoping someone could clarify or point me in a good (read: not super technical, super mathematical) direction.

First of all, what exactly is a transform? More specifically, what does it do here? I know it's an integer transform instead of a DCT to save on some math operations, but I am not sure what the purpose of a transform is. I've read lots of docs, and still can't quite grasp its underlying purpose. I think its a mapping, but from what domain to what?

A decoder tasks are mainly this:
1. Unwrap the packetized elementary stream header and determine various info. I understand this step pretty well.
2. Inverse entropy operation (inverse CABAC/CAVLC). I assume there is nothing fancy here, just a function to inverse CABAC/CAVLC.
3. ? we magically have multiple sized macro blocks??? what form are they in? I have no idea what, if anything, goes on here. What does our data look like/reprsent at this stage?
4. Inverse transform operation. We've now trasnformed our data back to bit land?
5. Inverse quantization operation. Does this step even occur?
6. I or P frame? go straight to 8 if I.
7. Inter or Intra frame encoding. I would really love some info on this.
8. deblocking
9. out to data frame queue

Okay. So my request here is to get explanation/whatever info possible that people can insert. Correct places that I'm wrong, add to places that you have info. Point me to places with good easy explanations of things if thats easiest.

A lot of my gaps here are basic video stuff, so please try not to get too upset with me.

And thus concludes my 4 year hiatus from doom9.

[omion]

3. From what I know of H.264, the macroblocks are always 16x16. However, they are split into one of 69 different motion vector patterns. So one macroblock might say that it has two motion vectors: one for each 8x16 rectangle. Or it might say that it has 16 motion vectors: one for each 4x4 square.

4. Note that the transform can be either 4x4 or 8x8, if the "high" profile is used (x264 supports 8x8 transforms) I assume this is decided on a macroblock basis, but I really don't know.

5. Inverse quantization is needed, except it doesn't really "de-quantize" the data. It multiplies the data by whatever it was divided by in the encode stage. Also note that this step should be before the de-transform, as it is the transform coefficients which are quantized

6 and 7. As far as I know, an I frame is an entirely "intra" frame, whereas P and B frames can have both "intra" (no motion estimation) or "inter" (normal motion estimation)

The transform is a mapping from spatial to frequency domains. It is done becuase the low-frequency info (average color and very smooth transitions) is more important than high-frequency info. So, after you've transformed the data, you can throw out or quantize the high-frequency information and still have the image look good.
Pretty much all lossy audio and visual encoders utilize some form of frequency transform. Most of the time it's the DCT, but some codecs (like H.264) use their own.


If I were to make the list, it would be somthing like this:
1. Unwrap the stream
2. Inverse entropy
3. De-quantize
4. De-transform
5. Motion estimation based on frames in the frame queue (skip for "intra" macroblocks)
6. Deblocking
7. Output to frame queue

The general layout is similar to other video codecs, but each step is more advanced than most other codecs.

I, however, have no experience with either an H.264 encoder or decoder, so I couldn't say for sure what goes on. Feel free to correct me.

[bendagr8]

So my math is terribly rusty. I just got a new document that will hopefully clear some of these things up, but before I dig into it:

How is video reprsented in the spatial domain.

We have a picture, the picture is represnted by all ones and zeroes. The picture is split up into 16x16 macroblocks, each pixel in the macroblock made up of ones and zeroes.

Now I'm sure I am just an idiot, but how is this spatial, I can envision no XY(Z) plane, just 11101010100011. Also, is the chroma data part of that same transform, or a sperate transform, or no transform at all?

[omion]

I'll make a little example and hopefully you'll understand. (Assuming I understand the question! :p )
Say I have a 2x2 image (8-bit grayscale). I'm going to label the pixels
A B
C DNow, the pixels are stored as simply ABCD (4 bytes in a row). But they still represent a 2x2 image. This is the spatial domain. The problem with it is that usually A, B, C, and D are similar colors, and that turns out to be fairly redundant. So we transform it into something like:
A+B+C+D A-B+C-D
A+B-C-D A-B-C+DAgain, those numbers are still stored, in memory, one after another. This version will need at least 10 bits per pixel, but it is better compressible. Why? Let's give the pixels some numbers:
168 169
170 172If I apply the transform to these pixels, then I get:
679 -3
-5 1As you can see, 3 of the numbers are very close to 0. This is good for compressibility.

The upper-left pixel now contains the average of all the pixels (well, times 4), the upper right pixel is how much the image changes horizontally, the lower left is how much the picture changes vertically, and the lower right is how much it changes diagonally (sort of...)

This is actually the same transform that H.264 uses for the two chroma planes, which brings up the second point:

All three channels are transformed separately. The luma channel (usually!) uses a 4x4 transform. However, for the chroma channels this is only a 2x2 space (due to chroma downsampling) so chroma uses the 2x2 transform I mentioned earlier.

If you're using the "high" profile, then the luma uses an 8x8 transform and chroma uses a 4x4.

[akupenguin]

This is actually the same transform that H.264 uses for the two chroma planes, which brings up the second point:

All three channels are transformed separately. The luma channel (usually!) uses a 4x4 transform. However, for the chroma channels this is only a 2x2 space (due to chroma downsampling) so chroma uses the 2x2 transform I mentioned earlier.

If you're using the "high" profile, then the luma uses an 8x8 transform and chroma uses a 4x4.
Chroma uses the same 4x4 transform as luma. Then you apply another 2x2 transform (the one described) to the DC coefficients from the 4x4s (the same way wavelets normally recurse). High profile's 8x8 transform is for luma only, it does not affect chroma coding.
Chroma downsampling affects the shape of the secondary transform (i.e. it's 4x2 in YUV 4:2:2).

[omion]

Ah. You're right. I knew it was something like that.

[bendagr8]

That was a great response omion, I understood it perfectly. I wish I could carry you to work :). Hmm, on second thought, they would probably fire me and hire you. Actually, this is just my domain until the real expert gets back from vacation.

Akupenguin, I didn't follow you on that. I would appreciate it if someone could explain it.

Also, in the case of a 4x4 transform, how does the transform work. I'm confused how to fill in the middle values. Hopefully you guys have patience, because this is obviously a math thing (I never took linear algebra).

A B C D
E F G H
I J K L
M N O P

transform

AA BB CC DD
EE FF GG HH
II JJ KK LL
M NN OO PP

How can I calculate the transformed values? What's the algorithm?

Thanks.

[omion]

That was a great response omion, I understood it perfectly. I wish I could carry you to work :). Hmm, on second thought, they would probably fire me and hire you. Actually, this is just my domain until the real expert gets back from vacation. :D

Akupenguin, I didn't follow you on that. I would appreciate it if someone could explain it.
Akupenguin is referring to the fact that the luma and chroma each go through two transforms. Here's how it works (can be confusing, so feel free to respond if you don't get it):

For luma, the 16x16 macroblock is divided up into 16 4x4 sub-blocks. These are each put through a 4x4 transfrom. The particular transform they use results in the upper-left pixel containing the average of all the pixels in a sub-block. This pixel is the DC component.
Now you have 16 "special" DC pixels (one from each 4x4 sub-block). So you make another 4x4 block out of those, and apply another transform to it.

In the end, you get one value that's the average of all the pixels in a macroblock, 15 values representing the difference between the sub-blocks, and 15 values per sub-block (15*16=240 total) representing small differences within each sub-block.

For chroma, it's pretty much the same, except that a 16x16 macroblock only contains 8x8 chroma samples (due to the colorspace used). So everthing happens the same, except that instead of making another 4x4 block out of the DC values, you can only make a 2x2 block. So you apply a 2x2 transform to it (this is the one I used as an example previously).

For chroma, you get one value representing the average of the 8x8 macroblock, 3 values representing the differences between the subblocks, and 15 values per subblock (15*4=60) representing small differences within each sub-block.

Also, in the case of a 4x4 transform, how does the transform work. I'm confused how to fill in the middle values. Hopefully you guys have patience, because this is obviously a math thing (I never took linear algebra).

A B C D
E F G H
I J K L
M N O P

transform

AA BB CC DD
EE FF GG HH
II JJ KK LL
M NN OO PP

How can I calculate the transformed values? What's the algorithm?

Thanks.

The first 4x4 transform matrix used is:
1 1 1 1
2 1 -1 -2
1 -1 -1 1
1 -2 2 -1
The second one (the one used on the DC coefficients) is the same but with all 2s turned into 1s. (I have no idea why they decided to use a different transform for the two stages...)

To apply the transform, some linear algebra would be very useful to know:
/ 1 1 1 1 \ / A B C D \ / 1 2 1 1 \
| 2 1 -1 -2 | * | E F G H | * | 1 1 -1 -2 |
| 1 -1 -1 1 | | I J K L | | 1 -1 -1 2 |
\ 1 -2 2 -1 / \ M N O P / \ 1 -2 1 -1 /
(Note that I may have gotten the order backwards). The * represent matrix multiplication. The actual symbolic result of this calculation is fairly long, so instead of writing it out, I'm going to suggest that you brush up on your matrix multiplication ;) .

What I can say is that the "AA" in your example is the DC component, and is equal to A+B+C+D+E+F+G+H+I+J+K+L+M+N+O+P. All of the "AA"s are made into another 4x4 matrix and the second transformation is applied to it, like I mentioned before.

If you're looking for the 8x8 transform used in the "high" profile, you can find it in a paper called "The H.264/AVC Advanced Video Coding Standard: Overview and Introduction to the Fidelity Range Extensions (http://www.cdt.luth.se/~peppar/kurs/smd151/spie04-h264OverviewPaper.pdf)" by Gary J. Sullivan et al. The paper also contains detailed explanations of the rest of the AVC codec. It's a good paper if you want technical info but don't want to go looking at the actual spec (Strangely enough, the publicly available version of the spec is 264 pages long :eek: )

PS. What do you do at your work that requires you to know the inner workings of AVC?

[bendagr8]

Answering you in a PM.