\section{ Wavelet filters }

This section will desribe the filters used for image decomposition implemented
in \verb|wavelet_xform.c|. The current code allows arbitrary combinations of 
high- and lowpass filters.



\subsection{ Analyzing highpass filters }

The following table lists the highpass filters. Order is the number of vanishing
moments of the filter.


\begin{center}
\scriptsize
\begin{tabular}{cl}
\hline
order & filter \\
\hline
1 & $d_{i} = x_{2i+1} - x_{2i}$ \\
2 & $d_{i} = x_{2i+1} - [x_{2i} + x_{2i+2}] / 2$ \\
4 & $d_{i} = x_{2i+1} - [9 (x_{2i} + x_{2i+2}) - (x_{2i-2} + x_{2i+4})] / 16$ \\
6 & $d_{i} = x_{2i+1} - [150 (x_{2i} + x_{2i+2}) - 25 (x_{2i-2} + x_{2i+4}) + 3 (x_{2i-4} + x_{2i+6})] / 256$ \\
\hline
\end{tabular}
\end{center}

The highpass filter with 6 vanishing moments is not yet implemented. I'm not
sure if this would make sense, it's wide support will probably cause ringing
and could make the transform slow.

All highpass filters are expanding because of differencing (8 bit input force
\mbox{9 bit} output). To avoid overflows we have to use 16bit-Integers when 
transforming 8bit images.



\subsection{ Synthesizing Lowpass filters }


\begin{center}
\scriptsize
\begin{tabular}{cl}
\hline
order & filter \\
\hline
1 & $s_{i} = x_{2i} + d_{i} / 2$ \\
2 & $s_{i} = x_{2i} + [d_{i-1} + d_{i}] / 4$ \\
4 & $s_{i} = x_{2i} + [9 (d_{i-1} + d_{i}) - (d_{i-2} + d_{i+1})] / 32$ \\
\hline
\end{tabular}
\end{center}

Lowpass filtering is an averaging operation and preserves the number of 
required bits to represent the coefficients.



\subsection{ Applying the Transform to a row of data }

Here you see how handling of no-power-of-two-sizes is done at the example of the
(1,1) wavelet.
We use a mirrored low-order filter at the right boundary when $n$ is odd:


\begin{center}
\begin{tabular}{lrlll}
\hline
$n$ is even: & $d_{i}$ & $=$ & $x_{2i+1} - x_{2i}$     & for $0 \le i < n/2$ \\
             & $s_{i}$ & $=$ & $x_{2i} + d_{i} / 2$    & for $0 \le i < n/2$ \\
\hline
$n$ is odd:  & $d_{i}$ & $=$ & $x_{2i+1} - x_{2i}$     & for $0 \le i < n/2$ \\
             & $s_{i}$ & $=$ & $x_{2i} + d_{i} / 2$    & for $0 \le i < n/2$ \\
             & $s_{i}$ & $=$ & $x_{2i} - d_{i} / 2$    & for $i = n/2$       \\
\hline
\end{tabular}
\end{center}


Now we have a lowpass filtered image on the left and the highpass coefficients
on the right side of the row. This Filter is applied again to the lowpass image 
on the left ($n$ is now $(n+1)/2$) until $n$ becomes $1$. 



\subsection{ The inverse Transform }

To reconstruct the original data we can simply reverse all operations and apply
them in reversed direction:

\begin{center}
\begin{tabular}{lrlll}
\hline
$n$ is even: & $x_{2i}$ & $=$ & $s_{i} - d_{i} / 2$    &  for $0 \le i < n/2$ \\
             & $x_{2i+1}$ & $=$ & $d_{i} + x_{2i}$     &  for $0 \le i < n/2$ \\
\hline
$n$ is odd: & $x_{2i}$ & $=$ & $s_{i} - d_{i} / 2$    &  for $0 \le i < n/2$ \\
            & $x_{2i}$ & $=$ & $s_{i} + d_{i} / 2$    &  for $i = n/2$       \\
            & $x_{2i+1}$ & $=$ & $d_{i} + x_{2i}$     &  for $0 \le i < n/2$ \\
\hline
\end{tabular}
\end{center}


\subsection{ Higher Order Filters }

The smooth high-order filter kernels have a wider support and need some special
handling at boundaries. Here we simply insert low-order wavelets. Below the
example of the Highpass with 2 vanishing moments:

\begin{center}
\begin{tabular}{lrlll}
\hline
$n$ is even: & $d_{i}$ & $=$ & $x_{2i+1} - [x_{2i} + x_{2i+2}] / 2$ 
                                                       & for $0 \le i < n/2-1$ \\
             & $d_{i}$ & $=$ & $x_{2i+1} - x_{2i}$     & for $i = n/2-1$       \\
\hline
\end{tabular}
\end{center}