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