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.

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.