Pattern-based integer sample motion search strategies in the context of HEVC

Georg Maier, Benjamin Bross, Dan Grois, Detlev Marpe, Heiko Schwarz, Remco C. Veltkamp, Thomas WiegandProceedings of SPIE, the International Society for Optical Engineering/Proceedings of SPIE 2015 · DOI

TL;DR

This paper introduces a flexible framework for integer sample motion estimation (ME) in HEVC video compression, aiming to significantly reduce computational complexity without a drastic loss in coding efficiency. By combining and optimizing various predictive, pattern-based, and early termination techniques, they achieve speedups of up to 7.6x for high-resolution sequences with minimal bit-rate overhead.

What Problem Does This Paper Address?

The HEVC (H.265) standard offers substantial improvements in video compression efficiency over its predecessor (H.264/AVC), but this comes at the cost of significantly higher computational demands for encoders. A major bottleneck is the motion estimation (ME) process, which is crucial for exploiting temporal redundancy between video frames. While HEVC supports fractional sample ME for higher accuracy, the integer sample ME stage remains a critical component. Existing fast ME algorithms often struggle to balance computational speed with coding efficiency, risking either excessive bit-rate overhead or getting trapped in suboptimal motion vector predictions. This paper addresses the need for a fast yet efficient integer sample ME strategy that can be adapted to different application requirements, particularly for real-time or low-delay scenarios.

Methods

The authors propose a modular integer sample ME framework for HEVC. This framework is built upon the Modified Diamond Search (MDS) algorithm and incorporates several key strategies:

  • Search Center and Motion Vector Predictors (MVPs): Instead of a zero-biased starting point, the search begins from the MVP selected by HEVC's Advanced Motion Vector Prediction (AMVP) mechanism. This MVP is augmented with spatial and temporal neighbors to form a set of predictors that guide the search.
  • Initial Search Patterns: The framework evaluates and combines various initial search patterns, including Quarter Sparse Diamond (QSD) and Half Sparse Diamond (HSD) patterns. A novel approach involves adaptively scaling these patterns based on the expected motion size and simplifying their selection by considering predictor quadrants.
  • Repeating Search Patterns: For continued searching, the paper considers small diamond patterns, rotating diamond patterns, and rotating hexagonal patterns, evaluating their trade-offs in complexity and effectiveness.
  • Early Termination Thresholds: To further accelerate the process, several adaptive early termination criteria are implemented. These include:
  • Zero Motion Prejudgement (ZMP): Quickly terminating the search if zero motion is highly probable.
  • Expected Motion Size-Based Threshold: Conditionally executing the initial search pattern based on the predicted motion magnitude.
  • Predictive MV Costs-Based Threshold: Terminating the search early if the cost of the initial search is already better than the predicted costs.

The proposed framework allows for flexible combinations of these techniques, enabling experimentation to find optimal trade-offs.

Datasets

The evaluation was conducted using sequences from the HEVC Common Test Conditions (CTC) standard. These sequences are categorized into different classes based on their resolution and content:

  • Class A: High resolution (2660x1600)
  • Class B: High resolution (1920x1080)
  • Class C: Medium resolution (832x480)
  • Class D: Low resolution (416x240)
  • Class E: High definition (1280x720), representing typical video conferencing content (low motion activity).
  • Class F: High definition (1280x720) and lower resolution (1024x768), primarily consisting of Computer-Generated Imagery (CGI) content.

The experiments utilized two HEVC configurations: Random Access (RA) and Low Delay P (LDP).

Key Insights and Ideas

  • MVP as a Strong Starting Point: Using the AMVP-selected MVP as the search center significantly improves efficiency compared to simpler zero-biased approaches.
  • Adaptive Pattern Scaling is Beneficial: Scaling search patterns based on the estimated motion size helps to better cover larger displacements and adapt to varying motion characteristics.
  • Early Termination is Crucial for Speed: Implementing intelligent early termination strategies, particularly ZMP and cost-based thresholds, is key to achieving substantial speedups.
  • Trade-offs are Inevitable but Manageable: While fast search algorithms inherently involve some loss in coding efficiency (bit-rate overhead), the proposed framework demonstrates that these losses can be kept minimal for many sequences, especially for high-resolution content.
  • Content Matters: CGI sequences (Class F) present a greater challenge, leading to higher bit-rate overheads, likely due to their less predictable and often unnatural motion patterns.

Key Results

The proposed integer sample ME framework achieved significant speedups with acceptable bit-rate overheads:

  • High Resolution Sequences: Speedups ranging from 3.2x to 7.6x were observed for high-resolution sequences (Class A and B) in LDP configuration, with a bit-rate overhead of 0.6%. For RA configuration, speedups of 1.5x to 3.2x were achieved with a bit-rate overhead of 1.5%.
  • CGI Content: For sequences with CGI content (Class F), similar speedups were observed, but with a higher bit-rate overhead, reaching up to 5.2%.
  • Comparison to HM Fast Search: The proposed algorithm generally outperformed the native fast search algorithm in HM 12.0 in terms of the speedup-to-BD-rate trade-off, especially for LDP configurations.
  • MDS Comparison: The proposed algorithm also showed improvements over the original Modified Diamond Search (MDS) algorithm in terms of speedup and BD-rate.

Limitations and Future Work

  • Limitations:
    • The paper acknowledges that for CGI sequences (Class F), the bit-rate overhead can be higher.
  • The RA configuration generally shows higher bit-rate losses compared to LDP.
  • The performance trade-off is influenced by the resolution of the test sequences, with higher resolutions generally yielding better results.
  • Future Work:
    • The authors suggest developing a "model kit" of the presented search options. This kit would allow for adaptive selection of the best strategy based on specific video sequences and application constraints (e.g., prioritizing speed over efficiency in low-delay scenarios, or vice-versa).
  • Further research could explore more sophisticated methods for selecting strategies based on real-time analysis of video content and available computational resources.

Summary updated

Abstract

The H.265/MPEG-H High Efficiency Video Coding (HEVC) standard provides a significant increase in coding efficiency compared to its predecessor, the H.264/MPEG-4 Advanced Video Coding (AVC) standard, which however comes at the cost of a high computational burden for a compliant encoder. Motion estimation (ME), which is a part of the inter-picture prediction process, typically consumes a high amount of computational resources, while significantly increasing the coding efficiency. In spite of the fact that both H.265/MPEG-H HEVC and H.264/MPEG-4 AVC standards allow processing motion information on a fractional sample level, the motion search algorithms based on the integer sample level remain to be an integral part of ME. In this paper, a flexible integer sample ME framework is proposed, thereby allowing to trade off significant reduction of ME computation time versus coding efficiency penalty in terms of bit rate overhead. As a result, through extensive experimentation, an integer sample ME algorithm that provides a good trade-off is derived, incorporating a combination and optimization of known predictive, pattern-based and early termination techniques. The proposed ME framework is implemented on a basis of the HEVC Test Model (HM) reference software, further being compared to the state-of-the-art fast search algorithm, which is a native part of HM. It is observed that for high resolution sequences, the integer sample ME process can be speed-up by factors varying from 3.2 to 7.6, resulting in the bit-rate overhead of 1.5% and 0.6% for Random Access (RA) and Low Delay P (LDP) configurations, respectively. In addition, the similar speed-up is observed for sequences with mainly Computer-Generated Imagery (CGI) content while trading off the bit rate overhead of up to 5.2%.
BibTeX
@inproceedings{maier2015pattern,
  author = {Georg Maier and Benjamin Bross and Dan Grois and Detlev Marpe and Heiko Schwarz and Remco C. Veltkamp and Thomas Wiegand},
  title = {{Pattern-based integer sample motion search strategies in the context of HEVC}},
  booktitle = {Proceedings of SPIE, the International Society for Optical Engineering/Proceedings of SPIE},
  year = {2015},
  doi = {10.1117/12.2193679},
}
Figure