CS280 "Computer Vision"
Final Project.
Siddharth Jain , Cheng Chang , Almudena Konrad
( morpheus@eecs.berkeley.edu , cchang@cs.berkeley.edu
, almudena@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.
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
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:
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.