Image analysis – Image compression or coding – Quantization
Reexamination Certificate
1998-01-26
2001-06-26
Mehta, Bhavesh (Department: 2621)
Image analysis
Image compression or coding
Quantization
C382S250000, C382S239000, C375S240220
Reexamination Certificate
active
06252994
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of Invention
This invention relates to digital systems for scanning, representing, and reproducing document images. More specifically, the present invention is directed to adaptive quantization within the JPEG sequential mode data syntax. In particular, it relates to a method of segmenting an image into blocks of different image types that can be used to compress the image more efficiently without loss of significant information based on the visual properties of the human eye.
2. Description of Related Art
The JPEG (Joint Photographic Expert Group) architecture can be viewed as a compression method from which various applications can define a compression system that is suitable for their particular needs. JPEG is concerned only with the encoding and decoding of image data—the interpretation of the data is beyond the scope of JPEG and is left to the applications that use it.
The JPEG specification consists of several parts, including protocols for both lossless and lossy compression encoding. The lossless compression algorithm uses a predictive/adaptive model with a Huffman code output stage without the loss of any information. The JPEG lossy compression algorithms, including the standard sequential mode with which this invention is most concerned, operate in several successive stages, as shown in FIG.
1
. These steps combine to form a compressor capable of compressing predominantly continuous tone images while losing little of their original fidelity. In general in this application, for simplicity the term “JPEG” used as an adjective will usually refer to JPEG sequential mode data syntax. For example, “JPEG compliant” means “compliant with the JPEG sequential mode data syntax.”
Central to the compression process is the Discrete Cosine Transform (DCT) performed on each image plane (e.g., color or luminosity values) of an image. As will be appreciated, there are mono-plane images (e.g., gray images), as well as multi-layer or multi-plane images (e.g., rgb or cmyk images). Therefore, it is to be understood that “image” sometimes is used herein to refer to a single plane of a multi-layer image because essentially the same compression process is performed for each image plane. For example, when a DCT is performed on the 64 values of an 8×8 pixel block within any plane of an image, the result is a set of 64 coefficients, representing amplitudes of 64 respective orthogonal waveform components, that together define the values for all 64 pixels in the 8×8 pixel block. An inverse DCT performed on the 64 coefficients will reproduce the original 64 values of the 8×8 pixel block.
The advantage of using these 64 coefficients instead of the 64 original values is that each coefficient represents the magnitude of an orthogonal waveform representing a different spatial frequency. Smooth textured blocks have low pixel-to-pixel variation, so many zero-value “high-frequency” DCT coefficients are likely. For example, performing a DCT on a block of 64 pixels having identical values will result in one nonzero coefficient and 63 zero value coefficients. Further, if the coefficients are ordered by spatial frequency, longer strings of zero-value coefficients will result.
As one skilled in the art will understand, data with long zero-value strings will enable greater data compression, for example when using Huffman-type entropy encoding. For this reason, when a DCT is computed for a (usually 8×8) pixel block, it is desirable to represent the coefficient for high spatial frequencies with less precision. This is done by a process called quantization, illustrated in FIG.
2
. Quantization is basically a process for reducing the precision of the DCT coefficients. Precision reduction is extremely important, since lower precision almost always implies greater throughput in the compressed data stream. One reason the JPEG algorithm compresses so effectively is that a large number of coefficients in the DCT block are rounded or truncated to zero value during the quantization stage.
A DCT coefficient is quantized by dividing it by a nonzero positive integer called a quantization value, and truncating or rounding the quotient—the quantized DCT coefficient—to the nearest integer. In order to reconstruct (dequantize) the DCT coefficient, the decoder must multiply it by the quantization value. Since some precision is lost in quantizing, the reconstructed DCT coefficients are approximations of the values before quantization.
Before quantizing, the DCT coefficients are ordered into a one-dimensional vector using the well known zigzag scan sequence as shown in Table 1 below. The lowest frequency component, represented by the coefficient labeled zero, is the DC component. The remaining coefficients are the AC coefficients, and are ordered horizontally and vertically from left to right and top to bottom, respectively, representing increasingly high frequencies. The DC coefficient is coded using a one-dimensional DPCM (Differential Pulse Code Modulation) technique, which converts the current DC coefficient to a difference from the DC coefficient of the previous block, followed by entropy coding. The AC coefficients in the zigzag scan are divided into runs of zero coefficients terminated by nonzero coefficients. Huffman codes are then assigned to each possible combination of zero coefficient run length and magnitude for the next non-zero AC coefficient.
TABLE 1
Zigzag scan index sequence for DCT coefficients
0,
1,
5,
6,
14,
15,
27,
28,
2,
4,
7,
13,
16,
26,
29,
42,
3,
8,
12,
17,
25,
30,
41,
43,
9,
11,
18,
24,
31,
40,
44,
53,
10,
19,
23,
32,
39,
45,
52,
54,
20,
22,
33,
38,
46,
51,
55,
60,
21,
34,
37,
47,
50,
56,
59,
61,
35,
36,
48,
49,
57,
58,
62,
63.
For compressing an image plane of an image, JPEG protocol allows the encoder to embed an 8×8 quantization table (Q-table) in the data that will be passed to the decoder. This Q-table can contain different values for quantizing the respective DCT coefficients, chosen so as to minimize perceived distortion in reconstructed images, using principles based on the human visual system. The lowest level of capability for the JPEG sequential mode is the “baseline system.” In this system, which is intended to allow a very simple implementation in hardware, no more than one table for each image plane (up to a maximum total of four, regardless of the total number of image planes) can be embedded in the data to be passed to the decoder.
In a typical JPEG baseline sequential technique, illustrated in
FIGS. 1-3
, source image pixel values of an 8×8 pixel block (p
00
, p
01
, . . . , p
xy
, . . . , p
77
)
102
are subjected to a discrete cosine transform (DCT)
104
F
. The resulting DCT coefficients are ordered into a DCT coefficient matrix (S
00
, S
01
, . . . , S
xy
, . . . , S
77
)
104
as shown in Table 1 above. Quantization
108
F
is performed on the DCT coefficients
104
, using a Q-table (Q
00
, Q
01
, . . . , Q
xy
, . . . , Q
77
)
106
to obtain quantized DCT coefficients (Sq
00
, Sq
01
, . . . , Sq
xy
, . . . , Sq
77
)
108
, by dividing each S
xy
by its corresponding Q
xy
and rounding the result to the nearest integer. The quantized DCT coefficients
108
are then encoded by an entropy encoder
110
using Huffman tables
112
, and the resulting encoded (compressed) data
114
are transmitted or stored until needed, at which time they are decoded, dequantized, and subjected to an inverse DCT to reconstruct the 8×8 pixel block
102
(or an approximation thereof).
Steps for performing JPEG compliant compression are summarized in FIG.
3
. In step S
302
, an image is scanned and pixels are organized into 8×8 pixel blocks. At step S
304
, a discrete cosine transform (DCT) is performed on a block. At step S
306
, the DCT coefficients are quantized and at step S
308
, encoding of the pixel block is performed. This process is repeated for all blocks in the image, until JPEG encoding has been performed for the entire image.
JPEG was originally adopted for encoding photographs that typically contain smo
Mehta Bhavesh
Oliff & Berridg,e PLC
Xerox Corporation
LandOfFree
Adaptive quantization compatible with the JPEG baseline... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Adaptive quantization compatible with the JPEG baseline..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Adaptive quantization compatible with the JPEG baseline... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2518468