DCTbased Image Compression using Arithmetic Encoding Technique
Ei Ei Phyo, Nang Aye Aye Htwe
Abstract—Image or data compression is also called as source coding. It is theprocess of encoding information using fewer bits than anunencoded representation is also making a use of specific encodingschemes. Compressionis a technique that makes storing easier for large amount of data.There are various techniques available for compression.In my paper work, I have analyzed Arithmetic algorithm among other common compression techniques like Run length,LZW and Huffman Encoding.Arithmetic encoding provides an effective mechanism for removing redundancy in the encoding of data. Arithmetic coding works and describes an efficient implementation that uses lookup table as a fast alternative to arithmetic operations. The transform technique is based on Discrete Cosine Transform (DCT) transform. The performance is evaluated in terms of compression ratio (CR), Mean Square Error (MSE), and Peak Signal to Noise Ratio (PSNR).
Keywords—Arithmetic, Discrete Cosine Transform, Encoding,MSE, PSNR, Quantization
I.INTRODUCTION
There are different techniques for compressing images. They are broadly classified into two classes called lossless and lossy compression techniques. Lossless compression techniques are generally used where the reconstruction quality is important, such as executable programs, text documents and source codes. The lossy compression techniques achieve data compression by losing some information while maintaining the reconstruction quality. As the name suggests in lossless compression techniques, no information regarding is lost. In other words, the reconstructed image from the compressed image is identical to the original image in every sense. Whereas in lossy compression, some image information is lost that is the reconstructed image from the compressed image is similar to the original image but not identical to it. Inthis work we will use a lossless compression and decompression through a technique called Arithmetic coding. Arithmetic encoding method is frequently applied to images or pixels. It is a small compression component used in JPEG compression.
This paper is organized as follows: related works of the system are described in section two. In section three, background theory is explained. In section four, system design and implementation result are presented. Finally, in section five, the paper has been concluded.
II.Related Works
Bheshaj Kumar,Kavita Thakur and G. R. Sinha proposed that performance evaluation of image compression using symbol reduction technique [1]. In this paper, Lossy JPEG compression is a widely used compression technique. Normally the JPEG technique uses two process quantization, which is lossy process and entropy encoding, which is considered lossless process. In this paper, a new technique has been proposed by combining the JPEG algorithm and Symbol Reduction Huffman technique for achieving more compression ratio. The symbols reduction technique reduces the number of symbols by combining together to form a new symbol. As a result of this technique the number of Huffman code to be generated also reduced. The result shows that the performance of standard JPEG method can be improved by proposed method. This hybrid approach achieves about 20% more compression ratio than the StandardJPEG.
JAGADISH H. PUJAR and LOHIT M. KADhLASKAR proposed a new lossless method of image compression and decompression using Huffman coding techniques [2].The need for an efficient technique for compression of images ever increasing because the raw images need large amounts of disk space seems to be a big disadvantage during transmission and storage. Even though there are so many compression technique already present a better technique which is faster, memory efficient and simple surely suits the requirements of the user. In this paper, the Lossless method of image compression and decompression using a simple coding technique called Huffman coding is proposed. This technique is simple in implementation and utilizes less memory. A software algorithm has been developed and implemented to compress and decompress the given image using Huffman coding techniques in a MATLAB platform.
D.Malarvizhi and Dr.K.Kuppusamy proposed that a new entropy encoding algorithm for image compression using DCT [3]. Image compression addresses the problem by reducing the amount ofdata required to represent a digital image. Image compression is achieved by removing data redundancy while preservinginformation content. In this paper, a new alternative method for simultaneous image acquisition and compression calledadaptive compressed sampling. In this quality measures values gives better result for compare to other techniques. PSNR image quality factor is better in Penguins reconstructed the result is 12.7263 for MSE and 37.0838 PSNR with low value indicates a good quality.
Asadollah Shahbahrami, Ramin Bahrampour, Mobin Sabbaghi Rostami and Mostafa Ayoubi Mobarhanproposed that Evaluation of Huffman and Arithmetic Algorithms for Multimedia Compression Standards [4]. Compression is a technique to reduce the quantity of data without excessively reducing the quality of the multimedia data. There are various techniques and standards for multimedia data compression, especially for image compression such as the JPEG and JPEG2000 standards. These standards consist of different functions such as color space conversion and entropy coding. Arithmetic and Huffman coding are normally used in the entropy coding phase. In this paper,there have implemented and tested Huffman and arithmetic algorithms. Our implemented results show that compression ratio of arithmetic coding is better than Huffman coding, while the performance of the Huffman coding is higher than Arithmetic coding. In addition, implementation of Huffman coding is much easier than the Arithmetic coding.
Bilal Kamal Ahmed proposed that DCT Image Compression by Run-Length and ShiftCoding Techniques[5]. In this work an image is processed as three color channel. The correlatedpixels values of an image can be transformed to a representation where its coefficients are de-correlated. The term "decorrelated"means that the transformed values are independent of one another. As a result, they can be encodedindependently, which make it simpler to construct a statistical model. Correlated values are coded with run-lengthcoding techniques while shift coding used to decode the DC term and the other five lifting values. In this work, wesuggest to save the first five values from every block to keep it back without any significant errors.The obtained bitrates was extended to be within range (11.4 , 2.6), compression ratio (2.76 , 13.34 )the values of the fiedilityparameters (PSNR) was within the range (31.61 , 46.21) for the Lena test image in both sizes (128×128 and 256×256),and PSNR was calculated as average for the three color channels, red, green , blue.
III.Background Theory
The JPEG image compression system is composed of four main steps: image acquisition, preprocessing, image compression and image decompression.
A. Image Acquisition
Theinput colorimage is acquired byusing offline technique through the scanner or digital camera or other digital input devices. The input image is JPEG type. And then, the size of the image is arbitrary size.For image resizing, bilinear interpolation method is used.
B. Image Preprocessing
In the preprocessing step, it is necessary to perform changing color and chrominance down-sampling.
(i) RGB to YCbCr Conversion
RGB to YCbCr color conversionis necessary to transform for more efficient processing and transmission of color signals. Luminance component (Y) represents the intensity of the image and look likes a gray scale version. The chrominance components (CbCr) representthe color information in the image.Two chrominance components contain high frequency color information to which the human eye is less sensitive. Most of this information can be discarded.
(ii) Chrominance Down-sampling
After changing color space from RGB to YCbCr, the image is down-sampled by the factor of 2. The format is 4:2:0. Down-sampling can cause degradation ofpixels in chrominance channel (CbCr) in image compression system. There are three color formats in the baseline system:
(i) 4:4:4 formats: The sampling rate of the luminance component is the same as those of the chrominance.
(ii)4:2:2 formats: There are 2 I samples and 2 Q samples for every 4 Y samples. This leads to half number of pixels in each line, but the same lines per frame.
(iii)4:2:0 formats: Sample I and Q components by half in both the horizontal and vertical directions. In this format, there are also 1 I sample and 1 Q sample for every 4 Y samples.
C. Image Compression
In the image compression, the following steps are performed.
1)DCT image transform,
2)Image quantization,
3)Zigzag scan and
4)Lossless coding
There are many lossless coding techniques. They are Run length encoding, Huffman encoding, Arithmetic encoding, Entropy encoding and so on. Among them, Arithmetic encoding is used in this paper.
1)DCT Image Transform
For image compression, Discrete Cosine Transform (DCT) is used. An input image f(x, y) is a two dimensional M by N matrix image with different intensity values.
To transform spatial to frequency domain for image compression, the system is needed to determine with the forward 2D-DCT transformation equation. The transform matrix is calculated as shown in Equation (1).
(1)
where, i,j = 0,1,2,3,…….., N-1
P(x,y)=input matrix
F(i,j)=transformed matrix.
2) Image Quantization
Quantization is the step where most of the image compression takes place. DCT really does not compress the image because it is almost lossless. For obtaining quantization matrices with other quality levels, scalar multiplications of standard quantization matrix are used. The transformed image matrix by using DCT is divided into the quantization matrix.Values of resultant matrix are then rounded to be the nearest integer value. This formula is shown in Equation (2).
Quantization=round (2)
The compression level of an image can be controlled by a constant, which is generally called the quality factor (Q-factor). The quality levels ranging from 1 to 100 are selected, where 1 gives poorest image quality and highest compression, while 100 gives the best quality and lowest compression. Different JPEG compression programs have different Q-factors. In this proposed system, the performance is shown with different Q factor for the same input image. Luminance quantization matrix Qij is shown in Table I. And then, Chrominance quantization matrix Qi,j is shown in Table II.
TABLE I
Luminance QuantizationTable in JPEG
16 / 11 / 10 / 16 / 24 / 40 / 51 / 6112 / 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 II
Chrominance QuantizationTable in JPEG
17 / 18 / 24 / 47 / 99 / 99 / 99 / 9918 / 21 / 26 / 66 / 99 / 99 / 99 / 99
24 / 26 / 56 / 99 / 99 / 99 / 99 / 99
47 / 66 / 99 / 99 / 99 / 99 / 99 / 99
99 / 99 / 99 / 99 / 99 / 99 / 99 / 99
99 / 99 / 99 / 99 / 99 / 99 / 99 / 99
99 / 99 / 99 / 99 / 99 / 99 / 99 / 99
99 / 99 / 99 / 99 / 99 / 99 / 99 / 99
3)Zigzag Scan
After quantization, the zigzag scan orders 64 coefficients (1 DC and 63 AC coefficients) into the one-dimensional vector format. Zigzag order rearranges the quantized coefficients of each 8x8 block for further encoding. The zigzag path is shown in Figure 1.
136 / 0 / 8 / 6 / 14 / 50 / 27 / 800 / 0 / 7 / 13 / 15 / 26 / 29 / 40
96 / 8 / 12 / 19 / 25 / 30 / 4 / 43
9 / 17 / -18 / 24 / 31 / -76 / 44 / 53
19 / 16 / 23 / 7 / 30 / 0 / 0 / 0
-29 / 2 / -7 / -4 / -6 / 0 / 0 / 0
-45 / -41 / -3 / -2 / 0 / 0 / 0 / 0
-44 / -14 / 0 / 0 / 0 / 0 / 0 / 0
Figure 1.ZigZag Path
136 / 0 / 0 / 96 / 0 / 8 / - / -Arithmetic encoding is used for all coefficients, one AC and 63 DC coefficients.
4)Arithmetic Encoding
Arithmetic coding is based on the concept of interval subdividing.
(i)In arithmetic coding a source ensemble is represented by an interval between 0 and 1 on the real number line.
(ii)Each symbol of the ensemble narrows this interval.
(iii)As the interval becomes smaller, the number of bits needed to specify it grows.
(iv)Arithmetic coding assumes an explicit probabilistic model of the source.
(v) It uses the probabilities of the source messages to successively narrow the interval used to represent the ensemble.
The image datacanbe represented with the interval's two ends [L,H).
L = 0.0, H = 1.0,
R = (H-L)
H = L + R * Q[x]
L = L + R * Q[x-1]
where, R is the interval range. H and L are two ends of the current code interval and then x is the new symbol to be encoded. Q(x) is the probability of symbol x.
The following are the example of arithmetic encoding. Table III depicts the probability and the range of the probability of the symbols between 0 and 1.
TABLE III
Probability and Range Distribution ofSymbols
Symbols / Probability / Range0 / 0.63 / [0,0.63]
2 / 0.11 / [0.63,0.74]
14 / 0.1 / [0.74,0.84]
136 / 0.1 / [0.84,0.94]
222 / 0.06 / [0.94,1.0]
The first symbol for 136 is in the probability range between 0.84 and 0.94.
D. Image Decompression
In the image decompression step, each of the above compression steps is reversed in reverse order.
- Use the arithmetic decoding technique to decode strings of bits into a 64-element array;
- Reform the 64-element array into an 8 × 8 block;
- Multiply each element in the block by a corresponding quantization value;
- Performs the IDCT on the de-quantized block;
- Add 128 to each of the de-transformed pixels to recover an approximation of the original image.
- System Design and Implementation Results
This section describes system design of the proposed system, implementation and performance evaluation.
- Design of the Proposed System
In this paper, Discrete Cosine Transform (DCT) is applied to implement image compression system. The overview of DCT-based image compression system is shown in Figure 2.
Figure 2. Overview of DCT-based Image Compression System
RGB to YCbCr conversion and chrominance down-sampling is conducted in image preprocessing step. This is explained in the background theory. DCT transform, image quantization,zigzag scan and arithmetic encoding are included in image compression system. To get the reconstructed image, image decompression is worked that is the reverse processes of image compression.
- Implementation of the Proposed System
There are two main steps in the image compression system. The first step is image compression and the second step is image decompression. Initially, wecan see implementation oforiginal and compressed images with quality level, Q10is shown inFigure 3. Figure 4 shows the quality level, Q35 of original and compressedimages.
Figure 3. Original and Compressed Museum Imagesat Q 10
Figure 4. Original and Compressed Images Museum at Q 50
This paper uses the two images with the different quality levels. But, in these figures, the performance parameters compression time, compression ratio (CR), MSE and PSNR are not the same.
The original and compressed images at quality level, Q80 is shown in Figure 5. The error image is shown by differencing the original and compressed image. In this figure, the compression time, MSE and PSNR are also calculated.
Figure 5. Original and Compressed Museum Images at Q80
The performance of compression is also researched with Rose image with quality level, Q10. This is shown in Figure 6. And then, the original and compressed Rose images with Q 35 are also shown in Figure 7.
Figure6. Original and Compressed Rose Images at Q 10
Figure7. Original and Compressed Rose Images at Q 35
The Rose image is shown with highest quality level, Q 100 to get the compressed image and to display the error image. This is shown in Figure 8.
Figure8. Original and Compressed Rose Images at Q 100
In this application, two different images are calculated with different quality levels. Although the quality levels are not the same, the performance evaluations are different.
The performance is measured by the parameters such as quality factor (Q-factor), compression ratio (CR), compression time, MSE and PSNR is shown in Table III.
TABLE III
The Performance Comparison of Image Compression System
Input Image / Q-Factor / CR / Compression Time / MSE / PSNR
Museum / Q-10 / 34% / 11.544s / 4.13x10-3 / 71.96
Museum / Q-50 / 26% / 11.609s / 2.57x10-3 / 74.02
Museum / Q-80 / 21% / 11.92s / 3.44x10-5 / 72.77
Rose / Q-10 / 33% / 11.73s / 6.23x10-5 / 90.19
Rose / Q-35 / 26% / 11.94s / 4.58x10-5 / 91.52
Rose / Q-100 / 9% / 12.52s / 1.14x10-5 / 97.55
V. Conclusions
DCT is powerful in image Transform so its breaking fast the images into blocks with summarizing the overall 64 value in DC value perfectly without any errors.The most powerful stage on the Compression system is quantization. An appropriate quantization formula and factors must be chosen. The performances of compression are not the same because of different Q-factors and different images. In this research, the same quality factor of Museum and Rose images has different performances. Using the arithmetic coding, the results may be compared with the above outputs which are implemented by using MATLAB. As the future work, compression of images for storing and transmitting images can be done by other lossless methods of image compression.
Acknowledgment
First and foremost,the author would like to express her thanks to Dr. Nang Aye Aye Htwe, Department of Information Technology, Mandalay Technological University, for her kindness, supports, helpful suggestion, true-line guidance for completion of this paper. The author wishes to express special thanks to Dr. Aung Myint Aye, Associate Professor and Head and her teachers at the Department of Information Technology, Mandalay Technological University, for their encouragement, support and guidance during the theoretical study and thesis preparation duration. Finally, the author wishes to express her parents and family for their kindness, support and generous help rendered to her research days.
REFERENCES
[1]Bheshaj Kumar,Kavita Thakur and G. R. Sinha: Performance Evaluation of Image Compression using Symbol Reduction technique”. Natarajan Meghanathan, et al. (Eds): ITCS, SIP, JSE-2012, CS & IT 04, pp. 217–227, 2012.
[2]JAGADISH H. PUJAR and LOHIT M. KADLASKAR: “A New Lossless Method of Image Compression and Decompression using Huffman Coding Techniques”. Journal of Theoretical and Applied Information Technology, , , (2010).
[3]D.Malarvizhi and Dr.K.Kuppusamy: “A New Entropy Encoding Algorithm for Image Compression using DCT”. International Journal of Engineering Trends and Technology- Volume3Issue3- (2012).
[4]Asadollah Shahbahrami, Ramin Bahrampour, Mobin Sabbaghi Rostami and Mostafa Ayoubi Mobarhanproposed that Evaluation of Huffman and Arithmetic Algorithms for Multimedia Compression Standards
[5]Bilal Kamal Ahmed: “DCT Image Compression by Run-Length and Shift Coding Techniques”. J. of university of Anbar for pure science: Vol.5:NO.3 : (2011).
Ei Ei Phyo,Information Technology, Mandalay Technological University (MTU), (),Mandalay, Myanmar, +95402698215
Nang Aye Aye Htwe, Information Technology, Mandalay Technological University (MTU), (),Mandalay, Myanmar, +955661208