Efficient Object Removal and Region Filling Image Refurbishing Approach

Abstract

Inpainting is a technique to restore damaged portions in images such that it is imperceivable to the naked eye. The challenge is to fill the damaged regions of images such that it looks more discernible and visually plausible while restoring the unity of the picture. Inpainting has various applications such as restoration of damaged photographic images, paintings and removal of particular objects from photographs and images. In this paper, a novel inpainting approach has been introduced that removes objects from images in an indistinguishable manner. Although the exemplar-based traditional object removal approach has certain plus points such as ability to preserve textural, structural details of an image and also preserves lucidity in images, it does not preserve the visual quality of inpainted images. This paper proposes a robust “image refurbishing” algorithm for both synthetic and real unshaded textured images wherein the local information from synthesized patch is used to reconstruct the target area in the image in pixel-by-pixel manner, thus propagating structural as well as textural information simultaneously using a single efficient algorithm. Furthermore, the state-of-art inpainting methods available till date use air-brush masking method; however, in the proposed approach, masking is automatically done which helps in reducing the inpainting time. The inpainted images obtained using the proposed approach are visually appealing which depict the efficiency of the proposed method in removing desired large objects from photographs and other images. The experimental results of the proposed method compare favorably to the state-of-the-art object removal approaches, showing supremacy of the proposed technique over others in terms of computational efficiency, visual quality of inpainted images and inpainting time.

1 Introduction

Inpainting is the term borrowed from medieval art where the restoration artists are tasked to bring the old photographs and damaged paintings close to the original state by filling in the missing gaps in order to make the destroyed artwork plausible while restoring its uniqueness. Image inpainting is a new and active research area [1] during the present decade, and its objective is to revert deterioration (scratches and cracks in photographs) and to remove undesired writings and objects from the image [2]. The inpainting problem first appeared in telecommunication sector where it was required to fill the image blocks lost during the transmission.

Digital image inpainting refers to the technique that is used to reconstruct corrupted and missing portions in an image utilizing information from neighboring areas of that particular image in such a way that the alterations made in restored workpiece are apparently valid [3]. The purpose of inpainting is enhancing the overall quality of the image by reverting deterioration to make it more legible while conserving the unity of the image. In recent years, an important part of artistic and scientific work is stored in the form of image and film archive. Thus, digital image inpainting has become a hotspot in digital photography and film industry. Image inpainting has numerous applications such as photo and film restoration, disocclusion, text removal, special effects in movies, red eye removal. Digital image inpainting is actually a linear transformation [4, 5]. A large number of inpainting algorithms continuously come forth due to extensive technology advancements and research in this field and the goal of all is to enhance the quality of image. The general steps that determine the underlying methodology (Fig. 1) [6] of any inpainting algorithm are:

Fig. 1

Entire image I, the target area Ω to be restored and its contour $\partial \Omega$

• 1. The figure determines the way in which the target region is to be filled, the purpose being to conserve the unity of the image. Thus, the first step is to identify/mask the target region $(\Omega )$ to be inpainted.

• 2. Structure of hole ($\partial \Omega$) is extended into the gap.

• 3. The target region/gap is then filled with pixels (x, y) ϵ Ω that match with those at the inpainting domain ($\partial \Omega$) boundary.

• 4. Minute details are then inpainted, or in other gates, the texture is added.

In order to retain the image data and conserve the unity of the picture, various techniques of inpainting have been proposed by researchers. Generally, digital inpainting approaches can be categorized into two main classes—diffusion method and exemplar method.

The most basic diffusion techniques are pixel interpolation-based [7,8,9,10]. Bertalmio et al. [11] was the first to present the digital inpainting approach that has been inspired from the partial differential (PD) heat flow equations. The partial differential equation-based approach is modeled to reconstruct the corrupted areas by diffusal of information from the known image area into the target area along direction of the isophote [12]. The main problem of this method is that it cannot restore textured images where it gives blurry result.

Another class of inpainting methods is the exemplar-based technique. Each state-of-the-art exemplar algorithm is based on the technique of synthesizing a texture sample using the information from neighboring region. Criminisi et al. [13] presented a patch-based exemplar approach that works on standard texture images where the accurate match texels from the original source region are recognized and copied directly into the missing region. Exemplar-based method combines features of both diffusion methods and texture synthesis [14] to determine the fill-in process. On comparing with the PDE method, exemplar-based method gives better results for large missing regions, but the overall cost of exemplar-based method is huge because of its iterative nature. Moreover, in most of exemplar-based methods, accurate results cannot be achieved because large missing area is filled with small synthesized artificial patches producing observable artifacts [15]. Zhang et al. [16] presented an inpainting method for filling in missing regions using the superpixel segmentation approach and considering a minimal user input. Ding et al. [17] proposed an algorithm for inpainting images using geometric structures and texture having large missing regions. The method reproduces the textural information using a nonlocal Gaussian texture measure and also uses trimmed mean filter for enhancing pixel intensity so as to achieve inpainted images. In [18], the authors have proposed a pixel-based algorithm for removal of objects from the images, and algorithm repairs the affected region by using the similar contour pixels that are around the affected areas.

In this paper, we introduce a new and efficient pixel-based “image refurbishing” approach for removal of bigger objects from images. This method utilizes local pixel information from the synthesized sample texture for reconstructing the lost data in the target region, propagating both structural and textural information simultaneously, thereby providing improved visual quality. Unlike all inpainting algorithms, our algorithm masks the target region automatically which adds to the efficacy of our algorithm. Compared to the exemplar-based algorithms, our algorithm gives plausible inpainting results.

Paper Outline: Section 2 presents the idea of traditional exemplar-based inpainting approach. Section 3 of this paper presents the proposed refurbishing algorithm for object removal. The experimental results of the proposed algorithm and traditional exemplar technique are compared in Section 4 of this paper. Section 5 discusses the conclusion and future scope of the work.

2 Exemplar Inpainting Approach

The idea behind the exemplar inpainting technique refers to the use of texels or image blocks extracted from either the source region in same image or from another image belonging to a set of representative images. The aim is to fill the hole with best candidate patch from the same image source region [6, 19]. One of the most important algorithms that is given as a reference while discussing exemplar inpainting approach is the one put forward by Criminisi et al. [13]. This algorithm focuses on removal of large objects from the image while filling in hole that is left behind with the information from the neighboring area. The very essence of exemplar-based inpainting method is extending the linear structure of the image and finding the patches from the complementary area of the hole which contains the desired information that needs to be filled in the gap. A description of the underlying concept of exemplar inpainting method is presented here for better understanding.

Figure 2 depicts the procedure of exemplar-based inpainting approach [20, 21]. Let us denote the input image as I, target area and its boundary by $\Omega$ and $\partial \Omega = I - \Omega$, respectively, $\Phi = I - \Omega$ is known area, $\Psi_{{\text{p}}}$ denotes the target patch, and the source patch/candidate patch is denoted by $\Psi q$. This method starts the inpainting process by filling the missing regions first near the boundary of the target area ($\Omega$) using texels blocks from the source area $(\Phi )$[22]. The priority value $P(p)$ for all the boundary points is computed, and the patch centered at the point ($p$) of the boundary ($\partial \Omega$) having maximum priority is filled first. The priority of patch is computed as multiplication of data term $D(p)$ and confidence term $C(p)$. The confidence term $C(p)$ gives the count of pixels known in target texel, and data term $D(p)$ is a function that determines isophote at point $(p)$ [23, 24].

Fig. 2

Texture synthesis using exemplar-based method a image with ϕ as source area, Ω as target and $\partial$Ω as boundary. b restoration region delimited by the ψ_p patch having center at p. c $\left( {\Psi_{{\text{q}}}^{\prime } ,\Psi_{{\text{q}}}^{\prime \prime } } \right)$ as candidate patches in the source area. d best-match candidate patch extended to the area delimited by patch ψ_p, getting l fill-in of Ω partially

Thus,

$$ P(p) = C(p) \cdot D(p) $$

(1)

Here, $C(p)$ is the confidence term defined as:

$$ C(p) = \frac{{\sum\nolimits_{q \in \Psi p \cap \Phi } {C(q)} }}{{\left| {\Psi_{{\text{p}}} } \right|}} $$

(2)

here, $\left| {\Psi_{{\text{p}}} } \right|$ is the size of patch $\Psi_{{\text{p}}}$. And $D(p)$ is the data term given as:

$$ D(p) = \frac{{\left| {\mathop \nabla \nolimits^{ \bot } \mathop I\nolimits_{np} .\overrightarrow {np} } \right|}}{\alpha } $$

(3)

here, $\alpha$ is the factor of normalization (for gray-level image, $\alpha$ = 255), $\overrightarrow {np}$ is the orthogonal unit vector to the contour ($\partial \Omega$) at point p, and $\nabla^{ \bot } I_{np}$ is isophote which is located at point p. Taking initial value of $C(p) = 0$;$\forall P\varepsilon_{{}} \Omega$ and $C(p) = 1;$$\forall P\varepsilon_{{}} \Phi ,$ the below given steps are iterated till all the target region ($\Omega$) is fully filled [13]:

• 1. Identify the region to be filled $\partial \Omega$ from target region $(\Omega )$.

  • 2. Compute the priorities of patches for all patches centered at the boundary of $\Omega$.

  • 3. Select $\Psi_{{\text{p}}}$ patch with highest patch priority $P(p)$.

  • 4. Within the source $\Phi$, the best-match $\Psi_{{\text{p}}}$ patch selected that has the least sum-of-squared difference (SSD) with the $\Psi_{{\text{p}}}$ patch with center at $p$$\forall p\varepsilon (\Psi p \cap \Phi )$.

  • 5. Fill the region $(\Omega )$ in target area patch with the pixel data from the best candidate patch $\Psi_{{\text{q}}}$, $\forall q\varepsilon \Phi$.

  • 6. Update the pixel confidence term at point $p$ in unknown/target patch $\Psi_{{\text{p}}}$.

3 Proposed Image Refurbishing Algorithm

The main issue with traditional exemplar inpainting approach is that mostly, the target patch has not sufficient required source pixels due to which they do not completely make use of content redundancy [25] in image for a meaningful representation. This thing in turn has adverse effects on the final result leading to blurring in some portions of the target region. Image refurbishing, a more robust but easy method to select the target patch in such a way that it contains enough of pixels from the known region to produce qualitative results, is introduced in this paper. Moreover, our algorithm uses automatic masking unlike other exemplar-based approaches that use manual masking using some airbrush software. Our concept is to synthesize a bigger target patch and use that information in a pixel-by-pixel manner on the target region which has proved effective for removing large objects from unshaded textured images. We now proceed with the illustration of our algorithm as follows.

3.1 Masking

Masking of the target region is the foremost step in any inpainting technique. All the inpainting techniques till date use manual masking using some airbrush softwares [26] like Photoshop which of course is very time consuming. So, in order to overcome this cumbersome masking method, we have introduced an efficient, automatic yet easy masking method. First of all, the user points out the target region $\Omega$ that is to be removed by making freehand boundary $\partial \Omega$ around the target region $\Omega$. Once the marking is done, our algorithm automatically masks the marked region. After that, we perform calculations on the masked image in order to get the coordinates of the bounding box around the mask. Knowing the coordinates, we crop that portion from the image and store its dimensions for use in patch synthesis.

3.2 Color-Pixel Refurbishing

Once the masking is complete, we utilize the dimensions of the cropped masked region in order to synthesize a patch of similar dimensions from the source area ($\Phi$) that is defined as whole image $I$ subtracted the target area, $(\Omega )$ i.e., $\Phi = I - \Omega$. Thus, the bigger best-matching patch $\Psi_{Bq}$ from source area $(\Phi )$ is selected, and pixel information $P_{\Phi i}$ from this patch $\Psi_{Bq}$ is propagated into the target region $\Omega$ till all pixels $(P_{\Omega } )$ in target area $(\Omega )$ are completely filled in.

As illustrated in Figs. 3 and 4, the target area ($\Omega$) is filled with information $P_{\Phi i}$ from the source region $(\Phi )$ in an efficient manner. For clear understanding, the masked values $(P_{\Omega } )$ in the target area $(\Omega )$ were filled with most appropriate values of pixels $(P_{\Phi 6} ,P_{\Phi 7} ,P_{\Phi 10} ,P_{\Phi 11} )$ from the source region $(\Phi )$. The color-pixel refurbishing process is governed by the following mathematical equation:

$$ \begin{aligned} & \sum\limits_{i = x1}^{x2} {\sum\limits_{j = y1}^{y2} {\sum\limits_{k = 1}^{3} {{\text{Im}} (i,j,k) = P_{\Phi } } } } \\ & \forall {\text{Im}} (i,j,k)\varepsilon \Omega \quad {\text{and}}\quad P_{\Phi } \varepsilon \Phi \\ \end{aligned} $$

(4)

Fig. 3

Structure and texture propagation by image refurbishing algorithm

Fig. 4

Image refurbishing a synthesized source patch $\Psi_{Bq}$. b Masked target region Ω. c Inpainted/restored target area

where $P_{\Phi }$ is the value of pixel outside masked area from source patch $\Psi_{Bq}$. The changes made in the inpainted region thus seem undetectable to the casual observer resulting in visually plausible outputs that look reasonable to the human eye. Formulating, a precise reckoning approach for depicting the success of our algorithm is an important yet useful task. To evaluate accurately, both the qualitative and quantitative approaches are used. The qualitative assessment of the results is done by human visual analysis (HVM), and the quantitative evaluation is done by analyzing and calculating mean square error (MSE) and peak signal-to-noise ratio (PSNR) of images. These correlation methods are mathematically expressed as:

$$ {\text{MSE}} = (1/mn)\sum\limits_{i = 0}^{m - 1} {\sum\limits_{j = 0}^{n - 1} {\left\| {I(i,j) - U(i,j)} \right\|^{2} } } $$

(5)

Here, $I$ is reference image and $U$ denotes its inpainted version, $i$ and $j$ are the coordinates of the pixels and m and n represent the number of rows and columns of original image, respectively. Lesser the MSE, the better is quality of inpainted image. PSNR gives ratio of maximum signal power noise power that corrupts signal. The PSNR values are usually represented in dB (decibels). Greater the value of the PSNR, better is quality of inpainted image. PSNR is mathematically expressed as:

$$ {\text{Peak}}\,{\text{SNR}} = 10\log_{10} \left( {\frac{{(2^{n} - 1)^{2} }}{{{\text{MSE}}}}} \right) $$

(6)

where $n$ is the number of bits.

Values of PSNR and MSE obtained from our algorithm are compared with the values obtained from traditional exemplar-based approach showing that our technique gives both qualitatively and quantitatively much better results than those obtained by exemplar-based algorithm.

4 Experimental Results and Discussion

For evaluating the performance of proposed approach, the experiments were conducted on MATLAB 13 b, and the results obtained were compared with traditional exemplar approach results. A set of 20 images has been utilized as test images so as to analyze performance efficiency of proposed approach. The quantitative analysis and evaluation of the proposed and traditional methods is done using peak signal-to-noise ratio (PSNR) and MSE. The result summary of MSE and peak SNR values is given in Table 1. The proposed “image refurbishing” approach shows improved MSE and peak SNR results than those obtained from traditional exemplar methods for all test images.

Table 1 Comparison of MSE and peak SNR of traditional exemplar method and proposed image refurbishing

We tested our proposed technique on high-resolution football field image as depicted in Fig. 5a. Masked target area (the football) is shown in Fig. 5b. In the result obtained from exemplar method shown in Fig. 5c, the inpainted/restored grasses show blocky effect and some blur. However, our method overcomes this blocky effect and provides better visual quality without image blur as depicted in Fig. 5d.

Fig. 5

Inpainting football field image

A comparison of exemplar method (E) and the proposed “image refurbishing” method (P) is given in Table 1. Also, performance evaluation graphs with the comparison of peak SNR and MSE values for three different images are depicted in Fig. 6a, b, respectively. It shows that proposed approach has improved not only the quality of inpainted image but also the inpainting efficiency.

Fig. 6

Comparison of peak SNR and MSE using three different images

5 Conclusion

In this paper, a new and efficient “image refurbishing” approach has been presented for removing larger objects from images. The proposed approach marks target area using automatic masking unlike traditional inpainting methods, wherein masking is done manually, thereby reducing time required for inpainting an image. In our method, information from a synthesized sample patch from the same image is propagated into the target area in a pixel-by-pixel manner until all unknown pixels in target area are completely filled. The proposed method propagates both structure and texture in target area with single potent scheme. Automatic masking of the proposed method not only reduces the inpainting time manifold but also uses pixel information from a bigger patch. The proposed approach significantly outperforms work done in traditional methods both by increasing computational efficiency and visual quality at the same time. The results obtained depict superiority of the proposed algorithm over traditional exemplar approach, since its peak SNR value is high and MSE has low value. However, it is applicable to unshaded textured images and quality is reduced with complicated/irregular textures. The future work will concentrate on investigating extensions to modify the current algorithm further for processing complex textures in photographs as well as for removing objects from videos.