Signal-Independent Separable KLT by Offline Training for Video Coding

Kui Fan, Ronggang Wang, Weisi Lin, Ling-Yu Duan, Wen Gao

Introduction

In video compression, the transform stage is critical for reducing spatial redundancy. By converting spatial pixel residuals—the difference between a predicted block and the actual block—into frequency coefficients, codecs can efficiently discard less important data. While the Discrete Cosine Transform (DCT-II) is the current industry standard, the Karhunen-Loève Transform (KLT) is theoretically the optimal linear transform due to its ability to perfectly decorrelate a signal.

Despite its theoretical advantages, traditional KLT has historically been impractical for real-world video codecs due to two primary issues: signal dependency and non-separability. Signal dependency typically requires "online training," where the encoder calculates a new transform matrix for every block, a process that is computationally prohibitive. Furthermore, traditional KLT treats an $N \times N$ block as a single $N^2$ vector, leading to massive matrix sizes (e.g., $256 \times 256$ for a $16 \times 16$ block) that demand excessive memory and processing power.

Proposed Method: Signal-Independent Separable KLT

To bridge the gap between KLT’s optimality and the practical constraints of the Versatile Video Coding (VVC) standard, researchers have proposed a Signal-Independent Separable KLT. This approach integrates into the standard coding pipeline as an alternative transform path.

Integration of KLT and Inverse KLT into the VVC transform pipeline as alternatives to standard DCT/DST.

The proposed framework relies on three core innovations:

  1. Separability: Instead of applying one massive matrix to the entire block, the transform is applied to rows and columns separately. For a $16 \times 16$ block, this reduces the matrix size from $256 \times 256$ to just $16 \times 16$, drastically lowering computational complexity.
  2. Offline Training: To eliminate the need for real-time calculation, transform matrices are trained offline using a massive dataset of residuals. This creates "universal" matrices that generalize across different video content.
  3. Implementation Efficiency: To prevent encoder-decoder drift caused by rounding errors, floating-point matrices are converted into fixed-point integers. The implementation also leverages SIMD (Single Instruction, Multiple Data) instructions to accelerate matrix multiplications.

Targeted Inter-Coding and Residual Selection

For Inter-coded (motion-compensated) blocks, KLT often produces results similar to DCT-II. To ensure KLT provides a meaningful benefit, the authors introduced a "Residual Selection" strategy. Instead of training on all residuals, they used a parameter ($\alpha$) to select only high-distortion residuals—those that DCT-II handles poorly. This teaches the KLT to act as a specialist for cases where the generalist DCT-II fails.

Impact of the residual selection parameter α on BD-rate performance, showing improved bitrate savings as α increases.

As shown in the experimental data, tuning the $\alpha$ parameter allows for the optimization of the BD-rate (Bjøntegaard Delta rate). Higher values of $\alpha$ focus the training on residuals that are most difficult to compress, leading to better overall coding efficiency.

Experimental Results

The proposed method was evaluated against the VVC reference software (VTM-1.1) using standard JVET test sequences not seen during the training phase.

  • Bitrate Savings: The method achieved an average of 2.7% bitrate saving in "All Intra" (AI) mode and 1.5% in "Random Access" (RA) mode. Some 4K sequences reached peak savings of up to 3.9%.
  • Complexity Trade-offs: While encoding time approximately doubled in AI mode due to the additional transform options the encoder must evaluate, the decoding time only increased by 1-4%. This minimal impact on decoding is crucial for consumer devices like smartphones and televisions.

Conclusion

By combining offline training with a separable matrix approach, this research demonstrates that a practical, signal-independent KLT can significantly improve video coding efficiency. While encoding complexity remains a challenge for real-time applications, the substantial bitrate savings and low decoding overhead make it a promising candidate for future standard enhancements. Future work will likely focus on fast-decision algorithms to reduce encoder search time and extending the technique to chroma components.

Summary updated

Abstract

After the works on High Efficiency Video Coding (HEVC) standard, the standard organizations continued to study the next generation of video coding standard, named Versatile Video Coding (VVC). The compression capacity of the VVC standard is expected to be substantially improved relative to the current HEVC standard by evolving the potential coding tools greatly. Transform is a key technique for compression efficiency, and core experiment 6 (CE6) in JVET is established to explore the transform-related coding tools. In this paper, we propose a novel signal-independent separable transform based on the Karhunen-Loève transform (KLT) to improve the efficiency of both intra and inter residual coding. In the proposed method, the drawbacks of the traditional KLT are addressed. A group of mode-independent intra transform matrices is calculated from abundant intra residual samples of all intra modes, while the inter separable KLT matrices are trained with the residuals that cannot be efficiently processed by the discrete cosine transform type II (DCT-II). The separable KLT is developed as an additional transform type apart from DCT-II. The experimental results show that the proposed method can achieve 2.7% and 1.5% bitrate saving averagely under All Intra and Random Access configurations on top of the reference software of VVC (VTM-1.1). In addition, the consistent performance improvement on test set also validates the property of signal independency and the strong generalization capacity of the proposed separable KLT.
BibTeX
@article{fan2019signal,
  author = {Kui Fan and Ronggang Wang and Weisi Lin and Ling-Yu Duan and Wen Gao},
  title = {{Signal-Independent Separable KLT by Offline Training for Video Coding}},
  journal = {IEEE Access},
  year = {2019},
  doi = {10.1109/access.2019.2903734},
}
Figure