- Wavelet compression package by Geoff Davis
- Arithmetic coding library by John Danskin
- PGM support by Ray Heasman

This code implements a wavelet transform-based image coder for grayscale
images. The coder is not the most sophisticated--it's a simple transform
coder--but each individual piece of the transform coder has been chosen
for high performance. The coder is quite effective, despite its lack of
more sophisticated features such as zerotrees. It yields performance comparable
to Shapiro's EZW coder (J. M. Shapiro, "Embedded image coding using
zerotrees of wavelet coefficients", *IEEE Trans. on Signal Processing*,
v. 41, no. 12, pp. 3445-3463, Dec. 1993). It is designed to be a foundation
upon which more more sophisticated coders can be built--there's no need
to reinvent the wheel if you're working on only one aspect of the coding
process.

Target ratio | Actual ratio | RMS error | PSNR (dB) | PSNR for EZW |
---|---|---|---|---|

4:1 | 4.02:1 | 1.66 | 43.71 | |

8:1 | 8.00:1 | 2.73 | 39.42 | 39.55 |

16:1 | 16.01:1 | 3.96 | 36.18 | 36.28 |

32:1 | 32.01:1 | 5.60 | 33.17 | 33.17 |

64:1 | 64.08:1 | 7.86 | 30.22 | 30.23 |

128:1 | 129.26:1 | 10.48 | 27.72 | 27.54 |

(Numbers for more state of the art wavelet coders can be found here, courtesy of the Image Communications Lab at UCLA)

**Source code:** (Version 0.3, last modified 1/29/97): wavelet.0.3.tar.gz

Version 0.3 fixes a bug in the allocator so that actual rates are much
closer to target rates. Also, it uses binary files for I/O which should
fix some problems that people using Windows 95 were having. Coefficients
default to floats rather than reals, which should save a lot of memory.
Also a bug and a few memory leaks in the WaveletTransform constructors
have been fixed. Some people have complained about my Makefile because
it only works with gmake. If you write a better one, please send it to
me! This package is also available via anonymous ftp from *ftp.cs.dartmouth.edu*
in the directory */pub/gdavis*.

NOTE: This is an alpha version of the code! It is documented, but not completely. Eventually I hope to add a tutorial to the distribution. There are one or two known (minor) bugs. Upgrades will be supplied on the web at irregular intervals. Caveat surfer.

**Standard test images:** A number of "standard" test
images have been included in the source distribution. Note that several
versions of these images exist. The included Lena image is from the RPI
site, ftp://ipl.rpi.edu/pub/image/still/usc.
The Barbara image comes from Alan Gersho's lab at U.C. Santa Barbara. The
Goldhill image is from R. Joshi at Washington State U. These images can
be found together at John Villasenor's Image
Communications Lab site. Additional commonly used images can be obtained
from the U. Waterloo BragZone).
Note, however, that the versions of the Lena and Barbara images at the
U. Waterloo site are *not* the same as the ones used in many of the
papers cited here.

The code has been designed for experimentation. It's very modular and should allow for simple replacements of individual components. One can easily replace the quantizer, the entropy coder, and the wavelet filters.

If you do modify/upgrade/replace sections of this code, I would very much appreciate hearing about it. I hope to make this construction kit a collaborative effort with a whole range of modules supplied by different researchers. A wish list of future improvements is included at the end of this file. I will provide WWW links to any extensions people provide.

A transform coder consists of 3 basic steps.

- An invertible transform is performed on an image.
- The transform coefficients are quantized (discretized).
- The quantized coefficients are entropy coded.

The entropy coding, quantization routines, and bit allocation are very
general-purpose. They will work with a whole variety of transforms, including
DCT's, wavelet packets, local trig bases, etc. Moreover, they have been
designed with the expectation that other features such as zerotrees or
perceptual weighting will be added later. Implementing more sophisticated
coders such as those described in Z. Xiong, K. Ramchandran and M. T. Orchard,
``Wavelet Packets Image Coding Using Space-frequency Quantization",
Preprint, 1996 and Z. Xiong, K. Ramchandran and M. T. Orchard, "Space-frequency
Quantization for Wavelet Image Coding", to appear in *IEEE Trans.
Image Processing*, 1997 (see
Z. Xiong's articles on line) should be relatively easy to do given
this code. The current transform routine should be fairly straightforward
to extend to perfom wavelet packet decompositions.

The wavelet transform implements symmetrized boundaries and works for images of (more or less) arbitrary sizes, as long as the aspect ratio is less than 2:1 (the aspect ratio limitation should be straightforward to eliminate, but I haven't gotten around to it). For the full details on how to perform such a transform, see Chris Brislawn, "Classification of nonexpansive symmetric extension transforms for multirate filter banks," Los Alamos Tech Report LA-UR-94-1747. Also the Los Alamos ftp site for some tutorial code.

The filters included with the wavelet transform include some of the
best known for image coding. It includes the set from J. Villasenor, B.
Belzer, J. Liao, "Wavelet
Filter Evaluation for Image Compression," *IEEE Transactions
on Image Processing*, Vol. 2, pp. 1053-1060, August 1995. There are
a few extra filters from Brislawn's code, a few Daubechies filters, and
a new (unpublished) 18/10 filter that Villasenor's group has found effective.
I've also just added a 7/9 pair from J. E. Odegard and C. S. Burrus, "Smooth
biorthogonal wavelets for applications in image compression,"
in Proceedings of DSP Workshop, Loen, Norway, September 1996. This pair
yields superior results to the standard Antonini pair for EZW on Barbara.

Two sets of quantizers are included. The first set performs a uniform
quantization and is fairly straightforward. The second is an embedded family
of quantizers fully described in D. Taubman and A. Zakhor, "Multirate
3-D subband coding of video", *IEEE Transactions on Image Processing*,
Vol 3, No. 5, Sept, 1994. The quantizers are equivalent to those used in
J. Shapiro, "Embedded image coding using zerotrees of wavelet coefficients,"
*IEEE Transactions on Signal Processing*, Vol. 41, No. 12, pp. 3445-3462,
Dec. 1993, but are coupled with a more effective entropy coding scheme.

Two sets of adaptive entropy coding schemes are also included. The first
performs histogram adaptation with escape codes (see *Text Compression*,
by Bell, Cleary and Witten). The escape codes keeps rare symbols from adding
too much to the overall symbol cost during early stages of histogram adaptation.
The second coder is an embedded coder designed for use with the embedded
quantizer above (See Taubman and Zakhor for full details). It adapts very
quickly and is very effective.

The arithmetic coder is based on an implementation of Alistair Moffat's linear time coding histogram (see Moffat's online papers) ). The implementation is courtesy of John Danskin, and the full distribution (most of which is included here) may be obtained here.

The bit allocation routines are based on integer programming algorithms
described in Y. Shoham and A. Gersho, "Efficient bit allocation for
an arbitrary set of quantizers," *IEEE Transactions on Acoustics,
Speech, and Signal Processing*, Vol. 36, No. 9, pp. 1445-1453, Sept
1988. They provide optimal or near-optimal allocations for the quantizers
included here.

- Add perceptual weights for different subbands.
- Modify wavelet.cc and transform.cc to handle images with different aspect ratios (shouldn't be too hard).
- Add support for color! The easiest way to do this would be to take an RGB image and to transform it to something like YIQ or HUV and then code each layer separately.
- Upgrade image.cc to support more image formats. Read/write .tiff's, .gif's, etc.
- Add entropy-constrained scalar quantizers.
- Add trellis coding.
- Add zerotrees.
- Add an 8x8 block DCT so that the code can be modified to do JPEG.
- Add an 8x8 block DCT with folding.
- Implement wavelet transform via lifting to improve speed.
- Add multiwavelets.
- Fix arithmetic coder so can switch back & forth between coding and writing ints/bits.
- Upgrade the dequantize routines, the entropy coder, and the arithmetic coder so that the code can handle truncated bitstreams.

If you want your code added to the distribution, please make sure it's well documented and debugged! I can either include your code or add a link to it on this page.

Wed Jan 29 1997.