View source for Large extra dimension

{{cleanup|reason=poor math and text formatting|date=May 2013}}

'''Curvelets''' are a non-[[Adaptive-additive algorithm|adaptive]] technique for multi-scale [[Object (computer science)|object]] representation. Being an extension of the [[wavelet]] concept, they are becoming popular in similar fields, namely in [[image processing]] and [[scientific computing]].

Wavelets generalize the [[Fourier transform]] by using a basis that represents both location and spatial frequency. For 2D or 3D signals, directional wavelet transforms go further, by using basis functions that are also localized in ''orientation''. A curvelet transform differs from other directional wavelet transforms in that the degree of localisation in orientation varies with scale. In particular, fine-scale basis functions are long ridges; the shape of the basis functions at scale ''j'' is <math>2^{-j}</math> by <math>2^{-j/2}</math> so the fine-scale bases are skinny ridges with a precisely determined orientation.

Curvelets are an appropriate basis for representing images (or other functions) which are smooth apart from singularities along smooth curves, ''where the curves have bounded curvature'', i.e. where objects in the image have a minimum length scale. This property holds for cartoons, geometrical diagrams, and text. As one zooms in on such images, the edges they contain appear increasingly straight. Curvelets take advantage of this property, by defining the higher resolution curvelets to be more elongated than the lower resolution curvelets. However, natural images (photographs) do not have this property; they have detail at every scale. Therefore, for natural images, it is preferable to use some sort of directional wavelet transform whose wavelets have the same aspect ratio at every scale.

When the image is of the right type, curvelets provide a representation that is considerably sparser than other wavelet transforms. This can be quantified by considering the best approximation of a geometrical test image that can be represented using only <math>n</math> wavelets, and analysing the approximation error as a function of <math>n</math>. For a Fourier transform, the squared error decreases only as <math>O(1/n^{1/2})</math>. For a wide variety of wavelet transforms, including both directional and non-directional variants, the squared error decreases as <math>O(1/n)</math>. The extra assumption underlying the curvelet transform allows it to achieve <math>O({(log(n))}^3/{n^2})</math>.

Efficient numerical algorithms exist for computing the curvelet transform of discrete data. The computational cost of a curvelet transform is approximately 10–20 times that of an FFT, and has the same dependence of <math>O(n^2log(n))</math>  for an image of size <math>n \times n</math>.

== Curvelet construction ==
To construct a basic curvelet <math>\phi</math> and provide a tiling of the 2-D frequency space, two main ideas should be followed:
# Consider polar coordinates in frequency domain
# Construct curvelet elements being locally supported near wedges

The number of wedges is <math> N_j = 4 \cdot 2^{\left \lceil \frac{j}{2} \right \rceil}</math> 
at the scale <math>2^{-j}</math>, i.e., it doubles in each second second circular ring.<br />

Let <math>\boldsymbol{\xi}=(\xi_1,\xi_2)^T</math> <br />
be the variable in frequency domain, and <math>r=\sqrt{\xi_1^2+\xi_2^2}, \omega=\arctan \frac{\xi_1}{\xi_2}</math> be the polar coordinates in the frequency domain.
<br />

We use the [[ansatz]] for the ''dilated basic curvelets'' in polar coordinates:<br />
<math>\hat{\phi}_{j,0,0}:=2^{\frac{-3j}{4}}W(2^{-j}r)\tilde{V}_{N_j}(\omega), r\ge 0, \omega \in [0,2\pi), j \in N_0</math><br /><br />

To construct a basic curvelet with compact support near a ″basic wedge″, the two windows <math>W</math> and <math>\tilde{V}_{N_j}</math>need to have compact support.
Here, we can simply take <math>W(r)</math> to cover <math>(0,\infty)</math>with dilated curvelets and <math>\tilde{V}_{N_j}</math> such that each circular ring is covered by the translations of <math>\tilde{V}_{N_j}</math> .<br />

Then the admissibility yields<br />
<math>\sum_{j=-\infty}^{\infty}\left| W(2^{-j}r) \right|^2=1, r \in (0,\infty).</math><sub>see ''[[Window function|Window Functions]]'' for more information</sub><br />
<br />
For tiling a circular ring into <math>N</math> wedges, where <math>N</math> is an arbitrary positive integer, we need a <math>2\pi</math>-periodic nonnegative window <math>\tilde{V}_{N}</math> with support inside <math>\left[ \frac{-2\pi}{N}, \frac{2\pi}{N} \right]</math> such that<br />
<math>\sum_{l=0}^{N-1}\tilde{V}^2_N(\omega-\frac{2\pi l}{N})=1</math>, for all <math>\omega \in \left[ 0, 2\pi \right)</math><br />
<math>\tilde{V}_N</math> can be simply constructed as <math>2\pi</math>-periodizations of a scaled window <math>V(\frac{N\omega}{2\pi})</math>.<br />
<br />
Then, it follows that<br />
<math>\sum_{l=0}^{N_j-1}\left| 2^{\frac{3j}{4}}\hat{\phi}_{j,0,0}(r, \omega-\frac{2\pi l}{N_j}) \right| ^2=\left|W(2^{-j}r) \right|^2\sum_{l=0}^{N_j-1}\tilde{V}^2_{N_j}(\omega-\frac{2\pi l}{N})=\left|W(2^{-j}r) \right|^2</math>

For a complete covering of the frequency plane including the region around zero, we need to define a low pass element<br />
<math>\hat{\phi}_{-1}:=W_0(\left| \xi \right|) with </math><br />
<math>W_0^2(r)^2:=1-\sum_{j=0}^{\infty}W(2^{-j}r)^2</math><br />
that is supported on the unit circle, and where we do not consider any rotation.

== Applications ==
* [[Image Processing]]
* Seismic Exploration
* [[Fluid Mechanics]]
* [[PDE]]s Solving
* Compressed Sensing

== See also ==
* [[Shearlet|Shearlet transform]]
* [[Bandelet|Bandelet transform]]
* [[Contourlet|Contourlet transform]] 
* [[Fresnel transform|Fresnelet transform]]
* [[Chirplet transform]]
* [[Noiselet |Noiselet transform]]
* [[Scale space]]

== References ==
*[[Emmanuel Candès|E. Candès]] and D. Donoho, "Curvelets – a surprisingly effective nonadaptive representation for objects with edges." In: A. Cohen, C. Rabut and L. Schumaker, Editors, ''Curves and Surface Fitting'': Saint-Malo 1999, Vanderbilt University Press, Nashville (2000), pp. 105&ndash;120.
* Majumdar Angshul [http://jprr.org/index.php/jprr/article/view/27 Bangla Basic Character Recognition using Digital Curvelet Transform] Journal of Pattern Recognition Research ([http://www.jprr.org JPRR]), Vol 2. (1) 2007 p.17-26
* Emmanuel Candes, Laurent Demanet, David Donoho and Lexing Ying [http://www.curvelet.org/papers/FDCT.pdf Fast Discrete Curvelet Transforms]
* J Ma, G Plonka, ''The Curvelet Transform'': Signal Processing Magazine, IEEE, 2010 - ieeexplore.ieee.org
* Jean-Luc Starck, Emmanuel J. Candès, and David L. Donoho, ''The Curvelet Transform for Image Denoising,'': IEEE Transactions on Image Processing, Vol. 11, No. 6, June 2002

== External links ==
*[http://curvelet.org/ Curvelet.org homepage]
[[Category:Image processing]]
[[Category:Time–frequency analysis]]
[[Category:Wavelets]]
It is used in object recognition