Coded data generation or conversion – Digital code to digital code converters
Reexamination Certificate
1999-01-20
2001-03-06
Young, Brian (Department: 2819)
Coded data generation or conversion
Digital code to digital code converters
C341S067000, C382S190000
Reexamination Certificate
active
06198412
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates generally to encoding of audio, video, images, speech and other types of information signals, and more particularly to memory-efficient encoding techniques for use with such signals.
BACKGROUND OF THE INVENTION
FIG. 1
shows a conventional transform encoder
10
having a structure common to many well-known audio, video and image coding standards. This common encoder structure includes a linear transform
12
, a scalar quantizer
14
, and an entropy coder
16
, arranged in that order. Transform coding of this type is generally viewed as a computationally efficient alternative to vector quantization. At high encoding rates, it is typically not the transform partitioning itself but the efficiency of the entropy coder that makes transform coding most useful. In the transform encoder
10
, the transform is calculated on continuous-value data, i.e., “full precision” data prior to quantization, even though the data will ultimately be represented more coarsely. This also tends to increase the complexity of the subsequent entropy coding operations. Although developments such as zero-tree structures, described in J. M. Shapiro, “Embedded image coding using zero trees of wavelet coefficients,” IEEE Trans. Signal Proc., 41(12):3445-3462, December 1993, mix the quantization and entropy coding operations to some degree, the transform is generally still calculated on continuous-value data.
In traditional transform coding of the type illustrated in
FIG. 1
, the input is generally a continuous-valued random vector sequence {tilde over (x)}, and it is presumed that the entropy coder
16
uses scalar entropy coding. The problem is then to design a continuous-valued linear transform {tilde over (T)} such that x=Q({tilde over (T)}({tilde over (x)})) is coded efficiently with scalar entropy coding, where x=(x
1
, x
2
, . . . x
n
) is a discrete-valued random vector and Q is a scalar quantization function. The average rate for entropy coding of x is lower bounded by the entropy: H(x)≦R(x), where H(•) denotes the entropy of a random variable and R(•) denotes the rate obtained with an actual code. Subscripts on R will be used herein to distinguish between specific codes, when necessary. In addition, there is always a code that performs within one bit of the entropy, i.e., R(x)<H(x)+1. A Huffman code is an example of one such code.
Scalar entropy coding separately encodes each of the n components of x. This separate encoding can reduce the memory requirements and encoding complexity in many applications, but may also result in an increase in encoding rate. There are two causes of this increase. First, the dependencies between components may not be completely exploited. This is reflected by the following basic property of entropy:
H
(
x
1
,
x
2
,
…
x
n
)
≤
∑
i
=
1
n
H
(
x
i
)
Second, when using an entropy code, one may do as much as one bit worse than the above-noted entropy bound, i.e., R
0
(x)≦H(x)+1. Thus, using n separate codes may waste n bits:
∑
i
=
1
n
R
i
(
x
i
)
≤
H
(
x
i
)
+
n
.
In the above-described traditional transform coding framework, the conventional approach is to pick the continuous-valued linear transform {tilde over (T)} from among a set of orthogonal transforms, as described in, e.g., A. Gersho and R. M. Gray, “Vector Quantization and Signal Compression,” Kluwer Acad. Pub., Boston, Mass. 1992. Use of a nonorthogonal transform would generally make the quantizer less effective. Among the orthogonal transforms, there is an essentially unique transform, known as a Karhunen-Loève transform, that minimizes the rate after scalar entropy coding. It was observed in M. T. Orchard et al., “Redundancy Rate-Distortion Analysis of Multiple Description Coding Using Pairwise Correlating Transforms,” Proc. IEEE Int. Conf. Image Proc., Vol. 1, pp. 608-611, Santa Barbara, Calif., October 1997, that if a continuous-valued vector {tilde over (x)} with independent components is first quantized and then transformed, i.e., such that x=T(Q({tilde over (x)})), then there is no need to limit the set of transforms. Generalizations to arbitrary dimension transform coding in the multiple description transform context are described in U.S. patent application Ser. No. 09/030,488 filed Feb. 25, 1998 in the name of inventors Vivek K. Goyal and Jelena Kovacevic and entitled “Multiple Description Transform Coding Using Optimal Transforms of Arbitrary Dimension.”
The above-described conventional approaches can suffer from significant drawbacks. For example, in traditional transform coding, all of the degrees of freedom in the design are generally used to minimize the rate, with the result that no degrees of freedom are left for other manipulations.
It is therefore generally not possible, using the conventional transform coding techniques described above, to minimize the entropy coding rate and simultaneously pursue other important objectives such as memory reduction. Conventional encoding techniques are therefore unduly complex, and often consume excessive storage and computational resources.
SUMMARY OF THE INVENTION
The invention provides transform encoding techniques which allow entropy coding to be simplified, e.g., to be carried out with reduced memory requirements, and without a substantial increase in the entropy coding rate. In an illustrative embodiment, a selected discrete linear transform is applied to a discrete-valued version of an information signal to be encoded. The transform is selected such that it produces a transformed output that can be entropy coded using a reduced codeword memory, i.e., fewer codewords, relative to the codeword memory required to encode the information signal without the transform. In one example of a particular implementation of this embodiment, the entropy coding may be, for example, scalar entropy coding which independently codes each of the components of the transformed discrete-valued version of the information signal, using a single entropy codebook for all of the components to be encoded. In this case, the reduced codeword memory in terms of number of codewords required is given approximately by the following expression:
(
∏
i
=
1
n
N
i
)
1
/
n
,
in which n is the number of components in the discrete-valued version of the information signal, and N
i
is the number of codewords needed to encode the ith component of the information signal without the linear transform of the invention. This represents a reduction in required codeword memory by a factor of about 1
.
As another example of a particular implementation of the illustrative embodiment, the entropy coding may utilize scalar entropy coding for a first subset of the components of the transformed discrete-valued version of the information signal, using a first codebook for each of the subset of components to be encoded, and vector entropy coding for a second subset of the components, using a second, larger codebook for each of the vectors to be encoded. In this case, the selected transform operates on the discrete-valued version of the information signal such that the components of the transformed discrete-valued version of the information signal have specified standard deviations. Other types of entropy coding can also be improved through appropriate selection of the discrete transform.
The improved coding techniques of the invention are suitable for use in any system with entropy coding. For example, the techniques of the invention are suitable for use in encoding all forms of discrete information for subsequent storage, transmission or processing.
REFERENCES:
patent: 5589829 (1996-12-01), Astle
patent: 5917943 (1999-06-01), Washizawa
P.G. Sherwood et al., “Error Protection of Wavelet Coded Images Using Residual Source Redundancy,” Proc. of the 31stAsilomar Conference on Signals, Systems and Computers, Nov. 1997.
M.T. Orchard et al., “Redundancy Rate-Distortion Analysis of Multiple Description Coding Using Pairwise
Lucent Technologies - Inc.
Nguyen John
Ryan & Mason & Lewis, LLP
Young Brian
LandOfFree
Method and apparatus for reduced complexity entropy coding 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 and apparatus for reduced complexity entropy coding, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for reduced complexity entropy coding will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2528796