Shearlet

In applied mathematical analysis, '''shearlets''' are a multiscale framework which allows efficient encoding of anisotropic features in multivariate problem classes. Originally, shearlets were introduced in 2006<ref name=shearletsintroduction/> for the analysis and sparse approximation of functions <math>f \in L^2(\R^2)</math>. They are a natural extension of wavelets, to accommodate the fact that multivariate functions are typically governed by anisotropic features such as edges in images, since wavelets, as isotropic objects, are not capable of capturing such phenomena.

Shearlets are constructed by parabolic scaling, shearing, and translation applied to a few generating functions. At fine scales, they are essentially supported within skinny and directional ridges following the parabolic scaling law, which reads ''length² ≈ width''. Similar to wavelets, shearlets arise from the affine group and allow a unified treatment of the continuum and digital situation leading to faithful implementations. Although they do not constitute an orthonormal basis for <math>L^2(\R^2)</math>, they still form a frame allowing stable expansions of arbitrary functions <math>f \in L^2(\R^2)</math>.

One of the most important properties of shearlets is their ability to provide optimally sparse approximations (in the sense of optimality in <ref name=cartoonbenchmark/>) for cartoon-like functions <math>f</math>. In imaging sciences, ''cartoon-like functions'' serve as a model for anisotropic features and are compactly supported in <math>[0,1]^2</math> while being <math>C^2</math> apart from a closed piecewise <math>C^2</math> singularity curve with bounded curvature. The decay rate of the <math>L^2</math>-error of the <math>N</math>-term shearlet approximation obtained by taking the <math>N</math> largest coefficients from the shearlet expansion is in fact optimal up to a log-factor:<ref name=shearletsparsebandlim/><ref name=shearletsparsecompact/> :<math>\| f - f_N \|_{L^2}^2 \leq C N^{-2} (\log N)^3, \quad N \to \infty,</math> where the constant <math>C</math> depends only on the maximum curvature of the singularity curve and the maximum magnitudes of <math>f</math>, <math>f'</math> and <math>f''.</math> This approximation rate significantly improves the best <math>N</math>-term approximation rate of wavelets providing only <math>O(N^{-1})</math> for such class of functions.

Shearlets are to date the only directional representation system that provides sparse approximation of anisotropic features while providing a unified treatment of the continuum and digital realm that allows faithful implementation. Extensions of shearlet systems to <math>L^2(\R^d), d \ge 2</math> are also available. A comprehensive presentation of the theory and applications of shearlets can be found in.<ref name=shearletbook/>

== Definition ==

=== Continuous shearlet systems ===

{{multiple image | direction = vertical | footer = Geometric effects of parabolic scaling and shearing with several parameters a and s. | image1 = shearletscaling.gif | alt1 = Parabolic scaling | image2 = shearletshearing.gif | alt2 = Shearing }}

The construction of continuous shearlet systems is based on ''parabolic scaling matrices''

:<math> A_a = \begin{bmatrix} a & 0 \\ 0 & a^{1/2} \end{bmatrix}, \quad a > 0 </math>

as a means to change the resolution, on ''shear matrices''

:<math> S_s = \begin{bmatrix} 1 & s \\ 0 & 1 \end{bmatrix}, \quad s \in \R </math>

as a means to change the orientation, and finally on translations to change the positioning. In comparison to curvelets, shearlets use shearings instead of rotations, the advantage being that the shear operator <math>S_s</math> leaves the integer lattice invariant in case <math>s \in \Z</math>, i.e., <math> S_s \Z^2 \subseteq \Z^2. </math> This indeed allows a unified treatment of the continuum and digital realm, thereby guaranteeing a faithful digital implementation.

For <math>\psi \in L^2(\R^2)</math> the ''continuous shearlet system'' generated by <math>\psi</math> is then defined as

:<math> \operatorname{SH}_{\mathrm{cont}}(\psi) = \{ \psi_{a,s,t} = a^{3/4} \psi(S_s A_a (\cdot - t)) \mid a > 0, s \in \R, t \in \R^2 \}, </math>

and the corresponding ''continuous shearlet transform'' is given by the map

:<math> f \mapsto \mathcal{SH}_\psi f(a, s, t) = \langle f, \psi_{a,s,t} \rangle, \quad f \in L^2(\R^2), \quad (a, s, t) \in \R_{>0} \times \R \times \R^2. </math>

=== Discrete shearlet systems ===

A discrete version of shearlet systems can be directly obtained from <math>\operatorname{SH}_{\mathrm{cont}}(\psi)</math> by discretizing the parameter set <math>\R_{>0} \times \R \times \R^2.</math> There are numerous approaches for this but the most popular one is given by

:<math> \{ (2^j, k, A_{2^j}^{-1} S_k^{-1} m) \mid j \in \Z, k \in \Z, m \in \Z^2\} \subseteq \R_{>0} \times \R \times \R^2. </math>

From this, the ''discrete shearlet system'' associated with the shearlet generator <math>\psi</math> is defined by

:<math> \operatorname{SH}(\psi) = \{ \psi_{j,k,m} = 2^{3j/4} \psi(S_k A_{2^j} \cdot{} - m) \mid j \in \Z, k \in \Z, m \in \Z^2 \}, </math>

and the associated ''discrete shearlet transform'' is defined by :<math> f \mapsto \mathcal{SH}_\psi f(j, k, m) = \langle f, \psi_{j,k,m} \rangle, \quad f \in L^2(\R^2), \quad (j, k, m) \in \Z \times \Z \times \Z^2. </math>

== Examples ==

{{multiple image | direction = horizontal | image1 = Classshearsupp.svg | alt1 = Classical shearlet frequency support | caption1 = Trapezoidal frequency support of the classical shearlet. | image2 = Classsheartiling.svg | alt2 = Classical shearlet frequency tiling | caption2 = Frequency tiling of the (discrete) classical shearlet system. }}

Let <math>\psi_1 \in L^2(\R)</math> be a function satisfying the ''discrete Calderón condition'', i.e.,

:<math>\sum_{j \in \Z} |\hat\psi_1(2^{-j} \xi)|^2 = 1, \text{for a.e. } \xi \in \R,</math>

with <math>\hat\psi_1 \in C^\infty(\R)</math> and <math>\operatorname{supp}\hat\psi_1 \subseteq [-\tfrac{1}{2}, -\tfrac{1}{16}] \cup [\tfrac{1}{16}, \tfrac{1}{2}],</math> where <math>\hat\psi_1</math> denotes the Fourier transform of <math>\psi_1.</math> For instance, one can choose <math>\psi_1</math> to be a Meyer wavelet. Furthermore, let <math>\psi_2 \in L^2(\R)</math> be such that <math>\hat\psi_2 \in C^\infty(\R),</math> <math>\operatorname{supp}\hat\psi_2 \subseteq [-1, 1]</math> and

:<math>\sum_{k= -1}^{1} |\hat\psi_2(\xi + k)|^2 = 1, \text{for a.e. } \xi\in\left[-1, 1\right].</math> One typically chooses <math>\hat \psi_2</math> to be a smooth bump function. Then <math>\psi \in L^2(\R^2)</math> given by

:<math>\hat\psi(\xi) = \hat\psi_1(\xi_1) \hat\psi_2\left( \tfrac{\xi_2}{\xi_1} \right), \quad \xi = (\xi_1, \xi_2) \in \R^2,</math>

is called a ''classical shearlet''. It can be shown that the corresponding discrete shearlet system <math>\operatorname{SH}(\psi)</math> constitutes a Parseval frame for <math>L^2(\R^2)</math> consisting of bandlimited functions.<ref name=shearletbook/>

Another example are compactly supported shearlet systems, where a compactly supported function <math>\psi \in L^2(\R^2)</math> can be chosen so that <math>\operatorname{SH}(\psi)</math> forms a frame for <math>L^2(\R^2)</math>.<ref name=shearletsparsecompact/><ref name=shearletcompact/><ref name=shearlets3dalpha/><ref name=VideoTextPur/> In this case, all shearlet elements in <math>\operatorname{SH}(\psi)</math> are compactly supported providing superior spatial localization compared to the classical shearlets, which are bandlimited. Although a compactly supported shearlet system does not generally form a Parseval frame, any function <math>f \in L^2(\R^2)</math> can be represented by the shearlet expansion due to its frame property.

== Cone-adapted shearlets ==

One drawback of shearlets defined as above is the directional bias of shearlet elements associated with large shearing parameters. This effect is already recognizable in the frequency tiling of classical shearlets (see Figure in Section #Examples), where the frequency support of a shearlet increasingly aligns along the <math>\xi_2</math>-axis as the shearing parameter <math>s</math> goes to infinity. This causes serious problems when analyzing a function whose Fourier transform is concentrated around the <math>\xi_2</math>-axis.

thumb|alt=Decomposition of the frequency domain into cones|Decomposition of the frequency domain into cones. To deal with this problem, the frequency domain is divided into a low-frequency part and two conic regions (see Figure):

:<math> \begin{align} \mathcal{R} &= \left\{ (\xi_1, \xi_2) \in \R^2 \mid |\xi_1|, |\xi_2| \leq 1 \right\}, \\ \mathcal{C}_{\mathrm{h}} &= \left\{ (\xi_1, \xi_2) \in \R^2 \mid | \xi_2 / \xi_1 | \leq 1, |\xi_1| > 1 \right\}, \\ \mathcal{C}_{\mathrm{v}} &= \left\{ (\xi_1, \xi_2) \in \R^2 \mid | \xi_1 / \xi_2 | \leq 1, |\xi_2| > 1 \right\}. \end{align} </math>

thumb|alt=Frequency tiling of the cone-adapted shearlet system|Frequency tiling of the cone-adapted shearlet system generated by the classical shearlet. The associated ''cone-adapted discrete shearlet system'' consists of three parts, each one corresponding to one of these frequency domains. It is generated by three functions <math> \phi, \psi, \tilde\psi \in L^2(\R^2)</math> and a ''lattice sampling'' factor <math>c = (c_1, c_2) \in (\R_{> 0})^2:</math>

:<math> \operatorname{SH}(\phi, \psi, \tilde\psi; c) = \Phi(\phi; c_1) \cup \Psi(\psi; c) \cup \tilde\Psi(\tilde\psi; c), </math>

where

:<math> \begin{align} \Phi(\phi; c_1) &= \{ \phi_m = \phi(\cdot{} - c_1 m) \mid m \in \Z^2 \}, \\ \Psi(\psi; c) &= \{ \psi_{j,k,m} = 2^{3j/4} \psi(S_k A_{2^j} \cdot{} - M_c m) \mid j \geq 0, |k| \leq \lceil 2^{j/2} \rceil, m \in \Z^2 \}, \\ \tilde\Psi(\tilde\psi; c) &= \{ \tilde{\psi}_{j,k,m} = 2^{3j/4} \psi(\tilde{S}_k \tilde{A}_{2^j} \cdot{} - \tilde{M}_c m) \mid j \geq 0, |k| \leq \lceil 2^{j/2} \rceil, m \in \Z^2 \}, \end{align} </math>

with

:<math> \begin{align} & \tilde{A}_a = \begin{bmatrix} a^{1/2} & 0 \\ 0 & a \end{bmatrix}, \; a > 0, \quad \tilde{S}_s = \begin{bmatrix} 1 & 0 \\ s & 1 \end{bmatrix}, \; s \in \R, \quad M_c = \begin{bmatrix} c_1 & 0 \\ 0 & c_2 \end{bmatrix}, \quad \text{and} \quad \tilde{M}_c = \begin{bmatrix} c_2 & 0 \\ 0 & c_1 \end{bmatrix}. \end{align}</math>

The systems <math>\Psi(\psi)</math> and <math>\tilde\Psi(\tilde\psi)</math> basically differ in the reversed roles of <math>x_1</math> and <math>x_2</math>. Thus, they correspond to the conic regions <math>\mathcal{C}_{\mathrm{h}}</math> and <math>\mathcal{C}_{\mathrm{v}}</math>, respectively. Finally, the ''scaling function'' <math>\phi</math> is associated with the low-frequency part <math>\mathcal{R}</math>.

== Applications ==

* Image processing and computer sciences<ref name=shearletbook/> ** Denoising ** Inverse problems ** Image enhancement ** Edge detection ** Inpainting ** Image separation * PDEs<ref name=shearletbook/> ** Resolution of the wavefront set ** Transport equations * Coorbit theory, characterization of smoothness spaces<ref name=shearletbook/> * Differential geometry: manifold learning

== Generalizations and extensions==

* 3D-Shearlets <ref name=shearlets3dalpha/><ref name=shearletbandlim/> * <math>\alpha</math>-Shearlets <ref name=shearlets3dalpha/> * Parabolic molecules <ref name=parabolicmole/> * Cylindrical Shearlets <ref name=OptSparseJGA/><ref name=Smooth_ACM/>

== References ==

<ref name=shearletbook>Kutyniok, Gitta, and Demetrio Labate, eds. ''Shearlets: Multiscale analysis for multivariate data''. Springer, 2012, {{isbn|0-8176-8315-1}}</ref> <ref name=shearletbandlim>Guo, Kanghui, and Demetrio Labate. "The construction of smooth Parseval frames of shearlets." Mathematical Modelling of Natural Phenomena '''8.01''' (2013): 82–105. {{cite web|url= http://www3.math.tu-berlin.de/numerik/mt/www.shearlet.org/papers/shear_construction.pdf |title=PDF }}</ref> <ref name=shearletcompact>Kittipoom, Pisamai, Gitta Kutyniok, and Wang-Q Lim. "Construction of compactly supported shearlet frames." Constructive Approximation '''35.1''' (2012): 21–72. {{cite arXiv|title=PDF |eprint=1003.5481 |last1=Kittipoom |first1=P. |last2=Kutyniok |first2=G. |last3=Lim |first3=W. |class=math.FA |year=2010 }}</ref> <ref name=shearletsparsebandlim>Guo, Kanghui, and Demetrio Labate. "Optimally sparse multidimensional representation using shearlets." SIAM Journal on Mathematical Analysis '''39.1''' (2007): 298–318. {{cite web|url= http://www3.math.tu-berlin.de/numerik/mt/mt/www.shearlet.org/papers/OSMRuS.pdf |title=PDF }}</ref> <ref name=shearletsparsecompact>Kutyniok, Gitta, and Wang-Q Lim. "Compactly supported shearlets are optimally sparse." Journal of Approximation Theory '''163.11''' (2011): 1564–1589. {{cite web|url= http://www.math.tu-berlin.de/fileadmin/i26_fg-kutyniok/wangQ/paper/JAT-D-10-00168_final.pdf |title=PDF }}</ref> <ref name=shearlets3dalpha>Kutyniok, Gitta, Jakob Lemvig, and Wang-Q Lim. "Optimally sparse approximations of 3D functions by compactly supported shearlet frames." SIAM Journal on Mathematical Analysis '''44.4''' (2012): 2962–3017. {{cite arXiv|title=PDF |eprint=1109.5993 |last1=Kutyniok |first1=Gitta |last2=Lemvig |first2=Jakob |last3=Lim |first3=Wang-Q |class=math.FA |year=2011 }}</ref> <ref name=shearletsintroduction>Guo, Kanghui, Gitta Kutyniok, and Demetrio Labate. "Sparse multidimensional representations using anisotropic dilation and shear operators." Wavelets and Splines (Athens, GA, 2005), G. Chen and MJ Lai, eds., Nashboro Press, Nashville, TN (2006): 189–201. {{cite web|url= http://www3.math.tu-berlin.de/numerik/mt/mt/www.shearlet.org/papers/SMRuADaSO.pdf |title=PDF }}</ref> <ref name=VideoTextPur>Purnendu Banerjee and B. B. Chaudhuri, “Video Text Localization using Wavelet and Shearlet Transforms”, In Proc. SPIE 9021, Document Recognition and Retrieval XXI, 2014 (doi:10.1117/12.2036077).{{cite book|title=Document Recognition and Retrieval XXI |arxiv=1307.4990|last1=Banerjee |first1=Purnendu |last2=Chaudhuri |first2=B. B. |editor1-first=Bertrand|editor1-last=Coüasnon|editor2-first=Eric K|editor2-last=Ringger|chapter=Video text localization using wavelet and shearlet transforms|year=2013 |volume=9021|pages=90210B|doi=10.1117/12.2036077|s2cid=10659099}}</ref> <ref name=cartoonbenchmark>Donoho, David Leigh. "Sparse components of images and optimal atomic decompositions." Constructive Approximation '''17.3''' (2001): 353–382. {{cite news|title=PDF |citeseerx = 10.1.1.379.8993}}</ref> <ref name=parabolicmole>Grohs, Philipp and Kutyniok, Gitta. "Parabolic molecules." Foundations of Computational Mathematics (to appear) {{cite arXiv|title=PDF |eprint=1206.1958 |last1=Grohs |first1=Philipp |last2=Kutyniok |first2=Gitta |class=math.FA |year=2012 }}</ref>

<ref name="OptSparseJGA">{{cite journal |title=Optimally Sparse Representations of Cartoon-Like Cylindrical Data |journal=The Journal of Geometric Analysis |date=2020-08-10 |last1=Easley |first1=Glenn R. |last2=Guo |first2= Kanghui |last3=Labate |first3=Demetrio |last4=Pahari |first4=Basanta R. |volume=39 |issue=9 |pages=8926–8946 |doi=10.1007/s12220-020-00493-0 |s2cid=221675372 |url=https://link.springer.com/article/10.1007/s12220-020-00493-0 |accessdate=2022-01-22 |url-access=subscription }}</ref> <ref name="Smooth_ACM">{{cite journal |title= Smooth projections and the construction of smooth Parseval frames of shearlets |journal=Advances in Computational Mathematics |date=2019-10-29 |last1=Bernhard |first1=Bernhard G. |last2=Labate |first2=Demetrio |last3=Pahari |first3=Basanta R. |volume=45 |issue=5–6 |pages=3241–3264 |doi=10.1007/s10444-019-09736-3 |s2cid=210118010 |url=https://link.springer.com/article/10.1007/s10444-019-09736-3 |accessdate=2022-01-22 |url-access=subscription }}</ref>

</references>

== External links == * [https://www.mathematik.uni-muenchen.de/personen/professoren/kutyniok/ Homepage of Gitta Kutyniok] * [http://www.math.uh.edu/~dlabate/ Homepage of Demetrio Labate]

Category:Image processing Category:Time–frequency analysis Category:Signal processing Category:Wavelets