A Space Odyssey
Image Compression and the Wavelet Transform
As a member of the High School class of 1984, I was imbued with more than my fair share of Orwellian analysis. Although a majority of present day references recount the omnipresent surveillance technology contained in George Orwell’s Nineteen Eighty-Four, its concept of Newspeak is equally prescient. The purpose of Newspeak was to reduce drastically the number of words in the English language in order to eliminate ideas deemed dangerous by the totalitarian dictator, Big Brother. Initially, the language was marketed for its utility as a streamlined communication vehicle, conserving both document storage space and transmission bandwidth. Over time, the loss of linguistic features, facets, and flavoring precluded the precise expression of original ideas.
Such can be the case with data compression. Curve fitting is a process by which information is gleaned from experimental data. For example, a data file containing the time-resolved detector response observing excited fluorescent molecules can be modeled by a single exponential decay. The four coefficients of amplitude, decay lifetime, starting time, and offset are varied until the mathematical curve fit equation closely resembles the original data. In this manner, these four coefficient values can serve as a surrogate for the thousands of experimental voltage values acquired by the detector. A reasonable facsimile of the original data can be reconstructed by using these coefficients in the appropriate equation.
The time-resolved acquisition of continuous sound waves from an orchestra collects data not from a single source, but from the superposition of multiple frequencies having varying amplitudes and phases. Through the application of the Discrete Fourier Transform (DFT), the digitally sampled time-resolved data can be analyzed in frequency space and the finite number of frequencies having non-zero amplitudes can serve as a compressed representation of the sound wave acquired in temporal space. Likewise, transform-based algorithms have been employed for two-dimensional digital image compression. In 1992, the Joint Photographic Experts Group (JPEG) adopted an international image- compression standard based on the Discrete Cosine Transform (DCT) — a real-valued cousin of the DFT providing better signal approximation using fewer coefficients. The DCT removes spatial and spectral redundancy among neighboring pixels while also removing small image features calculated to be below a relevancy threshold. Removal of this information earns this compression method the term “lossy,” as the reconstructed image does not contain all of the original information. The advanced Human Visual System (HVS) serves as an image receiver that interpolates the missing data and perceives the compressed image as being virtually indistinguishable from the original.
Quantitative scientific applications including medical imaging and sensor visualization require compression algorithms to be “lossless” — a condition wherein the reconstructed image is numerically identical to the original. Simply setting the DCT relevancy threshold to zero does not produce lossless compression. The difficulty lies in the limited “Newspeak vocabulary” of the DCT — it can only model spatial data as the summation of continuous cosine waves. In an effort to improve processing efficiency, the JPEG standard slices images into 8 x 8 pixel blocks. In the same fashion that it is inappropriate to use the mathematical model of a straight line to curve fit an exponential decay, it is impossible for a collection of continuous cosine waves to model successfully a finite 8 x 8 pixel region containing sharp boundaries and high-contrast features. The error in both of these examples is the poor choice of the model or basis function.
In the early 1980s, Professor Ingrid Daubechies, at present with the Program for Applied and Computational Mathematics at Princeton University, utilized basis functions that were defined over a finite interval. Rather than being a cosine wave that is integrated from negative to positive infinity in time space, these basis functions, coined “wavelets,” have defined edges or boundaries in the same way that digital images do not extend to infinity. By scaling and translating the basis wavelet (analogous to adjusting amplitude, frequency. and phase in the DFT), the Discrete Wavelet Transform (DWT) provides a more accurate fit to the image data while using fewer coefficients to represent the compressed image. Now armed with the freedom to transform data from time space to frequency space without being limited to cosine waves, the mathematical community is exploring the infinite combinations of more accurate basis functions available in the new “wavelet vocabulary.” Indeed the DCT is being supplanted by the DWT for use in the JPEG-2000 international image compression standard.
Because the DWT calculates the appropriate coefficients as floating-point numbers, the reconstructed digital image is also represented by floating-point pixel intensities whereas the original image consists only of integer values. With the goal of producing a truly lossless compression algorithm for the scientific community, Professor Daubechies, along with colleagues from AT&T-Labs Research, Lucent Technologies, and IBM, developed a vocabulary of wavelet transforms that map integer pixel intensities to integer coefficients. Professor Daubechies recently received the National Academy of Sciences Medal in Mathematics for her development of wavelet transforms. The first recognition of her early work was a paper awarded the Louis Empian Prize for Physics in her native country of Belgium. And I’m sure you can see this coming — in the year 1984.
This material originally appeared as a Contributed Editorial in Scientific Computing and Instrumentation 18:2 January 2001, pg. 14.
William L. Weaver is an Associate Professor in the Department of Integrated Science, Business, and Technology at La Salle University in Philadelphia, PA USA. He holds a B.S. Degree with Double Majors in Chemistry and Physics and earned his Ph.D. in Analytical Chemistry with expertise in Ultrafast LASER Spectroscopy. He teaches, writes, and speaks on the application of Systems Thinking to the development of New Products and Innovation.
