Wing Yung and AJ Shankar
This is a high-bandwith page. Sorry. It also looks best in a big browser window (> 800x600).
Readme.txt: a a guide to the UI, the theoretical aspects of the algorithms, and the technical aspects of the implementation.
In a nutshell, Image Inpainting is an iterative method for repairing damaged pictures or removing unnecessary elements from pictures.
This is the famous "cracked-plate" photograph of Abraham Lincoln taken by Alexander Gardner on February 5, 1865. On the left is the original, and on the right is the photo reconstructed by 10000 iterations of the Image Inpainting algorithm we implemented. To see the noise mask we used to produce this image, click here. The inpainting process took two minutes and 25 seconds on a Pentium II 450 with 128 megs of RAM. The algorithm is described in "Image Inpainting", an unpublished paper by Marcelo Bertalmio and Guillermo Sapiro of the University of Minnesota and Vicent Casellas and Coloma Ballester of the Universitat Pompeu Fabra.
Note that if you look very closely at the inpainted image, you can detect where the crack used to be; this is, of course, because you know exactly where to look and what to look for. In our experience people who do not have such knowledge (i.e. only see the final inpainted image) do not notice any evidence of tampering.
The majority of this page will be focused on the results of the program we implemented, as opposed to how it works. However, for a more theoretical summary, as well as some details about the user interface, read the readme.
Here's our favorite squirrel performing some magic. Levitation, baby. View the original here, and the noise mask here.
Looks like Shlomo put an easter egg in our CS275 renderer...
Here's the inpainted image, and the mask used. Unfortunately you can see some artifacts, especially on the wavy background plane. Also since part of the first 'o' follows the contour of the red ball, the algorithm has nothing with which to re-establish the curve, and so some feathering occurs. However for the most part on the smooth gradients of the balls it has no problems inpainting accurately.
The algorithm also fails on noisy textures, where derivates of surrounding pixels are not a good indication of what lies in between. For instance, view this vandalized image: outpool.jpg, and the corresponding inpainted one: outpool3.jpg (mask here). Most of the text is wiped out just fine; however, text on the water leaves noticable streaks, since the actual water is so variable.
The noise masks (which tell the algorithm which areas of the image to fix) can be constructed just by dragging the mouse (left button down) over the relevant areas. We provide an eraser (right mouse button), three brush sizes for drawing and erasing, and unlimited undos/redos. Additionally, the mask color can be cycled if it is too similar to the color of the picture, and masks can be saved and loaded for future use.
Here's an example of the progressive nature of the inpainting algorithm. View
big Linc after 100 iterations (below), 500, 1000,
2500, 5000. 10000
is what you see up top; after 20000, there isn't
much difference. In these cases, anisotropic diffusion is applied after every
Abe after 100 iterations and one diffusion.
We decided to see how the image would look without diffusion. Here is the diffusionless
inpainting after 100, 1000 (below), and 20000
steps. By 1000 steps you can clearly see some color artifacts; as a result,
by 20000 the crack is still somewhat visible, and there are green and red patches
After 1000 steps without diffusion, we can see splotches of (incorrect) color along the crack.
Furthermore, we tried the method suggested in the paper of doing 15 iterations
followed by two steps of diffusion, instead of 100/1 as we do normally. The
resulting image does not do nearly as good a job:
Abe Lincoln with some funky cowlicks.
We have no good way of comparing the speed of our algorithm with the speed of theirs; they seem to be within an order of magnitude, however. We spent a considerable amount of time optimizing the GL interface (avoiding unneccsary redraws, using efficient display methods, etc.), and the inpainting and diffusion algorithms (efficient data structures and algorithms) but certainly there is room for improvement. And 2.5 minutes for Lincoln is clearly beyond the realm of interactive use.
We believe that the tools we provide for the mask are fine, since the mask can be edited externally (for instance, with Photoshop) and therefore you can employ whatever lasso/magic wand tools you like.
As mentioned in the paper, the algorithm could be made far more useful if it were combined with a texture synthesis algorithm in filling in large areas.
Try It Out
Want to try inpainting? The executable runs under Win32 and requires the Glut dlls. Get it here. Input files must be in 24-bit TARGA (.tga) format.
firstname.lastname@example.org | email@example.com