## ffmpeg / doc / rate_distortion.txt @ 6785e927

History | View | Annotate | Download (2.05 KB)

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