From the Princeton Weekly Bulletin, March 9, 1998
Wavelets help retrieve images
By JoAnn Gutin
Dancing babies may be all the rage among computer graphics buffs, but Adam Finkelstein goes for a different kind of visual on his screen: Georgia O'Keefe's cattle skulls, for instance, or the "Breaking Wave" of 19th-century Japanese artist Hokusai or the ubiquitous Warhol portrait of Marilyn Monroe.
These iconic images are among those that Assistant Professor of Computer Science Finkelstein uses in the video demo of the new computer program he developed with colleagues at the University of Washington before coming to Princeton last spring. The program, which uses the cutting-edge mathematical tool known as wavelet analysis, makes searching for photos in an archive or on the Web as easy as playing Pictionary. And making things easy is the aspect of computer science Finkelstein most enjoys. "I like solving practical problems," he says. "For me it's rewarding to work on things that might be useful."
The problem he began to attack in graduate school was how to find images in a database. "A big problem in retrieving archived images," Finkelstein explains, "is how to index them. Say you've got a man wearing a yellow hat, riding a bicycle. That's three possible categories, and most pictures have many more elements than that. So you've got a problem."
|
|
|
|
|
|
The method he and his colleagues devised to solve the problem seems simple: the searcher sketches a rendition of the remembered image with a drawing program. The computer looks through its bank of scanned images (which can number in the tens of thousands) and produces 20 that seem to fill the bill. Almost instantaneously, the screen displays them in a sort of cyber-contact sheet to the right of the sketch, with the program's version the best match in the top left corner. If none of them is the right one, you can either pick the one closest to your mental template and use it to send the program off on another hunt, or you can refine your sketch. The program is interactive and constantly incorporates your additions into its selection process.
Even if your sketch would make a competent third-grader cringe, no need to worry. A horn-like crescent on top of a white rectangle is enough to summon up Georgia O'Keefe's cow skull; a big blue curve with some white foam sends the program straight to "Breaking Wave." As for Marilyn, "All you need is the blonde hair, basically," says Finkelstein.
Wavelet analysis
Behind this user friendliness lies a lot of deep, state-of-the-art mathematics. Wavelet analysis, Finkelstein explains, "is a tool for analyzing functions." Functions themselves are tools mathematicians use to represent dynamic phenomena.
"Visual detail is really a difference in brightness or tone from point to point, and wavelet analysis gives you a mathematical way to describe those differences," he says. If you gave each dot in a Seurat painting a number based on its brightness, you could then express the relationship between two adjacent dots as a function. "In the image-searching program," Finkelstein says, "we were looking to see if two images had similar kinds of wavelet analyses, which told us the images were similar."
While the math underlying wavelet analysis has been in development for many years, the technique has become what Finkelstein calls "a really big deal in computer graphics" only in the last five. Princeton math professor Ingrid Daubechies has been one of the pioneers, he notes. "She looks at deep mathematical problems about what sorts of analyses can be performed using wavelets. From that perspective, what I do is just an engineering problem."
A smarter VCR
Daubechies has a slightly different take on the relationship. "I know Adam's work, and I admire it very much," she says. "It's not the same thing I do, but I think it's very interesting, very important."
In fact, she says, practical applications are critical to the field of wavelet analysis, because the math and the applications are linked in a feedback loop. "The applications raise important new questions for the theory. If it weren't for applications, the theory wouldn't be evolving as it is."
Finkelstein is brimming over with new ideas for wavelet analysis. "Another application I'm looking at is making a smarter VCR. It would know what programs it's seen, would recognize the credits and would let you know when, say, 'Cheers!' was on. Maybe," he adds, "this VCR it could recognize a commercial you really hate and turn off the volume for as long as it's on."
Of course, a canny advertiser could probably figure out how to change the commercial subtly in order to escape detection, but even that possibility has an up side, according to Finkelstein: It would generate another practical problem to solve.