Originating Technology/NASA Contribution
Try this: Print out a lower-case letter “o” in Times New Roman, 10-point font. Now hold the paper at arm’s length. Viewed from this distance, the area inside the “o” is approximately equal to the area observed in the Hubble Ultra Deep Field, an image taken by the Hubble Space Telescope. Within that space—only one thirteen-millionth of the sky’s total area—Hubble revealed approximately 10,000 galaxies, each containing billions of stars. The observable universe as a whole contains some 80 billion galaxies and anywhere between 30 and 70 billion trillion stars.
In order to map the intimidating fields of stars Hubble—among other sensitive telescopes—would uncover following its launch in 1990, astronomers needed a powerful tool for comparing and matching star configurations within the telescope’s collected images. In 1986, Princeton University physics professor Edward J. Groth, supported by the Hubble Space Telescope program, invented a pattern-matching algorithm that addressed the challenge. The Groth algorithm forms triangles between every possible triplet of stars in an image (each star’s position being represented by an x-y coordinate pair). It then compares the triangles’ measurements to those in other images, determining any matches. Because certain properties of a triangle do not change if the triangle is rotated or altered in size, the algorithm allows astronomers to effectively map star locations using images of different magnification and orientation.
The Groth algorithm was incorporated into the Space Telescope Science Data Analysis System (STSDAS), a software suite for calibrating, analyzing, and reducing data gathered by Hubble. An updated version of the algorithm is still part of STSDAS, which is available to the public from the Space Telescope Science Institute, a NASA partner located in Baltimore, involved with management of Hubble and the currently under-development James Webb Space Telescope.
In 2002, Portland, Oregon, software programmer and technical writer Jason Holmberg had a rare encounter with a whale shark while scuba diving in the Red Sea. Growing to lengths of up to 40 feet, the filter-feeding whale shark is the world’s largest—and among its least understood—fish species. It is also listed as vulnerable to extinction by the International Union for Conservation of Nature. Fascinated, Holmberg began toying with ideas to help improve methods for tracking the unusual fish. (Physically tagging the sharks for satellite tracking proves inefficient because the tags are frequently lost or rendered inoperative within weeks or a few months; with plastic visual tags, less than 1 percent are spotted again after tagging.) Holmberg eventually teamed with marine biologist Brad Norman, founder of the Perth, Australia, nonprofit ECOCEAN, which studies the whale sharks that migrate annually through Western Australia’s Ningaloo Marine Park. Norman had been tracking the Ningaloo sharks by photographing and identifying each shark from the distinctive white spots on its skin, a marker as unique as fingerprints are in humans. The process was a tedious one; Norman had to examine and compare all photos by eye.
For help conceiving a computer-based tracking system, Holmberg turned to friend Dr. Zaven Arzoumanian, an astrophysicist with Universities Space Research Association on contract at Goddard Space Flight Center, who contributed to the undertaking as a side project independent of his NASA duties. The pair were contemplating the challenge of identifying whale sharks in an automated way when they encountered the Groth algorithm, which provided an ideal basis for creating a pattern-matching program using shark spots instead of stars in the universe. (Fittingly, the whale shark’s name in Madagascar, “marokintana,” means “many stars,” while “geger lintang,” its Javanese name, means “stars in the back.”) Holmberg and Arzoumanian modified the algorithm, applying a technique called blob extraction to pinpoint single-color pixel groups—a useful tweak since the whale shark’s spots are larger and more irregular in shape than stars in photographs. They also introduced rotation correction and contrast enhancement elements to clarify photos, compensate for perspective issues (the sharks are rarely photographed in perfect profile), and take into account 3-D qualities not present in space images.
“What we did in practice was make a very precise algorithm a little less precise,” says Arzoumanian. Since its completion in 2005, the modified Groth algorithm has proven to be highly effective: When a match between photographs is made, the algorithm ranks the correct shark as the first of all possible matches more than 90 percent of the time.
Holmberg built a database system around the algorithm that allows anyone, from researchers to tourists, to submit whale shark photographs for comparison and identification online. Called the ECOCEAN Whale Shark Photo-identification Library, the system has been used by ECOCEAN to collect images of over 1,600 whale sharks so far, providing a continuing data span that is helping researchers to learn more about the life histories and migration patterns of the elusive fish, as well as the status of the whale shark’s threatened population.
“We’re getting reliable population models, and we’re challenging a lot of previous conceptions about whale sharks,” says Holmberg, who notes that findings indicate the sharks may not be as massively migratory as once thought, nor may their numbers be declining, at least at Ningaloo Marine Park, as with most shark species. Photographs are now streaming into the ECOCEAN database from places as diverse as California, Mozambique, Belize, Honduras, and the Maldives. Holmberg credits this to the impact of ecotourism and the “citizen scientist,” the average person contributing valuable scientific information.
“The general public collects a lot of data,” he says. “We’re talking about an animal considered to be rare, maybe a couple of hundred documented sightings in all of history. Now, just this year, we’ll get over 2,400.” Holmberg is now working on a simplified version of the software for easier use by individual researchers studying other species.
The successful application of the modified Groth algorithm has attracted significant attention from scientific circles. Last year, researchers at the University of Central Florida (UCF), in Orlando, adapted the whale shark algorithm as part of a package for tracking polar bears. A threatened species in the United States, polar bears can be tracked using their own individually unique trait: the whisker spots on their muzzles. UCF researchers are compiling a database of photographs with the help of tourists visiting Churchill, Canada, a popular destination for polar bear enthusiasts. The polar bear population at Churchill has been declining dramatically, according to the Canadian Wildlife Service.
“This virtual mark-recapture capability allows people who are going to an ecotourism environment to have a positive effect on the animals. They all become our field assistants in a way,” says Jane Waterman, associate professor of biology and one of the principal investigators of the polar bear project. The database will provide an essential resource for understanding bear behavior and monitoring the bear population as the species suffers the effects of global warming.
The polar bear library is only the most recent application of the pattern-matching algorithm. “We’ve had lots of people approach us from various animal-tracking communities,” says Arzoumanian. California researchers are considering adapting the algorithm to track Mola mola, the ocean sunfish that frequents the waters off the Galápagos Islands. And the Megafishes Project, a collaboration between the National Geographic Society and the World Wildlife Fund, may apply it to track giant Eurasian trout in Mongolia. In theory, the algorithm can be applied to track any animal with unique spotting that does not change as it ages.
“There’s a groundswell of data we’re getting,” says Holmberg, “and it all goes back to the algorithm Edward Groth wrote years ago.”