Modeling Generalized Rate-Distortion Functions

Zhengfang Duanmu, Wentao Liu, Zhuoran Li, Zhou WangIEEE TIP 2020 · OpenReview

Abstract

Many multimedia applications require precise understanding of the rate-distortion characteristics measured by the function relating visual quality to media attributes, for which we term it the generalized rate-distortion (GRD) function. In this study, we explore the GRD behavior of compressed digital videos in a two-dimensional space of bitrate and resolution. Our analysis on a large-scale video dataset reveals that empirical parametric models are systematically biased while exhaustive search methods require excessive computation time to depict the GRD surfaces. By exploiting the properties that all GRD functions share, we develop an Robust Axial-Monotonic Clough-Tocher (RAMCT) interpolation method to model the GRD function. This model allows us to accurately reconstruct the complete GRD function of a source video content from a moderate number of measurements. To further reduce the computational cost, we present a novel sampling scheme based on a probabilistic model and an information measure. The proposed sampling method constructs a sequence of quality queries by minimizing the overall informativeness in the remaining samples. Experimental results show that the proposed algorithm significantly outperforms state-of-the-art approaches in accuracy and efficiency. Finally, we demonstrate the usage of the proposed model in three applications: rate-distortion curve prediction, per-title encoding profile generation, and video encoder comparison.

Introduction

In the world of streaming, there is no "one size fits all" setting. A high-action sports clip needs a different bitrate and resolution than a static interview to look good. Finding the optimal "bitrate ladder"—the set of resolution/bitrate pairs used by players to adapt to network conditions—is known as per-title encoding.

The video delivery chain involves multiple stages where quality can be lost, making the modeling of the final rendered video quality a complex task.

The challenge is that determining the quality of a single video at a specific bitrate and resolution requires two very expensive steps: encoding the video and running a quality assessment algorithm (like VMAF or SSIMplus). To map out the entire "quality surface" for a single clip using brute force could take hours or days. Existing mathematical models are either too rigid (parametric models that don't fit real data well) or require too much data.

Methodology

The authors propose a two-part solution to model the Generalized Rate-Distortion (GRD) function:

  1. RAMCT Interpolation: They build upon the Clough-Tocher (CT) scheme, which uses piecewise cubic polynomials to create a smooth surface over scattered data points. Crucially, they add Axial Monotonicity constraints. While increasing resolution doesn't always improve quality (e.g., at very low bitrates, a high-res video looks "mushy"), increasing bitrate always should. RAMCT ensures the mathematical model respects this physical reality.
  2. Uncertainty Sampling: Instead of picking points at random, they use a probabilistic model to represent uncertainty about the GRD surface. Their algorithm identifies which bitrate/resolution combination, if measured, would provide the most "information gain," allowing them to reconstruct the surface with minimal encodes.

Content-Awareness and Key Insights

A major finding is that the GRD surface is highly dependent on specific video content. A "talking head" video has a very steep quality climb that plateaus early, while a high-motion clip has a much shallower slope.

GRD surfaces for different video contents (a, b, c) show how the relationship between bitrate, resolution, and quality (SSIMplus) varies significantly by scene type.

By formulating the interpolation as a quadratic programming problem with monotonicity constraints, the authors ensure the model is mathematically well-behaved and physically plausible, avoiding the "wiggles" or dips in quality that standard interpolation can create as bitrate increases.

Key Results

  • Efficiency: The RAMCT model with uncertainty sampling reaches a target error threshold 100 times faster than traditional regression models.
  • Accuracy: With only 30 samples, RAMCT can reconstruct the GRD surface with significantly lower Mean Squared Error (MSE) than state-of-the-art parametric or linear models.
  • Real-World Impact: When applied to per-title encoding, the proposed framework achieved a 47% bitrate saving compared to fixed bitrate ladders while maintaining the same perceived quality.
  • Codec Comparison: The model allowed for a more "fair" comparison between codecs like H.264 and HEVC by looking at the entire surface rather than just a few points.

Future Work

Currently, the model focuses on bitrate and spatial resolution. Future work aims to incorporate frame rate and bit depth into the GRD function, turning the surface into a higher-dimensional manifold. Additionally, the researchers hope to achieve "blind prediction," where the entire GRD surface is predicted directly from raw source video features without performing any test encodes at all.

Summary updated

Abstract

Many multimedia applications require precise understanding of the rate-distortion characteristics measured by the function relating visual quality to media attributes, for which we term it the generalized rate-distortion (GRD) function. In this study, we explore the GRD behavior of compressed digital videos in a two-dimensional space of bitrate and resolution. Our analysis on a large-scale video dataset reveals that empirical parametric models are systematically biased while exhaustive search methods require excessive computation time to depict the GRD surfaces. By exploiting the properties that all GRD functions share, we develop an Robust Axial-Monotonic Clough-Tocher (RAMCT) interpolation method to model the GRD function. This model allows us to accurately reconstruct the complete GRD function of a source video content from a moderate number of measurements. To further reduce the computational cost, we present a novel sampling scheme based on a probabilistic model and an information measure. The proposed sampling method constructs a sequence of quality queries by minimizing the overall informativeness in the remaining samples. Experimental results show that the proposed algorithm significantly outperforms state-of-the-art approaches in accuracy and efficiency. Finally, we demonstrate the usage of the proposed model in three applications: rate-distortion curve prediction, per-title encoding profile generation, and video encoder comparison.
BibTeX
@article{duanmu2020modeling,
  author = {Zhengfang Duanmu and Wentao Liu and Zhuoran Li and Zhou Wang},
  title = {{Modeling Generalized Rate-Distortion Functions}},
  journal = {IEEE Trans. Image Process.},
  year = {2020},
  url = {https://openreview.net/forum?id=Rl9xKzNnCX},
}
Figure