CommitLineData
45e5f857
MM
1A Quick Description Of Rate Distortion Theory.
2
3We want to encode a video, picture or piece of music optimally. What does
5given filesize OR we want to get the smallest filesize at a given quality
6(in practice, these 2 goals are usually the same).
7
8Solving this directly is not practical; trying all byte sequences 1
9megabyte in length and selecting the "best looking" sequence will yield
10256^1000000 cases to try.
11
12But first, a word about quality, which is also called distortion.
13Distortion can be quantified by almost any quality measurement one chooses.
14Commonly, the sum of squared differences is used but more complex methods
15that consider psychovisual effects can be used as well. It makes no
16difference in this discussion.
17
18
19First step: that rate distortion factor called lambda...
20Let's consider the problem of minimizing:
21
22 distortion + lambda*rate
23
52760ed7
MN
24rate is the filesize
25distortion is the quality
26lambda is a fixed value choosen as a tradeoff between quality and filesize
27Is this equivalent to finding the best quality for a given max
45e5f857
MM
28filesize? The answer is yes. For each filesize limit there is some lambda
29factor for which minimizing above will get you the best quality (using your
30chosen quality measurement) at the desired (or lower) filesize.
31
32
33Second step: splitting the problem.
34Directly splitting the problem of finding the best quality at a given
35filesize is hard because we do not know how many bits from the total
36filesize should be allocated to each of the subproblems. But the formula
37from above:
38
39 distortion + lambda*rate
40
41can be trivially split. Consider:
42
43 (distortion0 + distortion1) + lambda*(rate0 + rate1)
44
45This creates a problem made of 2 independent subproblems. The subproblems
46might be 2 16x16 macroblocks in a frame of 32x16 size. To minimize:
47
48 (distortion0 + distortion1) + lambda*(rate0 + rate1)
49
50we just have to minimize:
51
52 distortion0 + lambda*rate0
53
c36264a3 54and
c36264a3 55
45e5f857
MM
56 distortion1 + lambda*rate1
57
58I.e, the 2 problems can be solved independently.
c36264a3
MN
59
60Author: Michael Niedermayer