Posted October 2007
In December 2005, while the IMA was in the midst of a thematic program on imaging science, a homicide investigator from Richmond, Virginia, contacted the institute about an unsolved murder.
The best clue available seemed to be a service station security camera video showing the perpetrator fleeing the crime scene in a car. Unfortunately the quality of the video was terrible, and it seemed impossible to extract information of use from it. Then again, math can do amazing things in service of crime-fighting—at least on popular television shows like NUMB3RS and CSI. Could the IMA be of help in this case?
Michael Black, a computer researcher from Brown University and a visitor to the IMA program, rose to the challenge. The story is told in the article below, which is reproduced from InsideBrown, a publication of Brown University.
Whodunit? Computer Scientists Bring Clarity to Grainy Surveillance Video
by Wendy Y. Lawton
It was late, 1 a.m. on a cool Virginia night last October, and Harry Phillips Jr. needed to get home to the next county. The 39-year-old walked into a 7-Eleven near the Richmond airport. He asked a young man buying a cheap cigar for a ride. They got in a four-door sedan and drove away.
The car headed southeast until the fast-food restaurants and hotels disappeared and open fields and subdivisions rose up in the darkness. About 1:20 a.m., the sedan pulled behind a Citgo gas station on an isolated stretch of road not far from a Nabisco cracker plant and a county park. Phillips got out of the car. Gunshots rang out.
Later that morning, the owner of the gas station found Harry Phillips Jr. dead, shot three times from behind. His wallet was gone.
Michael Black is a professor of computer science and a computer vision researcher. Scientists working in computer vision try to get machines to interpret real-world images with the clarity that humans do. Or in the case of forensic computer vision, they try to get machines to extract visual information that humans can't get to.
The work requires extensive knowledge of optics and a strong grasp of statistics, geometry, and mathematical computing. Black is a leader in the field.
In January, Black got e-mail from a colleague at the University of Minnesota. A police detective from Henrico County, Virginia, needed help solving a murder. The best evidence in the case is video shot by two security cameras - one mounted inside a convenience store, the other outside a gas station. The footage shows the victim, a suspect and the suspect's car. The images, however, are a disaster. They are distorted, speckled, blurred. Some are plagued by shadows, others by glare. The quality is so poor the suspect's features are barely distinguishable. The color of the car, its make and model are mysteries; the license plate number is, too. Was Black interested?
As a scientist, Black was tempted by the technical challenge. As a teacher, Black was enticed by the learning opportunity. He could show students how to work through a difficult problem as a team. "Crime shows make it look easy," Black said. "But I knew that extracting anything useful from these videos would require machine vision methods at or beyond the current state of the art."
On the first day of "Topics in Computer Vision" this spring, Black announced to the sixteen graduate and undergraduate students gathered that they'd be helping to solve a murder case. He described the crime, the video, and the goal: determine the make and model of the suspect's car. Excitement rippled through the room.
Several students, however, suspected a hoax. Computer vision students are used to "toy" problems, the kind that neatly illustrate a concept or a problem-solving method but lack real-world complexity. So a true-crime test? "It seemed crazy," said graduate student Eric Rachlin. "Solving a murder mystery in class? C'mon."
The deal, however, was real. Proof arrived in a priority package: the surveillance tape from the Citgo station that showed the car pulling in before the shooting. One student dismissed the video as "comically blurred."
The class broke into teams. To clean up the images, they tried just about everything. They used statistical modeling and Markov random fields to remove tiny lines and other visual "noise." They tried deinterlacing, a technique used to tease apart television images and sharpen their appearance. They used deghosting, a method of removing image doubles or "ghosts." Motion estimation, super-resolution, specularity detection, 3D tracking, camera calibration - students tried them all. Some techniques yielded good results. Others didn't; there simply wasn't enough data to unlock the mysteries inside the pixels.
The students and their professor pressed on. They asked police to send measurements of the gas pumps, parking lot lines and other critical objects in the video scenes. One grad student, Matt Loper, had his parents drive more than an hour from their Virginia home to photograph the gas station. Another grad student, Matt Leotta, walked around campus taking shots of Toyotas and Nissans - likely makes of the suspect's car - so that he could superimpose them onto the surveillance video for comparison.
"I've never taught such a motivated class," Black said. "I think we were all a little obsessed with solving this murder."
Andrew Stromberg, an investigator with the Henrico County Division of Police, flew to Providence for an April briefing. Afterward, Stromberg sent the 7-Eleven video that showed the suspect and the victim together. Could the class get any identifying details about the suspect? Students, who'd spent hundreds of hours on the project, worked past the last day of classes and into the reading period. In the middle of finals week, Stromberg and his partner, Charles Hanna, flew up to get their answers.
In a darkened classroom, the computer scientists and the cops met over coffee and doughnuts. As students made their presentation, it was clear: Mathematical prowess and meticulous work had paid off.
A computer program custom-made by grad student Alexandru Balan helped the class calibrate the wheelbase of the suspect's car. That key piece of data, coupled with telling details like headlight shape, body contour, and license plate position, led the class to a strong conclusion. The car is a Toyota Camry. It was made in 1992, 1993, or 1994. It has a sunroof wrapped in a wind deflector.
Using the convenience store video, the class sharpened images to better reveal the suspect's face. In a clever turn, students used calibration techniques and measurements from the doorway, counter, and other fixed objects in the convenience story to create a "virtual pole" that allowed them to gauge the suspect's height with a strong degree of certainty. The killer was five feet six or five feet seven.
Police plugged the vehicle information into a state database. There were 76,000 '92-'94 Toyota Camrys registered in Virginia. Add in the sunroof and likely paint color possibilities and that number dropped to about 600 cars. Sharper images of the suspect's face and a new height estimate were turned over to the county's police sketch artist.
"I'm pretty impressed," Stromberg said. "These students went above and beyond and came up with good information that gives us a lot of direction. We've got something where we had nothing. Eventually, this guy is going to get caught."
In the meantime, the cops are nominating the computer scientists for commendations. The awards are the highest civilians can receive from county police.
"It would be great to get a plaque," Rachlin said. "But I think everyone, at this point, just wants this guy caught."