Home / Wavelets / Basic JPEG

# Image Compression:

## How Math Led to the JPEG2000 Standard

#### Basic JPEG

##### Introduction/History

In 1992, JPEG became an international standard for compressing digital still images. The acronym JPEG comes from the Joint Photographic Experts Group. JPEG was formed in the 1980's by members from the International Organization for Standardization (ISO) and the International Telecommunications Union (ITU). According to a 2000 article by Maryline Charrier et. al., over 80% of all images that are transmitted via the internet are stored using the JPEG standard. Despite the popularity of the standard, JPEG members quickly identified some issues with the format and also compiled a list of enhancements that should be included in the next generation of the format. In this section, we will describe a very basic JPEG algorithm, show how it works on an example, discuss the inversion process, and then identify issues and problems with the format.

##### Basic Algorithm
 A digital grayscale image. Fullsize version

The JPEG algorithm has many features that are not covered here. It is our intent to provide a very basic idea of how JPEG can be used to compress a digital still image. There are four basic steps in the algorithm - preprocess, transformation, quantization, encoding. We have already talked about Huffman coding and JPEG uses a more sophisticated version of Huffman coding to perform coding. We will not discuss the advanced coding methods used by JPEG here. Interested readers should consult a refence such as The Data Compression Book. For those readers interested in more details about the mathematics of transformation and quantization, please visit the subsections Discrete Cosine Transformation and Quantization.

To explain the steps of the algorithm, we will use as a running example, the image above. The dimensions of the image 160 x 240 pixels.

### Step 1 - Preprocessing

If we wish to compress a color image in the JPG format, the first step is to convert the red, green, blue color channels to YCbCr space. After that, everything we do for a grayscale image is done to the Y, Cb, and Cr channels.

 Partitioning of the image into 8x8 blocks.

We next partition the image into blocks of size 8 x 8 pixels. Some more work is necessary if the dimensions of our image are not divisible by 8, but for the sake of presentation, we have chosen an image whose dimensions are 160 x 240 = 8*20 x 8*30. So this step creates 20 x 30 = 600 blocks.

Notice that we have highlighted the pixels in block row 4, block column 28. We will use the elements of this matrix to illustrate the mathematics of transformation and quantization steps. An enlargement of this block appears below as well as the 64 pixels intensities that make up the block.

 Enlargement of the example block.

 5 176 193 168 168 170 167 165 6 176 158 172 162 177 168 151 5 167 172 232 158 61 145 214 33 179 169 174 5 5 135 178 8 104 180 178 172 197 188 169 63 5 102 101 160 142 133 139 51 47 63 5 180 191 165 5 49 53 43 5 184 170 168 74 Pixel intensities of the block row 4, block column 28.

The last part of preprocessing the image is to subtract 127 from each pixel intensity in each block. This step centers the intensities about the value 0 and it is done to simple the mathematics of the transformation and quantization steps. For our running example block, here are the new values.

 -122 49 66 41 41 43 40 38 -121 49 31 45 35 50 41 24 -122 40 45 105 31 -66 18 87 -94 52 42 47 -122 -122 8 51 -119 -23 53 51 45 70 61 42 -64 -122 -25 -26 33 15 6 12 -76 -80 -64 -122 53 64 38 -122 -78 -74 -84 -122 57 43 41 -53 Pixel intensity values less 127 in block row 4, block column 28.

### Step 2 - Transformation

The preprocessing has done nothing that will make the coding portion of the algorithm more effective. The transformation step is the key to increasing the coder's effectiveness. The JPEG Image Compression Standard relies on the Discrete Cosine Transformation (DCT) to transform the image. The DCT is a product C = U B U^T where B is an 8 x 8 block from the preprocessed image and U is a special 8 x 8 matrix. More mathematical details about the DCT can be found in the subsection The Discrete Cosine Transformation. Loosely speaking, the DCT tends to push most of the high intensity information (larger values) in the 8 x 8 block to the upper left-hand of C with the remaining values in C taking on relatively small values. The DCT is applied to each 8 x 8 block. The image at left shows the DCT of our highlighted block while the image at right shows the DCT applied to each block of the preprocessed image.

 DCT of the example block. DCT applied to each block. Fullsize version

As you can see, most of the intensities in the discrete cosine transformed image are quite small and at first glance, one might think that the Huffman coding scheme would work very well with the this image. But there are still some problems. Let's have a look at the values (rounded to three digits) of the DCT of our example block:

 -27.500 -213.468 -149.608 -95.281 -103.750 -46.946 -58.717 27.226 168.229 51.611 -21.544 -239.520 -8.238 -24.495 -52.657 -96.621 -27.198 -31.236 -32.278 173.389 -51.141 -56.942 4.002 49.143 30.184 -43.070 -50.473 67.134 -14.115 11.139 71.010 18.039 19.500 8.460 33.589 -53.113 -36.750 2.918 -5.795 -18.387 -70.593 66.878 47.441 -32.614 -8.195 18.132 -22.994 6.631 12.078 -19.127 6.252 -55.157 85.586 -0.603 8.028 11.212 71.152 -38.373 -75.924 29.294 -16.451 -23.436 -4.213 15.624 DCT values in block row 4, block column 28.

The values in the matrix above have been rounded to 3 digits - in truth, most of the values are irrational numbers. Now most computers calculate the values (floating point numbers) to 16 digits (double precision) with the last digit being round-off error. Do you see the problem? The fact that the numbers are computed to 16 digits with round-off error in the last digit means that it is possible for a number to have two different representations! Thus, if we do nothing to modify this situation, the Huffman coding algorithm will not be effective. So the DCT does create a large number of near-zero values, but we need a quantization step to better prepare the data for coding.

### Step 3 - Quantization

The next step in the JPEG algorithm is the quantization step. Here we will make decisions about values in the transformed image - elements near zero will converted to zero and other elements will be shrunk so that their values are closer to zero. All quantized values will then be rounded to integers.

Quantization makes the JPEG algorithm an example of lossy compression. The DCT step is completely invertible - that is, we applied the DCT to each block B by computing C = U B U^T. It turns out we can recover B by the computation B = U^T C U. When we "shrink" values, it is possible to recover them. However, converting small values to 0 and rounding all quantized values are not reversable steps. We forever lose the ability to recover the original image. We perform quantization in order to obtain integer values and to convert a large number of the values to 0. The Huffman coding algorithm will be much more effective with quantized data and the hope is that when we view the compressed image, we haven't given up too much resolution. For applications such as web browsing, the resolution lost in order to gain storage space/transfer speed is acceptable.

Let's have another look at the DCT of our original block and the values that comprise it:

 DCT of the example block.

 -27.500 -213.468 -149.608 -95.281 -103.750 -46.946 -58.717 27.226 168.229 51.611 -21.544 -239.520 -8.238 -24.495 -52.657 -96.621 -27.198 -31.236 -32.278 173.389 -51.141 -56.942 4.002 49.143 30.184 -43.070 -50.473 67.134 -14.115 11.139 71.010 18.039 19.500 8.460 33.589 -53.113 -36.750 2.918 -5.795 -18.387 -70.593 66.878 47.441 -32.614 -8.195 18.132 -22.994 6.631 12.078 -19.127 6.252 -55.157 85.586 -0.603 8.028 11.212 71.152 -38.373 -75.924 29.294 -16.451 -23.436 -4.213 15.624 DCT values in block row 4, block column 28.

The mathematics of quantization is explained in the Quantization subsection. Here is the result of quantization applied to our example block. The image has been enhanced to facilitate viewing of the low intensities.

 Quantized DCT of the example block.

 -2 -19 -15 -6 -4 -1 -1 0 14 4 -2 -13 0 0 -1 -2 -2 -2 -2 7 -1 -1 0 1 2 -3 -2 2 0 0 1 0 1 0 1 -1 -1 0 0 0 -3 2 1 -1 0 0 0 0 0 0 0 -1 1 0 0 0 1 0 -1 0 0 0 0 0 DCT values in block row 4, block column 28.

For comparison purposes, we have plotted the transformed image from above next to the quantized version of the transformed image. The second image has been enhanced to facilitate viewing.

 DCT applied to each block. Fullsize version DCT and quantization applied to each block. Fullsize version

### Step 4 - Encoding

The last step in the JPEG process is to encode the transformed and quantized image. The regular JPEG standard uses an advanced version of Huffman coding. We will use the basic Huffman coding algorithm described in the Compression in a Nutshell section. The original image has dimensions 160 x 240 so that 160*240*8 = 307,200 bits are needed to store it to disk. If we apply Huffman coding to the transformed and quantized version of the image, we need only 85,143 bits to store the image to disk. The compression rate is about 2.217bpp. This represents a savings of over 70% of the original amount of bits needed to store the image!

##### Inverting the Process

The inversion process is quite straightforward. The first step is to decode the Huffman codes to obtain the quantized DCT of the image. In order to undo the shrinking process, elements in each 8x8 block are magnified by the appropriate amount (see the Quantization subsection for more details). At this point we have blocks C^' where the original DCT before quantization is C = U B U^T. We next invert the DCT by computing B^' = U^T C^'U for each block. The last step is to add 127 to each element in each block. The resulting matrix is an approximation to the original image.

The images below shows the original image at left and the JPEG compressed image at right. Recall that the image at right requires over 70% less storage space than that of the original image!

 A digital grayscale image. Fullsize version The compressed grayscale image. Fullsize version

Finally, we compare our example of block row 4, block column 28 with the compressed version of the block.

 Enlargement of the block.

 5 176 193 168 168 170 167 165 6 176 158 172 162 177 168 151 5 167 172 232 158 61 145 214 33 179 169 174 5 5 135 178 8 104 180 178 172 197 188 169 63 5 102 101 160 142 133 139 51 47 63 5 180 191 165 5 49 53 43 5 184 170 168 74 Pixel intensities of the block.
 Enlargement of the compressed block.

 0 172 198 190 149 159 149 179 17 166 131 175 168 195 192 140 12 167 177 255 140 39 123 203 22 178 170 145 1 28 146 187 11 103 183 190 160 207 189 155 60 9 80 103 157 144 115 156 60 48 67 11 176 196 139 19 49 58 47 0 190 168 176 60 Pixel intensities of the compressed block.
##### Issues and Problems

The JPEG Image Compression Standard is a very effective method for compressing digital images, but it does suffer from some problems. One problem is the decoupling that occurs before we apply the DCT - partitioning the image into 8x8 blocks results in the compressed image sometimes appearing "blocky". In the images below, we have zoomed in on the upper right hand corners of the original image and the compressed image. You can see the block artifacts in the compressed image.

 Upper right hand corner of original image. Fullsize version Upper right hand corner of compressed image. Fullsize version

The quantization step makes the JPEG Image Compression Standard an example of lossy compression. For some applications, such as web browsing, the loss of resolution is acceptable. For other applications, such as high resolution photographs for magazine advertisements, the loss of resolution is unacceptable.

As you will see in the Features/Enhancements subsection of the JPEG2000 section, researchers have found a better transformation and quantization methods to address the problems encountered by the JPEG standard.

 Wavelets and JPEG2000 Home Digital Image Basics Compression in a Nutshell Basic JPEG Wavelet Transformations JPEG2000 Features/Enhancements Quantization References and Links