Contourlets and sparse image expansions

N. MinhProceedings of SPIE, the International Society for Optical Engineering/Proceedings of SPIE 2003 · DOI

TL;DR

This paper introduces the contourlet transform, a novel image representation that excels at capturing geometric structures like smooth contours, outperforming wavelets. It achieves near-optimal approximation rates for images with smooth edges by introducing "directional vanishing moments" and anisotropic scaling, demonstrating its potential in applications like denoising and compression.

What Problem Does This Paper Address?

Traditional image processing techniques, like the widely adopted JPEG-2000 standard which uses wavelets, struggle with representing the inherent geometric structures in natural images. While wavelets are excellent at capturing point-like discontinuities, they fail to efficiently represent smooth curves or contours. This is because wavelets are typically separable, meaning they process images as a stack of 1D signals, and thus cannot effectively capture directional information. This limitation leads to suboptimal performance in applications like image compression and feature extraction, where representing smooth edges is crucial. The paper aims to bridge this gap by developing a transform that can effectively capture these geometric structures.

Methods

The contourlet transform is constructed using a two-stage filter bank approach. First, a Laplacian pyramid (LP) is applied to capture point discontinuities. This is followed by a directional filter bank (DFB) that links these points into contour segments. This construction is designed to be "digital-friendly," starting from a discrete-domain implementation and converging to a continuous-domain expansion.

A key theoretical contribution is the introduction of directional vanishing moments (DVMs). Analogous to how vanishing moments in wavelets help approximate smooth signals, DVMs in contourlets allow them to effectively capture singularities along specific directions. The paper also leverages anisotropic scaling, where the scaling factors differ along different directions, to better match the elongated nature of contours.

The paper then provides a theoretical analysis of the approximation behavior of contourlets for piecewise smooth functions with C² contours. It shows that with sufficient DVMs and anisotropic scaling, contourlets achieve an optimal approximation rate of O((log M)³M⁻²) for best M-term approximations, significantly outperforming wavelets (O(M⁻¹)).

Datasets

The paper uses the "peppers" and "Lena" images for numerical experiments and demonstrations. No new benchmarks or datasets were introduced.

Key Insights and Ideas

  • Contourlets capture geometry: The core idea is that images have more than just point singularities; they have smooth contours. Contourlets are specifically designed to represent these contours efficiently.
  • Directional Vanishing Moments (DVMs) are crucial: Just as wavelets need vanishing moments to approximate smooth signals, contourlets need DVMs to approximate features along specific directions, especially along contours.
  • Anisotropic scaling matches contour shape: Contours are often elongated. Anisotropic scaling in contourlets allows for different resolutions along different directions, better matching the geometry of these features.
  • Optimal approximation for smooth contours: The theoretical analysis shows that contourlets can achieve near-optimal approximation rates for images with smooth C² contours, a significant improvement over wavelets.
  • Practical implications for image processing: The paper demonstrates that these theoretical advantages translate to real-world benefits in applications like denoising and nonlinear approximation.

Key Results

  • Theoretical: Contourlet expansion achieves an optimal approximation rate of O((log M)³M⁻²) for best M-term approximation of 2D piecewise smooth functions with C² contours. This is a significant improvement over wavelets, which achieve O(M⁻¹).
  • Qualitative:
    • Contourlets are shown to capture fine contours and directional textures more effectively than wavelets.
  • In nonlinear approximation experiments, contourlets refine images with "sketches" that better represent edges, while wavelets tend to capture them as isolated "dots."
    • In denoising experiments, contourlets are more effective at recovering smooth contours and removing noise compared to wavelets.
  • Quantitative:
    • A gain of 1.46 dB in peak signal-to-noise ratio (PSNR) was observed in nonlinear approximation experiments when comparing contourlets to wavelets.
  • In denoising experiments, the SNR improved from 9.55 dB (noisy) to 13.82 dB (wavelet denoising) and 15.42 dB (contourlet denoising).

Limitations and Future Work

  • Filter Design: The paper acknowledges that designing optimized contourlet filters that precisely satisfy the directional vanishing moment condition is a topic for future research. The current filters used are biorthogonal and "close" to ideal, but not perfect.
  • Computational Complexity: While the paper states the contourlet transform has O(N) complexity for an image of N pixels, the practical implementation and overhead of the directional filter banks might be a consideration.
  • Further Improvements: The paper suggests that a more sophisticated denoising scheme, like one using a hidden Markov tree model that accounts for dependencies across scales, directions, and locations, could lead to further improvements.

Summary updated

Abstract

Recently, the contourlet transform has been developed as a true two-dimensional representation that can capture the geometrical structure in pictorial information. Unlike other transforms that were initially constructed in the continuous-domain and then discretized for sampled data, the contourlet construction starts from the discrete-domain using filter banks, and then convergences to a continuous-domain expansion via a multiresolution analysis framework. In this paper we study the approximation behavior of the contourlet expansion for two-dimensional piecewise smooth functions resembling natural images. Inspired by the vanishing moment property which is the key for the good approximation behavior of wavelets, we introduce the directional vanishing moment condition for contourlets. We show that with anisotropic scaling and sufficient directional vanishing moments, contourlets essentially achieve the optimal approximation rate, <i>O</i>((log <i>M</i>)<sup>3</sup> <i>M</i><sup>-2</sup>) square error with a best <i>M</i>-term approximation, for 2-D piecewise smooth functions with <i>C</i><sup>2</sup> contours. Finally, we show some numerical experiments demonstrating the potential of contourlets in several image processing applications.
BibTeX
@inproceedings{minh2003contourlets,
  author = {N. Minh},
  title = {{Contourlets and sparse image expansions}},
  booktitle = {Proceedings of SPIE, the International Society for Optical Engineering/Proceedings of SPIE},
  year = {2003},
  doi = {10.1117/12.505948},
}
Figure