Video compression with flexible playback order based on distributed source coding

Ngai‐Man Cheung, Huisheng Wang, Antonio OrtegaProceedings of SPIE, the International Society for Optical Engineering/Proceedings of SPIE 2006 · DOI

TL;DR

This paper tackles the challenge of enabling flexible video playback (like frame-by-frame backward playback) without the traditional high latency and memory overhead. They achieve this by framing the problem as distributed source coding, where a decoder can reconstruct a frame using either a past or future frame as side information, and introduce novel macroblock-level coding strategies to boost efficiency.

What Problem Does This Paper Address?

Current video compression standards, like MPEG and H.26X, rely on predictive coding where frames are encoded based on previously decoded frames. This rigid structure makes flexible playback, such as rewinding frame-by-frame, difficult. To support this, traditional methods might involve decoding large chunks of video (GOPs) and storing them, leading to significant delays and memory usage. Alternatively, using only intra-coded frames (independent frames) for random access drastically reduces coding efficiency. The core problem is how to enable flexible playback (e.g., backward playback, switching between views in multi-view video) without these drawbacks, especially when the decoder might have access to different "side information" (e.g., previous or next frame) depending on the playback mode, and the encoder doesn't know which will be available.

Methods

The paper's central innovation is framing flexible playback as a distributed source coding (DSC) problem. In DSC, the encoder doesn't have direct access to the decoder's "side information" (SI), but it knows the joint statistics of the source and the potential SI. This allows for efficient compression even with uncertainty about which SI will be available at the decoder.

Specifically, they propose:

  • Worst-Case Correlation Coding: The encoder generates parity bits based on the worst-case correlation between the source frame and all possible side information frames (e.g., previous and next frames for backward playback). This ensures that the frame can be reliably decoded regardless of which SI the decoder actually has.
  • Macroblock-Based Mode Switching: To further improve efficiency, they introduce novel macroblock modes within the DSC framework:
  • Inter Mode: Standard DSC is applied to compress the lowest frequency DCT coefficients.
  • Skip Mode: Portions of bit-planes are skipped if they are identical across all potential SI candidates, reducing the amount of data to be encoded. This is applied to luminance bit-planes.
  • Intra Mode: All coefficients are encoded independently, similar to traditional intra-coding.
  • Fast Algorithm for Skip Mode Selection: A computationally efficient method is proposed to determine the optimal number of bit-planes to skip for each frequency coefficient, balancing the number of skipped macroblocks with the amount of data skipped.

Datasets

The experiments were conducted using two standard video sequences:

  • Akiyo: A low-motion sequence.
  • Foreman: A high-motion sequence.

These sequences were used to evaluate the proposed method against existing techniques.

Key Insights and Ideas

  • Uncertainty as an Opportunity: Instead of treating the uncertainty of available side information as a problem, the paper leverages it by framing it within the DSC paradigm, which is inherently designed for such scenarios.
  • Worst-Case Guarantees: Encoding based on the worst-case correlation provides a robust solution that works regardless of which predictor (past or future frame) is available at the decoder, eliminating the need for the encoder to know the exact playback mode.
  • Macroblock-Level Flexibility: Applying DSC and novel modes (skip, intra) at the macroblock level allows for finer-grained adaptation to local content characteristics, leading to better compression efficiency than frame-level approaches.
  • Trade-offs in Skip Mode: The skip mode highlights a crucial trade-off: skipping more bit-planes per macroblock increases savings for those blocks but can increase the cost for other blocks due to reduced overall correlation. Finding the optimal skip level is key.

Key Results

  • Forward/Backward Playback: The proposed method achieves significant bit savings compared to intra-frame coding, especially for low-motion sequences like Akiyo (up to 40% bit saving).
  • Comparison to Inter-Frame Coding: While not outperforming traditional inter-frame coding (which requires more memory and delay for flexible playback), the proposed DSC approach offers a competitive alternative that avoids these penalties.
  • Skip Mode Effectiveness: The skip mode macroblock strategy demonstrated notable bit savings, achieving up to 32.41% saving in encoding bit-planes for Akiyo, translating to a 19.43% overall bit saving.
  • Intra Mode Value: The intra mode macroblock also showed promise, particularly for scenarios with weaker correlation (like multi-view video), offering up to 13.7% bit saving in individual frames.

Limitations and Future Work

  • Performance Gap with Inter-Frame: The paper acknowledges that their method does not achieve the same compression efficiency as traditional inter-frame coding. This is partly attributed to the overhead of including both forward and backward motion vectors and the need for lossless encoding to avoid drift.
  • Channel Code Design: The authors suggest that performance could be improved by using more sophisticated channel models.
  • Multiple Skip Modes: They are exploring techniques to design multiple skip modes to better handle variations in spatial correlation across different macroblocks.
  • Generalization: While forward/backward decoding is used as a primary example, the authors note that the core idea can be easily generalized to other flexible playback scenarios, such as switching between multiple views in multiview video coding.

Summary updated

Abstract

Some emerging applications may require flexible playback features for time-based media, such as video, that cannot be directly supported by current compression standards, because for these decoding of frames can only be done in a predetermined order. An example would be a video application where both backward and forward frame-by-frame playback are to be supported. A standard codec could support this by decoding complete GOPs in the desired order, and then playing back one frame at a time. Thus, potentially significant added delay and memory are needed to support backward playback, which can be lowered if small GOP sizes are chosen, at the cost of reduced coding efficiency. Other example applications where flexible playback may be desirable include switching between different views in multiview video coding, and accessing individual spectral bands in hyperspectral imagery. In this work we address flexible playback by showing that it becomes feasible when a particular data unit (e.g., a video frame) can be decoded using information from <i>either</i> one of a number of other data units (e.g., in the video case the next frame or the previous frame). Note that this is different from structures such as bi-directionally predicted frames, which require <i>both</i> predictor frames to be available at the decoder. We cast this problem as one of source coding with uncertainty about decoder side-information and propose a solution based on distributed source coding. In addition, we propose macroblock-based mode switching algorithms in the context of distributed video coding to improve coding efficiency. Our results show that, using forward/backward playback as an example, our proposed solution can achieve good coding efficiency without incurring additional delay and memory overhead.
BibTeX
@inproceedings{cheung2006video,
  author = {Ngai‐Man Cheung and Huisheng Wang and Antonio Ortega},
  title = {{Video compression with flexible playback order based on distributed source coding}},
  booktitle = {Proceedings of SPIE, the International Society for Optical Engineering/Proceedings of SPIE},
  year = {2006},
  doi = {10.1117/12.673684},
}

Loading related content...

Figure