Image analysis – Image compression or coding – Adaptive coding
Reexamination Certificate
2000-02-24
2003-11-18
Do, Anh Hong (Department: 2624)
Image analysis
Image compression or coding
Adaptive coding
C382S232000, C382S248000
Reexamination Certificate
active
06650782
ABSTRACT:
FIELD OF INVENTION
The invention relates to a method of ordering the compressed bit-planes of a subband or wavelet image coder in the decreasing order of visual significance, also referred to as visually progressive ordering. The method also provides for rate-control of one or more images that have been encoded in the visually progressive manner. The rate-control method truncates the compressed bit streams for individual images so that the total file size of the truncated bit-streams does not exceed a user-specified bit-budget and the overall visual quality of the image set is maximized.
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 emerging JPEG2000 image compression standard, as described in ISO/IEC JTC1/SC29 WG1 N1523, JPEG2000 Part I, Committee Draft, Version 1.0. A desirable feature of the subband bit-plane coders is that the order in which the compressed bit-planes appear in the output bit-stream is very flexible. For a practical and efficient compression system, the ordering has to satisfy only two conditions, namely: 1) for any subband, a bit-plane having higher significance should appear in the bit-stream before a bit-plane having a lower significance; and 2) the contexts used by the entropy coder must be dependent only on bit-planes that have appeared earlier in the bit-stream. Here, significance of a bit-plane refers to the position of the bit-plane in the binary representation of the quantized subband coefficient. In most binary representations, the left most bit-plane is the most significant and the right most bit-plane is the least significant.
These conditions will be referred to as the bit-plane ordering conditions. The ordering of the compressed bit-planes refers to the placement of bit-planes from all the subbands in the compressed bit-stream. It should be noted that compressed bit-planes from different subbands may be interspersed in the bit-stream. A useful feature of any coder that satisfies the bit-plane ordering conditions is that the compressed bit-stream is embedded. This means that if the compressed bit-stream is truncated at any arbitrary point, the truncated bit-stream can be decoded to produce a reconstructed image of lower quality than that produced by the full bit-stream. If the compressed bit-planes are ordered in the decreasing order of visual significance, then the bit-stream is said to be visually embedded or visually progressive.
In the prior art, visually 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.
A central aspect of this invention is to provide a method for ordering the compressed bit-planes in the decreasing order of visual significance. In the preferred embodiment, the visual significance of a bit-plane is quantified in terms of a threshold viewing distance, although other quality metrics indicative of a visual significance value could be used. A lower threshold viewing distance corresponds to lower visual significance. This eliminates the need for using multiple sets of visual weights and the problem of determining the rates at which the switching from one set of visual weights to another should occur. Furthermore, the invention provides an efficient method for rate-control of one or more images based on visually progressive ordering.
SUMMARY OF THE INVENTION
The invention relates to a method of ordering the compressed coefficient bit-planes of a subband or wavelet image coder in the decreasing order of their visual significance. The method also provides a means for a simple and computationally inexpensive method of determining truncation points for the compressed bit-streams corresponding to one or more images, so that the total file size of the truncated bit-streams does not exceed a user-specified bit-budget and the overall visual quality of the image set is maximized. One embodiment of the invention is a method for encoding a digital image comprising the steps of:
a) inputting the digital image;
b) decomposing the digital image into two or more subbands;
c) quantizing the subbands of the decomposed digital image to create quantized output values for each subband;
d) forming bit-planes from the quantized output values of each subband;
e) computing a visual significance value for each bit-plane;
f) ordering the bit-planes in decreasing order of the corresponding visual significance value;
g) entropy coding the ordered bit-planes to produce a compressed bit-stream; and
h) combining the compressed bit-stream with bit-plane ordering information to produce an encoded representation of the digital image.
While this embodiment describes only the encoder, it will be clear to those skilled in the art that the decoder will need to access the information regarding the bit-plane ordering before it can successfully reconstruct the image from the compressed bit-stream.
Another embodiment of this invention is a method for rate-control of one or more images comprising the steps of:
a) encoding the images in a visually progressive manner to form a compressed bit-stream for each image;
b) generating a table of visual significance values and corresponding file sizes for possible truncation points of the compressed bit-stream for each image;
c) initializing a current truncation point for each image;
d) truncating the compressed bit-stream for each image to the corresponding current truncation point;
e) calculating a total compressed file size for the truncated compressed bit-streams;
f) comparing the total compressed file size with a pre-determined bit-budget;
g) 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
h) repeating steps d through g until the total compressed file size is less than or equal to the bit-budget.
It is then an object of the invention to produce a compressed bit-stream for a digital image in which the bit-planes are ordered in the decreasing order of visual significance, that is, in the visually progressive manner.
It is a further object of the present invention to provide a simple and computationally inexpensive method for determining truncation points for the compressed bit-streams corresponding to individual images, so that the overall memory required is equal to or less than the bit-budget.
It is a further object of the present invention to provide a method of maximizing the visual quality of the reconstructed image for a given compressed file size when using a subband or wavelet decomposition.
Another object of the present invention is to provide a method of rate-control for one or more images that have been encoded in the visually progressive manner so that the overall memory required does not exceed the storage space available and the overall visual quality of the image set is maximized.
REFERENCES:
patent: 5867602 (1999-02-01), Zandi et al.
patent: 6327392 (2001-12-01), Li
Hwang et al., “Storage and Entropy-Constrained Multi-Stage Vector Quantization”, IEEE Global Telecommunications Conference, vol. 1, Nov. 1995, pps. 457-461.*
“Comparative study of wavelet and DCT decompositions with equivalent quantization and encoding strategies for medical images” by Paul W. Jones, Scott Daly, Roger S. Gaborski, and Majid Rabbani. Proc. SPIE Medical Imaging '95, vol. 2431, pp. 571-582.
“Visual Pro
Jones Paul W.
Joshi Rajan L.
Do Anh Hong
Eastman Kodak Company
Woods David M.
LandOfFree
Visually progressive ordering of compressed subband... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Visually progressive ordering of compressed subband..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Visually progressive ordering of compressed subband... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3133571