An Analytical Review of Lossy Image Compression using n-TV Method

An Analytical Review of Lossy Image Compression using n-TV Method

Dr. Anjali Mathur1 Department of Mathematics

Jodhpur Institute of Engineering & Technology Jodhpur, India

Nitesh Agarwal2 Dr. Sandeep Mathur3

Department of Computer Science Department of Mathematics

Jodhpur Institute of Engineering & Technology Jodhpur Institute of Engineering & Technology Jodhpur, India Jodhpur, India

Abstract- Image compression is widely used in general life for many purpose. Image compression process reduce required storage size of image, to store in digital devices. Digital devices & computational resources have limited communication & storage capabilities hence there is need to compress high quality digital image to overcome this limitation of digital devices & computational resources, for ex. a single high quality image may require 10 to 100 million of bits for representation. If such type of images are in communication with low bandwidth, than there is need to compress each image before communication to use proper bandwidth & for synchronized communication. Hence image compression is an important topic for researcher to improve image compression process by introducing new technique or method in this field. This paper deals with embedding n-TV method before entropy encoding this method make repeated sequence of values before entropy encoding (RLE), to get high compression ratio. This paper gives an analytical review of lossy image compression by using n-TV method at different positions in lossy image compression process.

Keywordsimage, compression, n-TV, RLE, entropy, encoding.

1. INTRODUCTION

   There are numerous applications of image processing, such as satellite imaging, medical imaging and video where the image size or image stream size is too large and require a large amount of storage space or high bandwidth for communication in its original form. Every storage device & communication bandwidth cannot satisfy this requirement hence image compression techniques are used in such type of applications where image size is too large to store in digital device & too large for communication purpose. Image compression plays a very important role in application like tele-videoconferencing, remote sensing, document & medical imaging and facsimile transmission, which depends on the efficient manipulation, storage & transmission of binary, gray scale or color images.

   Image compression techniques can be classified into two categories lossless image compression & lossy image compression. Images that provide numerical, Secure &

   financial information compressed using lossless image compression because we required original data back after decompression process. But other images like multimedia images can be compressed using lossy image compression because the human eye is very tolerant of approximation error in an image. Hence we may decide to exploit this tolerance to produce increased compression, at the expense of image quality by reducing some pixel data or information. Lossless image compression use some entropy encoding techniques like Run Length Encoding (RLE), Huffman Encoding, LZW (Lempel Ziv Welch) Encoding, and Area Encoding. This paper deals with RLE as a entropy encoding in lossless image compression. RLE entropy encoding give good compression ratio when image have repeated pixel value sequentially but all the image not have such type of repeated pattern hence present paper use n-TV (Threshold Value) method to make repeated sequence before entropy encoding.

   • Lossy Image Compression: – Lossy compression technique is especially suitable for natural images such as photos in application where minor loss of fidelity is acceptable. Lossy scheme is widely used must application. Because the reconstruct image is sufficient for representing original Image.

   Fig 1: Lossy Image Compression process

   Fig 1 shows the outline of lossy compression technique. Transformation is applied to the original image. The discrete transform cut the images into block of 64 pixels (8×8) and process each block independently, shifting and simplifying the colours so that there is less information to encode. Then the quantization process result in loss of information. In the quantization the value in each block are divided by a quantization coefficient.

   This is the compression step where information loss occurs. Pixels are changed only in relation to the other pixel with their entropy coding is applied after quantization. The reduced coefficients are then encoded usually with entropy coding. The decoding is a reverse process. In the decoding process firstly entropy encoding is applied to compress data to get the quantized data after that dequantized is applied to it and finally the inverse transformation is applied to get the reconstructed image by this scheme the decompress image is not identical to the original image but reasonable close to it. This scheme provides much higher compression ratio than lossless scheme.

   • n-TV method:- This method traverse input matrixxel matrix row by row. The method uses two node 1st node store the 1st pixel & 2nd node move forward row by row in pixel matrix. It take pixel difference between pixel value store in these two node & repeat the pixel value store in node 1 by replacing value of traversed pixel by node 2 until difference between these two nodes are not greater than n. Once a difference greater than n occurs node 1 store that pixel & node 2 traverse pixel one by one from its next adjacent pixel & same process is follow until complete pixel matrix not traversed. For ex.

     w = width of pixel matrix; h = height of pixel matrix;

     pixel[h][w] = pixel matrix of original image; for(i=0; i<h; i++)

     {

     j=0;

     tmp=pixel[i][j]; for(j=0; j<w; j++)

     {

     if( (difference between tmp & pixel[i][j]) > n) pixel[i][j] = tmp;

     else tmp=pixel[i][j];

     }

     }

     } [1]

     This method used in such type of image where modifying some pixel data does not cause any big problem.

   • 2D DCT: – DCT convert an image into its equivalent frequency domain by partitioning image pixel matrix into blocks of size N*N. An image is a 2D pixel matrix hence 2D DCT is used to transform an image. [8]

     2-D DCT can be defined as

     121	120	125	120	221	220	225	220
     106	104	107	106	206	204	207	206
     202	201	200	202	102	101	100	102
     28	29	30	32	28	29	30	32
     1	5	2	3	5	4	0	2
     155	154	153	150	151	152	157	158
     202	201	200	202	102	101	100	102
     121	120	125	120	221	220	225	220

     121	120	125	120	221	220	225	220
     106	104	107	106	206	204	207	206
     202	201	200	202	102	101	100	102
     28	29	30	32	28	29	30	32
     1	5	2	3	5	4	0	2
     155	154	153	150	151	152	157	158
     202	201	200	202	102	101	100	102
     121	120	125	120	221	220	225	220

     N1 N1

     2x1u

     2y1v

     Cu,vu(v)fx,ycos

     2N cos

     2N

     1

     for

     x0 y0

     u, v = 0,1,2,,N 1.

     & inverse transformation is defined as

     N1 N1

     2x1u

     2y1v

     Table 1: Input matrix

     fx,yu(v)cu,vcos

     2N cos

     2N

     2

     Table 1 shows a 2D input matrix but this matrix cannot be

     u0 v0

     compressed using RLE because pixel value not repeated sequentially. n-TV method convert this matrix so that it can be compressed using RLE. Let the value of variable n in n-TV

     Where Cu, v represents frequency value for u, v &

     f x, y represents pixel color value at position ( x, y ).

     method is 08 then converted pixel matrix is

     121	121	121	121	221	221	221	221
     106	106	106	106	206	206	206	206
     202	202	202	202	102	102	102	102
     28	28	28	28	28	28	28	28
     1	1	1	1	1	1	1	1
     155	155	155	155	155	155	155	155
     202	202	202	202	102	102	102	102
     121	121	121	121	221	221	221	221

     121	121	121	121	221	221	221	221
     106	106	106	106	206	206	206	206
     202	202	202	202	102	102	102	102
     28	28	28	28	28	28	28	28
     1	1	1	1	1	1	1	1
     155	155	155	155	155	155	155	155
     202	202	202	202	102	102	102	102
     121	121	121	121	221	221	221	221

     (u)

     1 for N

     u 0

     3

     2

     N

     1

     for u 0

     (v)

     for

     N

     v 0

     4

     Table 2: Input matrix After n-TV method with variable n =8

     After the n-TV method pixel matrix contain a good no of repeated pixel as shown in table 2. This repeated pixel helps

     2

     N

   • Quantization

     for v 0

     the RLE to compress pixel matrix. n-TV algorithm

     Input: Pixel matrix of input image. Output: Modified Pixel Matrix.

     {

     A Quantizer simply reduces the number of bits needed to store the transformed coefficients by reducing the precision of those values. Since this is a many-to-one mapping, it is a lossy process and is the main source of compression in an encoder.

     The quantization matrix is designed to provide more resolution to more perceivable frequency components over less perceivable components (usually lower frequencies over high frequencies) in addition to transforming as many components to 0, which can be encoded with greatest efficiency. A DCT block is quantize using following formula

2. LITERATURE SURVEY

   1. H. Husseen , S. Sh. Mahmud & R. J. Mohammed Image Compression Using Proposed Enhanced Run Length Encoding Algorithm , Ibn Al-Haitham Journal For Pure And Applied Science, VOL 24(1), pp. 315-328,

      QDCT i, j ROUND DCT (i, j)

      QT (i, j)

      5

      2011.

      This paper introduce new algorithm in witch we compute

      the differences between the adjacent pixels for each

      & this QDCT block dequantize by following formula

      DCT i, j ROUND QDCT (i, j) * QT (i, j) 6

      For i, j= 0, 1, 2, 3.,N-1

      Where (i,t) define position of input & output value, QDCT is DCT block after quantization, QT is standard quantization matrices & defined as

      16	11	10	16	24	40	51	61
      12	12	14	19	26	58	60	55
      14	13	16	24	40	57	69	56
      14	17	22	29	51	87	80	62
      18	22	37	56	68	109	103	77
      24	35	55	64	81	104	113	92
      49	64	78	87	103	121	120	101
      72	92	95	98	112	100	103	99

      Table 3: Standard Quantization Table [10]

      • RLE (Run Length Encoding):- This is a very simple compression technique method used for compressing sequential data. any digital image consist pixel values that are repeats sequentially for such type of image RLE is useful. In proposed n-TV method RLE receive sequential data from pixel matrix modified by n-TV method & store pixel value that repeats & no of time that pixel value repeat sequentially. For example table 2 by RLE compressed as

        Pixel Value	Repetition	Pixel Value	Repetition
        121	4	155	8
        221	4	202	4
        106	4	102	4
        106	4	121	4
        202	4	221	4
        102	4
        28	8
        1	8

        Table 4: Compressed Data after RLE

        Table 4 required less storage space as compare to table 1.

        Table 1 require total 64 values to store but table 3 require only 26 values to store [5].

        Compression Ratio (CR) = 64/26 = 2.46

        color, if the difference between pixels less than or equal to a threshold value (th<=10) we add 1 to C1, and if the difference is greater than 10 we do this process between next adjacent pixels until we reach the last pixel in the image. this method makes repeated sequence in the matrix so that it can give high compression ratio using RLE.

   2. Gregory K. Wallance, The JPEG Still Picture Compression Standard, IEEE Transaction on Consumer Electronics, Volume 38, No. 1, February 1992.

   This paper describes JPEG still image compression process. JPEG image compression process use DCT as a transformation technique & standard quantization table of 8*8 dimension before entropy encoding.

3. OBJECTIVE

   The main objective of this paper to find out a value of n in n-TV method on which lossy image compression gives best compress image with optimum compression ratio, MSE & PSNR values. The 2nd objective of this paper is to find out proper position of this method with entropy encoding in lossy image compression process to get best result.

4. METHEDOLOGY

   • Embedding n-TV method after the quantization in lossy image compression.

   Fig 2: Lossy Image Compression process with n-TV method (after quantization)

   Steps involved in this process

   1. Create pixel matrix of the image & divided it into blocks of size 8*8

   2. Apply FDCT (Forward Discrete Sine Transform) on each 8*8 block of pixel matrix to get equivalent 8*8 DCT blocks using eq (1).

   3. Apply eq (5) on each block of DCT to get QDCT block.

   4. Apply n-TV algorithm on each block of QDCT to get n-TV block.

   5. Combine each n-TV block & apply RLE on combine block & store this encoded block on secondary storage.

   6. To get required image read encoded matrix from secondary storage & apply entropy decoding (Run Length Decoding) on that encoded matrix.

   7. Divide this decoded matrix in to blocks of size 8*8.

   8. Apply eq (6) on each block to get DCT blocks.

   9. Apply eq (2) on each DCT block to get IDCT blocks.

   1. Using decoded matrix we get required image.

      Now we Find MSE (Mean Squared Error), PSNR (Peak Signal to Noise Ratio) & CR (Compression Ration) to determine quality of image obtain by proposed method for each value variable n used in n-TV algorithm.

5. OUTPUT

   • Lossy Image Compression with n-TV method (After

     1. Combine all IDCT blocks to get pixel matrix.

     2. Using pixel matrix we get required image.

     Now we Find MSE (Mean Squared Error), PSNR (Peak Signal to Noise Ratio) & CR (Compression Ration) to determine quality of image obtain by proposed method for each value variable n used in n-TV algorithm.

     Quantization)

     t=1

     t=2

     Size=47.9 KB

     1 H 1 W 1

     2

     H *W

     H *W

     MSEn

     [O(x, y)Mn (x, y)] 7

     x 0 y 0

     PSNRn=20*log10 (MAX) – 10*log10 (MSEn) (8)

     Size=39.9 KB

     CR Original Image size

     9

     n Output Image size

     t=3

     Where H=Height of Image, W= Width of Image, variable MAX shows max value of a pixel for example here image is 8 bit hence MAX=255 [6], MSEn, PSNRn & CRn is MSE, PSNR & CR at variable n used in n-TV method.

     Quality of image obtain by proposed method is depend on MSEn & PSNRn value. If as the MSE value increases PSNR

     Uncompressed Image Size=768 KB

     t=4

     Size=39.9 KB

     Size=31.9 KB

     value decreases then we get a bad quality of image by proposed method & if as the MSE value decreases PSNR value increases we get a batter quality image hence on basis of this MSEn & PSNRn value proposed method gives a best value of variable n on which we get a optimum compressed image with best quality.

     • Embedding n-TV method after the inverse transformation in lossy image compression.

     Fig 3: Lossy Image Compression process with n-TV method (after Inverse DCT)

     Steps involved in this process

     1. Create pixel matrix of the image & divided it into blocks of size 8*8

     2. Apply FDCT (Forward Discrete Sine Transform) on each 8*8 block of pixel matrix to get equivalent 8*8 DCT blocks using eq (1).

     3. Apply eq (5) on each block of DCT to get QDCT block.

     4. Apply eq (6) on each block to get DCT blocks.

     5. Apply eq (2) on each DCT block to get IDCT blocks.

     6. Combine each IDCT block & apply n-TV algorithm on combine block

     7. Apply RLE on store this encoded block on secondary

        storage.

     8. To get required image read encoded matrix from secondary storage & apply entropy decoding (Run Length Decoding) on that encoded matrix.

        Fig 4: Lossy Image Compression with n-TV Method after quantization

        Compressed Images

        Compressed Images

        Table 5: MSEn, PSNRn, CRn on different value of n

   • Graphs

   1. n-TV vs. CRn

      Fig 5: Variation in CRn with different value of variable n

   2. n-TV vs. MSEn

      Fig 6: Variation in MSEn with different value variable n

   3. n-TV vs. PSNRn

   • L

   • L

   Fig 7: Variation in PSNRn with different value variable n ossy Image Compression with n-TV method (After

   1. n-TV vs. CRn

      Fig 9: Variation in CRn with different value of variable n

   2. n-TV vs. MSEn

      IDCT)

      t=1

      Uncompressed Image Size=768 KB

      t=2

      t=3

      t=4

      Size=255 KB

      Size=199 KB

      Size=159 KB

      Fig 10: Variation in MSEn with different value variable n

   3. n-TV vs. PSNRn

   Size=136 KB

   Compressed Images

   Graphs

   Graphs

   Fig 8: Lossy Image Compression with n-TV Method after quantization

   Table 6: MSEn, PSNRn, CRn on different value of n

   Fig 11: Variation in PSNRn with different value variable n

6. CONCLUSION

The result presented in this document shows that

1. The results shows that as the value of variable n increases storage size of image decreases as shown in table 5 & in table 6.

2. As the value of n increases CRn also increases.As the value of n increases proposed process add more noises in the image i.e. value of MSEn increases as shown in Fig 6 & in fig 10.

3. Use of n-TV method after quantization gives worst result because it add errors in image in large amount that cannot be ignored as shown in table5.

4. Use of n-TV method after IDCTgives good result with less error than previous method. This error can be neglect.

FUTURE SCOP

Image compression process is very important field for researcher. There are wide range of scope in this field. Proposed method deals with variable n used in n-TV method in future we try to improve this method so that a best value of n is taken dynamically on the basis of input image i.e the value of n is depends on input image.

REFERENCES

1. A. H. Husseen , S. Sh. Mahmud & R. J. Mohammed Image Compression Using Proposed Enhanced Run Length Encoding Algorithm , Ibn Al-Haitham Journal For Pure And Applied Science, VOL 24(1), pp. 315-328, 2011.

2. A.M. Raid, W.M. khedr, M.A. El-dosuky and wesan Ahmed JPEG image compression using Discrete Cosine Transform A survey, International Journal of Computer Science & Engineering Survey (IJCSES), vol 5, no 2, pp. 29-47, April 2014.

3. Andrew B. Watson, Image Compression Using Discrete Cosine Transform, NASA Ames Research Centre, 4(1), pp. 81-88,1994

4. Anjali Kapoor and Dr. Renu Dhir, Image Compression Using Fast 2-D DCT Technique, International Journal on Computer Science and Engineering (IJCSE), vol. 3 pp. 2415-2419, 6 June 2011

5. Asha Lata & Permender singh Review of Image Compression Techniques, International Journal of Emerging Technology & Advanced Engineering (IJETAE), vol 3, issue 7, pp. 461-464, July 2013.

6. Firas A. Jassim and Hind E. Qassim, FIVE MODULUS METHOD FOR IMAGE COMPRESSION, signal & image processing: An International Journal (SIPIJ), vol 3, no.5, pp. 19-28,

   Octobar 2012

7. Harley R. Myler and Arthur R. Weeks The Pocket Handbook of Image Processing Algorithms in C, ISBN 0-13-642240-3 Prentice Hall P T R Englewood Cliffs, New Jercy 07632.

8. Gregory K. Wallance, The JPEG Still Picture Compression Standard, IEEE Transaction on Consumer Electronics, Volume 38, No. 1, February 1992.

9. Iain E.G. Richardson H.264 and MPEG-4 Video Compression: Video Coding for Next-generation Multimedia, ISBN 0470848375, 9780470848371, Wiley, 2003.

10. Jesse D. Kornblum Using JPEG quantization tables to identify imagery processed by software, ELSEVIER, DIGITAL INVESTIGATION 5, pp. S21-S25,2008.

11. Maneesha Gupta and Dr.Amit Kumar Garg, Analysis Of Image Compression Algorithm Using DCT International Journal of Engineering Research and Applications (IJERA), vol.2, pp. 515- 521, Jan-Feb 2012

12. N. Ahmed, T. Natarajan, and K.R. Rao, Discrete Cosine Transform, IEEE Transactions on Computers, vol. C-32, pp. 90-93, Jan. 1974.

13. Swati Dhamija and Priyanka Jain Comparative Analysis for Discrete Sine Transform as a suitable method for noise estimation IJCSI International Journal of Computer Science Issues, Vol. 8, Issue 5, No 3, September 2011 pp. 162-164.

14. V.Singh Recent Patents on Image Compression A Survey, Recent Patents on signal Processing (Bentham Open), vol 2, pp. 47- 62, 2010 .