Image analysis – Image compression or coding – Quantization
Reexamination Certificate
1998-01-29
2002-02-05
Boudreau, Leo (Department: 2721)
Image analysis
Image compression or coding
Quantization
C382S240000, C375S240220
Reexamination Certificate
active
06345126
ABSTRACT:
BACKGROUND OF THE INVENTION
This invention relates to a method for producing an embedded bit stream in a hierarchical table lookup vector quantizer for use in connection with image data compression wherein an image is encoded at a transmitter, transmitted, and/or selectively decoded at a receiver. An embedded bit stream is one in which any prefix of the bit stream is a valid bit stream of the image at a lower rate. The present invention provides transcoding to bit streams of arbitrary lower rate, simply by truncation. Thus, image data can be transmitted in an embedded bit stream and the receiver can use as much of the embedded bit stream as is necessary to reconstruct the image to a desired or allowable resolution. That is, the invention implements progressive decoding of bit streams to images with increasing resolution as bits arrive at the receiver.
While the invention is particularly directed to the art of image data compression, and will thus be described with specific reference thereto, it will be appreciated that the invention has applicability to other media, such as video and audio. Exemplary applications to such media include packet priorization for bandwidth scalability in networks, information prioritization for unequal error protection for wireless communication, and arbitrarily fine bit rate control at the encoder.
By way of background, image and video coding standards such as JPEG, MPEG, and MPEG-II are based on transform coding. In transform coding, a block transform such as the discrete cosine transform (DCT) is typically applied to 8×8 blocks of an image, and each transform coefficient or frequency band is independently quantized. The quantization stepsizes typically vary from band to band, with larger stepsizes in the higher frequency bands reflecting the fact that quantization errors at higher spatial frequencies are visually less apparent.
JPEG has a progressive transmission mode, in which an image is stored or transmitted with the most significant bits first, then the next most significant bits, and so on. This is accomplished by beginning with large stepsizes for each band, and successively halving the stepsizes in selected bands in some sequence. As each stepsize is halved, additional bits are stored or transmitted. The resulting bit stream is said to be embedded in the sense that any prefix of the bit stream can be decompressed into an image whose quality is appropriate for the length of the prefix. That is, lower resolution encodings are embedded in higher resolution encodings. Such an embedded bit stream is useful, for example, in image retrieval or telebrowsing applications in which the user must scan through a large collection of images to find a desired image, and it is too expensive or time-consuming to reproduce all the images in full detail. In these applications, the decoder can progressively reconstruct images of improving quality as bits arrive.
Most research on image and video coding algorithms still focuses on variants of transform coding. In particular, the transform is often based on wavelet analysis, subband filtering, or lapped orthogonal transforms, for which the transform blocks overlap, thereby reducing objectionable blocking artifacts.
J. M. Shapiro, “Embedded Image Coding Using Zerotrees of Wavelet Coefficients,” IEEE Trans. on Signal Processing, Vol. 41, No. 17, pp. 3445-3463, December 1993, and D. Taubman and A. Zakhor, “Multi-Rate 3-D Subband Coding of Video,” IEEE Trans. Image Proc., Vol. 3, No. 5, pp. 572-588, September 1994, employ wavelet transform coding in a progressive mode. Taubman uses the resulting embedded bit stream for simple bit rate control in a video encoder. Bit rate control is essential when coupling a variable-rate data compressor to a fixed-rate channel. If the channel can transmit exactly (or a maximum of) B bits per second, then the bit rate of the compressor must be decreased or increased when the buffer between the compressor and channel begins to overflow or underflow, respectively. With an embedded bit stream, bit rate control becomes as simple as taking a prefix of an appropriate length from the encoding for each frame (or other unit) of the video data.
Vector quantization is a generalization of simple (scalar) quantization, in which each vector of coefficients is simultaneously quantized using a small number of bits, e.g. 8, to represent the vector as the index of one of, for example, 256 possible reproduction vectors (called codewords) in a collection of reproduction vectors (called the codebook). A special case of vector quantization is scalar quantization applied independently to each component of a vector. The codewords in this case are constrained to lie on a rectangular lattice. In vector quantization, this constraint is removed. Hence vector quantization is superior to scalar quantization in that it can arrange the codewords in the vector space for maximum coding efficiency. For example, the codewords can be arranged to populate only the probable regions of the space. This can be accomplished using a training set of typical data and a clustering algorithm. See A. Gersho and R. M. Gray, “Vector Quantization and Signal Compression,” Kluwer Academic Publishers, 1992.
Not only do vector quantizers have superior rate-distortion performance; they also permit decoding by simple table lookup. When the decoder receives an 8 bit code, for example, it reproduces the original vector by using the code as the index to a table, and reading the reproduction vector out of the table. If all the coefficients of a block transform are blocked into a single vector, the decoder can decode the whole block with a simple table lookup. No inverse transform is necessary in this case, as it would be if the components of the transform were scalar quantized.
Unfortunately, there are some drawbacks to vector quantization. The first is encoder complexity. Since the codebook is unstructured, for each input vector, the encoder must perform a full search through the codebook looking for the codeword that would result in the lowest distortion. This is often excessively time-consuming for practical algorithms. A second related problem is that for a given bit rate (in bits per component), the number of bits per vector grows linearly with vector dimension, and hence the number of codewords grows exponentially with vector dimension (and hence so does encoder complexity, and encoder and decoder memory requirements). As a practical consequence, the vector dimension must match the bit rate. At low bit rates, large vector dimensions are feasible. At higher bit rates, only small dimensions may be feasible. At the highest bit rates, only scalar quantization may be feasible. At any given bit rate, the best rate-distortion performance will be attained with the largest feasible vector dimensions.
To reduce the computational complexity of searching the codebook of a vector quantizer, a number of alternatives have been developed. One of these is tree-structured vector quantization. In tree-structured vector quantization, the codewords are arranged in a tree structure (typically a binary tree), with one codeword at each node. Instead of searching the codebook exhaustively, it can be searched in a time logarithmic fashion by beginning at the root node, successively comparing the input vector to the codewords at each branch node, descending to the branch with the lower distortion, and repeating the process until reaching a leaf node. The codeword at the leaf is the desired reproduction vector and is represented by a binary code for the leaf, 8 bits to specify one of 256 leaves, for example. If the tree is complete, that is, if all leaves are at the same depth, (e.g. 8), then the path map to the leaf may be used as its index.
The path map has the embedded code property: any prefix represents a reproduction vector in a coarser codebook, i.e., at a higher level in the tree. Trees whose leaves are at varying depths result in a variable-rate code, in which the binary strings used to represent the reproduction vector vary in length depending on th
Chaddha Navin
Chou Philip A.
Vishwanath Mohan
Boudreau Leo
Fay Sharpe Fagan Minnich & McKee LLP
Sheral Ishrat
Xerox Corporation
LandOfFree
Method for transmitting data using an embedded bit stream... 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 for transmitting data using an embedded bit stream..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for transmitting data using an embedded bit stream... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2981030