IMAGE INPAINTING:

This project is based on an image inpainting algorithm proposed by Marcelo Bertalmio, Guillermo
Sapiro, Vicent Caselles, and Coloma Ballester. Image inpainting is, at its heart, a noise removal
algorithm. Given an image and a binary mask covering the noise, the algorithm attempts to fill in
the mask, and the result is a seamless image.

The general idea behind image inpainting is to look at the contours of the image and to try to
extend them into the masked region in a continuous manner. The places where these contours are
most prominent is along edges. This algorithm tries to extend these edges and the colors between
them correctly so that they match up across the mask. 

The algorithm consists of several iterations of "inpainting" followed by an iteration of
anisotropic diffusion. We wrote the inpainting code ourselves and adapted Robert Estes'
implementation of Adel's MCD algorithm for anisotropic diffusion.

USER INTERFACE:
The interface consists of two windows: the picture window and the concole window. The primary user
activity is drawing the mask over the area to be repaired. The mask is drawn with the left mouse
button and erased with the right mouse button. Whenever the user initiates a file I/O operation,
the file name is to be typed into the console window.


left mouse drag - draw mask
right mouse drag - erase mask
'C' - clear mask
'u' - unlimited undo (of mask drawing)
'r' - redo (mask drawing)
'U' - toggle undo on/off (off saves some memory -- not much)
'b' - brush size (rotate between three sizes)

't' - toggle mask display on/off
'c' - cycle through mask colors

's' - save image
'M' - save mask
'L' - load mask
'+' - one iteration of inpainting
'd' - one iteration of anisotropic diffusion

'D' - toggle diffusion on/off
'i' - 100 iterations, followed by a step of diffusion, if diffusion is on
'I' - 2000 iterations, followed by a step of diffusion, if diffusion is on
'V' - specify how many blocks of 100 iterations of inpainting to do, followed by a step of
diffusion, if diffusion is on

'a' - 15 iterations of inpainting, followed by 2 steps of diffusion
'A' - specify how many blocks of 15i/2d


INPAINTING:
The inpainting algorithm measures the smoothness of the image and uses this to decide how to
extend contours through the masked region. It uses the Laplacian as a smoothness indicator. To
find edge contours, we us a vector perpendicular to the gradient. The gradient of the image points
in the direction of greatest increase. Along edges, the gradient points perpendicular to the edge
because the greatest change in the value of the image is across an edge. 

Image inpainting is an iterative algorithm that only changes pixels in the mask. In order to get
from step n to step n+1:

define L(x,y) = 2D Laplacian at pixel (x,y)
dL is a vector, the change in smoothness to the left, right, top, and bottom of the current pixel
N is a vector, a vector perpendicular to the gradient
G is a scalar, a measure of the length of the gradient
Update is a pixel array
Image is a pixel array, the image at step n
ImageNext is a pixel array, the image at step n+1
deltat is a scalar, the step size for updating an image

for every pixel (x,y) in the mask
        dL(x,y) = (L(x+1,y) - L(x-1,y), L(x,y+1) - L(x,j-1))
        N = normalized vector perpendicular to gradient
        B = dL . N
        G = length*(N)
        Update(x,y) = B * G
        ImageNext(x,y) = Image(x,y) + deltat * Update(x,y)
length* is a special measure of length that needs to be used in order to get stable results. It is
defined as
_x - x direction
_y - y direction
_f - forward derivative - calculate derivative as difference between pixel in front and current
pixel
_b - backard derivative - calculate derivative as difference between current pixel and pixel in
back
_m - minimum of value and 0
_M - maximum of value and 0
if (B > 0)
        length* = sqrt(Image_xbm^2 + Image_xfM^2 + Image_ybm^2 + Image_yfM^2)
else
        length* = sqrt(Image_xbM^2 + Image_xfm^2 + Image_ybM^2 + Image_yfm^2)

ANISOTROPIC DIFFUSION:
After every several steps of inpainting, we run an iteration of anisotropic diffusion. Anisotropic
diffusion is one approach to noise removal because it tends to sharpen edges while smoothing over
continuous regions. It is used here for two reasons. It helps to smooth over some of the parts
filled in by the inpainting algorithm. It also helps to join edges across the mask as they are
being drawn in so that they will be continuous. We adapted Robert Estes' implementation of Adel's
MCD algorithm for our use.

OPTIMIZATIONS
We implemented a number of optimizations in an effort to make the program faster and more responsive. 
The image is kept in a format that GL can read directly (which allows for fairly quick redraws). 
However, for large images, even this incurs a noticable delay, so for most mask and image manipulations, 
we draw the changed pixels directly to the screen to avoid whole-image redraws. The mask itself is 
stored in a bitfield, and we developed fast algorithms for iteration and modification which utilize 
the fact that the mask is usually sparse. 

Undo and redo are also memory-efficient; although we must dynamically allocate memory as the user 
interacts with the program, we use a dynamic, scalable vector class which avoids costly linked lists
and pointers. As a result each pixel change requires only about 10 bytes of storage on average (4 each for 
x and y coords, 1 for indicating the type of operation, and 1 [on average] for pointing to the next 
vector).

For the inpainting and diffusion algorithms, we used inline functions and pass-by-reference as much as 
possible, and tried to avoid tedious iterations over the whole image. Diffusion is a very costly 
algorithm; our current implementation requires about 3x as much memory to run as the original image. 
There are likely more efficient implementations out there, but we couldn't think of a better way to 
implement it that would still be fast.


--------------------------------
Published Paper
ps file

Original Paper: Preprint
http://www.ima.umn.edu/preprints/dec99/dec99.html

Anisotropic Diffusion Code
http://info.cipic.ucdavis.edu/ftp/estes/ 

Implementation of inpainting
http://www-users.itlabs.umn.edu/~rams0053/