1A Quick Description Of Rate Distortion Theory. 2 3We 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 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 24rate is the filesize 25distortion is the quality 26lambda is a fixed value chosen as a tradeoff between quality and filesize 27Is this equivalent to finding the best quality for a given max 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 54and 55 56 distortion1 + lambda*rate1 57 58I.e, the 2 problems can be solved independently. 59 60Author: Michael Niedermayer 61Copyright: LGPL 62