h.264 improved intraframe coding

[raven21]

Hello!
I am writing a paper about intraframe coding and have found some proposed algorithms for efficient intraframe prediction methods (based on frequency characteristics, edge detection,etc. ). My question is are any of these algorithms included into standard lately and where these information can be found (meaning updates into standard)?

[raven21]

Nobody?!

[akupenguin]

Efficient in speed or in compression ratio?
Encoder-side algorithms or changes to the format itself? Because "updates into the standard" sounds like a backwards-incompatible change to ITU-T H.264, which isn't likely to happen.

[raven21]

Efficient in speed or in compression ratio?

Primarily in speed. Improved fast intra prediction algorithm by Liu, Hu, Zhu, Zhang, Han reduces the computation complexity of intra prediction from 52.90% to 56.31%, with 0.04 dB PSNR degradation and 2% increase of bit rate.

Encoder-side algorithms or changes to the format itself? Because "updates into the standard" sounds like a backwards-incompatible change to ITU-T H.264, which isn't likely to happen.

I just want to know are any of these new algorithms going to be used in some h.264 codec and be compatible with other codecs.

[akupenguin]

I don't have the appropriate journal subscription to read Liu's paper (http://www.springerlink.com/content/du84471r79xvp34u/), so maybe they have some new ideas.
I have tried the edge-based algorithm that was included in JM, as described in JVT-N046 (http://ftp3.itu.ch/av-arch/jvt-site/2005_01_HongKong/JVT-N046r1.doc) section 2.1.3.4. (patch for x264 (http://akuvian.org/src/x264/x264_edge_intra.0.diff)). But it turns out that while it works insofar as it doesn't lose much quality, it's not actually any faster than a MMX-optimized naive SATD search. The only reason it improved speed in JM is that the alternative algorithm was inefficiently implemented.
But even if Liu's algorithm is faster, 3% bitrate (which is the equivalent of 2% bitrate + .04 dB) is quite a lot to lose, compared to the relatively small gain you get from RD optimized intra directions in the first place.

I just want to know are any of these new algorithms going to be used in some h.264 codec
Then don't ask about the standard. These are encoder-side algorithms, whereas the standard only specifies what a decoder has to know in order to decode a stream. Fast encoder algorithms aren't in any standard, because they don't need to be.

[raven21]

I don't have the appropriate journal subscription to read Liu's paper (http://www.springerlink.com/content/du84471r79xvp34u/), so maybe they have some new ideas.

I have found it here (http://www.zju.edu.cn/jzus/2006/A06S1/A06S117.pdf), if you want to read it

But even if Liu's algorithm is faster, 3% bitrate (which is the equivalent of 2% bitrate + .04 dB) is quite a lot to lose, compared to the relatively small gain you get from RD optimized intra directions in the first place.

this is interesting to know, thanks.


whereas the standard only specifies what a decoder has to know in order to decode a stream.

and how decoder "knows" if these are new methods? Maybe my first question was wrong, so I want to know if some algorithm is found to be big improvement (apparently this one is not), what is the procedure then?

[Manao]

You have to really make the distinction between encoding decision, and decoding.

The standard set up a certain set of rules. As long as you follow those rules during the encoding stage, you are sure your video will be correctly decoded by a compliant decoder.

Now, the paper you linked to, for example, doesn't change the set of rules. It only changes how the decision is made. Decisions have to be made because the rules leave some leeway. So the decoder doesn't even have to know something has changed in the encoder, since it only cares for the rules.

However, if you were to change the rules themselves ( for example, by introducing a new prediction mode ), you would have to :
1. change the standard
2. update all the decoder to the new standard.

And the decoders not updated wouldn't be able to decode your video, since it wouldn't follow the same set of rules as the encoder anymore.

[raven21]

Very clear. Thanks a lot for simplified answer!!!

[SaadShams]

Very clear. Thanks a lot for simplified answer!!!

If you need further reading from papers/books, find here (http://getonebyone.googlepages.com/media_h264)

[guada2]

:thanks: SaadShams.

Bye.

[akupenguin]

I read Liu's paper. It is very similar to JVT-N046, and since it involves the same edge data it suffers from the same problem. Namely, it doesn't matter how good of a prediction their algorithm makes, because (in a well optimized codec) the time required to compute the prediction is more than the time saved by not evaluating some modes.

[raven21]

I read Liu's paper. It is very similar to JVT-N046

I didn't know that, searching among all that JVT papers is very time consuming, thanks for that information!

the time required to compute the prediction is more than the time saved by not evaluating some modes.

also interesting fact. where is then huge time saving (which they mention)?

[raven21]

If you need further reading from papers/books, find here (http://getonebyone.googlepages.com/media_h264)

Yes, i know about that page, Bond put link in his H.264 FAQ post. But some of the pdf-s I downloaded were broken, especially those I needed (concerning Intra prediction) so I looked somewhere else.

[Episodio1]

I always wondered why those 'engineers' don't add their knowledge to the open source community. Are their works patented by their universities?

[akupenguin]

I guess I'm being a bit harsh on Liu/N046. It is faster than brute-force. But x264's algorithm is simpler, faster, sacrifices less bitrate, and should be obvious.

JM, no RDO:
For each direction of each intra mb type (4 directions of i16x16, 9 directions of i8x8, 9 directions of i4x4, total of 22 modes), compute the SATD score. Keep the mode with the best SATD score.

JM, full RDO:
For each mode, compute the RD score. Keep the mode with the best RD score.

JM, edge-based:
Compute the edge map. Based on the edge data, disqualify some of the modes. For each remaining mode, compute the RD score. Keep the mode with the best RD score.

x264, no RDO:
For each mode, compute the SATD score. Keep the mode with the best SATD score. However, due to the fact that the Hadamard transform is linear and separable, and due to the shape of the intra prediction functions, all of the horizontal, vertical, DC, and plane modes can be merged into one, so it only takes 13 SATDs not 22. (Unlike the other speedups discussed here, this one is not a speed-vs-quality tradeoff, but rather a mathematical identity to get the same result with less arithmetic.)

x264, RDO:
For each mode, compute the SATD score. For each mode whose SATD score is within a certain threshold of the best SATD score, compute the RD score. Keep the mode with the best RD score.

one SATD evaluation costs about 650 cpu cycles.
one RD evaluation costs about 10000 cpu cycles.
the edge-map costs about 6000 cpu cycles.

The edge method skips RD of about half of the intra modes in any macroblock.
x264's method skips RD of about half of the intra modes in I-frames, but skips much more than half in P- and B-frames. Because it includes the inter-predicted macroblock types in the candidates for "best SATD score", quite often the inter modes will be so much better than the intra modes that it can disqualify all the intra modes before computing any RD scores. (btw, x264 uses the same "SATD threshold before RD" method when deciding between the inter modes, and when deciding between motion vectors in RD motion search.)

I always wondered why those 'engineers' don't add their knowledge to the open source community. Are their works patented by their universities?
To be cynical, I'd say it's because the intersection between "people who get papers published" and "people who can write good code" is small. The majority of CS research papers are not practical to implement.

[raven21]

I guess I'm being a bit harsh on Liu/N046. It is faster than brute-force. But x264's algorithm is simpler, faster, sacrifices less bitrate, and should be obvious.

Not to be confused, I am not "fan" of any of these methods, I am just writing about intra coding and improved methods. To be honest, I didn't know all these facts about x264. I have seen codecs comparison which put x264 on top (with Atheme) but your work is hard to follow, cause for amateurs in this you (all) go too deep. So it would be great to have some paper explaining these methods (like this SATD computation) in one place (meaning what options make x264 different and better )
Just a thought. :)

[sunil_bn]

hi can any one implemented any one of the fast intra prediction algorithms, with minimum loss of PSNR and very less increment in bit rate.