nest-open-source / nest-android-app / ffmpeg / 8e1cc55b733ae723de9931f20a13731bed8162f5 / . / doc / rate_distortion.txt

A Quick Description Of Rate Distortion Theory. | |

We want to encode a video, picture or piece of music optimally. What does | |

"optimally" really mean? It means that we want to get the best quality at a | |

given filesize OR we want to get the smallest filesize at a given quality | |

(in practice, these 2 goals are usually the same). | |

Solving this directly is not practical; trying all byte sequences 1 | |

megabyte in length and selecting the "best looking" sequence will yield | |

256^1000000 cases to try. | |

But first, a word about quality, which is also called distortion. | |

Distortion can be quantified by almost any quality measurement one chooses. | |

Commonly, the sum of squared differences is used but more complex methods | |

that consider psychovisual effects can be used as well. It makes no | |

difference in this discussion. | |

First step: that rate distortion factor called lambda... | |

Let's consider the problem of minimizing: | |

distortion + lambda*rate | |

rate is the filesize | |

distortion is the quality | |

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

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

filesize? The answer is yes. For each filesize limit there is some lambda | |

factor for which minimizing above will get you the best quality (using your | |

chosen quality measurement) at the desired (or lower) filesize. | |

Second step: splitting the problem. | |

Directly splitting the problem of finding the best quality at a given | |

filesize is hard because we do not know how many bits from the total | |

filesize should be allocated to each of the subproblems. But the formula | |

from above: | |

distortion + lambda*rate | |

can be trivially split. Consider: | |

(distortion0 + distortion1) + lambda*(rate0 + rate1) | |

This creates a problem made of 2 independent subproblems. The subproblems | |

might be 2 16x16 macroblocks in a frame of 32x16 size. To minimize: | |

(distortion0 + distortion1) + lambda*(rate0 + rate1) | |

we just have to minimize: | |

distortion0 + lambda*rate0 | |

and | |

distortion1 + lambda*rate1 | |

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

Author: Michael Niedermayer | |

Copyright: LGPL |