Multihypothesis prediction using decoder side-motion vector derivation in inter-frame video coding

Steffen Kamp, Johannes Ballé, M WienProceedings of SPIE, the International Society for Optical Engineering/Proceedings of SPIE 2008 · DOI

TL;DR

This paper introduces a novel video coding technique that significantly reduces bitrate by deriving motion vectors at the decoder using template matching, rather than explicitly encoding them. This "decoder-side motion vector derivation" (DMVD) enables efficient multihypothesis prediction, leading to an average bitrate reduction of 7.7% compared to H.264/AVC, with further gains by exploiting and mitigating sub-pixel interpolation rounding errors.

What Problem Does This Paper Address?

Video compression relies heavily on inter-frame prediction, where information from previous frames is used to predict current frames. This prediction is guided by motion vectors (MVs) that describe how blocks of pixels have moved. Traditionally, these MVs are meticulously estimated by the encoder and then transmitted to the decoder, which adds to the overall bitrate. While multihypothesis prediction (combining multiple predictions) can improve coding efficiency, the cost of encoding additional MVs limits its practical application. This paper tackles the challenge of achieving the benefits of multihypothesis prediction without the bitrate overhead of explicit MV transmission.

Methods

The core innovation is Decoder-Side Motion Vector Derivation (DMVD). Instead of sending MVs, the encoder signals that the decoder should derive them. This is achieved using template matching (TM). For a target block in the current frame, the decoder searches for a similar "template" region in previously decoded reference frames. The displacement of the best matching template is then used as the motion vector.

This DMVD approach is extended to multihypothesis prediction. Instead of just finding the single best matching template, the system identifies the L best matching templates. These L motion vectors are then used to generate L prediction signals, which are averaged to form the final prediction. A key advantage is that the computational complexity of finding the L best matches is similar to finding just one, and no extra bitrate is needed to signal these additional MVs, only a single flag per block.

Furthermore, the paper investigates and exploits rounding effects in H.264/AVC's sub-pixel interpolation. The authors derive the expected rounding error introduced by the standard's interpolation filters and propose a method to partially equalize this error by adjusting a rounding offset in the multihypothesis averaging process. They also evaluate the impact of an improved interpolation filter that minimizes rounding errors.

Datasets

The paper uses standard video sequences for evaluation, including:

  • Foreman, Mobile, Tempete (CIF, 30 Hz)
  • Paris (CIF, 15 Hz)
  • BigShips, ShuttleStart, City, Crew, Night (720p, 60 Hz, 150 frames)
  • Rolling Tomatoes (1080p, 60 Hz, 60 frames)

These are standard sequences used in VCEG (Video Coding Experts Group) common conditions for coding efficiency experiments. No new datasets were introduced.

Key Insights and Ideas

  • Decoupling MV transmission from prediction: The most significant insight is that motion information can be derived at the decoder without explicit transmission, unlocking the potential of advanced prediction techniques like multihypothesis prediction without bitrate penalty.
  • Template matching as a decoder-side MV source: TM proves to be a viable and efficient method for deriving MVs at the decoder, leveraging spatial and temporal correlations.
  • Exploiting rounding errors: The paper demonstrates that the inherent rounding errors in H.264/AVC's sub-pixel interpolation are not just artifacts but can be a source of performance gain when intelligently handled in a multihypothesis framework.
  • Multihypothesis averaging as an error equalizer: Averaging multiple predictions, especially when combined with a carefully chosen rounding offset, can mitigate the negative impact of sub-pixel interpolation rounding errors, leading to cleaner predictions.

Key Results

  • The proposed DMVD with multihypothesis prediction achieved an average bitrate reduction of 7.7% compared to the unmodified H.264/AVC reference software.
  • Peak bitrate reductions of up to 17% were observed for specific sequences (e.g., City).
  • When using an improved interpolation filter that minimizes rounding errors, the proposed scheme still achieved an average bitrate reduction of 4.7%.
  • The impact of the rounding offset U was significant: using U=0 (downward rounding) yielded better results than U=1/2 (rounding half-way cases away from zero) with the original H.264/AVC interpolation filter.

Limitations and Future Work

  • Decoder Complexity: While the encoder complexity is not significantly increased, the decoder's template matching search adds computational load. The paper notes that the search range is limited to mitigate this.
  • Error Resilience: The paper briefly mentions that disabling DMVD for P-Skip macroblocks was done to ensure fully parsable bitstreams even with lost slices. However, the impact of transmission errors on DMVD-derived MVs is acknowledged as a subject for further research.
  • Optimized Interpolation Filter: The paper implements an improved interpolation filter that reduces rounding errors. Future work could explore further optimization of this filter or other methods to address sub-pixel interpolation artifacts.
  • Rate-Distortion Optimization: The encoder makes a rate-distortion optimized decision on whether to use DMVD or explicit MV coding. Further refinement of this decision-making process could yield even better results.

Summary updated

Abstract

In this paper, a multihypothesis prediction scheme for inter frame video coding is proposed. Using a template matching algorithm, motion vectors are derived at the decoder side instead of explicitly coding the motion vectors into the bitstream. Therefore, higher numbers of hypotheses can be used in the averaging process at no additional coding cost. The proposed scheme has been implemented into the H.264/AVC reference software. Simulation results show bitrate reductions compared to H.264/AVC of 7.7% on average for the tested video sequences. It is shown that part of the performance gain is due to rounding effects in H.264/AVC sub-pixel interpolation which can be exploited in the averaging calculation of the proposed multihypothesis prediction. Experiments with an improved interpolation filter for both reference scheme and the proposed scheme still yield bitrate reductions of 4.7% on average.
BibTeX
@inproceedings{kamp2008multihypothesis,
  author = {Steffen Kamp and Johannes Ballé and M Wien},
  title = {{Multihypothesis prediction using decoder side-motion vector derivation in inter-frame video coding}},
  booktitle = {Proceedings of SPIE, the International Society for Optical Engineering/Proceedings of SPIE},
  year = {2008},
  doi = {10.1117/12.805923},
}
Figure