Low-Complexity Scaling Methodsfor DCT-II Approximations

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

TL;DR

This paper presents a novel framework for generating low-complexity approximations of the 2N-point Discrete Cosine Transform (DCT-II) from existing N-point approximations. These new methods, derived from a recursive matrix factorization, offer improved accuracy and comparable or better hardware efficiency compared to existing techniques like the JAM scaling method, making them suitable for energy-constrained applications like image and video compression.

What Problem Does This Paper Address?

The Discrete Cosine Transform (DCT), particularly the DCT-II, is a cornerstone of modern image and video compression codecs. While efficient algorithms exist for smaller block sizes (like 8x8), the increasing demand for higher compression ratios and energy efficiency in modern codecs (e.g., HEVC) necessitates the use of larger block sizes (16x16, 32x32) and low-complexity, often approximate, transforms. Designing these approximate transforms for larger block sizes is computationally challenging due to the quadratic increase in variables. Existing scaling methods, like the JAM method, provide a way to generate larger transforms from smaller ones but lack a solid mathematical justification and can introduce errors. This paper aims to address this gap by providing a mathematically grounded framework for creating low-complexity 2N-point DCT-II approximations from N-point ones, with improved performance and a clear understanding of their properties.

Methods

The core of this paper lies in developing a new framework for "scaling" N-point DCT-II approximations to generate 2N-point approximations. This is achieved by leveraging the recursive matrix factorization of the exact 2N-point DCT-II matrix, as proposed by Hou. The authors introduce a general scaling method that encompasses the existing JAM scaling method as a special case. This method involves parameter matrices, denoted as $B_N$ and $G_N$, which allow for flexibility in generating various approximations. The paper also derives conditions for the orthogonality of these scaled approximations, a desirable property for signal processing applications. Furthermore, they analyze the error performance and arithmetic complexity of their proposed methods.

Datasets

Not discussed in the paper. The paper focuses on theoretical development and performance evaluation using established DCT approximations as inputs to their scaling methods.

Key Insights and Ideas

  • Mathematical Justification for Scaling: The paper provides a rigorous mathematical foundation for scaling DCT-II approximations, moving beyond ad-hoc methods.
  • Flexibility through Parameter Matrices: The introduction of parameter matrices ($B_N$, $G_N$) allows for a family of scaling methods, offering a trade-off between complexity and approximation accuracy.
  • Outperforming Existing Methods: The proposed methods, particularly Methods VI and VII, demonstrate superior performance in terms of error metrics compared to the widely used JAM scaling method.
  • Multiplierless Approximations: The proposed scaling methods are inherently multiplierless, meaning they only require additions and bit-shifting operations, which is crucial for hardware efficiency and low power consumption.
  • Orthogonality Conditions: Establishing conditions for orthogonal approximations is vital for applications where invertibility is required, such as signal reconstruction.

Key Results

  • The proposed scaling methods generate 2N-point DCT-II approximations that outperform the JAM scaling method in terms of total error energy and mean squared error, as evidenced by statistical simulations.
  • Methods VI and VII consistently showed the lowest error floor (intercept 'b' in the regression model) and a high slope 'm', indicating they are less sensitive to the initial approximation error and provide better overall accuracy.
  • The paper demonstrates that the proposed methods do not incur higher arithmetic complexity compared to the JAM scaling method, with some methods even offering improved efficiency.
  • Hardware implementation on an FPGA showed that the proposed methods, when applied to the ABDCT approximation, achieved competitive results in terms of resource utilization (slices, LUTs, FFs) and operating frequency, with Method VII showing the least amount of FFs.

Limitations and Future Work

  • Limitations: While the paper provides sufficient conditions for orthogonality, they are not necessarily necessary. The performance of the proposed methods is also dependent on the quality of the initial N-point approximation used.
  • Future Work: The authors suggest exploring relationships between DCT-II and DCT-IV with higher sparsity factors to derive alternative scaling methods. They also propose investigating the behavior of these approximations after repeated recursive applications and exploring matrix parameterizations based on generalizations of existing algorithms.

Summary updated

Abstract

This paper introduces a collection of scaling methods for generating 2 N-point DCT-II approximations based on N-point low-complexity transformations. Such scaling is based on the Hou recursive matrix factorization of the exact 2 N-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 Methodsfor DCT-II Approximations}},
  journal = {IEEE Trans. Signal Process.},
  year = {2021},
  url = {https://openreview.net/forum?id=_a_oKVgfeAf},
}
Figure