Additional Lossless Compression of JPEG Images Nikolay Ponomarenko1, Karen Egiazarian2, Vladimir Lukin1, Jaakko Astola2 1 Dept 504, National Aerospace University (Kharkov Aviation Institute) 17 Chkalova Street, 61070, Kharkov, Ukraine E-mail:
[email protected] 2 Tampere International Center for Signal Processing, Tampere University of Technology P.O.Box-553, FIN-33101, Tampere, Finland E-mail: { karen, jta}@cs.tut.fi Abstract The task of additional compression of images earlier coded using JPEG is considered. A novel efficient method for coding quantized DCT coefficients is proposed. It is based on coefficient separation into bit planes, taking into account correlation between the values of neighbor coefficients in blocks, between the values of the corresponding coefficients of neighbor blocks as well as between the corresponding coefficients of different color layers. It is shown that the designed technique allows for images already compressed by JPEG to additionally increase compression ratio by 1.3…2.3 times without introducing additional losses.
1. Introduction The compression standard JPEG [1,2] based on discrete cosine transform (DCT) has been accepted in 1992. It has been the main standard of lossy image compression for more than 10 years. During this time, throughout the world an enormous number of images compressed and archived using JPEG has been stored. They are family archives of amateur pictures, medical image databases, remote sensing data, etc. After accepting of JPEG, more efficient methods for image lossy compression have been designed. For example, wavelet based coding put into basis of the later standard JPEG2000 [3,4] has been thoroughly studied. The usage of JPEG2000 leads to increasing of compression ratio (CR) by 2…2.5 times in comparison to JPEG for a given compression quality. Thus, there is the desire to apply new achievements in image compression theory for enhancing the CR of images stored in the format JPEG. One possible variant deals with application of JPEG2000 to decoded images previously compressed by JPEG according to procedure depicted in Fig. 1. However, in this case the losses introduced by JPEG are added by distortions due to application of JPEG2000. This can be acceptable only if these additional distortions (losses) are rather small (their evaluation is performed in Section 4). Besides, for some
applications like medical image compression, the introducing of additional losses is unacceptable at all. JPEG image
Decoding
Decoded image
Coding by JPEG2000
Figure Figure 1. The usage of JPEG2000 for recompression of JPEG images This paper presents a novel method for additional lossless compression of JPEG coded images. This method presumes partial decoding of JPEG image with further more effective removal of redundancy in quantized coefficients of image blocks (Fig. 2).
Image
Obtaining of quantized DCT coefficients Lossy
Coded image
Coding of DCT coefficients Lossless
More effective modified coding of DCT coefficients Lossless
JPEG image
Decoding of DCT coefficients Lossless
Figure 2. Lossless recompression of JPEG coded images Such approach is not absolutely new. For example, in [5] it is proposed to take into account correlation between spectral coefficients of image neighbor blocks. This allows further decreasing the coded file size by approximately 14% on the average. Below similarly to [6] we propose to use division of DCT coefficient array into bit planes and to take into account both correlation between the values of neighbor coefficients in blocks and the values of the corresponding coefficients of neighbor blocks. Besides, for color images it is possible to take into account correlation between the corresponding coefficients of different color layers.
2. Probability models for grayscale JPEG images Recall that for the compression standard JPEG an entire image is divided into 8x8 pixel blocks. Let us separate the array of absolute values of quantized DCT coefficients into n bit planes where n is the index of the highest (most significant) bit plane for which there exist non-zero values. The signs of non-zero quantized DCT coefficients are practically random values. Thus, for sign coding one bit is assigned and the corresponding values are passed to the output data stream from the very beginning of coding. Let Pkl,m(i,j) denotes the value of bit in the k–th bit plane for the i,j–th quantized DCT coefficient for the image block with indices l,m where k=1..n, i,j=1..8, l=1..L, m=1..M; L,M are the numbers of image blocks for both axes. Introduce the following conditions that are used for classification of types of bit plane points: 1) C1(k,l,m,i,j)=true, if 1∈ { Pk+2l,m(i,j),..., Pnl,m(i,j)}; 2) C2(k,l,m,i,j)=true, if 1∈ { Pk+1l,m(i,j),..., Pnl,m(i,j)}; 3) C3(k,l,m,i,j)=true, if 1∈ { Pkl,m(i,j),..., Pnl,m(i,j)}; 4) C4(k,l,m,i,j)=true, if Pk+1l,m(i,j)=1; 5) C5(k,l,m,i,j)=true, if Pkl,m(i,j)=1; 6) C6(k,l,m,i,j)=true, if true∈ {C2(k,l,m,i-1,j-1), C2(k,l,m,i-1,j), C2(k,l,m,i-1,j+1), C2(k,l,m,i,j-1)}; 7) C7(k,l,m,i,j)=true, if true∈ {C5(k,l,m,i-1,j-1), C5(k,l,m,i-1,j), C5(k,l,m,i-1,j+1), C5(k,l,m,i,j-1)}; 8) C8(k,l,m,i,j)=true, if true∈ {C3(k,l-1,m-1,i,j), C3(k,l-1,m,i,j), C3(k,l-1,m+1,i,j), C3(k,l,m-1,i,j)}; By checking these conditions the point Pkl,m(i,j) is referred to one or another probability models according to Table 1 (pmX denotes the probability model №X).
considered case, the best method for this array coding is to apply some lossless data coding technique, e.g., lossless versions of JPEG or JPEG2000. In some cases, this allows providing additional decreasing of compressed file size up to 5%. Below in simulations we for simplicity restricted ourselves by coding these coefficients separately from other ones with point value referring to one or another probability model according to Table 2.
C1
C2 true true
false
pm11
true
pm12
pm10 pm9
Therefore, the entire number of frequency models required for recompression of gray scale JPEG images is equal to 12.
3. Analysis of efficiency of grayscale JPEG image additional compression For testing the proposed method a set of standard grayscale images Lenna, Barbara, Goldhill, Baboon, Peppers has been used. All images have 512x512 pixels. As original files for additional compression, the JPEG images with original compression ratios 4, 8, 16 and 32 (bpp=2, 1, 0.5 and 0.25, respectively) have been used. Table 3 shows bpp after additional compression by the proposed technique (J-M). Besides, the values of the additional compression factor (ACF) are presented. The provided aggregate compression ratio (ACR) is, thus, the product of original CR and ACF. Table 3
Table 1 C8 true false
bpp (JPEG) Image
2
1
0.5
0.25
J-M ACF J-M ACF J-M ACF J-M ACF
false C7 false pm7 pm8
Lenna 1.525 1.31 0.676 1.48 0.286 1.75 0.114 2.20
true pm5 pm6
Barbara 1.483 1.35 0.635 1.58 0.266 1.88 0.109 2.30
pm3
Goldhill 1.503 1.33 0.670 1.49 0.285 1.75 0.112 2.23
C2 false C6 С1 false true true true
Table 2 false C8
false
pm4
pm2 pm1
Thus, we obtain 8 probability models for coding the point values of bit planes. All models are binary, i.e. a bit value can be either “0” or “1”. Note that for such models there exists an effective realization for arithmetic coding [7]. The DCT coefficients with indices i,j=1 for image blocks are the quantized mean values multiplied by correction factor. Being grouped in a separate array they produce downscaled copy of an original image. For the
Baboon 1.474 1.36 0.661 1.51 0.276 1.81 0.110 2.26 Peppers 1.509 1.33 0.676 1.48 0.286 1.75 0.112 2.22
As seen, the provided improvement is rather stable in the sense that ACF is practically independent on compressed image and is mainly determined by original CR of JPEG image. For instance, for some JPEG image with original CR=4 one can expect ACF≈1.3. Similarly, for original CR=8, 16 or 32 the expected ACF is approximately 1.5, 1.75 and 2.2, respectively. It is also reasonable to consider the percent distribution of bit plane point values between
probability models and entropy for them. Table 4 presents such data for the test image Lenna. Table 4 Probability models
bpp
1 1
%
2
3
4
5
6
7
8
9 10 11 12
Table 5 presents PSNR for J-M and for J-J methods for four bpp values provided for original JPEG files. As seen from Table 5, the use of JPEG2000 for additional compression always leads to considerable decreasing of image quality. Quite often such degradation exceeds 1 dB and it is visually noticeable (Fig. 3).
0.5 0.6 2.2 2.4 0.8 2.4 0.7 88.8 0.9 0.2 0.2 0.2
entropy 0.98 0.91 0.95 0.29 0.75 0.22 0.44 0.005 0.98 0.89 0.62 0.06 0.5
%
0.1 0.3 1.2 2.3 0.4 1.8 0.4 92.0 0.8 0.3 0.3 0.2
entropy 0.96 0.83 0.93 0.21 0.76 0.15 0.39 0.002 0.98 0.79 0.62 0.09
As seen, the point classification is performed rather efficiently. Especially apparently this is seen for pm8 to which the bits that are, with high probability, equal to “0” should be referred. Indeed, the small entropy of data for this model evidences that only a small number of bits equal to “1” are falsely referred to it.
4. Analysis of JPEG2000 additional compression
usage
for
Let us return to recompression scheme in Fig. 1 that presumes using JPEG2000 for additional compression of JPEG images. Consider what practical additional losses are observed in this case. For image compression quality evaluation let us use I
a)
J
PSNR = 10 lg(255 2 /[∑∑ ( I ij − I ije ) 2 / IJ ] ) where Iij is i =1 j =1
the pixel value after decompression, Ieij denotes the pixel value of original (not compressed) image, IJ define the image size. While considering JPEG images one should keep in mind the blocking artifacts in decoded images. The use of post-filtering for blocking artifact elimination [8] can result in considerable improvement (up to 1.5 dB) of decoded image quality. Because of this, we consider the quality of JPEG decoded images after blocking artifact removal. JPEG2000 is also applied to decoded images for which blocking artifacts are already removed. Let us additionally compress the decoded images Lenna, Barbara, Goldhill, Baboon, Peppers using JPEG2000 (this method is denoted as J-J). The CR for JPEG2000 are selected equal to the corresponding ACF presented in Table 3 for J-M. Table 5 PSNR,dB Image JPEG bpp=2 J-M
J-J
bpp=1 J-M
J-J
bpp=0.5 J-M
J-J
bpp=0.25 J-M
J-J
Lenna 41.04 40.02 37.22 36.42 33.83 32.85 29.49 28.61 Barbara 39.29 38.14 32.54 31.18 27.24 26.30 24.36 23.90 Goldhill 37.79 36.66 33.66 32.65 30.56 29.68 27.60 26.87 Baboon 29.86 28.67 25.75 24.70 23.18 22.29 21.14 20.57 Peppers 38.53 37.67 35.70 35.11 33.17 32.40 29.27 28.33
b) Figure 3. The fragments of decompressed image Barbara for recompression (bpp=0.635) methods J-M (a) and JPEG2000 (b) The obtained results demonstrate that the proposed method of partial recompression is preferable for further lossless compression of JPEG images. Besides, quite often additional losses in JPEG image compression are not acceptable. Thus, the use of JPEG2000 for this purpose is inadmissible.
5. Additional compression of color JPEG images Color JPEG images contain data for three layers, namely Y,U and V. The layer Y relates to information on pixel intensity and these data can be additionally compressed according to the same scheme as grayscale JPEG images (using probability models pm1-pm12, see Section 3). The layers U and V contain information on pixels color. There are two possible approaches to their additional compression. Simpler approach is to apply the J-M method to these two layers as well. More complex approach (denoted as J-C) is to make probability model more complex to take into consideration the correlation between different color layers. Let us evaluate what is the benefit due to such complexion. Let us introduce additional condition С9(k,l,m,i,j) that assigns the value true if for, at least, one earlier coded layer the condition C3(k,l,m,i,j) was true. For each of models pm3, pm4, pm5, pm6, pm7, pm8 in case of bit coding for layers U and V let us introduce two new models to be used instead of above listed ones. For C9(k,l,m,i,j)=true the first among introduced new models is applied, otherwise the second new model is used. Compare the methods J-M that is simpler and J-C that is more complex. The JPEG color images Lenna, Baboon, Goldhill, Peppers and Barbara have been used in tests. The obtained results (the obtained bpp values for four original bpp for JPEG images) for both techniques application are represented in Table 6. Table 6 bpp (JPEG) Image
2 J-M
1 J-C
J-M
0.5 J-C
J-M
J-C
0.25 J-M
J-C
Lenna 1.517 1.487 0.697 0.681 0.314 0.308 0.129 0.126 Barbara 1.486 1.457 0.664 0.650 0.304 0.297 0.119 0.116 Goldhill 1.534 1.498 0.691 0.677 0.312 0.306 0.129 0.126 Baboon 1.615 1.582 0.715 0.700 0.316 0.309 0.127 0.124 Peppers 1.511 1.479 0.671 0.656 0.299 0.293 0.125 0.122
As seen, the use of J-C allows obtaining ACRs that are only by 2-2.5% larger than for J-M. This can be explained by originally larger compression of JPEG data for layers U and V in comparison to the layer Y. In fact, the decoded data for layers U and V occupy less than half of entire JPEG coded file size. Thus, the additional benefit of 4-5% provided for layers U and V due to taking into account mutual correlation for them leads to 2-2.5% benefit for entire file. Since the provided benefit for the method J-C is rather small, in practice it seems reasonable to use J-M for additional compression for all three layers. Negligibly worse compression in this case is compensated by simpler probability model. All three
layers for J-M are additionally compressed separately. Then, in case of decoding errors, the method J-M possesses better noise immunity than J-C. Besides, there exists an opportunity to manipulate the data in separate layer without changing data in other layers.
6. Conclusions The obtained data show rather high efficiency of the designed method. It allows considerable, by 1.3…2.3 times, increasing of additional compression of JPEG images without introducing additional losses. Recall that the method [5] produces only about 14% additional compression. Moreover, the proposed method possesses all advantages inherent for methods implying bit plane coding. Data decoding and transferring (for example, in Internet) is started from the most significant bits and at any time can be interrupted with providing an opportunity to visualize and analyze the already obtained part of data. One more perspective of further enhancing the compression techniques based on bit plane coding and DCT deals with using partition schemes [9].
References [1] Wallace G. K., “The JPEG Still Picture Compression Standard”, Comm. Of the ACM, Vol.34, No.4, 1991. [2] W. B. Pennebaker and J. L. Mitchell, “JPEG Still Image Data Compression Standard”, Van Nostrand Reinhold, New York, 1993. [3] Christopoulos C., Skodras A., Ebrahimi T., “The JPEG2000 still image coding system: an overview”, IEEE Transactions on Consumer Electronics, Vol.46, Issue: 4, Nov. 2000, pp.1103–1127. [4] D. Taubman, M. Marcellin, “JPEG 2000: Image Compression Fundamentals, Standards and Practice”, Boston: Kluwer, 2002. [5] Bauermann I., Steinbach E., “Further Lossless Compression of JPEG Images”, Picture Coding Symp., PCS 2004, San Francisco, December 15-17, 2004. [6] Taubman D., “High Performance Scalable Image Compression with EBCOT”, IEEE Transactions on Image Proc., vol. 9, No. 7, July 2000, pp.1158-1170. [7] Langdon G.G., Rissanen J.J., “A simple general binary source code”, IEEE Trans.Inf.Theory, IT-28 (Sept.), 1982, pp. 800-803. [8] K. Egiazarian, M. Helsingius, P. Kuosmanen, J. Astola, “Removal of blocking and ringing artifacts using transform domain denoising”, Proc. of ISCAS’99, vol. 4, May 30 - June 2 , 1999, pp. 139 – 142. [9] Ponomarenko N., Lukin V., Egiazarian K., Astola J., “Partition Schemes in DCT Based Image Compression”, Technical Report 3-2002, ISBN 952-15-0811-6, Tampere University of Technology, Finland, 2002, 100 p.
