<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 3.2 Final//EN">
<!--Converted with LaTeX2HTML 98.1p1 release (March 2nd, 1998)
originally by Nikos Drakos (nikos@cbl.leeds.ac.uk), CBLU, University of Leeds
* revised and updated by: Marcus Hennecke, Ross Moore, Herb Swan
* with significant contributions from:
Jens Lippmann, Marek Rouchal, Martin Wilck and others -->
<HTML>
<HEAD>
<TITLE>The Wavelet transform using the Fourier transform</TITLE>
<META NAME="description" CONTENT="The Wavelet transform using the Fourier transform">
<META NAME="keywords" CONTENT="vol2">
<META NAME="resource-type" CONTENT="document">
<META NAME="distribution" CONTENT="global">
<META HTTP-EQUIV="Content-Type" CONTENT="text/html; charset=iso-8859-1">
<LINK REL="STYLESHEET" HREF="vol2.css">
<LINK REL="next" HREF="node323.html">
<LINK REL="previous" HREF="node321.html">
<LINK REL="up" HREF="node321.html">
<LINK REL="next" HREF="node323.html">
</HEAD>
<BODY >
<!--Navigation Panel-->
<A NAME="tex2html5475"
HREF="node323.html">
<IMG WIDTH="37" HEIGHT="24" ALIGN="BOTTOM" BORDER="0" ALT="next"
SRC="icons.gif/next_motif.gif"></A>
<A NAME="tex2html5472"
HREF="node321.html">
<IMG WIDTH="26" HEIGHT="24" ALIGN="BOTTOM" BORDER="0" ALT="up"
SRC="icons.gif/up_motif.gif"></A>
<A NAME="tex2html5466"
HREF="node321.html">
<IMG WIDTH="63" HEIGHT="24" ALIGN="BOTTOM" BORDER="0" ALT="previous"
SRC="icons.gif/previous_motif.gif"></A>
<A NAME="tex2html5474"
HREF="node1.html">
<IMG WIDTH="65" HEIGHT="24" ALIGN="BOTTOM" BORDER="0" ALT="contents"
SRC="icons.gif/contents_motif.gif"></A>
<BR>
<B> Next:</B> <A NAME="tex2html5476"
HREF="node323.html">The Reconstruction</A>
<B> Up:</B> <A NAME="tex2html5473"
HREF="node321.html">Multiresolution with scaling functions</A>
<B> Previous:</B> <A NAME="tex2html5467"
HREF="node321.html">Multiresolution with scaling functions</A>
<BR>
<BR>
<!--End of Navigation Panel-->
<H3><A NAME="SECTION002045100000000000000">
The Wavelet transform using the Fourier transform</A>
</H3>
We start with the set of scalar products
<!-- MATH: $c_0(k)=<f(x),\phi(x-k)>$ -->
<IMG
WIDTH="256" HEIGHT="44" ALIGN="MIDDLE" BORDER="0"
SRC="img693.gif"
ALT="$c_0(k)=<f(x),\phi(x-k)>$">.
If
<IMG
WIDTH="49" HEIGHT="44" ALIGN="MIDDLE" BORDER="0"
SRC="img694.gif"
ALT="$\phi(x)$">
has a cut-off frequency
<!-- MATH: $\nu_c\le {1\over 2}$ -->
<IMG
WIDTH="66" HEIGHT="49" ALIGN="MIDDLE" BORDER="0"
SRC="img695.gif"
ALT="$\nu_c\le {1\over 2}$">[#starck1<#14704<A
HREF="node370.html#>"></A>,#starck2<#14705<A
HREF="node370.html#>"></A>,#starck3<#14706<A
HREF="node370.html#>"></A>,#starck4<#14707<A
HREF="node370.html#>"></A>], the data are
correctly sampled. The data at the resolution <I>j</I>=1 are:
<BR>
<DIV ALIGN="CENTER">
<!-- MATH: \begin{eqnarray}
c_1(k)=<f(x),\frac{1}{2}\phi(\frac{x}{2}-k)>
\end{eqnarray} -->
<TABLE ALIGN="CENTER" CELLPADDING="0" WIDTH="100%">
<TR VALIGN="MIDDLE"><TD NOWRAP ALIGN="RIGHT"><IMG
WIDTH="277" HEIGHT="69" ALIGN="MIDDLE" BORDER="0"
SRC="img696.gif"
ALT="$\displaystyle c_1(k)=<f(x),\frac{1}{2}\phi(\frac{x}{2}-k)>$"></TD>
<TD> </TD>
<TD> </TD>
<TD WIDTH=10 ALIGN="RIGHT">
(14.47)</TD></TR>
</TABLE></DIV>
<BR CLEAR="ALL"><P></P>
and we can compute the set <I>c</I><SUB>1</SUB>(<I>k</I>) from <I>c</I><SUB>0</SUB>(<I>k</I>) with a discrete
filter
<!-- MATH: $\hat h(\nu)$ -->
<IMG
WIDTH="47" HEIGHT="53" ALIGN="MIDDLE" BORDER="0"
SRC="img697.gif"
ALT="$\hat h(\nu)$">:
<BR>
<DIV ALIGN="CENTER">
<!-- MATH: \begin{eqnarray}
\hat h(\nu)= \left\{
\begin{array}{ll}
{\hat{\phi}(2\nu)\over \hat{\phi}(\nu)} & \mbox{if } \mid \nu \mid < \nu_c \\
0 & \mbox{if } \nu_c \leq \mid \nu \mid < {1\over 2}
\end{array}
\right.
\end{eqnarray} -->
<TABLE ALIGN="CENTER" CELLPADDING="0" WIDTH="100%">
<TR VALIGN="MIDDLE"><TD NOWRAP ALIGN="RIGHT"><IMG
WIDTH="318" HEIGHT="94" ALIGN="MIDDLE" BORDER="0"
SRC="img698.gif"
ALT="$\displaystyle \hat h(\nu)= \left\{
\begin{array}{ll}
{\hat{\phi}(2\nu)\over \ha...
...u_c \\
0 & \mbox{if } \nu_c \leq \mid \nu \mid < {1\over 2}
\end{array}\right.$"></TD>
<TD> </TD>
<TD> </TD>
<TD WIDTH=10 ALIGN="RIGHT">
(14.48)</TD></TR>
</TABLE></DIV>
<BR CLEAR="ALL"><P></P>
and
<BR>
<DIV ALIGN="CENTER">
<!-- MATH: \begin{eqnarray}
\forall \nu, \forall n \mbox{ } & \hat h(\nu + n) = \hat h(\nu)
\end{eqnarray} -->
<TABLE ALIGN="CENTER" CELLPADDING="0" WIDTH="100%">
<TR VALIGN="MIDDLE"><TD NOWRAP ALIGN="RIGHT"><IMG
WIDTH="70" HEIGHT="41" ALIGN="MIDDLE" BORDER="0"
SRC="img699.gif"
ALT="$\displaystyle \forall \nu, \forall n \mbox{ }$"></TD>
<TD ALIGN="CENTER" NOWRAP><IMG
WIDTH="159" HEIGHT="53" ALIGN="MIDDLE" BORDER="0"
SRC="img700.gif"
ALT="$\textstyle \hat h(\nu + n) = \hat h(\nu)$"></TD>
<TD> </TD>
<TD WIDTH=10 ALIGN="RIGHT">
(14.49)</TD></TR>
</TABLE></DIV>
<BR CLEAR="ALL"><P></P>
where <I>n</I> is an integer.
So:
<BR>
<DIV ALIGN="CENTER">
<!-- MATH: \begin{eqnarray}
\hat{c}_{j+1}(\nu)=\hat{c}_{j}(\nu)\hat{h}(2^{j}\nu)
\end{eqnarray} -->
<TABLE ALIGN="CENTER" CELLPADDING="0" WIDTH="100%">
<TR VALIGN="MIDDLE"><TD NOWRAP ALIGN="RIGHT"><IMG
WIDTH="212" HEIGHT="53" ALIGN="MIDDLE" BORDER="0"
SRC="img701.gif"
ALT="$\displaystyle \hat{c}_{j+1}(\nu)=\hat{c}_{j}(\nu)\hat{h}(2^{j}\nu)$"></TD>
<TD> </TD>
<TD> </TD>
<TD WIDTH=10 ALIGN="RIGHT">
(14.50)</TD></TR>
</TABLE></DIV>
<BR CLEAR="ALL"><P></P>
The cut-off frequency is reduced by a factor 2 at each step, allowing a
reduction of the number of samples by this factor.
<P>
The wavelet coefficients at the scale <I>j</I>+1 are:
<BR>
<DIV ALIGN="CENTER">
<!-- MATH: \begin{eqnarray}
w_{j+1}(k)=<f(x),2^{-(j+1)}\psi(2^{-(j+1)}x-k)>
\end{eqnarray} -->
<TABLE ALIGN="CENTER" CELLPADDING="0" WIDTH="100%">
<TR VALIGN="MIDDLE"><TD NOWRAP ALIGN="RIGHT"><IMG
WIDTH="421" HEIGHT="53" ALIGN="MIDDLE" BORDER="0"
SRC="img702.gif"
ALT="$\displaystyle w_{j+1}(k)=<f(x),2^{-(j+1)}\psi(2^{-(j+1)}x-k)>$"></TD>
<TD> </TD>
<TD> </TD>
<TD WIDTH=10 ALIGN="RIGHT">
(14.51)</TD></TR>
</TABLE></DIV>
<BR CLEAR="ALL"><P></P>
and they can be computed directly from <I>c</I><SUB><I>j</I></SUB>(<I>k</I>) by:
<BR>
<DIV ALIGN="CENTER">
<!-- MATH: \begin{eqnarray}
\hat{w}_{j+1}(\nu)=\hat{c}_{j}(\nu)\hat g(2^{j}\nu)
\end{eqnarray} -->
<TABLE ALIGN="CENTER" CELLPADDING="0" WIDTH="100%">
<TR VALIGN="MIDDLE"><TD NOWRAP ALIGN="RIGHT"><IMG
WIDTH="217" HEIGHT="51" ALIGN="MIDDLE" BORDER="0"
SRC="img703.gif"
ALT="$\displaystyle \hat{w}_{j+1}(\nu)=\hat{c}_{j}(\nu)\hat g(2^{j}\nu)$"></TD>
<TD> </TD>
<TD> </TD>
<TD WIDTH=10 ALIGN="RIGHT">
(14.52)</TD></TR>
</TABLE></DIV>
<BR CLEAR="ALL"><P></P>
where <I>g</I> is the following discrete filter:
<BR>
<DIV ALIGN="CENTER">
<!-- MATH: \begin{eqnarray}
\hat g(\nu)= \left\{
\begin{array}{ll}
{\hat{\psi}(2\nu)\over \hat{\phi}(\nu)} & \mbox{if } \mid \nu \mid < \nu_c \\
1 & \mbox{if } \nu_c \leq \mid \nu \mid < {1\over 2}
\end{array}
\right.
\end{eqnarray} -->
<TABLE ALIGN="CENTER" CELLPADDING="0" WIDTH="100%">
<TR VALIGN="MIDDLE"><TD NOWRAP ALIGN="RIGHT"><IMG
WIDTH="318" HEIGHT="94" ALIGN="MIDDLE" BORDER="0"
SRC="img704.gif"
ALT="$\displaystyle \hat g(\nu)= \left\{
\begin{array}{ll}
{\hat{\psi}(2\nu)\over \ha...
...u_c \\
1 & \mbox{if } \nu_c \leq \mid \nu \mid < {1\over 2}
\end{array}\right.$"></TD>
<TD> </TD>
<TD> </TD>
<TD WIDTH=10 ALIGN="RIGHT">
(14.53)</TD></TR>
</TABLE></DIV>
<BR CLEAR="ALL"><P></P>
and
<BR>
<DIV ALIGN="CENTER">
<!-- MATH: \begin{eqnarray}
\forall \nu, \forall n \mbox{ } & \hat g(\nu + n) = \hat g(\nu)
\end{eqnarray} -->
<TABLE ALIGN="CENTER" CELLPADDING="0" WIDTH="100%">
<TR VALIGN="MIDDLE"><TD NOWRAP ALIGN="RIGHT"><IMG
WIDTH="70" HEIGHT="41" ALIGN="MIDDLE" BORDER="0"
SRC="img705.gif"
ALT="$\displaystyle \forall \nu, \forall n \mbox{ }$"></TD>
<TD ALIGN="CENTER" NOWRAP><IMG
WIDTH="156" HEIGHT="44" ALIGN="MIDDLE" BORDER="0"
SRC="img706.gif"
ALT="$\textstyle \hat g(\nu + n) = \hat g(\nu)$"></TD>
<TD> </TD>
<TD WIDTH=10 ALIGN="RIGHT">
(14.54)</TD></TR>
</TABLE></DIV>
<BR CLEAR="ALL"><P></P>
<P>
The frequency band is also reduced by a factor 2 at each step.
Applying the sampling theorem, we can build a pyramid of
<!-- MATH: $N+{N\over 2}+\ldots+1=2N$ -->
<IMG
WIDTH="221" HEIGHT="50" ALIGN="MIDDLE" BORDER="0"
SRC="img707.gif"
ALT="$N+{N\over 2}+\ldots+1=2N$">
elements.
For an image analysis the number of elements is
<!-- MATH: ${4\over 3}N^2$ -->
<IMG
WIDTH="49" HEIGHT="49" ALIGN="MIDDLE" BORDER="0"
SRC="img708.gif"
ALT="${4\over 3}N^2$">.
The
overdetermination is not very high.
<P>
The B-spline functions are compact in this directe space. They
correspond to the autoconvolution of a square function. In
the Fourier space we have:
<BR>
<DIV ALIGN="CENTER">
<!-- MATH: \begin{eqnarray}
\hat B_l(\nu)={\sin\pi\nu\over\pi\nu}^{l+1}
\end{eqnarray} -->
<TABLE ALIGN="CENTER" CELLPADDING="0" WIDTH="100%">
<TR VALIGN="MIDDLE"><TD NOWRAP ALIGN="RIGHT"><IMG
WIDTH="174" HEIGHT="79" ALIGN="MIDDLE" BORDER="0"
SRC="img709.gif"
ALT="$\displaystyle \hat B_l(\nu)={\sin\pi\nu\over\pi\nu}^{l+1}$"></TD>
<TD> </TD>
<TD> </TD>
<TD WIDTH=10 ALIGN="RIGHT">
(14.55)</TD></TR>
</TABLE></DIV>
<BR CLEAR="ALL"><P></P><I>B</I><SUB>3</SUB>(<I>x</I>) is a set of 4 polynomials of degree 3.
We choose the scaling function <IMG
WIDTH="48" HEIGHT="44" ALIGN="MIDDLE" BORDER="0"
SRC="img710.gif"
ALT="$\phi(\nu)$">
which has a
<I>B</I><SUB>3</SUB>(<I>x</I>) profile in the Fourier space:
<BR>
<DIV ALIGN="CENTER">
<!-- MATH: \begin{eqnarray}
\hat{\phi}(\nu)={3\over 2}B_3(4\nu)
\end{eqnarray} -->
<TABLE ALIGN="CENTER" CELLPADDING="0" WIDTH="100%">
<TR VALIGN="MIDDLE"><TD NOWRAP ALIGN="RIGHT"><IMG
WIDTH="158" HEIGHT="69" ALIGN="MIDDLE" BORDER="0"
SRC="img711.gif"
ALT="$\displaystyle \hat{\phi}(\nu)={3\over 2}B_3(4\nu)$"></TD>
<TD> </TD>
<TD> </TD>
<TD WIDTH=10 ALIGN="RIGHT">
(14.56)</TD></TR>
</TABLE></DIV>
<BR CLEAR="ALL"><P></P>
In the direct space we get:
<BR>
<DIV ALIGN="CENTER">
<!-- MATH: \begin{eqnarray}
\phi(x)={3\over 8}[{\sin{\pi x\over 4}\over {\pi x\over
4}}]^4
\end{eqnarray} -->
<TABLE ALIGN="CENTER" CELLPADDING="0" WIDTH="100%">
<TR VALIGN="MIDDLE"><TD NOWRAP ALIGN="RIGHT"><IMG
WIDTH="175" HEIGHT="74" ALIGN="MIDDLE" BORDER="0"
SRC="img712.gif"
ALT="$\displaystyle \phi(x)={3\over 8}[{\sin{\pi x\over 4}\over {\pi x\over
4}}]^4$"></TD>
<TD> </TD>
<TD> </TD>
<TD WIDTH=10 ALIGN="RIGHT">
(14.57)</TD></TR>
</TABLE></DIV>
<BR CLEAR="ALL"><P></P>
This function is quite similar to a Gaussian one and converges
rapidly to 0. For 2-D the scaling function is defined by
<!-- MATH: $\hat \phi(u,v) = {3\over 2}B_3(4r)$ -->
<IMG
WIDTH="175" HEIGHT="53" ALIGN="MIDDLE" BORDER="0"
SRC="img713.gif"
ALT="$\hat \phi(u,v) = {3\over 2}B_3(4r)$">,
with
<!-- MATH: $r = \sqrt(u^2+v^2)$ -->
<IMG
WIDTH="152" HEIGHT="50" ALIGN="MIDDLE" BORDER="0"
SRC="img714.gif"
ALT="$r = \sqrt(u^2+v^2)$">.
It is an isotropic function.
<P>
The wavelet transform algorithm with <I>n</I><SUB><I>p</I></SUB> scales is the following one:
<DL COMPACT>
<DT>1.
<DD>We start with a B3-Spline scaling function and we derive <IMG
WIDTH="20" HEIGHT="41" ALIGN="MIDDLE" BORDER="0"
SRC="img715.gif"
ALT="$\psi$">,
<I>h</I> and
<I>g</I> numerically.
<DT>2.
<DD>We compute the corresponding image FFT. We name <I>T</I><SUB>0</SUB> the resulting complex array;
<DT>3.
<DD>We set <I>j</I> to 0. We iterate:
<DT>4.
<DD>We multiply <I>T</I><SUB><I>j</I></SUB> by
<!-- MATH: $\hat g(2^ju,2^jv)$ -->
<IMG
WIDTH="107" HEIGHT="48" ALIGN="MIDDLE" BORDER="0"
SRC="img716.gif"
ALT="$\hat g(2^ju,2^jv)$">.
We get the complex array
<I>W</I><SUB><I>j</I>+1</SUB>. The inverse FFT
gives the wavelet coefficients at the scale 2<SUP><I>j</I></SUP>;
<DT>5.
<DD>We multiply <I>T</I><SUB><I>j</I></SUB> by
<!-- MATH: $\hat h(2^ju,2^jv)$ -->
<IMG
WIDTH="108" HEIGHT="53" ALIGN="MIDDLE" BORDER="0"
SRC="img717.gif"
ALT="$\hat h(2^ju,2^jv)$">.
We get the array
<I>T</I><SUB><I>j</I>+1</SUB>. Its inverse FFT gives the image at the scale 2<SUP><I>j</I>+1</SUP>.
The frequency band is reduced by a factor 2.
<DT>6.
<DD>We increment <I>j</I>
<DT>7.
<DD>If
<!-- MATH: $j \leq n_p$ -->
<IMG
WIDTH="68" HEIGHT="40" ALIGN="MIDDLE" BORDER="0"
SRC="img718.gif"
ALT="$j \leq n_p$">,
we go back to 4.
<DT>8.
<DD>The set
<!-- MATH: $\{w_1, w_2, \dots, w_{n_p}, c_{n_p}\}$ -->
<IMG
WIDTH="210" HEIGHT="44" ALIGN="MIDDLE" BORDER="0"
SRC="img719.gif"
ALT="$\{w_1, w_2, \dots, w_{n_p}, c_{n_p}\}$">
describes the
wavelet transform.
</DL>
<P>
If the wavelet is the difference between two resolutions, we have:
<BR>
<DIV ALIGN="CENTER">
<!-- MATH: \begin{eqnarray}
\hat \psi(2\nu) = \hat \phi(\nu) - \hat \phi(2\nu)
\end{eqnarray} -->
<TABLE ALIGN="CENTER" CELLPADDING="0" WIDTH="100%">
<TR VALIGN="MIDDLE"><TD NOWRAP ALIGN="RIGHT"><IMG
WIDTH="212" HEIGHT="53" ALIGN="MIDDLE" BORDER="0"
SRC="img720.gif"
ALT="$\displaystyle \hat \psi(2\nu) = \hat \phi(\nu) - \hat \phi(2\nu)$"></TD>
<TD> </TD>
<TD> </TD>
<TD WIDTH=10 ALIGN="RIGHT">
(14.58)</TD></TR>
</TABLE></DIV>
<BR CLEAR="ALL"><P></P>
and:
<BR>
<DIV ALIGN="CENTER">
<!-- MATH: \begin{eqnarray}
\hat g(\nu) = 1 - \hat h(\nu)
\end{eqnarray} -->
<TABLE ALIGN="CENTER" CELLPADDING="0" WIDTH="100%">
<TR VALIGN="MIDDLE"><TD NOWRAP ALIGN="RIGHT"><IMG
WIDTH="154" HEIGHT="53" ALIGN="MIDDLE" BORDER="0"
SRC="img721.gif"
ALT="$\displaystyle \hat g(\nu) = 1 - \hat h(\nu)$"></TD>
<TD> </TD>
<TD> </TD>
<TD WIDTH=10 ALIGN="RIGHT">
(14.59)</TD></TR>
</TABLE></DIV>
<BR CLEAR="ALL"><P></P>
then the wavelet coefficients
<!-- MATH: $\hat w_j(\nu)$ -->
<IMG
WIDTH="60" HEIGHT="44" ALIGN="MIDDLE" BORDER="0"
SRC="img722.gif"
ALT="$\hat w_j(\nu)$">
can be computed by
<!-- MATH: $\hat c_{j-1}(\nu) - \hat c_j(\nu)$ -->
<IMG
WIDTH="148" HEIGHT="44" ALIGN="MIDDLE" BORDER="0"
SRC="img723.gif"
ALT="$\hat c_{j-1}(\nu) - \hat c_j(\nu)$">.
<P>
<HR>
<!--Navigation Panel-->
<A NAME="tex2html5475"
HREF="node323.html">
<IMG WIDTH="37" HEIGHT="24" ALIGN="BOTTOM" BORDER="0" ALT="next"
SRC="icons.gif/next_motif.gif"></A>
<A NAME="tex2html5472"
HREF="node321.html">
<IMG WIDTH="26" HEIGHT="24" ALIGN="BOTTOM" BORDER="0" ALT="up"
SRC="icons.gif/up_motif.gif"></A>
<A NAME="tex2html5466"
HREF="node321.html">
<IMG WIDTH="63" HEIGHT="24" ALIGN="BOTTOM" BORDER="0" ALT="previous"
SRC="icons.gif/previous_motif.gif"></A>
<A NAME="tex2html5474"
HREF="node1.html">
<IMG WIDTH="65" HEIGHT="24" ALIGN="BOTTOM" BORDER="0" ALT="contents"
SRC="icons.gif/contents_motif.gif"></A>
<BR>
<B> Next:</B> <A NAME="tex2html5476"
HREF="node323.html">The Reconstruction</A>
<B> Up:</B> <A NAME="tex2html5473"
HREF="node321.html">Multiresolution with scaling functions</A>
<B> Previous:</B> <A NAME="tex2html5467"
HREF="node321.html">Multiresolution with scaling functions</A>
<!--End of Navigation Panel-->
<ADDRESS>
<I>Petra Nass</I>
<BR><I>1999-06-15</I>
</ADDRESS>
</BODY>
</HTML>
