New Algorithm to Find the Missing Strings During Compressed Image Transmission using Huffman Encoding

New Algorithm to Find the Missing Strings During Compressed Image Transmission using Huffman Encoding

M. A. P. Manimekelai,

Professor, Dept ECE, Karunya University, Coimbatore-641114 Mariam Stephina Punnose, Rinda Regi, Sherin Alphonsa John Students, ECE,Karunya University,Coimbatore,India-641114

Abstract – Usually Images require a large disk space during transmission and storage.This is disadvantageous as it consumes more memory and becomes slower and suits the requirements of the user.There are many methods of image compression and decompression but we have used a simple coding technique called Huffman coding in MATLAB platform.This technique is simple in implementation and utilizes less memory but major drawback is some strings of symbols will be missing during the transmission of the compressed image.In this paper we propose a new algorithm to overcome this problem.

Keywords:Huffmancoding,PSNR,MSE,Compression Ratio

1. INTRODUCTION

   An efficient method for image compression is necessary as normal images take large amount of disk space and transmission speed will be very low.There are many compression techniques.There are two main types of image compression ,i.elossy and lossless.Lossless compression is preferred for archival purposes and often for medical imaging, technical drawings, clip art, or comics. Lossy compression methods, especially when used at low bit rates, introduce compression artifacts.Lossy methods are especially suitable for natural images such as photographs in applications where minor (sometimes imperceptible) loss of fidelity is acceptable to achieve a substantial reduction in bit rate. The lossy compression that produces imperceptible differences may be called visually lossless.Lossy compression formats suffer from generation loss: repeatedly compressing and decompressing the file will cause it to progressively lose quality. This is in contrast with lossless data compression, where data will not be lost via the use of such a procedure.Huffman encoding is one of the most qualitative lossless compression technique existing.A digital image after sampling and quantization requires enormous storage .Assuming, a 24 bit color image 512×512 pixles will occupy 768 Kbyte storage on a disk [1] . It takes nearly 4 minutes to transmit an image over a 28.8 kbps modem.The purpose for image compression is to reduce the amount of data required for representing sample digital images and reducing the cost of image transmission.

   The compression of images plays a key role in many important applications such as image database,image communications,remote sensing(weather sensing and other earth resource applications).The image compression is done in gray scale with pixel values between 0 and 255.There are different methods of image compression, which include lossy and lossless [2]. In lossless compression no information regarding the image is lost.In other words,the reconstructed image from compressed image is identical to the original image [3]. In lossy compression image information is lost,i.e..,the reconstructed image from compressed image is not identical to original image.Huffman encoding generates minimum redundancy codes compared to other algorithms.It is being effectively used in text ,image ,video compression and conferencing system such as JPEG,MPEG-2,MPEG-4 and H.263 etc.It can calculate the probability value and sort the symbols based on the probability value by collecting the unique symbols from the source image .From the lowest probability value symbol to the highest probability value symbol, two symbols combined to form a binary tree.A synthetic performance of the compression is given by PSNR and Compression Ratio to validate the image compression. Image compression has two main categories [4]. Statistical schemes and dictionary schemes. Huffman coding comes under statistical scheme.

   The major disadvantage of image compression and transmission during Huffman encoding is that some strings of symbols will be missing during transmission.The main objective of this paper is to obtain a new algorithm to find the missing strings during transmission time.

   The entire paper consists of the following sections: i)Introduction

   ii)Principle behind compression iii)Error metrics

   1. Perfomance Parameters

   2. Huffman coding

   3. Algorithm to find missing strings

2. PRINCIPLE BEHIND COMPRESSSION:

   The common characterstic of most images is that the neighbouring pixels are correlated and therefore contain redundant information.Two fundamental components of compression are redundancy and irrelevancy reduction.

   1. Removal of duplication from the signal source

   2. Irrelevancy reduction, omits parts of the signal that will not be noticed by Human Visual System.

   In an image that consists of a sequence of images there are three type of redundancies to compress file size

   1. Coding Redundancy: fewer bits torepresent frequently occurring symbols.

   2. Interpixel redundancy:Neighbouring pixels have almost same value

   3. Psycho Visual redundancy: Human visual system cannot simultaneously distinguish all colours.

3. ERROR METRICS:

   Mean Square Error is the cumulative squared error between compressed and original image.

4. PERFOMANCE PARAMETERS:

   A)Compression Ratios:

   Its defined as the number of bits to represent the size of original image to the number of bits to represent the size of compressed image [5]. R=n1/n2 where n1 and n2 represents the number of bits required by original and compressed image respectively.

   B)Peak Signal To Noise Ratio(Psnr):

   Its the measure of quality of reconstruction of image.The signal in this case is the original data and the noise is the error introduced by compression.Logically a higher value of PSNR is good because it means that the ratio of signal to noise is higher [6].

5. HUFFMAN CODING :

The two important observations of Huffman code procedure are:

1. More frequently occurred symbols will have shorter code words than symbol that occur less frequently.

2. The two symbols that occur least frequently will have the same length.

The Huffman code is an entropy encoding algorithm used for lossless data compression [7]. The term refers to the use of a variable length code table for encoding a source symbol where the variable length code table has been derived in a particular way based on the estimated probability of occurrence for each possible value of the source symbol. It uses specific method for choosing the representation for each symbol, resulting in a prefix code that expresses the most common source symbols using shorter strings of bits than are used for less common source symbols.

ADVANTAGES:

i)Algorithm is easy to implement [8]. ii)Produce a lossless compression of images. DISADVANTAGES :

1. Algorithm varies with different formats[8].

2. Huffman encoding is usually done in two passes. During the first pass a statistical model is built, and then in the second pass the image data is encoded based on the generated model. From here we can see that Huffman encoding is relatively a slow process as time is required to build the statistical model in orderto achieve efficient compression rate.

3. Compression of image files that contains long runs of identical pixels by Huffman Is not as efficient when compared to RLE.

4. One of the major disadvantage is that , the encoded data is corrupted with missing bits, thenwhatever that is decoded will be wrong values and the final image displayed will not be fully correct. This paper aims at finding the missing bits during transmission of the compressed image using Huffman coding.

6) ALGORITHM TO FIND MISSING STRINGS: Step1 :Read the image on the work space of Matlab

Step2 :Convert the given colour image into gray scale image .

Step3 :Double mapping is done by DCT (Discrete cosine transform)

Step 4 : Obtain quantization matrix Step 5 :Assign DCT matrix [8].

Step 6:Include the block processing functions Step 7:Get the channel for encoding

Step 8:Complete the scale forward DCT

Step 9:If channel=1,compute quantization for luminescence,else compute quantization for colors.

Step 10:Compute the entropy code for the whole channel and get the entropy code without zeroes on the end.

Step11 :Perform Huffman encoding and add to output.

Step12:Perform Huffman decoding and check if it is correct.

Step13:Execute entropy decoding and dequantisation steps.

Step14:By performing the inverse DCT,scale back the original image and set it as the output.

Step15:To find out the missing strings,remove first symbol and calculate the ratio.

Step 16: Calculate the CR and PSNR [10]. Step17:Show the results.

RESULTS: INPUT IMAGE :

ENTROPY VALUES:

PERFOMANCE METRICS:

INPUT-OUTPUT IMAGE:

MISSING BITS:

CONCLUSION:

The above presented shows a new algorithm to find the missing strings of symbols during compressed image transmission. The technique used for compression is lossy Huffman encoding. The input image is given on the MATLab platform of size 512×512 pixels in .bmp format. Depending upon the frequency of occurance of symbols(in the image), they are encoded, quantized and mapped. Further dequantization and decoding is done to obtain back the original image. In this process, few string of bits can be missing while transmission. This paper presents the algorithm to find those missing bits. Also performace parameters such as mean square ratio(MSR) and compression ratio(CR) are calculated to validate the new algorithm. It is seen that whenever the CR increases, error will be minimum. It means that compressed image is almost same as original image.

REFERENCES:

1. A new lossless method of image compression and decompression using Huffman coding techniques-Jagadesh H. Pujaar, Lohit M Kadlaskar,Dept of EEE, BVB college of Engg and Tech,Hubly,India.

2. Lossless image compression- B C Vemuri, S Sahni, F Chen, C Kapoor,C Leonard and J Fitzsimmons

3. A Survey: Various techniques of image compression- Gaurav Vijayvargiya, Dr Sanjay Silakari, Dr Rajeev Pandey- Dept of CSE, UIT-RGPV,Bhopal , India

4. Latent palmprint matching-Anil K Jain, Fellow, IEEE and Jianjing Feng

5. Image compression using Huffman coding based on Histogram information and image segmentation. DrMonisha Sharma(professor), MrChandrashekhar K.( Asst Professor), Lalak Chauhan-Dept of ECE,SreeSankaracharya College of Engg and Tech, Bhilai, India.

6. A new,fast and efficient image coder based on set partitioning in hierarchical trees-IEEE- A Said,W Pearlman.

7. Literature review of image compression algorithm- Padmaja V K,Dr B Chandrasekhar, Jwaharlal Technological University,Anantapur,India

8. A low complexity, conext based lossless image compression algorithm-M J Weinberger,GSeroussi, G Sapiro

9. Experiments with lossless and virtually lossless image compression algorithms-G G Langdon and C AHaidinyak

10. DSalomon:Data compression-The complete reference, Springer Verlag