Hole Filling in Images (aka Image Inpainting)

The Problem Statement:

Given an image I with regions where rgb values of pixels are not known (holes) we want to fill these holes (determine rgb values of pixels) as sensibly as we can from the information available to us from the rest of the image.

Applications:

Restoration of old and damaged photographs.
Special Effects (removal of entire objects from images like microphones or wires, ref. figures above).
Removal of superimposed text like dates, subtitles or publicity.

Two Approaches:

Filling in by Joint Interpolation of Vector Fields and Gray Levels by G. Sapiro et. al. in IEEE. Trans. Image Processing, Aug. 2001, pp. 1200[1]. The idea is to take a band B around the hole and to fill the hole using the geometric and photometric information outside the hole (see Fig. 1). The authors come up with a variational model and attempt to continue the level sets of the image inside the hole by minimizing an energy functional.

Fig. 1

Limitations:

essentially deals with local inpainting i.e. does not rely on global feature or pattern recognition. An example of this limitation is illustrated in Figure 2. In this image the occluded domain is the square in the middle. By looking at both images, we would fill in the left image with black, and the right image with white. However, through local impainting, both images would fill in the middle square with black.

cannot fill holes in textured images and thus cannot be applied to natural images[2]. Ref. Mathematical Models for local non-texture inpaintings by Tony Chan and Jianhong Shen at http://www.math.ucla.edu/~imagers

can fill only small holes because for big holes extending the level lines using the variational model does not help

time taken will go up as the area of the hole increases

Another Approach:

Instead of using the complicated method of Sapiro we can use a very simple trick: take a window around the hole, now scan the image with this window over regions where we know rgb values and if you find a region which matches with the window just copy and paste it onto the hole. This is the idea of image quilting[3]:

Image Quilting for Texture Synthesis and Transfer by A.A. Efros and W.T. Freeman, Proc. SIGGRAPH 2001, Los Angeles, CA

Salient Features:

method will work very well on structured patterns and textures

limitation of local inpainting is removed

can be used to fill very big holes

There is an inherent assumption that there is some good region in the image from where we can copy and paste - this actually turns out to be true in many natural images which are repetitive e.g. a building has windows, arches etc. which repeat

But what if a `good match' is really missing?

In this case we have to perform some sort of interpolation/extrapolation of surrounding geometry and rgb levels and expect Sapiro's algorithm to give better result.

So we have the following method:

search the image for holes
take a window around the region to be filled. If the hole is in a `textured region' (a textured region here is used to mean a region for which there is a `good match' somewhere in the image from where we can copy and paste) we should search for a BestMatch else we should use some form of interpolation (we think extrapolation is a better term but are using interpolation following Sapiro).

Problems faced:

(P1) How do you find out if the hole is in a `textured region'?
(P2) What is the size of the window and hence the block which you copy and paste? should it be the size of a `texel'? if so how do you find the size of a texel (element of periodicity in very loose terms) in an arbitrary textured image?
(P3) If you have a very big hole you probably want to fill it piece by piece instead of taking a huge window and trying to match that window.
(P4) How to search the image for a BestMatch efficiently? Searching the image by moving the center of the scanning window pixel by pixel will take insanely long periods of time to do the hole-filling.
(P5) Efros cuts the rectangular patches with a minimum boundary cut as he synthesizes an image so that the boundary between adjacent patches is unnoticable[3]. How to find the minimum boundary cut(s) for an arbitary shaped patch with arbitary shaped overlap(s)?

Solutions:

(S4) The problem of doing an efficient search is addressed by using Gaussian Pyramids (ref. Chapter 7). Figures below show pyramids for an example image (original image 512x512 reduced to 128x128 by successive smoothing and subsampling)

(S3) Instead of searching for holes and taking a window surrounding the hole do a much simpler thing: go in raster scan order, store all hole pixels which are at the boundary of holes into an array and process this array. This gives one more advantage over Sapiro's method: there is no need of recognizing the holes and finding a window that surrounds the hole
(S1, S2) The first two questions are not easy to tackle. We address them in the following (indirect?) way: don't bother to find out if the hole is in a textured region or not, find the BestMatch. If BestMatch differs by an amount greater than a threshold then reduce the window size (make it adaptive) and again find the BestMatch. After doing this say 3 times or if the window becomes very small if we still don't have a good match then we should do some interpolation.
Fine Points:
- we should carefully choose a suitable metric which measures the difference of a block in the image from the patch we are trying to match. The metric we use is
  d = RMS difference of rgb values between the two windows/sqrt(N)
  where N is the # of pixels used in determing the RMS value
- the threshold is related to the metric you choose and based uopn our metric actually depends on the window size as well as what particular image you are trying to process (thus we make it a user-specified parameter).
(S5) Our results show that making the minimum boundary cut is not crucial and so we simply don't make any cuts.

We now come to the question of what interpolation to use if we are unlucky not to get a good match:

Using Sapiro's method makes little sense because:

we did not `recognise' the hole. We just know that we have a window which is centered at an unknown pixel (recall Sapiro's method requires the program to recognize the holes and take bands around them; unknown pixel means the rgb value of the pixel is unknown)
If the hole is very big Sapiro's method will take a long time (have to minimise a functional) and won't give any particularly impressive result.

Instead of using Sapiro's method we use the following tricks:

Do Simple Averaging: just set the value of the unknown pixel (at the boundary) equal to the average of its known neighbors. If you do lot of averaging it will lead to blurring; also if the neighboring pixels differ a lot in their rgb values doing simple averaging is not advisable so in these cases:
If all the neighbors (of the unknown pixel) to the left are known just set the rgb of the unknown pixel equal to its immediate left neighbor. Adopt similar strategy for right, top, bottom neighbors. Fig. 4 illustrates this approach. Pixels 1, 2 and 3 are known and pixel R is unknown. On all the images, R takes the rgb values of 2, which is the closer pixel.

Summarising then we have the following algorithm:

while(there are holes in the image)
{
    get boundary points of holes into an array B
    while(B is not fully processed)
    {
        let ctr denote the active index of B
        take a window centered at B[ctr] and find the BestMatch corresponding to this window
        if d(BestMatch) >
            reduce the size of window and find the BestMatch again;
            stop this when you have exceed some N times or when the window size has become very small
         if d(BestMatch) <
                copy and paste BestMatch onto the hole centered at B[ctr]
        else
                do one of the tricks of Simple Averaging etc.
    }
}

Note that the method is very fast (less than 5 min. on a 2.2 GHz PC) and is scalable i.e. can be used to fill very big holes in very big images.

Go to Results Page

Acknowledgements:

Christian Fruh: for suggesting the use of image quilting for hole-filling
Professor David Forsyth: for introducing us to the subject of Computer Vision

References

[1] "Filling in by Joint Interpolation of Vector Fields and Gray Levels", G. Sapiro et. al., IEEE. Trans. Image Processing, Aug. 2001, pp. 1200.
[2] "Mathematical Models for local non-texture inpaintings", Tony Chan and Jianhong Shen, http://www.math.ucla.edu/~imagers.
[3] "Image Quilting for Texture Synthesis and Transfer by A.A.", Efros and W.T. Freeman, Proc. SIGGRAPH 2001, Los Angeles, CA.