Image Compression:
How Math Led to the JPEG2000 Standard
Quantization
The Discrete Cosine Transformation (DCT) maps the preprocessed 8 x 8 blocks of a digital image to a setting that is more amenable to the coding portion of the image compression algorithm. The reason the DCT is an effective tool in the compression algorithm is that it takes (near) constant blocks and transforms them to new blocks where most of the values are (near) zero. Unfortunately, the elements of the DCT matrix are irrational numbers and the input intensites are integer-valued, so that the output values are typically real-valued. The coding method works best if the output are integer-valued. In order to produce integer-valued output, a quantization step is added to the JPEG algorithm.
Let's use the test block (preprocessed) from the Basic JPEG section as a running example to illustrate how JPEG quantization works. The preprocessed block is given below:
|
A = \left[\matrix{
-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 }\right]
|
Pixel intensity values less 127.
|
The DCT (rounded to two decimal places) of the block is given below. Note that nearly all the values are non-integers.
|
B = \left[\matrix{-27.50 & -213.47 & -149.61 & -95.28 & -103.75 & -46.95 & -58.72 & 27.23 \\ 168.23 & 51.61 & -21.54 & -239.52 & -8.24 & -24.50 & -52.66 & -96.62 \\ -27.20 & -31.24 & -32.28 & 173.39 & -51.14 & -56.94 & 4.00 & 49.14 \\ 30.18 & -43.07 & -50.47 & 67.13 & -14.12 & 11.14 & 71.01 & 18.04 \\ 19.50 & 8.46 & 33.59 & -53.11 & -36.75 & 2.92 & -5.80 & -18.39 \\ -70.59 & 66.88 & 47.44 & -32.61 & -8.20 & 18.13 & -22.99 & 6.63 \\ 12.08 & -19.13 & 6.25 & -55.16 & 85.59 & -0.60 & 8.03 & 11.21 \\ 71.15 & -38.37 & -75.92 & 29.29 & -16.45 & -23.44 & -4.21 & 15.62
}\right]
|
|
|
To quantize the above block, the JPEG algorithm first divides each element by a prescribed value and then rounds the result to produce integers. The values that are used in the element-wise division step are given in matrix Z below:
|
Z = \left[\matrix{16 & 11 & 10 & 16 & 24 & 40 & 51 & 61 \\ 12 & 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
}\right]
|
The values used for element-wise division.
|
We create the new matrix Q whose elements are q_{jk} = R(b_{jk}/z_{jk}) for j,k = 1, \ldots, 8. Here, R(\cdot ) is the rounding function. Note that the values are largest in the lower right corner of Z. These divides should produce values close to zero so that the rounding function will convert the quotient to zero.
Here are the values for Q for our running example block:
|
Q = \left[\matrix{ -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
}\right]
|
|
|
Note that while the DCT is invertible and the element-wise division is reversible, the rounding step cannot be undone. Thus JPEG is an example of lossy compression. Each block in the image is quantized in this way and these integers are sent to the coding portion of the algorithm. In general, a large number of the quantized values are zero.
Reversing the Process
To reverse the process and obtain an approximation to the original preprocessed block A, we reverse the division step and apply the inverse DCT. That is, we first form matrix B^' whose elements are defined by b^'_{jk} = q_{jk}*z_{jk}. Note that the the values of B^' below are a bit different than the corresponding values in B.
|
B^' = \left[\matrix{-32 & -209 & -150 & -96 & -96 & -40 & -51 & 0 \\ 168 & 48 & -28 & -247 & 0 & 0 & -60 & -110 \\ -28 & -26 & -32 & 168 & -40 & -57 & 0 & 56 \\ 28 & -51 & -44 & 58 & 0 & 0 & 80 & 0 \\ 18 & 0 & 37 & -56 & -68 & 0 & 0 & 0 \\ -72 & 70 & 55 & -64 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & -87 & 103 & 0 & 0 & 0 \\ 72 & 0 & -95 & 0 & 0 & 0 & 0 & 0
}\right]
|
Reversing the division step.
|
We then obtain an approximation to A by computing the inverse DCT. We have A^' = U^T B^' U. The matrix A is also displayed below so that you can see the loss in resolution.
|
A^' = \left[\matrix{-128 & 45 & 71 & 63 & 22 & 32 & 22 & 52 \\ -110 & 39 & 4 & 48 & 41 & 68 & 65 & 13 \\ -115 & 40 & 50 & 152 & 13 & -88 & -4 & 76 \\ -105 & 51 & 43 & 18 & -126 & -99 & 19 & 60 \\ -116 & -24 & 56 & 63 & 33 & 80 & 62 & 28 \\ -67 & -118 & -47 & -24 & 30 & 17 & -12 & 29 \\ -67 & -79 & -60 & -116 & 49 & 69 & 12 & -108 \\ -78 & -69 & -80 & -138 & 63 & 41 & 49 & -67
}\right]
|
Application of the inverse DCT to the quantized block.
|
|
A = \left[\matrix{
-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 }\right]
|
The original preprocessed block.
|
