HCShredder - the guided CQ encoding frontend for HCEnc

[mikneadia]

[1st: Let´s make shure we do not mix up HCPredictor and HCShredder
HCPredictor = OPV / CQ sizeprediction based tool similar to D2SRoBa for CCE/DVDSVCD
HCShredder = Segmented encoding with CQ prediction for the start Q-value

I got it. Can a mod move the post to the appropriate thread. Thx .

What do you mean by opposite sign ?

My english is bad too. I took the term from the Wiki page because it is a root-finding algorithm.
I meant that I have a value that is undersizing and the other is oversizing . The zeros of the function Q vs (Size - S(desired)).
We can plot Log(Size/S(desired)) vs Q. It is easier for me to express myself (bad english) using that misleading analogy

[mikneadia]

Hi, D$

But we will have imperfect information ( on 20 % of the movie) that we may take advantage of. We compute incorrectly the initial Q ( similar to an estimate of the average) but we may gather information that will impact your algorithm ( how to encode segment (N+1) ) , one speed chase in the movie or the "action" in the movie being mostly constant...

We are accumulating a lot of information during the intial phase (CQ based on sample) and during the encode ( we should try to take advantage of all the information and then "clamp" should be a complex function (depending upon a lot of parameters).
Let me try to be clearer. Instead of predicting many future events  at a given time (which is the case if "clamp" is fixed,for ex) we should predict only one event a time ("clamp" for Next segment only , gather additionnal information based on the encode of segment (N),update it (combined with information previously gathered...). Same concept in analyzing 5 1% samples instead of a 5 % sample.
Idem for decision process (for ex, the predictive method decision (bisection or else) should be taken at the last minute, before each encode, based on all information previously gathered.We should have as many InitialValues in the INI file as possible, that are updated often(this will also make InitialValues much less critical for the end result).

[mikneadia]

I am assuming that the following assumption is more or less true (All the Error*(b) only depends upon b (not the source)).
 Because we are plotting Log(S/Sd) vs Q , we segment the interval definition of (S/Sd) in equal interval (geometric mean starting at 1/2, finishing at 2 for ex). Defining the interval definition of(S/Sd) is very important.I don't know if it is source-type dependent (DVD, capture...) but it has to be as small as possible. We have to be sure (100% sure) that will be able to make a first guess estimate (even if it is your Q=8 stating value) that is in that interval. Inside each sub-interval,we regroup some data in "Sets of information" (S/Sd before prediction, Q before prediction, prediction strategy 1, prediction strategy 2,Qopt(after many iterations)).
Error1=(5)-(3); Error2=(5)-(4) ; (5) being the 5th information in the "Set of information".
We compute the STD , the mean,the inferior estimate (mean-2*STD)or else) and the superior estimate ((mean+2*STD)or else) of Error1 and Error2 (not too much dispersion, I hope!). Those functions are staircase lookalike.
We try to find c such as Error1(b)< Error2(b) for b<c.

Some results
The assumption "(All the Error*(b) only depends upon b (not the source))" is definitely not true, unfortunately.
But I found consistently enough, on DVD progressive sources,
a) that bisection and predictive mode were predicting more or less the same thing when they were oversized (the last iteration produce a size that was above the desired size) .
b) that predictive mode was making a better prediction when they were undersized and in that case, both methods were consistently overshooting (predictive modeless than bisection).
c) I found an empirical formula (trial and error) that seems to work better than bisection and predictive mode 2 around the optimum (to increase convergence).
The formula is aimed when a=S(N)/S(desired) is between 0.9 and 1.2
Q(N+1)=Q(N)*(1+bLog(a)) where b=1+2(a-1) ; any function with f(1)=1 is a candidate for b.
Conclusions: It seems that the above formula (if proven consistent across sources: Sorry. I do not have enough DVD!) and also the other two interpolations methods (not enough DVD, too!) do a better job when a>1 ( as well as the fact that 1.2>1/0.9). An initial Q estimate that overestimates size might be a better choice. Still a lot of work left for those who have a lot of DVDs and are interested by interpolation (I think that the above formula shows it might pay off and that was done quick and dirty with a small sample of DVD so a lot of room left for improvment).
A function based on trial and error and having different definitions depending on "S(N)/S(desired)"  might do a better job than standard interpolation method (used to interpolate any function) for the only function we want to interpolate (Q vs Size). Did not get too many followers on that path (neither detractors, so...)

[Darksoul71]

Hi,

sorry for my late reply. I was away for
the weekend and quite busy yesterday.

I think I should elaborate a few things:
The two algorithms which are available are only used in the prediction phase.

Prediction phase here means:
I try to find out (based on a 1% sample for the whole movie) which quantiser
I have to use to meet the target size.

To say it more mathematical:
S = f(Q)

S = our target size
f = some function we don´t know which essentially discribes the movie (e.g. complexity, compressibility)
Q = quantizer used to encode the movie

If we know f, we could easily solve the equation -> no size prediction neccessary
Since we do not know f, we have to go the empirical approach to find out what
value (= size) f(Q) produces.

Q(n+1) is of course calculated based on Q(n).

For the first run we do not have Q(n). So we have to look
out for a start value.

When using bisection as algorithm, the normal start value
would be the middle of both borders (31-1) / 2 = 15.

Taking into account that we´ll most likely have smaller
values than 15 for the final Q, we can savely set the
start Q to 8 (or something like that). Essentially this
simply makes the next interval smaller when the start
Q is choosen smartly but also can enlarge the interval
if choosen badly.

For me a smartly choosen starting Q (based on your experiences)
is what I would call an educated guess. Someone may correct me
if I understand this term wrong.

I´ll try to outline this:
The "dumb" approach to choose a start value for bisection
would be the middle of both borders. The borders for the
quantiser used in HCEnc are 1 and 31.

So we would end up with 15 as start value (as stated above).

It´s smarter, but requires some experiences around what your
CQ encoded movies usually come out, to choose a Q-value as
start which is close to your "standard Q".

Example:
For me almost 99% of all movies have had no higher Q-value
than 5 meeting their target size. In this case I would set
6 as start value. The start Q is either the upper border
(if choosen smartly) or the lower border (if choosen badly)
for the next bisection interval.

So an interval of 1-6 would be much better than 1-15,
whereas an interval of 6-31 would be much worse than
15-31.

Since I do not know which target quantizer the user
normally has, I can only leave him the option to finetune
this value.

Other parameters such as acceptable size and quantizer
deviation plus quantizer precision have an impact on
the numbers of runs as well.

All I can say here:
Bisection (even at high precision and a dumb starting Q)
will most likely hit the target size at max. 6 runs.
This still saves us 94% runtime when using 1% sample
compared to normal 2 pass mode.

Bisection always converges

At least when using limited precision for the quantiser.

Using my "condensed" Newton Raphson algorithm also will
work in most of the cases but sometimes diverges or
"jumps" left and right from the best solution.

Big advantage: Prediction is faster

To me it boils down to this:
Investing a lot of time for CQ prediction makes no
real sense just in order to save 1-2% runtime.

The formula is aimed when a=S(N)/S(desired) is between 0.9 and 1.2
Q(N+1)=Q(N)*(1+bLog(a)) where b=1+2(a-1) ; any function with f(1)=1 is a candidate for b.

This would indicate that I have to use different formulas
depending on the size of a. Hm, might be a valuable
approach but currently I´m fine with the two choices
between stable and slow or potentially unstable and fast.

Just as sidenote:
You indicated that RB-Opt somehow uses a 2pass CQ prediction.
Can you please give more details on this ?

After the initial prediction I encode the first segment
with the calculated Q. Now Q(n+1) is directly calculated
based on the deviation between target size of the segment
and real size. This is of course similar to the "unstable"
formula I use for CQ prediction but other than in CQ
prediction I do no "regression". I simply use the ratio
of the size (similar to your a) as correction factor.

We are accumulating a lot of information during the intial phase
(CQ based on sample) and during the encode ( we should try to take
advantage of all the information and then "clamp" should be a complex
function (depending upon a lot of parameters).

Hm, I have to disagree. We do not collect a lot of informations
during the first few CQ prediction runs. While the encoder of course
will see the action / complexity of each scene distributed over the
whole movie, the result will always be an average. The only informations
we have:
Filesize of 1% samples for a certain quantizer. This might give us
a graph but I´m unsure what to do with this graph

The quantiser we find is already quite close to the "optimal"
quantiser which we have to use to hit the target size precisely.
With some very small adjustments will most likely hit the
target size perfectly.

The clamp function itself is just a workaround to avoid too
massive changes in regard to the quantizer.

To my understanding the only true approach for "guided" CQ is
the adjustment of the found quantiser based on the compression
curve of the movie and the already used size. In other words:
Only perfectly possible when integrated into HCEnc.

The biggest disadvantage in my / manolitos method:
We post-react / correct......

The quantizer is rised after a segment was undersized.
The quantizer is lowered after a segment was oversized.

I´m now thinking about build a rough "compressibility curve"
similar to the ABD (= adaptive bitrate distribution) feature
of QuEnc^n.

Have a look here for details:
http://forum.doom9.org/showpost.php?p=829350&postcount=33

The same could work for HCShredder like this:
1) Do CQ prediction for 1% of the complete movie
2) Do a CQ encoding with Q=1 for 1% of each segment
3) Get the size for each 1% segment encoding
4) Calculate the average size of the Q=1 encodings
5) Calculate the deviation in % based on the average size of
   step 4 for each segment (similar to ADB)
6) Correct the CQ from step 1 for each segment based on
   the deviation calculated in step 5

This way we would take the action level per segment
into account prior any encoding taking place. The
speed penalty is negligible since we talk about 1%
of 10% (=0.1%).

What do you think ?

The assumption "(All the Error*(b) only depends upon b (not the source))" is definitely not true, unfortunately.

Well, unfortunately we do not have a source independent correction factor.
That´s what I found out during my experients where I analyzed the size deviation
for each quantizer (in 0.5 steps) with different movie sources. That´s why I
stopped my experiments and left the idea that there might be some sort of correction
function we could use for HCPredictor.

The errors were varying between -7% to up to 20% (depending on source and quantizer).

Best regards,
D$

[mikneadia]

Hi, D$.

This is of course similar to the "unstable" formula I use for CQ prediction but other than in CQ
prediction I do no "regression". I simply use the ratio of the size (similar to your a) as correction factor.

Just my "2-cents" thought. I think this is an important source of discrepancies. (the difficulty to have a 1-pass VBR must come from somewhere!); may be too "simple " ; not enough accurate. Discussed later in this post.

Filesize of 1% samples for a certain quantizer. This might give us
a graph but I´m unsure what to do with this graph

If I understood correctly your ABD model (that is looking very promising :You should give it a special name for further discussions ), you could avoid steps 2 to 4.
For each 1% segment, you know the size for their own optimal Q (assuming that for step 1, you computed optimal Q for each 1% segment and then did a weighted average to get "CQ prediction for 1% of the complete movie"). Then, you compute step 5 using optimal Q for each segment instead of their size for Q=1 (computations will be totally different, but you will get a similar result for no additionnal time).
The weighting factor is very interesting. I had in mind a "dampening" factor (cf "math" thread).

Investing a lot of time for CQ prediction makes no real sense just in order to save 1-2% runtime.

I agree for the investment part. I just do not agree that CQ prediction is used only in the prediction phase. If you knew perfectly S=f(Q), the only issues left will be the representativity of the 1% sample and Initial Q. If after having encoded perfectly the right first segment and if you knew the perfect Q for the segment 2 (because I assume that that S=f(Q) is perfectly known) everything will be fine. That is why I do think that knowing as much as possible S=f(Q) is important. May be make an interpolation on each segment with data coming from the bisection method. (keeping one S=f(Q) curve per segment).

You indicated that RB-Opt somehow uses a 2pass CQ prediction. Can you please give more details on this ?

I misled you, but this is the term used by Rb-opt. He uses 1 sample, computes Qopt and then uses a second sample (his 2-pass) to compute Qopt for the second sample and computes the average Qopt of the two samples.

The biggest disadvantage in my / manolitos method: We post-react / correct......
The quantizer is rised after a segment was undersized. The quantizer is lowered after a segment was oversized.

It may mean we all agree that we need better predicting method (predicting Q(N+1) with information available at the encode of segment(N)), better than Q(N+1)=Q(N)*S(N)/S(desired)). Most of the "math" posts had actually HCPredictor in mind, not HCShredder.

Great work.

[Darksoul71]

Hi all,

beside some more mathematical discussions on the size correction algorithm
I´m currently testing HCShredder in "real live" and play around with the clamp
borders. I´m somewhat surprised that no-one reported back....

Did HCShredder work for you to meet the target size ?
Did you like the results ?

I would pleased to hear your feedback....

Beside an optional 2-pass mode for the last segment (nearly 100%
exact target size) I´m thinking about some interesting functionality
which I found posted over at doom9 (unfortunately I just copied
the text but not the reference):

...
We already have the ability to set a favourite matrix
for low (<3000) and very low (<2000) bitrates (as well as extras).
But many segments fall into "Medium" (say 3000-3500) and "Medim-High" (3500-4000),
as well as High (4000+).

I wonder if it's possible (or worthwhile) to add 3 more choices to the options to
cater for these segments?
...

They were discussing something like an "adaptive matrix selection" based
on the bitrate. This would be very easy to implement. Would this be a
function you use ? Beside applying a different matrix based on the bitrate,
I could imagine to apply different filters as well based on the bitrate.

What do you think ?

Cheers,
D$

[mikneadia]

post#10 and 11 in http://forum.doom9.org/showthread.php?p=1092206 
Also, the criteria for selection matrix might be compressibilty instead of bitrate. You might already have run a sample with standard matrix and based on the final Q, you select a matrix . (if the Q was " high " (you need to compress a lot, you select what would have been a "low-bitrate" matrix. This will enable you to take into account what "s in the AVS script (filters, different resolutions....).

off topic: Why compensate the accumulated error sizing over the next encode (instead of the remaining ones on a pro-rata basis)?

P.S. The ref is blutach ( http://forum.doom9.org/showthread.php?p=1058876 )

[Darksoul71]

Hi all,

hm, it seems that the concept of HCShredder needs a more detailed mathematical approach....

In my recent tests a lot of files came out perfectly sized (e.g. 1-2% over or undersized)
but yesterday I experienced two oversized file (6% and 8%) when doing DivX2DVD conversion
with DIKO based on NTSC material.

I used +/- 20% clamp here.

@mikneadia:
I hope you are not disappointed that I didn´t reply on your suggestions earlier. It´s just
that I´m very busy in "real live" with other things and the mathematical stuff is really
time intensive to understand and evaluate for me. Your input is definitely apreciated.

First thanks for the reference to the D9 thread...I just found it by coincidence and saved
the posting as text file because I liked the idea.

Ok, the idea of using a matrix based on the Q-value sounds cool. Makes more sense than
bitrate to me.

I had another idea I´ll post over in the mathematical thread.

VM was so kind to "upgrade" me to Mod. So I´ll try to move the relevant posts from here
over to the "math thread"

For now HCShredder development is frozen. I want to release a new version of HCEnc^n
first which supports the "lossless" feature of HCEnc which I found very usefull and also
will remove the dependency on DGIndex for merging the M2V segment. There a still a few
tests to do so.

To quote 3D Realms:
HCenc^n will be released "when it´s done !" *ggg*

Cheers,
D$