Image Compression Using DWT and Vector
Quantization

Tejas S. Patel; Ravindra Modi; Keyur J. Patel

Image Compression Using DWT and Vector Quantization

Tejas S. Patel¹, Ravindra Modi², Keyur J. Patel³

Master of Technology, Dept. of Information Technology, U V Patel College of Engineering, Kherva, Gujarat, India
Assistant Professor, Dept. of Information Technology, U V Patel College of Engineering, Kherva, Gujarat, India
Master of Technology, Dept. of Information Technology, U V Patel College of Engineering, Kherva, Gujarat, India

Related article at Pubmed, Scholar Google

Visit for more related articles at International Journal of Innovative Research in Computer and Communication Engineering

Abstract

Ideally, an image compression technique removes redundant and/or irrelevant information, and efficiently encodes what remains. Image compression is most important for efficient transmission and storage space of images. Image compression plays a most powerful role in digital image processing. In this paper, DWT and Vector quantization technique are simulated. Using different codebook size, we apply DWT-VQ technique and Extended DWT-VQ (Which is the modification algorithm) on various kinds of images. The results of simulation are shown and compared different quality parameter of it’s by applying on various images.

Keywords

DWT, Vector quantization, Image processing.

INTRODUCTION

In recent year, many numbers of applications need large number of images for solving our problem. Digital image can be store on disk and this storing space of image is also important [4]. Because less memory space means less time of required to processing for image. The concept of image compression “Image compression means reduced the amount of data required to represent a digital image” [4].A method and system for transmitting a digital image (i.e., an array of pixels) from a digital data source to a digital data receiver. More the size of the data be smaller, it provides better transmission speed and saves time [3]. There are many application where the image compression is effectively increased efficiency and performance like Health Industries, retail stores, federal Government Agencies, security industries, museums and galleries etc[2],[6].

II. BACKGROUND STUDY

A. DWT

Wavelet [4],[2],[5] analysis can be used divided the information of an image into approximation and detailed subsignal. The approximation sub-signal shows the general trend of pixel value, and three detailed sub-signal show vertical, horizontal and diagonal details or changes in image. If these detail is very small than they can be set to zero without significantly changing the image. If the number of zeroes is greater than the compression ratio is also greater. There is two types of wavelet is used. First one is Continues Wavelet Transform [4] and second one is Discrete Wavelet Transform [4]. Wavelet analysis is computed by filter bank. There is two type of filter

1) High pass filter [4]: high frequency information is kept, low frequency information is lost.

2) Low pass filter [4]: law frequency information is kept, high frequency information is lost.

So signal is effectively decomposed into two parts, a detailed part (high frequency) and approximation part (law frequency).

Level 1 detail is horizontal detail, level2 detail is vertical detail and level 3 detail is diagonal detail of the image signal.

B. Vector Quantization

Vector quantization [9] is a lossy type image compressing technique because in VQ technique some information may be loss due to quantization. First image is divided into fixed size block called training set and also create a codebook which has indexed image block of the same size of representing types of image block. Then it prepares a string for image by finding corresponding block index and arranging them.

In fig there are shown one image with its block and its codebook. There are also shown corresponding block index from codebook or closest match block index.

Instead of transmitting pixel value we simple transmit codebook and encoded string “0 0 1 0 2 2 2 0 3 2 2 0 0 4 0 0” so at the decoded side we can reconstruct original image by using this encoded string and codebook by putting the corresponding block from codebook.

1). Algorithm for codebook design

Important part of vector quantization is designing the codebook. There are many algorithms are available for designing the codebook. One of the most used algorithm is LBG.

In my implementation for designing m size codebook of 4x4 vectors I have use simple algorithm whose steps are described below.

1. MxN size Image is partition into 4x4 blocks. These blocks are arranged into a vector this vector is called training set.

2. Initially in codebook there take two vector one of contains whole zeros and one contains 255

3. Now find the mean of training set and we get one 16 elements vector. This vector is added into codebook.

4. Now training set is divided into two training set. By using Euclidian distance from initial vector. Here is vector which contains all zeros elements.

5. Now for this two training set again find mean of its. And we find two vectors. These two vectors are added into codebook.

6. Now this two training set are split into four training set. And this finding mean and splitting process done until we find m vector.

III. PROPOSED METHOD

C. Hybrid System DWT-VQ For Image Compression

In fig.3 there is shown hybrid model of DWT-VQ techniques for Image Compression. The steps of this compression shown below

Steps:

1). Apply the DWT transform and got the four bands LL, LH, HL, HH of original image.

2).Partition the LH, HL, HH bands into 4x4 block then apply Vector Quantization on each block and result is the compressed image.

This system got high compression ratio without loss of much information because applying DWT transform we minimize the domain of codebook vector. This will helpful in achieving high compression ratio without loss of information. This is basic system; there are more models with the change of step. We can apply DWT more than 2 level and apply different vector quantization technique. I have made the little change in this system. Before applying Vector Quantization I have added one pre-process step this extended model is shown in next chapter

D. Extended Hybrid System DWT-VQ for Image Compression

Steps:

1. Apply the DWT transform on the original image and got four bands of original image LL, LH, HL, HH.

2. Then apply the preprocess step as below.

a. First partition the LH, HL, HH bands into the 4x4 block.

b. Compute the mean of each block.

c. Subtract the mean of block from each elements of that block and result is difference matrix.

3. Now apply the Vector Quantization on this difference matrix. With codebook there is also pass mean of each block to decoder side.

This preprocess step is also decrease the information loss without affecting the much compression ratio. Because after subtracting mean we got highly correlated data which means we do better quantization using vector quantization. This computation of difference matrix is discussed in paper result is shown less MSE than ordinary Vector Quantization technique.

IV. SIMULATION AND RESULTS

E. Hybrid System DWT-VQ for Image Compression

Hybrid system of DWT-VQ is applying on image and result is shown in below fig.

MSE of Compressed image with original image is shown above table. From that we conclude it will affect minor level data. Loss of data is very small. In below figure, compressed images of hybrid DWT-VQ system using different codebook size have shown.

The quality of reconstructed image depends upon the size of code book. If the codebook size is increased, we see (Table II) that the compression ratio (which is the ratio of the uncompressed size to the compressed size) decreases because the number of bits that represent the block is increased and MSE decrease.

By using hybrid DWT-VQ technique we can achieve 3.5 to 9.45 Compression ratio and loss of information is quite negligible. Though we can decrease MSE by applying our modification. We can decrease MSE in this method if we increased the correlation of pixels of image this what done by computing differential matrix. But this will decrease a little compression ratio.

F. Extended Hybrid System DWT-VQ for Image Compression

Now step of computing differential matrix before applying vector quantization is applied to out three images and output of compressed image is shown below. We can see that it is identical to original image. There is no any artifact in compressed image.

Loss of information is very low in this technique we can see that in below table. In compare to existing hybrid DWTVQ technique MSE is less. So it improves the quality of compressed image.

In table III, MSE of compressed image shown that there is less information loss with compared to total information and also less with compared to existing hybrid DWT-VQ compression technique.

We can apply this Extended Hybrid DWT-VQ technique by using different codebook size.

MSE and compression ratio of compressed image is shown table IV. Compression ratio is quite good if we consider the benefits of no losing information this what we exactly want to do “Compression without loss of information”. This compression is low if we compare with existing Hybrid DWT-VQ system but our modification step reduced loss of information.

MSE comparison of extended hybrid DWT-VQ system and hybrid DWT-VQ is shown in Fig.10’s graph. We can see that MSE is less in extended hybrid DWT-VQ System.

Compression ratio comparison of extended hybrid DWT-VQ system and hybrid DWT-VQ is shown in above graph. We can see that Compression ratio is less in Extended Hybrid DWT-VQ System. Difference is about 0.75. This difference is quite negligible if we consider the minimum information loss.

Comparison of extended hybrid DWT-VQ system with existing compression technique

V. CONCLUSION

Today is the most famous technique for compression is JPEG. JPEG achieve compression ratio from 2.4 up to 144. If we want high quality then JPEG provides 2.4 compression ratio and if we can compromises with quality then it will provide 144.our proposed system provides 2.97 to 6.11 compression ratio with high quality in sense of information loss. Though if we consider time as cost then our proposed system required more time because counting differential matrix is time consuming, but this defect can be removed if we provide efficient hardware component for our proposed system.

References

Abhishek Kaushik, Maneesha Gupta,“Analysis of Image Compression Algorithms”,International Journal of Engineering Research and Applications,march-april 2012.
Anilkumar Katharotiya, Swati J. Patel Mahesh Goyani,“Comparative Analysis between DCT &DWT Techniques of Image Compression”,Journal of Information Engineering and Applications,Vol 1, No.2, 2011.
Md. Rubaiyat Hasan, “Data Compression using Huffman based LZW Encoding Technique”,International Journal of Scientific & Engineering Research, Volume 2, Issue 11, 1 ISSN 2229-5518 IJSER, November 2011.
Rafael C. Gonzalez, Richard E. Woods, “Digital Image Processing (2nd edition)”, NJ:Prentice Hall 1992.
Karen Lees, “Image compression using Wavelets", Report of M.S. 2002.
Gonzalez, R.C. and Woods, R.E, “Digital Image Processing using MATLAB”, Pearson Education, India,2006.
LockerGnome, “Real World Application of Image Compression”, 2011.
Bhavna Gautam,“A Thesis on Image Compression using Discrete Cosine Transform and Discrete Wavelet Transform”,National Institute of Rourkela.
Paul Shelley, Xiaobo Li, Bin Han,“A hybrid quantization scheme for image compression”,University of Alberta,2003.
Martha R. Quispe-Ayala, Krista Asalde-Alvarez, Avid Roman-Gonzalez, “Image Classification Using Data Compression Techniques”,Author manuscript, published in 2010 IEEE 26th Convention of Electrical and Electronics Engineers in Israel - IEEEI 2010, Israel 2010.
Nopparat Pantaesaena, M.Sangworaisl, C. Nantajiwakornchai and T. Phanpraist, “Image compression using vector quantization”, ReCCIT, Thialand,2005.