 Open Access
 Total Downloads : 780
 Authors : Diya V. Chudasama, Khushboo P. Parmar, Dipali Patel, Kruti Dangarwala, Shaishav Shah
 Paper ID : IJERTV4IS030953
 Volume & Issue : Volume 04, Issue 03 (March 2015)
 DOI : http://dx.doi.org/10.17577/IJERTV4IS030953
 Published (First Online): 30032015
 ISSN (Online) : 22780181
 Publisher Name : IJERT
 License: This work is licensed under a Creative Commons Attribution 4.0 International License
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 392001, 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.

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.

TYPES OF COMPRESSION
In classification of Image compression method there are two types.
Fig. 2. Types of Data Compression Techniques

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.

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


COMPRESSION ALGORITHM

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].

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 bottomup 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].

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.

LZW
LZW is denoted by the name LempelZivWelch developed by Abraham Lempel, Jacob Zev and Terry Welch in 1984. It is dictionarybased 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.


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.

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 nonrun having a length 3, and the next
Compression Ratio =
Compressed Size
(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.


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

Jaya S. kulchandani and Suman H. pal , Image Compression: review and comparative analysis International journal of research and technology (IJERT) ISSN: 22780181 vol.3 issue 11,November2014

www.wikipedia.com

Shrusti Porwal, Yashi Chaudhary, Jitendra Joshi, Manish Jain, Data Compression Methodologies for Lossless Data and Comparison between Algorithms ISSN: 23195967 International Journal of Engineering Science and Innovative Technology (IJESIT), Volume 2,
Issue 2, March 2013

Uli Grasemann and Risto Miikkulainen,Effective Image Compression using Evolved Wavelets,ACM, pp. 19611968, 2005

V.K padmaja and Dr B.chandrasekhar, Literature review of image compression algoriyhm IJSER vol. 3 PP 162012
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

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

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

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

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

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

Data Compression Conference (DCC '00), March 2830, 2000, Snowbird, Utah.

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.

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

Dalvir Kaur and Kamaljeet Kaur, Data Compression on Columnar Database using Hybrid Approach (Huffman And LempelZiv Welch Algorithm), International Journal of Advanced Research in Computer Science and Software Engineering, Volume 3, Issue 5, pp. 889894
,May 2013.

Athira B. Kaimal, S. Manimurugan, C.S.C .Devadass Image Compression Techniques: A Survey International Journal of Engineering Inventions eISSN: 22787461, pISBN: 23196491 Volume 2, Issue 4 (February 2013) PP: 2628