Source-linked AI summary
Improved 8-point Approximate DCT for Image and Video Compression Requiring Only 14 Additions
U. S. Potluri, A. Madanayake, R. J. Cintra, F. M. Bayer, S. Kulasekera, A. Edirisuriya
TL;DR
The paper addresses the computational and circuitry costs of DCT-based video processing, particularly for HEVC. It introduces a new low-power 8-point DCT approximation and reports lower complexity and faster operation than the examined alternatives.
Problem
HEVC and related video-processing systems require substantial arithmetic effort, while circuitry complexity and power consumption make minimizing computational cost important.
Method
The paper introduces a novel low-power 8-point DCT approximation for reducing computational complexity.
Results
The proposed transform has lower computational complexity and is faster than all other approximations considered.
Takeaways & Limitations
The proposed transform is identified as the best examined DCT approximation in computational complexity and speed.
Takeaways & Limitations
The CMOS realization remains incomplete, with future work involving proprietary TSMC libraries and continuing implementation beyond the reported stage.
Abstract
from arXiv · showhide
Video processing systems such as HEVC requiring low energy consumption needed for the multimedia market has lead to extensive development in fast algorithms for the efficient approximation of 2-D DCT transforms. The DCT is employed in a multitude of compression standards due to its remarkable energy compaction properties. Multiplier-free approximate DCT transforms have been proposed that offer superior compression performance at very low circuit complexity. Such approximations can be realized in digital VLSI hardware using additions and subtractions only, leading to significant reductions in chip area and power consumption compared to conventional DCTs and integer transforms. In this paper, we introduce a novel 8-point DCT approximation that requires only 14 addition operations and no multiplications. The proposed transform possesses low computational complexity and is compared to state-of-the-art DCT approximations in terms of both algorithm complexity and peak signal-to-noise ratio. The proposed DCT approximation is a candidate for reconfigurable video standards such as HEVC. The proposed transform and several other DCT approximations are mapped to systolic-array digital architectures and physically realized as digital prototype circuits using FPGA technology and mapped to 45 nm CMOS technology.
1 Introduction
The paper motivates low-complexity DCT approximations for image and video coding, particularly where HEVC’s computational demand and hardware cost challenge low-power systems. It introduces a 14-addition approximation and hardware implementations for comparing several 2-D 8-point DCT methods.
- The DCT provides good energy compaction and is used in image and video coding standards including JPEG, MPEG, H.261, H.263, and H.264/AVC.
- HEVC can be 2–4 times more computationally demanding than H.264/AVC, motivating low-complexity DCT-like approximations.
- Floating-point operations increase circuit complexity and power consumption, so approximate transforms are considered to reduce computational cost.
- The proposed DCT approximation requires only 14 additions and is obtained by optimizing the transform’s computational cost.
2 Reconfigurable DCT-like Fast Algorithms in Video CODECs
The section frames approximate DCTs as multiplier-free, low-cost alternatives suited to reconfigurable video codecs. Their intended use is to trade picture quality against circuit complexity, power, and available energy in changing operating conditions.
- Approximate DCT matrices with entries from {0, ±1/2, ±1, ±2} require only binary additions and shifts, eliminating multiplicative complexity.
- Approximate DCT implementations can be economical because they omit multipliers while retaining performance characteristics similar to exact DCT-like transforms.
- HEVC’s on-the-fly reconfiguration makes suites of fast algorithms and digital VLSI architectures valuable for low-energy, high-performance embedded systems.
- Different approximations can support operating-point changes between higher signal-to-noise ratio and lower complexity as device power availability changes.
- Incoming-stream SNR is content-specific and difficult to predict without real-time video metrics, limiting straightforward approximation selection.
3 Review of Approximate DCT Methods
The reviewed approximate DCT methods use structured low-complexity matrices and factorizations to avoid multiplications. The section surveys BAS, CB, modified CB, and application-specific transforms, including their arithmetic properties.
- Approximate DCT methods commonly factor into a diagonal matrix and a sparse low-complexity matrix with powers-of-two entries.
- The diagonal matrix can be absorbed into JPEG-like quantization, bounding the approximation’s additional computational complexity.
- BAS-2008 is factorized into sparse matrices containing {0, ±1/2, ±1} elements, enabling a fast algorithm.
- The BAS-2011 transform uses a parameter a, with suggested values {0, 1/2, 1} and an additional low-complexity error-free choice of a = 2.
- The CB approximation contains only {0, ±1} elements, while the modified CB transform requires only 14 additions.
4 Proposed Transform
The proposed transform is found by searching structured 8×8 matrices for minimal arithmetic cost while preserving a DCT-like form and orthogonality. The search yields candidate matrices, from which one is selected using compressed-image quality.
- An exhaustive search produces eight minimal-cost candidate matrices, and the candidate with the best JPEG-like compressed-image quality is selected.
- The optimization restricts matrix entries to {0, ±1, ±2} so the resulting transform avoids multiplication operations.
- The imposed matrix structure preserves DCT-like symmetry, requires non-null rows, and enforces orthogonality through a diagonal T·T^T.
- Ten retained transform coefficients are adopted as a compromise for evaluating compressed-image quality.
- The selected solution is presented as a novel DCT approximation with a sparse factorization for fast computation.
5 Computational Complexity and Performance Analysis
The evaluation compares DCT approximations by arithmetic complexity, proximity to the exact DCT, transform measures, and compressed-image quality. The proposed transform combines 14 additions with competitive compression and video-coding performance.
- Arithmetic complexity: 14 additions make the proposed transform one of the lowest-complexity DCT approximations, matching Modified CB-2011 and using no multiplicative complexity.The arithmetic-complexity analysis counts additions/subtractions and bit shifts, while all considered approximations have null multiplicative complexity.
- Image compression performance: The proposed transform can outperform Modified CB-2011 in image compression according to PSNR and UQI values.This comparison is reported alongside the shared 14-addition complexity of both transforms.
- Complexity-performance trade-off: BAS-2011 can achieve better PSNR than the proposed algorithm, but requires about 14.3% more operations relative to the DCT for high compression ratios.The comparison covers r = 2, 3, . . . , 20.
- Transform measures: The proposed transform improves coding gain by 7.9% and transform efficiency by 5%, while retaining a 14-addition implementation.The reported complexity is associated with the possibility of smaller, faster, and more energy-efficient circuitry.
- Accuracy measures: Closeness to the exact DCT is not sufficient to identify the best approximation for image compression, as proximity measures can disagree with image-quality results.The paper illustrates this behavior by contrasting proximity measures with compression performance in its accuracy results.
- Video compression performance: For the BasketballPass sequence, the rate-point difference between the Chen DCT and proposed approximation is negligible, with a mean absolute difference of 0.1234 dB.The comparison uses rate-distortion curves for the test sequence.
6 Digital Architectures and Realizations
The paper implements approximate 8-point DCTs as reconfigurable 2-D digital architectures, using row and column transforms separated by a transposition buffer. These designs are verified on FPGA hardware and evaluated for resource use, timing, and power, with the proposed and modified CB-2011 designs showing the strongest hardware results.
- 6.1 Proposed Architectures: The 2-D architectures apply a selected 1-D approximation first across image rows and then across columns of the transposed intermediate result.The row- and column-wise transforms may differ, although the implementations use identical transforms for simplicity.
- 6.1 Proposed Architectures: A real-time row-parallel transposition buffer reorders row-transformed data into the format required by the column-transform circuit.
- The proposed and modified CB-2011 designs are faster and use fewer hardware resources than the remaining approximations.
7 Conclusion
The paper introduces a low-complexity 8-point approximate DCT using 14 additions, evaluates it against prominent approximations, and implements the designs in FPGA and 45 nm CMOS technologies. The proposed transform closely approaches the ideal DCT, is faster and less complex than the alternatives examined, and is suitable for image and video processing including HEVC.
- 7 Conclusion: The proposed 8-point DCT approximation requires only 14 addition operations and is implemented alongside prominent competing approximate DCT methods.The implementations address both 1-D and 2-D approximate DCTs using FPGA tools and 45 nm CMOS technology.
- 7 Conclusion: The proposed transform and modified CB-2011 approximation perform very close to the ideal DCT while providing lower computational complexity and higher speed than the other approximations examined.The conclusion identifies the proposed transform as the best approximation among those examined in computational complexity and speed.
- 7 Conclusion: In image compression, the proposed transform could outperform the modified CB-2011 algorithm.
- 7 Conclusion: CMOS implementations operate much faster than FPGA implementations for the same function-word size.The architectures are therefore described as suitable for image and video processing and as candidates for standards including HEVC.
- 7 Conclusion: Future work includes replacing FreePDK cells with optimized proprietary libraries, completing fabrication and post-fabrication testing, and extending the approximations to additional HEVC transforms.The planned extensions cover 4-, 16-, and 32-point DCTs and the 4-point discrete sine transform.