Back to publication index
Alexander E. Mohr Eve A. Riskin Richard E. Ladner
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
firstname.lastname@example.org email@example.com firstname.lastname@example.org
Appears in the Proceedings of the 1998 International Conference
Processing (ICIP'98). 5 pages.
ps (2.22M) - pdf (1.58M) - ps.gz (957k) - pdf.gz (952k) - DOS-format ps (2.25M).
The wavelet transform  is a tool for space-frequency analysis that uses wavelet basis functions to decompose signals in L2(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 . 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.
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.
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.
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 , we think unequal error protection schemes look promising. They have worked well with the transmission of video sequences  and our preliminary results  indicate that they are also promising for the transmission of still images.