CS280 "Computer Vision"
Final Project. 

Siddharth Jain , Cheng Chang ,  Almudena Konrad
( morpheus@eecs.berkeley.educchang@cs.berkeley.edualmudena@cs.berkeley.edu )

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.


Two Approaches:


        Fig. 1




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:

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:

Problems faced:



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:

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


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]
                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



[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.