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