Image Compression via Modified TiBS Algorithm to Achieve High Compression Rate

International Journal of Computer Applications (0975 – 8887) Volume 78 – No.13, September 2013 Image Compression via Modified TiBS Algorithm to Achieve High Compression Rate Pravin B. Pokle# Narendra.G. Bawane*, Ph.D #Ph.D. Scholar, Deptt. of Electronics Engg, *Principal, S.B.Jain Institute of Engg., B.D.College of Engg, Wardha,India Management and Research, Nagpur, India ABSTRACT algorithm. In [2, 6] comparison of energy consumption of JPEG, In recent times the integration of video, audio and data in JPEG2000 and SPIHT is carried out. These algorithms lead to telecommunication devices has revolutionized communication greater energy consumption than the transmission of the world. It has proven to be useful to almost every industry: the uncompressed image. Transform-based image coding algorithms corporate world, entertainment industry, multimedia, education have been the object of intense research during the last twenty and even at home. The major problems associated with these years. Eventually they have been selected as the main mechanism applications are the high data rates, high bandwidth and large of data compression in the definition of digital image and video memory required for storage and computing resources. Even with coding standards. For example JPEG, MPEG-1, MPEG-2, H.261 faster internet speed, throughput rates and advanced network and H.263 all rely on an algorithm based on the Discrete Cosine infrastructure, there are major bottlenecks to transfer such high Transform (DCT). volume data through the network due to bandwidth limitations. Image compression schemes come under two categories: lossless There is a need to develop compression techniques in order to and lossy compression. Lossless compression uses coding make the best use of available bandwidth. Thus storage and techniques to compress the data while retaining all information compression of these high resolution images plays a vital role in content. However, the compression achieved using this method such applications to conserve the energy and processor’s for file size reduction is not sufficient for many applications [3, computational resources. This paper presents a lightweight 9]. On the other hand lossy image compression, as its name modified TiBS algorithm for image compression and storage. The implies, results after compression contains the loss of some proposed modified compression method operates on a 3x3 block information content while the file size reduction can be much and is based on pixel removal technique. The results shows that more significant than obtained with lossless compression. Run- proposed method provides a maximum compression of 33% length encoding (RLE) and JPEG compression algorithms are which is more than that achievable by standard TiBS algorithm. examples of lossless compression. The Lempel–Ziv (LZ) compression methods are among the most popular algorithms for lossless storage. Wavelet and higher-level JPEG are the examples Keywords of lossy compression techniques. JPEG 2000 is a progressive Image compression, DWT, DCT, TiBS (tiny block-size lossless-to-lossy compression algorithm. JPEG handles only still encoding), Huffman, RLE. images; also another standard called MPEG is used for motion pictures [8, 10]. 1. INTRODUCTION JPEG is one of the most used image compression that has revolutionized lossy data compression by providing a method to The increase in the digital imaging techniques in the last few decrease the size of natural images with minimal loss of decades has made it possible to capture high resolution images perceivable data. The codec uses a combination of DCT, using hand held devices such as digital cameras, mobile phones, quantization matrices, and entropy encoding and Huffman ipads etc. Further with the available wireless technologies it is encoding to discard less relevant data and compress the image. often required to transfer these images wirelessly from a remote However, the JPEG standard causes harsh blocking artifacts, due location to a destination location as in case of a wireless sensor to the uniform discretization of the image into 8x8 blocks, when network. As these digital images are usually represented by a images are compressed to low bit rates [4, 11]. very large number of bits, communication of a single image from The newer standard, JPEG2000 [12], significantly reduces the source to sink node involves the transmission of several data distortion present after compression. Here first a global wavelet packets. This results in large energy consumption at the source transform to the image is applied, and then EBCOT (Embedded node than nodes collecting and forwarding scalar data. As the Block Coding with Optimal Truncation Points) encoding is radio transceivers are one of the most power consuming performed, followed by further entropy encoding [5]. The use of components on sensor nodes, it is obvious that compression of EBCOT and entropy coding after the wavelet transformation image data would definitely lead to significant energy savings [1]. allows a highly compressed version of the image with very little Image compression, is the science of reducing the amount of data distortion. However, the algorithm does not provide a technique required to represent an image. The use of available compression to take advantage of local patterns within the image, such as a techniques like JPEG, JPEG 2000, PNG, SPIHT, etc can serve low frequency area in the background of an image, due to the the purpose to compression the image. But more an image is initial global wavelet transform, which prevents this approach compressed; more is the need for an ARQ (Automatic Repeat- from having the highest amount of compression possible. reQuest) or FEC (Forward Error Correction) based protocol to As most of digital images are intended for human observers, maintain a certain level of image quality. This error control some loss of information in the digital image can often be method counter balances the energy saved by compression unnoticed by the human eye, hence much of the research work 32  International Journal of Computer Applications (0975 – 8887) Volume 78 – No.13, September 2013 nowadays is focused on lossy compression that minimizes visual distortion and possibly obtains visually lossless results. In general in any compression algorithms, there are three basic steps: B0,0 B0,1 x3|i-1, j-1 x2|i-1, j x3|i-1, I/P j Compressed Transform Quantizer Encoder Image B1,0 x1|i, j-1 x0|i, j x1|i, Fig 1: Typical image compression system j In this paper a modified lightweight image compression Bi,j algorithm called TiBs (tiny block-size image compression), that employs a 3x3 block size instead of a 2x2 block is proposed. The x3|i, j-1 x2|i, j x3|i, j proposed modified TiBS algorithm provides a good trade-off between energy consumption and image quality. Finally a comparison is made between DCT, DWT, Huffman, RLE, TiBS (2x2 block size) and proposed modified TiBS (3x3 block size). The paper is organized as follows: Section 2 describes the Fig 3: Representation of 2x2 block Bi,j [5]. technical principles of the TiBS algorithm. In Section 3 we present the proposed modified TiBS algorithm. Section 4 gives 2.1 Self-Adaptive Pixel Removal the results of the proposed algorithm and finally, Section 5 cover This step where certain number of pixels from the image are conclusions and provides some future directions. removed in such a way that spatial correlation among the unremoved pixels is retained, so as to estimate the missing pixels 2. TiBS ALGORITHM at the decoder end. In the standard TiBS algorithm 1-pixel is removed out of the four pixel intensities so that the encoded 2×2 TiBS is a lossy compression algorithm with very low complexity block can be represented with 3×m bits. At the decoder end this which provides communication of images in an energy-efficient missing pixel can be estimated from its surrounding pixels based manner, even for high packet loss rates. Since DCT or DWT is on spatial error concealment method. One drawback of this computationally intensive and the Encoder in TiBs does not use method is that the quality of the resulting image cannot be DCT or DWT, its working is somewhat different than the controlled as the magnitude of block distortion can vary from conventional structure as shown in figure 1. Figure 2 depict block block to block significantly. However this drawback can be dealt diagram of TiBS algorithm. This algorithm operates on blocks of with to a good extent by a self-adaptive pixel removal (SAPR) 2x2 pixels. Each block is encoded independently, based on three method as proposed in [7]. This SAPR method removes that pixel stages: uniform scalar quantization, self-adaptive pixel removal, which induces the smallest block distortion. In this method first and variable-length coding. The quantization stage is optional;  depending on the user requirements. No quantization stage results X 0 |i , j and Do|i,j are computed assuming that Xo|i,j is the in better image quality instead of energy savings. The most removed pixel and so on for the remaining three pixels. Then to original part of TiBS is the self-adaptive pixel removal technique. find the best pixel to be removed by finding out k such that mink (Dk|i,j) which is the block distortionbetween original and decompressed image. Finally this pixel is removed and its place Original block of Encoded block is inserted into the LSBs of the three retained pixels, using the Q SAPR 2 x 2 pixels (B i,j) (B^ i, j) transform τ as given below. ..................... (3) Fig 2: TiBS compression scheme. Consider a digital image with an array of pixels with width C and where z ={z1, z2, z3}are the LSB’s of three retained pixels from a height R which are the even integers in colour plane then, set of p € (0, 1, 2, 3) ................. (1) 2.2 Uniform Scalar Quantization Where the pixel intensities are represented using m bits. Thus the In SAPR method, for each block of 2×2 pixels only one pixel out pixel intensities are integers in the range 0 to M, where of four pixels is discarded and hence this achieves a compression ................. (2) ratio of 4:3. Higher compression ratios can be obtained when a scalar quantizer is applied to a block first. Quantization here acts TiBS algorithm divides the color plane into non overlapping 2×2 as a rounding off of the input values to decrease the number of blocks of pixels. Let Bi,j denote the block at the ith row and jth distinct output values to a smaller set m′ such that m′< m. As in column (with 0≤i<H/2 and 0≤j<W/2). Before encoding process [7], a simple uniform quantizer as given in equation 1 below Bi,j contains four pixel intensities, denoted X0|i,j, X1|i,j, X2|i,j represents the quantization levels.  ~ and X3|i,j as shown in Figure 3. Let B i , j and B i , j denote the encoded and decompressed version of Bi,j respectively. .................. (4) Where QΔ is number of quantization levels, 2Δ is the step size and x is the original pixel intensity, this will show increase in the compression ratio substantially. Basic use of this step is to reduce the number of blocks in an image. 33  International Journal of Computer Applications (0975 – 8887) Volume 78 – No.13, September 2013 3. PROPOSED MODIFIED TiBS So we get (216)10 for maximum intensity value and (145)10 for medium value pixel. ALGORITHM In the proposed modified TiBS algorithm, we consider a 3x3 Step4. Encode the remaining block with new decimal values block as shown in figure 4 below. In our proposed modified TiBS as given below. method we remove three pixels; the maximum, the minimum and the medium one, out of each 3x3 block. Thus by applying this So this gives the final encoded array of six unremoved pixel method each 3x3 block requires 3x2x8 bits as compared to 3x3x8 which are the transmitted and thus convert our 3x3 block into a bits for the uncoded image. By using this method the 3x2 block of pixels. compression ratio of more than 25% (up to 33%) can be achieved as compared to 25% in case of standard TiBS algorithm discussed above. The encoding and decoding process of proposed method is elaborated with the help of an example below. 3.2 Decoding Algorithm. Now at the decoder side on receiving the 6 pixel values we reconstruct the 3x3 block as follows with following received pixel values: Step1. Search for the location for missing pixels in the Received stream. Step2.Check for the four LSB’s for each of the received decimal value. Here we get the position of missing pixel value in the decoded 3x3 block. Fig 4: Representation of 3x3 block Bi,j. Step3. Repeat it for each received numbers. 3.1 Encoding Algorithm Step4. Replace the decimal values according to the position obtained as given below which are the missing pixels. Step1. Partition the given image into 3 x 3 blocks of pixels. Step2. Reduce the No. of block using uniform scalar Quantization. Consider the following reduce block.  640 1281 2202   3 4 5  Step5. Now to complete the decoding process the remaining  32 157 64  positions are filled out serially from the received pixel values. Note here that the order here is not changed it’s the same as the  786 1297 2558    pixels were originally received. So we get the finally decoded pixel value as: Step3. Search for the min, Max and Medium intensity value  67 78 216  Pixels from each block.    64 145 64   78 129 216  Now from the above block the minimum value is 32, the   maximum value is 255 and medium value is 128. These pixels So to sum up we have reconstructed the 3x3 pixel array with are removed so this leaves us the below matrix: transmission of only 3x2 values at the decoder side, this is  64 X 220  represented graphically as below.    X 157 64   78 129 X   The indexes of these removed pixels are 1, 3 and 8 respectively. So this leaves us with the 6 unremoved values as: The index of the minimum value pixel removed is 3, which give 0011 in binary. This binary is replaced with the binary equivalent of the first value i.e.; 64 of the unremoved pixel as shown below; (64)10 = (00100000)8 (00100011)8 = (67)10 Fig 5: Modified TiBS encoding-decoding Process Now comparing this with the original pixel values before encoding, from this it is clear that the proposed technique is lossy Similarly the same process is repeated for the maximum and compression technique as three out of nine pixels are removed, medium intensity value pixels respectively. 34  International Journal of Computer Applications (0975 – 8887) Volume 78 – No.13, September 2013 but the result shows that the loss of image information is not that substantial considering the human vision. 4. RESULTS OF MODIFIED TiBS ALGORITHM Figure 6 below shows the input image and figure 7 shows the compressed image using Huffman, DCT and RLE algorithms. Figure 7(a) shows the compressed image using standard TiBS algorithm and figure 7(b) shows the decompressed using our proposed modified TiBS algorithm. Fig 7(b): Compressed Image using proposed modified TiBS. Fig 6: Input image (a) (b) Figure 7: Compressed Image. (c) (d) Fig 8: Test Images. First row of Table I, shows the comparison between Huffman, RLE, DCT, standard TiBS and proposed modified TIBS algorithm based on Minimum mean square error (MMSE), PSNR, compression ratio and time required for the results obtained in figure 6 and 7 above. The rest of the rows directly show the comparison of results among these algorithms with respect four different images. Fig 7(a): Compressed Image using standard TiBS. 35  International Journal of Computer Applications (0975 – 8887) Volume 78 – No.13, September 2013 Table I: Comparison of results for different images Image Parameters Huffman DCT RLE TiBS Modified TiBS Image 1 MMSE (dB) 47.066 31.428 47.066 39.67 21.01 Hydrangeas Image PSNR (dB) 16.727 14.973 16.727 83.97 82.84 (Figure 7) Compression Ratio (%) 7.181 74.90 51.425 25.00 28.93 Time Elapsed (s) 0727 0.117 0.165 0.39 1.42 Image 2 MMSE (dB) 47.902 34.927 47.902 32.78 15.19 Koala Image PSNR (dB) 16.804 15.432 16.804 84.02 83.15 (Figure 8. a) Compression Ratio (%) 2.979 74.902 48.569 25.00 27.76 Time Elapsed (s) 0.903 0.118 0.168 0.40 1.42 Image 3 MMSE (dB) 47.677 26.892 47.677 44.12 17.94 Desert Image PSNR (dB) 16.783 14.296 16.783 84.15 83.25 (Figure 8. b) Compression Ratio (%) 3.268 74.902 48.932 25.00 26.10 Time Elapsed (s) 0.822 0.117 0.164 0.40 1.39 Image 4 MMSE (dB) 48.120 34.023 48.120 38.18 14.09 Tulip Image PSNR (dB) 16.823 15.318 16.823 84.27 83.56 (Figure 8. c) Compression Ratio (%) 4.819 74.902 47.522 25.00 26.56 Time Elapsed (s) 0.820 0.118 0.165 0.40 1.24 Image 5 MMSE (dB) 45.908 26.360 45.908 40.03 26.37 Jelly Fish Image PSNR (dB) 16.619 14.209 16.619 83.09 83.71 (Figure 8. d) Compression Ratio (%) 20.041 74.902 55.713 25.00 24.82 Time Elapsed (s) 0.631 0.118 0.167 0.40 1.36 modifications can be made in the proposed method for further 5. CONCLUSIONS improvement of the PSNR and compression ratio. For compression of digital images there are many algorithms exists and lots of researchers have been proposed various 6. REFERENCES algorithms on image compression. From this literature it is clear [1] I.F.Akyildiz, W.Su, Y.Sankarasubramaniam and E.Cayirci, that the most of the compression techniques adopted "Wireless Sensor Networks: A Survey", Computer Networks transformation, Quantization and assignment of codeword’s to 38(4)(2002) 393–422. the pixels in an image. Since transformation step is computationally complex and more intensive and it takes more [2] Ferrigno L, Marano S, Paciello V, Pietrosanto A. computation time which will delay the result after compression. Pietrosanto. Balancing computational and transmission Again in conventional methods it is very difficult to recover the power consumption in wireless image sensor networks. missing pixels at the decoder side. In this paper, a modified TiBS International Conference on Virtual Environments, Human- algorithm is proposed which uses a 3x3 tiny block size and Computer Interfaces, and Measures Systems. Italy. 2005: removes 3 pixels from each of these blocks. The advantage of 61–66 this method is that since the block size is only of 3 x 3 which is [3] Shantanu D. Rane and Guillermo Sapiro, Member, very small, and becomes more robust, computationally easier to IEEE,”Evaluation of JPEG-LS, the New Lossless and encode and becomes less complex as in this method no Controlled-Lossy Still Image Compression Standard, for transformation is required. Also at the decoder side the missing Compression of High-Resolution Elevation Data”, IEEE pixels can be easily retained to reconstruct the original image Transactions on Geoscience and Remote sensing, VOL. 39, from the block of pixels having small size of 3 x 3 for each block. NO. 10, Oct. 2001 Since we discard three pixels from each block this method achieves the compression ratio up to 33 % which very much [4] Med Lassaad KADDACHI, Adel SOUDANI, Ibtihel useful for wireless transmission of image data. The results NOUlRA, Vincent LECUlRE and Kholdoun TORKI obtained for different images show that the proposed modified "Efficient hardware solution for low power and adaptive TiBS algorithm has better compression ratio and PSNR values as image-compression in WSN", 978-1-4244-8157-6110, compared to the standard TiBS algorithm. In future certain ICECS 2010, IEEE. Zhang, Y. Z., Xu, C., Wang, W. T., & 36  International Journal of Computer Applications (0975 – 8887) Volume 78 – No.13, September 2013 Chen, L. B. Performance Analysis and architecture design structural similarity,” IEEE Transactions on Image for EBCOT encoder in JPEG2000. IEEE Transactions on Processing, Vol. 13, no. 4, 2004. Circuits and Systems for Video Technology, 17(10), 1336– 1347.-2007. [8] B. Goossens, A. Pizurica, and W. Philips, “Removal of correlated noise by modeling the signal of interest in the [5] C. Duran-Faundez, V. Lecuire, "Error resilient image wavelet domain,” IEEE Trans.Image Process., vol. 18, no. 6, communication with chaotic pixel interleaving for wireless pp. 1153–1165, Jun. 2009. camera sensors", Workshop on Real-World Wireless Sensor Networks (REALWSN 2008), ACM, Glasgow, Scotland [9] R. C. Gonzalez and R. E. Woods, "Digital Image (2008), pp. 21–25. Processing", 2nd Ed., Prentice Hall, 2004. [6] Cristian Duran-Faundez, Vincent Lecuire, Francis Lepage, [10] Wallace, G. K. “The JPEG Still Picture Compression "Tiny block-size coding for energy-efficient image Standard”, Comm. ACM, vol. 34, no. 4, April 1991, pp. 30- compression and communication in wireless camera sensor 44. networks", Signal Processing: Image Communication 26 [11] Grzegorz, P. (2005).Ahigh-performance architecture for (2011) 466–481. 2011 Elsevier embeddedblock coding in JPEG 2000. IEEE Transactions on [7] Z. Wang, A. C. Bovik, H. R. Sheikh and E. P. Simoncelli, Circuits and Systems for Video Technology, 15(9), 1182– “Image quality assessment: From error visibility to 1191. IJCATM : www.ijcaonline.org 37