[XviD-devel] _real_ adaptive quantization

[Christoph Lampert]

On 1 Oct 2002, skal wrote:

> 
> 	Hi Christoph,
> 
> On Mon, 2002-09-30 at 21:04, Christoph Lampert wrote:
> > Hi,
> > 
> > I found my bug and now I can tell you about the very first results of 
> > "non-heuristic adaptive quantization". In my extensive tests with the huge
> > data set of full 10 frames of the foreman sequence in QCIF (176x144),
> > I achieved the immense quality improvement of 0.0002 in PSNR 
> > (from 37.57531 to 37.57551) when at the same time REDUCING bitrate by 
> > incredible .0517% (from 1934 bytes to 1933 bytes). 
> > 
> > Well... maybe not _too_ impressive so far, but at least it works now. 
> > 
> 	bwehehe...
> 
> 	How to you decide the q vs q+1 quant? Do you call a round
> 	of quant(q)/dequant(q)/quant(q+1)/dequant(q+1)/choose best ?

Currently it's brute force, as you describe, but not only for Q and Q+1,
but also Q+2 (not more, because it wouldn't always be possible to return
to Q in next step). It really calculated MSE of DCT-coefficients.
And yes, it's veeeery slow ;-) 

I thought of using more advanced routine, like cycling through
coefficients, calculating several distorsion in one step, but all this is
"only" speedup and at the moment, I'm after the theory what can be gained
at all. 

> 	If so, I have something in store that I didn't have the
> 	chance to test, yet. It computes the SAD implied by
> 	the H263 quant/dequant process, for a given q, with
> 	use of 2 tables access to hash the input coeff, thanks to
> 	something like:
>
> 	  (a*256 + b)%q  = ( (a*256)%q + b%q ) % q. = (b+Offset(a))%q
> 
> 	(quant error is not exactly (a%q), but that's the idea)

Approximation is always good... 

But I just got another idea: There are 4096 possible DCT values per coeff. 
There are possible 31 quantizers. If I create a table of
resulting distorsions, when quantizing any coeff with any quant it would
"only" be 126976 entries, right? 
Now, the most frequently used values will become constant anyway, because
the quantized coefficient becomes zero. If that happens for one quant, 
its the same for all higher quants, too. So there is a huge potential 
for saving space, if it's really needed. 
Large coefficients won't become zero, but they are much less often
used. E.g. everything above 512 and below -512 could be calculated "by
hand" and only the rest is put into the table -> 31744 entries. 
That's not much overhead, is it? 

"Precalculate and re-use as much as possible." (Rule #7 of fast computing)

> 	The term (a*256)%q is tabulated as an offset added to 'b'.
> 	(It's very like the rule to guess whether a number is
> 	divisible by 3: sum up its numbers, and check if its
> 	a multiple of 3...).
> 
> 	It also extend to directly computing the difference
> 	between q & q+1 in one shot, but only for quantizer
> 	less than Q=8 so far I've seen (afterward, tables are
> 	growing too huge).

I'll have a look at it, thank you!

> 	I have no clue how it can be extended to MPEG4-quantization,
> 	because quantizer range is (256 times) bigger...

I have no clue either. H263 is difficult enough for the moment...

> 	I attach my test proggy that scans all the input range...
> 	If you have time to plug this into your code, I'd really
> 	like to know how it behaves (within your ruthless testsuite:)

Let's see if it beat my incredible quality improvements at incredibly
reduced bitrate... ;-) 


gruel