git.sesse.net Git - ffmpeg/blob - doc/rate_distortion.txt

   1 A quick description of Rate distortion theory.
   2
   3 We want to encode a video, picture or music optimally.
   4 What does optimally mean?
   5 It means that we want to get the best quality at a given
   6 filesize OR (which is almost the same actually) We want to get the
   7 smallest filesize at a given quality.
   8
   9 Solving this directly isnt practical, try all byte sequences
  10 1MB long and pick the best looking, yeah 256^1000000 cases to try ;)
  11
  12 But first a word about Quality also called distortion, this can
  13 really be almost any quality meassurement one wants. Commonly the
  14 sum of squared differenes is used but more complex things that
  15 consider psychivisual effects can be used as well, it makes no differnce
  16 to us here.
  17
  18
  19 First step, that RD factor called lambda ...
  20 Lets consider the problem of minimizing
  21
  22 distortion + lambda*rate
  23
  24 for a fixed lambda, rate here would be the filesize, distortion the quality
  25 Is this equivalent to finding the best quality for a given max filesize?
  26 The awnser is yes, for each filesize limit there is some lambda factor for
  27 which minimizing above will get you the best quality (in your provided quality
  28 meassurement) at that (or a lower) filesize
  29
  30
  31 Second step, spliting the problem.
  32 Directly spliting the problem of finding the best quality at a given filesize
  33 is hard because we dont know how much filesize to assign to each of the
  34 subproblems optimally.
  35 But distortion + lambda*rate can trivially be split
  36 just consider
  37 (distortion0 + distortion1) + lambda*(rate0 +rate1)
  38 a problem made of 2 independant subproblems, the subproblems might be 2
  39 16x16 macroblocks in a frame of 32x16 size.
  40 to minimize
  41 (distortion0 + distortion1) + lambda*(rate0 +rate1)
  42 one just have to minimize
  43 distortion0 + lambda*rate0
  44 and
  45 distortion1 + lambda*rate1
  46
  47 aka the 2 problems can be solved independantly
  48
  49 Author: Michael Niedermayer
  50 Copyright: LGPL