A genetic algorithm beats the FBI
Computer scientists from the University of Texas at Austin have used a genetic algorithm to develop a program which can better digitally improve images of fingerprints than the human-based FBI's fingerprint image compression program, according to the National Science Foundation (NSF) in "Man Against Machine." They started by feeding their computers with basic programming instructions needed to compress graphic images. Then they waited for the birth of a better algorithm. After 50 iterations -- or generations -- their genetic algorithm consistently outperformed the FBI's human-designed program for fingerprint image compression. And don't think it's only research. The FBI has today 50 million sets of fingerprints in its archives and performs about 60,000 digital fingerprint image transactions every day. So this software development might soon help to speed up a suspect's identification process.
Here is the introduction of the NSF news release.
It sounds like a plot for a science fiction movie, but it's not. Computers now create programs that solve complex problems better than programs designed by people. University of Texas at Austin researchers Uli Grasemann and Risto Miikkulainen, for example, recently reported that a computer-generated algorithm can digitally improve images of fingerprints better than the FBI's human-designed program currently can.
But what exactly are these image compression programs useful for?
A program used to compress fingerprint images -- images that may prove guilt or innocence -- must not introduce distortion that limits its usefulness. The FBI and its collaborators designed the current world-standard program for fingerprint image compression, known as WSQ, in the early 1990s to compress images to about one-fifteenth of their original byte size. By comparison, JPEG compresses fingerprint images to one-fifth of the original size without distortion.
Grasemann and Miikkulainen, who are working in the Neural Networks Research Group at the University of Texas at Austin, tested the progress of their evolving program after each generation. And after 50 generations, the genetic algorithm consistently outperformed the human-derived WSQ.
You can see below the progress of evolution during a typical run is shown at generations 1, 10, 20 and 50. These images are compressed using a ratio of 16:1. "The first generation produced a more or less random wavelet that performs poorly. Over the next generations, both image quality and the smoothness of the wavelets increase sharply. (Credit: University of Texas at Austin).
As Grasemann said, "It is fascinating and a little ironic that computers can come up with new and creative solutions that human experts miss. There is definitely tremendous potential to increase the quality of work in many areas of science and engineering using genetic algorithms."
This research work has been presented during the 2005 Genetic and Evolutionary Computation Conference (GECCO) which was held in Washington, D.C., on June 25-29, 2005.
The scientific paper, named "Effective image compression using evolved wavelets," received an award in the in the Human-Competitive Results Competition. Here are two links to the abstract and to the full paper (PDF format, 8 pages, 370 KB). The above images were extracted from this paper.
Sources: National Science Foundation news release, September 1, 2005; and various web sites
You'll find related stories by following the links below.