Low-complexity Scaling Methods for DCT-II Approximations

Diego F. G. Coelho, Renato J. Cintra, Arjuna Madanayake, Sirani M. Perera

TL;DR

This paper presents a novel framework for creating efficient, low-complexity approximations of the Discrete Cosine Transform (DCT-II), crucial for image and video compression. By developing new "scaling" methods based on existing DCT-II approximations, they achieve better performance (lower error) and comparable or improved hardware efficiency compared to prior state-of-the-art techniques, including the widely used JAM method.

What Problem Does This Paper Address?

The Discrete Cosine Transform (DCT-II) is a cornerstone of modern image and video compression codecs (like H.264/AVC and HEVC). However, computing the exact DCT-II can be computationally expensive, especially for larger block sizes (e.g., 16- and 32-point transforms) required by newer standards. This drives the need for "approximate transforms" that offer similar compression quality with significantly reduced computational cost, particularly for hardware implementations where energy efficiency is paramount. While previous work has focused on 8-point DCT-II approximations, scaling these to larger block sizes presents a challenge due to the quadratic increase in complexity. Existing scaling methods, like the JAM method, are functional but lack a solid mathematical foundation and can introduce their own errors. This paper aims to bridge this gap by providing a mathematically justified framework for generating low-complexity DCT-II approximations for larger block sizes.

Methods

The core of this paper lies in a new framework for "scaling" existing $N$-point DCT-II approximations to generate $2N$-point approximations. This is achieved by leveraging the Hou recursive matrix factorization of the exact $2N$-point DCT-II matrix. The authors introduce a general scaling method, of which the JAM scaling method is identified as a specific instance. They provide a mathematical derivation and justification for this scaling process, which involves decomposing the $2N$-point DCT-II matrix into smaller blocks and using parameter matrices ($B_N$ and $G_N$) to construct the approximations.

Key methodological contributions include:

  • Mathematical Justification for Scaling: Providing a rigorous derivation for the DCT-II approximation scaling process, addressing a perceived gap in prior work.
  • A Family of Scaling Methods: Introducing a flexible framework that allows for the generation of multiple DCT-II approximations by selecting different parameter matrices ($B_N$ and $G_N$).
  • Orthogonality Conditions: Deriving conditions under which the generated approximate DCT-II matrices are orthogonal, a desirable property for signal processing applications.
  • Error and Performance Analysis: Conducting extensive statistical simulations and performance measurements to compare the proposed methods against the JAM method and other existing approximations.
  • Hardware Implementation: Demonstrating the practical viability of the proposed methods through FPGA implementation.

Datasets

Not discussed in the paper. The paper focuses on theoretical development and evaluation using synthetic data and existing transform approximations.

Key Insights and Ideas

  • Scaling as a General Principle: The paper demonstrates that scaling existing DCT-II approximations is a powerful and generalizable technique for creating efficient transforms for larger block sizes.
  • Mathematical Rigor for Approximations: By providing a solid mathematical foundation for the scaling process, the authors build confidence in the reliability and predictability of their proposed methods.
  • Trade-offs in Approximation Design: The choice of parameter matrices ($B_N$ and $G_N$) directly influences the trade-off between approximation error and computational complexity, allowing for tailored solutions.
  • Outperforming Existing Methods: The proposed methods, particularly VI and VII, show a consistent advantage over the JAM method in terms of error metrics, even when starting with various well-established 8-point DCT-II approximations.
  • Hardware Efficiency: The proposed scaling methods, when implemented on FPGAs, demonstrate competitive or superior performance in terms of resource utilization and operating frequency compared to the JAM method.

Key Results

  • Error Reduction: Methods VI and VII consistently outperform the JAM scaling method in terms of Frobenius norm error, even for larger block sizes (16 and 32 points). For instance, they show lower errors across various tested 8-point DCT-II approximations.
  • Coding Performance: Methods VI and VII also outperform the JAM method in terms of total error energy. Methods I, II, and III show comparable coding performance to the JAM method.
  • Hardware Metrics:
    • Method VII uses the least number of flip-flops (FFs) and achieves a high maximum operating frequency.
  • Method I achieves the lowest critical path delay, leading to high operating frequencies.
  • Method I also demonstrates the most efficient implementation in terms of dynamic power, with a reduction of 7.58% compared to the JAM implementation.
  • Arithmetic Complexity: The proposed scaling methods do not incur higher arithmetic complexity than the JAM scaling method, as they are designed to be multiplierless.

Limitations and Future Work

  • Limitations:
    • The paper focuses on 2N-point approximations derived from N-point ones. While effective, it doesn't explore all possible scaling strategies.
  • The orthogonality conditions derived are sufficient but not always necessary, meaning some non-orthogonal approximations might still be useful.
  • Future Work:
    • Investigating alternative DCT-II and DCT-IV relationships for deriving new scaling methods with potentially higher sparsity.
  • Analyzing the behavior of the proposed DCT-II approximations after multiple recursive applications of the scaling process.
  • Exploring matrix parameterizations based on generalizations of existing algorithms to further enhance sparsity and efficiency.

Summary updated

Abstract

This paper introduces a collection of scaling methods for generating $2N$-point DCT-II approximations based on $N$-point low-complexity transformations. Such scaling is based on the Hou recursive matrix factorization of the exact $2N$-point DCT-II matrix. Encompassing the widely employed Jridi-Alfalou-Meher scaling method, the proposed techniques are shown to produce DCT-II approximations that outperform the transforms resulting from the JAM scaling method according to total error energy and mean squared error. Orthogonality conditions are derived and an extensive error analysis based on statistical simulation demonstrates the good performance of the introduced scaling methods. A hardware implementation is also provided demonstrating the competitiveness of the proposed methods when compared to the JAM scaling method.
BibTeX
@article{coelho2021low,
  author = {Diego F. G. Coelho and Renato J. Cintra and Arjuna Madanayake and Sirani M. Perera},
  title = {{Low-complexity Scaling Methods for DCT-II Approximations}},
  journal = {IEEE Trans. Signal Process.},
  year = {2021},
  url = {https://openreview.net/forum?id=_a_oKVgfeAf},
}

Loading related content...

Figure