Throughout this course we have become comfortable representing digital signals in the frequency domain using the Fourier Transform. With that, we were able to compress an image by filtering out all but the most important frequencies for each image color band (red, green, and blue). Wavelet analysis is a similar technique, but converts an image into a different basis for analysis.
While Fourier analysis isolates an image into the various frequencies present, wavelet transforms have the added benefit of localizing the transform in space as well. There are a large collection of different basis wavelets that can be used for this analysis, but in order to introduce the wavelet transform and the ideas behind it simply, the Haar basis was used to generate an image compression algorithm. The basic ideas of this transform have been detailed in 1D to present the concepts at a more intuitive level before applying it to the 2D image transform. The Haar basis in real space consists essentially of 2 basis vectors:
The first vector in this basis serves to represent the large details of an image, while the second vector is useful in representing edges and fast changing elements in any given vector. These two basis vectors can be shifted and scaled in any number of ways to collectively represent the signal. While these basis vectors can be used in any number of ways to represent a signal, it was specifically used to decompose a given vector X with length 2N as follows:
Each of the resulting vectors X and Y are length N, while the original signal was of length 2N. The result of this is to essentially split a given vector into 2 sub-bands, one representing the larger details of the signal (Y), and one representing the finer details (Z). These will be referred to as low and high pass decompositions respectively throughout the rest of this report. In order to obtain the original signal from the 2 sub-bands, the following can be used:
It can be clearly seen that this transform is computationally very cheap, since only a few additions and multiplications must be performed to split the vector into the low and high sub-bands, and addition and subtraction are used to reconstruct the even and odd elements of the original signal. This analysis can then be generalized to a 2 dimensional matrix by performing the transform on the columns and the rows of each image separately. The final result of this is to decompose an image into 4 separate matrices, each ¼ the size of the original. These separate matrices can be used to entirely reconstruct the original matrix by adding and subtracting across the columns and rows respectively. These 4 decompositions are referred to as high-high, high-low, low-high, and low-low, since the columns and rows are treated separately throughout the analysis. If both columns and rows are high-pass filtered, the resulting image is referred to as high-high, and if both are low-pass filtered it is referred to as low-low. An example of this decomposition is included below, with the low-low image in the top left and the high-high image in the bottom right. The resulting matrix can be generated for the red, green, and blue color matrices separately, but the analysis has been performed for the gray-scaled version of the image for simplicity below:
The resulting transformed image can be used to fully recover the original image by adding the high and low passed versions over the columns and rows respectively, similar to the 1D analysis performed above.
Image Compression 