- Open Access
- Total Downloads : 27
- Authors : Dr. Anjali Mathur, Nitesh Agarwal, Dr. Sandeep Mathur
- Paper ID : IJERTCONV4IS12010
- Volume & Issue : ETRASECT – 2016 (Volume 4 – Issue 12)
- Published (First Online): 24-04-2018
- ISSN (Online) : 2278-0181
- Publisher Name : IJERT
- License: This work is licensed under a Creative Commons Attribution 4.0 International License
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.
-
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
LITERATURE SURVEY
-
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.
-
-
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.
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.
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
-
Create pixel matrix of the image & divided it into blocks of size 8*8
-
Apply FDCT (Forward Discrete Sine Transform) on each 8*8 block of pixel matrix to get equivalent 8*8 DCT blocks using eq (1).
-
Apply eq (5) on each block of DCT to get QDCT block.
-
Apply n-TV algorithm on each block of QDCT to get n-TV block.
-
Combine each n-TV block & apply RLE on combine block & store this encoded block on secondary storage.
-
To get required image read encoded matrix from secondary storage & apply entropy decoding (Run Length Decoding) on that encoded matrix.
-
Divide this decoded matrix in to blocks of size 8*8.
-
Apply eq (6) on each block to get DCT blocks.
-
Apply eq (2) on each DCT block to get IDCT blocks.
-
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.
OUTPUT
-
Lossy Image Compression with n-TV method (After
-
Combine all IDCT blocks to get pixel matrix.
-
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
-
Create pixel matrix of the image & divided it into blocks of size 8*8
-
Apply FDCT (Forward Discrete Sine Transform) on each 8*8 block of pixel matrix to get equivalent 8*8 DCT blocks using eq (1).
-
Apply eq (5) on each block of DCT to get QDCT block.
-
Apply eq (6) on each block to get DCT blocks.
-
Apply eq (2) on each DCT block to get IDCT blocks.
-
Combine each IDCT block & apply n-TV algorithm on combine block
-
Apply RLE on store this encoded block on secondary
storage.
-
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
-
n-TV vs. CRn
Fig 5: Variation in CRn with different value of variable n
-
n-TV vs. MSEn
Fig 6: Variation in MSEn with different value variable n
-
n-TV vs. PSNRn
-
L
-
L
Fig 7: Variation in PSNRn with different value variable n ossy Image Compression with n-TV method (After
-
n-TV vs. CRn
Fig 9: Variation in CRn with different value of variable n
-
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
-
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
CONCLUSION
The result presented in this document shows that
-
The results shows that as the value of variable n increases storage size of image decreases as shown in table 5 & in table 6.
-
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.
-
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.
-
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
-
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.
-
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.
-
Andrew B. Watson, Image Compression Using Discrete Cosine Transform, NASA Ames Research Centre, 4(1), pp. 81-88,1994
-
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
-
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.
-
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
-
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.
-
Gregory K. Wallance, The JPEG Still Picture Compression Standard, IEEE Transaction on Consumer Electronics, Volume 38, No. 1, February 1992.
-
Iain E.G. Richardson H.264 and MPEG-4 Video Compression: Video Coding for Next-generation Multimedia, ISBN 0470848375, 9780470848371, Wiley, 2003.
-
Jesse D. Kornblum Using JPEG quantization tables to identify imagery processed by software, ELSEVIER, DIGITAL INVESTIGATION 5, pp. S21-S25,2008.
-
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
-
N. Ahmed, T. Natarajan, and K.R. Rao, Discrete Cosine Transform, IEEE Transactions on Computers, vol. C-32, pp. 90-93, Jan. 1974.
-
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.
-
V.Singh Recent Patents on Image Compression A Survey, Recent Patents on signal Processing (Bentham Open), vol 2, pp. 47- 62, 2010 .
-