Image compression using an edge adapted redundant dictionary and wavelets

Lorenzo Peotta, L. Granai, Pierre VandergheynstSignal 2005 · DOI

TL;DR

This paper introduces a novel image compression technique that excels at low bitrates by separately modeling image edges and smooth regions. It uses a redundant dictionary of edge-adapted wavelets for edges and standard wavelets for the rest, achieving better PSNR and visual quality than JPEG2000 at very low bitrates.

What Problem Does This Paper Address?

The paper tackles the challenge of low bit-rate image compression, a critical problem for applications like storing images on memory-constrained devices or streaming them over the internet. While 2D wavelets are the current state-of-the-art, they struggle to efficiently represent the natural geometry of images, particularly edges and contours. Standard wavelets tend to create artifacts around these sharp transitions. The authors aim to improve compression by specifically addressing how to represent these edge structures more effectively.

Methods

The core of the proposed method is a two-pronged approach:

  • Edge Representation: The paper introduces a redundant dictionary of "edge-adapted" functions. These functions are built by applying transformations (translation, rotation, bending, and anisotropic scaling) to generating functions. This allows them to capture the orientation and shape of image edges more accurately than standard wavelets. The Matching Pursuit (MP) algorithm is used to find a sparse representation of the edge component of the image using this dictionary.
  • Residual Representation: The remaining part of the image (smooth regions and textures), after the edge approximation, is then coded using standard wavelets (specifically, the Cohen-Daubechies-Feauveau 9,7 biorthogonal wavelet).
  • Rate-Distortion Optimization: A crucial aspect is the Rate-Distortion (RD) optimization procedure. This process intelligently balances the number of edge atoms used from the redundant dictionary and the quantization step for the wavelet coefficients to achieve the best trade-off between compression rate and image distortion.

Datasets

The paper evaluates its method on standard images: "cameraman," "peppers," and "Lena." These are common benchmarks in image processing and compression research. The authors mention using images of size 256x256 pixels for their experiments.

Key Insights and Ideas

  • Separating Edges and Smoothness is Key: The paper's fundamental insight is that treating image edges and smooth regions differently leads to significant compression gains, especially at low bitrates. Edges are visually dominant at low bitrates, and their efficient representation is paramount.
  • Geometric Dictionary for Edges: The custom-designed redundant dictionary, capable of adapting to edge orientation and shape through transformations like bending and anisotropic scaling, is a major innovation. This allows for a much sparser representation of edges compared to standard wavelets.
  • Matching Pursuit for Sparsity: While finding the absolute sparsest representation in a redundant dictionary is NP-hard, the paper leverages the Matching Pursuit algorithm as an effective greedy strategy to find good sparse approximations.
  • Wavelets for the Remainder: Using standard wavelets for the residual (smooth parts and textures) is a practical choice, as wavelets are well-suited for these types of signals and offer efficient coding.
  • RD Optimization for Balance: The RD optimization is essential for finding the optimal balance between the complex edge representation and the simpler wavelet representation, ensuring overall efficiency.

Key Results

  • Superior PSNR at Low Bitrates: The proposed method (MPW) consistently outperforms JPEG2000 and a pure wavelet encoder in terms of PSNR at very low bitrates (e.g., below 0.1 bpp). For example, at 0.1 bpp, MPW achieves a PSNR of 25.06 dB for "cameraman," compared to 23.63 dB for JPEG2000 and 23.79 dB for pure wavelets.
  • Improved Visual Quality: Beyond PSNR, the paper highlights significant improvements in visual quality, particularly the reduction of ringing artifacts around edges, which are typical of wavelet-based compression. Figure 7 visually demonstrates this advantage.
  • Computational Cost: The authors note that for images of size 256x256, the MPW coding takes around one hour on a 2GHz processor. This indicates a higher computational cost compared to standard codecs, a trade-off for improved compression performance.

Limitations and Future Work

  • Computational Complexity: The primary limitation acknowledged is the computational cost of the Matching Pursuit algorithm and the large redundant dictionary, leading to longer encoding times.
  • Fine Quantization Assumption: The rate-distortion analysis relies on a fine quantization assumption for wavelets, which may not hold at very low bitrates. The paper mentions that dead-zone uniform quantizers are used to improve RD performance at low bitrates.
  • Future Work: The paper suggests that further research could explore alternative search algorithms for the dictionary to reduce computational complexity, potentially using tree-based pursuit methods, though they note that quality loss can be an issue with some of these. The authors also mention that the PSNR can decrease when using less redundant dictionaries, implying that dictionary size is a key factor.

Summary updated

BibTeX
@inproceedings{peotta2005image,
  author = {Lorenzo Peotta and L. Granai and Pierre Vandergheynst},
  title = {{Image compression using an edge adapted redundant dictionary and wavelets}},
  booktitle = {Signal},
  year = {2005},
  doi = {10.1016/j.sigpro.2005.05.023},
}
Figure