An adaptive Lagrange multiplier determination method for rate-distortion optimisation in hybrid video codecs

Fan Zhang, David R. BullICIP 2015 · OpenReview

Introduction

In modern video compression standards such as H.264/AVC and HEVC, encoders must make complex decisions regarding block sizes and prediction modes. These choices are governed by Rate-Distortion Optimisation (RDO), which seeks to minimize a cost function: $J = D + \lambda R$. In this equation, $D$ represents distortion (quality loss), $R$ represents the bitrate (file size), and $\lambda$ (the Lagrange multiplier) acts as the critical weight balancing the two.

For decades, codecs have relied on a fixed formula to calculate $\lambda$ based solely on the Quantisation Parameter (QP). However, this "one-size-fits-all" approach assumes a high-bitrate environment and fails to account for the specific content of the video. Researchers from the University of Bristol have developed an adaptive method that tunes $\lambda$ dynamically, achieving significant bitrate savings with negligible computational overhead.

Proposed Adaptive Method

The core innovation of this research is an Adaptive Lagrange Multiplier Determination method. Instead of a static formula, the encoder analyzes the statistics of recently encoded frames to predict the optimal $\lambda$ for the current frame. The process follows three main steps:

  1. Scene Cut Detection: The system monitors for sudden changes in content using histogram differences. If a scene cut is detected, statistics are reset to avoid using irrelevant data from the previous scene.
  2. Distortion Tracking: The encoder maintains a weighted average of the Mean Squared Error (MSE) for both P-frames (predictive) and B-frames (bi-predictive).
  3. Power Function Mapping: The researchers discovered a strong correlation between the distortion ratio ($r_{P/B} = D_P / D_B$) and the optimal Lagrange multiplier ratio ($r_\lambda$).
Figure 2: The power function mapping between the distortion ratio ($r_{P/B}$) and the optimal Lagrange multiplier ratio ($r_\lambda$) for the HEVC codec.

As shown in Figure 2, this relationship is modeled using a three-parameter power function: $r_\lambda = a \cdot r_{P/B}^b + c$. The encoder uses this calculated $r_\lambda$ to scale the baseline Lagrange multiplier. To ensure visual stability and prevent flickering, the change in $\lambda$ is constrained to within $\pm 5\%$ between consecutive B-frames.

Datasets and Evaluation

The study utilized a diverse set of 36 video sequences across four resolution groups, ranging from CIF (352x288) to Full HD (1920x1080). The evaluation set included standard test sequences like Miss America, dynamic textures from the DynTex database, and high-quality textures from the BVI Video Texture Database.

Key Insights

  • Flaws in the High-Rate Assumption: Standard formulas for $\lambda$ assume bitrates are high enough for certain mathematical approximations to hold. The authors found that for static scenes (where "skip mode" is common) and dynamic textures (where "intra mode" is frequent), these assumptions lead to sub-optimal compression.
  • Distortion Ratio as a Proxy: Using the ratio of distortion between different frame types ($r_{P/B}$) effectively captures the predictability and complexity of a scene, allowing the encoder to adjust its quality-to-bits strategy on the fly.
  • Low Complexity: Unlike AI-based compression improvements that require significant GPU power, this is a lightweight statistical update suitable for real-time hardware encoders.

Results

The algorithm was integrated into the reference software for both H.264 (JM 15.1) and HEVC (HM 14.0). Using Bjontegaard Delta (BD-rate) measurements, the researchers observed:

  • Overall Savings: Average bitrate reductions of 4.0% for H.264 and 3.0% for HEVC.
  • Peak Performance: Some sequences achieved savings as high as 11.4%.
  • Content Sensitivity: The highest gains were found in static and dynamic texture content, proving the adaptive approach successfully addresses the weaknesses of standard models.
Figure 6: Rate-savings achieved as a function of the Lagrange multiplier ratio ($r_\lambda$) for the HEVC codec across various test sequences.

Limitations and Future Work

While the results are impressive, the authors note that current tests focused on constant Quantisation Parameters. Future work will investigate how dynamic Rate Control (varying QP) and different Group of Pictures (GOP) structures affect the $r_{P/B}$ relationship. Additionally, moving from frame-level to block-level Lagrange multiplier determination could yield even higher precision and efficiency.

Summary updated

BibTeX
@inproceedings{zhang2015adaptive,
  author = {Fan Zhang and David R. Bull},
  title = {{An adaptive Lagrange multiplier determination method for rate-distortion optimisation in hybrid video codecs}},
  booktitle = {ICIP},
  year = {2015},
  url = {https://openreview.net/forum?id=Mls9JGq30n},
}
Figure