Bytes, Camera, Action at IMA Workshop
June 12, 2006
Before: Like many classic movies, Jean Cocteau's 1946 La Belle et la B�te has deteriorated badly.
Barry A. Cipra
If you're a movie buff, the Institute for Mathematics and its Applications at the University of Minnesota was the place to be in early February. All the more so if your cinematic tastes run to the classics.
Many classic movies are in bad shape, marred by dust, scratches, and general deterioration of the film stock. Measures available in these digital days to make old movies watchable were a theme of a workshop, The Mathematics of Film Editing and Restoration, held at the IMA, February 6�10. Six dozen applied mathematicians, computer scientists, and digital wizards from the film industry met to discuss technical challenges in the manipulation of moving images. Speakers considered the ins and outs of camera tracking, video "texture," and googlesque searching of full-length feature films, along with techniques for dirt, grain, and scratch removal.
As Jay Cassidy, a film editor at Mathematical Technologies Incorporated, put it, "We're in Act I of a digital revolution."
It's a revolution driven by economics and algorithms. Film buffs have long bemoaned the unavailability of obscure titles, and historians fret about the disintegration of valuable archival footage. (Many old "movies" do little more than document ordinary events of everyday life, but that's the sort of thing historians find fascinating. One of the earliest, eeriest movies, for example, shot by the brothers Lumi�re, shows only a weary stream of workers exiting a factory gate at the end of a shift---not exactly entertaining, but oddly engrossing. Some such prints survive, in various states of disrepair, but many have deteriorated, and much, of course, is simply lost.) The relative cheapness of bits etched on a plastic disk or stored somewhere on a server---and the public's willingness to pay for packaged or packeted products---increasingly make such problems seem solvable. A growing fraction of the Internet Movie Database is finding its way onto DVD; now available, for example, is Mary Ellen Bute's 1937 short Parabola (in the Unseen Cinema collection).
Digital De-dirting
Once a reel of film has been scanned into digital form, powerful new algorithms can be brought to bear on it, automatically detecting and correcting the ravages of time. Edge-detection and segmentation algorithms, for example, can be used to analyze individual frames. The results from a set of consecutive frames can distinguish animate from inanimate objects within the picture, even if everything appears to be moving because the camera was doing a zoom or pan. If some "object" suddenly appears on one frame but is absent from adjacent frames, it's probably dirt---a particle of dust or a bit of ash from some careless editor's cigarette. (If, on the other hand, everything suddenly and permanently changes, the likely cause is a cut from one scene or camera angle to another.) Likewise, certain persistent features that wander about or vary at random can be identified as scratches, graininess, or flicker. (Graininess is a result of chemical degradation; flicker often has a biological cause: In many cases the culprit is a fungus feeding on the gelatin of the physical film.) Another kind of blemish consists of frames that are partially torn away.
The more difficult step is to fix the digitized flaws. Several speakers, including Cassidy and his MTI colleague Kevin Manbeck, showed before-and-after versions of clips from old movies. The differences are often stunning. Shadowy, indistinct noise-pocked scenes become sharply defined film noir. By some criteria, in fact, the results can be too good: We're so used to old movies looking bad that the restored versions sometimes seem suspiciously modern.
Cassidy and Manbeck demoed MTI's digital restoration system, Correct DRS, a partially automatic system that film restorers can work with interactively. Using frames from the 1962 Truffaut film Jules et Jim, Cassidy showed how an operator clicks on dirt spots to draw boxes around them; the restoration software then removes the spots. The interactivity is important, Manbeck notes: "A fully automated process is going to make mistakes."
Tools are also available for restoring color. Daniel Rosen, senior scientist at Warner Bros., showed a frame from The Wizard of Oz, which has faded badly over the years, side by side with a vibrantly colored restoration. (Rosen spent many years in the aerospace industry, as a signal processing specialist. Working on movies presents its own challenges, he says. "We're talking about an industry built around some of the most frustratingly creative people imaginable.")
Scribbles
Color can also be added. Guillermo Sapiro, a professor of electrical and computer engineering at the University of Minnesota (who, with Lance Williams of Applied Minds and Andrew Zisserman of Oxford University, organized the workshop), described a new method for "inpainting" based on computed paths of "least resistance."
There is, to put it mildly, a great deal of resistance among classic film aficionados to the commercial practice of colorizing black and white movies. Like atomic energy, though, inpainting has benefits in some settings. It can be used, for example, to restore portions of already colored images that have been obscured by text. Film editors can use it to remove unwanted foreground objects. Another useful application is automatic color coding of portions of technical drawings otherwise rendered in shades of gray.
Sapiro calls the method he and others have developed for inpainting grayscale images the "scribble method." The basic idea is for a user---say a film editor or a technical artist---to apply simple streaks of selected colors from the program's palette to various portions of the image. Using the gradient of the grayscale luminence, the algorithm then propagates the scribbled colors; a crisp black line should stop a color short, while the tapering darkness of a shadow should only slow it down.
There are many ways to do the propagation. Sapiro credits a former student, Liron Yatziv, now at Siemens Corporate Research in Princeton, with one of the best methods. As Sapiro recalls it, he gave Yatziv a straightforward assignment---implementation of a standard method---only to have the student return two days later with a much better solution. The key is to define an "intrinsic distance" between any pair of points in the image as the minimum, over all curves connecting the two points, of the integral of the absolute value of the gradient of the luminence. The distance from a given pixel to a given color is then defined as the minimum intrinsic distance between the given pixel and any pixel that has been scribbled with the given color. Finally, the color assigned to each pixel is defined as a combination of the scribbles, weighted according to distance.
The instrinsic-distance method sounds as if it could be slow, but Yatziv, Sapiro, and Alberto Bartesaghi, also of the University of Minnesota, have found a fast, O(N) implementation based on the fast marching algorithm for solving Eikonal equations. Examples of the method, including a colorized clip showing Charlie Chaplin in Modern Times and a try-it-yourself demo, can be found at http://mountains.ece.umn.edu/~liron/colorization/.
"We love distance functions," Sapiro says. Moreover, he points out, scribbles are not limited to color. They can also indicate brightness, depth, or even "do not touch" regions you want protected from further editing---essentially "whatever attribute you want propagated." Mathematically, he adds, there is an interesting unsolved problem: Given, for example, an original color image and a black and white version of it, what is the optimal "scribble" on the black and white version from which the propagation algorithm will reproduce the original? Even a suboptimal solution has potential for color image compression.
Product Placement
Digital technology obviously also facilitates filmmaking itself. The creation of special effects and computer animation are well-known examples. But the placement of such effects within traditional camera-filmed scenes is another application. David Capel of the visual effects software company 2d3 in Oxford, England, and Philip McLauchlan of Imagineer Systems in Guild-ford, England, described their companies' solutions (Boujou and Monet, respectively).
The key challenge, Capel explains, is the convincing insertion of a computer graphic into a scene that has been filmed with a moving camera. A "simple" example will be familiar to fans of (American) football: the line, usually yellow, indicating the location of the next first down, that appears to TV viewers to be painted onto the field. Capel showed a more challenging example in which a gigantic ladybug (for demo purposes) was to appear firmly attached to the roof of an office building filmed in a flyover of a city scene. Without perfect placement in each frame, the bug would appear jittery in the animation.
One solution would be to precisely monitor the movement of the camera, but that kind of information is rarely available. In general, the solution is to infer the 3D position of the camera (along with any changes in its lens settings) from a sequence of 2D frames, using automatic detection of such salient features as the corners of the roof-top. Assuming a static background (usually the case for buildings---unless you're filming an earthquake disaster flick!), computing the camera motion is an exercise in projective geometry. With a bit of outside help, the analysis can also determine which features, such as a rooftop shed or a bird in flight, should occlude the graphic insert and which should be occluded by it.
Richard Szeliski of Microsoft Research in Redmond, Washington, talked about "video texture," in which a short video clip is looped to produce an infinite amount of continuous action. Computational scientists are accustomed to seeing the output of simulations run repeatedly, usually with an abrupt jump when the visualization resets. For such applications, the discontinuity is not a serious problem; indeed, it reminds the viewer that the simulation is restarting. But other applications call for seamless looping. The designer of a video sports game, for example, may want to incorporate crowd scenes as realistic background. In that case, sudden jumps would destroy the illusion. Likewise, a Web site advertising a beachfront hotel may want to showcase the gently breaking waves hotel guests can expect to enjoy.
Video texture can also be used for subtle animation of portions of ordinarily still pictures. Szeliski showed examples, including a pair of paintings by Monet, one with waterlilies and the other with boats in a harbor, stochastically shimmering in the impressionistic light. (The examples are viewable at http://grail.cs.washington.edu/projects/StochasticMotionTextures/.) So far, Szeliski says, the existing software is for passive viewing applications only. The long-range goal, though, is to integrate documentary realism into interactive video.
Who's That Girl?
[I] Still recall the images that
Seem to live out there
---Eurythmics, For the Love of Big Brother
With all the video and still imagery coming online, there is a growing need for search engines that can sort through purely visual data. Andrew Zisserman demonstrated an image-retrieval system, called "Video Google," developed by the Visual Geometry Group at Oxford. (The name will undoubtedly change, unless the Internet giant buys them out.) The system analyzes images by decomposing them into "visual words"---objects with certain invariant properties that persist even as the viewpoint changes or partial occlusion occurs. The "words" are then indexed and ranked for rapid retrieval.
Ultimately, the goal is to be able to enter an image of an object into a search box and get a ranked list of every scene from the entire database in which that object appears. For now, the demos are done on a movie-by-movie basis, and searches are carried out by selecting items from a frame in one scene (by drawing a box around, say, Bill Murray's face); the search result consists of snippets from other scenes. But the results are already impressive. Zisserman showed examples from Groundhog Day (with Bill Murray)--an especially good choice in that the movie repeats many scenes over and over. In one frame he selected Murray's striped necktie; the search turned up numerous other frames with the same tie, including one in which it was draped over a chair in Murray's hotel room.
The Oxford group's Web site (http://www.robots.ox.ac.uk/~vgg/research/vgoogle/) includes a demo featuring the 1946 movie Dressed to Kill, with Basil Rathbone as Sherlock Holmes. Zisserman also described current work on facial recognition, using examples from the Julia Roberts movie Pretty Woman and an episode of the TV show Buffy the Vampire Slayer. The challenge is to identify characters even when they're shown only in profile, and to keep track of multiple characters who momentarily occlude one another or exit and re-enter a scene. Changes in facial expression present another, related challenge: Ideally, for example, a search would produce all variations on Julia Roberts's trademark smile---or, conversely, on her frown.
Innumerable problems in searching, editing, and restoration of digital video remain, and new ones will doubtless emerge. Rosen mentioned one that arose as Warner Bros. was making the first big-budget movie ever shot entirely in digital: a persistent vertical streak that he calls a "digital scratch." The cause seems to be physical flaws, found in all digital cameras, that depress the response of the occasional photoreceptor. The streak didn't show up on the high-definition monitors used for editing and daily rushes; it became evident only when the movie was projected onto a full-sized screen for studio executives--at which point Rosen recalls hearing a pointed "What the hell is that?"
After: Actor Jean Marias has regained his good looks in this sample frame from the restored version of La Belle et la B�te. Both frames courtesy of Criterion Collection, New York.
Rosen says that his main job was not so much to figure out what caused the problem as simply to edit out the streak. (He was not at liberty to name the movie, but other sources say it's the new Superman movie.) His cautionary tale suggests that people who care about movies will always have a lot of work to do. The IMA workshop showed that the requisite algorithmic tools are coming into focus. One thing is already clear: When Hollywood starts awarding digital Oscars, the recipients will know how to keep them free of scratches.
Barry A. Cipra is a mathematician and writer based in Northfield, Minnesota.
