Image analysis – Image compression or coding
Reexamination Certificate
2000-10-27
2004-05-11
Couso, Jose L. (Department: 2621)
Image analysis
Image compression or coding
Reexamination Certificate
active
06735339
ABSTRACT:
TECHNICAL FIELD
The present invention pertains generally to audio and image coding systems and methods, and pertains more particularly to lossless compression techniques that can be used in audio and image coding systems to provide high levels of compression at low computational cost without requiring high-accuracy pre-defined probability distribution functions of the information to be compressed.
BACKGROUND ART
There is considerable interest among those in the fields of audio and image signal processing to reduce the amount of information required to represent audio and image signals without perceptible loss in signal quality. By reducing the amount of information required to represent such signals, the representations impose lower information capacity requirements upon communication paths and storage media. Of course, there are limits to the amount of reduction that can be realized without degrading the perceived signal quality.
Information capacity requirements can be reduced by applying either or both of two types of data compression techniques. One type, sometimes referred to as “lossy” compression, reduces information capacity requirements in a manner which does not assure, and generally prevents, perfect recovery of the original signal. Another type, sometimes referred to as “lossless” compression, reduces information capacity requirements in a manner that permits perfect recovery of the original signal.
Lossy Compression
Quantization is one well known digital lossy compression technique. Quantization can reduce information capacity requirements by reducing the number of bits used to represent each sample of a digital signal, thereby reducing the accuracy of the digital signal representation. The reduced accuracy or quantizing error is manifested as noise, therefore, quantization may be thought of as a process that injects noise into a signal. If the quantization errors are of sufficient magnitude, the quantizing noise will be perceptible and degrade the subjective quality of the coded signal.
Perceptual coding systems attempt to apply lossy compression techniques to an input signal without suffering any perceptible degradation by removing components of information that are imperceptible or irrelevant to perceived signal quality. A complementary decoding system can recover a replica of the input signal that is perceptually indistinguishable from the input signal provided the removed components are truly irrelevant.
So called split-band coding techniques are often used in perceptual coding systems because they can facilitate the analysis of an input signal to identify its irrelevant parts. A split-band encoder splits an input signal into several narrow-band signals, analyzes the narrow-band signals to identify those parts deemed to be irrelevant, and adaptively quantizes each narrow-band signal in a manner that removes these parts.
Split-band audio encoding often comprises the use of a forward or analysis filterbank to divide an audio signal into several subband signals each having a bandwidth commensurate with the so called critical bandwidths of the human auditory system. Each subband signal is quantized using just enough bits to ensure that the quantizing noise in each subband is masked by the spectral component in that subband and adjacent subbands. Split-band audio decoding comprises reconstructing a replica of the original signal using an inverse or synthesis filterbank. If the bandwidths of the filters in the filter banks and the quantization accuracy of the subband signals are chosen properly, the reconstructed replica can be perceptually indistinguishable from the original signal.
Two such coding techniques are subband coding and transform coding. Subband coding may use various analog and/or digital filtering techniques to implement the filterbanks. Transform coding uses various time-domain to frequency-domain transforms to implement the filterbanks. Adjacent frequency-domain transform coefficients may be grouped to define “subbands” having effective bandwidths that are sums of individual transform coefficient bandwidths.
Throughout the following discussion, the term “split-band coding” and the like refers to subband encoding and decoding, transform encoding and decoding, and other encoding and decoding techniques that operate upon portions of the useful signal bandwidth. The term “subband” refers to these portions of the useful signal bandwidth, whether implemented by a true subband coder, a transform coder, or other technique. The term “subband signal” refers to a split-band filtered signal within a respective subband.
Another lossy compression technique is called scaling. Many coding techniques including split-band coding convey signals using a scaled representation to extend the dynamic range of encoded information represented by a limited number of bits. A scaled representation comprises one or more “scaling factors” associated with “scaled values” corresponding to elements of the encoded signals. Many forms of scaled representation are known. By sacrificing some accuracy in the scaled values, even fewer bits may be used to convey information using a “block-scaled representation.” A block-scaled representation comprises a group or block of scaled values associated with a common scaling factor.
Lossless and Hybrid Compression
Lossless compression techniques reduce information capacity requirements of a signal without degradation by reducing or eliminating components of the signal that are redundant. A complementary decompression technique can recover the original signal perfectly by providing the redundant component removed during compression. Examples of lossless compression techniques include run-length encoding, adaptive and nonadaptive forms of differential coding, linear predictive coding, transform coding, and forms of so called entropy coding such as Huffman coding. Variations, combinations and adaptive forms of these compression techniques are also known.
Generally, the best levels of compression are achieved by hybrid techniques that combine lossless and lossy compression techniques. Two types of hybrid techniques are discussed below.
An example of the first hybrid type combines lossless transform coding with lossy vector quantization to quantize transform coefficients. Vector quantization uses a codebook of quantized values in an N-dimensional vector space and quantizes each source vector to the value that is associated with the closest codebook vector. Computational complexity for the process needed to find the closest vector increases geometrically as the dimension of the codebook vector space increases. In principle, vector quantization provides optimum encoding according to a rate-distortion theory, as discussed in Gersho and Gray, “Vector Quantization and Signal Compression,” Prentice-Hall, 1992; however, optimum performance is achieved only asymptotically as the dimension of the vector space approaches infinity. As a result, near-optimum coding performance can be achieved only in exchange for incurring much higher computational costs. Alternative quantization methods such as transform weighted interleaved vector quantization and pyramid vector quantization, described in Iwakami et al., “High Quality Audio Coding at Less than 64 kb/s by using Transform-Domain Weighted Interleaved Vector Quantization (TWIN-VQ),” IEEE Proc. of ICASSP, 1995, pp. 3095-98, and Cadel et al., “Pyramid Vector Coding for High Quality Audio Compression,” IEEE Proc. of ICASSP, 1996, may be used to reduce computational complexity. Unfortunately, even the computational cost of these methods is very high.
An example of the second hybrid type combines lossless transform coding with lossy uniform quantization of the transform coefficients and a subsequent lossless encoding of the quantized coefficients using, for example, Huffman encoding. The Huffman encoding technique uses a codebook that is based on a pre-determined probability distribution function (PDF) of input values, and that associates shorter-length codes to the more frequently occurring values. Both scalar-Huffman
Couso Jose L.
Dolby Laboratories Licensing Corporation
Gallagher & Lathrop
Lathrop, Esq. David N.
LandOfFree
Multi-stage encoding of signal components that are... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Multi-stage encoding of signal components that are..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Multi-stage encoding of signal components that are... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3242320