Complete Title: Effective Image Compression using Evolved Wavelets. Authors Uli Grasemann Department of Computer Sciences The University of Texas at Austin 1 University Station C0500 Austin, TX 78712-0233 USA email: uli@cs.utexas.edu phone: (512) 203-3501 Risto Miikkulainen Department of Computer Sciences The University of Texas at Austin 1 University Station C0500 Austin, TX 78712-0233 USA email: risto@cs.utexas.edu phone: (512) 471-9571 Corresponding Author Uli Grasemann Statement In the last two decades, significant research effort has been spent on the discovery of wavelets that perform well in specific applications, especially image compression. Designing wavelets by hand has traditionally been a very involved mathematical process that was considered more of an art than a science. Numerous different families of wavelets have been published in the literature, and were considered significant contributions at the time. Notable examples are the "Daubechies wavelets", a family of orthogonal wavelets first published in 1988 [1], and the "Antonini wavelet" [2], a biorthogonal wavelet that is still the most popular wavelet for image compression. For the compression of photographic images, the Antonini wavelet is considered the best known wavelet, and is widely used as the default wavelet in state-of-the art image coders like JPEG2000. Using photographic images as training examples, the genetic algorithm described in the attached paper has dicovered several wavelets that are so similar to the Antonini wavelet (in appearance as well as in performance), that it is fair to say that the algorithm has rediscovered it. The Antonini wavelet is also known as the "FBI wavelet" because the FBI uses it for fingerprint compression. Using fingerprint images as training examples, the GA consistently discovered wavelets that outperformed the FBI wavelet significantly. On average, using evolved wavelets lead to a decrease in file size of 10 - 15% over images compressed with the FBI wavelet, without loss of image quality. Even greater improvements have been shown for the case of scanned documents, although there is no accepted best wavelet for this task. Overall, the GA described in the paper satisfies the following of the eight criteria: (B) The result is equal to or better than a result that was accepted as a new scientific result at the time when it was published in a peer-reviewed scientific journal. (E) The result is equal to or better than the most recent human-created solution to a long-standing problem for which there has been a succession of increasingly better human-created solutions. (F) The result is equal to or better than a result that was considered an achievement in its field at the time it was first discovered. (G) The result solves a problem of indisputable difficulty in its field. Full Citation Uli Grasemann and Risto Miikkulainen. "Effective Image Compression using Evolved Wavelets." In Proceedings of the Genetic and Evolutionary Computation Conference, 2005. To appear. Abstract Wavelet-based image coders like the JPEG2000 standard are the state of the art in image compression. Unlike traditional image coders, however, their performance depends to a large degree on the choice of a good wavelet. Most wavelet based image coders use standard wavelets that are known to perform well on photographic images. However, these wavelets do not perform as well on other common image classes, like scanned documents or fingerprints. In this paper, a method based on the coevolutionary genetic algorithm introduced in [3] is used to evolve specialized wavelets for fingerprint images. These wavelets are compared to the hand-designed wavelet currently used by the FBI to compress fingerprints. The results show that the evolved wavelets consistently outperform the hand-designed wavelet. Using evolution to adapt wavelets to classes of images can therefore significantly increase the quality of compressed images. References [1] M. Antonini, M. Barlaud, P. Mathieu, and I. Daubechies. "Image coding using wavelet transform." IEEE Transactions on Image Processing, 1992. [2] DAUBECHIES, I. "Orthonormal bases of compactly supported wavelets." Comm. Pure Appl. Math. 41, 909 - 996, 1988. [3] U. Grasemann and R. Miikkulainen. "Evolving wavelets using a coevolutionary genetic algorithm and lifting." In Proceedings of the Genetic and Evolutionary Computation Conference, volume II, pages 969 - 980, New York, NY, 2004. Springer.