## ffmpeg / doc / rate_distortion.txt @ 4dcde00c

History | View | Annotate | Download (2.05 KB)

1 | 45e5f857 | Mike Melanson | 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 | 52760ed7 | Michael Niedermayer | 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 |
||

28 | 45e5f857 | Mike Melanson | 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 | c36264a3 | Michael Niedermayer | and |

55 | |||

56 | 45e5f857 | Mike Melanson | distortion1 + lambda*rate1 |

57 | |||

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

59 | c36264a3 | Michael Niedermayer | |

60 | Author: Michael Niedermayer |
||

61 | Copyright: LGPL |