IntroductionCompressionDecompressionExampleIntroductionCompressionDecompressionExampleHome PageTitle PageJJ IIJ IPage 1 of 8Go BackFull ScreenCloseQuitUsing JPEG to Compress Still PicturesTyler GenterDecember 17, 2010IntroductionCompressionDecompressionExampleHome PageTitle PageJJ IIJ IPage 1 of 8Go BackFull ScreenCloseQuitAbstractJPEG can be used to compress digital images taken of real-life scenes. It uses less disk spaceto store the image by discarding less important information contained in the images.IntroductionCompressionDecompressionExampleHome PageTitle PageJJ IIJ IPage 1 of 8Go BackFull ScreenCloseQuitIntroductionMore and more people have access to personal computers, mp3 players, and internet devicestoday. The price of memory has also dropped exponentially in the last 30 years. However, digitalpictures in their raw form still use up relatively large amounts of memory. As a result, manypeople have been interested in reducing the size of digital pictures without loosing quality. Thishas resulted in the Joint Photograph Experts Group creating a standard, called JPEG. JPEGexploits the fact that many images are from an analogue source to reduce the size of images.As a result, it achieves better compression ratios than other image compression algorithms likethe Graphics Interchange Format or generic algorithms like pkzip or bzip2.CompressionA picture (when digitized on a computer) can be seen as a large matrix, with each entrycontaining a pixel. Each pixel represents a single point of the image, and is typically encodedas red, green and blue. That is, each pixel describes how much red, green, and blue light arecombined together to make the color at that point.The first step in JPEG is to split this large matrix up into multiple blocks, each 8 by 8.Each of these smaller matrices is then compressed individually. First the 8 by 8 matrix is splitinto 3 matrices. Each red, green, and blue pixel is converted to luminance and chrominance,Y’, CB, and CR. Y’ contains the luminance, how bright the pixel is at that point. CBand CRcontain how much blue and red the pixel contains, respectively.At this point, each 8 by 8 matrix, B is looked at individually. Each pixel is represented byan 8 bit unsigned value, with range [0, 255]. The matrix f is formed by subtracting 128 fromeach pixel,f = B − 128 (1)Now every entry in f is a signed 8 bit integer, with range [−128, 127]. The matrix still representsthe picture in the location domain; that is, the position and values of the entries directlycorrespond to the value of the pixel at that location.The matrix f is then converted to the frequency domain, F , using the discrete cosine trans-form (DCT). The data in the rows and columns vary as you go across and down the originalIntroductionCompressionDecompressionExampleHome PageTitle PageJJ IIJ IPage 2 of 8Go BackFull ScreenCloseQuitmatrix. The data can be seen as a sum of cosine functions, of different amplitudes and frequen-cies. After the DCT, the entries in the matrix are the amplitudes of these cosine functions.The location of the amplitudes is the frequency, with frequency increasing as you go across anddown. The entries in the lower right represent the amplitude of higher frequency fluctuationsin the original pixels. However, pictures of natural scenes have few sharp, crisp edges, so thisinformation is less important. This is key for JPEG to reduce memory usage.The JPEG standard defines a function to convert f to F (from location domain to frequencydomain):F (u, v) =14C(u)C(v)"7Xx=07Xy =0f(x, y) cos(2x + 1)uπ16cos(2y + 1)vπ16#(2)whereC(u), C(v) = 1/√2 for u, v = 0C(u), C(v) = 1 otherwise.However, JPEG compression is pretty much always performed on a computer, where speedand power usage are important. It turns out that it is possible to construct a matrix, T , thatperforms the discrete cosine transform. The equation is:F = T fTT(3)where T is the discrete cosine transform matrix, f is the matrix to be converted, and F is theresulting transformed matrix. T is an 8 by 8 matrix, where every element tmnbelongs to rowm, column n:t1n=r18tmn=r14cosπ(2n − 1)(m − 1)16(4)The result is:IntroductionCompressionDecompressionExampleHome PageTitle PageJJ IIJ IPage 3 of 8Go BackFull ScreenCloseQuitT =0.3536 0.3536 0.3536 0.3536 0.3536 0.3536 0.3536 0.35360.4904 0.4157 0.2778 0.0975 −0.0975 −0.2778 −0.4157 −0.49040.4619 0.1913 −0.1913 −0.4619 −0.4619 −0.1913 0.1913 0.46190.4157 −0.0975 −0.4904 −0.2778 0.2778 0.4904 0.0975 −0.41570.3536 −0.3536 −0.3536 0.3536 0.3536 −0.3536 −0.3536 0.35360.2778 −0.4904 0.0975 0.4157 −0.4157 −0.0975 0.4904 −0.27780.1913 −0.4619 0.4619 −0.1913 −0.1913 0.4619 −0.4619 0.19130.0975 −0.2778 0.4157 −0.4904 0.4904 −0.4157 0.2778 −0.0975(5)This is a huge optimization for performing the transform. Cosine only needs to be calculated56 times for an infinite number of pictures, compared to 128 times for every matrix when using(2), of which there are thousands of in a typical picture. Multiplication is a relatively slowoperation on most processors, and calculating cosine is even slower.Every entry in the matrix F is then divided by the entry in the same location in a quanti-zation matrix and rounded to the nearest integer:FQ(u, v) = Integer RoundF (u, v)Q(u, v)(6)The quantization matrix has the property that the entries in the lower right are larger. Thismeans that in the resulting matrix, the entries in the lower right are most likely zero. Theseentries are less important, as explained above, so it is less important to keep them.A sample quantization matrix from the JPEG standard is:Q =16 11 10 16 24 40 51 6112 12 14 19 26 58 60 5514 13 16 24 40 57 69 5614 17 22 29 51 87 80 6218 22 37 56 68 109 103 7724 35 55 64 81 104 113 9249 64 78 87 103 121 120 10172 92 95 98 112 100 103 99(7)IntroductionCompressionDecompressionExampleHome PageTitle PageJJ IIJ IPage 4 of 8Go BackFull ScreenCloseQuitHowever, the compressor can choose its own quantization matrix to use.The entries of the resulting matrix are then written to disk in a zig-zag pattern using HuffmanCoding. More common entries in the matrix take up less space on the disk. Many of the entriesin FQare zero, especially in the lower right, and this is also used to save space when writingthe image to