Patch-Based Inpainting for Object Removal and Region Filling in Images

1 Introduction

The two most commonly used graphical techniques to fill the gap after object removal are image inpainting and texture synthesis. Digital image inpainting refers to the inpainting process performed on digitized images. It is important to have an algorithm that can automatically fill in a region marked by the user. The user provides the image with a marked region to be inpainted, which is referred to as the mask, in a specified color. The filling in of these marked regions by the computer algorithm should result in an image that looks natural and undistorted. Object removal from images is an image manipulation technique. Removing objects from images starts with the masking out of the undesired object and by making a gap at the area occupied by that object. Then this gap is filled using digital inpainting techniques.

Texture replication and propagation are used to fill in gaps in images. Different approaches were developed for synthesizing textures, including statistical and image-based methods. The application of these methods for filling the gaps in an image is called constrained texture synthesis, and it is used for filling images having more textured areas. Neither structural inpainting nor texture synthesis alone can provide the ultimate solution, but the combination of these two produces good results. Image inpainting considers the image as a collection of structures, shapes, and objects that are separated from one another by sharp edges, but each one is itself smooth, and texture considers the low-stochasticity features of the image. Various approaches are introduced to reconstruct images using inpainting techniques, such as level lines, PDE-based inpainting, fluid interpolation, Euler’s elastic, bounded variation, and heat transfer [2, 3, 4, 7, 19].

All such methods have their own advantages and limitations. The proposed patch-based inpainting approach overcomes many of the limitations of earlier approaches.

Automatic digital image inpainting first brought into the field of image processing by Bertalmio et al. [4]. This algorithm imitates the traditional inpainting processes, such as identification of the area to be corrected, marking of the boundary of a region to be filled, and continuing the lines of similar color. These techniques are effective only for small scratches. The algorithms work well in images that are relatively smooth and have low noise or texture. The process cannot fill in regions that are highly textured or that contain large noise, which leads to noncontinuation and blurring of the edges. Since then, there are a number of algorithms proposed to solve the inpainting problem [2, 7, 18]. These are used to fill only narrow gaps in images. They fail to reconstruct large damaged regions in the images. Motion estimation and autoregressive models to interpolate losses in films from adjacent frames are used [16]. The basic idea is to copy the right pixels from neighboring frames into the gap. The technique cannot be applied to still images or films, where the regions to be inpainted span over many frames.

The work [5] decomposes the original image into two components, which are processed separately by inpainting and texture synthesis. The outputs of the two are summed up as the resultant image. This approach remains limited to the removal of small image cracks, and the diffusion process continues to blur the filled region. Drori et al. [10] describes an algorithm that interleaves a smooth approximation with example-based detail synthesis for image completion. Both of these proposed algorithms were extremely slow. The first attempt to use exemplar-based synthesis specifically for object removal was proposed [14]. They proposed that the order in which a pixel in the target region is filled is dictated by the level of “texturedness” of the pixel’s neighborhood. Although the intuition is sound, strong linear structures were often overruled by nearby noise, thus reducing the value of the extra computation. A related technique drove the fill order by the local shape of the target region but fails to explicitly propagate linear structures [6].

Several researchers have considered texture synthesis as a way to fill large image regions with “pure” textures. Pure textures are defined as repetitive two-dimensional textural patterns with moderate stochasticity. This is based on a large research carried out on texture synthesis, which seeks to replicate the texture from a given small source sample of pure texture [9, 13, 15]. These exemplar-based techniques cheaply and effectively generate new texture by sampling and copying color values from the source [1, 12, 17]. It only contains the process to replicate textured areas in the images. In case of regular textures, exemplar-based inpainting works well but fails to replicate structures in the still images.

In contrast with previous approaches, there is a need for a technique that does not require the user to specify where the information to fill comes from and instead be automatically be accomplished by the algorithm. The technique should allow to simultaneously fill in numerous regions containing completely different structures and surrounding backgrounds. In addition, no limitations should be imposed on the topology of the region to be inpainted. Therefore, the patch-based approach of Criminisi et al. [8] seems more appropriate, and a further modification is being proposed in the present article. This results in an algorithm that has the efficiency and qualitative performance of exemplar-based texture synthesis as well as linear structure inpainting.

2 Key Observations and Algorithm

Both image inpainting and texture synthesis have their strengths and weaknesses. Image inpainting, which extends the linear structure into the gap using the isophote information of the boundary pixels, leads to a natural propagation of the linear structures into the gap. However, because the extension is actually using diffusion techniques, artifacts (e.g., blur) could be introduced. Meanwhile, texture synthesis copies the pixels from the existing parts of the image, thus avoiding blur. The shortcoming of texture synthesis is that it focuses on the whole image space and not on resolving the priorities of pixels on texture and linear structures around the boundary of the gap. As a result, texture propagation dominates, and linear structures are not naturally extended into the gap. The result would likely have distorted lines and noticeable differences between the gap and its surrounding area.

One interesting observation is that although image inpainting and texture synthesis seem to differ, they might actually complement each other. If we could combine the advantages of both approaches, we would get a clear gap filling that is the natural extension from the surrounding area. Criminisi et al. [8] proposed an algorithm that exactly does this. They used the sampling concept of Efros et al. [11] and improved on it by considering the isophotes, giving a higher priority to those points that are on the boundary of the gap as well as on structures, isophotes, and corners, which leads to their natural extension into the gap. To identify those points, Criminisi et al. [8] gives a priority value to all the pixels on the boundary of the gap. These important points on the structure and corners will get higher priorities according to the algorithm, and thus, the linear structures would be extended first. For each pixel on the boundary, a patch is constructed with that pixel at the center (Figure 1). The patch’s priority is the product of two elements: a confidence term C(p) and a data term D(p).

Figure 1

Notation Diagram.

Given Patch ψ_p,n_p is Normal to the Contour ∂Ω of the Target Region is the Isophote (Direction and Intensity) at Point P. The Source Region is Denoted by φ. The Entire Image is Denoted with I.

2.1 Computing Priorities of the Patch

Our filling algorithm assigns high priorities to the pixels on corners via the confidence term and simultaneously assigns priorities to pixels on isophotes via data terms; thus, the highest-priority-pixel patch is filled first.

where α is the normalization factor (e.g., α=255).

Priorities are calculated as

where C(p) describes the number of pixels already filled in the patch. Figure 2 shows that the patches, including the corners and thin tendrils, of the target region have a higher priority and are filled first.

Figure 2

Confidence of Pixel p with a 7×7 Patch.

White Indicates the Pixels of the Target Region. Pixels on Sharp Corners have High Confidence and hence are Filled on Priority, which Leads to a Simultaneous Neighboring Structure and Texture Propagation in the Gap.

D(p) describes how strong the isophote is in hitting the boundary. This term boosts the priority of a patch that an isophote “flows” into. D(p) is especially important because it encourages linear structures to be synthesized first and are thus propagated securely into the target region.

The confidence of the source region pixels is initially set to 1 and that of the gap region is set to 0. Once the boundary pixel patch ψ_p is filled, the newly filled pixels of the target region of ψ_p will be assigned the same confidence of p. As the algorithm propagates in target region, the confidence value decreases exponentially, which makes the computed priorities indistinguishable, resulting in an incorrect filling order. Even if the data values are increasing, the shape of the priority curve is dominated by exponentially decreasing confidence values. This effect is more noticeable when filling a large target region. This intense dominance is due to the effect of multiplication. Thus, the original priority in the multiplicative form needs to be changed to avoid a pronounced decreasing effect. The additive form, Eq. (4), with weight constants is more linearly proportional and stable to unexpected changes.

The additive form of the fill priorities is

The direct combination of C(p) and D(p) is unreasonable because of the significant difference in their values. The priority values are dominated by confidence values as compared to values. As the algorithm propagates, the rate of C(p) significantly decreases (Figure 3). Therefore, it is regularized and weighted:

Figure 3

(A) Average Decrease of C_p. (B) Data Term D_p. (C) Priorities. (D) More Linear and Regularized RC_p Over Iterations.

where ω is a regularizing factor.

Additional weights can be incorporated to control the contribution of C(p) and D(p) in priorities P(p) for various types of images:

with α + β=1, where α=0.7 and β=0.3.

It is also obvious that the best matching patch will be found mostly near the target patch. Thus, we bound the search area to improve the performance of the algorithm either by n×m pixels around ψ_p or by the empirical equation

where P_w is the patch width, I_w is the image width, p_x and p_y are the pixel coordinates, D_x and D_y are the extra search margins, and W_c and W_r are the target region dimensions.

We searched the best matching patch ψ_q∈φ of ψ_p in the bounded area by computing the sum squared error (SSE). It is possible that there are multiple best matching patches ψ_q∈φ with the same SSE. To resolve such conflict, we computed the variance wrt mean of ψ_p∈φ as

where p defines the size of the set.

2.2 Algorithm of Patch-Based Inpainting

The pictorial representation of the algorithm is shown in Figure 4.

Figure 4

Structure Propagation by Patch-Based Synthesis.

(A) Original Image I, with Ω as Region to Fill (Target Region), ∂Ω as the Target Region Boundary (Fill Front), and φ=I–Ω as Source Region. (B) ψ_p is the Patch to be Filled, Centered at p∈∂Ω. (C) The Probable Match of ψ_p is on the Isophote, e.g., ψ_q′ and ψ_q″. (d) Unfilled Portion of ψ_p∈Ω is Filled from the Corresponding Best Matching Patch Part

Algorithm:

• Extract the manually selected initial fill front ∂Ω.

• Repeat until done:

  1. Identify the fill front ∂Ω^t. If Ω^t=0, exit.

  2. Compute priorities using Eq. (6).

  3. Find the patch ψ_p∈∂Ω with the maximum priority.

  4. Search φ for the patch ψ_q that minimizes the error.

  5. Copy the image data from the source patch ψ_q∈φ corresponding to ψ_p∈φ.

  6. Update the confidence term, Eq. (5).

t indicates the iteration number.

3 Implementation Details

4 Results

The results of the algorithm of Criminisi et al. [8] were compared with our patch-based inpainting algorithm. Figure 5 indicates the effectiveness of the proposed algorithm for large object removal. Here an algorithm is applied to a variety of color images (Figure 6), which include complex structures and textures. The patch size is set to be greater than the largest texture element or the thickest structure (e.g., edges) in the source region.

Figure 5

Large-Object Removal.

(A, C) Original Photographs. (B, D) The Region Corresponding to the Foreground Person (Approximately 7 and 22%, Respectively, of the Image) has been Manually Selected and then Automatically Removed. Notice that the Background Structures and Texture have been Synthesized.

Figure 6

(A) Original Image. (B) Result of Algorithm [8]. (C) Our Algorithm Result.

Additional experimental results with synthetic images and photographs are shown in Figures 7–16. In all the results, (a) is the degraded image, (b) is the mask image, and (c) is the result of our inpainting algorithm. For Figures 7–9, the patch size is set to 9×9; for Figures 10 and 11, a patch size of 7×7 suffices. Figure 12 shows the distributed fill area. Figure 13 indicates that the corner artifacts result from two isophote joints hidden under the target region. Figures 14 and 15 show large object removal and reconstruction of a relative smooth background. Figure 16 shows the efficacy of our algorithm in curved edge reconstruction. The statistical comparisons of a few representative results in terms of root mean square error (RMSE) and peak signal-to-noise ratio (PSNR) are given in Table 1.

Figure 7

Nice1: Patch Size 9×9.

Figure 8

Nice2: Patch Size 9×9.

Figure 9

Results with Larger Degradation (Nice3): Patch Size 9×9.

Figure 10

Results with Scratch on Edges (Nice4): Patch Size 7×7.

Figure 11

The Child Image Reconstruction: Patch Size 7×7.

Figure 12

Image Repairing Example (Lenna): Patch Size 9×9.

Figure 13

Corner Reconstruction.

Figure 14

Large Object Removal in Photograph: Patch Size 9×9.

Figure 15

Removing an Object on a Highly Textured Background: Patch Size 9×9.

Figure 16

Curved Structure Reconstruction: Patch Size 9×9.

Figure 17 shows the sample frames of a damaged ancient Ajanta painting generated through the iterations of the algorithms for four images. The results in Figure 17E are encouraging.

Figure 17

(A) The Original (B–D) are Intermediate Images. (E) The Inpainted Image by our Algorithm.

It should be noted that the time required for a 7×7 patch size is higher compared with that of a 9×9 patch size.

5 Conclusions

This article has presented a modified method for removing large objects from digital photographs. The result is an image in which the selected object has been replaced by a visually reasonable background. This approach uses a patch-based texture synthesis technique modulated by a scheme for determining the fill order of the target region. Pixels maintain a confidence value that, together with image isophotes, influences their fill priority. The technique is capable of propagating both a linear structure and a two-dimensional texture into the target region with a single, simple algorithm. The present studies also indicate that a simple selection of the fill order is necessary and sufficient to handle this task.

This method performs well for large object removal as well as restoration of small scratches. In instances in which larger objects are removed, this method dramatically outperforms earlier works in terms of both perceptual quality and computational efficiency.