You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
71 lines
5.0 KiB
71 lines
5.0 KiB
|
|
\section{Introduction}
|
|
\label{sec:intro}
|
|
We start this paper by motivating the need for wavelets. As a starting point of signal processing we first consider the well known Fourier transform. As this section is mainly for the motivations we will not be very precise or give concrete algorithms.
|
|
|
|
\subsection{Recalling the Fourier transform}
|
|
Recall the Fourier transform (of length 128): given an input signal $x = \sum_{i=0}^{127} x_i e_i$ (represented on the standard basis $\{e_i\}_i$) we can compute Fourier coefficients $x'_i$ such that $x = \sum_{i=0}^{127} x'_i f_i$. As we're not interested in the mathematics behind this transform, we will not specify the basis $\{f_i\}_i$. Conceptually the Fourier transform is a basis transformation:
|
|
|
|
$$ SampleDomain \to FourierDomain. $$
|
|
|
|
Furthermore this transformation has an inverse. Real world applications of this transform often consists of going to the Fourier domain, applying some (easy to compute) function and go back to sample domain.
|
|
|
|
In figure~\ref{fig:fourier_concepts} an input signal of length $128$ is expressed on the standard basis, and on the Fourier basis (simplified, for illustrational purposes). We see that this signal is better expressed in the Fourier domain, as we only need three coefficients instead of all $128$.
|
|
|
|
\tikzstyle{plain_line}=[]
|
|
\begin{figure}
|
|
\begin{tabular}{c|c}
|
|
\begin{subfigure}[b]{0.5\textwidth}
|
|
\centering
|
|
\includegraphics[scale=0.8]{fourier_concept1}
|
|
\caption{Representing a signal on the standard basis.}
|
|
\end{subfigure}&
|
|
\begin{subfigure}[b]{0.5\textwidth}
|
|
\centering
|
|
\includegraphics[scale=0.8]{fourier_concept2}
|
|
\caption{Representing a signal on the Fourier basis.}
|
|
\end{subfigure}
|
|
\end{tabular}
|
|
\caption{We can represent the same signal on different basis. Note that the Fourier representation is smaller in this case.}
|
|
\label{fig:fourier_concepts}
|
|
\end{figure}
|
|
|
|
The figure also shows us that we might do compression based on these Fourier coefficients. Instead of storing all samples, we just store only a few coefficients from which we are able to approximate the original input. However there is a shortcoming to this. Consider the following scenario. A sensor far away detects a signal, transforms it and sends the Fourier coefficients to earth. During the transmission one of the coefficients is corrupted. This results in a wave across the whole signal. The error is \emph{non-local}. If, however, we decided to send the original samples, a corrupted sample would only affect a small part of the signal, i.e. the error is \emph{local}. This is illustrated in figure~\ref{fig:fourier_error}.
|
|
|
|
\tikzstyle{plain_line}=[]
|
|
\begin{figure}
|
|
\begin{tabular}{c|c}
|
|
\begin{subfigure}[b]{0.5\textwidth}
|
|
\centering
|
|
\includegraphics[scale=0.8]{fourier_error1}
|
|
\caption{The signal with $e_{10}$ added.}
|
|
\end{subfigure}&
|
|
\begin{subfigure}[b]{0.5\textwidth}
|
|
\centering
|
|
\includegraphics[scale=0.8]{fourier_error2}
|
|
\caption{The signal with $f_{10}$ added.}
|
|
\end{subfigure}
|
|
\end{tabular}
|
|
\caption{If one coefficient is corrupted the results depends on the representation. In the fourier basis shuch an error is visible across the signal, whereas it is local in the standard basis.}
|
|
\label{fig:fourier_error}
|
|
\end{figure}
|
|
|
|
|
|
\subsection{The simplest wavelet transform}
|
|
At the heart of the Fourier transform is the choice of the basis elements $f_i$. With a bit of creativity we can cook up different basis elements with different properties. To illustrate this we will have a quick look at the so-called \emph{Haar wavelets}. These wavelets also form a basis. Some of these basis elements are depicted in figure~\ref{fig:haarwvlt}. The other basis elements are made by narrowing the ones shown. In contrast to the Fourier basis elements, these wavelets are not smooth at all. If again we add $h_{10}$ to our signal, only a small portion is altered.
|
|
|
|
\begin{figure}
|
|
\centering
|
|
\begin{tikzpicture}
|
|
\begin{groupplot}[group style={group size=2 by 2}, clip=false, yticklabels={,,}, height=3cm, width=0.5\textwidth, xmin=0, xmax=128, ymin=-1.1, ymax=1.1, domain=0:128]
|
|
\nextgroupplot \addplot[plain_line] coordinates {(0,1) (128,1)}; \legend{$h_0$}
|
|
\nextgroupplot \addplot[plain_line] coordinates {(0,1) (64,1) (64,-1) (128,-1)}; \legend{$h_1$}
|
|
\nextgroupplot \addplot[plain_line] coordinates {(0,1) (32,1) (32,-1) (64,-1) (64,0) (128,0)}; \legend{$h_2$}
|
|
\nextgroupplot \addplot[plain_line] coordinates {(0,0) (64,0) (64,1) (96,1) (96,-1) (128,-1) (128,0)}; \legend{$h_3$}
|
|
\end{groupplot}
|
|
\end{tikzpicture}
|
|
\caption{Some of the Haar wavelets.}
|
|
\label{fig:haarwvlt}
|
|
\end{figure}
|
|
|
|
Another important difference is the way these basis elements can represent signals. With the Fourier basis elements we can easily approximate smooth signals, but with the Haar basis elements this is much harder. However representing a piecewise constant signal is almost trivial with the Haar wavelets. In photography the latter is preferred, as edges are very common (think of black branches of a tree against a clear sky). So depending on the application this \emph{non-smoothness} is either good or bad.
|
|
|