WARush

TAU researcher turns film sequences into "genetic code" to catch video pirates

You know when you're watching a pirated film downloaded from the Internet — there's no mistaking the fuzzy footage, or the guy in the front row getting up for popcorn. Despite the poor quality, pirated video is a serious problem around the world. Criminal copyright infringement occurs on a massive scale over the Internet, costing the film industry — and the U.S. economy — billions of dollars annually.

Now Dr. Alex Bronstein of Tel Aviv University's Department of Electrical Engineering has a new way to stop video pirates. With his twin brother Michael and Israeli researcher Prof. Ron Kimmel, he has developed the ultimate solution: treating video footage like DNA.

Sequencing the video genome

"It's not only members of the animal and plant kingdom that can have DNA," says Dr. Bronstein, who was inspired by DNA sequencing tools used in bioinformatics laboratories. "If a DNA test can identify and catch criminals, we thought that a similar code might be applicable to video. If the code were copied and changed, we'd catch it."

Of course, video does not have a real genetic code like members of the animal kingdom, so Dr. Bronstein and his team created a DNA analogue, like a unique fingerprint, that can be applied to video files. The result is a unique DNA fingerprint for each individual movie anywhere on the planet.

When scenes are altered, colors changed, or film is bootlegged on a camera at the movie theatre, the film can be tracked and traced on the Internet, explains Dr. Bronstein. And, like the films, video thieves can be tracked and caught.

The technology employs an invisible sequence and series of grids applied over the film, turning the footage into a series of numbers. The tool can then scan the content of Web sites where pirated films are believed to be offered, pinpointing subsequent mutations of the original.

The technique is called "video DNA matching." It detects aberrations in pirated video in the same way that biologists detect mutations in the genetic code to determine, for example, an individual's family connections. The technique works by identifying features of the film that remain basically unchanged by typical color and resolution manipulations, and geometric transformations. It's effective even with border changes, commercials added or scenes edited out.

Finding a common onscreen ancestry

The researchers have set their sights on popular video-sharing web sites like YouTube. YouTube, they say, automates the detection of copyright infringement to some degree, but their technique doesn't work when the video has been altered.

The problem with catching bootlegged and pirated video is that it requires thousands of man-hours to watch the content being downloaded. Production companies know their only hope in recouping stolen content is by automating the process. "Video DNA" can provide a more accurate and useful form of this automation.

——A proposed "proof" is probably a bust--but even failed attempts can advance computer science.

Programmers and computer scientists have been buzzing for the past week about the latest attempt to solve one of the most vexing questions in computer science: the so-called "P versus NP problem."

Vinay Deolalikar, a research scientist at HP Labs in Palo Alto, CA, posted his "proof" online and sent it to several experts in the field on August 6. Colleagues immediately began dissecting the proof on academic blogs and wikis. Early reactions were respectful but skeptical, and the current consensus is that Deolalikar's approach is fundamentally flawed.

A solid proof would earn Deolalikar fame and fortune. The Clay Mathematics Institute in Cambridge, MA, has named "P versus NP" as one of its "Millennium" problems, and offers $1 million to anyone who provides a verified proof.

But "P versus NP" is more than just an abstract mathematical puzzle. It seeks to determine--once and for all--which kinds of problems can be solved by computers, and which kinds cannot. "P"-class problems are "easy" for computers to solve; that is, solutions to these problems can be computed in a reasonable amount of time compared to the complexity of the problem. Meanwhile, for "NP" problems, a solution might be very hard to find--perhaps requiring billions of years' worth of computation--but once found, it is easily checked. (Imagine a jigsaw puzzle: finding the right arrangement of pieces is difficult, but you can tell when the puzzle is finished correctly just by looking at it.)

NP-class problems include many pattern-matching and optimization problems that are of great practical interest, such as determining the optimal arrangement of transistors on a silicon chip, developing accurate financial-forecasting models, or analyzing protein-folding behavior in a cell.

The "P versus NP problem" asks whether these two classes are actually identical; that is, whether every NP problem is also a P problem. If P equals NP, every NP problem would contain a hidden shortcut, allowing computers to quickly find perfect solutions to them. But if P does not equal NP, then no such shortcuts exist, and computers' problem-solving powers will remain fundamentally and permanently limited. Practical experience overwhelmingly suggests that P does not equal NP. But until someone provides a sound mathematical proof, the validity of the assumption remains open to question.

Even if Deolalikar's proof were found to be sound, then the question remains--what impact would such a proof have on relevant areas of computing?

Superficially, one might think the answer is "not much." "Proving that P does not equal NP would just confirm what almost everyone already assumes to be true for practical purposes," explains Scott Aaronson, a complexity researcher at MIT's Computer Science and Artificial Intelligence Laboratory.