Back to publication index

Recovering from Bit Errors in Scalar-Quantized Discrete Wavelet Transformed Images

Alexander E. Mohr	Eve A. Riskin	Richard E. Ladner 1
Electrical Engineering	Electrical Engineering	Computer Science
University of Washington	University of Washington	University of Washington
Seattle, WA  98195-2500	Seattle, WA  98195-2500	Seattle, WA  98195-2350
[email protected]	[email protected]	[email protected]

Appears in the Proceedings of the 1998 International Conference on Image Processing (ICIP'98). 5 pages.
ps (2.22M) - pdf (1.58M) - ps.gz (957k) - pdf.gz (952k) - DOS-format ps (2.25M).

Abstract

In this paper we study the effects of transmission noise on fixed-length coded wavelet coefficients. We extend our previous work on maximum a posteriori detectors [1] to include inter-bitplane information and determine which transmitted codeword was most likely corrupted into a received erroneous codeword. We present a simple method of recovering from these errors once detected and demonstrate our restoration methodology on scalar-quantized wavelet coefficients that have been transmitted across a binary symmetric channel.

   
Introduction

The wavelet transform [2] is a tool for space-frequency analysis that uses wavelet basis functions to decompose signals in L²(R) into distinct frequency subbands, each of which corresponds to different scale information. The 2-dimensional discrete wavelet transform (DWT) decomposes an image into high and low frequency components along each image dimension. Figure 1 shows a 3-level DWT. Wavelets used for lossy transform compression have provided some of the best compression performance to date [3,4]. The question of robustness to transmission noise and error is beginning to be explored; many of these encoded bit streams are not robust when transmitted without explicit error control codes [5]. We use a discrete wavelet image that has been quantized by an organized quantizer to present a simple method of recovering from bit errors introduced by a binary symmetric channel.

  

Figure 1: The ten subbands in a 3-level Discrete Wavelet Transform. The lowest-frequency information is in the s3-s3 subband and the highest-frequency information is in the d1-d1 subband.

We use fixed-length scalar quantization codebooks that have been organized progressively. As a result, errors in the most significant bits of a codeword index result in large changes in the coefficient value, which are easily detected, while errors in the least significant bits of a codeword index result in only minor changes in the coefficient value, rendering them less important to correct. Our motivations for using scalar quantization are that (1) it has been widely studied and (2) it provides a clear framework within which to study the effects of channel noise on codeword indexes.

   
Approach

Our algorithm exploits the redundancy, or correlation, that remains in the low-frequency subbands. Because of that redundancy, a coefficient's neighbors can give some insight into the expected range of values for the central coefficient. If a coefficient has a value that is outside of the expected range, it is possible that the codeword index has been corrupted by bit errors. For low bit error rates (less than 5%), it is also probable that an erroneous codeword index differs in only one bit from the correct one.

  

Figure 2: The eight neighboring coefficients of the central codeword.

Our correction algorithm has two components. The first component corrects bit errors in codeword indexes, while the second modifies coefficient values directly. The bit-correction component begins by examining the eight neighbors of the received codeword, as in Figure 2, and sorting them in ascending order of the coefficients. It then discards the highest and lowest values on the supposition that they might be erroneous, and determines if the central coefficient falls within the range determined by the remaining values.

If the central coefficient falls outside of that range, it is deemed a probable error. When that situation occurs, the bit-correction component compares all codewords with a Hamming distance of one from the erroneous codeword, and selects the one that would best fit within the previously established range. Note that this is similar to median filtering, but we examine a broad range of replacement values and only correct the bit that was the most likely to be corrupt.

The second component applies essentially the same approach as the first component; however, it corrects coefficient values instead of codeword indexes. This component employs a non-linear filter: if the central coefficient is within the range of expected values after discarding the highest and lowest neighbors, then the central coefficient is left unchanged. Otherwise, it is replaced with the value of the nearest remaining neighbor.

Our correction method begins by applying the bit-correction component to the indexes of the s3-s3 subband from Figure 1. The indexes are then converted to actual coefficient values, and the non-linear filter is applied to the s3-s3 subband. From that point on, reconstruction of one level of the DWT alternates with an application of the non-linear filter to the newly constructed subband. For example, the corrected s3-s3 subband is combined with the raw s3-d3, d3-s3, and d3-d3 subbands, using an inverse DWT to generate the raw s2-s2 subband. The non-linear filter is then applied to the raw s2-s2 subband. Next, the corrected s2-s2 subband is combined with the raw s2-d2, d2-s2, and d2-d2 subbands to generate the raw s1-s1 subband, which is then non-linear filtered, and so on. This process is repeated until the entire reconstructed image is obtained and filtered.

   
Results

To determine the effectiveness of the combination of codeword index replacement and recursive application of non-linear filtering, we used the standard 8-bit 512 $\times$ 512 Lenna. We chose a 3-level DWT using the Daubechies 4-tap filter, quantized each subband at 8 bits per coefficient, and introduced errors into the bits at a rate of 1 percent. Figure 3 shows the reconstructed image without correction.

  

Figure 3: A reconstruction of Lenna without any correction. The PSNR is 23.74 dB.

An example of the progression of our algorithm as it corrects an image is presented in Figures 4, 5, and 6. The final reconstructed image is presented in Figure 7. Compare it to the image in Figure 3 when no correction is used.

  

Figure 4: The received s3-s3 subband of the Lenna image magnified by a factor of 8 (top). The corrected s3-s3 subband (bottom).

  

Figure 5: The raw s2-s2 subband of the Lenna image magnified by a factor of 4. It is generated from the corrected s3-s3 subband and the raw s3-d3, d3-s3, and d3-d3 subbands (top). The corrected s2-s2 subband (bottom).

  

Figure 6: The raw s1-s1 subband of the Lenna image magnified by a factor of 2. It is generated from the corrected s2-s2 subband and the raw s1-d1, d1-s1, and d1-d1 subbands (top). The corrected s1-s1 subband (bottom).

  

Figure 7: The raw entire Lenna image. It is generated from the corrected s1-s1 subband and the raw s1-d1, d1-s1, and d1-d1 subbands (top). The final corrected image with a PSNR of 27.54 dB (bottom) [Note: Image resolution reduced for HTML version].

The peak signal-to-noise (PSNR) is 23.74 dB for the received image in Figure 3 and 27.54 dB for the corrected image in Figure 7. In this case, our correction method increased the PSNR by 3.80 dB, with an obvious improvement in picture quality. We also tested some other filtering methods. A 3 $\times$ 3 median filter on the uncorrected image resulted in a PSNR of 25.30 dB, while a 3 $\times$ 3 averaging filter yielded a PSNR of 25.13 dB.

   
Summary

The performance of our correction method is based upon exploiting the correlation between a wavelet coefficient and its neighbors. In the initial bit-correction step, our algorithm finds the codeword index that is the best match for the codeword's neighborhood. In the subsequent coefficient filtering steps, it uses a non-linear filter that moves outliers closer to the median. By alternating a reconstruction phase with a correction phase, our method corrects errors at each scale of the image.

Future Work

In our future work, we will examine the situation in which an image is transmitted across a packet loss channel. Although some preliminary work in this area has been done [6], we think unequal error protection schemes look promising. They have worked well with the transmission of video sequences [7] and our preliminary results [8] indicate that they are also promising for the transmission of still images.

Bibliography

1

R.-Y. Wang, E. A. Riskin, and R. Ladner, ``Codebook organization to enhance maximum a posteriori detection of progressive transmission of vector quantized images over noisy channels,'' IEEE Trans. on Image Proc., vol. 5, pp. 37-48, Jan. 1996.

2

I. Daubechies, Ten Lectures on Wavelets.
Philadelphia, PA: Society for Industrial and Applied Mathematics, 1992.

3

J. M. Shapiro, ``Embedded image coding using zerotrees of wavelet coefficients,'' IEEE Transactions on Signal Processing, vol. 41, pp. 3445-3462, Dec. 1993.

4

A. Said and W. A. Pearlman, ``A new, fast, and efficient image codec based on set partitioning in hierarchical trees,'' IEEE Transactions on Circuits and Systems for Video Technology, vol. 6, pp. 243-250, June 1996.

5

P. G. Sherwood and K. Zeger, ``Progressive image coding for noisy channels,'' IEEE Signal Processing Letters, vol. 4, no. 7, pp. 189-191, 1997.

6

J. K. Rogers and P. C. Cosman, ``Robust wavelet zerotree image compression with fixed-length packetization,'' in Proc. of Data Compression Conference, pp. 418-427, Mar. 1998.

7

A. Albanese, J. Blömer, J. Edmonds, M. Luby, and M. Sudan, ``Priority encoding transmission,'' IEEE Trans. on Inform. Theory, vol. 42, pp. 1737-44, Nov. 1996.

8

A. E. Mohr, E. A. Riskin, and R. E. Ladner, ``Transmitting still images across packet-erasure channels.'' In preparation, 1998.

Footnotes

... Ladner¹

This work was supported by U. S. Army Research Office Grant DAAH004-96-1-0255.