Sparse representation based down-sampling image compression

Jin Wang, Yunhui Shi, Dehui Kong, Wenpeng Ding, Chunjing Li, Baocai YinJournal of Computational and Applied Mathematics 2011 · DOI

TL;DR

This paper proposes a novel image compression technique that leverages down-sampling and sparse representation to improve compression efficiency and subjective image quality, particularly at low bitrates. By analytically modeling the compression error introduced by down-sampling and then using sparse representation to reconstruct lost high-frequency details, the method achieves better results than JPEG2000.

What Problem Does This Paper Address?

Traditional image compression methods like JPEG2000, while effective, can still struggle with achieving high compression ratios while maintaining excellent visual quality, especially at very low bitrates. A known technique to improve compression is down-sampling the image before compression, which reduces the amount of data to encode. However, this process inherently loses high-frequency information, leading to blurred reconstructed images. The challenge is to effectively recover this lost high-frequency information to restore visual detail without significantly increasing the bitrate. Existing methods for recovering this information often rely on complex adaptive strategies or specific models like piecewise autoregressive (PAR) models, which the authors aim to improve upon.

Methods

The core of this paper lies in two main contributions:

  1. Analytical Model of Compression Error: The authors first develop a mathematical model to analyze the compression error introduced by down-sampling an image before applying wavelet transform-based compression (like JPEG2000). This model helps explain why down-sampling can improve coding performance and quantifies the error as a function of the down-sampling factor, bit allocation, and image characteristics.
  2. Sparse Representation for High-Frequency Reconstruction: Inspired by recent advances in sparse signal representation, the paper proposes a method to recover the lost high-frequency information. This involves:
  3. Basis Vector Codebook Generation: A codebook of overcomplete basis vectors is learned from a set of training images. This codebook captures common image patterns. The process involves extracting "primitive patches" from both high-quality (original) and low-quality (down-sampled and re-upsampled) versions of training images. The similarity between these pairs is used to learn the basis vectors.
  4. High-Frequency Patch Reconstruction: For an image to be compressed, it undergoes the same down-sampling and re-upsampling process. The blurred image is then processed to extract low-quality patches. These patches are used to query the pre-trained codebook to find the most similar high-quality basis vectors. Sparse representation techniques (specifically L1 optimization) are then employed to reconstruct the missing high-frequency details using these basis vectors.
  5. Blending: The reconstructed high-frequency details are blended with the down-sampled and re-upsampled (low-frequency) image to produce the final, high-quality reconstructed image.

Datasets

  • Training: The authors used a dataset of 24,768 × 512 or 512 × 768 Kodak images for training the basis vector codebook.
  • Evaluation: The paper mentions testing on "various images" and shows results for the "Lena" image.

Key Insights and Ideas

  • Down-sampling as a beneficial preprocessing step: The analytical model provides a theoretical basis for why down-sampling can improve compression efficiency, not just an empirical observation.
  • Sparse representation for detail recovery: The paper demonstrates that sparse representation, using a learned overcomplete dictionary, is a powerful tool for reconstructing lost high-frequency image details that are lost during down-sampling and compression.
  • Leveraging similarity between blurred and sharp patches: The core idea for codebook generation is to exploit the inherent similarity between a blurred patch and its corresponding sharp version to learn how to reconstruct the missing details.
  • Focus on edge areas: The method prioritizes edge areas for reconstruction, recognizing their importance for visual perception and their often lower-dimensional nature, making them amenable to sparse representation.

Key Results

  • Improved PSNR at low bitrates: Figure 2 shows that the proposed scheme consistently outperforms JPEG2000 in terms of Peak Signal-to-Noise Ratio (PSNR) at low bitrates (ranging from 0.02 to 0.2 bpp). For example, at 0.1 bpp, the proposed scheme achieves PSNRs around 30.33 dB (Figure 3b) and 30.91 dB (Figure 4b), compared to JPEG2000's 29.96 dB (Figure 3a) and 30.55 dB (Figure 4a).
  • Enhanced Subjective Quality: Figures 3 and 4 visually demonstrate that the proposed scheme produces images with fewer ringing artifacts and better overall visual quality compared to JPEG2000, especially at low bitrates.
  • Analytical explanation for down-sampling benefits: The paper provides a mathematical framework to understand the error introduced by down-sampling.

Limitations and Future Work

  • Artifacts still present: The authors acknowledge that artifacts can still be found, for instance, on Lena's shoulder and the top of her hat.
  • Codebook optimization: They suggest that the learned codebook could be further optimized.
  • Improved similarity metrics: The paper proposes exploring better image similarity metrics, such as Structural Similarity (SSIM), to further enhance the scheme's performance.
  • Complexity: While the paper focuses on improving quality at low bitrates, the computational complexity of the sparse representation and codebook generation might be a consideration for real-time applications.

Summary updated

BibTeX
@article{wang2011sparse,
  author = {Jin Wang and Yunhui Shi and Dehui Kong and Wenpeng Ding and Chunjing Li and Baocai Yin},
  title = {{Sparse representation based down-sampling image compression}},
  journal = {Journal of Computational and Applied Mathematics},
  year = {2011},
  doi = {10.1016/j.cam.2011.06.025},
}
Figure