January 2004
http://www.coe.berkeley.edu/labnotes/0104
Commuter-friendly version

Tamara Miller's interest in computer vision was sparked when she spent a summer at the University of Florida working on an eye tracking system for a hands-free computer mouse as part of the National Science Foundation's prestigious Research Experiences for Undergraduates (REU) program. (David Pescovitz photo)

The human face has 80 muscles that work in tandem to create a seemingly infinite array of expressions that dramatically change the way we look from moment to moment. While humans have a relatively easy time matching our contorting faces to names, computers are notoriously bad at it. If software could automatically and accurately identify people's faces though, myriad applications emerge--from intelligent surveillance systems to software that helps us navigate massive collections of photographs. UC Berkeley PhD candidate Tamara Miller and computer science professor David Forsyth are tackling the latter in an effort to advance the science of computer face recognition as a whole.

The researchers developed a system that automatically associates 45,000 face images culled from online news articles with the names of the individuals in the photos. In their current demonstration, a user is presented with a cluster of photos depicting a single individual--top United Nations weapons inspector Hans Blix, for instance. The more someone appears in the news, the larger the cluster of images. Clicking on a particular photo links the image to its associated news article.

"The system enables you to browse the news by faces and bring up articles related to the people you see," Miller says.

The software is remarkably adept at identifying dozens of images of, say, Colin Powell even when the photos depict the Secretary of State from a variety of angles, under different lighting conditions, and with dozens of very different expressions on his face.

"Most photos in the news aren't mug shots with the person looking right into the camera," says Forsyth, a researcher with the Center for Information Technology Research in the Interest of Society (CITRIS). "People do all kinds of remarkable things with their faces. For example, we have piles of photographs of George Bush biting his upper lip when he's nervous."

This figure shows a representative set of face/name clusters. The picture greatly exaggerates the error rate in order to show interesting phenomena and all the types of error the researchers encounter. For example, in the case of Burmese opposition leader Auung San Suu Kyi, the clustering is effective even with individuals who wear moustaches (John Bolton) and eyeglasses (Hans Blix). Yet the James Bond cluster depicts photographs of an actor who portrayed the character and, erroneously, another individual who played the role of a villain in one film. (courtesy the researchers)

One potential application of the technology is a tool that automatically organizes and enables easy searches of photographic archives without depending solely on text annotations. Also, while the Berkeley research is not focused on surveillance, Forsyth imagines it could lead to a system that analyzes video footage taken during or before a criminal activity to flag possible suspects.

The process of linking a massive collection of faces with names begins with extracting the faces from the rest of a photograph. Software written by Miller then corrects, or rectifies, the position of each face so that it matches a "canonical" pose that can be compared with other faces. The rectifying software runs on the Millennium Cluster, a CITRIS testbed of more than 1,000 individual PCs that work in parallel to solve computationally-intensive problems.

"The rectifying software finds the eyes, nose, and mouth and conducts the transformation between the original and the canonical pose," Miller says.

The identification process is helped along by extracting names from the captions that accompany the photos. Labeling the photos based only on the captions is not possible though because, for instance, there may be several people in a particular photograph. While humans can determine by the caption who is who, computers are tripped up by the syntax of the text. Instead, each face in a photo is associated with all of the names in a caption. Then the computer compares the face with already established clusters of named faces to statistically determine if it tagged it with the correct name.

In a recent scientific paper, Forsyth, Miller, and their colleagues report that the system is correct 95% of the time. Sometimes though, "one innocent error by the program could cause considerable offense," Forsyth says. For example, due to a mistake extracting names from the caption, the system incorrectly labeled a photo of the German Justice Minister as Adolf Hitler.

While the kinks of the software are still being worked out, including its inability to label faces photographed in profile, the development of a massive image database that can be automatically labeled is a leap forward for computer face recognition.

"One problem in face recognition research is that the experimental datasets of images that people use are often very different from the real world," says Forsyth, a researchers with the Center for Information Research in the Interest of Society. "It's a bit like studying animal behavior in a zoo. You can do it, but you can never be certain about what you've learned. Our dataset is more realistic because it contains faces captured 'in the wild.'"

Professor Borivoje Nikolic holds several of his low-power integrated circuits. (David Pescovitz photo)

Every eighteen months or so, new integrated circuits with more transistors packed into the same amount of space continue to step up the already-dazzling graphics of our desktop PCs and the capabilities of the portable devices in our pockets. In the background though, chip designers are faced with a potential showstopper: the challenge of power consumption and heat dissipation. The faster the chip, the higher its power requirements and power density. Intel CTO Patrick Gelsinger has said that if the problem is not solved, chips available by the end of the decade will, proportionately for their size, generate the heat of a nuclear reactor.

To cool things off, UC Berkeley professor Borivoje Nikolic of the Department of Electrical Engineering and Computer Sciences, is developing techniques to dramatically reduce power consumption, without sacrificing much performance. The optimization challenges are two sides of the same coin.

"All of the tools that the industry relies on were built to extract the maximum performance from transistors," Nikolic says. "But we now want to get the maximum performance for a given power or the minimum power for required performance."

The solution, Nikolic explains, is "energy-performance optimization" at every level of chip design, from the overall architecture of the integrated circuit down to the tiniest components of the transistors. While the optimization techniques differ depending on the level, the aim is the same: balance the trade-offs between energy and performance.
To help chip designers find this sweet spot, Nikolic and his graduate students, are continuing UC Berkeley's rich history of developing groundbreaking tools for integrated circuit design. The new software tool analyzes new chip designs to pinpoint the trade-offs between energy and performance.

"To reduce power consumption, you must first understand where your power goes," Nikolic says.

So far, the tool has shown that saving energy to reduce performance in one aspect of a chip design does not mean that the chip's overall performance will dramatically suffer. Instead, redesigning another part of the chip could make-up for the performance loss at a much lower energy cost.

"With a performance reduction of just a few percent, we might be able to cut a chip's power consumption in half," Nikolic says.

To demonstrate their novel approach, the researchers are examining several chip power-intensive chip components in light of the power constraint issue. The first is to identify the most ideal design for an adder, the digital logic circuits used by a computer to add two or more binary numbers. In collaboration with IBM, the researchers are also designing a new low-power Floating Point Unit (FPU), the part of a microprocessor that handles complex calculations involving decimal points. Many high-end graphics applications, for example, depend on powerful FPUs.

"Ninety-nine percent of designs for the most basic components don't make sense when you think about power constraints," Nikolic says.

While low-power integrated circuits are necessary to keep next generation chips from sizzling, they're also essential for the continued proliferation of mobile computing technology.

"The key is to minimize the energy requirements to extend the battery life," Nikolic says. "So we ask, what is the lowest amount of energy needed for a certain computational task?"

To that end, Nikolic is collaborating with Robert Broderson, a professor in EECS and the co-director of the Berkeley Wireless Research Center (BWRC), and others on low-power integrated circuits for telecommunications applications like mobile phones and wireless handheld computers. One novel approach was proposed by Yun Chiu, a graduate student working with Nikolic and EECS professor Paul Gray. (Gray is also the University's Executive Vice Chancellor and Provost). Chiu's method involves substituting a high-accuracy, high-power analog-to-digital converter component with one that uses less power but is also prone to error. Then, a robust digital signal processor that doesn't suck down much juice can correct the errors.

Ultimately, the aim of all Nikolic's research is to prevent the performance curve of future chips from burning itself out with power problems.

Professor David M. Auslander, also the associate dean for research and student affairs, recently won the 2003 Eckman Award from the Instrumentation, Systems, and Automation Society. The award recognizes outstanding contributions to education and training in science, engineering, and technology of instrumentation.

This artistic interpretation depicts a rotating SNAP satellite observing a supernova. (courtesy LBNL)

UC Berkeley professor of computer science Lotfi A. Zadeh

The world is not black and white. For instance, concepts like "tall" or "short" are not based on Aristotelian "either/or" logic. Historically, computers, which operate based on "true of false" approaches, have had problems with questions that involve "degrees of truth." But with his seminal 1965 scientific paper "Fuzzy Sets," UC Berkeley professor of computer science Lotfi A. Zadeh invented a new approach to help computers deal with the real world.

"A basic difference between fuzzy logic and other logical systems is that in fuzzy logic, everything is, or is allowed to be, a matter of degree," Zadeh says.

Now, fuzzy logic is found in myriad applications and everyday products, from traffic signals and subway systems to television sets and washing machines. Fuzzy logic was born from Zadeh's work on natural language recognition, exploring computer systems that can handle the uncertainty of human language.

"Humans make decisions with perceptions rather than measurements," Zadeh has said. "When you are driving a car, your decisions are based on your perceptions, not on precise calculations of speed, time and distance. Humans have a remarkable ability to make a wide variety of decisions based on perceptions."

While fuzzy logic's departure from "either/or" logic into a model of "a little of this/a little of that" was initially met with skepticism, especially in the West, its impact is now worldwide. In the US alone, 1,700 patents related to fuzzy logic have been granted, while in Japan, where Zadeh's approach proliferated more quickly, 4,801 were issued. For example, traffic lights that self-adjust based on traffic flow are based on fuzzy logic, as are the loading sensors in some washing machines, the contrast control in many television sets, and medical devices like blood pressure monitors.

"Instead of setting the controls of a camera for exposure, shutter speed, color balance and flash, you just aim it and the camera decides what to do," he said.

Zadeh joined the UC Berkeley faculty in 1959 and served as its chairman from 1963 to 1968. He has also received honorary doctorates from more than a dozen institutions. Zadeh's work has been recognized with many awards including the IEEE Medal of Honor, the ACM 2000 Allen Newell Award, the Okawa Prize, and the Honda Prize, all for his development of fuzzy logic.

"Fuzzy logic is used to make machines smarter," Zadeh said. "It increases their machine IQ."

Original article: "1972: The Release of SPICE, still the industry standard tool for integrated circuit design" (Lab Notes, May/June 2002)
http://www.coe.berkeley.edu/labnotes/0502/history.html

Each year the EDA (Electrical Design Automation) Consortium awards the Phil Kaufman Award to honor the accomplishments of individuals who have made a "substantial, sustainable contribution to the success and advancement of the industry that benefits the industry's tools users - electronic designers." Dean Richard Newton is the 2003 recipient of the award.

Newton was recognized for his seminal contributions to the field of integrated circuit design. While a graduate student at UC Berkeley in the 1970s, he was instrumental in the development of the Simulation Program With Integrated Circuit Emphasis (SPICE). The tool, or one of its myriad derivatives, has been wielded in the design of nearly every single integrated circuit developed in the last 25 years. Newton later helped found several successful companies in the space, including Cadence Design Systems and Synopsys.