[FFmpeg-devel] [PATCH] DNxHD/VC-3 encoder

[Loren Merritt]

On Fri, 7 Sep 2007, Michael Niedermayer wrote:

> when people start using qsort you know theres something wrong in their
> encoder (or at least not optimal)
>
> so, lets first check if i understand the constraints
> * its possible to change qscale per macroblock and it doesnt cost anything
> * theres a fixed number of bits available for each frame (pre mpeg1 design)
>
> in that case the optimal solution (though not fastest) is to do a
> binary search over lambda (using the number of bits and the ones available
> to find the best lambda which results in a frame which is not too large)
>
> then for each such lambda, find the best qscale for each MB, again by
> binary search minimizing SSD + bits*lambda (that way we know the best
> qscales and how many bits the frame would need)

Your algorithm produces the same decisions as the one with qsort. I don't 
know which is faster.

Consider the list of possible block encodings sorted by 
delta_ssd/delta_bits. Optimizing for qps at any given lambda will produce 
some prefix of that list. i.e. for any lambda, there is some 
position in the list such that all preceding entries have ssd/bits 
better than lambda, and all following entries have ssd/bits worse 
than lambda. So instead of evaluating bits(lambda) as a black box and 
searching for a specified values of bits, construct the function 
lambda(bits) and evaluate it at the specified value of bits.

--Loren Merritt