Digital Signal Processing - Part 3/6
Check it out here: Github
In this blog we shall cover the Haar wavelet transform on an image using python. To understand the Haar basis for the image transformation we will first look at the theory behind it and then write a python program that allows us to transform an image. We will use the iconic Cameraman image for the same.
We consider a set of real valued matrices of size M x N, we can turn this into a vector space by defining addition and scalar multiplication in the usual way,
As a matter of fact, the space of a real valued M x N Matrix is equivalent to:
and we can always "unroll" the matrix into a vector. Assume we move by column to column; then the matrix becomes:
Although the matrix and vector forms represent the same data, the matrix form allows us to display the data in the form of an image. Assume each value in the matrix is a grayscale intensity, where zero is black and 255 is white; for example, we can create a checkerboard pattern of any size with the following image:
Given the equivalence between the space of M x N, Matrices and R^MN, we can easily define the inner product fo the two matrices in the usual way:
(where we have neglected the conjugation since we will only deal with real-valued matrices); in other words, we can take the inner product between two matrices as the standard inner product of their unrolled versions. The inner product allows us to define orthogonality between images and this is rather useful since we are going to explore a couple of bases for this space.
Haar basis was developed by Alfred Haar in 1909. It is the simplest and the most widely adopted wavelet basis. Let us start with a 1D signal.
The function in the right-hand side can be expressed as:
Phi(x) and Psi(x) are called mother scale function and mother wavelet function respectively. Other basis functions could be derived by scaling and translation of these functions.
For a 1-D discrete signal with length N (N>2), we can repeat this average & difference process to obtain 1 scale coefficient and N-1 detail coefficients.
The following is an example of transforming a 1-D discrete signal [9 7 3 5]
Thus, the wavelet transforms of [9 7 3 5] is given by [6 2 1 -1]
Less significant detail coefficients could be discarded for data compression purposes, like the image shows. To do a 2D Haar transform we can simply do a 1D transform twice for each axis.
1. We load an image onto the notebook. For this, we are going to use the cameraman image with image. This is one of the most famous testing images and is a low-resolution version of the original image.
2. To find out the number of grey levels we can simply check the first row of the image and its values.
3. We find that integers are between zero and 255 this means that encoding is over 8 bits since:
4. This means we have 256 Gray levels.
5. The canonical basis for any matrix space R^MN is the set of "delta" matrices where only one element equals to one while all the others are 0. Let us call them En with 0 ≤ n ≤ MN. Here is a function to create the canonical basis vector given its index:
6. Here are some basis vectors: look for the position of white pixel, which differentiates them and note that we enumerate pixels column-wise.
7. Transmitting an image can either be done pixel wise with separated values, but then we need to realise, that even a image with , coefficients in a row with take a lot of time.
8. And if due to some transmission failure we are only able to see a part of the image since the other part will have to be replaced by zeros, we would see:
9. For this reason, we use the Haar basis. This is a new basis for the image space. We can use Haar basis for transmission since it also compresses the amount of data to be transmitted.
Check out the code here