Multidimensional Haar transforms

This post summarizes how to compute the multidimensional Haar transform both in normal and separable way.

NOTE: A print-friendly (and more complete) version of this post can be found here.

Haar functions

The Haar functions are the simplest possible wavelets. The 1D mother wavelet function $\psi(t)$ can be described as:

$\begin{equation*} \psi_1(t) = \begin{cases} 1, & \text{for } 0 \leq t \ < \frac{1}{2} \\ -1, & \text{for } \frac{1}{2} \leq t < 1 \\ 0, & \text{otherwise.} \end{cases} \end{equation*}$

The corresponding scaling function $\phi(t)$ is described as:

$\begin{equation*} \phi_1(t) = \begin{cases} 1, & \text{for } 0 \leq t < 1\\ 0, & \text{otherwise}. \end{cases} \end{equation*}$

2D Haar functions can be constructed using tensor products as follows:

$\begin{equation*} 2D = \begin{cases} {\psi}_2^1 = \psi_1 \otimes \phi_1 \\ {\psi}_2^2 = \phi_1 \otimes \psi_1 \\ {\psi}_2^3 = \psi_1 \otimes \psi_1 \\ {\phi}_2 = \phi_1 \otimes \phi_1.\\ \end{cases} \end{equation*}$

In the same way, 3D filters are:

$\begin{equation*} 3D = \begin{cases} {\psi}_3^1 = \psi_2^1 \otimes \psi_1 \\ {\psi}_3^2 = \phi_2^2 \otimes \psi_1 \\ {\psi}_3^3 = \psi_2^3 \otimes \psi_1 \\ {\psi}_3^4 = \psi_2^4 \otimes \psi_1 \\ {\psi}_3^5 = \psi_2^1 \otimes \phi_1 \\ {\psi}_3^6 = \phi_2^2 \otimes \phi_1 \\ {\psi}_3^7 = \psi_2^3 \otimes \phi_1 \\ {\phi}_3 = \phi_2 \otimes \phi_1. \end{cases} \end{equation*}$

The number of functions needed depends of the number of dimensions as $2^d$ , where $d$ are the dimensions. So there are two filters for 1D ( $2^1$ ), four filters for 2D ( $2^2$ ), eight filters for 3D ( $2^3$ ) and so on.

For the 4D case the filters are:

$\begin{equation*} 4D = \begin{cases} {\psi}_4^1 = \psi_3^1 \otimes \psi_1 \\ \ldots \\ {\psi}_4^{15} = \psi_3^7 \otimes \phi_1 \\ {\phi}_4 = \phi_3 \otimes \phi_1. \end{cases} \end{equation*}$

This can be generalised to any number of dimensions.

Haar transform

The Haar transform is the simplest of the wavelet transforms. This transform is computed by convolving the signal to be transformed with all necessary Haar functions and by subsampling accordingly afterwords.

The single-level 1D transform $\hat{x}$ is described by the following two 1D-convolutions:

$\begin{equation*} \hat{x}(k_1) = \begin{cases} \displaystyle\sum_{u_1 = -\infty}^{\infty}{\psi_1(u_1)x(k_1 - u_1)}\\ \displaystyle\sum_{u_1 = -\infty}^{\infty}{\phi_1(u_1)x(k_1 - u_1)}\\ \end{cases} \end{equation*}$

and by analogy the 2D traansform is given by the following four 2D-convolutions:

$\begin{equation*} \hat{x}(k_1, k_2) = \begin{cases} \displaystyle\sum_{u_1 = -\infty}^{\infty}\sum_{u_2 = -\infty}^{\infty}{\psi_2^1(u_1, u_2)x(k_1 - u_1, k_2 - u_2)}\\ \displaystyle\sum_{u_1 = -\infty}^{\infty}\sum_{u_2 = -\infty}^{\infty}{\psi_2^2(u_1, u_2)x(k_1 - u_1, k_2 - u_2)}\\ \displaystyle\sum_{u_1 = -\infty}^{\infty}\sum_{u_2 = -\infty}^{\infty}{\psi_2^3(u_1, u_2)x(k_1 - u_1, k_2 - u_2)}\\ \displaystyle\sum_{u_1 = -\infty}^{\infty}\sum_{u_2 = -\infty}^{\infty}{\phi_2(u_1, u_2)x(k_1 - u_1, k_2 - u_2)}. \end{cases} \end{equation*}$

In previous equations the interval of $u$ variables is infinite; in practice however, convolutions are usually computed for finite intervals.
Generalizing to $d$ dimensions, then we will have $\hat{x}$ computed by $2^d$ $d$ -dimensional convolutions:

$\begin{equation*} \hat{x}(k_1, \ldots, k_d) = \begin{cases} \displaystyle\sum_{u_1 = -\infty}^{\infty}\ldots\sum_{u_d= -\infty}^{\infty}{\psi_d^1(u_1, \ldots, u_d)x(k_1 - u_1, \ldots, k_d - u_d)}\\ \ldots \\ \displaystyle\sum_{u_1 = -\infty}^{\infty}\ldots \sum_{u_d = -\infty}^{\infty}{\psi_d^{2^d -1}(u_1, \ldots, u_d)x(k_1 - u_1, \ldots, k_d - u_d)}\\ \displaystyle\sum_{u_1 = -\infty}^{\infty}\ldots \sum_{u_d = -\infty}^{\infty}{\phi_d(u_1,\ldots, u_d)x(k_1 - u_1,\ldots, k_d - u_d)}. \end{cases} \end{equation*}$

Separable convolutions

Computing multidimensional convolutions can be complicated or too impractical sometimes. For this reason, in some specific cases, a multidimensional convolution can be computed as one-dimensional convolution along all dimensions. The necessary condition to have convolution computed this way is that at least one of the signals being convolved must be separable.
A signal is said to be {separable} if it can be written as product of one-dimensional signals:

$\begin{equation*} x(u_1, \ldots, u_d) = f_1(u_1) f_2(u_2)\ldots f_d(u_d) = \prod_{d=1}^{D}f_d(u_d). \end{equation*}$

In this case we can compute the so-called row-column convolution, described below.

Given a 2D-signals $x$ and the 2D Haar functions as described above, than a separable convolution for the 2D Haar transform is described as:

$\begin{eqnarray*} \hat{x}(k_1, k_2) =& \displaystyle\sum_{u_1 = -\infty}^{\infty}\displaystyle\sum_{u_2= -\infty}^{\infty}{\psi_2^p(u_1, u_2)x(k_1 - u_1, k_2 - u_2)}\\ &= \displaystyle\sum_{u_1 = -\infty}^{\infty}\displaystyle\sum_{u_2= -\infty}^{\infty}{\psi_2^{(p,1)}(u_1)\psi_2^{(p,2)}(u_2)x(k_1 - u_1, k_2 - u_2) }\\ &= \displaystyle\sum_{u_1 = -\infty}^{\infty}{\psi_2^{(p,1)}(u_1) \left[\displaystyle\sum_{u_2 = -\infty}^{\infty}\psi_2^{(p,2)}(u_2)x(k_1 - u_1, k_2 - u_2) \right]} \end{eqnarray*}$

for any filter $p$ of the 2D Haar functions.

The muldidimensional Haar transform can be computed as sequences of 1D Haar transform along all dimensions.

Author: CarmineCella

Carmine-Emanuele Cella is a weekend-pilot; he wanted to be a mathematician but he ended up in writing music that nobody understands. Freud would say about him that he received too much love during his infancy but his psychologist just says that he should accept himself as he is. He loves life and he teaches at the University of California, Berkeley. View all posts by CarmineCella

Author: CarmineCella

Leave a Reply Cancel reply