Wavelet image coder using trellis-coded quantization

[0002] The present application is based on prior U.S. application Ser. No. 08/886,502, filed on Jul. 1, 1997, which is hereby incorporated by reference, and priority thereto for common subject matter is hereby claimed.

[0003] This invention relates in general to image coders and, more particularly, to image coders utilizing wavelet decomposition and trellis coded quantization.

[0004] Image compression algorithms generally try to reduce the number of bits required to represent digital imagery while adhering to certain quantitative and subjective image fidelity criteria. Techniques such as JPEG (an algorithm which was standardized by Joint Pictures Expert Group to compress still imagery) and other more advanced designs utilizing variable-length entropy coding are extremely susceptible to channel errors. This susceptibility may make these types of image coders useless when operated over very noisy channels or where the amount of error protection (channel coding) required would not be acceptable.

[0005] What is needed is a very high-performance image coder which is robust to channel errors when operated over the binary symmetric channel. The coder should provide state-of-the-art performance with no channel errors present and graceful degradation as channel errors increase. Additionally, the coder should be of modest complexity to enable implementation on a variety of platforms. This type of coder would find application in wireless digital battlefield communications as well as any type of military system needing transmission of high-resolution imagery over noisy, low-bandwidth channels.

[0006] FIG. 1 is a block diagram illustrating a wavelet image coder/decoder in accordance with one embodiment of the present invention; and

[0007] FIG. 2 is a block diagram illustrating a wavelet image coder/decoder in accordance with another embodiment of the present invention.

[0008] There have been several approaches to designing quantizers which operate over binary symmetric channels (BSC). These have included channel-optimized scalar quantization (COSQ), for example, as discussed by N. Farvardin and V. Vaishampayan, in “Optimal Quantizer Design for Noisy Channels: An Approach to Combined Source-Channel Coding,” IEEE Trans, Inform. Theory,vol. 33, pp. 827-838, November, 1987 and channel-optimized trellis-coded quantization (COTCQ), for example, as discussed by M. Wang and T. R. Fischer, in “Trellis-Coded Quantization Designed for Noisy Channels,” IEEE Trans. Inform. Theory,vol. 40, pp. 1792-1802, November, 1994, among others, which publications are incorporated in Appendices B and C, respectively for their teachings, especially with respect to trellis coding (block 16) and decoding (block 30) publication “Robust Quantization For Image Coding and Noisy Digital Trnamission” by Q. Chen and T. R. Fischer, published in the Conference Proceedings of the Data Compression Conference, Snowbird, Utah, March, 1996, is incorporated in Appendix A.

[0009] As used herein, the term “binary symmetric channels” refers to a channel wherein noise causes some number of bits to “flip” at random, i.e., a bit that is supposed to be a logical one becomes a logical zero, or vice versa, and wherein the probability of a logical one becoming a logical zero is the same as the probability of a logical zero becoming a logical one. This behavior is typical of wireless channels having noise (block 28) and radio digital links are examples of binary symmetric channels.

[0010] Table 1 shows the obtained signal to noise ratio of COSQ when encoding the memoryless Gaussian, Laplacian, and generalized Gaussian (a=0.5) sources at 3 bits/sample, as a function of bit error probability (BEP). Also shown are the respective rate-distortion function values when BEP=0.005.

[0011] From Table 1, it is evident that the encoded performance of COSQ is opposite in order to that theoretically possible as seen from the rate-distortion functions. That is, COSQ achieves the best possible SNR performance when encoding the memoryless Gaussian source, and degraded performance when encoding all other generalized Gaussian sources with shape parameters α of less than 2. Note that these same general performance characteristics hold true when COTCQ is employed.

[0012] FIG. 1 serves as a simplified schematic view of a wavelet image coder/decoder system 8 using robust channel-optimized trellis-coded quantization in accordance with the teachings of the present invention. As illustrated, system 8 includes an image coder 6 that communicates digital images to an image decoder 7 via a channel 28. That is, the image coder 6 is, in the preferred embodiment, part of a transmitter and the image decoder 7 is part of a receiver in a communications system. In the preferred embodiment of the present invention, a robust quantization method is employed whereby the signal to be quantized (block 10) is all-pass filtered (block 14) to produce a signal with Gaussian statistics. Since the ideal all-pass filter does not change the frequency response magnitude, the implementation of the filtering operation can be done by changing the frequency phase response of the input. A simple way to do this is to scramble the phase spectra of the input source by adding some randomized reference phase spectra as prefiltering, and then adding the same, but negative reference phase spectra as postfiltering, to recover the original phase spectra of the source. A large variety of reference signals could be chosen. One possible choice of the reference phase spectra is the binary phase spectra of a pseudo-noise signal or the m-sequence. The size of the pseudo-noise signal should be the same as that of the input source. If the input source is a two-D signal (e.g., an image), the two-D quasi-m-array can be used as the pseudo-noise signal. The quasi-m-array is generated by two identical m-sequences. Since the binary pseudo-noise phase can be pre-computed and stored, prefiltering and postfiltering can be easily carried out, however, an FFT and inverse FFT are needed for each filtering operation, which increases the computational complexity of encoding and decoding. FIG. 3 of Appendix A shows the implementation of the all-pass filtering operation by phase-scrambling. Since fixed-rate channel-optimized trellis-coded quantization (block 16) is used, the performance curves obtained by quantizing the memoryless Laplacian source or any generalized Gaussian source (with shape parameter of a<2), will be elevated to the performance of the encoded Gaussian source. Fixed-rate channel-optimized trellis-code quantization (Block 16) is shown in sufficient detail for one of ordinary skill in the art to understand at page 1793 of Appendix C which is entitled “Trellis-Coded Qantization Designed For Noisy Channels”.

[0013] The all-pass filter is implemented by using a phase scrambling operation (block 14). The input sequence x(n) is transformed using an FFT, and pseudo-random noise is added to the phase component. An inverse FFT is then performed with the resulting sequence y(n) being (nearly) Gaussian distributed. In this way, the performance curve of a Gaussian channel-optimized quantizer can be achieved with a broad range of source distributions. Thus, a fixed (Gaussian) rate-distortion performance is guaranteed, independent of the source distribution.

[0014] In image decoder 7, phase descrambling (block 32) is accomplished via a similar sequence of operations as were employed for the scrambling (block 14) using the same (but negative reference) pseudo-random noise sequence to recover the phase in the restored image (block 38). The descrambling operation (Block 32) is similar to that described above for the phase scrambling operation (Block 14) and is shown in detail beginning at the last paragraph of page 6 and continuing through to FIG. 3 at page 7 of Appendix A as was mentioned above.

[0015] For operation over binary symmetric channel 28, a channel optimized version of trellis-coded quantizing encoder 16 and decoder 30 was developed, as is discussed by M. Wang and T. R. Fischer, in “Trellis-Coded Quantization Designed for Noisy Channels,” IEEE Trans. Inform. Theory,vol. 40, pp. 1792-1802, November, 1994, which is hereby incorporated by reference. It is shown that for bit error probabilities greater than 0, a 4-state COTCQ system outperformed 8-dimensional channel-optimized vector quantization (COVQ) for encoding the memoryless Gaussian source. Moreover, the COTCQ system greatly outperforms the COSQ system reported in N. Farvardin and V. Vaishampayan, “Optimal Quantizer Design for Noisy Channels: An Approach to Combined Source-Channel Coding,” IEEE Trans. Inform. Theory,vol. 33, pp. 827-838, November, 1987. For implementation of trellis-coding quantization decoding (Block 30) see again, page 1793 of Appendix C. This is explained similar to that for the encoding process (Block 16) as was mentioned above.

[0016] Image coder 6 of the instant invention is based on wavelet decomposition (block 12) used in conjunction with robust channel-optimized trellis-coded quantization (block 16). Input image 10 is transformed using the 2-D discrete wavelet transform 12 (DWT) into 16 equal-sized subbands. The lowest frequency subband (LFS) is partitioned into non-overlapping 4×4 blocks (block 18) and transformed using 2-D discrete cosine transform 20 (DCT). The lowest frequency subband contains 90%-95% of the energy in input image 10 and tends to be characterized by a high degree of spatial correlation, i.e., if two consecutive bits are known, the next bit can be estimated or guessed. The higher frequency subbands tend to have a low degree of correlation and therefore do not require the discrete cosine transform process (which results in a sequence having substantially less correlation). “Like” DCT coefficients (i.e., those coefficients corresponding to the same DCT frequency position within each 4 by 4 block) are collected into sequences as are the remaining 15 high-frequency subbands (block 20). Each sequence is separately all-pass filtered (using the phase scrambling technique, block 14) and encoded (block 16) using fixed-rate channel-optimized TCQ designed for the memoryless Gaussian source.

[0017] In calculating statistics (block 22) for the data, the sequence corresponding to the DC discrete cosine transform coefficients has nonzero mean while the remaining “non-DC” discrete cosine transform coefficient sequences as well as the 15 high-frequency subbands are assumed to have a mean of zero. All discrete cosine transform and high-frequency subbands are normalized by subtracting their mean (only the sequence corresponding to the DC or lowest frequency subband transform coefficients has non-zero mean) and by dividing by their respective standard deviations (block 22). These quantities are quantized (block 24) using 8-bit uniform scalar quantization and are sent directly via the digital channel (block 28) while sequence variances are processed to determine a rate allocation (block 26) that provides an optimal signal to noise ratio (SNR) when the image data are trellis-coded quantization encoded (block 16). A greater variance corresponds to greater signal energy and this in turn determines the number of bits to be selected for optimal signal to noise properties in the encoded signal. In other words, a choice between 2, 4 etc. bit encoding is made based on rate distortion characteristics describing predetermined signal to noise characteristics and the required bit rate, as is described in “Efficient Bit Allocation For An Arbitrary Set Of Quantizers”, by Shoham et al., IEEE Trans. Acoust., Speech, Signal Processing,vol. ASSP-36, no. 9, pp. 1445-1453, September 1988, which is hereby incorporated by reference.

[0018] Following transmission (block 28), received data are decoded (block 30), the phase is descrambled (block 32) and an inverse discrete cosine transform of the lowest frequency subband is performed (block 34). Wavelet reconstruction (block 36) recombines the sixteen subbands into an output image 38.

[0019] Image coder 16, 30 of the instant invention is an extension of the coder presented in the paper “Robust Quantization for Image Coding and Noisy Digital Transmission” by Chen et al., in Conf. Proceedings,Data Compression Conference, Snowbird, Utah, March, 1996, which is hereby incorporated in Appendix A. It is based on COSQ and utilizes a 13-band pyramid decomposition.

[0020] Applicant has discovered that a symmetric 16-band decomposition with 2-D DCT encoding (block 20) of the LFS provides significantly higher performance than the 13-band system. Additionally, applicant has also discovered that entropy-constrained TCQ (ECTCQ) utilized in a system similar to the one discussed here, vastly outperforms (both quantitatively and subjectively) the identical system using entropy-constrained scalar quantization (ECSQ). Applicant expects a similar increase in performance by using COTCQ as opposed to COSQ, especially when the BEP is less than 0.05. Moreover, applicant expects this coder to exhibit the same graceful degradation characteristics with increasing channel BEP as shown in Q. Chen and T. R. Fischer, “Robust Quantization for Image Coding and Noisy Digital Transmission,” in Conf. Proceedings,Data Compression Conference, Snowbird, Utah, March, 1996.

[0021] Thus, a technique has been described which overcomes specific problems and accomplishes certain advantages relative to prior art methods and mechanisms. The improvements over known technology are significant. This technique combines a method for converting any memoryless sequence to a Gaussian sequence (robust quantization) for more efficient quantization, with wavelet decomposition, channel-optimized trellis-coded quantization, and optimal rate allocation, to produce an image coder providing state-of-the-art image compression performance when operated over extremely noisy channels. This algorithm may be implemented in hardware and/or software in any system utilizing wireline or wireless communications where high-quality, low-bit-rate image transmission over extremely noisy channels.

[0022] FIG. 2 is a block diagram illustrating a wavelet image coder/decoder system 40 in accordance with another embodiment of the present invention. Where possible, the same reference numerals are used in FIG. 2 that were used in FIG. 1 to describe similar functionality. As illustrated, the wavelet coder/decoder system 40 does not include the lowest frequency subband (LFS) extraction unit 18 or the discrete cosine transform (DCT) unit 20 of the image coder 6 of FIG. 1. In addition, the wavelet coder/decoder system 40 does not include the inverse discrete cosine transform unit 34 of the image coder 6 of FIG. 1. Instead of processing the LFS using a DCT, the wavelet coder/decoder system 40 further decomposes the LFS with additional levels of wavelet decomposition. In addition, the wavelet coder/decoder system 40 uses a different form of trellis coded quantization (i.e., fixed rate TCQ) than the system 8 of FIG. 1.

[0023] As with the previously described system, the coder/decoder system 40 is a non-entropy-coded design utilizing wavelet decomposition, trellis-coded quantization (TCQ), and frequency-domain phase scrambling. The coder/decoder system 40 combines attributes from the robust quantization design reported in Chen et al. (discussed above) and the wavelet/TCQ coders reported in the papers “Hyperspectral Image Coding Using Wavelet Transforms and Trellis Coded Quantization” by G. P. Abousleman, Wavelet Applications II,H. Szu, Editor, Proc. SPIE 2491, 1995, and “Image Coding Using Wavelet Transforms and Entropy-Constrained Trellis-Coded Quantization” by Sriram et al., IEEE Trans. Image Processing,vol. 4, June, 1995, both of which are hereby incorporated by reference.

[0024] The system 8 of FIG. 1 is designed for use with noisy channels, and, therefore, it was determined that COTCQ quantization techniques would be used in the trellis coded quantization encoding unit 16. Use of COTCQ generally requires a large matrix of codebooks to be generated that includes one set of codebooks for every operational channel bit error rate. The system 40 of FIG. 2, on the other hand, is designed for use with a channel that approximates a noiseless channel and, therefore, it was determined that the less complex fixed rate trellis coded quantization (FRTCQ) would be used in the trellis coded quantization encoding unit 42. FRTCQ uses a different rate allocation scheme than COTCQ and thus requires a much smaller number of codebooks and less codebook storage than the COTCQ system. In a preferred embodiment, only 8 codebooks are used (the largest of which is only 512 codewords in length) requiring less than 1024 floating-point codewords of codebook storage. The system 40 of FIG. 2 is designed for use in a communications system that utilizes some form of channel noise mitigation to approximate a noiseless channel. For example, in one embodiment of the invention, the system 40 is implemented in a communications system that utilizes adaptive-rate coded digital image transmission to reduce the effects of noise in the channel. Adaptive-rate coded digital image transmission refers to a system that is capable of adapting transmission characteristics based on the present condition of the channel 28, as sensed in the transmitter or, preferably, in the receiver (as discussed in a co-owned, co-pending application entitled “Adaptive-Rate Coded Digital Image Transmission” having inventors Kleider and Abousleman, which is hereby incorporated by reference).

[0025] The following discussion is with reference to FIG. 2. As before, the signal to be quantized is all-pass filtered to produce a signal with Gaussian statistics. The all-pass filter is implemented using a phase scrambling operation in the phase scrambling unit 14. That is, the input sequence, x(n), is transformed using the fast Fourier transform (FFT), and separated into its magnitude and phase components. The phase spectrum of an appropriate reference function is then added to the phase spectrum of the input sequence. An inverse FFT is then performed with the resulting sequence, y(n), being (nearly) Gaussian distributed. In this way, the performance curve of a Gaussian-optimized quantizer can be achieved with a broad range of source distributions.

[0026] A convenient reference function for the all-pass filtering operation is the binary pseudo-noise (PN) sequence, also known as the m-sequence. The m-sequence is chosen because of its ease of generation and its autocorrelation properties. The sequence utilized in the system discussed herein is generated from a feedback shift register corresponding to the 16th-order primitive polynomial x¹⁶+x⁵+x³+x+1 [11]. The sequence is then truncated to the appropriate length (as determined by the size of a given subband) prior to Fourier transformation, thus guaranteeing frequency-domain phase symmetry.

[0027] In a preferred embodiment, the image to be encoded is decomposed into 22 subbands using a modified Mallat tree configuration in the wavelet decomposition unit 12. That is, the image is initially decomposed into 16 equal-sized subbands, with two additional levels of decomposition being applied to the lowest-frequency subband. Decomposition is preferably performed using a plurality of high pass filters and low pass filters. Each subband is collected into a one-dimensional sequence and separately all-pass filtered in the phase scrambling unit 14 and encoded using fixed-rate trellis coded quantization (FRTCQ) in the trellis coded quantization encoding unit 16 designed for the memoryless Gaussian source. A discussion of FRTCQ can be found in the paper “Trellis Coded Quantization of Memoryless and Gauss-Markov Sources” by Marcellin et al., IEEE Trans. Commun.,vol. 38, Jan, 1990, which is hereby incorporated in Appendix D. Sections III-V, pages 83-86, of Appendix D show a fixed rate trellis coded quantization (FRTCQ) unit for performing a FRTCQ on phase scrambled frequency subbands. All subbands are normalized by subtracting their mean (only the sequence corresponding to the lowest-frequency subband is assumed to have non-zero mean) and dividing by their respective standard deviations. The mean values and standard deviation values are determined in the calculate statistics unit 22.

[0028] The total side information to be transmitted consists of the mean value of the lowest-frequency subband and the standard deviation values of all 22 subbands. In a preferred embodiment, these quantities are quantized with 16-bit uniform scalar quantizers using a total of 368 bits in the scalar quantizer unit 24. The compression ratio is also transmitted and allotted 10 bits. These quantities are assumed to be transmitted with no channel errors. Finally, the initial trellis state (for use in the TCQ encoding unit 16) for each encoded sequence requires 2 bits (for a 4-state trellis). The total side information then consists of 422 bits per image.

[0029] Fixed-rate TCQ codebooks are designed in one-bit increments from 1 to 8 bits/sample. The training sequence consisted of 100,000 samples derived from a Gaussian pseudo random number generator. Codebook design uses a modified version of the generalized Lloyd algorithm for vector quantizer design.

[0030] Rate allocation is performed in the rate allocation unit 26 by using the iterative technique discussed in Shoham et al. The algorithm allocates bits based on the rate-distortion performance of the various trellis-based quantizers and the energy content of the wavelet coefficients. This rate allocation procedure allows precise bit rate specification, independent of the image to be coded.

[0031] The foregoing description of the specific embodiments will so fully reveal the general nature of the invention that others can, by applying current knowledge, readily modify and/or adapt for various applications such specific embodiments without departing from the generic concept, and therefore such adaptations and modifications should and are intended to be comprehended within the meaning and range of equivalents of the disclosed embodiments.

[0032] It is to be understood that the phraseology or terminology employed herein is for the purpose of description and not of limitation. Accordingly, the invention is intended to embrace all such alternatives, modifications, equivalents and variations as fall within the spirit and broad scope of the appended claims.

[Inline image omitted. See PDF.]



[Inline image omitted. See PDF.]



[Inline image omitted. See PDF.]



[Inline image omitted. See PDF.]



[Inline image omitted. See PDF.]



[Inline image omitted. See PDF.]



[Inline image omitted. See PDF.]



[Inline image omitted. See PDF.]



[Inline image omitted. See PDF.]



[Inline image omitted. See PDF.]



[Inline image omitted. See PDF.]



[Inline image omitted. See PDF.]



[Inline image omitted. See PDF.]



[Inline image omitted. See PDF.]



[Inline image omitted. See PDF.]



[Inline image omitted. See PDF.]



[Inline image omitted. See PDF.]



[Inline image omitted. See PDF.]



[Inline image omitted. See PDF.]



[Inline image omitted. See PDF.]



[Inline image omitted. See PDF.]



[Inline image omitted. See PDF.]



[Inline image omitted. See PDF.]



[Inline image omitted. See PDF.]



[Inline image omitted. See PDF.]



[Inline image omitted. See PDF.]



[Inline image omitted. See PDF.]



[Inline image omitted. See PDF.]



[Inline image omitted. See PDF.]



[Inline image omitted. See PDF.]



[Inline image omitted. See PDF.]



[Inline image omitted. See PDF.]



[Inline image omitted. See PDF.]



[Inline image omitted. See PDF.]



[Inline image omitted. See PDF.]



[Inline image omitted. See PDF.]



[Inline image omitted. See PDF.]



[Inline image omitted. See PDF.]



[Inline image omitted. See PDF.]



[Inline image omitted. See PDF.]



[Inline image omitted. See PDF.]



[Inline image omitted. See PDF.]



[Inline image omitted. See PDF.]



[Inline image omitted. See PDF.]