Quantization

Figure 11.3 shows the JPEG compression process as a three-step procedure, the first step being a DCT transformation. DCT is a lossless transformation that doesn’t actually perform compression. It prepares for the “lossy,” or quantization, stage of the process.

The DCT output matrix takes more space to store than the original matrix of pixels. The input to the DCT function consists of eight-bit pixel values, but the values that come out can range from a low of -1,024 to a high of 1,023, occupying eleven bits. Something drastic needs to happen before the DCT matrix can take up less space.

The “drastic” action used to reduce the number of bits required for storage of the DCT matrix is referred to as “Quantization.” Quantization is simply the process of reducing the number of bits needed to store an integer value by reducing the precision of the integer. Once a DCT image has been compressed, we can generally reduce the precision of the coefficients more and more as we move away from the DC coefficient at the origin. The farther away are from 0,0, the less the element contributes to the graphical image, so the less we care about maintaining rigorous precision in its value.

The JPEG algorithm implements Quantization using a Quantization matrix. For every element position in the DCT matrix, a corresponding value in the quantization matrix gives a quantum value. The quantum value indicates what the step size is going to be for that element in the compressed rendition of the picture, with values ranging from one to 255.

The elements that matter most to the picture will be encoded with a small step size, size 1 offering the most precision. Values can become higher as we move away from the origin. The actual formula for quantization is quite simple:

                         DCT(i,j)
Quantized Value(i,j) = -------------- Rounded to nearest integer
                       Quantum(i,j)

From the formula, it becomes clear that quantization values above twenty-five or perhaps fifty assure that virtually all higher-frequency components will be rounded down to zero. Only if the high-frequency coefficients get up to unusually large values will they be encoded as non-zero values.

During decoding, the dequantization formula operates in reverse:

DCT(i,j) = Quantized Value(i,j) * Quantum(i,j)

Once again, from this we can see that when you use large quantum values, you run the risk of generating large errors in the DCT output during dequantization. Fortunately, errors generated in the high-frequency components during dequantization normally don’t have a serious effect on picture quality.

Selecting a Quantization Matrix

Clearly an enormous number of schemes could be used to define values in the quantization matrix. At least two experimental approaches can test different quantization schemes. One measures the mathematical error found between an input and output image after it has been decompressed, trying to determine an acceptable level of error. A second approach tries to judge the effect of decompression on the human eye, which may not always correspond exactly with mathematical differences in error levels.

Since the quantization matrix can obviously be defined a runtime when compression takes place, JPEG allows for the use of any quantization matrix; however, the ISO has developed a standard set of quantization values supplied for use by implementers of JPEG code. These tables are based on extensive testing by members of the JPEG committee, and they provide a good baseline for established levels of compression.

One nice feature about selecting quantization matrices at runtime is that it is quite simple to “dial in” a picture quality value when compressing graphics using the JPEG algorithm. By choosing extraordinarily high step sizes for most DCT coefficients, we get excellent compression ratios and poor picture quality. By choosing cautiously low step sizes, compression ratios will begin to slip to not so impressive levels, but picture quality should be excellent. This allows for a great deal of flexibility for the user of JPEG code, choosing picture quality based on both imaging requirements and storage capacity.

The quantization tables used in the test code supplied with this program are created using a very simple algorithm. To determine the value of the quantum step sizes, the user inputs a single “quality factor” which should range from one to about twenty-five. Values larger than twenty-five would work, but picture quality has degraded far enough at quality level 25 to make going any farther an exercise in futility.

 for ( i = 0 ; i < N ; i++ )
   for ( j = 0 ; j < N ; j++ )
     Quantum[ i ][ j ] = 1 + ( ( 1 + i + j ) * quality );

The quality level sets the difference between adjoining bands of the same quantization level. These bands are oriented on diagonal lines across the matrix, so quantization levels of the same value are all roughly the same distance from the origin. An example of what the quantization matrix looks like with a quality factor of two follows:

Figure 11.10  The matrix at quality factor 2.

As a result of this configuration, the DCT coefficient at 7,7 would have to reach a value of sixteen to be encoded as a value other than zero. This sets the threshold for the value of an element before it is going to contribute any meaningful information to the picture. Any contribution under the value of this threshold is simply thrown out. This is the exact point in the algorithm where the “lossy” effect takes place. The first DCT step is lossless except for minor mathematical precision loss. And the step following quantization is a lossless encoding step. So this is the only place where we get a chance to actually discard data.

Figure 11.11 shows the effects of quantization on a DCT matrix. The quantization matrix shown in the previous figure was applied to this block of DCT, which comes from the first block of test file CHEETAH.GS. The quantization/dequantization cycle has readily apparent effects. The high-frequency portions of the matrix have for the most part been truncated down to zero, eliminating their effect on the decompressed image. The coefficients in the matrix that are close to the DC coefficient may have been modified, but only by small amounts.

Figure 11.11  The effects of quantization.

The interesting thing is that while we appear to be making wholesale changes to the saved image, quality factor 2 makes only minor changes that are barely noticeable. Yet the clearing of so many of the coefficients allows the image to be compressed by 60 percent, even in the very simple compression program used in this chapter.