A Method for Lossless Compression of Images using Dithering to Improve the Quality: A Review

A Method for Lossless Compression of Images using Dithering to Improve the Quality: A Review

Veena Shukla

Student, Department of Computer Engineering AISSMS College of Engineering, Pune University Pune, India

Prof. N. R. Talhar

Faculty, Department of Computer Engineering AISSMS College of Engineering, Pune University Pune, India

Abstract Lossless compression of images is always better than lossy compression as we do not want to compromise with the quality of the image. Dithering is a technique that is used to make a color from the combination of available colors in case a particular color is not available. There are many image compression algorithms, such as entropy coding, arithmetic coding, Huffman coding, area coding, run length encoding that help to perform lossless image compression. Therefore, to improve the compression gain and the quality, special compression techniques can be used. In this paper we are reviewing about lossless compression of images and trying to figure out which technique is most appropriate and can provide improved results.

Keywords Lossless compression, Lossless compression techniques, Dithering, Dithering methods, Image quality

1. INTRODUCTION

   Lossless compression is a technique in which data bits remain the same after compression and when the image is uncompressed, all the original data can be recovered. This technique is useful whereas losing the data can be a problem. This method is applicable to both image and audio data. This method basically redrafts the data of true file in a more competent way. Suppose, when using lossy compression, a file is compacted, its size may be one-tenth of the true one but data loss affecting quality of the image is there whereas by using lossless compaction or compression, dimension of file can be smaller than half of the true one but the quality is almost same as the true image. Image compression plays essential role in many different applications e.g. remote sensing, image databases, image communications. The principle idea for image compression is to lessen the amount of data necessary for representing sampled digital images and therefore lessen the cost for storage and transmission.

   Dithering is the process of portraying an image with fewer colors than are in image. The most important application of quantization is for display devices that cannot deal with original colors. In this process, we possibly will have quantization errors, e.g., misrepresentation. To rise above quantization errors, dithering algorithms are used. In order to reduce the errors this method appends a dither signal to the entered image. The most illustrious algorithm was proposed by FloydSteinberg, which is identified as the Floyd Steinberg dithering technique in 1976.

   Quality of image can be defined as the attribute when compared to the original image which measures the apparent image deprivation. Normally all the systems commence distortion so to consider this factor is very important. Image

   quality consists of various factors like sharpness, contrast, accuracy, brightness, range, artifacts and many more. So to achieve the quality in an image, it is important to consider all these factors.

2. COMPRESSION ALGORITHMS

   Lossless and lossy are the two compression algorithms. Lossless compression algorithms compress the data in such a way that after compression it matches the true data. On the other hand lossy compression algorithms reduce the data to a very large amount but the quality of data is compromised in these algorithms.

   Lossless compression techniques: In these techniques re- enactment of image is same as the true image. It translates the image into pixels. The first step is the prediction of next pixel of image from the close to image pixel. The second is to find the difference between predicted pixel value and the original pixel value by using some encoding and decoding algorithms.

   1. Run length encoding (RLE)

   2. Huffman encoding

   3. Entropy Encoding

   4. Arithmetic encoding

   1. Run length encoding (RLE)

      Run length encoding algorithms is the fast and simplest technique in which the lengthy sequence of same symbols is replaced by shorter sequence. This algorithm is different from other algorithms in three aspects which are the coding of length information, the threshold and the marking of the start of the run. We are going to use this technique in the implementation.

   2. Huffman Encoding

      This algorithm also provides optimal results when rate of recurrence of entity script are used to compress the data. Also the algorithm says that if you have some scripts that are more recurrent than others, it makes sense to use lesser bits to encode those scripts than to encode the less frequent script.

   3. Entropy Encoding

      It is also one of the lossless image compression technique, this algorithm compress the image in a way that replace all fixed-length input character with the analogous variable-length prefix free output codeword. Main advantage of this technique is that it works independently with the characteristics that are specific to the medium. Also it assigns distinctive prefix-free code occurs in the input.

   4. Arithmetic Encoding

      This algorithm is type of entropy algorithm. This algorithm stores whole message into distinct codeIn this algorithm when a string of characters is processed through this algorithm, less frequent characters are stored with more bits and more frequent characters are stored with less bits. As a result only fewer bits are stored.

      Lossy techniques: In lossy techniques the compressed image is not same as the true one. There is significant amount of loss in these techniques. These methods provide high compression gain than lossless compression.

      1. Predictive coding

      2. Transform coding

3. DITHERING

   Dithering is an applied form of blare. It is the process of constructing an image with fewer colors when actual colors are not available. The process is done by evaluating each pixel in an image with a color palette having a fixed number of shades, Say 24. Now for every pixel RGB values, the closest of the 24 color values in the palette is selected as

   representative color. In a dithered image, colors not available in the color palette are matched by a dispersion of colored pixels from within the available color palette. The human eye recognize the dispersion or the diffusion as a mixture of the colors within it. As a result Dithering produces a quantized image by following some steps.

   1. Disturbing the input image by a signal (dither)

   2. To quantize the image this signal is added to give better results.

   The most well-known algorithm for Dithering the Images had been developed by Floyd Steinberg, popularly known as the FloydSteinberg dithering technique. The FloydSteinberg dithering techniques uses error-diffusion algorithms as an alternative of basic dithering algorithms, like average, ordered, or random, and produce images which look closer to the original form of the Image. The Floyd- Stein-berg dithering algorithm is based on error-diffusion (dispersion). The error- diffusion technique describes each point in the image. The first step is to find the nearest shade of the color available, then calculate the difference between the values in the image and the colors it has. By dividing up these errors values and distribute them over the adjoining pixels which are not identified yet. When these later pixels are received,just add the errors distributed from the earlier pixels and let the values to the permissible range if it is needed and then continue the process till all pixels are covered in the image.

   Dithering is mainly divided into two methods.

   1. Ordered dithering

   2. Clustered dithering

4. RELATED WORK

   In the paper Color quantization through dithering techniques C. Alasseur, A.G. Constantinides and L. Husson have proposed the method where noise is filtered by using sigma-delta modulators and with the filtration of noise, the quality of quantized image is improved.

   In the paper Lossless compression of dithered images Basar Koc, ziya Arnavut and Huseyin Kocak have tried PDT(pseudo-distance technique) for dithered images which is providing better compression gain and improved images.

   In the paper A New Lossless Method of Image Compression and Decompression Using Huffman Coding Techniques Jagadish H. Pujar and Lohit M. Kadlaskar have suggested lossless method of compression and decompression using the well-known Huffman-coding technique. They have developed algorithm for compression and decompression in MATLAB software platform.

   In the paper Image compression using DCT and Wavelet transformations Prabhakar Telagarapu,V. Jagan Naveen , A. Lakshmi Prasanthi, G. Vijaya Santhi have implemented the analysis of compression using DCT and Wavelet transformation as there is the scope for high compression with better quality and they have arrived at a conclusion that the performance of DWT is better than DCT.

   In the paper Compressing color-indexed images by dynamically reordering their palettes Yuk-Hee Chan, Ka- Chun Lui and P.K. Lun have suggested that the technique which turns the index map of color-indexed image into a new index map where each element serves the indexed pixel separately.

   In the paper Lossless image compression algorithms for transmitting over low bandwidth line Dr. E. Kannan and G. Murugan have suggested a technique for near-lossless image compression algorithm which is based on bayer format image and they have used Huffman coding technique for compression of the images.

   In the paper A lossless compression algorithm for color- indexed images using adaptive palette reordering Ka-Chun Lui and Yuk-Hee Chan have developed a technique for an adaptive palette reordering to reshape the statistical properties of the color index map of color-index image with dynamic palette.

5. CONCLUSION

As discussed in the paper, for compressing image, to a certain extent it is beneficial in terms of storage and transmission, due to low resource allocation required for same. For this purpose we have discussed lossless compression of images; methods and techniques implemented in the process and how useful or error free they are? Also, performing lossless compression using dithering can be advantageous in terms of improving the quality of image apart from compressing the same. By using lossless compression, it is very useful wherein the loss of data could pose many problems. Therefore lossless compression gives better results with superior compression gain as comparing with the lossy compression.

REFERENCES

1. Basar Koc, Ziya Arnavut ,Huseyyin Kocak Lossless Compression of Dithered Images , IEEE Photonics Journal 2013.

2. C Alasseur, A.G. Constantinides, L. Husson Colour Quantization through Dithering techniques , Electrical and Electronic Engineering Department, Imperial College, Exhibition Road, LONDON, SW7 2BT, UK.

3. Ka-Chun Lui and Yuk-Hee Chan A Lossless Compression Algorithm For Color-Indexed Images using Adaptive Palette Reordering, Department of Electronic and Information Engineering, The Hong Kong Polytechnic University, Hong Kong.

4. Jagadish H Pujar, Lohit M Kadlaskar A New Lossless Method Of Image Compression And Decompression Using Huffman Coding Techniques , Department of EEE, BVB College of Engg. & Tech. Hubli India.

5. Yuk Hee Chan, Ka-chun Lui, P. K. Lun Compressing Color-Indexed Images by dynamically reordering their Palletes, EUPISCO 2008 Swizerland.

6. Dr. E Kannan, G. Murugan Lossless Image Compression Algorithm For Transmitting Over Low Bandwidth Line, IJARCSSE 2012.

7. Prabhakar Telagarapu, V. Jagan Navees, A LakshmiPrasanthi, G Vijaya Santhi Image Compression Using DCT and Wavelet Transformations , GMR Institute of Technology, Rajam-532 127 Srikakulam , A.P. India.

8. Satveer singh, Harleen Kaur Study on Different Lossless Image Compression Techniques

9. Satveer Singh et al, Int.J.Computer Technology & Applications,Vol 5 (3),1020-1026.

10. R.Divya,M.K VidhyaLakshmi Comparison between Lossless Compression of the Dithered Image Using Pseudo-Distance Transform and Modified Pseudo-Distance Transform International Journal of Scientific & Engineering Research, Volume 5, Issue 4, April-2014.

11. Quantisation of Colour Images , by E. S. H. Cheung and A. G. Constantinides, Proc. Of International Conference on Digital Signal Processing, Cyprus, 1993

12. [Online] Available: http://www.visgraf.impa.br/Courses/ip00/proj/Dithering1

/.