App for analyzing leafy curves lets amateur botanists identify trees

Peter Belhumeur just wanted to know what type of tree was outside his apartment. He scanned field guides, looking for willowlike leaves with a wavy, spiked edge, but he couldn’t find the right one. Neither could his neighbors.

As it happened, though, he was building a tool designed to address just this problem.  Belhumeur is a computer scientist at Columbia University who has worked on face recognition, and he and David Jacobs of the University of Maryland in College Park had dreamed up an iPhone app that would use similar mathematical methods to recognize trees. Leafsnap (www.leafsnap.com) allows a person to pick a leaf from the U.S. Northeast, snap a picture of it against a white background, and find out which tree species it is most likely to have come from.

“We thought we could build an electronic field guide for the 21st century,” Belhumeur says, “so that the search would be initiated by an image, much like a Google search is initiated by a text query.”

To teach a smartphone to identify trees, Belhumeur and Jacobs first needed to know how a botanist does the job, so they turned to John Kress of the Smithsonian Institution in Washington, D.C., and his colleagues. Although botanists consider many aspects of the tree — the bark, the flowers, the overall shape of the tree, its height — the key feature is the shape of the leaves.

So the scientists had to define “shape” in a way that a computer could understand. They ended up focusing on curvature at varying scales: At the finest scale, a sharply curving leaf would be serrated, like an elm leaf. At the middle level, a leaf with a lot of curvature would have lobes, like an oak leaf. And at the largest scale, a highly curved leaf would be round like an aspen rather than elongated like a willow.

To calculate curvature, the researchers place a disk under the edge of the leaf and then compute the percentage of the disk that is covered by the leaf. If the edge is perfectly straight, exactly half the disk will be covered; if the edge is concave, less than half will be; and if it is convex, more than half will be. The app analyzes a leaf by comparing the distribution of its curvature at each scale with a set of 8,000 leaf photographs.

Leafsnap then returns a ranked list of the species that are the closest matches. Clicking on a species gives more information, including high-quality photos of the entire tree, its bark, leaves, flowers and fruit.

About 70 percent of the time, the team found, the app returns the correct species as its top choice. It gets within the top three about 90 percent of the time, as long as the picture is taken against a bright background and is free of shadows.

Face-recognition algorithms often use a similar approach with different criteria. One common criterion involves drawing an arrow at each point of the image toward the lightest nearby area. For example, a point at the top of an eyebrow would have an arrow pointing upward, since the skin above the eyebrow is lighter than the eyebrow hair below. Crucially, that will be true regardless of how the face is lit. The face-recognition algorithm can then compare the distributions of the arrows to match up different images of the same face.

In the first two months after its May release, Leafsnap was downloaded more than 300,000 times, swamping the servers in Belhumeur’s lab. The team now wants to expand to include trees across the entire United States.

Shape analysis has the potential for much broader application. Google, for example, would like to develop its Google Goggles app to recognize a pair of shoes from their shape in a photograph and take you to a website to buy them. Doctors would like to be able to take a CAT scan, identify the organs from their shapes, and use a computer to precisely guide radiation treatment. Other researchers are working to identify Alzheimer’s patients from the shape of their hippocampi. Leafsnap’s basic mathematical approach could be applied to all these problems.

For now, the team is pretty happy with just leaves. Belhumeur tried the app prototype on the puzzling tree outside his apartment. The answer made his heart sink: a sawtooth oak. “I thought, that’s discouraging, because this is clearly not an oak,” he says. “I know what an oak looks like, and this isn’t it.” But even though he knew that oaks have round, lobed leaves, not the pointed ones on his tree, he checked out the sawtooth oak anyway. And sure enough, the app had it right.

SN Prime | August 29, 2011 | Vol. 1, No. 11