Two Ideas for CCE Prediction

vmesquita · #1 03-17-2004, 06:07 PM

Today I had a bit of free time to wonder and had two ideas for CCE prediction, and both could be implemented in DIKO. Here they go:

1) A better mathematical model for CCE QFactor: Right now I am using a linear model. I try Q=1(MIN), Q=40 (MAX), calculate the next Q Factor to try as if the QFactor curve was linear. If the sample is 3% bigger or smaller than the target, prediction is over, otherwise this QFACTOR becomes MIN or MAX (depending if the it was bigger or smaller) and the process starts again. But this leads to the need of 4 or 5 samples sometimes, exactly because linear approach is a bad one. If we could find a function that it's closer (exactly would be impossible), less cycles would be needed. Also CCE doesn't release that much versions as TMPGENC so this would be more viable

2) After finding the right Q Factor, encode again using different scenes (as in ping-pong method) and a larger sample range like 5% ( sampler(length=75) instead of sampler(length=15)):
a) If the result is X% bigger, decrease QFactor by 1,
b) If the result is Y% bigger, decrease QFactor by 2,
c) If the result is X% smaller, increase QFactor by 1,
d) If the result is Y% smaller, increase QFactor by 2,

This are just ideas, I still could not find time to play with it. But to me looks like togheter, prediction would be much more accurate taking about the same time it took before.

EDIT: If anyone wants data to play with, there's this old newbee post here with a excel spreadsheet with Q Factor vs size for a sample he tried. The link is still working: http://fruchtiger.tripod.com/CCE-KDVD_Q1-40.xls
http://www.kvcd.net/forum/viewtopic....r=asc&start=16

vmesquita · #2 03-17-2004, 08:33 PM

Vertical is Size, Horizontal is QFactor. The pink line is the actual size and blue line is the calculated size in the first interaction. So that's why DIKO is taking many predictions cycle before finding the right QFactor. The right QFactor is only found with 1 or 2 cycles (before the initial two with Q1 and Q40) only if the QFactor is next to the borders (38,39,40 or 1,2,3). It would be better to try Factor 20, then try 1 or 40 (depending if the file got bigger or smaller) and use the method described in the previous post from this point on.
Everyone please note: what was said above is intended to make prediction go faster, not make it more precise. To make it more precise, after the right Q Factor is found, it could be fine-tuned using larger samples (3% or 5% instead of 1%). I am still thinking about how this can work.

vmesquita · #3 03-18-2004, 06:40 AM

The first idea is already implemented and working for the next release of DIKO. And results are amazing: ideal Q Factor is found with only 1 cycle after doing MAX and MIN. Only 4 cycles are needed to find the right QFactor if it's between 1 and QMax/2, and 3 cycles if it is between QMax/2 and QMax. Nobody posted here (yet?), but if anyone is interested I can provide a simple how-to describing how to do this manually.

I tested for the QFactor between 1 and 40, I am not sure if it would work for higher QFactors, but I don't recommend using QFactor higher than 40 to prevent bad quality.
Now I am still thinking about how idea 2 can work...

jorel · #4 03-18-2004, 07:02 AM

the "how to" will be cool but....

"only" for D.I.K.O.

ps:
you understand the "only"! (over the over)

vmesquita · #5 03-18-2004, 07:21 AM

No, this can be used manually too.

You must be familiar with the prediction described in my guide. But of course this won't be a problem for you Jorel.

I'll be using QMin=1 (Maximmum quality possible) and QMax=40 (worse quality acceptable)

1) First calculate the idel sample size using the method described in my guide or my calculator.
2) Add the line sampler (length=15) in the end of the script. Encode using CCE at QMax/2, i.e. , Q=20. and write down the size, which will be called Q20_Size. Now do 3A or 3B according to the obtained sample size you got.
3A) If the encoded sample comes bigger than ideal sample size you calculed before, encode at Q=40. The size of the obtained sample will be called Q40Size. The Final Q will be calculed using this formula:

40- ((Ideal_SAMPLE_Size)*40-20)/(Q20_Size-Q40size)

3B) If the encoded sample comes smaller than ideal sample size you calculed before, encode at Q=1. The size of the obtained sample will be called Q1_Size. The final Q will be calculed using this formula:
20- ((Ideal_SAMPLE_Size)*20-1)/(Q1_Size-Q20size)

If you want, you can run one more cycle to check if the calculated QFactor gives a sample that is around 3% the ideal size, but in all 5 tests I did till now, this has always happened.
This way you can find the ideal QFactor in only 2 cycles., if it's between 1 and 40!

Of course, I just invented all this (this idea has less than 24 hours) so it's highly experimental.

Fell free to test.

GFR · #6 03-18-2004, 07:34 AM

vmesquita,

have you tried a Newton-Raphson search instead of a binary search?

r6d2 from doom9 forum has an Excel worksheet to do this, if you want to give it a try.

http://www.geocities.com/r6d2_stuff/

vmesquita · #7 03-18-2004, 07:47 AM

I got this spreadsheet a while ago but didn't understand how to use it.

Anyway, this method I am describing here could look simple and silly, but it has worked in 5 tests.

Of course it's a CCE specific method and the 5 tests is too little to say something, and I also don't know if it's efective in every CCE version since it's based in the graphic shown above. But I am amazed with this possibility of finding the correct QFactor in few steps, and them be able to fine tune using larger samples.
BTW, using larger samples is really efective against undersizing. Look at this test I just did:
Sampler(length=15) ------> Size 23.22 Mb
Sampler(length=60) ------> Size 83,9 Mb (If the proportion was correct it should give 92,88 Mb).
This movie actually gave me a greatly undersized file so that's why I am using it for the tests. The undersize was around 10% and the bigger sample somehow shows it.

EDIT: I am using CCE 2.67.00.09 for this tests.

vmesquita · #8 03-18-2004, 08:47 AM

Using the experimental data New_Bee provided, which may not be that generic but I don't have time to check this now, I came to the following conclusion:

Between 2 and 6, Size decreases about 1.2% every time you lower it
Between 7 and 22, Size decreases about 2.8% every time you lower it
Between 23 and 34, Size decreases about 2.1% every time you lower it
Between 35 and 40, Size decreases about 1.5% every time you lower it

The idea is: after doing the prediction process described in my previous post, create a big sample ( sampler(length=60) ) and use the data above to fine tune the Q Factor avoiding oversized/undersized files. I just implemented this in DIKO (I am starting to find easier to implement and test than test manually

) and I am testing right now. I'll let you know the results.

jorel · #9 03-18-2004, 10:41 AM

i have a new .mpv with 2,23Gb that i did using Q=5 for start the tests!
i did another full encode using Q=1 and the size is 2,53Gb !
another full encode using Q=10 and got ~1,85Gb(was trashed,don't remember the correct size)

(i was testing full encodes with differents Q values,before you post this thread)

have some parameter that you want to test?
i have this new .mpv with 2,23Gb ( Q=5 ) for reference!

GFR · #10 03-18-2004, 12:09 PM

Quote:

Originally Posted by vmesquita

I got this spreadsheet a while ago but didn't understand how to use it.

It is quite straightforward...

Code:

Encoder	1

1=CCE, 2=TMPGEnc

Q Min	1
Q Desired	30
Q Max	60

the above are automatically set when you choose the encoder, but you can change it to suit your preferences. That's the best Q possible, the worst Q acceptable, and an average Q you'd be satisfied with.

Q Error	0,5

Let it at 0,5 if you want to stop when two consecutive iterations give the same Q. If you set at 1 it will stop when two consecutive iterations give Q's 1 unit apart.

BR Error	1,0%

This sets the precision of the prediction. It will stop with a 1% deviation from the optimal value.

CD Size	 800

Here you'll enter the size of the CD or DVD in megabytes. 800 is for a CD.
 
CD Spare Size	 8 

Spare size for subs, security margin etc.

Mux Overhead	1,1%

The mux overhead.

Max SVCD BR	2756

Set at 9000 for a DVD.

Sample Size	1,0%

I type a formula here, = number_of_frames_of_sampler / number_of_frames_of_whole_movie

If you use Sampler(length=15) and the framerate = 23.976fps, that's ~1%
If you use Sampler(length=15) and the framerate = 29.97fps, that's ~0,8%

Audio Size	9%

This value is used to automatically calculate the audio bitrate you use and so how much space is left for the video.

Movie Duration	1:38:00

Target BRs for Video and Audio and Number of CDs
No. of CDs	1	2	3	4	5	6
Needed Total BR	1117	2234	3351	4468	5585	6702
Available Total BR	1117	2234	2756	2756	2756	2756
Resulting Audio BR	96	192	224	224	224	224
Resulting Video BR	1021	2042	2532	2532	2532	2532
Resulting Video Max	2660	2564	2532	2532	2532	2532
Unfilled CDs			3	4	5	6
Fill rate	191%	100%	68%	51%	41%	34%
CD Size needed to fill	1557	817	555	418	336	282
Resulting CDs		2	3	4	5	6


Each column gives the bitrate needed for a given number of CDs (DVDs). We mostly use the 1CD column, sometimes 2Cds.

Look at the line Resulting Audio BR. If you think it's too low or high, change the Audio Size % above.

Chosen values in table above after first Q trial	
	Chosen Target
No. of CDs	2
Target BR	2042


This is the BR you need, automatically calculated from the values you entered. The size of the sample file has also been automatically calculated.


Now you choose which method you'll use (binary, Newton-Raphson or modified N-R). 

Newton's Iteration 2	Q	Q Found	Sample Size	BR	Convergence Function	Error	Q Value
1	30	FALSO	 13.698.522 	1864	-178	-8,7%	0
2	25	FALSO	 14.857.638 	2021	-21	-1,0%	0
3	24	VERDADEIRO	 15.111.312 	2056	14	0,7%	24
4	24	#N/D	 15.111.312 	2056	14	0,7%	0


Look at the first line of the table, that's average CQ you're aiming, let's say 30. Run the avs with sampler with CCE @ CQ=30. Now look at the size of the mpv (13.698.522) and type it in the table. 

Now look at the next line, its CQ has changed automatically. Run CCE with this CQ (let's say 25). Type the size of the mpv (14.857.638).

Now the CQ of the next line has automatically changed, use this new CQ (24). Type the mpv size, it's OK, QFOUND turns TRUE. If not, the next line has a new CQ for you to try, and so on until it's OK.

If you look at the formula in the CQ cells you get the formula for the N-R search that you can use in your own program.

=SE(F69=F68;NÃO.DISP();MÁXIMO(ARRED(B69-(B69-B68)/(F69-F68)*F69;0);Q_Min))

This is the main part of the equation:

B69-(B69-B68)/(F69-F68)*F69

translated:

Q - (Q - lastQ) / (error - last_error) * error


Unless you need a very low CQ like CQ<10 it converges in 3-4 iterations. For this example, the binary search would take 6 iterations.

PS binary search formula:

=ARRED(MÉDIA(I81;J81);0)

MÉDIA(QMIN;QMAX); where QMAX, QMIN are updated at each iteration (if the sample was too big, QMIN:=Q, if the sample was too small, QMAX:=Q - that's for CCE, size decreases with Q).

Another link

http://www.angelfire.com/droid/r6d2/

vmesquita · #11 03-18-2004, 06:21 PM

Quote:

Originally Posted by GFR

Unless you need a very low CQ like CQ<10 it converges in 3-4 iterations. For this example, the binary search would take 6 iterations. "

You see, this method I am developing (idea 1) only requires 2 interactions to find the Q corresponding to the sample size.

If you look in the graph, the size for a Qfactor between 1 and 20 approaches a straight line, and between 20 and 40 aproaches another. It's simple like that.

Actually, I was thinking of a improved version, since only two cycles are actually needed, this cycles can be done using larger samples, making prediction as accurate as you want. I rewrote the mini-how-to. Jorel, if you have the time, please test this.

1) First calculate the idel sample size using the method described in my guide or my calculator. Multiply by 4.
2) Add the line sampler (length=60) in the end of the script. Encode using CCE at QMax/2, i.e. , Q=20. and write down the size, which will be called Q20_Size. Now do 3A or 3B according to the obtained sample size you got.
3A) If the encoded sample comes bigger than ideal sample size you calculed before, encode at Q=40. The size of the obtained sample will be called Q40Size. The Final Q will be calculed using this formula:

40- ((Ideal_SAMPLE_Size)*40-20)/(Q20_Size-Q40size)

3B) If the encoded sample comes smaller than ideal sample size you calculed before, encode at Q=1. The size of the obtained sample will be called Q1_Size. The final Q will be calculed using this formula:
20- ((Ideal_SAMPLE_Size)*20-1)/(Q1_Size-Q20size)

If you want, you can run one more cycle to check if the calculated QFactor gives a sample that is around 3% the ideal size.

This way you can find the ideal QFactor in only 2 cycles., if it's between 1 and 40!

bman · #12 03-19-2004, 06:22 AM

@ vmesquita
I didn't tested your method yet but decided to give u some ( maybe useful ) info

I'm using manual prediction method with CCE 2.66 and result is

Judge yourself :
With sampler(length=75) as Jorel found and reported while ago in another thread , predicted size - 4043 mb and resulted - 4024 mb

Only 19mb diff on ~4Gb file !?

I like very much your scintific aproach with whole math calcs around the subject Guys ( vmesquita and gfr too ) .

Maybe my small experience can help in here maybe not , worth to try !

What I'm doing is much simpler (PAL & NTSC movies )-
Wanted size for DVD is ~3700mb if I'm using AC3 original sound and ~3900 if I'm using MP2 224-128kbps .
If u run CCE 2.66 just 20-25% from whole clip with sampler(len=75) result u'll get be very close to the whole samle size . So if sample takes ~5-6 minutes with len=75 then just in 1.5-2 min u have first pass ?!
and so on till u get close enough to desired file size .
Then u encode whole samle ( just to be sure )
It works for me quite well but what I always wanted not to make this manually ( and not to be stacked to pc )
I'll be glad if enyone'll find this info useful
bman

jorel · #13 03-19-2004, 06:51 AM

hey bman,
i was waiting the vmesquita results but ....

edited>
.....better is still waiting!

bman · #14 03-19-2004, 07:40 AM

Quote:

Originally Posted by jorel

hey bman,
i was waiting the vmesquita results but i can't resist:

see how i search my prediction for CCE CBR encodes:

TNT - AS / FT = SOS

TNT - Total Needed Target (size of dvd (- 100mb))
AS - Audio Size(s) (all audios together)
FT - Full time (in minutes)
SOS- Size Of Sample

encode with Q=x to find the SOS!

Jorel
Sorry but it's easier if u devide needed file size on 20 in case of sampler(len=75) for PAL and sampler(len=72) for NTSC that is GOP*3 as u yourself suggested some time ago (with sampler(len=25) I devide on 60 ) .
Anyway subject for me is how to make prediction With CCE automated not how we find needed sample size that we already learned to do some time ago

bman

jorel · #15 03-19-2004, 08:14 AM

edited>

jorel · #16 03-19-2004, 08:39 AM

vmesquita,
i'm still waiting your results!

i did another full encode using Q=20 and got 1,55GB !

bman · #17 03-19-2004, 08:49 AM

Ok ' Lets make some order in here

When i sayd "u yourself suggested some time ago " I maent => sampler(len=75) for PAL and sampler(len=72) for NTSC that is GOP*3 and that was in TMPG prediction thread .
Sampler length of 3 GOP's for prediction is very accurate and I'm happy with results .
U just make your avs script with sampler length of 75, load to CCE and encode just 25% - ~2min to encode and result multiply on 4 and on 20 and that's your final file size .
Try this and tell me your results .
Now I'm living my office and going back home so in a 1hr or so I'll be with u to see your results if u'll make test

bman

GFR · #18 03-19-2004, 08:52 AM

Quote:

Originally Posted by vmesquita

You see, this method I am developing (idea 1) only requires 2 interactions to find the Q corresponding to the sample size.

If you look in the graph, the size for a Qfactor between 1 and 20 approaches a straight line, and between 20 and 40 aproaches another. It's simple like that.

And a 3rd iteration to verify that your calculated CQ is OK. We're tied

The method in the spreadsheet is exactly the same, only the chosen points are different. If you look at the example in the spreadsheet, he makes two iterations, CQ1=30 , CQ2=16 (or CQ2=25 in the modified case), assumes it's a straight line from 16-30 (25-30) and calculates CQ=25 (CQ=24). If you run 3rd iteration and the error is too big you can "narrow" the range that is considered a line and so on.

To run your method in the spreadsheet, type 20 instead of 30 in the Q Desired field. Then choose the table Newton's Iteration 1 and instead of the "11" that it puts automatically in the second line, you put 1 or 40, according to your rule. The 3rd line in the table gives you the CQ.

You can increase the accuracy with some "educated guesses". Like, let's say, you're encoding a movie, and you know from experience that for the length of this movie, with this level of action, there's no way you can go below CQ=10, so you can use CQ=10 instead of CQ=1 in your method. If you guessed right, and the actual needed CQ is 10<CQ<20, so the line from 10-20 should be closer to the curve than the line from 1-20, and your error should be smaller.

The spreadsheet tries to make these guesses automatically that's how the second line in the tables are filled.

GFR · #19 03-19-2004, 08:55 AM

Quote:

Originally Posted by vmesquita

If you want, you can run one more cycle to check if the calculated QFactor gives a sample that is around 3% the ideal size.

This way you can find the ideal QFactor in only 2 cycles., if it's between 1 and 40!

Also, in the spreadsheet, change BR Error to 3%. The number of iterations I mentioned were for 1%.

vmesquita · #20 03-19-2004, 09:05 AM

@GFR
Ok, now I understood how it works.

And it's really very similar.

But the interation to confirm is dispensable for a 3% accuracy according to my tests.

The idea2 is after finding this Q using the method above, do a one time big sample (about 5%) and fine-tune using a variation table. I implemented this in DIKO and tested with a encode that previously gave me 250 Mb undersize, and got 40 Mb undersize fine tuning using idea2 (much better). I can post the variation table later if you're interested to play with.
But maybe it makes more sense to do prediction using 2 cycles of big samples (4%) and skip the confirmation cycle. I am still thinking how it can work, since there's one more limitation: DIKO has always to do a cycle using QMax to check if it's possible to get the footage in the media.

EDIT: I think a 1% accuracy is overkill because of the flutuations of the resulting filesize...