Image analysis – Image compression or coding – Quantization
Reexamination Certificate
1998-12-29
2002-02-19
Grant, II, Jerome (Department: 2624)
Image analysis
Image compression or coding
Quantization
C382S232000
Reexamination Certificate
active
06349151
ABSTRACT:
FIELD OF THE INVENTION
The current invention relates generally to the field of image processing, and, in particular, to a method of controlling the rate and quality of compressed images.
BACKGROUND OF THE INVENTION
The advent of the Internet coupled with dramatic improvements in software and printing technologies is causing a migration from local printing presses to the semi-automated high-speed and high-volume shops that can be located virtually anywhere in the world. Printer manufacturers, in order to succeed in this new paradigm, are required to make faster and cheaper printers while maintaining the high levels of image quality required by various applications. Consequently, there is an ever increasing need for image compression, not just for storage considerations, but also for enabling the digital circuitry to keep up with the extremely high data rates dictated by the printing process.
These factors impose a strict requirement on the robustness and speed of the compression technology used in these systems. Many printing applications have a strict requirement on the minimum compressed data rate in order to enable the high-speed printing process while at the same time, they also require very high quality decompressed images. Unfortunately, these two requirements are often in direct conflict with one another. In fact, a key factor in the design of many high-speed printing systems is the development of a compression strategy that reduces the amount of compressed data to or below a desired compressed file size (or equivalently, the desired data rate), while still achieving a minimum (or better) level of quality. The current invention deals with the development of such a compression strategy.
A popular technique for the compression of continuous tone images is the JPEG international compression standard. (Digital compression and coding of continuous-tone still images—
Part I: Requirements and Guidelines
(
JPEG
), ISO/IEC International Standard 10918-1, ITU-T Rec. T.81, 1993, or W. B. Pennebaker and J. L. Mitchell,
JPEG Still Image Data Compression Standard
, Van Nostrand Reinhold, New York, 1993). Briefly, when using JPEG compression, the digital image is formatted into 8×8 blocks of pixel values, and a linear decorrelating transformation known as the discrete cosine transform (DCT) is applied to each block to generate 8×8 blocks of DCT coefficients. The DCT coefficients are then normalized and quantized using a frequency-dependent uniform scalar quantizer.
In the JPEG standard, the user can specify a different quantizer step size for each coefficient. This allows the user to control the resulting distortion due to quantization in each coefficient. The quantizer step sizes may be designed based on the relative perceptual importance of the various DCT coefficients or according to other criteria depending on the application. The 64 quantizer step sizes corresponding to the 64 DCT coefficients in each 8×8 block are specified by the elements of an 8×8 user-defined array, called the quantization table or “Q-table”. The Q-table is the main component in the JPEG system for controlling the compressed file size and the resulting decompressed image quality.
Each block of the quantized transform coefficients is ordered into a one-dimensional vector using a pre-defined zig-zag scan that rearranges the quantized coefficients in the order of roughly decreasing energy. This usually results in long runs of zero quantized values that can be efficiently encoded by runlength coding. Each nonzero quantized value and the number of zero values preceding it are encoded as a runlength/amplitude pair using a minimum redundancy coding scheme such as Huffman coding. The binary coded transform coefficients along with an image header containing information such as the Q-table specification, the Huffman table specification, and other image-related data are either stored in a memory device or transmitted over a channel.
As mentioned previously, the ability to trade off image quality for compressed file size in JPEG is accomplished by manipulating the elements of the Q-table. In general, each of the 64 components of the Q-table can be manipulated independently of one another to achieve the desired image quality and file size (or equivalently, the desired compression ratio or bit rate) or image quality. However, in most applications, it is customary to simply scale all of the elements of a basic Q-table with a single constant. For example, multiplying all elements of a given Q-table by a scale factor larger than unity would result in a coarser quantization for each coefficient and hence a lower image quality. But at the same time, a smaller file size is achieved. On the other hand, multiplication by a scale smaller than unity would result in a finer quantization, higher image quality, and a larger file size. This scaling strategy for trading image quality for compressed file size is advocated by many developers of JPEG compression products including the Independent JPEG Group (IJG) whose free software is probably the most widely used tool for JPEG compression. A current version of the software is available at the time of this writing from ftp://ftp.uu.net/graphics/jpeg/. The LJG implementation scales a basic Q-table by using a parameter known as the “IJG quality setting”, which converts a value between 1 and 100 to a multiplicative scaling factor.
In many applications, an image needs to be JPEG-compressed to a pre-specified file size. This problem is sometimes referred to as “rate control”. In the prior art, JPEG rate control is typically accomplished by compressing the image multiple times until the desired file size is achieved. First, the image is compressed using a basic Q-table, e.g., one that has been designed for that application or the example tables given in the JPEG standard specifications. If the target file size is not achieved, the components of the Q-table are appropriately scaled based on a pre-defined strategy, and the image is compressed again with the scaled Q-table. This process is repeated until the compressed file size is within an acceptable range of the target file size. One strategy that can be used to determine the Q-table scaling at each iteration is described in the prior art by Tzou (IEEE Transactions on Circuits And Systems For Video Technology, Vol 1, No. 2, June 1991, pages 184-196). Although this and other similar strategies often provides rapid convergence (usually 3 or less iterations), they usually require the pre-calculation of an operational rate-distortion (R-D) curve for the class of imagery used in that particular application. This curve is constructed by: (i) compressing many representative images using different scaled versions of a basic Q-table; (ii) averaging the resulting file sizes for each Q-table scale to obtain the so-called “control points” on the curve; and (iii) using piecewise-polynomials to approximate all points between the control points by interpolation to obtain a plot of the average file size against the scaling parameter.
A major drawback of rate control strategies practiced in the prior art is that the various Q-tables used to compress an image to different file sizes are typically scaled versions of a basic Q-table. Although the prior art teaches techniques for the optimization of the Q-table elements for a specific set of viewing and display conditions (see for example, the technique described by Daly in “Application of a noise-adaptive contrast sensitivity function to image data compression,” Optical Engineering, Volume 19, number 8, pages 979-987, August 1990), it is clearly understood that the scaling of such a Q-table to achieve different file sizes is more of a convenience than an optimal strategy. In fact, at the time of this writing, it is stated at the IJG website
(http://www.faqs.org/faqs/compression-faq/part2/index.html) that “Tuning the quantization tables for best results is something of a black art, and is an active research area. Most existing encoders use simple linear scaling of the example tables given i
Honsinger Chris W.
Jones Paul W.
Rabbani Majid
Eastman Kodak Company
Grant II Jerome
Woods David M.
LandOfFree
Method and apparatus for visually optimized compression... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for visually optimized compression..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for visually optimized compression... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2981000