| In
this article, I will present an introduction to “wavelets”
and the 1D Haar Transform. Then I will show how the 1D Haar
Transform can easily be extended to 2D. This article assumes
that the reader has general knowledge about basis functions.
If not, please look at my introductory article on basis
functions before reading this one. |
What are
Wavelets?
Wavelets are a
set of non-linear bases. When projecting (or approximating) a
function in terms of wavelets, the wavelet basis functions are
chosen according to the function being approximated. Hence, unlike
families of linear bases where the same, static set of
basis functions are used for every input function, wavelets
employ a dynamic set of basis functions that represents the
input function in the most efficient way. Thus wavelets are able to
provide a great deal of compression and are therefore very popular
in the fields of image and signal processing.
Let’s get in to
the details of how this dynamic set of basis functions is chosen and
how the input function is transformed into wavelets.
Lets suppose that
we have a string of numbers: ( 2, 2, 2, 2 ) and we want to transmit
this over a network. Of course, we would like to do this in the
fastest possible way, which implies that we want to send the least
amount of data possible. So let’s consider our options. Trivially,
one of our options is to just send all the four numbers, i.e., send
the first '2', then the second '2', then the third, and lastly the
fourth. In doing so, we are implicitly choosing the following basis:
|
<1, 0, 0, 0>
<0, 1, 0, 0>
<0, 0, 1, 0>
<0, 0, 0, 1> |
But as you would suspect, this is not
the best way of doing things. Can we do better? The trick is to
choose a basis that represents our data efficiently and in a very
compact fashion. Notice that our data is pretty uniform; in fact it
is just a constant signal of 2. We would like to exploit this
uniformity. If we choose the basis vector <1, 1, 1, 1>, we can
represent our data by just one number! We would only have to send
the number 2 over the network, and our entire data string could be
reconstructed by just multiplying (or weighting) with the basis
vector <1, 1, 1, 1>. This is great, but we still need three more
basis vectors to complete our basis since the space in our example
is 4 dimensional. Remember, that all basis vectors have to be
orthogonal (or perpendicular). This means that if you take the dot
(or scalar) product of any two basis vectors, the result should be
zero. So our task is to find a vector that is orthogonal to <1, 1,
1, 1>. One such vector is <1, 1, -1, -1>. If you take the dot
product of these two vectors, the result is indeed zero.
Graphically, these two vectors look like this:
 |
 |
|
<1,1,1,1> |
<1,1,-1,-1> |
Notice that graphically these basis vectors look like “waves”, hence the name
wavelets. Now that we have two basis vectors, we need two more. Haar
constructed the remaining basis vectors by a process of dilation
and shifting. Dilation basically means squeezing;
therefore the remaining basis vectors were constructed by squeezing
and shifting. If we squeeze the vector <1, 1, -1, -1>, we get <1,
-1, 0, 0>. The 1, 1 pair gets squeezed in to a single 1, and
similarly the -1, -1 pair becomes a single -1. Next, we perform a
shift on the resultant basis vector and get: <0, 0, 1, -1> which is
our final basis vector. Graphically, these two vectors look like
this:
 |
 |
|
<1,-1,0,0> |
<0,0,1,-1> |
We now have a complete basis for our four dimensional
space, comprised of the following basis vectors or wavelets.
|
<1, 1, 1, 1>
<1, 1, -1, -1>
<1, -1, 0, 0>
<0, 0, 1, -1> |
Take time to
convince yourself that all four of these vectors are
perpendicular to each other (take the dot product and see if it
is zero). Even though these basis vectors are orthogonal, they
are not orthonormal. However, we can easily normalize
them by calculating the magnitude of each of these vectors and
then dividing their components by that magnitude.
|
<1, 1, 1, 1> |
--> magnitude = sqrt((1)2 + (1)2
+ (1)2 + (1)2) = 2 |
--> <1/2, 1/2,
1/2, 1/2> |
|
<1, 1, -1, -1> |
--> magnitude
= sqrt((1)2 + (1)2 + (-1)2
+ (-1)2) = 2 |
--> <1/2, 1/2,
-1/2, -1/2> |
| <1, -1, 0, 0> |
--> magnitude
= sqrt((1)2 + (-1)2 + (0)2
+ (0)2) = √2 |
--> <1/√2,
-1/√2, 0, 0> |
| <0, 0, 1, -1> |
--> magnitude
= sqrt((0)2 + (0)2 + (1)2
+ (-1)2) = √2 |
--> <0, 0,
1/√2, -1/√2> |
|
Now that we
have our basis, let us look at an example of how we can project
an input vector in to wavelets. This is also known as the 1D
Haar Transform.
1D Haar Transform
Suppose our
input vector is: <4, 2, 5, 5>. To project this in to wavelets,
we simply take a dot product of the input vector with each of
the basis vectors.
|
dot ( <4, 2, 5, 5>
, <1/2, 1/2, 1/2, 1/2> ) = 8 |
| dot ( <4, 2,
5, 5> , <1/2, 1/2, -1/2, -1/2> ) = -2 |
| dot ( <4, 2,
5, 5> , <1/√2, -1/√2, 0, 0> ) = 2/√2 |
| dot ( <4, 2,
5, 5> , <0, 0, 1/√2, -1/√2> ) = 0 |
|
Thus the input vector got transformed in to <8,
-2, 2/√2,
0>. Notice the 4th component is 0! This means that we do not
need the 4th basis vector, we can reconstruct our
original input vector with just the first three basis vectors.
In other words, we dynamically chose 3 basis vectors from
a possible 4 according to our input.
|
8 * <1/2, 1/2,
1/2, 1/2> |
= <4, 4, 4, 4> |
|
-2 * <1/2, 1/2, -1/2, -1/2> |
= <-1, -1, 1,
1> |
|
2/√2 * <1/√2, -1/√2, 0, 0> |
= <1, -1, 0,
0> |
|
add the vectors |
= <4, 2, 5,
5> |
|
Until now, we had a 4 component input vector, and
a corresponding set of 4 component basis vectors. But what if we
have a larger input vector, say with 8 components? Would we need
to find the new basis vectors? The answer is no. We can use the
smaller basis that we already have. In fact, we can use the
simplest wavelet basis which consists of: <1/√2,
1/√2>
and <1/√2,
-1/√2>.
These are the smallest wavelets, notice you cannot squeeze them
any further. However in choosing these smaller basis vectors for
larger input, we can no longer do the Haar wavelet transform in
one pass as we did earlier. We will have to recursively
transform the input vector until we get to our final result. As
an example, let us use the simple, 2 component basis to
transform the 4 component input vector that we had in our
previous example. The algorithm is outlined below, and our
example is traced along side.
|
# |
|
Example |
|
|
Input Vector: |
<4,2,5,5> |
| |
Transformed Vector
(basis coefficients): |
<?,?,?,?>
(we are calculating this) |
| |
Basis Vectors
(wavelets): |
<1/√2,
1/√2>,
<1/√2,
-1/√2> |
|
1. |
If size of input
vector is less than size of basis vector, place
input in transformed vector and exit |
Size of input vector = 4
Size of basis vector = 2
4 > 2, so continue |
|
2. |
Break input vector
in to parts of size of the wavelet: |
<4,2> , <5,5> |
|
3. |
Take dot product
of first basis with every part: |
dot(<4,2> ,
<1/√2, 1/√2>)
= 6/√2
dot(<5,5> ,
<1/√2, 1/√2>)
= 10/√2 |
|
4. |
Take dot product
of second basis with every part: |
dot(<4,2> ,
<1/√2,
-1/√2>)
= 2/√2
dot(<5,5> ,
<1/√2,
-1/√2>)
= 0 |
|
|
Result of 3. is
the new Input Vector: |
<6/√2,
10/√2> |
|
|
Result of 4. fills part of the Transformed Vector: |
<
?, ?,
2/√2,
0> |
|
5. |
Go to 1. |
Size of input vector = 2
Size of basis vector = 2
2 = 2, so continue |
|
|
|
dot(<6/√2,
10/√2>
,
<1/√2, 1/√2>)
= 8 |
|
|
|
dot(<6/√2,
10/√2>
,
<1/√2,
-1/√2>)
= -2 |
|
|
Input Vector: |
<8> |
|
|
Updated
Transformed Vector: |
<
?, -2,
2/√2,
0> |
|
|
|
Size of input vector = 1
Size of basis vector = 2
1 < 2, so place input in transformed vector and
exit |
|
|
Transformed Vector
(final result): |
<8, -2,
2/√2,
0> |
|
This algorithm is
very simple. If you think about it, all it does is take the sums
and differences of every pair of numbers in the input vector and
divides them by square root of 2. Then, the process is repeated
on the resultant vector of the summed terms. Following is an
implementation of the 1D Haar Transform in C++
/* Inputs: vec = input vector, n = size of input vector
*/
void
haar1d(float
*vec,
int
n)
{
int i=0;
int
w=n;
float
*vecp = new
float[n];
for(i=0;i<n;i++)
vecp[i] =
0;
while(w>1)
{
w/=2;
for(i=0;i<w;i++)
{
vecp[i] = (vec[2*i]
+ vec[2*i+1])/sqrt(2.0);
vecp[i+w] = (vec[2*i]
- vec[2*i+1])/sqrt(2.0);
}
for(i=0;i<(w*2);i++)
vec[i] = vecp[i];
}
delete
[] vecp;
}
|
2D Haar Transform
The 1D Haar
Transform can be easily extended to 2D. In the 2D case, we
operate on an input matrix instead of an input vector. To
transform the input matrix, we first apply the 1D Haar transform
on each row. We take the resultant matrix, and then apply the 1D
Haar transform on each column. This gives us the final
transformed matrix. The source code for both the 1D and 2D Haar
transform can be downloaded here. The 2D
Haar transform is used extensively in image compression.
|