Survival of the fittest draws homeland security scrutiny

The evolutionary views of Charles Darwin, or at least processes derived from them, made it into the homeland security agenda of the International Society for Optical Engineering (SPIE; Bellingham, WA) as a potential means of radically simplifying gargantuan image-processing tasks.

Th 115250

The evolutionary views of Charles Darwin, or at least processes derived from them, made it into the homeland security agenda of the International Society for Optical Engineering (SPIE; Bellingham, WA) as a potential means of radically simplifying gargantuan image-processing tasks. Researchers at the Los Alamos National Laboratory (LANL; Los Alamos, NM) are achieving impressive results using a software system based upon evolutionary computation methods in which the fittest algorithms for various image-processing tasks are chosen through an automated process of natural selection.

The Los Alamos team developed its evolutionary computation system—dubbed GENIE for genetic imagery exploitation—because the availability of massive quantities of multispectral image data from a wide variety of sources is growing much faster than the availability of analysts to interpret the data, said team member John Szymanski prior to his scheduled presentation at the SPIE conference on Optics and Photonics in Homeland Security (Dec. 11–12, 2002; Alexandria, VA). Unlike most automated image-analysis methods for multispectral data, GENIE attempts to at least partially compensate for the increasing shortage of human analysts by including a capacity for examining the spatial cues that guide human observers.

On the one hand, this more-human approach to automated analysis makes GENIE's image-processing solutions more generalizable over broad categories of image data placed in widely different environments than traditional automated methods. On the other hand, adding spatial analysis can significantly increase the complexity of an image-processing task. The researchers solved the latter dilemma by automating another human approach to particularly intriguing challenges: sexual reproduction. "We basically perform an analog of sexual reproduction by taking genes from different parents and putting them together," Szymanski said. "You hope that you are keeping the things that are good, and things that work well in the [image-processing] problem can be brought along to the next generation."

Genes and chromosomes

The "genes" in this automated evolutionary scheme are actually elementary image operators, such as edge detectors, texture measures, spectral operations, and various morphological filters. And the "parents" or "chromosomes" are actually image processing algorithms or pipelines containing different combinations and arrangements of various genes. Currently, the typical algorithms or chromosomes competing in GENIE's evolutionary process consist of between five and ten operational steps or genes. A typical evolutionary population might consist of 100 chromosomes.

Th 115250
A computer algorithm based on evolutionary process finds the "fittest" solutions to imaging problems. An iterative process in which an operator marked desired features in an aerial photograph in green and undesired features in red enabled evolution of an algorithm for finding beaches.
Click here to enlarge image

null

Based on desired image characteristics provided by the operator through a graphical interface, GENIE compares performance attributes among its numerous newborn algorithms (see figure). The evolutionary software then makes the tough Darwinian decisions. "The top 10% of them work pretty well, so GENIE keeps those, and the bottom 20% don't work very well so GENIE throws those away," Szymanski said. "GENIE allows the middle ones to reproduce by crossing them together in an analog of sexual reproduction that brings a new population to bear."

As an example, Szymanski described the evolution of an image-processing algorithm to identify water. "An early generation might find all of the dark things in an image. Then the next generation might find dark things and smooth things," he said. The idea in going from one generation to the next is to add new capability to the best algorithm in the current generation, he said.

The GENIE system achieved its first major success two and a half years ago in identifying the severity of wildfire burn damage and contributing to landscape rehabilitation based on airborne image data taken after the Los Alamos-area Cerro Grande wildfire. The software system was also used to identify debris fields in New York City based on satellite imagery following the destruction of the World Trade Center towers. Currently, the researchers are pursuing new and increasingly challenging applications, particularly incorporating numerous inputs from diverse sensor systems, as well as contributing to ongoing research in machine learning.

More in Detectors & Imaging