Image Compression:
How Math Led to the JPEG2000 Standard
JPEG2000
Introduction/History
In 1997, the Joint Photographic Experts Group (JPEG) began work on the next version of the JPEG Image Compression Standard. Members of the group had identified some problems with the original JPEG standard as well compiled a "wish list" of new features and enhancements the next version of the standard should possess. The new standard was named the JPEG2000 Image Compression Standard.
Many of the features and enhancements of JPEG2000 are described in the subsection Features/Enhancements as well as the problems of the original standard that were addressed by JPEG2000. The mathematics behind the Discrete Wavelet Transformation used in JPEG2000 is described in the Wavelet Transformations section and the subsection Quantization gives more information about the quantization process in lossy JPEG2000 compression. The goal of this section is to describe a very basic algorithm for performing JPEG2000 compression on a digital grayscale image.
Basic Algorithm
Like JPEG, the JPEG2000 Image Compression Standard consists of four basic steps in the algorithm - preprocess, transformation, quantization, encoding. Unlike JPEG, the quantization step is optional if the user wishes to perform lossless compression. Where JPEG uses an advanced version of Huffman coding, JPEG2000 utilizes a new coding method called Embedded Block Coding with Optimized Truncation (EBCOT). We will not discuss EBCOTon this site - interested readers should consult the book by Taubman and Marcellin.
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
The only preprocessing step we will use is the centering of the grayscale intensity values. Towards this end, we subtract 127 from each intensity value in the image matrix. If we were compressing a color image, we would first convert to YCbCr space and then center each of the Y, Cb, and Cr channels.
Step 2 - Transformation
One of the major changes in the JPEG2000 standard is the use of the Discrete Wavelet Transformation (DWT) instead of the DCT. If we are performing lossy compression, we use the DWT with the CDF97 filter. For lossless compression, we use the DWT in conjunction with the LeGall53 filter and perform the computation using the lifting method due to Wim Sweldens. In both cases, we compute 2-3 iterations of the DWT. In our example, we compute two iterations of each transformation.
Step 3 - Quantization
If we are performing lossless compression, the DWT pictured above right is encoded and the algorithm is concluded. For lossy compression, JPEG2000 employs a quantization scheme somewhat similar to that used by JPEG on the 8 x 8 blocks. For two iterations, the DWT creates seven blocks and each of these blocks are quantized separately. Values in each block are either moved closer to zero or converted to zero and then converted to an integer via the floor function. More details regarding the quantization process can be found in the Quantization subsection. The result for our running example is displayed at right.
Step 4 - Encoding
For the final step in the compression standard, we use Embedded Block Coding with Optimized Truncation. We do not cover the EBCOT method here.
For lossless compression, we simply use EBCOT to code the elements of the wavelet transformation constructed with the LeGall filter. In this case, we can store the image using 215,544 bits. The original image, in raw format, requires 307,200 bits of storage so the lossless method represents a savings of about 30%. The compression rate is 5.6bpp.
For lossy compression, EBCOT allows us to use only 84,504 bits as opposed to the original size of 160*240*8 = 307,200 bits. The compression rate is about 2.2bpp. If we compress the same image using JPEG, we need 103,944 bits for a compression rate of 2.7bpp. The original image, the JPEG2000-compressed image, and the JPEG-compressed image are plotted below.
The images below show the upper left-hand corners of each of the above images. You will see blocky artifacts in the JPEG corner that do not appear in the JPEG2000 corner.
