JPEG-Like Image Compression, Part 2

In last month's installment of this two-part article, I described the basic techniques, algorithms, and vocabulary of JPEG image compression. In particular, I examined the concepts of discrete-cosine transforms, frequency-coefficient quantization, Huffman encoding, color-space conversion, and image subsampling. I also presented the various considerations which influenced the implementation of an image-compression technique called "CAL" (my initials), which implements the same algorithms as JPEG, but encapsulates the images in a simple, proprietary file format. This month, I'll focus on CAL and how it differs from JPEG, then present the C++ classes on which CAL is built.

CAL differs from JPEG in that it provides only a partial subset of the overall functionality described in the JPEG specification. In particular, CAL:

• Supports only the baseline-sequential mode of operation.
• Supports only Huffman encoding for entropy coding.
• Uses the default, static Huffman tables from the JPEG specification for encoding/decoding of images.
• Does not carry any Huffman code tables or symbol tables within the encoded CAL image when it is stored in a file.
• Uses a simple file format.
• Supports only 8-bit gray-scale and 24-bit RGB true-color images.

JPEG and CAL differ greatly in the file format in which they store compressed images. JPEG images are stored in JFIF or TIFF formats, whereas CAL images are stored in a simple file format.

The CAL file format is simple because the format of compressed images is fixed. In contrast, the JPEG specification allows for many different image formats. The specification supports a varying number of image components, a variety of color spaces, and various subsampling factors, in addition to custom Huffman tables. To enable this kind of flexibility, the JPEG file formats, by necessity, must be more complex.

An object of the ExpandCALImage class is used to expand a previously compressed CAL image file. The single constructor for ExpandCALImage requires a filename of a CAL image as its parameter. One of the first operations performed within the constructor is the creation of a Huffman class object for file I/O and Huffman decoding. The new Huffman object first reads in the header of the specified image file. To verify that the specified file does indeed contain a CAL image, the CALFileTag entry in the file header is checked for the letters "CL." If the file contains a CAL image, a block of memory is allocated to store the image as it is expanded; the block size is specified in the file header. Next, an instance of the BufferManager class is created for managing the decoded image data. The BufferManager, in conjunction with the ColorConvert class it spawns, handles YCbCr-to-RGB color conversion on the expanded image data as the image is made available. Finally, the quantization tables are initialized to the quality factor specified in the image file header, and the variables used in the DC-coefficient difference calculations are initialized to 0. If all operations performed in the constructor are successful, the class variable ErrorCode is set to a no-error indication. Many member functions of this class check ErrorCode for the no-error indication before proceeding with execution.

The only purpose of the destructor for ExpandCALImage is to free the Huffman and BufferManager objects along with the memory allocated for the image by the constructor.

The ExpandImage member function expands images by organizing calls to functions in other classes that perform the expansion process. The expansion process is entirely driven by information contained in the CAL file header. Specifically, the header tells the code the number of MCUs in the image, and how many blocks make up each MCU. Since CAL uses a fixed subsampling mechanism, the content of a block in an MCU can be determined by the block number. This is important because Y blocks must be processed differently than either Cb or Cr blocks. For gray-scale images, there are four blocks in an MCU numbered 0..3 and they all contain Y information. For true-color image, there are six blocks in an MCU numbered 0..5. Blocks 0..3 contain Y information, block 4 contains Cb information, and block 5 contains Cr information. A switch statement determines how to process each block.

All Y blocks are processed in exactly the same fashion. First, the Huffman-encoded frequency coefficients must be decoded from the bit stream by a call to the DecodeBlock function. Notice that DecodeBlock is instructed to use the luminance tables for decoding Y data. With the block decoded, the actual value of the DC coefficient for the block can be calculated from the decoded value and the previous DC-coefficient value stored in the class object. The new value of the DC coefficient is stored for use by the next block of Y data. The next step is to subject the decoded frequency-coefficient data to dequantization with a call to QuantizeBlock. Here, too, the function is told to use the luminance dequantization table on the Y data block and to perform the DEQUANT operation.

Operations on the Cb and Cr chrominance blocks are very similar to those performed on the Y block with the exception that chrominance tables are used in place of the luminance table for decoding and dequantizing the data. Also, the DC-coefficient calculations are performed independently for the Cb and Cr blocks.

After either a luminance or chrominance block is decoded, it is subjected to an inverse zigzag reordering that places the ordered frequency-coefficient values back into pixel order. This done, the data is processed by an inverse cosine transform to retrieve the pixel data from the frequency data. The PutNextBlock function in the BufferManager class object is finally called to store the recovered pixel values back into the image buffer (after color conversion to RGB, of course).

The Huffman object's FlushInputStream member function is called between processing MCUs of image data. Remember, each MCU is separate and is padded to a byte boundary by the addition of 1 bits to the data stream. At the conclusion of MCU processing, the FlushInputStream function resets the Huffman-decoding software for processing the next MCU of data. This properly disposes of any padding bits added to the bit stream.

The processing of compressed image-data blocks continues until there are no more blocks to process. At that time ExpandImage returns a True, indicating success.

After the image-expansion process completes successfully, the ExpandCALImage object contains the image in memory (in DIB format). The application software can then poll the object for the image parameters and data.

CAL image compression is handled by an object of the CompressCALImage class. The constructor for CompressCALImage is passed the following:

• A filename to be given the compressed image.
• An indication of whether the image is gray scale or true color.
• A pointer to the image data in memory.
• A pointer to the image palette in memory (if required).
• The dimensions of the image in pixels.
• The number of bits per pixel for the image.
• The number of colors considered important for the image.
• A quality-factor compression control.

The CompressCALImage constructor first creates a Huffman object for file I/O and a BufferManager class object for extraction of pixel data from the image being compressed. After these objects are instantiated, the header structure within the class is filled with appropriate image information. Next, the quantization tables are initialized by a call to SetQuality. The quantization tables are parameterized using the quality factor passed in as a parameter to the constructor. Finally, the previous DC-coefficient variables are set to 0 so that they can be used to encode DC-coefficient differences instead of absolute values. The destructor for the CompressCALImage is simple; it serves only to delete the Huffman and the BufferManager class objects, as they aren't needed by the time the destructor runs.

Image compression occurs when CompressImage is called. After checking if the initialization performed within the class constructor was successful, the header (filled in by the constructor) is written to the output file. Following this, two nested loops control the compression process. The outer loop is traversed for each MCU in the image, and the inner loop is traversed for each block of each MCU. Image compression proceeds in reverse order from image expansion. First, a call to GetNextBlock retrieves the next block of image data. The block number to be fetched is passed to this function as a parameter. A block number of 0..3 will fetch a Y block, a block number of 4 will fetch a Cb block, and a block number of 5 will fetch a Cr block. Because gray-scale images have only four blocks per MCU, blocks of nonexistent CB or Cr data will never be fetched. True-color images, however, utilize all block varieties.

After a block of image data is fetched, it undergoes discrete cosine transformation, followed by a forward zigzag. The frequency coefficients are then in the proper, increasing-frequency order for the quantization and encoding processes. The processing that follows depends upon the type of block, which is determined by the block number. Block numbers 0..3 of Y data are forward quantized with luminance-quantization tables. The difference in DC-coefficient value replaces the DC coefficient in the data block, whereupon EncodeBlock encodes the luminance data. Chrominance data is handled in a similar fashion, except chrominance tables are used for quantization and Huffman encoding. When a complete MCU of data has been processed, the Huffman data stream is flushed (padded with 1s) and processing begins on the next MCU. When there are no more MCUs to process, the CAL file is closed with a call to CloseFile. A Boolean True is returned if image compression was successful.

During image compression, the buffer manager breaks up an image into blocks appropriate for compression. Conversely, during image expansion, the buffer manager reconstructs an image from blocks of data passed to it. The buffer manager manages four internal buffers (Y1, Y2, Cb, and Cr) when true-color images are processed and just two buffers (Y1 and Y2) for gray-scale images. These buffers can accommodate 16 rows of full-width image data, which are necessary to support the two-dimensional 4:2:2 subsampling performed on the image's chrominance components. Because of the subsampling, each 16x16 group of pixels in a true-color image results in four Y blocks and one block each of Cb and Cr. Each 16x16 group of pixels in a gray-scale image results in four Y blocks only.

During image compression, BufferManager reads 16 rows of image data at a time from the DIB image pointed to in memory, calls upon a ColorConvert class object to convert the RGB data to YCbCr, and then stores the converted data in its internal buffers. Every call to GetNextBlock retrieves a block of data from the buffer identified by the requested block number. Blocks 0 and 1 are fetched from Y1; blocks 2 and 3, from Y2; block 4, from Cb; and block 5, from the Cr buffer. When there is no more data in the buffers, the next 16 rows of image data are read in and the process repeats.

During image expansion, a call to PutNextBlock places a block of image data into the buffer identified by the specified block number. Block numbers 0 and 1 are stored in the Y1 buffer; block numbers 2 and 3, in the Y2 buffer; block number 4, in the Cb buffer; and block number 5, in the Cr buffer. When PutNextBlock is called and the internal buffers are full, 16 rows of data will be retrieved from the buffers, converted back to RGB format, and stored in the memory allocated for the image at the appropriate location (determined by the row number).

The ColorConvert class is also complex because it converts colors using scaled long integers instead of the more traditional floating-point numbers. This was done for performance. (Refer to last month's installment for the equations used for RGB-to-YCbCr color-space conversions.) Note that all of the possible terms in the color equations in the ColorConvert code are precomputed within the class constructor, so only array lookups and adds are necessary when the code needs to convert colors. This was also done to enhance performance. It's also important to offset the Cb and Cr values that occupy the range -0.5 to +0.5 when the scale is from 0.0 to 1.0 so that they reside in the range of byte values from 0 to 255. This is done by setting the value of 0 at code 127. Chrominance values above 127 are then considered positive, and values below 127 are negative. The code for the ColorConvert class (see color.hpp and color.cpp) shows how this offset is managed, how the 2-D chrominance subsampling is performed, and how long integers and scaling are used in place of floating-point numbers during the color calculations.

JPEG compression is no more than the logical application of various image-processing algorithms to image data. As CAL illustrates, when JPEG compression is broken down into its constituent algorithms, the pieces are easily understood.

typedef struct {
WORD   StructureSize;   // Size of structure for version control
WORD   CALFileTag;      // Tag should be "CL"
IMAGETYPE ImageType;    // Type of image - gray scale or true color
WORD   ImageWidth;      // Image width in pixels
WORD   ImageHeight;     // Image height in pixels
DWORD  RasterSize;      // DIB raster size including padding
WORD   BitsPerPixel;    // Number of bits per pixel for the image.
                       // 8 for gray scale and 24 for true color images
WORD   NumberOfColors;  // Number of important colors in image usually 256 for
                       // gray scale images and always 0 for true color images
WORD   QualityFactor;   // Quality factor image compressed with. Range 10..100
WORD   NumberOfMCUs;    // Total number of MCUs in image
WORD   BlocksPerMCU;    // Number of blocks in a single MCU.
                      // 4 for gray scale and 6 for true color images
RGBCOLOR Palette[256];  // Palettefor image display. Required only for gray scale images
DWORD  Unused1;         // Whatever you want you can put here
} CALFILEHEADER;

CompressCALImage *C;    // Create an instance of class for CAL compression
ExpandCALImage *E;      // Create an instance of class for CAL expansion
// Attempt to compress a CAL image from a true color DIB image in memory
// Parameter passed to instance of CompressCALImage object refer to image
// in memory. Quality factor of 50 used.
C = new CompressCALImage("cal50.cal", TRUECOLORTYPE,
            Ptr to DIB data, NULL,
            ImageWidth, ImageHeight,
            24, 0, 50);
// Now compress the image
C->CompressImage();
delete C;              // Compression object is no longer needed
// Now attempt to expand the previously compressed CAL image
E = new ExpandCALImage("cal50.cal");
// Now expand the image
E->ExpandImage();
// At the conclusion of image expansion, the E object contains the DIB image and its
// associated specifications.Make sure to copy the image data out of the E object before
// the object is deleted otherwise the image will be destroyed as well as the object.
BYTE huge *lpImage = E->GetDataPtr(); // Get ptr to DIB image data
WORD ImageWidth  = E->GetWidth();
WORD ImageHeight = E->GetHeight();
// Process and/or display the image here
delete E;              // Delete object when it and the image are no longer needed

Copyright © 1995, Dr. Dobb's Journal