next up previous contents index
Next: ridgpolrec Up: Reference Previous: istkwave1   Contents   Index


$ \bigcirc$Name

ridgelet Ridgelet transform of an image

$ \bigcirc$Command Synopsis

ridgelet [-I in_im] np in_re out_re out_im

-I in_im : imaginary input (Fimage N*N)

np : resolution np

in_re : real input (Fimage N*N)

out_re : real ridgelets coefficients (Fimage 2N*2N)

out_im : imaginary ridgelets coefficients (Fimage 2N*2N)

$ \bigcirc$Function Summary

void ridgelet (in_re , in_im , np , out_re , out_im )

int np ;

Fimage in_re , in_im ;

Fimage out_re , out_im ;

$ \bigcirc$Description

The module ridgelet computes the np level discrete ridgelet transform of a Fimage according to the algorithm of J.L. Starck, E. Candès et D.Donoho [SCD02]. It transforms a N×N image into a 2N×2N image where, from left to right, we have from thinner details to approximation.

In continuous, the 2D-ridgelet transform in I R2 can be defined as follows:

Let's consider $ \psi$ : I R $ \rightarrow$ I R a smooth univariate function with sufficient decay and satisfying the condition:

$\displaystyle \int_{{\scriptsize\mbox{I\hspace{-0.15em}R}}}^{}$|$\displaystyle \hat{{\psi}}$($\displaystyle \xi$)|2/|$\displaystyle \xi$|2dx < $\displaystyle \infty$

which holds if, for instance, if $ \int$$ \psi$(t)dt = 0.

Let's suppose that $ \psi$ is normalized so that

$\displaystyle \int_{{\scriptsize\mbox{I\hspace{-0.15em}R}}}^{}$|$\displaystyle \hat{{\psi}}$($\displaystyle \xi$)|2|$\displaystyle \xi$|-2dx = 1

$ \forall$a > 0, b $ \in$ I R, $ \forall$$ \theta$ $ \in$ [0, 2$ \pi$], we define the bivariate ridgelet

$\displaystyle \psi_{{a,b,\theta}}^{}$(x1, x2) = $\displaystyle {\frac{{1}}{{\sqrt{a}}}}$$\displaystyle \psi$($\displaystyle {\frac{{x_{1}cos \theta + x_{2}sin \theta-b}}{{a}}}$)


This function is constant along lines x1cos$ \theta$ + x2sin$ \theta$ = k, for k constant in I R. Tranverse to these ridges, it is a wavelet.
Given an integrable bivariate function f (x), we define its ridgelet coefficients by

Rf(a, b,$\displaystyle \theta$) = $\displaystyle \int$$\displaystyle \overline{{\psi}}_{{a,b,\theta}}^{}$(x)f (x)dx

We can reconstruct exactly f from its coefficients thanks to the formula

f (x) = $\displaystyle \int_{0}^{{2\pi}}$$\displaystyle \int_{{\scriptsize\mbox{I\hspace{-0.15em}R}}}^{}$$\displaystyle \int_{0}^{{\infty}}$Rf(a, b,$\displaystyle \theta$)$\displaystyle \psi_{{a,b,\theta}}^{}$(x)$\displaystyle {\frac{{da}}{{a^3}}}$db$\displaystyle {\frac{{d\theta}}{{4\pi}}}$ (12)
valid a.e. for functions wich are both integrable and square integrable. Furthermore, this formula is stable and satisfies a Parseval relation

$\displaystyle \int$| f (x)|2dx = $\displaystyle \int_{0}^{{2\pi}}$$\displaystyle \int_{{\scriptsize\mbox{I\hspace{-0.15em}R}}}^{}$$\displaystyle \int_{0}^{{\infty}}$| Rf(a, b,$\displaystyle \theta$)|2$\displaystyle {\frac{{da}}{{a^3}}}$db$\displaystyle {\frac{{d\theta}}{{4\pi}}}$

Hence, as for wavelet or Fourier transforms, the identity (1) expresses the fact that one can represent any arbitrary function as a continuous superposition of ridgelets.

Let's go back to the coefficients Rf(a, b,$ \theta$) calculus. We can view ridgelet analysis as a form of wavelet analysis in the Radon domain. We recall that the Radon transform of an object f is the collection of line integrals indexed by ($ \theta$, t) $ \in$ [0, 2$ \pi$$ \scriptsize\mbox{I\hspace{-0.15em}R}$ given by

Rf ($\displaystyle \theta$, t) = $\displaystyle \int_{{\scriptsize\mbox{I\hspace{-0.15em}R}}}^{}$f (x1, x2)$\displaystyle \delta$(x1cos$\displaystyle \theta$+x2sin$\displaystyle \theta$-t)dx1dx2

where $ \delta$ is the Dirac distribution. The ridgelet coefficients Rf(a, b,$ \theta$) of f are given by analysis of the Radon transform via

Rf(a, b,$\displaystyle \theta$) = $\displaystyle \int_{{\scriptsize\mbox{I\hspace{-0.15em}R}}}^{}$Rf (t,$\displaystyle \theta$)a-$\scriptstyle {\frac{{1}}{{2}}}$$\displaystyle \psi$($\displaystyle {\frac{{t-b}}{{a}}}$)dt

Hence the ridgelet transform is precisely the application of a one-dimensional wavelet transform to the slices of the Radon transfom where the angular variable $ \theta$ is constant and t is varying.

Our algorithm starts calculating the Radon transform Rf (t,$ \theta$), and then applies the one-dimensional wavelet transform to the slices Rf (.,$ \theta$). In order to calculate the Radon transform, we use the projection-slice formula:

$\displaystyle \hat{f}$($\displaystyle \lambda$cos$\displaystyle \theta$,$\displaystyle \lambda$sin$\displaystyle \theta$) = $\displaystyle \int$Rf (t,$\displaystyle \theta$)exp(-it$\displaystyle \lambda$)dt

This means that the Radon transform can be obtained by applying the one-dimensional inverse Fourier transform to the two-dimensional Fourier transform restricted to radial lines going through the origin. Given a square image, the algorithm follows successively these steps:
  1. Compute the 2D-FFT of f, giving an image $ \hat{f}$
  2. Conversion of the cartesian grid into a polar grid: interpolating, we substitute the sampled values of the Fourier transform obtained on the square lattice with sampled values of $ \hat{f}$ on a polar lattice (ie where the points fall on lines going through the origin)
  3. Apply the 1D-wavelet transform on the radial lines in the Fourier domain.

$ \bigcirc$See Also

fft2d, fline_extract, ridgrecpol, stkwave1.


$ \bigcirc$Version 1.0

Last Modification date : Thu Apr 15 08:03:52 2004

$ \bigcirc$Author

Claire Jonchery, Amandine Robin

next up previous contents index
Next: ridgpolrec Up: Reference Previous: istkwave1   Contents   Index
mw 2004-05-05