<!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 convolution from the continuous wavelet transform</TITLE>
<META NAME="description" CONTENT="The convolution from the continuous wavelet 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="node330.html">
<LINK REL="previous" HREF="node328.html">
<LINK REL="up" HREF="node328.html">
<LINK REL="next" HREF="node330.html">
</HEAD>
<BODY >
<!--Navigation Panel-->
<A NAME="tex2html5556"
HREF="node330.html">
<IMG WIDTH="37" HEIGHT="24" ALIGN="BOTTOM" BORDER="0" ALT="next"
SRC="icons.gif/next_motif.gif"></A>
<A NAME="tex2html5553"
HREF="node328.html">
<IMG WIDTH="26" HEIGHT="24" ALIGN="BOTTOM" BORDER="0" ALT="up"
SRC="icons.gif/up_motif.gif"></A>
<A NAME="tex2html5547"
HREF="node328.html">
<IMG WIDTH="63" HEIGHT="24" ALIGN="BOTTOM" BORDER="0" ALT="previous"
SRC="icons.gif/previous_motif.gif"></A>
<A NAME="tex2html5555"
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="tex2html5557"
HREF="node330.html">The Wiener-like filtering in</A>
<B> Up:</B> <A NAME="tex2html5554"
HREF="node328.html">Noise reduction from the</A>
<B> Previous:</B> <A NAME="tex2html5548"
HREF="node328.html">Noise reduction from the</A>
<BR>
<BR>
<!--End of Navigation Panel-->
<H2><A NAME="SECTION002061000000000000000">
The convolution from the continuous wavelet transform</A>
</H2>
We will examine here the computation of a convolution
by using the continuous wavelet transform in order to get a framework for
linear smoothings. Let us consider the
convolution product of two functions:
<BR>
<DIV ALIGN="CENTER">
<!-- MATH: \begin{eqnarray}
h(x)=\int_{-\infty}^{+\infty} f(u)g(x-u)dx
\end{eqnarray} -->
<TABLE ALIGN="CENTER" CELLPADDING="0" WIDTH="100%">
<TR VALIGN="MIDDLE"><TD NOWRAP ALIGN="RIGHT"><IMG
WIDTH="277" HEIGHT="73" ALIGN="MIDDLE" BORDER="0"
SRC="img767.gif"
ALT="$\displaystyle h(x)=\int_{-\infty}^{+\infty} f(u)g(x-u)dx$"></TD>
<TD> </TD>
<TD> </TD>
<TD WIDTH=10 ALIGN="RIGHT">
(14.68)</TD></TR>
</TABLE></DIV>
<BR CLEAR="ALL"><P></P>
We introduce two real wavelets functions <IMG
WIDTH="51" HEIGHT="44" ALIGN="MIDDLE" BORDER="0"
SRC="img768.gif"
ALT="$\psi(x)$">
and <IMG
WIDTH="48" HEIGHT="44" ALIGN="MIDDLE" BORDER="0"
SRC="img769.gif"
ALT="$\chi(x)$">such that:
<BR>
<DIV ALIGN="CENTER">
<!-- MATH: \begin{eqnarray}
C=\int_0^{+\infty} \frac{\hat{\psi}^*(\nu)\hat{\chi}(\nu)}{\nu}d\nu
\end{eqnarray} -->
<TABLE ALIGN="CENTER" CELLPADDING="0" WIDTH="100%">
<TR VALIGN="MIDDLE"><TD NOWRAP ALIGN="RIGHT"><IMG
WIDTH="232" HEIGHT="83" ALIGN="MIDDLE" BORDER="0"
SRC="img770.gif"
ALT="$\displaystyle C=\int_0^{+\infty} \frac{\hat{\psi}^*(\nu)\hat{\chi}(\nu)}{\nu}d\nu$"></TD>
<TD> </TD>
<TD> </TD>
<TD WIDTH=10 ALIGN="RIGHT">
(14.69)</TD></TR>
</TABLE></DIV>
<BR CLEAR="ALL"><P></P>
is defined.
<I>W</I><SUB><I>g</I></SUB>(<I>a</I>,<I>b</I>) denotes the wavelet transform of <I>g</I> with the wavelet
function <IMG
WIDTH="50" HEIGHT="44" ALIGN="MIDDLE" BORDER="0"
SRC="img771.gif"
ALT="$\psi(x)$">:
<BR>
<DIV ALIGN="CENTER">
<!-- MATH: \begin{eqnarray}
W_g(a,b)=\frac{1}{\sqrt a}\int_{-\infty}^{+\infty}g(x)\psi^*(\frac{x-b}{a})dx
\end{eqnarray} -->
<TABLE ALIGN="CENTER" CELLPADDING="0" WIDTH="100%">
<TR VALIGN="MIDDLE"><TD NOWRAP ALIGN="RIGHT"><IMG
WIDTH="365" HEIGHT="73" ALIGN="MIDDLE" BORDER="0"
SRC="img772.gif"
ALT="$\displaystyle W_g(a,b)=\frac{1}{\sqrt a}\int_{-\infty}^{+\infty}g(x)\psi^*(\frac{x-b}{a})dx$"></TD>
<TD> </TD>
<TD> </TD>
<TD WIDTH=10 ALIGN="RIGHT">
(14.70)</TD></TR>
</TABLE></DIV>
<BR CLEAR="ALL"><P></P>
We restore <I>g</I>(<I>x</I>) with the wavelet function <IMG
WIDTH="48" HEIGHT="44" ALIGN="MIDDLE" BORDER="0"
SRC="img773.gif"
ALT="$\chi(x)$">:
<BR>
<DIV ALIGN="CENTER">
<!-- MATH: \begin{eqnarray}
g(x)=\frac{1}{C}\int_0^{+\infty}\int_{-\infty}^{+\infty}\frac{1}{\sqrt a}
W_g(a,b)\chi(\frac{x-b}{a})\frac{dadb}{a^2}
\end{eqnarray} -->
<TABLE ALIGN="CENTER" CELLPADDING="0" WIDTH="100%">
<TR VALIGN="MIDDLE"><TD NOWRAP ALIGN="RIGHT"><IMG
WIDTH="455" HEIGHT="73" ALIGN="MIDDLE" BORDER="0"
SRC="img774.gif"
ALT="$\displaystyle g(x)=\frac{1}{C}\int_0^{+\infty}\int_{-\infty}^{+\infty}\frac{1}{\sqrt a}
W_g(a,b)\chi(\frac{x-b}{a})\frac{dadb}{a^2}$"></TD>
<TD> </TD>
<TD> </TD>
<TD WIDTH=10 ALIGN="RIGHT">
(14.71)</TD></TR>
</TABLE></DIV>
<BR CLEAR="ALL"><P></P>
The convolution product can be written as:
<BR>
<DIV ALIGN="CENTER">
<!-- MATH: \begin{eqnarray}
h(x)=\frac{1}{C}\int_0^{+\infty}\frac{da}{a^{\frac{5}{
2}}}\int_{-\infty}^{+\infty}
W_g(a,b)db\int_{-\infty}^{+\infty}f(u)\chi(\frac{x-u-b}{a}) du
\end{eqnarray} -->
<TABLE ALIGN="CENTER" CELLPADDING="0" WIDTH="100%">
<TR VALIGN="MIDDLE"><TD NOWRAP ALIGN="RIGHT"><IMG
WIDTH="591" HEIGHT="73" ALIGN="MIDDLE" BORDER="0"
SRC="img775.gif"
ALT="$\displaystyle h(x)=\frac{1}{C}\int_0^{+\infty}\frac{da}{a^{\frac{5}{
2}}}\int_{-\infty}^{+\infty}
W_g(a,b)db\int_{-\infty}^{+\infty}f(u)\chi(\frac{x-u-b}{a}) du$"></TD>
<TD> </TD>
<TD> </TD>
<TD WIDTH=10 ALIGN="RIGHT">
(14.72)</TD></TR>
</TABLE></DIV>
<BR CLEAR="ALL"><P></P>
Let us denote
<!-- MATH: $\tilde{\chi}(x)=\chi(-x)$ -->
<IMG
WIDTH="138" HEIGHT="44" ALIGN="MIDDLE" BORDER="0"
SRC="img776.gif"
ALT="$\tilde{\chi}(x)=\chi(-x)$">.
The wavelet transform <I>W</I><SUB><I>f</I></SUB>(<I>a</I>,<I>b</I>) of <I>f</I>(<I>x</I>) with
the wavelet
<!-- MATH: $\tilde{\chi}(x)$ -->
<IMG
WIDTH="48" HEIGHT="44" ALIGN="MIDDLE" BORDER="0"
SRC="img777.gif"
ALT="$\tilde{\chi}(x)$">
is:
<BR>
<DIV ALIGN="CENTER">
<!-- MATH: \begin{eqnarray}
\tilde W_f(a,b)=\frac{1}{\sqrt
a}\int_{-\infty}^{+\infty}f(x)\tilde{\chi}(\frac{x-b}{a})dx
\end{eqnarray} -->
<TABLE ALIGN="CENTER" CELLPADDING="0" WIDTH="100%">
<TR VALIGN="MIDDLE"><TD NOWRAP ALIGN="RIGHT"><IMG
WIDTH="357" HEIGHT="73" ALIGN="MIDDLE" BORDER="0"
SRC="img778.gif"
ALT="$\displaystyle \tilde W_f(a,b)=\frac{1}{\sqrt
a}\int_{-\infty}^{+\infty}f(x)\tilde{\chi}(\frac{x-b}{a})dx$"></TD>
<TD> </TD>
<TD> </TD>
<TD WIDTH=10 ALIGN="RIGHT">
(14.73)</TD></TR>
</TABLE></DIV>
<BR CLEAR="ALL"><P></P>
That leads to:
<BR>
<DIV ALIGN="CENTER">
<!-- MATH: \begin{eqnarray}
h(x)=\frac{1}{C}\int_0^{+\infty}\frac{da}{a^2}\int_{-\infty}^{+\infty}
\tilde W_f(a,x-b)W_g(a,b)db
\end{eqnarray} -->
<TABLE ALIGN="CENTER" CELLPADDING="0" WIDTH="100%">
<TR VALIGN="MIDDLE"><TD NOWRAP ALIGN="RIGHT"><IMG
WIDTH="459" HEIGHT="73" ALIGN="MIDDLE" BORDER="0"
SRC="img779.gif"
ALT="$\displaystyle h(x)=\frac{1}{C}\int_0^{+\infty}\frac{da}{a^2}\int_{-\infty}^{+\infty}
\tilde W_f(a,x-b)W_g(a,b)db$"></TD>
<TD> </TD>
<TD> </TD>
<TD WIDTH=10 ALIGN="RIGHT">
(14.74)</TD></TR>
</TABLE></DIV>
<BR CLEAR="ALL"><P></P>
Then we get the final result:
<BR>
<DIV ALIGN="CENTER">
<!-- MATH: \begin{eqnarray}
h(x)={1\over C}\int_0^{+\infty}\tilde W_f(a,x)\otimes W_g(a,x)\frac{da}{
a^2}
\end{eqnarray} -->
<TABLE ALIGN="CENTER" CELLPADDING="0" WIDTH="100%">
<TR VALIGN="MIDDLE"><TD NOWRAP ALIGN="RIGHT"><IMG
WIDTH="375" HEIGHT="73" ALIGN="MIDDLE" BORDER="0"
SRC="img780.gif"
ALT="$\displaystyle h(x)={1\over C}\int_0^{+\infty}\tilde W_f(a,x)\otimes W_g(a,x)\frac{da}{
a^2}$"></TD>
<TD> </TD>
<TD> </TD>
<TD WIDTH=10 ALIGN="RIGHT">
(14.75)</TD></TR>
</TABLE></DIV>
<BR CLEAR="ALL"><P></P>
In order to compute a convolution with the continuous wavelet
transform:
<UL>
<LI>We compute the wavelet transform
<!-- MATH: $\tilde W_f(a,b)$ -->
<IMG
WIDTH="84" HEIGHT="51" ALIGN="MIDDLE" BORDER="0"
SRC="img781.gif"
ALT="$\tilde W_f(a,b)$">
of the function <I>f</I>(<I>x</I>) with the
wavelet function
<!-- MATH: $\tilde{\chi}(x)$ -->
<IMG
WIDTH="49" HEIGHT="44" ALIGN="MIDDLE" BORDER="0"
SRC="img782.gif"
ALT="$\tilde{\chi}(x)$">;
<LI>We compute the wavelet transform <I>W</I><SUB><I>g</I></SUB>(<I>a</I>,<I>b</I>) of the function <I>g</I>(<I>x</I>) with the
wavelet function <IMG
WIDTH="50" HEIGHT="44" ALIGN="MIDDLE" BORDER="0"
SRC="img783.gif"
ALT="$\psi (x)$">;
<LI>We sum the convolution product of the wavelet transforms, scale by scale.
</UL>
<P>
The wavelet transform permits us to perform any linear filtering.
Its efficiency depends on the number of terms in the wavelet
transform associated with <I>g</I>(<I>x</I>) for a given signal <I>f</I>(<I>x</I>). If we
have a filter where the number of significant coefficients is
small for each scale, the complexity of the algorithm is
proportional to <I>N</I>. For a classical convolution, the complexity
is also proportional to <I>N</I>, but the number of operations is also
proportional to the length of the convolution mask. The main
advantage of the present technique lies in the possibility of having a
filter with long scale terms without computing the convolution on
a large window. If we achieve the convolution with the FFT
algorithm, the complexity is of order <IMG
WIDTH="90" HEIGHT="41" ALIGN="MIDDLE" BORDER="0"
SRC="img785.gif"
ALT="$N\log_2N$">.
The computing time is
longer than the one obtained with the wavelet transform if we
concentrate the energy on very few coefficients.
<P>
<HR>
<!--Navigation Panel-->
<A NAME="tex2html5556"
HREF="node330.html">
<IMG WIDTH="37" HEIGHT="24" ALIGN="BOTTOM" BORDER="0" ALT="next"
SRC="icons.gif/next_motif.gif"></A>
<A NAME="tex2html5553"
HREF="node328.html">
<IMG WIDTH="26" HEIGHT="24" ALIGN="BOTTOM" BORDER="0" ALT="up"
SRC="icons.gif/up_motif.gif"></A>
<A NAME="tex2html5547"
HREF="node328.html">
<IMG WIDTH="63" HEIGHT="24" ALIGN="BOTTOM" BORDER="0" ALT="previous"
SRC="icons.gif/previous_motif.gif"></A>
<A NAME="tex2html5555"
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="tex2html5557"
HREF="node330.html">The Wiener-like filtering in</A>
<B> Up:</B> <A NAME="tex2html5554"
HREF="node328.html">Noise reduction from the</A>
<B> Previous:</B> <A NAME="tex2html5548"
HREF="node328.html">Noise reduction from the</A>
<!--End of Navigation Panel-->
<ADDRESS>
<I>Petra Nass</I>
<BR><I>1999-06-15</I>
</ADDRESS>
</BODY>
</HTML>
