**Alexander E. Mohr ^{1}
- Eve A. Riskin - Richard E. Ladner
**

Proceedings of the 32nd Annual Conference on Information Sciences
and Systems, March 1998 (CISS'98). 2 pages.

ps (217k) -
pdf (373k) -
ps.gz (42k) -
pdf.gz (80k) -
DOS-format ps (220k).

Approach

The wavelet transform is a linear orthonormal transform that concentrates signal energy in a small number of subbands, and any error introduced in the transform domain is quantitively identical in the signal domain. A tree-structured vector quantizer is progressive: a crude representation is transmitted first, followed by better and better approximations in subsequent passes. Our approach to handling the loss of a bit in a codeword is to truncate it to the previously-received bits, thus treating those bits as an index to an internal node in the tree.

Adjusted Distortion

- Let
be the rate in bits per vector.**r** - Let
**D**_{r}be the distortion at rate.**r** - Let
**P**_{L}be the probability of losing a bit.

We then let

P_{U,k} |
= | (1-P_{L}) P_{U,k-1} |
(1) |

be the probability that bit

Solving that recurrence yields:

P_{U,k} |
= | (1-P_{L})^{k}. |
(2) |

The ``benefit'' of a bit is the decrease in distortion
that results from receiving that bit, as illustrated in
Figure 1:

B_{k} |
= | (D_{k-1} - D_{k}). |
(3) |

In the presence of bit
loss, the * k*-th bit no longer reduces the distortion by

In other words, the adjusted distortion for a given rate is the distortion at rate 0 subtracted by the adjusted benefit of each additional bit.

Bit Allocation

Bit allocation among the subbands is done with an extension [1] to the GBFOS algorithm [2]. It allocates bits among the various subbands such that all allocations lie on the lower convex hull of the rate-distortion curve. The effect of Equation 4 is to bias the allocation against longer codeword indexes. As the percentage of lost bits increases, the coarse subbands that would normally have many bits assigned to them (corresponding to a deep tree) end up with a reduced number of bits, while the fine-scale subbands that would usually have few, if any, bits assigned to them, end up receiving more (but still not as many as the coarse ones, as shown in Figure 2). Essentially, in the presence of high bit loss rates, the benefits of allocating bits to low-rate detail subbands are diminished, but the benefits of high-rate coarse subbands are diminished far more rapidly.

Conclusion

Future Work

**1**-
E. A. Riskin, ``Optimum bit allocation via the generalized BFOS algorithm,''
*IEEE Transactions on Information Theory*, vol. 37, pp. 400-402, Mar. 1991. **2**-
L. Breiman, J. H. Friedman, R. A. Olshen, and C. J. Stone,
*Classification and Regression Trees*.

The Wadsworth Statistics/Probability Series, Belmont, California: Wadsworth, 1984. **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.

- ... Mohr
^{1} - This work was supported by U.S. Army Research Office grant DAAH04-96-1-0255, an NSF Young Investigator Award, and a Sloan Research Fellowship. Departments of Electrical Engineering and Computer Science and Engineering, University of Washington, Box 352500, Seattle, WA 98195-2500. http://rcs.ee.washington.edu/dcl/amohr/