Evolved transforms improve image compression

A novel technique for optimizing compression outperforms wavelets for data subject to quantization or thresholding.
03 February 2009
Frank Moore, Brendan Babb, Michael Peterson, and Gary Lamont

Many image processing applications, including JPEG20001 and fingerprint compression,2 use wavelets. By redistributing an image's energy into a set of lower-resolution trend subimages, discrete wavelet transforms (DWTs) can significantly reduce the number of bits required for representation. Quantization (approximating a signal with a smaller number of bits) and thresholding (setting all but the largest transform values to zero) may achieve additional compression. However, these techniques introduce irreversible information loss, since the mean squared error (MSE) of reconstructed images increases proportionately with both techniques.

One approach that may circumvent this problem is evolutionary computation (EC), which uses fitness-based selection and genetics-inspired operators to evolve solutions to a combinatorial optimization task. Yet very few researchers have applied this technique to the wavelet domain. Grasemann and Mikkulainen3 combined a genetic algorithm (GA) with a lifting scheme, a methodology for synthesizing new perfect reconstruction wavelets from an existing wavelet filter. This method improved performance for specific classes of images.3 Unlike their technique, however, our GA imposes none of the mathematical properties required of wavelets, such as conservation of energy.

Since 2004, our team has used EC to evolve transforms that outperform wavelets for many compression and reconstruction tasks involving quantization and thresholding. Each run creates an initial population by randomly mutating the wavelet and scaling numbers of a selected wavelet's forward and inverse transforms. Candidate solutions compress and subsequently reconstruct images from a training population. Each candidate's fitness reflects two parameters: the compressed image size, and the reconstructed one's MSE. The best individual is copied into a new generation, which is otherwise populated by combining fitness-driven selection with specialized mutation and crossover operators. Repeating this process over many generations produces a best-of-run solution.

Figure 1. A typical satellite image.

In 2006, our team used a GA to evolve transforms that reduced average MSE in reconstructed digital photographs by 22% (1.126dB) under conditions subject to 64:1 quantization.4 We extended this approach to evolve multi-resolution analysis (MRA) transforms, reducing MSE by 10% (0.50dB) at three levels of decomposition.5

In 2007, we applied our approach to the fingerprint compression problem, whose solution incorporates the 9/7 DWT.6 At 16:1 thresholding (retaining the largest 6.25% of transform values), our best four-level MRA transform averaged 16.01% (0.76dB) MSE reduction for a test population of 80 fingerprints, in comparison to the 9/7. This result established a new state-of-the-art for fingerprint compression under conditions subject to thresholding error.7

Figure 2. Figure 1 after compression and reconstruction by the 9/7 wavelet at 64:1 quantization.

Figure 3. The same image produced by the evolved transform shows visible improvement.

Figure 4. The 9/7's difference image.

Figure 5. The evolved transform's darker image indicates reduced MSE.

In 2008, we used an evolution strategy to achieve success in a third important domain, satellite images8 (see Figure 1). At 64:1 quantization, our best transform averaged 33.78% (1.79 dB) MSE reduction, while maintaining the average information entropy (IE) of compressed images at 99.57% in comparison to the 9/7 (see Figures 25). This evolved transform also achieved 49.88% (3.00 dB) and 42.35% (2.39 dB) average MSE reduction when tested on 80 fingerprints and 18 digital photographs, while maintaining average IE of 104.36% and 100.08%, respectively. Thus, our best evolved transform improves reconstructed image quality without substantial loss of compression capability over a broad range of image classes.

EC can evolve transforms that outperform wavelets for compression tasks involving quantization or thresholding. Ongoing research is optimizing MRA transforms for satellite images. Future applications include radio frequency signal compression and medical image denoising.

Frank Moore, Brendan Babb, Michael Peterson
Mathematical Sciences Department
University of Alaska Anchorage (UAA)
Anchorage, AK

Frank Moore is an associate professor of computer science at UAA. He has taught computer science, computer engineering, and electrical engineering courses at the undergraduate and graduate level since 1997, and has been involved in many military research and development projects.

Brendan Babb has over 20 years experience as a software programmer and analyst in the engineering and telecommunications industries. He holds three patents, jointly or on his own, at Advanced Micro Devices for work on error detection and correction technology. He is currently working as a research technician for the Mathematical Sciences Department at UAA.

Michael Peterson is an assistant professor of computer science at UAA. His research interests include evolutionary computation, image processing, computational intelligence, and bioinformatics. Since 2005, he has investigated the application of evolutionary algorithms to the optimization of wavelet-based transforms for image processing applications.

Gary Lamont
Electrical and Computer Engineering
Air Force Institute of Technology (AFIT)
Wright-Patterson Air Force Base, OH

Gary Lamont is a professor of electrical and computer engineering at AFIT. He has advised many MS and PhD students and teaches courses in computer science and engineering. He has authored textbooks, chapters, and many technical papers, and is a member of the Institute of Electrical and Electronics Engineers, Association for Computing Machinery, American Society for Engineering Education, Society for Industrial and Applied Mathematics, Tau Beta Pi, and Eta Kappa Nu.