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
 |
 |
 |
|---|---|---|
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.
Seam carving algorithms function is to preserve the most relevant aspects of an image, thus allowing for altercations to be made to the image that are minimally detectable. The paper entitled “Seam Carving for Content Aware Image Resizing” by Shai Avidan and Ariel Shamir was the basis of our seam carving implementation for image removal. Avidan and Shamir present the details of the seam carving algorithm and its various uses, which include image resizing, storing dynamically-sized images, object removal, and image content enhancement.
Methods
Exemplar-Based Inpainting
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
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
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.
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.
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.
Seam Carving for Object Removal
A seam is defined as an optimally 8-connected path of pixels on a single image spanning from either top to bottom or left to right. Optimality is defined by an image energy function which attempts to label pixels based on the amount of content they possess. By carving out or inserting seams in both directions, we can effectively retarget the image to a new size while protecting the content of the image. Seam carving can also be used to for image content enhancement and object removal, the latter of which is the subject of our project. The intuition behind seam carving is that by carving out pixels of the least energy and retaining pixels with high energy, we can effectively adjust the size of the image without producing a substantial visual effect. This same logic can be abstracted to object removal, that by removing the seams connected the object with least energy we can remove the object while producing minimal visual changes to the remainder of the image. The seam carving algorithm supports several types of energy functions such as, gradient magnitude, entropy, visual saliency, and eye-gaze movement. The most popular energy functions are gradient magnitude and histogram of gradients, we instantiated the former.
Implementation of object removal through seam carving
The user must first select the following parameters:
1. The user must select whether he wishes to carve vertical seams, horizontal seams, or a combination of both vertical and horizontal seams. 2. The user must select an algorithm for computing the energy of an image. The most prevalent of which are Histogram of Gradients and gradient magnitude.
These are decisions that are currently made by the designer, but the options to chose can be extended to the user to best match his intended image. Based on these decisions, the programs is able to compute the image energy and remove seams in the desired dimensions. The energy image is strongly negatively weighted at the pixels of the object to be removed, in order to ensure that seams intersecting the desired object are removed with priority.
Energy Computation
1. The first step is to compute the energy function of the image based on the gradient magnitude. A strong energy function is integral to the success of the seam carving algorithm because ultimately these energies will determine the seams to be removed from the image and are responsible for preserving the images content. There are several acceptable top-down and bottom-up algorithms for assigning energy values to the image. Top-down methods include the output of face-detectors, Harris-corners measure, eye gaze measurement, and segmentation. While bottom-up methods include entropy measures, Histogram of Gradients, L1 and L2 norms of the gradient, and gradient magnitude. The performance of each of these methods is highly dependent on the composition of the selected image. We chose the work with the gradient magnitude, e1, due to its relatively consistent performance across a range of images.
Weighted target object
2. The second step in our implementation is to introduce a predefined weighting system to the energy image. We introduce a negative energy to the pixels selected for removal from the image in order to attract seams to the desired part of the image and to ensure that the desired aspects are removed. This is a slight modification from the traditional seam carving approach in which only the energy function is used to determine the relevance of pixels.
Seam selection
3. The third step is to identify the optimal seam. The optimal seam could be either horizontal or vertical dependent on the desired retargeting of the image. A seam is a connected path of pixels spanning from either left to right or top to bottom.
Let I be a n x m image, formally we define a vertical seam to be:
We select the optimal seam for removal from the image, mean we select the 8-connected path where the summation of the energy values of all the pixels are the least.
This minimal seam is calculated through dynamic programming. The image is traversed from the second row to the last row and the commulative minimun energy M for all possible connect seams M is calculated for each (i,j):
at the end of the process the minimum value of the last row in M will indicate the end of the minimally connected seam in the image. From here, we backtrack from this minimum entry on M to find the optimal seam.
4. This seam is removed by traversing the seam and shifting each pixel to the right of the seam over by one, effectively removing a column from the image.
5. These steps are repeated until the object is completely removed.
Results/Analysis
Exemplar-Based Inpainting
Best Cases
Exemplar-based inpainting is best suited when an entire object is to be removed. The window-size for the images below was set to 9X9 pixels. The surrounding environment, for the images below, is sampled directly and is able to fill in the hole left by the object.
 |
 |
 |
 |
|---|---|---|---|
 |
 |
 |
 |
|---|---|---|---|
 |
 |
 |
 |
|---|---|---|---|
 |
 |
 |
 |
|---|---|---|---|
 |
 |
 |
 |
|---|---|---|---|
 |
 |
 |
|---|---|---|
Worst Cases
Exemplar-based inpainting does not work well when an arbitrary chunk of the image is to be covered. The object chosen to be removed must be taken as a whole, otherwise deformations can occur
|
 |
 |
 |
|---|---|---|---|
Seam Carving for Object Removal
We analyzed the seam carving object removal algorithm by visually analyzing the results on a series of test images. These images varied in content, color, foreground and background composition, as well as texture, and target object size. We performed basic visual saliency test to see if the altercation were immediately apparent. We also performed more detailed analysis to determine where and why the algorithm left visual artifacts.
The algorithm performed well for both small and medium sized target object, but left the image unrecognizable when removed large objects. Large objects produced poor results largely because the large number of seams that had to be removed in order to remove the object entirely. The algorithm also showed that if could work well in both cluttered and plain backgrounds, but showed easily recognizable errors when the image contain patterned backgrounds. We also produced visual displays of the images energy functions and selected visual seams, in order to better visualize how the content was being manipulated.
Best Cases
 |
 |
 |
 |
 |
|---|---|---|---|---|
 |
 |
 |
 |
 |
|---|---|---|---|---|
 |
 |
 |
 |
 |
|---|---|---|---|---|
Worst Cases
|
 |
 |
 |
 |
|---|---|---|---|---|
 |
 |
 |
 |
 |
|---|---|---|---|---|
Conclusions/Future Work
Conclusions
Seam Carving
Seam Carving works best when
- Low energy seams can be found
- Missing information in the image is primarily removed from the background
- The object removed is relatively small
Seam Carving doesn't work well when:
- The size of the object is large
- On diagonal lines/textures
It is ideal for image resizing but can produce desirable results when used for object removal
Exemplar-Based Inpainting
Exemplar-Based Inpainting works best when
- The image contains linear structures
- For almost all textures surrounding the object to be removed
- The object removed is small-medium
Exemplar-Based Inpainting doesn't work well when
- Run on a partially selected object
- The size of the object is very large
Future Work
- Try different similarity metrics for Exemplar-Based Inpainting – cosine similarity, etc.
- Extend Seam Carving to 3D (i.e. videos) - pick seams that are minimal across the entire video segment
- Experiment with different energy functions in Seam Carving - try using the CIE Lab space
References
- Avidan and Shamir, “Seam Carving for Content-Aware Image Resizing”
- Criminisi, Perez and Toyama, “Object Removal by Exemplar-Based Inpainting”
- Criminisi, Perez and Toyama, “Region Filling and Object Removal by Exemplar-Based Image Inpainting”
- Lanman, “Texture Synthesis and Manipulation”, http://alumni.media.mit.edu/~dlanman/courses/en256/Lanman-Inpainting-Final%20Report.pdf
- Sooraj Bhat,"Object Removal by Exemplar-based Inpainting - A CS7495 Final Project by Sooraj Bhat",http://www.cc.gatech.edu/~sooraj/inpainting/
Appendix I
Exemplar-Based Inpainting Code: http://white.stanford.edu/teach/images/5/55/ExemplarBasedInpainting.zip
Appendix II
Work Breakdown
The work breakdown was quite even for this project. We helped each other resolve bugs in the code and in understanding both the algorithms.
Devin worked on:
- Implementing object removal using Seam Carving
- Generating results using Seam Carving for object removal
- Generating test set
- Conclusion and Future Work
Raj worked on:
- Updating code for the implementation of Exemplar-Based Inpainting [5]
- Generating results using Exemplar-Based Inpainting
- Conclusion and Future Work
- Generating test set
- Finding applications for object removal