Commit | Line | Data |
---|---|---|

45e5f857 MM |
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 | ||

52760ed7 MN |
24 | rate is the filesize |

25 | distortion is the quality | |

26 | lambda is a fixed value choosen as a tradeoff between quality and filesize | |

27 | Is this equivalent to finding the best quality for a given max | |

45e5f857 MM |
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 | ||

c36264a3 | 54 | and |

c36264a3 | 55 | |

45e5f857 MM |
56 | distortion1 + lambda*rate1 |

57 | ||

58 | I.e, the 2 problems can be solved independently. | |

c36264a3 MN |
59 | |

60 | Author: Michael Niedermayer | |

61 | Copyright: LGPL |