Survey of Image Compression Method Lossless Approach

Survey of Image Compression Method Lossless Approach

Diya Chudasama#1, Khushboo Parmar#2, Dipali Patel#3, Kruti J. Dangarwala#4, Shaishav Shah#5

#Department of Information Technology Shri Sad Vidya Mandal Institute of Technology

Bharuch 392-001, Gujarat, India

AbstractImage Compression is useful technique through which we can reduce the storage space of images which will helpful to increase storage and transmission process with saving the channel bandwidth. There are number of algorithms available for lossy and lossless image compression. As lossy technique is not reversible so it is beneficial to use lossless technique to recover the original image. In this paper we analyze different types of existing method of lossless image compression. The methods which are discussed are Run Length Encoding, Huffman coding, Arithmetic, and LZW with its performance.

Keywords:Compression, Lossy, Lossless, Run Length Encoding,Huffman Coding, Arithmetic Coding, LZW.

1. INTRODUCTION

   The Prime need of Image Compression is to reduce the size the image for storage purpose [1]. Now a day it is common to compress the file image so that new changes can take place & to meet the criteria for certain limitation. This paper indicates about different technique used for image compression. Compression of binary raw data is expressively different than compression of image [2]. Image Compression also reduce the redundancy, extra information, & to transform data in efficient manner. Why the need of short data is more needed? The perfect reason for this is that it lower down the cost.

   Fig.1. Flow of Data Compression

   Data Compression has convincing application in field like distributed system. There are several ways to classified image compression technique. Among them one of important characteristics is that how much amount of data is reduced during compression which cannot recover during decompression Technique in which only some amount of data is removed is called lossy data compression. And technique in which we get data is same as actual data is known as lossless data compression. Lossless image compression are at prime importance in field of medical while for lossy it is useful in video compression. When for given information

   A1/A2 redundancy of data RD for same piece of data in multiple lines is represented as follow

   RD = 1 (1/LR) (1)

   Where R is compression ratio LR=A1/A2 [4].

   There are many technique for following compression which are as follows Run length Encoding, Arithmetic coding, Huffman, Dictionary Based, Sliding window Technique, etc[3]. Among this we have used four techniques Run Length Encoding, Huffman Coding, Arithmetic Coding, and LZW.

2. TYPES OF COMPRESSION

   In classification of Image compression method there are two types.

   Fig. 2. Types of Data Compression Techniques

   1. Lossless Compression Technique

      Lossless compression is a compression in which after decompression the image remains same as the actual image. Lossless data compression most probably exploits statistical redundancy to express data more precisely without any loss in information [11].As mentioned earlier lossless methods are preferred for medical imaging, technical drawing, satellite image etc. The following are some of the methods which are used for lossless compression.

      Fig. 3. Types of Lossless Compression

      It has many applications & useful in format like ZIP file & in grip of UNIX. Many file format like GIF, PNG uses only lossless compression for its image [7].There are many algorithms which are used in lossless image compression.

   2. Lossy Compression

   In lossy compression name itself states that there is loss of data in some manner. The decompressed image is not same as actual image [5]. Lossy compression has batter compression ratio over lossless techniques with some loss of data. It is not reversible. In order to check the image quality, it checks the Pixel color variation of in color values. The variation is so small that human eye cannot distinguish [6]. The most common example of lossy compression is JPEG and Wavelet Coding. Lossy compression is most commonly used to compress multimedia data like audio, video, and still images, especially in applications such as streaming media [15].

   Fig. 4. Types of Lossy Compression

3. COMPRESSION ALGORITHM

   1. Run Length Encoding

      One of the simplest form in compression technique is runlength encoding. The main concept for run length coding is this that it changes the known symbols which are known as runs. The change unknown symbol is replaced by single known and identical value [9].The files which uses the most runlength coding is TIFF, BMP, etc. It is a Lossless method and Useful in fax application in which most of the data is

      6 letters taken as a run having length 6, since symbol 1 is repeated consequently [10].

   2. Huffman Coding

      Huffman coding depends on the rule of probability distribution. To develop a code words pixel value of probability distribution is used. In first step frequency is calculated and then code is assigned to it. Symbol with more probability gets short code. At the end binary tree is created. The Huffman Coding is distinguished from the Shannon Fano method by its bottom-up approach [12]. For ex, for following sequence {p,q,r,s} the probability of sequence is

      {0.121,0.28,0.372,0.28}. Tree is created from left to right with two symbol of smaller probability. Summation of two numbers must be equivalent probability of third. The process carries on till it left to one [8]. The bits are numbered from right to left but priority is given to root and then to others [9].

   3. Arithmetic Coding

      Among all technique arithmetic coding is powerful technique for lossless statical encoding and gain much more attention in few years. In arithmetic coding instead of coding each image pixel(symbol) individually, entire image sequence is assigned single arithmetic code word [13] A code word from interval 0 to 1 (0,1] is defined. The output from an arithmetic coding process is a single number less than 1 and greater than or equal to 0.This single number can be uniquely decoded to create the exact stream of symbols that went into its construction. To construct the output number, the symbols are defined a set probabilities.

   4. LZW

   LZW is denoted by the name LempelZivWelch developed by Abraham Lempel, Jacob Zev and Terry Welch in 1984. It is dictionary-based compression technique which allows mapping of a variable length of image sequence to fixed length of code [14]. LZW algorithm records the pattern in dictionary. The first 255 entries contain the value of ASCII therefore the actual allocation of index to the string starts from index 256. The main working principle of LZW algorithm is the multiple occurrence of bit sequence for a given image that needs to be encoded. LZW algorithm builds a dictionary by replacing the multiple occurrences of pattern by an index code. As it is adaptive technique so no need to transmit the dictionary. At receiver side dictionary will rebuilt during decoding process.

4. COMPARATIVE ANALYSIS

   Comparative analysis for various image compression techniques is done after checking of compression ratio or in terms of time performance time of various algorithms on various images.

   1. Compression Ratio

      Compression ratio is the ratio between the original size of the image and the compressed size of the image it is calculated as

      Original Size

      represented by white spaes.For example, the text 1010000001 is considered as a source to compress, taken the first 3 letters as a non-run having a length 3, and the next

      Compression Ratio =

      Compressed Size

      (2)

   2. Compression Time

   Time taken for compression and decompression must be taken into consideration as in some cases decompression time and in some cases compression time to be considered is necessary and in some cases both of them are necessary.

   Here we compare compression ratio of Run Length Encoding, Huffman Coding, Arithmetic Coding and LZW algorithms on various images. Table I shows comparative analysis for the methods discussed in the paper for the images in fig. 4 along with the application area.

5. CONCLUSION

Image Compression is an important field of research due to its wide range of application in image processing area. In this paper we performed a survey on various lossless compressing techniques. Paper fuscous mainly on algorithm listed Huffman Coding, Run Length Encoding, Arithmetic Coding, and LZW. Comparative analysis is provided for the discussed techniques based on the compression ratio achieved by each technique.

Fig. 5.(a) Image_1 with original file size= 10,834 bytes

(b) Image_2 with original file size= 8392 bytes Table 1

REFERENCES

1. Jaya S. kulchandani and Suman H. pal , Image Compression: review and comparative analysis International journal of research and technology (IJERT) ISSN: 2278-0181 vol.3 issue 11,November-2014

2. www.wikipedia.com

3. Shrusti Porwal, Yashi Chaudhary, Jitendra Joshi, Manish Jain, Data Compression Methodologies for Lossless Data and Comparison between Algorithms ISSN: 2319-5967 International Journal of Engineering Science and Innovative Technology (IJESIT), Volume 2,

   Issue 2, March 2013

4. Uli Grasemann and Risto Miikkulainen,Effective Image Compression using Evolved Wavelets,ACM, pp. 1961-1968, 2005

5. V.K padmaja and Dr B.chandrasekhar, Literature review of image compression algoriyhm IJSER vol. 3 PP 1-6-2012

   Algorithm	Image_1	Image_2	Application Area
   	CR	CR
   Run Length Encoding	1.03	1.02	Used mostly for frequently occurring Sequences of pixels.
   Huffman coding	1.57	1.19	Used in JPEG
   Arithmetic Coding	1.84	1.58	Used in TIFF and GIF files
   LZW	1.28	1.36	Used mostly for TIFF, BMP

6. ManjinderKaur, GaganpreetKaur , A Survey of Lossless and Lossy Image Compression Techniques International Journal of Advanced Research in Computer Science and Software Engineering Volume 3,

   Issue 2, February 2013 ISSN: 2277 128X

7. Gaurav Vijayvargiya, Dr. Sanjay Silakari,Dr. Rajeev Pandey, A Survey: Various Techniques of Image Compression IJCSIS) International Journal of Computer Science and Information Security,

   Vol. 11, No. 10, October 2013

8. Mamta Sharma, Compression Using Huffman Coding International Journal of Computer Science and Network Security, Vol.10 No.5, pp. 133-141,May 2010.

9. Uchale Bhagwat Shankar, Image Compression Technique, International Journal of Information Technology and Knowledge Management, Volume 2, No. 2, pp. 265-269, December 2010.

10. R. Gonzalez and R. Woods, Digital Image Processing, 2nd ed. Upper Saddle River, NJ, USA: Prentice Hall,Inc,2002.

11. Data Compression Conference (DCC '00), March 28-30, 2000, Snowbird, Utah.

12. Huffman D.A., A method for the construction of minimum redundancy codes, Proceedings of the Institute of Radio Engineers, 40 (9), pp. 10981101, September 1952.

13. Introduction to Data Compression, Khalid Sayood, Ed Fox (Editor), March 2000.

14. Dalvir Kaur and Kamaljeet Kaur, Data Compression on Columnar- Database using Hybrid Approach (Huffman And Lempel-Ziv Welch Algorithm), International Journal of Advanced Research in Computer Science and Software Engineering, Volume 3, Issue 5, pp. 889-894

    ,May 2013.

15. 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, Issue 4 (February 2013) PP: 26-28