Image Compression Techniques with LZW method

Abstract

Image compression is a technique which is used to reduce the size of the data. In other words, it means to remove the extra data from the available by applying some techniques and tricks which makes the data easy for storing and transmitting it over the transmission medium. The compression techniques are broadly divided into two categories. First one is Lossy Compression in which some of the data is lost while compressing it and second technique is lossless technique in which data is not lost after compressing it. These compression techniques can be applied on different image formats. This review paper compares the different compression techniques.

Introduction

I. INTRODUCTION

Most of the Internet users are facing the problem of storing the huge amount of data. As the number of users of the Internet increases, the amount of data on the internet also increases day by day. To store and transmit the data, it requires more and more memory which leads to the problem of shortage of memory and traffic congestion on the internet. To tackle this problem, data compression may be provide some relief. As data compression techniques can reduce the size of the data.

In other words, Data compression is a technique which helps in reducing the size of data. These compression techniques can be applied on any kind of data. There are mainly five types of data. These are in the form of text, audio, video, animation and images. These compression techniques remove the redundant data present in the file. In other words, the compression is performed by removing the redundant bits in the file and hence decreases the size of the file. In this manuscript, we will deal with digital image and review the image compression techniques. The redundancy (duplicity) in the file is of three types:

1. Coding Redundancy: A normal image is having a length which is composed of pixels. To exemplify, if an image has 256 gray scale shades, it will be represented by a group of 8-Bit Integers. The coding redundancy can be removed by using arithmetic and Huffman coding compression techniques [3].
2. Psycho-visual Redundancy: It is impossible for humans to analyze the every luminance or pixel value in an image. So, some pixels known as unnecessary pixels can be removed from an image which does not affect the normal visual processing [3]. 
3. Inter-pixel Redundancy: There are some pixels in a video or an image which are known as adjoining pixels. These pixels are statistically depending upon each other and removing these pixels cannot affect the overall visual of an image [3].

The main aim of the compression techniques is to remove the above mention redundancies without losing the details present in an image. The general model for compressing an image is as shown in Figure 1 [4].

The above figure 1 shows the model for compressing and decompressing an image. The compression is performed at sender side and decompression is performed at receiver side.

At sender side, an image is taken and then passed through mapper where an input image is compressed and its interpixel redundancy is removed. After that it passed through quantizer where lossy compression is performed on it. Then an input image is encoded into a different format for its security.

At receiver side, the encoded image is firstly decoded into a required format. After that the image is dequantized by the dequantizier to get the details hide by the quantizer by performing quantization. At last, inverse mapper is used to get the required image.

II. DIGITAL IMAGE COMPRESSION TECHNIQUES

As discussed earlier, an image is compressed while transmitting it from sender to receiver. To compress an image, we have different types of compression techniques. Broadly, digital image compression techniques are divided into two categories.

1. Lossless Compression
2. Lossy Compression

The figure 2 shows the categorization of the compression techniques.

A. Lossless Compression

The first technique of digital image compression techniques is Lossless Compression. As its name suggest, in lossless compression, the output image is same as that of input image. In other words, the details of an input image do not loss while compressing and decompressing an image and output image after compression and decompression is exactly the copy of an input image. The losseless compression is further categorized into three categories.

1. Run Length Encoding (RLE): It is one of the easiest lossless compression techniques for compressing an image. In run length encoding, we count the numbers of same or identical characters and write the length of these characters along with the character instead of writing the same character again and again. This technique is used for gray scale images. For example, when we decode an image into bits sequence to transmit over the medium and we want to compress it using run length encoding. Suppose the bit sequence is like: 1110000011100000 and it can be compressed as 13051305 and this is transmitted over the transmission medium and decompressed at other end to get the original image. Hence, the data is not lost in this technique; it is categorized under lossless compression.
2. Huffman Coding: It is one of another compression technique of lossless technique. Dr. David A. Huffman is the founder of this technique and he founded it in 1952 [6]. In this compression technique, less bits are given to the symbols that are used more often and more bits are given to the symbols that are used less often. It is a compression technique which is based on statistical amount of probabilities [7].

For example, Huffman coding is explained in the following steps:   

a. Step 1: The sting is Input:

b. Step 2: The data is sorted on the basis of given frequencies:

c. Step 3: The least two counted frequencies are selected:

d. Step 4: The selected frequencies are added together and the table is updated:

e. Step 5: The step 2,3 and 4 are repeated and these steps are repeated until the final code is processed:

3. LZW Coding: It is the third type of lossless compression technique. LZW is an abbreviation of Lempel-Ziv-Welch. The name of the technique is proposed from the name of the three researchers. It was developed by the first two developers Abraham Lempel and Jacob Ziv in 1978 and improved by the third developer named Terry Welch in 1984. This technique is based on the dictionary coding. It is categorized as static and dynamic technique. When the dictionary is fixed, then it is a static dictionary coding. Similarly, when the dictionary is updated regularly, it is called as dynamic dictionary coding. This technique is used widely for GIF and UNIX formats [8]. It requires memory to store data in the form dictionary.

B. Lossy Compression

The second compression technique for the compression of an image is lossy compression.  In this technique, some data is lost during compression and decompression mechanism. On other words, the ouput image is not exactly same as that of input image. The lossy compression techniques are further of three types.

1. Transform Coding: The first type of lossy compression technique is the Transform Coding. In this technique, the spatial pixel of an image is converted into transform coefficients. The number of formed coefficients is same as that of pixels transformed.  Lapped orthogonal, Discrete Cosine Transformation (DCT), Walsh-Hadamard and Karhonen Loeve are the different types of transforms are done to transform picture into coding [9].
2. Vector Quantization: The second type of lossy compression is the Vector Quantization. It is based on scalar quantization.  In this technique, a fixed size called code vectors are generated. Firstly, an image is divided into different blocks known as image vectors. Then, the nearest matching vector is determined from the dictionary for each vector. At last, the index generated helps in encoding the original vector image [10].
3. Fractal Coding: The third type of lossy compression technique is Fractal Coding. In Fractal coding, an image is firstly divided into different segments with the help of common points like frequency, differences in color texture and edges of an image. In these segments, one part of the image is identical to other part of an image. In this, a lookup table acts as a dictionary for fractal segments. It contains the code library having set of suitable numbers. The fractals are used to compress the image and an image is finally encoded [11].

III. DIFFERENCE BETWEEN LOSSY AND LOSSLESS COMPRESSION

Conclusion

This paper evaluation the numerous strategies and algorithms used for compressing the statistics. The compression strategies are extensively categorized as lossy and lossless compression. The lossless compression method consists of the Run period Coding, LZW Compression method, Huffman Encoding and arithmetic Encoding set of rules. whereas lossy compression consists of transform Coding (Discrete Cosine remodel, Walsh-Hadamard and Karhonen Loeve), Fractal Coding and and so on. it is usually the difference between the compression techniques.

References

[1] Khalid A “Introduction to data compression” Third edition-2006. [2] G. Ramya and K. N. Abdul Kader Nihal, “ Study and Survey on Image Compression Techniques” Asian Journal of Computer Science and Technology ISSN: 2249-0701 Vol.8 No.S2, 2019, pp. 70-74 [3] Nadeem A , Salman K and Gufran S, “A novel Image Compression method” IEEE in Fourth international conference on communication systems and network technologies, 2014. [4] Raajndeep Kaur, Pooja, “A Review of Image Compression Techniques” International Journal of Computer Applications, May 2016. [5] Sonal Chawla, Meenakshi Beri, Ritu Mudgil, “Image Compression Techniques: A Review”, IJCSMC, Vol. 3, Issue. 8, August 2014, pg.291 – 296. [6] G. M. Padmaja, P. Nirupama, “Analysis of Various Image Compression Techniques” ARPN Journal of Science and Technology ISSN 2225-7217 vol. 2, no. 4, May 2012. [7] F.I. Khandwani and P.E. Ajmire, “A Survey of Lossless Image Compression Techniques”, International Journal of Electrical Electronics and Computer Science Engineering, Vol. 5, No.1,pp. 39-42, February 2018. [8] G. Vijayvargiya, D.S. Silakari and D. Pandey, “A Survey: Various Techniques of Image Compression”, International Journal of Computer Science and Information Security, Vol. 11, No. 10, October 2013. [9] A.B. Kaimal, S. Manimurugan and C. Devadass, “Image Compression Techniques: A Survey”, International Journal of Engineering Inventions, Vol. 2, No. 4, pp. 26-28, February 2013. [10] P.B. Pokle and N.G. Bawane, “Comparative Study of Various Image Compression Techniques”, International Journal of Scientific and Engineering Research, Vol. 4, No. 5, pp. 1902-1908, May 2013. [11] D.V. Rojatkar, N.D. Borkar, B.R. Naik and R.N. Peddiwar, “Image Compression Techniques: Lossy and Lossless”, International Journal of Engineering Research and General Science, Vol. 3, No. 2, pp. 912-917, April 2015. [12] A.R.M. Shanavas and M. Shameera, “Secured Lossless Medical Image Compression Based On Adaptive Binary Optimization”, IOSR Journal of Computer Engineering, Vol. 16, No. 2, pp. 43-47, April 2014. [13] Athira B. Kaimal, S. Manimurugan, C.S.C .Devadass, “Image Compression Techniques: A Survey” International Journal of Engineering Inventions e-ISSN: 2278-7461, p-ISBN: 2319- 6491 Volume 2, pp: 26-28 Issue 4 (February 2013). [14] M. Puttaraju, Dr. A. R. Aswatha,” FPGA Implementation of 5/3 Integer DWT for Image Compression”, (IJACSA) International Journal of Advanced Computer Science and Applications, Vol. 3, No. 10, 2012. [15] Asha Lata, Permender Singh, “Review of Image Compression Techniques” International Journal of Emerging Technology and Advanced Engineering (ISSN 2250-2459, ISO 9001:2008 Certified Journal, Volume 3, Issue 7, July 2013. [16] G. M. Padmaja, P. Nirupama, “Analysis of Various Image Compression Techniques” ARPN Journal of Science and Technology ISSN 2225-7217 vol. 2, no. 4, May 2012. [17] J.M. Shapiro, “Embedded image coding using zero tree of wavelet coefficients”, IEEE Trans. on Signal Processing, vol. 41, 3445-3462, 1993. [18] A. Said, W.A. Pearlman, “A new, fast, and efficient image codec based on set partitioning in hierarchical trees”, IEEE Trans. on Circuits and Systems for Video Technology, vol. 6, 243-250, 1996. [19] M. Shameera and A.R.M. Shanavas, “Analysis of Adaptive Binary Optimization for Lossless Medical Image Compression”, International Journal of Engineering Research and Technology, Vol. 3, No. 7, pp. 1221-1224, July 2014. [20] Rao, K. R., Yip, P., “Discrete Cosine Transforms - Algorithms, Advantages, Applications”, Academic Press, 1990.

Copyright

Copyright © 2022 Harjit Kaur, Shaweta Mahey, Nirmal Kaur. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.