The new B-frame decision (--bframes 16 and you)

[Dark Shikari]

One of the GSOC projects for the summer was to improve B-frame decision. This was the most important project, IMO... but the student on the task just disappeared after the first week.

So I decided to do his job for him, and with akupenguin's assistance on the algorithm side of things, spent this week writing an optimal trellis-like function for B-frame decision. This algorithm provides perfect B-frame decision--or more precisely, as perfect as one can get with the current cost approximation function used.

The downside is that its a bit slower, and moreover, its speed scales linearly with --bframes. While with the previous algorithm, --bframes 16 was only minimally slower than --bframes 3, here it will be a lot slower. And this new algorithm is going to be default, since it is considerably better. The old algorithm will still be available for those who need a fast but inaccurate B-frame decision method.

So, this is a warning to all those who use --bframes 16, MeGUI and otherwise; the new B-frame decision is coming soon, and when it does, in the interests of speed you may want to lower the --bframes value to 3-5 or something otherwise reasonable.

[LoRd_MuldeR]

Thanks for the info, looking forward :thanks:

BTW: Will this be available as another patch or will it be released directly in the git?

[Dark Shikari]

Thanks for the info, looking forward :thanks:

BTW: Will this be available as another patch or will it be released directly in the git?Almost certainly direct when I feel that it has been sufficiently tested. This one's easy to test, since I can just test raw PSNR (unlike psy optimizations).

[gav1577]

Well done Dark Shikari & akupenguin your work is always appreciated keep up the good work :thanks:

[Ranguvar]

Fantastic :D

I can't wait until this comes out; I've been looking forward to it since I heard it was a GSoC project.

Great work, Shikari and aku, as always! :)

[Sharktooth]

One of the GSOC projects for the summer was to improve B-frame decision. This was the most important project, IMO... but the student on the task just disappeared after the first week.

So I decided to do his job for him, and with akupenguin's assistance on the algorithm side of things, spent this week writing an optimal trellis-like function for B-frame decision. This algorithm provides perfect B-frame decision--or more precisely, as perfect as one can get with the current cost approximation function used.

The downside is that its a bit slower, and moreover, its speed scales linearly with --bframes. While with the previous algorithm, --bframes 16 was only minimally slower than --bframes 3, here it will be a lot slower. And this new algorithm is going to be default, since it is considerably better. The old algorithm will still be available for those who need a fast but inaccurate B-frame decision method.

So, this is a warning to all those who use --bframes 16, MeGUI and otherwise; the new B-frame decision is coming soon, and when it does, in the interests of speed you may want to lower the --bframes value to 3-5 or something otherwise reasonable.
Dont worry, MeGUI presets with 16 b-frames (except the insane presets) will be updated as soon as i see that commit in x264 git changelog, also the Devices, Standalones, DXVA presets have already a limited number of b-frames.
thanks for informing us.
can you tell us what will be the x264 option to select the old decision mode (so i can start implementing in megui)?

EDIT: I've just updated the new x264 presets for MeGUI...

[Dark Shikari]

Dont worry, MeGUI presets with 16 b-frames (except the insane presets) will be updated as soon as i see that commit in x264 git changelog, also the Devices, Standalones, DXVA presets have already a limited number of b-frames.
thanks for informing us.
can you tell us what will be the x264 option to select the old decision mode (so i can start implementing in megui)?--b-adapt will be the option, and 0 will be the same as --no-b-adapt, 1 will be the old method, 2 will be the new method.

--no-b-adapt will still exist for legacy compatibility.

[Sharktooth]

ok. is it worth keeping the old method?

[Dark Shikari]

ok. is it worth keeping the old method?If you want very fast encoding, the old method is probably still useful for that purpose. The new method has a significant speed penalty, albeit only on the first pass.

From my testing so far, the new B-frame decision gives about 3% more efficient encoding overall and 15% or more improvement in cases with lots and lots of fades.

[Sharktooth]

well, for very fast encoding we have presets with 0 or 1 b-frames... (like --crf 22 --bframes 1 --nf --no-cabac --subme 1 --partitions none --me dia --threads auto --thread-input --progress --no-psnr --no-ssim)
if you want uber speed i dont think quality/compression is so important... also almost all multipass presets include a fast first pass...

[Dark Shikari]

well, for very fast encoding we have presets with 0 or 1 b-frames...With the old B-frame algorithm, fewer B-frames are not necessarily faster. Zero is almost always faster than 1 or more, but 1 is not necessarily faster than 3.
if you want uber speed i dont think quality is so important... also almost all presets include a fast first pass...My point being that this will slow down that fast first pass a good bit ;)

[Sharktooth]

edited my previous post.
however, the idea is if you want fast encoding, you wont run multiple passes...

[Dark Shikari]

edited my previous post.
however, the idea is if you want fast encoding, you wont run multiple passes...A one-pass encode counts as a "first-pass" for purposes of being slowed down by B-frame decision.

[Sharktooth]

yep. in any case, you have to choose, speed or compression/quality.
with current HW, speed is becoming less important.

[Avenger007]

Deos this new algorithm improve b-pyramid as well?
Is the number of consecutive b-frames generally going to increase when compared with the old algorithm? The old algorithm almost never used more than 4 consecutive b-frames.

[Dark Shikari]

Deos this new algorithm improve b-pyramid as well?The new algorithm does have pyramid-specific code, so it should. It doesn't have any code for deciding between pyramid and non-pyramid though; pyramid is still forced by x264; it just takes pyramid into account when deciding number of B-frames.

Is the number of consecutive b-frames generally going to increase when compared with the old algorithm? The old algorithm almost never used more than 4 consecutive b-frames.That's because more than 4 is almost never useful ;)

I've found generally that the new algorithm, without pyramid, may raise or lower number of B-frames. With pyramid, it generally raises the number.

[cogman]

So, will the improvement of bframe 16 be pretty much non-existent over say bframe 6? I guess I'm just wondering if this will make bframes similar to the way reference frames are now (IE, 16 refs may give some imperceivable improvement but you are fine with far fewer).

Though, My quad is hungry, so I probably won't change my encoding settings :D

[Soichiro]

Unlike in live-action, where more than 3-4 bframes are rarely placed in a sequence, more than 4 bframes is very useful in animated sources. Previously, my testing showed that increasing bframes from 6 to 16 provided a 10% speed hit, but a fairly large quality boost on an animated test clip (much better than increasing ref frames, which costs much more speed). However, I'm wondering just how much of a speed hit this new method will cause, and if it will still be worth it...

[Comatose]

Me too... my encodes are already super slow, I'm not sure I want it to be a ton slower for only a slight improvement in quality :\
I guess I'll have to try it for myself to decide if it's worth it x_x

[Soichiro]

I did some test encodes.

http://kuroha.no-ip.org/New%20BFrame%20Test.mkv
http://kuroha.no-ip.org/Old%20BFrame%20Test.mkv

And the logfile: http://kuroha.no-ip.org/Stats.txt

(and stats files for those who want them: http://kuroha.no-ip.org/oldmethod.txt & http://kuroha.no-ip.org/newmethod.txt)

2nd pass encodes were nearly the same speed, but the first pass with the new bframe method was over 50% slower, and the thing that concerns me is that the new method actually creates a slightly worse PSNR and SSIM. The new method also seems to favor b-frames a lot more, but in a pattern that strikes me as a bit odd, with 20% of bframes being located in 15-frame sequences.

(Unrelated, but I totally need to edit that kara. Good thing I used this as a test encode <_<;; )

Edit: After watching through both encodes, I'd have to say that, without any careful comparison, the new b-frame system seems to look a bit better, despite the PSNR and SSIM.

[Dark Shikari]

This is one reason I'm not releasing it officially yet--there may still be some kinks to work out ;) In particular, I'm not entirely sure whether the method I used for B-pyramid heuristic is going to be problematic or not.

The only case I have found where the new algorithm is worse than the old algorithm is the case where you have a bunch of frames that are nearly 100% I-blocks, and not because of a fade. A couple scenes in "300" do this. This is a flaw in the cost algorithm, not really in the decision method.

Try without b-pyramid to see if the pyramid heuristic is the problem--since I haven't tested that as much.

My own tests show about a 0.15db improvement on everything, PSNR-wise, and about a 0.75db improvement on an animated clip with lots of fades. The extreme clip from "300" lost about 0.2db PSNR.

Edit: I already may have found a rather nasty bug in it, so don't complain just yet ;)

[iwod]

So you have just done what was suppose to be a whole summer of work in one week of your spare time?? :D

[Dark Shikari]

So you have just done what was suppose to be a whole summer of work in one week of your spare time?? :DEh, the project was supposed to cover a lot more than what I did (pyramid vs non-pyramid decision, better frametype cost function, multi-level b-pyramid, opengop, etc).

[burfadel]

As stated with psy-RDO etc etc, what looks better is more important than SSIM and PSNR, as they are not entirely accurate. Afterall, isn't it a measurement of the differences between the original and encoded, with a higher score for less difference? Now the differences for the old method may be slighly less, but the difference in the differences may be a lot more for the old method. That would mean the new method would look better...?

[Dark Shikari]

As stated with psy-RDO etc etc, what looks better is more important than SSIM and PSNR, as they are not entirely accurate. Afterall, isn't it a measurement of the differences between the original and encoded, with a higher score for less difference? Now the differences for the old method may be slighly less, but the difference in the differences may be a lot more for the old method. That would mean the new method would look better...?For everything other than psy optimizations, one has to make the assumption that a given change will not have a signiificant psychovisual impact--and therefore that one can use PSNR when optimizing the feature. Otherwise its too difficult to try to improve non-psy optimizations.

[burfadel]

I think I might have added my last post on the wrong thread :) oops! well, that's easy enough I guess with multiple similar tabs open!

Anyways, I was going to ask, is the slowdown and benefit of higher b-frames similar to that of with reference frames? Also, with psy-rdo I'm guessing the new decision mode may even show more gains, due to the nature of psy-rdo? I know they're not exactly related, but since psy-rdo changes the image in a particular manner the b-frame decision may be changed?... :)

[Dark Shikari]

It seems the new algorithm's slowness has drastically aggravated the threading problem with fast firstpass + b-adapt... I'm reconsidering making it default. I may wait until threaded slicetype decision is done before making it default.

[burfadel]

It seems the new algorithm's slowness has drastically aggravated the threading problem with fast firstpass + b-adapt... I'm reconsidering making it default. I may wait until threaded slicetype decision is done before making it default.

Does this affect CRF mode though? it could be made default for CRF but optional for multiple passes (such that CRF just implies that it is enabled).

[Dark Shikari]

Does this affect CRF mode though? it could be made default for CRF but optional for multiple passes (such that CRF just implies that it is enabled).Its just as bad in CRF--its just that in CRF, people normally use slower settings, while in the first pass of a 2pass encode, they use fast settings.

Anything that causes threading issues is going to be less problematic at slower setting levels.

[guada2]

@Dark Shikari

A small question:
Which is the adjustment of reference of this codec for multipass mode(1+2) at High bitrate and ultra low bitrate?

[vmrsss]

Hi Dark Shikari, and thanks for the good work.

(1) If the new algorithm scales linearly with the --bframes parameter, and we know that the final number of consecutive B frames varies a lot with the kind of source, it'll be useful to have a rule of thumb to decide what --bframes to use for each encode rather than going straight to --bframes 16. Or is it that the speed depends not on the parameter but on the number of consecutive B frames actually allocated during the encoding?

(2) Are the key aspect of the new algorithm described somewhere?

best

[akupenguin]

Actually cost scales with the square of max-B-frames, so you really don't want to use 16. We have discussed an optimization which could reduce it to linear, but that's not implemented yet.
If the new algorithm scales linearly with the --bframes parameter, and we know that the final number of consecutive B frames varies a lot with the kind of source, it'll be useful to have a rule of thumb to decide what --bframes to use for each encode rather than going straight to --bframes 16.
1) I just added a line to the stats summary you get at the end of every encode, so try out the algorithm and see how many you get.
2) If you don't have a good reason to think otherwise, 3 is a good number.
3) We will probably eventually add some heuristics to speed up trellis, but that comes after the generically optimal case.
Are the key aspect of the new algorithm described somewhere?
Good question. It wouldn't make sense to explain this instance of the algorithm in isolation (Trellis can be used for lots of things, and instantiating it only for frame types obscures the real structure), but I have wondered about a good introduction of Trellis to point people to. I personally consider it just a special case of Dijkstra's algorithm, but that probably doesn't help, because if you knew Dijkstra's shortest path algorithm this wouldn't need explaining.

[vmrsss]

2) If you don't have a good reason to think otherwise, 3 is a good number.

Ah, quite a few fewer than I expected...

3) We will probably eventually add some heuristics to speed up trellis, but that comes after the generically optimal case.

Hmm, so the new algorithm is an instance/variation of trellis? (Sorry if the question is dumb.) Sometimes you read trellis is not recommended with --crf (which is what i use most of the times), does this change with the new algorithm?

I have wondered about a good introduction of Trellis to point people to. I personally consider it just a special case of Dijkstra's algorithm, but that probably doesn't help, because if you knew Dijkstra's algorithm this wouldn't need explaining.

On the contrary, maybe I don't know which of Dijkstra's algorithms you're referring to and a general explanation of the context an specifics of the problems, together with a pointer to Dijkstra would be exactly sufficient.

[akupenguin]

Hmm, so the new algorithm is an instance/variation of trellis?
Trellis is exactly the same as trellis. It just so happens that "trellis quantization" was implemented before "trellis frametype decision", so the former got abbreviated.

Sometimes you read trellis is not recommended with --crf (which is what i use most of the times), does this change with the new algorithm?
That misconception has somehow persisted since long ago when XviD's implementation of trellis quantization had a bug. I have attempted to purge it from the internet, but of course that's impossible; I can only edit wikis, not individual people's memory.

On the contrary, maybe I don't know which of Dijkstra's algorithms you're referring to and a general explanation of the context an specifics of the problems, together with a pointer to Dijkstra would be exactly sufficient.

Dijkstra's shortest path algorithm. (http://en.wikipedia.org/wiki/Dijkstra's_algorithm)
We want to find a sequence of frame types (or DCT coefficient values, or other decisions) to minimize their total cost. (We of course have to measure cost somehow, so when I say the solution is optimal, I only mean with respect to the particular metric I picked.) The cost of each frametype at each position depends not only on the pixel content of that frame, but also on the types of the neighboring frames, but the amount of such history that's relevant can be condensed into a rather small context (in particular, just name which frames this one is predicted from).
So we construct a weighted directed graph. Each vertex represents a P-frame. Each edge represents an encoding of the destination P-frame predicted from the source P-frame. The weight of an edge is the cost of that encoding of that P-frame plus the costs of that encoding of all intervening B-frames.
Then we ask Dijkstra to find the path from start to end with the lowest cost.
The special case part is that we never really construct a graph, just do all the comparisons in the shortest path algorithm implicitly, and some can be reordered for convenience, and all array sizes are small and known in advance.

[Dark Shikari]

Simple explanation of algorithm using an example:

In this example, Max B-frames is 2. All paths must end with a P-frame.

Path length of 1 gives us P as our best path.

Path length of 2 gives us BP and _P. "_" is the best path of length 1.
This gives us BP and PP. Now, we calculate the actual costs.
Let's say, for the sake of this example, that BP is best.

Path length of 3 gives us BBP and _BP and __P. "__" is the best path of length 2.
This gives us BBP and PBP and BPP. Now, we calculate the actual costs.
Let's say, for the sake of this example, that BBP is best.

Path length of 4 gives us _BBP and __BP and ___P. "___" is the best path of length 3.
This gives us PBBP and BPBP and BBPP. Now, we calculate the actual costs.
Let's say, for the sake of this example, that BPBP is best.

Path length of 4 gives us __BBP and ___BP and ____P. "____" is the best path of length 4.
This gives us BPBBP and BBPBP and BPBPP.

Now--wait a minute--all of the paths agree that the first frame is a B! So the first frame is a B.

Process is repeated until they agree on a P-frame, and then encoding starts.

(Note: current algorithm does not actually use the "agreeing" method--instead it just goes for quite some distance into the future and uses the longest path as the tie-break.)

[LoRd_MuldeR]

This somehow reminds me of the "Knapsack problem" ;)

[lexor]

This somehow reminds me of the "Knapsack problem" ;)

I hope not, that sucker is NP-complete. If they were alike, we'd be paying way more than linear time per b-frame.

[Dark Shikari]

I hope not, that sucker is NP-complete. If they were alike, we'd be paying way more than linear time per b-frame.Yup, this problem appears NP-complete at first-glance, but in reality is just linear-time if you dynamic-program it.

[Inventive Software]

This might sound daft, but in the past with a 2-pass encode, I use the same number of B-frames in both passes because that way the stats file might be of some use in this. Does this now make more sense with the new algo?

[Dark Shikari]

This might sound daft, but in the past with a 2-pass encode, I use the same number of B-frames in both passes because that way the stats file might be of some use in this. Does this now make more sense with the new algo?You have to use the same number of B-frames on both passes--the B-frame decision isn't done in the second pass, its re-used from the first.

[skystrife]

Interesting development, not sure if anyone else has this problem.

When running my own patched build + the new bframe decision patch I don't achieve 100% cpu usage (I get about 25%-ish on 4 cores) as opposed to 100% on 4 cores with the patched build without the new bframe decision. Is this to be expected or is something borking in the threading department with the new bframe decision method?

[LoRd_MuldeR]

This might be because the frametype-decision, which is not multi-threaded yet, becomes the bottleneck?

BTW: Where can I get that patch? :)

[Audionut]

Current patches thread of course. ;)

[LoRd_MuldeR]

I don't think the new improved b-frame decision has been posted as a patch yet. If I'm mistaken, please point me to that post...

[skystrife]

I don't think the new improved b-frame decision has been posted as a patch yet. If I'm mistaken, please point me to that post...

http://forum.doom9.org/showthread.php?p=1163095#post1163095

[LoRd_MuldeR]

Ehm? I think this link is either broken or the patch has been removed :confused:

http://pastebin.com/d495ce2e

[Dark Shikari]

I set it up for only a day for a reason :p

Here's the latest version (http://pastebin.com/f75a7283), which reverts to --b-adapt 1 as the default.

[LoRd_MuldeR]

I set it up for only a day for a reason :p

Here's the latest version (http://pastebin.com/f75a7283), which reverts to --b-adapt 1 as the default.

Thank you, Sir.

[foxyshadis]

Interesting development, not sure if anyone else has this problem.

When running my own patched build + the new bframe decision patch I don't achieve 100% cpu usage (I get about 25%-ish on 4 cores) as opposed to 100% on 4 cores with the patched build without the new bframe decision. Is this to be expected or is something borking in the threading department with the new bframe decision method?

And you definitely have pthreads compiled in?

[skystrife]

Yes, pthreads is compiled in. The same build environment was used for both the new bframes decision build and the old bframes decision build.