Image analysis – Image compression or coding – Quantization
Reexamination Certificate
1998-09-30
2001-12-11
Couso, Jose L. (Department: 2621)
Image analysis
Image compression or coding
Quantization
Reexamination Certificate
active
06330370
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates generally to multiple description transform coding (MDTC) of signals for transmission over a network or other type of communication medium, and more particularly to MDTC of images.
BACKGROUND OF THE INVENTION
Multiple description transform coding (MDTC) is a type of joint source-channel coding (JSC) designed for transmission channels which are subject to failure or “erasure.” The objective of MDTC is to ensure that a decoder which receives an arbitrary subset of the channels can produce a useful reconstruction of the original signal. One type of MDTC introduces correlation between transmitted coefficients in a known, controlled manner so that lost coefficients can be statistically estimated from received coefficients. This correlation is used at the decoder at the coefficient level, as opposed to the bit level, so it is fundamentally different than techniques that use information about the transmitted data to produce likelihood information for the channel decoder. The latter is a common element in other types of JSC coding systems, as shown, for example, in P. G. Sherwood and K. Zeger, “Error Protection of Wavelet Coded Images Using Residual Source Redundancy,” Proc. of the 31
st
Asilomar Conference on Signals, Systems and Computers, November 1997. Other types of MDTC may be based on techniques such as frame expansions, as described in V. K. Goyal et al., “Multiple Description Transform Coding: Robustness to Erasures Using Tight Frame Expansions,” In Proc. IEEE Int. Symp. Inform. Theory, August 1998.
A known MDTC technique for coding pairs of independent Gaussian random variables is described in M. T. Orchard et al., “Redundancy Rate-Distortion Analysis of Multiple Description Coding Using Pairwise Correlating Transforms,” Proc. IEEE Int. Conf. Image Proc., Santa Barbara, Calif., October 1997. This MDTC technique provides optimal 2×2 transforms for coding pairs of signals for transmission over two channels. However, this technique as well as other conventional techniques fail to provide optimal generalized n×m transforms for coding any n signal components for transmission over any m channels. In addition, conventional transforms such as those in the M. T. Orchard et al. reference fail to provide a sufficient number of degrees of freedom, and are therefore unduly limited in terms of design flexibility. Moreover, the optimality of the 2×2 transforms in the M. T. Orchard et al. reference requires that the channel failures be independent and have equal probabilities. The conventional techniques thus generally do not provide optimal transforms for applications in which, for example, channel failures either are dependent or have unequal probabilities, or both. These and other drawbacks of conventional MDTC prevent its effective implementation in many important applications.
SUMMARY OF THE INVENTION
The invention provides MDTC techniques which can be used to implement optimal or near-optimal n×m transforms for coding any number n of signal components for transmission over any number m of channels. A multiple description (MD) joint source-channel (JSC) encoder in accordance with an illustrative embodiment of the invention encodes n components of an image signal for transmission over m channels of a communication medium, in applications in which at least one of n and m may be greater than two, and in which the failure probabilities of the m channels may be non-independent and non-equivalent.
In accordance with one aspect of the invention, the MD JSC encoder may be configured to provide statistical redundancy between different descriptions of the image signal. For example, the encoder may form vectors from discrete cosine transform (DCT) coefficients of the image signal separated both in frequency and in space. The vectors may be formed such that the spatial separation between the DCT coefficients is maximized. A correlating transform is applied to the resulting vectors, followed by entropy coding, grouping of the coded vectors as a function of frequency, and application of a cascade transform to each of the groups, in order to generate the multiple descriptions of the image signal.
In accordance with another aspect of the invention, the MD JSC encoder may be configured to provide deterministic redundancy between different descriptions of the image signal. For example, the encoder may form vectors from DCT coefficients of the image signal so as to include coefficients of like frequency separated in space. The vectors are expanded by multiplication with a frame operator, and then quantized using a step size which may be a function of frequency, in order to generate the multiple descriptions of the image signal. In both the statistical redundancy and deterministic redundancy embodiments noted above, other types of linear transforms may be used in place of the DCT.
An MD JSC encoder in accordance with the invention may include a series combination of N “macro” MD encoders followed by an entropy coder, and each of the N macro MD encoders includes a parallel arrangement of M “micro” MD encoders. Each of the M micro MD encoders implements one of: (i) a quantizer block followed by a transform block, (ii) a transform block followed by a quantizer block, (iii) a quantizer block with no transform block, and (iv) an identity function. In addition, a given n×m transform implemented by the MD JSC encoder may be in the form of a cascade structure of several transforms each having dimension less than n×m. This general MD JSC encoder structure allows the encoder to implement any desired n×m transform while also minimizing design complexity.
The MDTC techniques of the invention do not require independent or equivalent channel failure probabilities. As a result, the invention allows MDTC to be implemented effectively in a much wider range of applications than has heretofore been possible using conventional techniques. The MDTC techniques of the invention are suitable for use in conjunction with signal transmission over many different types of channels, including, for example, lossy packet networks such as the Internet, wireless networks, and broadband ATM networks.
REFERENCES:
patent: 5836003 (1998-11-01), Sadeh
patent: 6018303 (2000-01-01), Sadeh
Batllo et al., Asymptotic Performance of Multiple Description Transform Codes, IEEE Trans. on Infor. Theor., vol. 43, No. 2, pp. 703-709, Mar. 1997.*
The Bell System Technical Journal, “Source Coding” pp. 1681-1721, Nov. 1974.*
Orchard et al., Redundancy Rate-Distortrion Analysis of Multiple Description Coding using Pair wise Correlating Transtorms, IEEE, pp. 608-611, 1997.*
Batllo et al., Multiple Description Transform Codes with an Application to Packetized Speech, IEEE, p. 458, 1994.*
Batllo et al., “Multiple Description Source Encoding of Gaussian Random Variable: A Geometric Treatment”, IEEE, p. 273, 1997.*
Yang et al. Low Delay Communication for Raleigh Fading Channels: An Application of the Multiple Description Quantizers, IEEE Trans. on Comm., vol. 43, No. 11, pp. 2771-2783, 1995.*
Vaishampayan, “Design of Multiple Description Scalar Quantizers”, IEEE Trans. on Inf. The, vol. 39, No. 3, pp. 821-834.*
Subrahmanya et al. “Multiple Descriptions Encoding of Images” pp. 1-10, 1996.*
Pentland, Alex, “Multiple Model encoding of Images”, MIT, pp 1509-1513, 1993.*
Zhang et al., “New Results in Binary Multiple Descriptions”, IEEE Trans. on Information Th; Vol. IT-33, No. 4, pp. 502-521, 1987.*
Vaishampayan et al., “Asymtotic Analysis of Multiple Description Quantizers”, IEEE Trans. a Inf. Th., pp. 1-20, 1997.*
Vaishampayan, Vinay A., Application of Multiple Description Codes to Image and Video Transmission over Lassy Networks, 7th International Workshop on Packet video. pp 1-6, 1996.*
V.K. Goyal et al., “Multiple Description Transform Coding: Robustness to Erasures Using Tight Frame Expansions,” In Proc. IEEE Int. Symp. Inform. Theory, Aug. 1998.
V.K. Goyal and J Kovacevic, “Optimal Multiple Description Transform Coding of Gaussian Vectors,” In Proc. IEEE Data Compr
Goyal Vivek K.
Kovacevic Jelena
Vetterli Martin
Couso Jose L.
Lucent Technologies - Inc.
Ryan & Mason & Lewis, LLP
LandOfFree
Multiple description transform coding of images using... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Multiple description transform coding of images using..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Multiple description transform coding of images using... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2569588