Object Removal

Introduction

Our project analyzes object removal from images in depth. Object removal is a generic term that describes manipulating images to accentuate or hide specific aspects of the image. Some of the applications of object removal include removing a person from an image altogether, removing an object that is occluding the primary point of interest, removing scratches/distortions from images for the purposes of image restoration, or even removing text that has been superimposed on the image. There are quite a few techniques that have being employed to accomplish this task, each having it’s own benefits and drawbacks. In this project, our goal was to explore two of these techniques, specifically exemplar-based inpainting and seam carving.

Applications


Figure 1: Texture Modification	Figure 2: Image Restoration	Figure 3: Object Removal

Background

Exemplar-based texture synthesis algorithms suffice to capture both the texture and the structure of the image. The paper titled “Object Removal by Exemplar-Based Inpainting” by Criminisi and Toyama was the basis of our investigation into object removal. Criminisi and Toyama present the details of an exemplar-based algorithm that is able to capture both texture and propagate structure into the target region.

Methods

Exemplar-based inpainting techniques, in general, remove a objects by replacing them with a visually plausible backgrounds. The core of their algorithm is broken down into two parts. The first part fills holes in images by propagating linear structures into the target region. The intuition behind this techniques arises from the “Connectivity Principle” of vision psychology, which states that broken lines tend to be connected. The second part addresses composite textures - multiple textures interacting spatially. The idea behind this part is to fill in larger areas of an image by repeating the textures that surrounds the target region with some level of stochasticity. This is done in an onion-peel like approach starting from the outer layers and moving inwards towards the centre of the target region.

At first the user selects the following parameters:

1. The user selects a target region,Ω, to be removed

2. All exemplar-based techniques fill the target region using patches, Ψ, instead of pixels for efficiency reasons. The user then selects the window-size for patches - in practice it is slightly larger than the largest distinguishable texture element

Figure 4: Structure propagation by exemplar-based texture synthesis

After the parameters have been selected, the object removal algorithm is able to run. In this algorithm, each pixel maintains a color value and a confidence value. Only the patches adjacent to the fill front are given a priority value as well. The algorithm repeats the following three steps till all the pixel values in the target region are assigned a color

Figure 5: Notation Diagram

1. The first step is to compute priorities for the patches that are adjacent to the fill front - initially this will only be the patches adjacent to the source region. Patch priorities are critical since they determine which of the patches gets filled in first. The algorithm fills in the patches with the highest priority and for that reason is known as a best-fill first algorithm. The priority of a patch seeks to balance propagating linear structures with filling in composite textures. As a result, it is defined as the product of two terms, the confidence term and the data term.

|Ψp| is the area of Ψp, α is a normalization factor, and np is a unit vector orthogonal to the front δΩ in the point p. The C(p) term is set to 0 for the target region and set to 1 for the source region during initialization. The confidence term measures how much reliable information surrounds the point p and is being used to first fill those patches that have more of the surrounding pixels filled in. This term gives preference to those patches that at the fill front, i.e. closest to the source region. The data term, on the other hand, gives preference to the linear structures. It is a function of the strength of the linear structures hitting the front δΩ and boosts the priorities of patches that lie along the path of these linear structures.

Figure 7: Effects of data and conﬁdence terms

2. The second step involves propagating texture and structure information. Once all the priorities have been calculated, we take the patch with the highest priority and fill it with information from the source region. The information from the source region is directly sampled as opposed to being propagated using diffusion. Diffusion leads to image smoothing and as a result a blurry fill-in, especially of large regions.

The patch in the source region that is the most similar to the target patch is used to fill the pixels of the target patch. The similarity is measured using the sum of squared distances of the already filled pixels in the target patch. The CIE Lab color values are used seeing as the difference between the pixels is somewhat representative to the difference in visual similarity.

3. The third step involves updating confidence values of the target patch that has just been filled-in. The confidence of the updated pixels is copied over from the pixels that were previously filled in.

The figure below shows the pseudo-code of the algorithm described above.

Figure 6: Region Filling Algorithm

We analyzed the exemplar-based inpainting algorithm by running it on a set of images while varying the size and location of the target region on a subset of these images. This allowed us to determine the impact of the fill region as well as it allowed us to determine on what set of images this algorithm worked well for and for what set of images it didn’t work well for. We measured the success/failure of the algorithm visually by either assigning it a pass or fail. The images we used were a combination of synthetic and real photographs with a variety of textures as backgrounds.

We also visualized the confidence and data terms to further analyze the algorithm and give us a better sense on which term was dominating. All of our analysis was done on Matlab seeing as Matlab is best suited for matrix manipulation and image processing tasks.