Image analysis – Image compression or coding – Transform coding
Reexamination Certificate
1998-10-29
2001-05-15
Au, Amelia M. (Department: 2623)
Image analysis
Image compression or coding
Transform coding
C375S240200
Reexamination Certificate
active
06233359
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
This invention relates generally to an image compression technique, and more particularly to a technique that further reduces the size of an existing compressed file to satisfy a certain bit budget in such a way that the information discarded is minimal.
2. Description of the Related Art
The emergence of compression standards such as JPEG (an acronym for “Joint Photographic Experts Group”) has led to many digital imaging systems and applications that create and maintain content only in JPEG compressed format. For instance, in most digital still-imaging cameras (DSCs) such as the Epson PhotoPC 600, Kodak DC-10, etc., pictures captured by the camera are immediately compressed within the camera and (together with the corresponding thumbnail images) are stored in the camera's storage system as JPEG files. Due to constraints within the camera, the thumbnail images (which are also in JPEG format) are constrained to be less than a particular size. Therefore, any images which exceed the size limitation imposed by the camera must be reduced.
Under the current state of the art, some camera-based image compression techniques reduce the size of captured images to meet the constraints of the camera by incorporating into the compression process a procedure that simply sets to zero some of the higher frequency coefficients regardless of their value. Higher frequency coefficients carry less important information than lower frequency coefficients. Thus, turning a high frequency coefficient to zero usually does not present a problem, except when the magnitude of that coefficient is high. In that case, important information will be lost if the high-magnitude coefficient is turned to zero.
Another proposed technique for reducing the magnitude of some quantized coefficients during compression in order to reduce compressed size is set forth in U.S. Pat. No. 5,754,696. For each block of quantized DCT coefficients in the zig-zag scan order, this technique considers two possibilities: (1) coding the coefficients as they are, and (2) reducing the magnitude of low-frequency coefficients above a threshold (i.e., coefficients occurring before a certain ordinal number in the zig-zag scan whose magnitude is above a certain threshold). For the coefficients for which such a magnitude reduction reduces the bit-rate (essentially the coefficients whose magnitude class as defined in the Huffman coding model changes as a result of magnitude reduction), the technique retains the magnitude reduction.
This is a rather inefficient technique. The lower-frequency coefficients are perceptually the most important ones, and reducing their magnitude is bound to affect the image quality adversely. Moreover, the file size reduction obtained in this technique is because of reductions in non-zero magnitude categories, which give small reductions at the expense of much quality.
OBJECTS OF THE INVENTION
Therefore, it is an object of the present invention to overcome the aforementioned problems associated with further reducing a compressed file size.
It is another object of this invention to provide a transcoding technique to guarantee a smaller compressed file size via a thresholding strategy where the information discarded is minimal.
It is a further object of this invention to provide a transcoding technique to be used in a transform-based compression process such as JPEG to generate a smaller compressed file size by reducing the magnitude of coefficients occurring after a selected cutoff ordinal number in the zig-zag scan whose magnitude is below a certain threshold.
It is still another object of this invention to provide a transcoding technique to be used in a transform-based compression process such as JPEG to generate a smaller compressed file size by choosing the cutoff ordinal number via a sophisticated savings calculation strategy.
It is yet another object of this invention to provide a transcoding technique to be used in a transform-based compression process such as JPEG to generate a smaller compressed file size by increasing the lengths of runs of coefficient values of zero to provide a relatively large size reduction at a small quality expense.
SUMMARY OF THE INVENTION
The present invention provides an apparatus and method for generating a second array of frequency-ordered coefficients from a first array of frequency-ordered coefficients using a transcoding technique. The second array of coefficients is generated by establishing an array of predetermined threshold values, one corresponding to each of the coefficients in the first array coefficients, determining a cutoff ordinal number in the first array of coefficients, and setting to zero each of the frequency coefficients in the first array having an ordinal number greater than or equal to the determined cutoff ordinal number and having a magnitude less than or equal to its corresponding threshold value.
In another feature of the invention, the determining step above may additionally comprise generating an array of bit-savings values, one corresponding to each ordinal number in the first array. In this case, each bit-savings value is indicative of a number of bits that would be saved by setting to zero all of the coefficients in the first array having an ordinal number greater than or equal to the corresponding ordinal number (n) and having a magnitude less than or equal to the corresponding threshold value T[n]. Preferably, each bit-savings value is an incremental number of bits that would be saved by setting to zero all of the coefficients in the first array having an ordinal number greater than or equal to n and having a magnitude less than or equal to T[n] relative to setting to zero all of the coefficients in the first array having an ordinal number greater than or equal to n+1 and having a magnitude less than or equal to T[n+]. In accordance with the invention, each savings value in the array of savings values is computed by adding the bits needed to code a run of zeros preceding the n
th
coefficient and a run of zeros following the n
th
coefficient and subtracting the bits needed to code a combined longer run of zeros including the runs of zeros preceding and following the n
th
coefficient while factoring into the computation runs of zeros longer than 16 and end-of-block conditions.
In accordance with a further feature of the invention, the first array of frequency-ordered coefficients, when encoded into a compressed bit-stream, exceeds a predetermined bit budget, and the second array of frequency-ordered coefficients, when encoded into a compressed bit-stream, satisfies the predetermined bit budget.
The transcoding technique of the present invention may be applied in an imaging device, such as a digital still-image camera, or in a system, such as a computer system. Moreover, the technique may be implemented using either software, hardware or combination thereof. If the technique is implemented, either in whole or in part, with software, then the software may be embodied on any processor-readable medium such as a memory, a disk, or a signal on a line.
Other objects and attainments together with a fuller understanding of the invention will become apparent and appreciated by referring to the following description and claims taken in conjunction with the accompanying drawings.
REFERENCES:
patent: 5253078 (1993-10-01), Balkanski et al.
patent: 5461422 (1995-10-01), Hsieh
patent: 5677736 (1997-10-01), Suzuki et al.
patent: 5706216 (1998-01-01), Reisch
patent: 5734755 (1998-03-01), Ramchandran et al.
patent: 5754696 (1998-05-01), Miyashita et al.
patent: 5768436 (1998-06-01), Keesman
patent: 5774597 (1998-06-01), Wilson
patent: 5778102 (1998-07-01), Sandford, II et al.
patent: 5838834 (1998-11-01), Saito
patent: 6002801 (1999-12-01), Strongin et al.
Ivashin Victor
Ratnakar Viresh
Au Amelia M.
Gabrik Michael T.
Seiko Epson Corporation
Wu Jingge
LandOfFree
File size bounded JPEG transcoder (FSBJT) does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with File size bounded JPEG transcoder (FSBJT), we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and File size bounded JPEG transcoder (FSBJT) will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2548193