Sparse multidimensional representation using shearlets

Demetrio Labate, Wang‐Q Lim, Gitta Kutyniok, Guido WeissProceedings of SPIE, the International Society for Optical Engineering/Proceedings of SPIE 2005 · DOI

TL;DR

This paper introduces "shearlets," a novel multidimensional representation system designed to efficiently capture the geometric features of images, particularly edges and curves. By combining dilation, shear, and translation operations, shearlets offer a sparse representation that outperforms traditional wavelets for image processing tasks, paving the way for more effective image compression and analysis.

What Problem Does This Paper Address?

Traditional wavelet transforms, while powerful for one-dimensional signals, struggle to efficiently represent multidimensional data like images. Specifically, natural images often contain edges and curves – discontinuities that are difficult to capture sparsely with standard wavelet bases. This leads to a large number of wavelet coefficients being needed to represent these features accurately, making the representation inefficient for tasks like compression. Previous attempts to address this, such as curvelets and contourlets, have shown promise by incorporating directional and elongated basis elements. This paper aims to introduce a new system, shearlets, that builds upon these ideas to provide an even more effective and mathematically elegant solution for sparse multidimensional representation.

Methods

The core of this paper is the introduction of shearlets, a new class of multidimensional representation systems. These systems are constructed by applying a combination of dilation, shear transformation, and translation to a basic generating function (a "mother wavelet").

  • Affine Systems: Shearlets are defined as affine systems of the form $A_{AB}(\Psi) = \{|det A|^{i/2} \psi(B^i A^j x - k) : i, j \in \mathbb{Z}, k \in \mathbb{Z}^2\}$. Here, $A$ and $B$ are specific matrices that control the dilation and shearing, respectively, and $\psi$ is the generating function.
  • Generalized Multiresolution Analysis (MRA): The authors frame the study of shearlets within a generalized MRA. This framework allows for a more flexible construction than classical MRAs, accommodating the composite dilations introduced by the shear operations.
  • Continuous Shearlet Transform: A continuous version of the shearlet transform is defined, $S_f(a, s, t) = \langle f, \psi_{a,s,t} \rangle$, where $\psi_{a,s,t}$ are the shearlets. This transform is shown to have properties that allow it to localize and identify the orientation of discontinuities in signals.
  • Discretization and Tight Frames: The paper details a procedure to discretize the continuous shearlet transform, leading to discrete shearlet systems. These discrete systems are shown to form tight frames for $L^2(\mathbb{R}^2)$, meaning they provide a stable and complete representation of signals.
  • Cascade Algorithm: A recursive algorithm, generalizing the classical cascade algorithm for wavelets, is derived for the implementation of shearlet transforms. This algorithm is crucial for practical applications.

Datasets

Not discussed in the paper. The paper focuses on the theoretical construction and properties of shearlets, rather than their application to specific datasets.

Key Insights and Ideas

  • Shearlets Excel at Capturing Geometric Features: The fundamental insight is that by incorporating shear transformations, shearlets can create basis elements that are highly elongated and oriented. This makes them exceptionally well-suited to represent edges and curves, which are prevalent in natural images.
  • Bridging the Gap Between Wavelets and Curvelets: Shearlets offer a unified framework that combines aspects of both wavelets (multiscale analysis) and curvelets (directional analysis). They achieve this through a more direct affine construction.
  • Generalized MRA for Enhanced Flexibility: The use of a generalized MRA allows for a more sophisticated analysis of these composite dilation systems, leading to a deeper understanding of their properties and enabling efficient discrete implementations.
  • Recursive Implementation: The development of a generalized cascade algorithm is a significant practical contribution, making shearlet transforms computationally feasible for real-world applications.

Key Results

  • Sparse Representation: Shearlets are shown to provide sparse representations for functions with discontinuities along curves, meaning significantly fewer coefficients are needed compared to traditional wavelets.
  • Tight Frame Property: The discrete shearlet systems are proven to be tight frames for $L^2(\mathbb{R}^2)$, ensuring stable and complete signal representation.
  • Edge Localization and Orientation Identification: The continuous shearlet transform can not only locate singularities (edges) in a signal but also identify their orientation, a crucial property for image analysis.
  • Generalization of Cascade Algorithm: The paper presents a recursive algorithm for computing shearlet coefficients, extending the well-established cascade algorithm for wavelets.

Limitations and Future Work

  • Regularity Issues: The authors mention that they are currently investigating the regularity issues associated with these shearlet systems. The degree of smoothness of the shearlet basis functions is an important factor for their performance in various applications.
  • Connection to Other Directional Representations: The paper notes the ongoing investigation into the connection of shearlets with other directional filter banks, such as curvelets and contourlets. Understanding these relationships can lead to hybrid approaches or a clearer picture of the landscape of multidimensional representations.
  • Practical Applications: While the paper lays the theoretical groundwork, future work will likely involve applying shearlets to specific image processing tasks like compression, denoising, and feature extraction to demonstrate their practical advantages.

Summary updated

Abstract

In this paper we describe a new class of multidimensional representation systems, called shearlets. They are obtained by applying the actions of dilation, shear transformation and translation to a fixed function, and exhibit the geometric and mathematical properties, e.g., directionality, elongated shapes, scales, oscillations, recently advocated by many authors for sparse image processing applications. These systems can be studied within the framework of a generalized multiresolution analysis. This approach leads to a recursive algorithm for the implementation of these systems, that generalizes the classical cascade algorithm.
BibTeX
@inproceedings{labate2005sparse,
  author = {Demetrio Labate and Wang‐Q Lim and Gitta Kutyniok and Guido Weiss},
  title = {{Sparse multidimensional representation using shearlets}},
  booktitle = {Proceedings of SPIE, the International Society for Optical Engineering/Proceedings of SPIE},
  year = {2005},
  doi = {10.1117/12.613494},
}
Figure