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 can be described as:
The corresponding scaling function is described as:
2D Haar functions can be constructed using tensor products as follows:
In the same way, 3D filters are:
The number of functions needed depends of the number of dimensions as , where
are the dimensions. So there are two filters for 1D (
), four filters for 2D (
), eight filters for 3D (
) and so on.
For the 4D case the filters are:
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 is described by the following two 1D-convolutions:
and by analogy the 2D traansform is given by the following four 2D-convolutions:
In previous equations the interval of variables is infinite; in practice however, convolutions are usually computed for finite intervals.
Generalizing to dimensions, then we will have
computed by
-dimensional convolutions:
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:
In this case we can compute the so-called row-column convolution, described below.
Given a 2D-signals

for any filter

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