[THREAD SPLIT] Is Trellis always beneficial?

[ChronoCross]

And now that an old-timer (i.e. me) voices protest you are taking it back. But in a way like you didn't really mean what you wrote first. And the next thing I read, you are spreading that trellis shouldn't be used with custom matrices?!? Veto, veto, veto.

I have to disagree. In my Experience(I said earlier that perfect settings don't exist) i have found that trellis doesn't work very well with anything other than the mpeg and H.263 matricies. video blocks and degraded quality ensue. sorry if you don't agree but like I said this is from my own experience with the codec.

but then again this is just in the humble opinion of a simple encoder.

-ChronoCross

[Peter Cheat]

Originally posted by *.mp4 guy
No trellis is the god of good features;)


This depends totally on the bitrate and matrix that is used for the encode. For very low bitrates (say 350-450kbit/s), trellis will make the image more blocky. However, it improves the image considerably for higher bitrates. Also, with matrices designed for high bitrates used with a too low bitrate + trellis, the blockiness will be more apparent than using a high bitrate matrix with low bitrate without trellis. Also low bitrate matrices at low bitrate with trellis can cause more blocking depending on the content. This is from my experience.

How trellis works (I think) is finds the block that has the least rate distortion * bits (or something like that) rather than the block that uses the least bits. Using the least bits will make the block more noisy, but probably not visibly blocky. Using RD, a block will be smoother (averaged over block) and consequently, more visibly blocky. The best way to determine whether trellis will improve the perceptual quality of the image for you is to encode the entire material with and without trellis, and make up your own mind.

@ChronoCross You are sort of right, you obviously do medium to low bitrate encodes.

I'm out,
Peter Cheat

[Manao]

Treillis doesn't change how the ME is done. Treillis is used when quantizing the blocks. Instead of quantizing it "simply" by dividing the DCT coefficient by the quantizer and then rounding ( toward zero ), it tries for each DCT coefficient two quantized values : round(DCT / quant) and round(DCT / quant) - 1. The second one often increases the distorsion ( because the first one is optimal distorsion wise ). However, the second one is lower than the first one, so it takes less bits to compress, especially if it becomes zero.

Hence, if you choose the second coefficient instead of the first one, distorsion will be larger, but DCT coefficients will take less bits.

On the tests I made with XviD and treillis, with H263 quantifications, it allows a gain of 0.3 dB at fixed filesize. The gain should be the same with custom quant ( except if it's buggy )

Edit : I almost forgot, it works at all bitrates.

[Arlong]

In my opinion, Rate-Distortion algorithm works well in most cases. TQ should now do good with almost all Q matricies.

My PNSR tests say this too :)

[Peter Cheat]

PSNR = Peak Signal To Noise Ratio

It does not measure the overall quality of video, it is a mathematical representation of the difference between the original image (video) and the compressed image (video). I have encoded scenes with XviD that have an average PSNR of over 40dB and blocks did occur. This was a ~5 min low bitrate scene in which 4.5 min was dark (night scene) the rest was bright (day light scene). The dark part was encoded well, without any blocking, but the short daylight segment contained significant blocking.

RD _should_ theoretically be better (mathematically it is using PSNR as the judge) but perceptually it may not. I'll try to find a scene that demonstrates this and encode it to the same file size with and without trellis searched quantisation.

@Manao Trellis (searched quantisation) finds the block that matches with the least sum of squared errors (abbreviated to SSE). Therefore it affects the decision on which MB to use, which may alter the ME. Ok it will alter the ME.

I don't understand why people are so hung up on PSNR. I can pull out many comparisons using PSNR, SSE, SNR, MSE, etc etc. Overall quality of an image cannot be determined mathematically. It really is personal. This thread is really a waste of time, I can see its going to turn into a flame war.

I'm Out,
Peter Cheat

btw I am a Computer Systems Engineering student. I know a thing or two about signals analysis and processing...

[RadicalEd]

Overall quality of an image cannot be determined mathematically.

Currently. I'm sure with a more advanced understanding of the HVS it will eventually become possible to build a perfect perceptual model. It's just that nobody has been able to do such a thing yet.
Moot point as of now, but food for thought nevertheless.

[Manao]

RadicalEd : well, a first basic step toward a R-HVS optimization would be to ponderate the distorsion brought by the modification of the quantized DCT coefficient by ( for example ) the coefficient of an HVS custom quant matrix. But it seems XviD devs are even more interested in bringing some perceptual considerations ( just have a look at the mailing list ).

Peter Cheat : I can assure you my definition of treillis is good. Have a look at that document (http://www.icsl.ucla.edu/~ipl/Publications/Journal/trellis-based_r-d_optimal_quantization_in_h263+.pdf)

[Peter Cheat]

I still maintain that trellis quantisation changes the encoders decision on which macroblock to use.

Anyway, I just did a quick test with a tv capture of X-Men. I encoded the first 2500 frames in XviD with constant quantiser of 9 with and without trellis. The results may surprise. The resolution was 640x480, and the .h263 matrix was used.

With Trellis
------------
Filesize: 17,030KB
Minimum Average Maximum
Mean Absolute Deviation: 0.1557 11.2229 120.2715
Mean Deviation: -116.6081 -0.2507 +117.2820
PSNR: 4.8737 27.3300 55.6608


Without Trellis
---------------
Filesize: 17,046KB
Minimum Average Maximum
Mean Absolute Deviation: 0.0837 11.2348 120.2715
Mean Deviation: -116.6081 -0.2642 +117.2811
PSNR: 4.8737 27.3985 58.0808

As you can see, the filesizes are basically the same, but with trellis enabled, the average PSNR reduced by ~0.07dB.

Both clips were blocky. Looking in VDub frame by frame, no real difference can be seen, but the trellis encode was more blocky in high motion.

If you don't believe these try a low bitrate encode for yourself with constant quant.

[Audionut]

This from Koepi,

VHQ R-D code is different from trellis quant (which works on the DCT of the macroblock and sets all coefficients to zero in cases the decision says so).

It's supposed to set DCT-coefficients to 0 if the distortion introduced by that is lower than a weighted amount of bits saved (coding 0-coefficients is efficient.). It'll introduce a slight drop in PSNR by it's nature, but the filesize gain overcompensates for that (in 2pass scenarios, that is.)

[Sagittaire]

I still maintain that trellis quantisation changes the encoders decision on which macroblock to use.

Anyway, I just did a quick test with a tv capture of X-Men. I encoded the first 2500 frames in XviD with constant quantiser of 9 with and without trellis. The results may surprise. The resolution was 640x480, and the .h263 matrix was used.

With Trellis
------------
Filesize: 17,030KB
Minimum Average Maximum
Mean Absolute Deviation: 0.1557 11.2229 120.2715
Mean Deviation: -116.6081 -0.2507 +117.2820
PSNR: 4.8737 27.3300 55.6608


Without Trellis
---------------
Filesize: 17,046KB
Minimum Average Maximum
Mean Absolute Deviation: 0.0837 11.2348 120.2715
Mean Deviation: -116.6081 -0.2642 +117.2811
PSNR: 4.8737 27.3985 58.0808


1) q9 is a ridiculous quatizer with MPEG ASP and H263. 27 dB is a ridiculous PSNR too. Use PSNR in this case is ridiculous too ...

2) max PSNR with treillis is 55.6608 dB and max PSNR without treilli is 58.0808. No trellis seem very better for black frame and no conclusions are possible for average PSNR: Make frame PSNR graph or use Overall PSNR ...

[Manao]

Peter Cheat : filesize are not the same. When PSNR is so low, the PSNR / bitrate curve is almost vertical.

I made two RD curves, one with trellis, one without trellis, on foreman ( cif ). Other settings were default except for chroma motion ( unchecked ), and VHQ 4.

http://jourdan.madism.org/~manao/xvid-trellis.png

As you can see, at high bitrates, trellis' curve ( the green one ) is higher than without trellis. At low bitrates, it's hard to see, but if I zoom on that part :

http://jourdan.madism.org/~manao/xvid-trellis-zoom.png

You can see it's still higher. The gain is not as important as if the quantizer was 3, but there's still a gain.

And finally, those figures are taken from overall PSNR, not average. If you look at your figures, you'll see that absolute mean deviation is lower with trellis than without. And why did you not give us the overall ? Oh, also, how did you achieve a min psnr of 4 ?

[Peter Cheat]

Obviously I do not use quantiser 9 for normal encoding, I was merely tring to do a quick demonstration of a case that I know will show that trellis will not be beneficial. The topic of the thread is "Is Trellis always beneficial?". These results show that it is not. Whether or not constant quantiser 9 is a realistic quantiser to use for encoding with this matrix is not relevant in the context of this thread.

Also, I stand corrected about trellis. Trellis changes the decision about how a block is coded, and has nothing to do with macro bloack decision. A bit of a mix up on my part.

Now a comment of the results I obtained which I didn't have time to do before.

Overall PSNR?? What is that supposed to mean. The PSNR of each frame has been calculated and then averaged to give the average PSNR. AFAIK this is the normal procedure. If you mean to say that I should get the Peak signal of the entire clip as a whole, then divide by the average noise, then convert to decibels, well this is meaningless. IMHO, SNR can give a better representation of how close an image is to the original, but PSNR is the accepted convention.

As you can guess, the clip used is very dark. This was used on purpose to demonstrate. In this case, the Mean Absolute Deviation gives a more accurate representation of how close the sequence is to the original.

To elaborate on the overall quality - it was almost the same. The sequence encoded with trellis couldn't be separated from the sequence encoded without trellis when watching in realtime. The difference could only be seen on a frame by frame basis, where a noticible increase in visible blocks occured during high motion.

I'll generate a PSNR graph later so you can make up your mind for yourself.

This has been discussed before see http://forum.doom9.org/showthread.php?s=&postid=434506
The reason for the increase in visible blocking may be a bug in the code. I don't know, I just report what I see.

[Peter Cheat]

I encoded the same material at quant = 2 with trellis on and off.

With Trellis
------------
Quantiser = 2;
Bitrate = ~5000kbits/s
Filesize: 61,184KB
Results:Minimum,Average,Maximum
Mean Absolute Deviation: 0.0000,10.7810,120.0338
Mean Deviation: -116.4967,+0.0435,+117.3716
PSNR: 4.8822,30.1807,103.0050

Without Trellis
---------------
Quantiser = 2;
Bitrate = ~5000kbits/s
Filesize: 60,958KB
Results: Minimum,Average,Maximum
Mean Absolute Deviation: 0.0000,10.7808,120.0338
Mean Deviation: -116.4967,+0.0438,+117.3717
PSNR: 4.8822,30.5041,103.0050

The PSNR of the encode without trellis is +0.3234dB larger than with trellis. Now, I know that you are going to say its not a fair representation of the data. So, just for you, I have uploaded the results here (http://petercheat.host.sk/files/Trellis_Quantisation_Test_-_X-Men.zip). You can try to manipulate them however you want, the results still show that trellis does more harm then good in this case. I know its impossible to change your minds, I just want to distribute the real facts to others. The high motion segment (frame 1000 - 1675) also has a lower PSNR on average. On a frame by frame basis, it is higher and lower, but it is MOSTLY lower.

So the answer to this thread is NO!

I'm out,
Peter Cheat

[Manao]

I can't download the file ( "Forbidden You don't have permission to access /files/Trellis_Quantisation_Test_-_X-Men.zip on this server." )

Anyway, the min PSNR is still around 5, with a quantizer 2, and that doesn't bother you ? When the max mean absolute deviation is 120, it means that your comparing two totally different frames. Oh, and it's the first time I see a PSNR of 30 at quantizer 2.

So please, when computing the PSNR, do assure yourself that you're computing it on the same frames, because you obviously don't.

[Audionut]

Forgive my ignorance, as I only use xvid 1.1 builds.

Has the trellis bug been fixed in Koepi's builds?


I think it all boils down to this.

Does trellis decrease the quality of your encodes?
Perhaps, but can you see this with the naked eye?

Does trellis decrease file size?
Yes!



I should also mention that the validity of PSNR values, are suspect, at best, on this forum AFAIK.

[Teegedeck]

1) The Trellis bug has been fixed a long time ago.

2) Trellis visually improves the quality of your encodes.

3) In theory and in practice (until proven otherwise).

4) This can be visually proven - the Trellis encode should be sharper.

I don't regard PSNR to prove anything.
Personally I have visually tested the Trellis-fix with a 2-CD encode.

4) I can only advise anyone who is in doubt to verify this himself: Encode the same clip with and without Trellis and compare (with your eyes, that is sufficient).

5) The only valid question - and it is the topic of this thread - is: Are there occasions/special cases (low bitrate? anime?) where Trellis doesn't help?

[Sagittaire]

I encoded the same material at quant = 2 with trellis on and off.

With Trellis
------------
Quantiser = 2;
PSNR: 4.8822,30.1807,103.0050

Without Trellis
---------------
Quantiser = 2;
PSNR: 4.8822,30.5041,103.0050


Frame are desynchro ... min PSNR = 4.8822 and avg PSNR = 30.5041 ... it's impossible with q2 H263 encoding ... it's impossible with q31 H263 encoding too ...

And drop black(s) frame(s) (max PSNR = 103 dB with desynchro -> multiple consecutive black frame)

[unmei]

Indeed indeed.
I thought the zip would contain samples, or at least some frames, but it contains xls lists with PSNR output for all the frames.

The only thing i see there is you really screwed something up. Maybe 50% of the frames have PSNR 15-20, 25% have PSNR above 90 and a tiny quarter or so have "normal" values. I guess high values are all black/close to black frames. The "normal" ones somehow managed to give sensible PSNR by accident (almost static?)

[edit]
Maybe i should say something about the topic as well..
I never explicitly tested trellis vs no trellis, but i use trellis in all my anime encodes and never encountered a "problem". I wouldnt know about a slight PSNR decrease of course, but i can say it never produced artifacts or something like that for me. (i also use it for non-anime, but 80 or 90% of my encodes are anime and that genre was also what were to be confirmed here).

[virus]

Obviously Peter Cheat forgot to cut away the first frame(s) to compensate for the use of B-frames. So he's comparing one frame with... the previous one. This ain't good ;) Average PSNR for a Q2 encode should be always > 40 dB.

Also: after reading the paper (thanks Manao for the link) I'd say that personally I wouldn't use trellis for a constant quantizer encode. Its point is to somehow reduce the quality of single macroblocks, but with a good return in terms of bitrate savings (well, maybe that can be changed by modulating the lambda parameter, not sure).

Usually in a 2-pass scenario these saved bits can be spread across all the frames to improve the average quality of the video (and thus increase the Average PSNR). In a fixed quantizer encode, of course, you cannot spend your "bit reservoir" for anything, since all the frames receive the same treatment. So the PSNR should be slightly lower with fixed quantizers. That's just my understanding of this feature, anyway, I may be wrong.

cheers :)
virus

[Peter Cheat]

It is possible that frames are out of sync. I'll check the AviSynth script and then update the results. If the XviD seqeunce is BBIPBBP or whatever, doesn't AviSynth decode the first B frame(s) by decoding the I frame first, or does the XviD decoder cut them off?

[PowerMacG4]

bframes shouldnt reference I frames.

[Manao]

PowerMacG4 : b-frames can have both forward and backward references as i-frames, though with close gop, only a forward reference can be an i-frame.

Peter Cheat : the decoder doesn't cut them off, however, it delaies them by one or several frames ( it depends ). To check the delay, I use Interleave(source, encode) in avisynth, and I check whether both frames are the same or not.

virus : at first sight, I thought also that trellis could only lower PSNR. However, look at the curves I gave, it can raise psnr at fixed quantizer with h263 ( for example, q2 and q4 ). I have no explanations yet ( perhaps a different deadzone ? )

[virus]

Originally posted by Manao
However, look at the curves I gave, it can raise psnr at fixed quantizer with h263 ( for example, q2 and q4 ). I have no explanations yet ( perhaps a different deadzone ? )
Since you used the defaults and so no AQ, well, I have no explanation too. Maybe there is some interaction between VHQ4 and trellis? There shouldn't be a relationship really, since VHQ applies to MB mode decision (also to the MB candidates' choice if used at level 4, but probably this is not important) while trellis works on the DCT coefficients.

Or maybe this comes from the fact that trellis works in the domain of frequency on a differential signal while the PSNR is computed on the actual image in the spatial domain, so maybe a slight distortion applied to the DCT coefficients does not necessarily translate into a worse PSNR in the reconstructed signal.

Ok, enough speculation :D

[Didée]

Originally posted by Manao
it can raise psnr at fixed quantizer with h263
More speculation:

I'm not fully sure how the situation is in actual 1.0/1.1 builds. But formerly, it was so that for mpeg quantization, Trellis would only zero coefficients out, whereas for h263, it could either zero a coefficient, or raise a zero'ed coefficient from 0 to 1. The latter would explain the PSNR gain.

[virus]

@Didée

I crosschecked the source (\src\utils\mbtransquant.c) and I cannot confirm your thoughts: all the matrices are treated the same way. Here's the only bit of code in the whole routine where knowledge about the QM is used:
const int q = ((Q*QuantMatrix[Zigzag[i]])>>4);
which is part of the standard code to calculate the quantizer step.
For the rest, well, I'm not sure I can fully understand the code (Skal's code is always full of nice tricks ;)) but it seems that Manao is perfectly right: negative levels are incremented by 1 and positive levels are decremented by 1 for the comparison. That is, a simple rounding towards zero. How this can lead to a fixed quantizer encode with higher PSNR is still a mystery... :rolleyes:

[Manao]

The funny thing is that at q2, q4, q6 it increases the psnr, and q3, q5, q7 it decreases it. I tested on another clip, with another codec which supports trellis, and the same behavior occured, so it's definitely a feature, not an interaction between vhq4 and trellis.

When computing distorsion on the DCT coefficients, we make an error of 10 % ( because of rounding / saturation while doing the idct ). That could explain why the psnr can raise, but not why it is so systematical.

That's why I still think it's because of dead zone, because when doing the h263 quantization, the formula xvid is applying is "qc = (c - (q/2)) / (2*q)". Therefore, the deadzone is higher if q is even. It's no proof, but I think the explanation is somehow hidden behind that fact. ( though when desperatly looking at the source code, I see that the deadzone is strictly the same when quantizing with trellis )

[virus]

WARNING: looong, boring post! :)

Originally posted by Manao
The funny thing is that at q2, q4, q6 it increases the psnr, and q3, q5, q7 it decreases it.
OK, this hint looks interesting enough... let's try to understand what happens in the simple case of H.263 quantization. Here's the complete computation procedure in dct_quantize_trellis_c():
const int q = ((Q*QuantMatrix[Zigzag[j]])>>4);
const int Mult = 2*q;
const int Bias = (q-1) | 1;
const int Lev0 = Mult + Bias;
Note: here I used an index "j" instead of "i" to avoid
problems with the text formatting tags
I've seen that in this case (H.263) XviD "builds" a quantization matrix full of 16s (the coeffs are in 1/16 units). This means that the first row reduces to:
const int q = Q;
where Q is the macroblock quantizer. Without AQ, Q is also the main frame quantizer. Let's concentrate on the bias then.
For even Q (or q), the bias becomes "<odd number> | 1", which is a no-op, so if the frame quantizer is Q, the bias is Q-1.
For odd Q (or q), the bias is "<even number> | 1", which increments it by 1. So if the frame quantizer is Q, the bias is still (Q-1)+1=Q.

So the quantizer vs bias function is:
Q bias
---------
1 1
2 1
3 3
4 3
5 5
6 5
7 7
...


And now we can compute Lev0 = 2*Q + bias for every frame quantizer:
Q Lev0
---------
1 3
2 5
3 9
4 11
5 15
6 17
7 21
...


What is Lev0? Well, it should be (= to the best of my understanding) the threshold under which a DCT coefficient is rounded to zero by the quantization process. That is: if (-Lev0 < DCTcoeff < Lev0) then the coefficient is rounded to zero and discarded.
Under such circumstances, there's a bit of code in the routine which apparently also checks if -1 or +1 can fit better in the R/D sense (-1 for negative DCTcoeff, +1 for positive).
A DCTcoeff quantized to +1 is reconstructed as +Lev0, while a DCTcoeff quantized to -1 is reconstructed as -Lev0.

Example:
Q=2, so Lev0=5. Current DCT coefficient = +3.
DCTcoeff is +3 so the quantization rounds it to 0. But the routine will also search for a value of 1! If 1 is chosen, the output will be reconstructed by Lev0=5. That means that the coefficient will be rounded to 5 instead of 0. (the error drops from 3 to 2 and thus we have improved our encoding)

Q=3, so Lev0=9. Current DCT coefficient still = +3.
DCTcoeff is +3 so the quantization rounds it to 0. Trellis will also search for a value of 1! If 1 is chosen, the output will be reconstructed by Lev0=9. That means that the coefficient will be rounded to 9 instead of 0. (the error raises from 3 to 6 and thus we have worsened the error)

This (maybe, not sure really) shows how the PSNR can improve. Since increasing from a even Q to an odd Q raises considerably the Lev0 threshold, maybe we can also understand why small DCTcoeffs (like -3, -2, -1, 0, +1, +2, +3 - they should happen very frequently) can be rounded to +1/-1 (instead of 0) with "higher probability of success" with an even quantizer.

...and now, please say what I did wrong in that "proof", 'cause I'm pretty sure I've b0rked something :D

virus

[Manao]

No I think you're right. I overlooked the use of Lev0 inside the specialized code when the quantized coefficient was -1, 0 or 1.

[Peter Cheat]

I updated the results, this time I got the frames in sync here (http://petercheat.host.sk/files/Trellis_Quantisation_Test_-_X-Men.zip). I now included an example frame (high quality jpegs) of the original frame, frame encoded with trellis and frame encoded without trellis at Q9. The frame encoded without trellis seems to be more sharper (yes, it does to me) and less blocky. Look at the top centre of the frame of the trellis encode, it is really ugly, and the gradient is gone. Without trellis, its still a little blocky but the gradient is still there. What can't be seen in these images is the block-blurring during the zoom-in in this part of the scene. The trellis encode looks much more horrible in this respect. But, you may disagree.

Update of results:
At Q2, the no trellis encode had a HIGHER PSNR than the trellis encode, 49.7764dB vs 49.6193dB.

At Q9, the no trellis encode had a LOWER PSNR than the trellis encode, 39.5614dB vs 39.5773dB.

This is totally the opposite of what I see. At Q2, the trellis encode is sharper. At Q9, the encode without trellis, I think is better. That's up to discussion though.

These results contradict the even q=increased psnr, odd q=lowered psnr. I'm sure didn't mix up the encodings, I reencoded the material to make sure :p

[Manao]

I took a look at the screenshots : both are blocky ( for my eyes ), some part of the frame without trellis looks better, others look worse. Perhaps on the overall I would slightly tend to prefer the one without trellis ( thought the up-left corner is really ugly )

Just a piece of advice : on your screenshots, you can see that the first and last row of macroblocks inside the picture are far more blocky than the rest, and that the color is slightly different. I think it's because you didn't crop the black borders.

Oh, and your results do not necessarily contradict the odd / even quantizer thingy : you used b-frames ( which are encoded at another quantizer ), and since we don't know what were your b-frames settings, we can't know what was the quant used.

[virus]

My own PSNR results:
quant H.263, QPel, no AQ, no B-VOPs, no GMC, MSP6, VHQ4, no Chroma ME, no Turbo
Q Trellis No-Trellis Difference
---------------------------------------
2 47.50 47.41 +0.09
3 45.81 45.89 -0.08
4 44.54 44.49 +0.05
5 43.54 43.55 -0.01
6 42.75 42.71 +0.04
7 42.09 42.08 +0.01
Looks like the even/odd thingie only happens for low quantizers.
Anyway Peter, it's not rocket science, so "counterexamples" can easily be found I think. It's all related to the likelihood of a zeroed coeff to be lifted to +1/-1 by trellis vs. the value of Lev0.
At low bitrates the scenario is very different and so different aspects are probably more relevant (and trellis becomes less important overall, it seems).

[MfA]

Fixed Q testing? That is downright silly ...

[Manao]

MfA : not if you draw a rd curve, thus taking into account the filesize.

[virus]

Here's the R/D curve then :rolleyes:

http://img73.exs.cx/img73/1914/trellis_rd.png

It only shows that trellis improves slightly the R/D curve as expected, nothing more. It does not answer the question we were investigating, about the "strange" behaviour of trellis at a fixed quantizer. What kind of test should we do if we're talking about fixed Q? :rolleyes:

[MfA]

It isnt strange behaviour, as you noted there is a crude RD optimization built into the standard quantizer ... and it is indeed more likely to be wrong on even quantizers, trellis just corrects this.

On the whole though trellis is there to save bits at the cost of increased distortion ... so when it decreases PSNR at fixed quant it is most likely just doing its job, when it manages to increase PSNR it is just doing its job very well.

PS. personally I have never liked trellis search, it makes it impossible to determine the quantization bounds for the image at the decoder ... in the future post processing could improve to the point where stuff encoded with trellis search might even end up looking worse.

[Peter Cheat]

Originally posted by Manao
Oh, and your results do not necessarily contradict the odd / even quantizer thingy : you used b-frames ( which are encoded at another quantizer ), and since we don't know what were your b-frames settings, we can't know what was the quant used.

For Q2, b-frames were encoded at Q4.
For Q9, b-frames were encoded at Q15.

Originally posted by Manao
Just a piece of advice : on your screenshots, you can see that the first and last row of macroblocks inside the picture are far more blocky than the rest, and that the color is slightly different. I think it's because you didn't crop the black borders.

Good point, I did forget to crop the black borders. I was using this scene to test mpeg2 encoding, hence why there are black borders in the first place.

@virus
What happens when the bitrate goes down below 400kbits/s with and without trellis?

@MfA
Fixed Q testing isn't so silly. When you take into account the differences in frame sizes (or filesize) in respect to PSNR (which is the best way to determine quality that we currently have) we can determine whether trellis improves the quality of an image, or degrades it, relative to frame size.

For my testing, I didn't use GMC and used VHQ1. I remember seeing posts relating to increased blocking with trellis sometime ago on an XviD devel forum. It was suggested that using VHQ increased blocking, but turning it off reduced blocking. I'll test with every possible VHQ level and post the results.

[virus]

Originally posted by Peter Cheat
What happens when the bitrate goes down below 400kbits/s with and without trellis?
Haven't tested so low bitrates (anything below Q7 is really low quality - and XviD is not tuned for that). Anyway I've just tried the same encoding at Q9 and here are the results:
rate PSNR
(kbit/s) (dB)
-------------------------------
Trellis 489.2 41.08
No trellis 493.5 41.07

Trellis seems to work in a more "uniform" way at high quantizers. That is, there's not so much difference in terms of PSNR as at low Q. Here probably different factors are more relevant. Maybe here the high value of Lev0 (27 @ Q9) is simply more important than the fact that it doesn't scale uniformly with Q. Trellis remains efficient anyway.

For my testing, I didn't use GMC and used VHQ1. I remember seeing posts relating to increased blocking with trellis sometime ago on an XviD devel forum. It was suggested that using VHQ increased blocking, but turning it off reduced blocking. I'll test with every possible VHQ level and post the results.
It depends on how much time ago this was written... remember that all versions up to 1.0.0-final had a bug in the trellis search which gave suboptimal results (including maybe some artefacts). Only version 1.0.1 and 1.0.2 have a perfectly working trellis, so things may have changed. As Manao pointed out, VHQ should not interfere with trellis though.

[Peter Cheat]

I may be using 1.0.0-final, I don't remember whether I download 1.0.1, I've just downloaded 1.0.2 and see if it makes a difference.

[dragongodz]

you may also want to try comparing using SSIM aswell as PSNR and see what that tells you.

[Raptus]

Originally posted by RadicalEd
I'm sure with a more advanced understanding of the HVS it will eventually become possible to build a perfect perceptual model.
Better models yes, a perfect one, no!
You can perfectly compare a HVS model to the psychoacoustic model of modern lossy audio coders. And like with audio compression some problems arise, because as with hearing, every person has a different HVS, neither do we know the playback conditions (screen size, resolution, distance, luminosity, ambient light, etc.), which influence the perceived subjective quality.

Personaly I find it odd that measures like PSNR are still being used as quality meters. In audio compression doing simple difference comparisons between the input and the output is "forbidden", the only valid quality comparisons being trough ABX tests (see the Hydrogenaudio forum). Yes, I'd propose that such a methodology should be used for judging the quality of video, too.

[Manao]

Raptus : PSNR still has some meaning for human vision. With a PSNR over 50, you know you'll get visual transparency. In audio, we don't hear sample's values, we hear frequencies, that's a lot more different. We're very sensitive to ratio between two frequencies, and so on. A distorsion measure as simple as PSNR wouldn't mean anything in audio, but in video it does.

[Raptus]

Did it sound as if I was saying that we hear samples values?? ;)

In video you've got the same concepts as in audio, after DCT image detail translates into frequency (thus lowpass filtering etc), too, both got ringing and artifacts, and as I stated previously everyone has a different perception of subjective quality, to name a few.

What I'm trying to say is that PSNR is too simplistic to represent perceived quality (i'm sure you've seen clips were a lower PSNR actually resulted in subjetively higher quality), it just compares distortion between still images, not considering a single thing we know about HVS other than the smaller the distortion, the better.

I am sure this will change, much research has still to be done (or applied), resulting in better ways to measure subjective quality (again, ABX tests could be a first approach); psychoacoustic research in the context of compression seems to be quite a few steps ahead of video.

[crusty]

Manao:
virus : at first sight, I thought also that trellis could only lower PSNR. However, look at the curves I gave, it can raise psnr at fixed quantizer with h263 ( for example, q2 and q4 ). I have no explanations yet ( perhaps a different deadzone ? )

AFAIK, Trellis not only drops some detail, but can also bring it back from the DCT-grave in some instances. It could be that on some material it actually raises PSNR because more detail is brought back.

I'm sure with a more advanced understanding of the HVS it will eventually become possible to build a perfect perceptual model.
LOL...a perfect model is simply impossible because. Who ever heard of a perfect human? Eyesight and eye-to-brain mental capabilities simply vary too much. Even if you did make a perfect model, there wouldn't be many people around that are modelled by it.
;)
It isnt strange behaviour, as you noted there is a crude RD optimization built into the standard quantizer ... and it is indeed more likely to be wrong on even quantizers, trellis just corrects this.

This makes me think that doing 2-pass encodes with minQ=2 instead of 1 is even better practise than I imagined....