Source-linked AI summary
A DCT Approximation for Image Compression
R. J. Cintra, F. M. Bayer
TL;DR
The paper addresses the need for low-complexity computation of the 8-point DCT, for which existing fast algorithms require multiplications. It introduces an orthogonal approximation based on matrix polar decomposition and evaluates it for image compression, where it could outperform SDCT and BAS-2008 at low and high compression ratios with only two additional arithmetic operations.
Problem
Existing fast DCT algorithms require several multiplication operations, motivating approximate 8-point DCT algorithms for lower-complexity computation.
Method
The paper introduces an orthogonal 8-point DCT approximation based on matrix polar decomposition and applies it with quantization for image compression.
Results
The proposed approximation could outperform SDCT at any compression ratio and BAS-2008 at high and low compression ratios, with only two additional arithmetic operations.
Takeaways & Limitations
The approximation offers image-compression performance superior to SDCT and potentially BAS-2008 in low- and high-compression scenarios while retaining comparable complexity.
Takeaways & Limitations
The cited prior approximation lacks orthogonality and has a resulting approximation limitation identified by the authors.
Abstract
from arXiv · showhide
An orthogonal approximation for the 8-point discrete cosine transform (DCT) is introduced. The proposed transformation matrix contains only zeros and ones; multiplications and bit-shift operations are absent. Close spectral behavior relative to the DCT was adopted as design criterion. The proposed algorithm is superior to the signed discrete cosine transform. It could also outperform state-of-the-art algorithms in low and high image compression scenarios, exhibiting at the same time a comparable computational complexity.
1 Introduction
The 8-point DCT is widely used in image and video processing because of its energy compaction properties, but exact and fast implementations remain computationally demanding. This motivates approximate algorithms that estimate the DCT with lower complexity, including methods designed for image compression.
- 1 Introduction: The 8-point DCT is a key step in many image and video processing applications and coding standards.It is used in JPEG, MPEG-1, MPEG-2, H.261, and H.263.
- 1 Introduction: Its adoption is mainly attributed to good energy compaction properties closely related to the Karhunen-Loève transform.
- 1 Introduction: Existing fast DCT algorithms require several multiplication operations, while practical advances in low-complexity exact-DCT computation have been limited.The arithmetic cosine transform is noted as a possible exception, but practical implementation remains underdeveloped.
- 1 Introduction: Approximate algorithms target the 8-point DCT by providing meaningful estimations at low-complexity requirements rather than computing it exactly.
- 1 Introduction: The paper introduces a low-complexity DCT approximation for image compression, combining an orthogonal transformation with quantization and coefficients intended to remain close to exact-DCT coefficients.The design restricts attention to matrices considered good DCT approximations.
2 DCT round-off approximations
The proposed round-off approximation constructs a low-complexity, orthogonal transform from a rounded DCT matrix and diagonal orthogonalization. It preserves close spectral behavior to the DCT while achieving competitive arithmetic complexity and image-compression performance.
- Construction: The method scales the standard DCT matrix by two and applies element-wise rounding to form C0.The resulting matrix is then used as the low-complexity basis for the approximation.
- Construction: C0 contains only 0, 1, and −1, requiring additions without multiplications or bit-shift operations.A scaled transpose can also perform approximate inversion, giving the transform a quasi-symmetrical structure.
- Orthogonalization: The orthogonal approximation ˆCorth = S · C0 combines C0 with a diagonal matrix S obtained through polar-decomposition-based orthogonalization.This construction is orthogonal, retains C0’s low computational complexity, and allows scaling factors to be merged into quantization.
- Complexity: The proposed algorithm is less complex than the SDCT and requires only two additional operations relative to the best BAS algorithms.Its fast implementation is assessed using addition, multiplication, and bit-shift counts.
- Spectral evaluation: The proposed approximation is more closely related to the DCT than the other evaluated approximations in spectral behavior and energy characteristics.Comparisons exclude m = 0,4 because all considered transforms have identical transfer functions there; the strongest results occur for m = 1,3,5,7.
3 Application to image compression and discussion
The proposed approximation was evaluated for 8×8 image compression using average quality metrics, coefficient retention, and reconstructed-image comparisons. It outperformed SDCT across compression ratios and showed advantages over BAS-2008 at low and high compression, with only two additional arithmetic operations.
- Evaluation methodology: The evaluation used 45 512 × 512 8-bit greyscale images and average PSNR across images for compression ratios 1 ≤r ≤45.Each image was divided into 8 × 8 blocks, transformed, zigzag-truncated to retain the first r coefficients, and reconstructed.
- Evaluation methodology: The 2-D approximate transform computed each block as T · A · T⊤, producing 64 transform-domain coefficients before zigzag coefficient retention.The remaining coefficients were set to zero and the inverse procedure reconstructed the processed image.
- Quantitative assessment: The proposed approximation could outperform SDCT at any compression ratio and BAS-2008 at high- and low-compression ratios, while remaining comparable in the mid-range.This performance was achieved at the expense of only two additional arithmetic operations.
- Quantitative assessment: According to average UQI and MSE absolute percentage error relative to the exact DCT, the proposed approximation performed better at almost all compression ratios.It was clearly superior for high- and low-compression-ratio applications.
- Application scope: The results indicate that the approximation is adequate for image compression, including low-bit-rate transmission and applications using high compression ratios.The paper identifies r ≤16 as a suitable range for the proposed approximation in the cited face-recognition and JPEG contexts.
- Qualitative assessment: With only 5 of 64 coefficients retained per 8 × 8 block, reconstructed images from the proposed method were close to DCT results and superior to SDCT and BAS-2008.Compared with BAS-2008, the reconstructed images had better quality and fewer blocking artifacts for Lena, Airplane (F-16), and boat.512.
4 Conclusion
The correspondence introduces a polar-decomposition-based DCT approximation that outperforms BAS-2008 in high- and low-compression scenarios according to several image-quality measurements. Its constructive round-off formulation supports generalizations, including alternative rounding functions and hybrid transforms assembled from existing matrix rows.
- The proposed DCT approximation is based on matrix polar decomposition.
- The method could outperform BAS-2008 in high- and low-compression scenarios according to PSNR, UQI, and MSE measurements.
- Its constructive round-off formulation makes generalizations more readily possible.
- Replacing round-off with floor or ceiling functions could produce entirely new approximations.
- The transform's distinct row structure could support hybrid algorithms combining rows from existing approximations.