[FFmpeg-devel] [PATCH] RoQ video encoder

[Michael Niedermayer]

Hi

On Fri, Jun 01, 2007 at 03:39:22PM -0400, Eric Lasota wrote:
> *Michael Niedermayer wrote:*
> > a patch to fix this is welcome (a sample which shows some artifacts with
> > the current decoder but works correctly with the ID decoder would also
> > be welcome if you have such a sample)
> >   
> http://icculus.org/~riot/bf2introseg.bz2
> Try that.  Q3A plays it fine.  Treating MOT as mcomp(0, 0) should cause 
> minor artifacts with the jet flyby, and severe artifacts with the muzzle 
> flashes.
> > you dont seem to understand how the buffer handling in libavcodec works
> > there is no gurantee that the frame you get from get_buffer() will be
> > the same as the last you released with release_buffer()
> > you can use reget_buffer() to achive that ...
> >   
> Yeah, I misread that part.
> > could you explain how the roq encoder decides on the choice it makes
> > for encoding each block, ive not reviewed the highlevel design of it
> > carefully yet (i of course will before any patch with it will get
> > accepted) i was just confused a little by all the sorting ...
> >   
> RoQ only has 259 possible encodings of each 8x8 macroblock (assuming the 
> parameters are the same, and there is no reason for them not to be), and 
> the encoder always spent most of its time during the codebook generation 
> and matching phases, so I figured an encoder could be written which just 
> brute-forced everything to aggressively squeeze quality out of the bit 
> budget:
> - The best results for each type of encoding are evaluated (i.e. the 
> best codebook entry for each macroblock, the best motion vector, etc.), 
> and the error of all encoding mixes are determined.
> - All macroblocks are assigned a possibility list, which contains all 
> possible encodings of the macroblock.
> - The list is sorted by bit usage in descending order, and then error in 
> ascending order.
> - Possibilities with the same bit usage as the next possibility are 
> discarded (ensuring only the lowest-error possibility for a each bit 
> consumption remains.).  List is re-sorted to push invalid entries to the 
> end of the list.
> - Possibilities with lower bit usage and higher error are discarded.
> The result of this is a list where plist[n+1] always consumes more bits 
> and has more error than plist[n].  The sort operations are mainly to 
> push discarded entries to the end of the list.
> - A list of reductions is created, one for each macroblock.  A reduction 
> represents a change in the encoding of a macroblock that reduces the 
> size of it.  Is declared as a pointer to a macroblock, an index into its 
> possibility list, and the error increase and bit reduction of going from 
> plist[index] to plist[index+1].
> - The reduction list is sorted by error per bits saved, in ascending 
> order.  Reductions where plist[index+1] does not exist are forced to the 
> end of the list.
> - Reduction loop: The reduction earliest in the list is processed: Its 
> index is incremented, the error and bit cost changes of the next index 
> in that possibility list is evaluated, and the reduction is 
> bubble-sorted to its new proper location in the list.  If the size of 
> the encoded frame falls below the desired value, or no more reductions 
> can be performed, the loop is exited.
> 
> A flaw with this is that during the possibility list creation, it is 
> possible that, for example, going from plist[0] to plist[2] may produce 
> less error-per-bit than going from plist[0] to plist[1].  The update I 
> added discards any entry which is a less-efficient use of the bit budget 
> than an entry further down the list.  Mileage varies, but I noted some 
> pretty significant quality improvements in high-action frames.
> 
> In retrospect though, given that end-result, the entire list could be 
> processed in one step, so I'll have to make a new patch with a better 
> method: Find the lowest-error possibility, if there is a tie, pick the 
> one with the fewest bits consumed, add it to the new list.  Find the 
> entry with the least error added per bit reduced, add it to the list.  
> Repeat until no more bit reductions are available.  I'll make a patch 
> for that.
> 
> 
> A major flaw with this has also been the chicken-and-egg problem of 
> codebook generation.  That is, whether motion compensation is used 
> instead of the codebook depends on how good the codebook is, but the 
> codebook would be better if it didn't use parts of the image that get 
> skipped for motion compensation.  Regenerating the codebook isn't really 
> an option, because that screws with the rate control (the size of the 
> codebook is a fairly significant factor in evaluating frame size, and 
> often a good portion of the 4x4 entries are unused).  I wouldn't say 
> that using all of the 4x4 entries is really a goal either, because 
> codebook entries are not necessarily a good use of the bit budget either.
> 
> Best option would really be to only use codebook generation if motion 
> compensation and backbuffer skip both go over error thresholds (should 
> be a separate one for each, higher threshold for SKIP versus MCOMP), but 
> picking that threshold is tricky as it can vary heavily with scene 
> complexity.  It MIGHT be possible to pick an error threshold by doing 
> two passes per frame, but I never really entertained that possibility 
> because the codebook generator is agonizingly slow.

the encoder is scary ...

ignoring the codebook generation the optimal solution is to iterate
over all possible encodings and choose the one with the lowest
rate distortion, that is distortion + lambda*bits (lambda is a constant 
for the whole frame or movie which can be used to tune quality vs. bitrate,
distortion is the sum of squared differences or something like that)

and a 2pass code book generator would be cool too, something like
encode the whole frame and then just build a codebook based on all
the blocks except the SKIP/MCOMP blocks and redo the whole encode
would need 2x as much time of course ...

[...]
-- 
Michael     GnuPG fingerprint: 9FF2128B147EF6730BADF133611EC787040B0FAB

Its not that you shouldnt use gotos but rather that you should write
readable code and code with gotos often but not always is less readable
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 189 bytes
Desc: not available
URL: <http://lists.mplayerhq.hu/pipermail/ffmpeg-devel/attachments/20070601/e8cd74a4/attachment.pgp>