Globally Variance-Constrained Sparse Representation and Its Application in Image Set Coding

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

Introduction

Sparse representation (SR) has long been a cornerstone of signal processing, particularly for tasks like denoising and signal restoration. By representing a signal as a linear combination of a few "atoms" from a dictionary, SR captures the essential structure of data. However, applying SR to image compression presents a unique challenge: the "cost of the map." In compression, encoding the indices of non-zero coefficients (the sparsity pattern) can often consume more bits than the coefficient values themselves. Traditional $l_0$ norm models fail to account for this bitrate overhead, and local, patch-based processing often ignores global correlations.

This paper introduces Globally Variance-Constrained Sparse Representation (GVCSR), a framework designed to bridge the gap between sparse coding and efficient data compression by optimizing for rate-distortion performance.

Theoretical Foundation: Variance as a Bitrate Proxy

The core innovation of GVCSR lies in its approach to rate estimation. Drawing from Shannon’s information theory, the authors utilize the entropy inequality, which states that the entropy (and thus the minimum bitrate) of a data source is bounded by its variance.

The correlation between the variance of sparse coefficients and the actual coding bits required.

As shown in the figure above, there is a strong monotonic relationship between data variance and coding bits. By incorporating a variance constraint into the sparse coding objective function, the authors transform a difficult discrete optimization problem (minimizing bits) into a continuous optimization problem that can be solved using robust mathematical tools.

Methodology: Global Optimization via ADMM

Unlike traditional greedy algorithms like Orthogonal Matching Pursuit (OMP) that operate on individual patches, GVCSR employs a global optimization strategy. Using the Alternating Direction Method of Multipliers (ADMM), the framework solves for sparse coefficients and dictionary atoms simultaneously across all patches in an image or image set. This ensures that similar features across the data are represented by stable coefficient patterns, which are significantly easier for entropy coders to compress.

To address the computational intensity of this global approach—specifically the Singular Value Decomposition (SVD) steps—the authors developed a specialized fast SVD algorithm. This optimization reduces the complexity of the variance matrix calculations from $O(N^3)$ to $O(N)$, making the global approach computationally feasible and comparable in speed to standard methods like K-SVD.

Application in Image Set Coding

The GVCSR framework is particularly effective for image set compression, such as collections of photographs of the same scene (e.g., the CastleEntry or Fountain datasets). By training a dictionary on a reference image, the system captures the shared "visual language" of the set. Subsequent images are encoded using this shared dictionary, effectively capturing inter-image redundancies without the need for explicit geometric registration or complex motion compensation.

Experimental Results

The performance of GVCSR was evaluated using the Kodak database for general representation and several specific image sets for compression benchmarks.

Rate-distortion performance comparison showing GVCSR (red line) consistently outperforming other sparse representation methods.

As illustrated in the rate-distortion curves, GVCSR consistently achieves higher Peak Signal-to-Noise Ratio (PSNR) values than state-of-the-art methods like RDOMP, SPA, and CeSaMP at equivalent bitrates. Furthermore, in image set coding tests, the GVCSR-based framework outperformed standard codecs including JPEG, JPEG2000, and even HEVC (intra-mode), demonstrating its practical utility in high-performance compression scenarios.

Conclusion

GVCSR represents a significant shift in sparse representation research, moving from simple sparsity to joint rate-distortion optimization. By using variance as a proxy for bitrate and implementing a global ADMM-based solver, the authors have created a framework that excels in both reconstruction quality and compression efficiency. Future work may extend these "global" optimization concepts to video coding, where temporal redundancies offer even greater opportunities for variance-constrained representation.

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 <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">Shannon</i> entropy inequality, the variance of Gaussian distributed data bound 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 paper, where a variance-constrained rate term is introduced to the optimization process. Specifically, we employ the alternating direction method of multipliers (ADMMs) 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 and Its Application in Image Set Coding}},
  journal = {IEEE Trans. Image Process.},
  year = {2018},
  doi = {10.1109/tip.2018.2823546},
}
Figure