Haar Transform

The one-dimensional Haar transform is contructed by taking two numbers, a and b and mapping them to a lowpass value sqrt(2)*a/2 + sqrt(2)*b/2 and a highpass value sqrt(2)*b/2 -sqrt(2)*a/2. For image compression, we mulitplied this transform by sqrt(2) so that it mapped the integers to integers. The modified transform is

| a | | a + b |
| b | -> | b - a |

The output of this transform is certainly integer valued if a and b are integers. To invert the process, we simply divide the inverse transform by sqrt(2).

The problem with this transform is that it increases the dynamic range of the lowpass portion of the data. That is, for a,b, integers from {0,...,255}, the lowpass value could range from 0 to 510. It is desirable to keep the range of lowpass values the same as that of the original input. Thus it is suggested to use a modified Haar wavelet transform

(6.32)
| a | | (a + b)/2 |
| b | -> | b - a |

Certainly, the average of a and b is contained in [a,b], but the problem is that the lowpass values of this transform are not necessarily integer valued.

In this problem, we see how to compute the transform (6.32) via a process known as lifting and then convert the results to integers in such a way that the original input can be recovered. Throughout this problem, we assume that v=[v_1,...,v_N]^T where N is even with v_k in {0,...,255},k=1,...N.

(a) The transform (6.32) sends

v-> [ (v_1+v_2)/2,...,(v_N-1+v_N)/2 | v_2 -v_1,...,v_N - v_N-1]^T

If we let s and D denote the lowpass and highpass portions of the transform, respectively, then for k = 1,...,N/2,

s_k=(v_{2k-1} + v_{2k})/2 and d_k = v_{2k} - v_{2k-1}

Let e = (e_1,...,e_N/2)^T = (v2,v4,...,v_N)^T hold the even-indexed elements of v, and let o (o_1,...,o_N/2)^T = (v_1,v_3,...,v_N-1)^T hold the odd-indexed elements of v. Show that we can obtain D and s by first compting

d_k = e_k - o_k

for k = 1,...,N/2, and then computing

s_k= o_k + 1/2 d_k

for k = 1,...,N/2.


I need to write a module for this in Mathematica 7.0 or MATLAB, can anyone give me suggestions on where to start?