XGitUrl: 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