Man Against Machine

September 2, 2005
Man Against Machine

Computer-generated method outperforms human-designed program for fingerprint improvement

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.

The increasing quality of a fingerprint image after compression is shown through subsequent generations of genetic algorithm evolution. By generation 50, the quality of the image surpasses the quality of the same image compressed by the current world-standard program designed by humans. Credit: Grasemann and Mikkulainen, Effective Image Compression using Evolved Wavelets, GECCO '05, (c) 2005 ACM, Inc. Used by permission.

An "algorithm" is a computer program designed to systematically solve a problem. Image compression algorithms try to minimize the number of bytes in graphics files while preserving image quality as much as possible. Fewer bytes mean less storage space and faster file transfer times. JPEG, for example, is a common compression format used for photographs.

The FBI has nearly 50 million sets of fingerprints from criminals on file and adds approximately 5,000 new ones per day, making fingerprint image compression paramount. In addition, the bureau makes 50,000-60,000 digital fingerprint image transactions per day--half related to civil matters and half related to criminal activity.

"Genetic algorithms" are created when computers evaluate and improve a population of possible solutions to a problem in a stepwise fashion. The new program evolves by letting good solutions produce offspring as bad solutions die out. Over time, the individual solutions in the population become better and better, producing a final, best solution. The method uses terms derived from biology, such as generation, inheritance and mutation, to describe the particular program manipulation the computer uses at each step of improvement, hence the name genetic algorithm.

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 applied genetic algorithms to solve the fingerprint compression puzzle in work supported by the National Science Foundation's Computer and Information Science and Engineering directorate. They provided their computer with the basic programming instructions needed to compress graphic images and then waited for a better algorithm to be born. The progress of the evolving program was tested at each generation. After 50 generations, the genetic algorithm consistently outperformed the human-derived WSQ.

Grasemann pointed out that other human-designed, modern image compression programs also surpass WSQ, but the computer-generated nature of their method is unique.

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."

Grasemann and Miikkulainen, as well as researchers from two other NSF-funded projects, received awards at the 7th Annual Genetic and Evolutionary Computation Conference (GECCO) held in Washington, D.C. earlier this year. The competition pits man against machine in tasks ranging from how to design improved ventilation systems for commercial buildings, to improving synthetic anti-bacterial compounds. Results of the conference are presented in the Proceedings of GECCO 2005, published by the Association for Computing Machinery.

Source: NSF

Explore further: Fruit fly brains inform search engines of the future

Related Stories

Fruit fly brains inform search engines of the future

November 9, 2017

Every day, websites you visit and smartphone apps that you use are crunching huge sets of data to find things that resemble each other: products that are similar to your past purchases; songs that are similar to tunes you've ...

Fingerprint Matching Techniques Need Reform

January 22, 2007

Fingerprint matches -- key to fighting international terrorism and keeping criminals off the street -- are no longer foolproof, warns a law professor at the University of California, Davis.

Recommended for you

Study identifies new malaria parasites in wild bonobos

November 21, 2017

Malaria parasites, although widespread among wild chimpanzees and gorillas, have not been detected in bonobos, a chimp cousin. Reasoning that previous studies may have missed infected bonobo populations, a team led by Beatrice ...

Physicists design $100 handheld muon detector

November 20, 2017

At any given moment, the Earth's atmosphere is showered with high-energy cosmic rays that have been blasted from supernovae and other astrophysical phenomena far beyond the Solar System. When cosmic rays collide with the ...

The strange case of the scuba-diving fly

November 20, 2017

More than a century ago, American writer Mark Twain observed a curious phenomenon at Mono Lake, just to the east of Yosemite National Park: enormous numbers of small flies would crawl underwater to forage and lay eggs, but ...

0 comments

Please sign in to add a comment. Registration is free, and takes less than a minute. Read more

Click here to reset your password.
Sign in to get notified via email when new comments are made.