Image analysis – Image compression or coding – Adaptive coding
Reexamination Certificate
1998-01-30
2003-09-23
Johnson, Timothy M. (Department: 2625)
Image analysis
Image compression or coding
Adaptive coding
C382S247000
Reexamination Certificate
active
06625321
ABSTRACT:
BACKGROUND OF THE INVENTION
This invention relates to embedded coding techniques and more particularly to an embedded image coder with improved rate-distortion.
Embedded image coding improves coding performance and also allows a bitstream to be truncated at any point and still decode a reasonably good image. Some representative embedded coding techniques include the embedded zerotree wavelet coding (EZW) discussed in J. Shapiro, “Embedded image coding using zerotree of wavelet coefficients”, IEEE Trans. On Signal Processing, vol. 41, pp.3445-3462, December 1993, the set partitioning in hierarchical trees (SPIHT) discussed in A. Said, and W. Pearlman, “A new, fast and efficient image codec based on set partitioning in hierarchical trees”, IEEE Trans. On Circuit and System for Video Technology, Vol. 6, No. 3, June 1996, pp. 243-250 and the layered zero coding (LZC) discussed in, D Taubman and A. Zakhor, “Multirate 3-D subband coding of video”, IEEE Trans. On Image Processing, Vol. 3, No. 5, September 1994, pp.572-588.
The ability to adjust the compression ratio by simply truncating the coding bitstream makes embedding attractive for a number of applications such as progressive image transmission, internet browsing, scalable image and video databases, digital cameras, low delay image communications, etc. Taking internet image browsing as an example, embedded coding requires storage on a server of only one copy of a high quality image. Depending on user demand, channel bandwidth conditions, and browser monitor quality, selectable amounts of the image bit stream can be delivered to the browser. At an early stage of browsing, images can be retrieved with coarse quality so that a user can quickly go through a large number of images before choosing one image of interest. The chosen image can then be fully downloaded with a better quality level. During the download process, the image quality is gradually refined. The user can terminate the download process as soon as the quality is satisfactory to discern the image.
Embedded coding allows the bitstream to be arbitrarily truncated. However, existing embedded coding techniques are not optimized at every truncation point in the bit stream. Thus, if the encoded bitstream is truncated at random points in the bit stream, the image produced by the bit stream up to the point of truncation does not necessarily produce optimal image quality.
It is known that a fixed rate coder achieves optimality if the rate-distortion (R-D) slopes of all coded coefficients are the same, T. M. Cover and J. A. Thomas, “Elements of information theory”, Chapter 13, John Wiley & Sons Inc, 1991. The criterion was used in rate control to adjust the quantization step size Q of each macroblocks, in which case the coding of video was optimal when the R-D slopes of all macroblocks were constant. See L.-J. Lin, A. Ortega and C.-C. J. Kuo, “Rate control using spline-interpolated R-D characteristics”, SPIE: Visual Communication and Image Processing, vol. 2727, Orlando, Fla., April 1996, pp. 111-122 and K. Ramchandran, A. Ortega and M. Vetterli, “Bit allocation for dependent quantization with applications to multiresolution and MPEG video coders”, IEEE Trans. On Image Processing, Vol. 3, No. 5, September 1994, pp. 533-545.
Xiong and Ramchandran use the constant rate-distortion slope criterion to derive the optimal quantization for wavelet packet coding. Z. Xiong and K. Ramchandran, “Wavelet packet-based image coding using joint space-frequency quantization”, First IEEE International Conference on Image Processing, Austin, Tex., Nov. 13-16, 1994. However, Xiong and Ramchandran do not optimize rate-distortion optimization for embedded coders.
The R-D slopes of significance identification and refinement coding are different, and by placing the significance identification before the refinement coding, the coding efficiency can be improved. However, the improvement is limited since only the coding order of a few coefficients is effected. See Li, Cheng and Kuo J. Li, P. Cheng and C. -C. J. Kuo, “On the improvements of embedded zerotree wavelet (EZW) coding”, SPIE: Visual Communication and Image Processing, vol. 2601, Taipei, Taiwan, May. 1995, pp. 1490-1501.
Thus, a need remains for an embedded coder that optimizes rate-distortion at many different truncation points in an encoded bit stream.
SUMMARY OF THE INVENTION
A rate-distortion optimised embedding (RDE) coder optimises rate-distortion performance by coding coefficients in order of their R-D slope. RDE allocates the available coding bits first to the coefficient with the steepest R-D slope, which indicates the largest distortion decrease per coding bit. The resultant RDE bitstream can be truncated at any point and still maintain an optimal R-D performance. To avoid the overhead of coding order transmission, an expected R-D slope is calculated by both the encoder and the decoder from previous RDE coded bits. A probability estimation table from a QM arithmetic coder allows the R-D slope to be derived using a lookup table operation. The RDE rate-distortion optimisation significantly improves the coding efficiency over a wide bit rate range.
The RDE embedded coding method digitizes the image and then transforms the image to form a set of coefficients each comprising multiple bits. The RDE coder repeatedly analyzes all the candidate bits before encoding individual bits. The candidate bits comprise one most significant unencoded bit from each coefficient. Individual rate-distortion values for the candidate bits represent a ratio of information content in the bit per cost in transmitting the bit. Selected bits are then encoded according to the associated distortion reduction values for the bits.
In one embodiment, one bit among the candidate bits having a maximum distortion reduction value is encoded. The candidate bits are updated comprising a next less significant bit in the encoded bit coefficient and the remaining unencoded candidate bits. The bit among the candidate bits with the highest distortion reduction value per coding bit is encoded next. The process is repeated until the RDE coder reaches a specified bit rate.
In another embodiment, a threshold value is set and the candidate bits having distortion reduction values greater than the threshold are encoded in each scan. The candidate bits are updated comprising a next less significant bit in the encoded bit coefficient and the remaining unencoded candidate bits. The threshold value is then reduced and a next set of unencoded candidate bits are processed. The candidate bits in the next set having distortion reduction values greater than the reduced threshold value are then encoded. The process is repeated until the RDE coder reaches the predetermined bit rate.
REFERENCES:
patent: 4811398 (1989-03-01), Copperi et al.
patent: 5023611 (1991-06-01), Chamzas et al.
patent: 5099440 (1992-03-01), Pennebaker et al.
patent: 5315670 (1994-05-01), Shapiro
patent: 5506686 (1996-04-01), Auyeung et al.
patent: 5691770 (1997-11-01), Keesman et al.
patent: 5694171 (1997-12-01), Katto
patent: 5778192 (1998-07-01), Schuster et al.
Ramchandran et al., Rate-Distortion Optimal Fast Thresholding with Complete JPEG/MPEG Decoder Compatibility, Sep. 1994, p 700-704, IEEE Transactions on Image Processing, V 3, No. 5.*
Ramchandran et al., “Bit Allocation for Dependent Quantization with Applications to Multiresolution and MPEG Video Coders”, IEEE Trans. on Image Proc., vol. 3, No. 5, Sep. 1994.*
“Embedded Image Coding Using Zerotree of Wavelet Coefficients”, written by J. Shapiro,IEEE Trans. On Signal Processing, vol. 41, Dec. 1993, pp. 3445-3462.
“A Zero-Tree Entropy Coding Tool for Wavelet Compression of Video” written by S. Martucci and the VLBR Team, ISO/IEC JTC/SC29/WG11/N0441, Nov. 1995, 7 pages.
“A New, Fast and Efficient Image Codec Based on Set Partitioning in Hierarchical Trees” written by A. Said and W. Pearlman,IEEE Trans. On Circuit and System for Video Technology, vol. 6, No. 3, Jun. 1996. pp. 243-250.
“Multirate 3-D Subband Coding of Video” written by D. Taubman and A. Zakhor,IEEE Tran
Lei Shaw-Min
Li Jin
Johnson Timothy M.
Marger Johnson & McCollom
Sharp Laboratories of America Inc.
LandOfFree
Embedded image coder with rate-distortion optimization does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Embedded image coder with rate-distortion optimization, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Embedded image coder with rate-distortion optimization will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3112562