Image analysis – Image compression or coding – Quantization
Reexamination Certificate
2002-11-15
2004-08-03
Mehta, Bhavesh M. (Department: 2625)
Image analysis
Image compression or coding
Quantization
C375S240030
Reexamination Certificate
active
06771831
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to a data compression method and system. More in particular, it relates to a method for designing an optimal scalar quantizer to be used in communications or storage systems.
In a communication system, the information to be sent along a channel is usually encoded by means of a source coder, which compresses the data to be sent. The source coder employs a source code that can either be lossless or lossy. A lossless source code is completely reversible, while a lossy source code creates a distortion of the signal to be transmitted. Any lossy source code can be described as a quantizer followed by a lossless compression algorithm. The quantizer performs an approximation step and the lossless compression algorithm performs a lossless compression step.
Quantizers that operate on blocks of source output are called vector quantizers. Quantizers that quantize each output separately are called scalar quantizers. In scalar quantization, each single-source output is quantized to one of some number of levels, and these levels are encoded into a binary sequence. See, for example, “Communication Systems Engineering,” John G. Proakis and Masoud Salehi, Prentice-Hall Inc., 1994, p. 246.
For example, the initial source alphabet can be a list of 256 brightness levels numbered from 0 to 255 in a gray scale image. Each symbol can have a certain relative frequency, or probability, so that a list of symbol/probability pairs can be defined, forming a discrete probability function, also known as probability mass function or pmf. A scalar quantizer would approximate the initial source alphabet with a smaller set, for example, the set {10, 35, 49, 102} by mapping each number between 0 and 255 to either 10, 35, 49 or 102. A new probability function would arise, given by the relative frequencies of 10, 35, 49 and 102 in the approximation. The “distortion measure” quantities indicate how badly the data is distorted by the chosen mapping.
The output of the quantizer is assumed to go to a lossless compression algorithm, which introduces no further approximations, but produces a more compact representation of the data by taking advantage of its redundancy. The quantizer mapping is chosen with the aim of both keeping the distortion low and allowing a compact representation. The “rate” describes how compact the representation is, with lower rate indicating a shorter data representation. The shorter data descriptions require less memory to store and less time to transmit. Generally, coarser approximations yield higher distortion and lower rate.
There are two important rate measures: in “fixed rate” scenarios, the number of symbols for the approximation is fixed, and each approximation has the same description length. Therefore, the rate does not enter into consideration, and all that remains in quantizer design is the choice of approximation symbols that yield the least distortion, i.e. the least approximation error. In “variable rate” scenarios, the number of approximating symbols is not fixed beforehand and each approximation can have a different description length.
In some systems, an optional initial transform step is provided, where an initial reversible transformation is performed as preprocessing. The code then quantizes the transformed data. The reconstruction process replaces each description by its corresponding reconstruction and then reverses the transformation.
When only one approximation of the original data is given, the quantizer is called a single-description quantizer. However, there is a need to design quantizers not limited to single-description scenarios, but also capable of handling other coding scenarios, like multiple description and multiple resolution coding.
Multiple description refers to the simultaneous production of two or more approximations of the original data. Some approximations are given independent descriptions, while others are reached by combining two or more of the independent descriptions. Reference can be made, for example, to a communications system where more than one path is available, like the case, for example, of one transmitter and multiple receiving antennas. In such case, the different descriptions will travel independently, and some of them may not be received at all.
Multiple description (MD) can be general or restricted. In general-MD, all scenarios are a-priori possible. In restricted-MD, some combinations are known to be impossible. Therefore, in restricted-MD, the sender can make certain assumptions that reduce the number of scenarios to be considered and simplify the code. A special case of restricted-MD is called multi-resolution. In multi-resolution, each description is received only if the previous ones have been received, so that description 3 cannot arrive without description 1 and description 2. A specialized version of the method according to the present invention runs much faster in the multi-resolution case.
Throughout the description of the present invention, reference will be made to the enclosed Annex A, which makes part of the present disclosure. Annex A also contains a reference to twenty prior art publications. The same notation [1] . . . [20] used for those references in Annex A will be used throughout the description.
2. Description of the Prior Art
Prior art approaches in globally optimal scalar quantizer design for fixed-rate, single-encoder, single-decoder codes for finite-alphabet sources are known. See, for example, references [1], [2], [3], and [4] of Annex A.
A quantizer design algorithm for variable-rate scalar quantization is also known from reference [2] of Annex A, but is very slow.
Additionally, algorithms are known which handle both fixed- and variable-rate, single or multiple descriptions, by iterative methods, where the initial step is that of providing an arbitrary solution and then obtaining a better solution after each iteration. However, these algorithms do not necessarily yield an optimal quantizer, and have no bound on the running time.
Therefore, there is a need for a method for designing an optimal quantizer for signal encoding/decoding which can be applied to the multiple environments described above. Such method must also have a polynomial complexity.
SUMMARY OF THE INVENTION
The present invention overcomes the above limitations and problems by providing a method which finds a quantizer in single-description and multiple-description scenarios with polynomial complexity. Under appropriate conditions, explained throughout the following description, the quantizer is the optimal quantizer. In particular, the quantizer according to the present invention is optimal when it provides the optimum rate/distortion tradeoff. An optimum rate/distortion combination is a combination which makes the rate no larger than some specified allowed value and reduces distortion as much as possible. In particular, the improvement in the quantizer distortion associated with a small increase in rate is matched to a desired target value. The target value is chosen so that the distortion is minimized.
According to a first aspect of the present invention, a signal encoding system having a coder for encoding signals is provided, the coder including a quantizer and a lossless coder, the quantizer producing a distortion on the signals to be encoded, wherein the quantizer is an optimal quantizer under a rate/distortion tradeoff, so that the distortion is minimized when the rate of the optimal quantizer is no larger than a specified value.
According to a second aspect of the present invention, a signal decoding system having a decoder for decoding signals is provided, the decoder including a lossless decoder and an inverse quantizer wherein the inverse quantizer is an optimal quantizer under a rate/distortion tradeoff, so that the distortion is minimized when the rate of the optimal quantizer is no larger than a specified value.
According to a third aspect of the present invention, a s
Effros Michelle
Muresan Dan
California Institute of Technology
Ladas & Parry
Mehta Bhavesh M.
Sukhaphadhana Christopher
LandOfFree
Data compression method and system using globally optimal... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Data compression method and system using globally optimal..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Data compression method and system using globally optimal... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3294987