Image Compression:
How Math Led to the JPEG2000 Standard
JPEG2000 Quantization
There are two types of quantization options for the JPEG2000 standard. Both types require the construction of quantization step sizes that are used to determine whether or not a given element from the wavelet transformation is either shrunk closer to zero or simply converted to 0. For explicit quantization, the user supplies all step sizes. Formulas for compute the necessary step sizes are used with implicit quantization - we will describe implicit quantization in this subsection.
The Quantization Function
JPEG2000 quantization makes use of the following quantization function:
q(t) = \mathop{\rm sgn}(t) \lfloor\, |\, t\, |/d \,\rfloor
| |
|
|
| |
|
The function |\, t\, | /d
|
where d > 0 is the quantization step size. Let's have a closer look at how this function works. We start by taking the absolute value of the input value t and dividing it by positive d. If you remember the plot of f(t) = |\, t \, |, then you will agree that dividing by d simply changes the slope of the two linear pieces from \pm 1 to \pm 1/d. We have plotted |\, t\, | / d in the figure at right.
| |
|
|
|
| |
|
The function \lfloor \,|\, t\, | /d\, \rfloor
|
|
The next step in constructing q(t) is to apply the floor function, \lfloor \, \cdot \, \rfloor to each value in the preceding plot. The floor function converts a given value t to the largest integer less than or equal to t. Note that for values of t in the interval (-d, d), the value of |\, t\, |/d are nonnegative and less than one, so the floor function converts them to zero. Values in the intervals [d, 2d) and (-2d,-d] are converted to one - in general, values in the intervals [md, (m+1)d) and (-(m+1)d, -md] where m is any positive integer, are converted to m. The graph at left illustrates the effects of the floor function.
| |
|
|
|
| |
|
The function q(t) = \mathop{\rm sgn}(t) \lfloor \,|\, t\, | /d\, \rfloor
|
|
The last step in the construction of the quantization is to attach the original sign of the input value to the floored value. We do this using the sign function - \mathop{\rm sgn}(t) returns 1 if t > 0, 0 if t = 0, and -1 if t < 0. The effect of multiplying the values of the image above by \mathop{\rm sgn}(t) simply negates the values in the second quadrant.
As an example, let's take d = 2 and apply the quantization function to the vector
\left[ 3, -2.1, 0.8, -0.4, -6, 4, 9, 10\right]
The result is
\left[ 1, -1, 0, 0, -3, 2, 4, 5\right].
Applying the Quantization Function to the DWT
The JPEG2000 Image Compression Standard calls for an application of the Discrete Wavelet Transformation to the preprocessed image. In the example below, we have applied three iterations of the DWT using the LeGall filter. The resulting image consists of 1 blur + 9 details = 10 blocks. In general, if we compute i iterations of the DWT, we create 1 blur + 3*i details = 3*i + 1 blocks.
| |
|
|
|
|
|
| |
|
|
|
|
Three iterations of the DWT
|
JPEG2000 performs quantization by applying the quantization function to each of the blocks of the DWT. A different quantization step size is computed for each block. Each quantization step size makes use of the base step size \tau. This value is defined as
\tau = 2^{R-c+i}\left( 1 +f/2^{11}\right)
Where R is the number of bits needed to represent the original intensities, i is the number of iterations of the DWT, and c, f are the number of bits used to represent the exponent and mantissa, respectively of the blur portion of the DWT. We take R = 8, i = 3, c = 8.5, and f = 8 (see Digital Image Processing, 3rd Edition for more details) to obtain
\tau = 2^{8-8.5+3}\left( 1 + 8/2^{11}\right) = 2^{2.5}\cdot 1.00390625 \approx 5.678951
For the blur portion of the transform, we use the quantization step size d = \tau/2^i = \tau/8 \approx 0.709869. For the detail blocks, we take d = \tau/2^{k-1} for the vertical and horizontal blocks, and d = \tau/2^(k-2) for the vertical blocks. Here, k = 1, \ldots, i.
For our example, the first iteration would use d \approx 5.678951 for the first iteration vertical and horizontal detail blocks and d \approx 11.357903 for the first iteration diagonal block. The quantization step sizes for the second iteration are 2.839476, 5.678951 for the vertical/horizontal and diagonal blocks, respectively. The quantization step sizes for the third iteration are 1.419738, 0.709869 for the vertical/horizontal and diagonal blocks, respectively. Note the quantization steps sizes decrease as the iteration value increases. Note that the last vertical block and the blur block use quantization step size 0.709869 < 1. Dividing by this number actually increases values in these blocks.
