X-Git-Url: http://git.ffmpeg.org/gitweb/ffmpeg.git/blobdiff_plain/c36264a3537b932ea3220838a43e81d63b6cc2f1..bee694bc4ce2bb25afc50d5d885fab41c990909f:/doc/rate_distortion.txt diff --git a/doc/rate_distortion.txt b/doc/rate_distortion.txt index 2706393..a7d2c87 100644 --- a/doc/rate_distortion.txt +++ b/doc/rate_distortion.txt @@ -1,50 +1,61 @@ -A quick description of Rate distortion theory. - -We want to encode a video, picture or music optimally. -What does optimally mean? -It means that we want to get the best quality at a given -filesize OR (which is almost the same actually) We want to get the -smallest filesize at a given quality. - -Solving this directly isnt practical, try all byte sequences -1MB long and pick the best looking, yeah 256^1000000 cases to try ;) - -But first a word about Quality also called distortion, this can -really be almost any quality meassurement one wants. Commonly the -sum of squared differenes is used but more complex things that -consider psychivisual effects can be used as well, it makes no differnce -to us here. - - -First step, that RD factor called lambda ... -Lets consider the problem of minimizing - -distortion + lambda*rate - -for a fixed lambda, rate here would be the filesize, distortion the quality -Is this equivalent to finding the best quality for a given max filesize? -The awnser is yes, for each filesize limit there is some lambda factor for -which minimizing above will get you the best quality (in your provided quality -meassurement) at that (or a lower) filesize - - -Second step, spliting the problem. -Directly spliting the problem of finding the best quality at a given filesize -is hard because we dont know how much filesize to assign to each of the -subproblems optimally. -But distortion + lambda*rate can trivially be split -just consider -(distortion0 + distortion1) + lambda*(rate0 +rate1) -a problem made of 2 independant subproblems, the subproblems might be 2 -16x16 macroblocks in a frame of 32x16 size. -to minimize -(distortion0 + distortion1) + lambda*(rate0 +rate1) -one just have to minimize -distortion0 + lambda*rate0 +A Quick Description Of Rate Distortion Theory. + +We want to encode a video, picture or piece of music optimally. What does +"optimally" really mean? It means that we want to get the best quality at a +given filesize OR we want to get the smallest filesize at a given quality +(in practice, these 2 goals are usually the same). + +Solving this directly is not practical; trying all byte sequences 1 +megabyte in length and selecting the "best looking" sequence will yield +256^1000000 cases to try. + +But first, a word about quality, which is also called distortion. +Distortion can be quantified by almost any quality measurement one chooses. +Commonly, the sum of squared differences is used but more complex methods +that consider psychovisual effects can be used as well. It makes no +difference in this discussion. + + +First step: that rate distortion factor called lambda... +Let's consider the problem of minimizing: + + distortion + lambda*rate + +rate is the filesize +distortion is the quality +lambda is a fixed value choosen as a tradeoff between quality and filesize +Is this equivalent to finding the best quality for a given max +filesize? The answer is yes. For each filesize limit there is some lambda +factor for which minimizing above will get you the best quality (using your +chosen quality measurement) at the desired (or lower) filesize. + + +Second step: splitting the problem. +Directly splitting the problem of finding the best quality at a given +filesize is hard because we do not know how many bits from the total +filesize should be allocated to each of the subproblems. But the formula +from above: + + distortion + lambda*rate + +can be trivially split. Consider: + + (distortion0 + distortion1) + lambda*(rate0 + rate1) + +This creates a problem made of 2 independent subproblems. The subproblems +might be 2 16x16 macroblocks in a frame of 32x16 size. To minimize: + + (distortion0 + distortion1) + lambda*(rate0 + rate1) + +we just have to minimize: + + distortion0 + lambda*rate0 + and -distortion1 + lambda*rate1 -aka the 2 problems can be solved independantly + distortion1 + lambda*rate1 + +I.e, the 2 problems can be solved independently. Author: Michael Niedermayer Copyright: LGPL