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
amohr@isdl.ee.washington.edu riskin@isdl.ee.washington.edu ladner@cs.washington.edu

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).

Introduction

The wavelet transform [2] is a tool for space-frequency
analysis that uses wavelet basis functions to decompose signals in
*L*^{2}(*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.

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.

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 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.

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.

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 3 median filter on the uncorrected image resulted in a PSNR of 25.30 dB, while a 3 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.

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.

**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.

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