Download (direct link):
JPEG: STILL IMAGE COMPRESSION STANDARD
kinds of images show that on the average their performances are relatively close to each other . The chosen option for prediction is indicated in the header of the compressed file so that both the encoder and decoder use the same function for prediction.
Table 3.1 Prediction Functions in Lossless JPEG
Option Prediction Function Type of Prediction
0 No prediction Differential Coding
1 Xp = A 1-D Horizontal Prediction
2 XP = B 1-D Vertical Prediction
3 Xp = C 1-D Diagonal Prediction
4 Xp = A + B - C 2-D Prediction
5 XP = A + \(B-C) 2-D Prediction
6 Xp = B + \(A-C) 2-D Prediction
7 XP = ±(A + B) 2-D Prediction
In lossless mode, the standard allows precision (P) of the input source image to be 2 bits to 16 bits wide. Since there is no previously encoded pixel known to the encoder when it encodes the very first pixels in the very first row of the image, it is handled differently. For a given input precision P and a point transform parameter Pt, the predicted value for the first pixel in the first line is 2P~P‘-1. By default, we can assume Pt = 0. For details of the point transform parameter, the reader is advised to consult the JPEG standard .
For all other pixels (except the first one) in the first line, we use option 1 for prediction function. Except for the first line, option 2 is used to predict the very first pixel in all other lines. For all other pixels, we select one of the eight options for the prediction function from Table 3.1. Once a predictor is selected, it is used for all other pixels in the block.
In lossless JPEG standard, the prediction error values are computed modulo 216 in order to take consideration of the full precision allowed in this mode. These error values are not directly encoded using Huffman codes. They are first represented as a pair of symbols (CATEGORY, MAGNITUDE). The first symbol CATEGORY represents the category of the error value. The second symbol MAGNITUDE represents the variable-length integer (VLI) for the prediction error value. The category represents the number of bits to encode the MAGNITUDE in terms of VLI. All the possible prediction error values modulo 216 and their corresponding categories are shown in Table 3.2. Only the CATEGORY in the symbol pair for each prediction error value is Huffman coded. The codeword for the symbol pair (CATEGORY, MAGNITUDE) is formed in two steps. First it assigns the Huffman code of the CATEGORY. This Huffman code is then appended with additional
THE JPEG LOSSLESS CODING ALGORITHM 59
Table 3.2 Categories of Prediction Error Values
Category Prediction Error Value
1 -1, +1
2 -3, -2, +2, +3
3 -7, . ., -4, +4, . . . , +7
4 -15, .., -8, +8, ..., + 15
5 -31, . ., -16, +16, ... , +31
6 -63, . ., -32, +32, ... , +63
7 -127, . ., -64, +64, ... , +127
8 -255, .. , -128, +128, . ., +255
9 -511, .. , -256, +256, . ., +511
10 -1023, .. , -512, +512, . ., +1023
11 -2047, ... -1024, +1024, .., +2047
12 -4095, ... -2048, +2048, .., +4095
13 -8191, ... -4096, +4096, .., +8191
14 -16383, ... -8192, +8192, .., +16383
15 -32767, ..., -16384, +16384, ..., +32767
CATEGORY number of bits to represent the MAGNITUDE in VLI. If the prediction error value is positive, the MAGNITUDE is directly binary represented by a VLI using CATEGORY number of bits and hence it starts with bit 1. If the error value is negative, the VLI is one’s complement of its absolute value and hence it starts with bit 0. For example, the prediction error value 25 is represented by the pair (5, 25) because the number 25 belongs to category 5 in Table 3.2 and hence 25 is represented by a 5-bit VLI. If the Huffman code for category 5 is Oil, then the binary codeword for the error value 25 will be 01111001. The first three bits correspond to the Huffman code Oil for category 5 and the next 5 bits, 11001, is the VLI for 25. Similarly, the prediction error value —25 will be represented as 01100110 where the last 5 bits, 00110, is the l’s complement of 11001 to represent —25, and since —25 belongs to the same category 5, the first three bits of the codeword corresponds to the Huffman code of category 5. Use of the category table greatly simplifies the Huffman coder. Without this categorization, we would need to use a Huffman table with 216 entries for all the 216 possible symbols of prediction error values, which definitely complicates the implementation of the Huffman coder both in software and hardware, if it is not rendered impossible for all practical purposes.
Detailed information for implementation of the JPEG lossless coding for both the Huffman coding mode and the arithmetic coding mode can be found in Annex H of the JPEG standard .
JPEG: STILL IMAGE COMPRESSION STANDARD
3.3 BASELINE JPEG COMPRESSION
The baseline JPEG compression algorithm is widely used among the four modes in JPEG family. This is defined for compression of continuous-tone images with 1 to 4 components. Number of components for grayscale images is 1, whereas a color image can have up to four color components. The baseline JPEG allows only 8-bit samples within each component of the source image. An example of a four-component color image is a CMYK (Cyan, Magenta, Yellow, and Black) image, which is used in many applications such as printing, scanning, etc. A color image for display has three color components, RGB (Red, Green, and Blue), though. In a typical color image, the spatial intercomponent correlation between the red, green, and blue color components is significant. In order to achieve good compression performance, correlation between the color components is first reduced by converting the RGB image into a decorrelated color space. In baseline JPEG, a three-color RGB image is first transformed into a luminance-chrominance (L-C) color space such as YCbCr, YUV, CIELAB, etc. The advantage of converting the image into luminance-chrominance color space is that the luminance and chrominance components are very much decorrelated between each other. Moreover, the chrominance channels contain much redundant information and can easily be subsampled without sacrificing any visual quality for the reconstructed image.