[XviD-devel] GME and Block ME

[Christoph Lampert]

On Fri, 18 Apr 2003, Radek Czyz wrote:

> Hi everyone,
> 
> gruel wrote:
> > Currently, I "solve" this by using _two_ block searches, one pre-analysis
> > before GME and the ordinary after GME. I can't just use MEAnalysis (for
> > B-frame decision) as pre-analysis, because it's too coarse. I need at
> > least 16x16 blocks in halfpel resolution, so just ordinary ME, except for
> > 4MV. With MEAnalysis this make 3 step of block ME... suboptimal!
> 
> > Is anyone interested in a small discussion about how to get rid of this
> > double/trippe work? Syskin perhaps?
> 
> After one day of thinking, I really didn't come up with anything...
> So let me just ask you, how bad MEAnalysis is? I never checked it ;)
> How bad would it be to follow it with halfpel refinement? This can
> only be done in FrameCodeP, because we don't have halfpel-filtered
> pictures available during p/b/i decision. We could also peform the
> motion search for all edge macroblocks, because we have edges then (we
> ignore all edge MBs during decision, not only because edges are not
> available, but also because it could be difficult to find good motion
> for them for example in case of camera panning).

32x32 blocks is too coarse (I believe), at least in low sizes (352x288 and
below). I rather think we should do a good MEAnalysis and reduce later ME
instead of doing a coarse MEANalysis and full ME. 
 
> Now, differenent stuff:
> 
> Has anyone heard of using 'sum of squared DCT coefficients' in place
> of SAD/SSE? I tried that, call it holiday-boredom if you wish ;)
> It was better then SAD, and at least not worse: 1-3% filesize gain at
> almost exactly the same PSNR. Better then SSE. And not _horribly_ slow.

In theory (mathematically) it should be identical to SSE (DCT is an
orthogonal transform). 

> And diffenrent stuff again:
> 
> gruel wrote:
> > (...) and start writing a trellis quant inbetween?
> 
> Yay, trellis quant :-) I was about to ask you what it's all about,
> googling for it gave me nothing :(. Anyway, could you please tell me,
> briefly, how it works? I understand that it's looking for
> optimal bits/distortion, but the question is: what does it do to
> change bits/distortion? 

It's kind of an advanced "TOOSMALL_LIMIT". Sometimes reducing a qunatized
coefficient to 1 less than the "correct" result can save many bits. But of
course the quantization error gets larger. 
So you introduce a lagrangian to weight distorsion versus bits needed and 
optimize quantized coefficients to optimal.

E.g. (thought model, not real values how quantization is done)
fixed quant 5,

coeff:    32 11 -2 -3  2  6  5

normally this is quantized to 
           6  2  0 -1  0  1  1

and dequnatized to 
          30 10  0 -5  0  5  5

error  
           2  1  2  2  2  1  0    sum-of-sq: 18


but instead if you quantized to 
           6  2  0  0  0  1  1

dequant
          30 10  0  0  0  5  5

error
           2  1  2  3  2  1  0   sum-of-sq: 23

The error is larger, but you may have saved many bits 
because you can save 3 zeros in a row instead of 0 -1 0

So it may be good to set a non-zero coefficient to zero 
to safe bits which can be spend (in the next frame). 

It's not always reducing to 7, it could e.g. be good to 
reduce a value of 64 to 63, because then you don't have to 
use ESCAPE-codes in VLC encoding which are rather costly. 

Because VLC tables are so complicated there is no general rule, when to
reduce coefficient and when not, so a clever optmization method must be
used to calculate the "optimal".

> At first I thought it's changing the quantizer
> but no - ffmpeg's file with trellis quant had constant quantizer. So I
> thought that it's decreasing, maybe discarding coefficients - that
> would decrease number of bits and increase distortion, ok. But again,
> no - ffmpeg's file was _larger_ and with much better PSNR...

_That_ I don't understand, either...

> I have just no idea how is it possible to increase PSNR, or even
> increase bits (or both..) during quantization....
> 
> Ffmpeg's code was way too criptic for this ;)

gruel