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

DOI : 10.17577/IJERTCONV4IS12010

Download Full-Text PDF Cite this Publication

Text Only Version

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 .

Leave a Reply