Image analysis – Image compression or coding – Adaptive coding
Reexamination Certificate
2000-05-26
2003-12-23
Boudreau, Leo (Department: 2621)
Image analysis
Image compression or coding
Adaptive coding
C382S248000, C382S302000
Reexamination Certificate
active
06668090
ABSTRACT:
FIELD OF INVENTION
This invention describes a method for producing a compressed digital image that is organized into layers corresponding to increasing visual quality level, and for providing rate-control of such compressed digital image.
BACKGROUND OF THE INVENTION
In recent years, many methods for subband or wavelet coding of images have been proposed. Some of these methods use entropy coding of the subband coefficient bit-planes, where the subband coefficients may have been quantized. Importantly, bit-plane encoding of wavelet coefficients is being used in the proposed JPEG2000 image compression standard, as described in ISO/IEC JTC1/SC29 WG1 N1646, JPEG2000 Part I Final Committee Draft, Version 1.0, March 2000.
The block diagram of a generic JPEG2000 encoder is shown in FIG.
1
. The JPEG2000 encoder decomposes the image into a hierarchy of resolutions and the compressed data corresponding to a resolution is further divided into a number of quality layers, say 1,2, . . . , L. At any resolution, adding more layers to the compressed bit-stream generally improves the quality of the image reconstructed at that resolution and at higher resolutions. The JPEG2000 standard offers great flexibility in terms of organization and ordering of the compressed bit-stream. One such ordering enabled by JPEG2000 standard is known as “layer-resolution-component-position progressive”, henceforward referred to as “layer-progressive”. In this ordering, the compressed bit-stream is arranged in the increasing order of layer-index. That is, the data corresponding to layer
1
from all resolution levels appears at the start of the compressed bit-stream. This is followed by all the data belonging to layer
2
, and so on. One useful property of such an ordering is that, if whole or partial layers appearing at the end of the compressed bit-stream are discarded, the truncated bit-stream can be decoded to produce a reconstructed image of lower quality.
As noted previously, layer-progressive ordering will generally provide improved quality with additional layers. However, there is no guarantee that the perceived image quality will be improved with each additional layer. This is because quality is often quantified in terms of mean squared error or similar metrics, and it is well known that these metrics do not correlate well with perceived image quality.
The JPEG2000 standard places very few restrictions on the formation of layers. Thus, it is up to the individual JPEG2000 encoder to devise application-specific methods for the formation of layers. In the prior art, a layer-progressive ordering is determined based on the relative visual weighting of the subbands (J. Li, “Visual Progressive Coding”, SPIE Visual Communication and Image Processing, Vol. 3653, No. 116, San Jose, Calif., January 1999). In this method, it is possible to use different sets of visual weights at different ranges of bit-rates. The chief drawback of the method is that it is difficult to determine the bit-rate at which visual weights should be changed. This is because the compression ratios can vary widely depending on the image content, for the same compression settings.
Taubman (David Taubman, “High Performance Scalable Image Compression with EBCOT”, to appear in IEEE Transactions on Image Processing) describes a method for the formation of layers in a JPEG2000 encoder. In his method, mean squared error (MSE) or visually weighted MSE is used as the distortion metric. Then, rate-distortion trade-off is used to decide how the layers are formed. As mentioned previously, MSE often does not correlate well with perceived visual quality. Also, it may sometimes be necessary to adjust the visual weightings based on the compression settings.
SUMMARY OF THE INVENTION
Accordingly, it is an object of the present invention to provide a method for the formation of the layers of a compressed bit-stream in a JPEG2000 encoder in such a manner that the layers correspond to increasing visual quality level. This object is achieved by a method for producing a compressed digital image from an input digital image, wherein the compressed digital image is organized into layers corresponding to increasing visual quality levels, comprising the steps of:
(a) decomposing the input digital image to produce a plurality of subbands, each subband having a plurality of subband coefficients;
(b) quantizing the plurality of subband coefficients of each subband of the decomposed input digital image to produce a quantized output value for each subband coefficient of each subband;
(c) forming at least one bit-plane from the quantized output values of the subband coefficients of each subband;
(d) entropy encoding each bit-plane of each subband in at least one pass to produce a compressed bit-stream corresponding to each pass, wherein each subband is entropy encoded independently of the other subbands;
(e) computing a visual significance value for each pass;
(f) providing a visual quality table that specifies a number of expected visual quality levels and corresponding visual significance values;
(g) for each expected visual quality level, identifying a minimal set of passes and their compressed bit-streams that are necessary to achieve the corresponding visual significance value; and
(h) ordering the compressed bit-streams corresponding to passes into layers from the lowest expected visual quality level to the highest expected visual quality level specified in the visual quality table to produce a compressed digital image, wherein each layer includes the passes and their corresponding compressed bit-streams from the identified minimal set corresponding to the expected visual quality level that have not been included in any lower visual quality layers.
It is a further object to provide an efficient method for rate-control of one or more compressed digital images having layers which correspond to increasing visual quality level. This object is achieved by a method of rate-control for at least one image, comprising the steps of:
(a) providing a visual quality table for each image that specifies a number of expected visual quality levels and corresponding visual significance values;
(b) compressing the plurality of images to produce compressed digital images, wherein each compressed digital image includes layers corresponding to the expected visual quality levels specified in the visual quality table;
(c) producing a table of visual significance values and corresponding file sizes for possible truncation points of each compressed digital image, wherein for the expected visual quality levels of each compressed digital image, the truncation points represent the number of bytes necessary to achieve the corresponding expected visual quality levels;
(d) initializing a current truncation point for each image;
(e) truncating each compressed digital image to the corresponding current truncation point;
(f) calculating a total compressed file size for the truncated compressed digital images;
(g) comparing the total compressed file size for the truncated compressed digital images with a pre-determined bit-budget;
(h) updating the current truncation point to the next possible truncation point for the image having the lowest visual significance value at the next possible truncation point; and
(i) repeating steps (e) through (h) until the total compressed file size is equal to or less than the bit-budget.
ADVANTAGES OF THE INVENTION
The present invention provides a method for the formation of layers in such a manner that the compressed data in a lower-indexed layer at any resolution has higher visual significance and appears earlier in the compressed bit-stream compared to a higher-indexed layer at any resolution. This is also known as a “visually progressive” compressed bit-stream. The advantage of this ordering is that if the compressed bit-stream is truncated, visually less significant layers will be discarded first. In addition, when the compressed bit-stream is arranged in a layer-progressive manner, and the bit-stream is truncated to retain only the first j layers, the j
th
visual qu
Jones Paul W.
Joshi Rajan L.
Boudreau Leo
Crocker Pamela R.
Dang Duy M.
Eastman Kodak Company
LandOfFree
Producing a compressed digital image organized into layers... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Producing a compressed digital image organized into layers..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Producing a compressed digital image organized into layers... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3148473