Globally Variance-Constrained Sparse Representation for Image Set Compression

Xiang Zhang, Jiarui Sun, Siwei Ma, Zhouchen Lin, Jian Zhang, Shiqi Wang, Wen Gao

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.

Correlation between coding bits and data variance.

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.

Rate-distortion performance comparison of GVCSR against state-of-the-art methods.

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

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, based on which various successful applications have been achieved. However, in the scenario of data compression, its efficiency and popularity are hindered. It is because of the fact that encoding sparsely distributed coefficients may consume more bits for representing the index of nonzero coefficients. Therefore, introducing an accurate rate-constraint in sparse coding and dictionary learning becomes meaningful, which has not been fully exploited in the context of sparse representation. According to the Shannon entropy inequality, the variance of a Gaussian distributed data bounds its entropy, indicating the actual bitrate can be well estimated by its variance. Hence, a Globally Variance-Constrained Sparse Representation (GVCSR) model is proposed in this work, where a variance-constrained rate term is introduced to the optimization process. Specifically, we employ the Alternating Direction Method of Multipliers (ADMM) to solve the non-convex optimization problem for sparse coding and dictionary learning, both of them have shown the state-of-the-art rate-distortion performance for image representation. Furthermore, we investigate the potential of applying the GVCSR algorithm in the practical image set compression, where the optimized dictionary is trained to efficiently represent the images captured in similar scenarios by implicitly utilizing inter-image correlations. Experimental results have demonstrated superior rate-distortion performance against the state-of-the-art methods.
BibTeX
@article{zhang2018globally,
  author = {Xiang Zhang and Jiarui Sun and Siwei Ma and Zhouchen Lin and Jian Zhang and Shiqi Wang and Wen Gao},
  title = {{Globally Variance-Constrained Sparse Representation for Image Set Compression}},
  journal = {IEEE Trans. Image Process.},
  year = {2018},
  doi = {10.1109/tip.2018.2823546},
}
Figure