Abstract
Sparse representation leads to an efficient way to approximately recover a signal by the linear composition of a few bases from a learnt dictionary. However, in the scenario of data compression, its efficiency is hindered because encoding sparsely distributed coefficients may consume more bits for representing the index of nonzero coefficients. This paper proposes a Globally Variance-Constrained Sparse Representation (GVCSR) model, where a variance-constrained rate term is introduced to the optimization process. Based on Shannon entropy inequality, the variance of Gaussian distributed data bounds its entropy, indicating that the actual bitrate can be well estimated by its variance. Using the Alternating Direction Method of Multipliers (ADMM), the model achieves state-of-the-art rate-distortion performance for image representation and image set compression.
Introduction
Sparse representation (SR) is a powerful tool for signal processing, where a signal is reconstructed using a linear combination of just a few "atoms" from a learned dictionary. While SR is excellent for tasks like denoising and restoration, it often struggles in image compression due to the Rate-Distortion (R-D) tradeoff. Standard sparse coding focuses on minimizing the number of non-zero coefficients ($\\ell_0$ norm), but this doesn't accurately reflect the actual number of bits needed to encode the positions (indices) and values of those coefficients. Furthermore, most existing methods process image patches locally and independently, ignoring global data structures. The GVCSR model aims to create a "compression-friendly" sparse model that considers the global bitrate cost during the optimization process.
Methodology: Variance as a Bitrate Proxy
The core innovation of GVCSR is the use of global variance as a proxy for bitrate. According to Shannon entropy theory, the entropy (and thus the bitrate) of Gaussian or Laplacian distributed data is bounded by its variance. By minimizing the variance of the sparse coefficients, the model encourages the coefficients to be more "clustered" and similar to one another, making them significantly easier to compress.
To solve the resulting non-convex optimization problem, the authors employ the Alternating Direction Method of Multipliers (ADMM) to split the problem into manageable sub-problems for the sparse coefficients and the dictionary. To handle the high computational cost of Singular Value Decomposition (SVD) in the ADMM steps, a fast algorithm was derived that reduces complexity from $O(N^3)$ to $O(N)$ by exploiting the specific structure of the variance matrix.
Image Set Compression Framework
For image sets (groups of similar photos), the model trains a dictionary on a "reference image." This dictionary implicitly captures the inter-image correlations, allowing other images in the set to be represented with extreme efficiency. Instead of explicitly calculating how one image moves to become another (motion estimation), the dictionary learns the common features of the scene, reducing redundancy implicitly.
Key Results
The researchers evaluated GVCSR using standard benchmarks like the Kodak database and various image sets including Lakes and CastleEntry.
Experimental results demonstrated that GVCSR consistently achieved higher Peak Signal-to-Noise Ratio (PSNR) at the same bitrates compared to standard sparse coding (OMP) and state-of-the-art dictionary learning methods like K-SVD. In image set compression tests, the GVCSR-based framework outperformed popular standards including JPEG, JPEG2000, and HEVC (intra coding), as well as specialized image set compression algorithms based on SIFT descriptors.
Conclusion
GVCSR bridges the gap between sparse signal representation and practical data compression by introducing a variance-constrained rate term. By stabilizing the bitstream and leveraging implicit correlations, it provides a robust framework for high-efficiency image storage. Future work may extend this approach to video coding and large-scale cloud-based photo album storage where inter-image redundancy is massive.
Summary updated