The Korean Society of Marine Engineering

[ Brief Communication ]

Journal of Advanced Marine Engineering and Technology - Vol. 46, No. 5, pp.248-251

ISSN: 2234-7925 (Print) 2765-4796 (Online)

Print publication date 31 Oct 2022

Received 18 Aug 2022 Revised 14 Sep 2022 Accepted 26 Sep 2022

DOI: https://doi.org/10.5916/jamet.2022.46.5.248

Adaptive image inpainting algorithm based on POCS and patch stationarity

Si-Woong Lee¹

; Byoung-Ju Yun^†

1Professor, Department of Intelligent Media Engineering, Hanbat National University, Tel: +82-42-821-1146 swlee69@hanbat.ac.kr

Correspondence to: ^†Professor, School of Electronics Engineering, Kyungpook National University, 80, Daehak-ro, Buk-gu, Daegu 41566, Korea, E-mail: bjisyun@ee.knu.ac.kr, Tel: +82-53-950-7329

Copyright ⓒ The Korean Society of Marine Engineering
This is an Open Access article distributed under the terms of the Creative Commons Attribution Non-Commercial License (http://creativecommons.org/licenses/by-nc/3.0), which permits unrestricted non-commercial use, distribution, and reproduction in any medium, provided the original work is properly cited.

Abstract

To remove objects from digital images, certain measures are required to restore the empty and damaged regions in an image. The process of restoring a corrupted image by filling empty regions with background textures is called image inpainting. This study proposes a new algorithm to suppress the generation of texture garbage in the image inpainting process. We analyze the characteristics of the projections onto convex sets (POCS)-based and static patch-based exemplar search techniques and propose an adaptive algorithm that can compensate for the shortcomings of both methods. The experiments showed that the proposed method naturally inpainted empty areas while effectively suppressing the generation of texture garbage.

Keywords:

Image inpainting, Texture garbage, Merge algorithm, Filling empty region, Background texture

1. Introduction

The domain of an input image (Ω) from which certain objects are intentionally removed comprises a filled (or known) region S and an empty (or unknown) region U , that is, Ω = S ∪ U . The purpose of image inpainting is to reconstruct the image by estimating the color of each pixel p in region U using the data from region S as visually natural as possible.

Existing image inpainting techniques can be classified into two approaches. Diffusion-based methods fill an empty area by transferring the linear structure from the surrounding pixel values to the area to be restored through diffusion [1]-[3]. This technique can obtain good results while preserving the linear structure of the image when the area to be reconstructed is narrow. However, when the area to be reconstructed is wide, texture information cannot be preserved and blurring occurs [4]. The method using texture synthesis samples the texture of the surrounding area and uses it to fill the empty region [5]-[10]. This type of inpainting method efficiently preserves the texture of the image but does not efficiently maintain the linear structure in the image [4]. To overcome this, Criminisi et al. [8] proposed an exemplar-based inpainting method. In this technique, the priority function of the inpainting patch is designed for an efficient propagation of the linear structure, and inpainting is performed according to this priority, thereby preserving the linear structure of the image.

The disadvantages of exemplar-based image inpainting include edge jaggedness and texture garbage [4]. Texture garbage is a phenomenon in which an inhomogeneous texture that does not match the background signal is inserted in the inpainted image, thus degrading the overall quality of the resulting image. In this study, we analyze existing algorithms for suppressing such texture garbage and present an adaptive image inpainting algorithm that can effectively combine their advantages.

2. Related works

2.1 Exemplar-Based Texture Synthesis

In the exemplar-based image inpainting proposed by Criminisi et al., the priority is calculated for patch Ψ_p corresponding to certain pixel p at boundary δU, and then patch $ψ p^$ with the highest priority is obtained. Table 1 lists the definitions of these symbols. Subsequently, patch $ψ q^$ , which is most similar to $ψ p^$ (called the source exemplar), is detected in S, and the value of each pixel to be filled in $ψ p^$ is copied from its corresponding pixel inside $ψ q^$ . For more details on this algorithm, please refer to [8].

Table 1:

Definitions of symbols

2.2 Conventional Approaches

Conventional exemplar-based inpainting uses the sum of squared differences (SSD) between $ψ p^S$ and $ψ q S$ , which is the known area of the two patches, as a distance function in a similar patch search process. Therefore, if region $ψ q^U$ of patch $ψ q^$ , which is determined as an exemplar patch, contains a signal that has no correlation with region $ψ q^S$ , this signal is copied to region $ψ p^U$ and appears as texture garbage.

Reference [9] proposed an inpainting method using patch extrapolation to suppress the generation of texture garbage. For the priority-determined patch, the empty area is filled using POCS-based extrapolation, and then similar patches are searched for. However, this method has a disadvantage in that the extrapolation performance degrades as the size of the empty area in the patch increases.

The algorithm presented in [10] is a method for suppressing the occurrence of texture garbage by statistically analyzing the spatial stationary characteristics of patches and considering only those patches that satisfy the stationary condition as candidate patches. The decision criterion for the stationary condition of the candidate patch is as follows:

E Ψ q S - E Ψ q U ≤ β ⋅ S T D Ψ q S,

(1)

where E( $ψ q S$ ) and STD( $ψ q S$ ) are the mean and standard deviation of the brightness values of region $ψ q S$ , respectively. That is, a patch whose average brightness difference between areas $ψ q S$ and $ψ q U$ is equal to or less than a threshold is determined as a stationary patch.

3. Proposed method

As described above, in the POCS-based technique [9], as the size of the region to be filled in the patch increases, the optimal patch search performance deteriorates owing to the degradation of the extrapolation performance. However, the stationary patch-based technique [10] may limit the dynamic characteristics between the filled and empty regions within the candidate patch. In addition, a disadvantage exists in that a large amount of calculation is required because the mean and variance of $ψ q S$ and $ψ q U$ must be calculated at all positions in the search area to calculate the decision expression of Equation (1).

To compensate for the shortcomings of these two techniques, this study proposes an adaptive inpainting algorithm that merges the two algorithms. In the proposed method, the normalization size of the known region in the current target patch is calculated as follows:

γ = Ψ p^S Ψ,

(2)

where |Ψ| is the area of patch Ψ. If γ is close to 1, the size of the empty area is small, and the patch extrapolation performance is excellent. Therefore, the closer γ is to 1, the more reasonable it is to reflect POCS-based inpainting results. Conversely, when γ is small, the extrapolation performance is poor. Therefore, it is preferable to use stationary patch-based inpainting rather than POCS-based inpainting.

In general, the merging structure of two inputs may be implemented in a weighted sum or switching form. Considering the fact that the weighted sum of images can lead to an undesirable blurring effect in the resulting image, the proposed method implements the merge structure by applying the switching method as follows:

Ψ p^U = Ψ q^P U, i f γ ≥ γ t h Ψ q^(S) U, e l s e

(3)

where $ψ q^P$ and $ψ q^S$ denote the best-match patches selected using the POCS-based and stationary patch-based methods, respectively. The proposed method improves the overall inpainting performance by switching between the POCS-based and stationary patch-based methods according to the size of the area to be filled in the current patch, according to Equation (3). Table 2 presents the overall algorithm of the proposed inpainting method, where the improved patch search process is shown in bold.

Table 2:

Proposed inpainting algorithm.

4. Experimental results

In the experiments, after manually removing a specific object from the image, an empty area was inpainted using a mask image of the removed area. To analyze the performance of the proposed method, the method proposed by Criminisi et al. [8], which is a representative exemplar-based inpainting method, was used as the conventional method, and its performance was compared. In the experiment, the size of the patch was set to 9 × 9, β = 1.0, and γ_th = 0.65.

In image inpainting, the signal of the background area covered by an object cannot be known. Therefore, evaluating the performance of inpainting with an objective numerical value is difficult, and the performance is mainly compared through a visual evaluation of whether the filled area appears natural without edge jaggedness or texture garbage.

Figure 1 shows the result of the inpainting after removing certain areas, including the pillars of the road sign. In the reconstructed image of the conventional method, a signal with a texture different from that of the background bush appeared as texture garbage in the area to the right of the reconstructed column. In particular, notably, the solid line in the sign plate was copied to the target area and appeared as texture garbage. However, in the reconstructed image of the proposed method, notably, the column was well reconstructed without interruption, and the reconstructed image was obtained naturally without generating texture garbage.

Figure 1:

Experimental results for a road sign image: (a) original image (b) object-removed image (c) conventional method (d) proposed method

Figure 2 shows the results of the inpainting after removing a ship floating in the sea. In the inpainted image of the conventional method, black and white patterned texture garbage appeared in the restored mountain region. In addition, in the center of the restored sea, notably, a bird that did not originally exist appeared as a copy. This was also texture garbage that was generated when birds were included in the exemplar patch and copied to the target area. However, notably, texture garbage was not generated in the inpainted image of the proposed method.

Figure 2:

Experimental results for a seagull image: (a) original image (b) object-removed image (c) conventional method (d) proposed method

5. Conclusion

An algorithm that can suppress the generation of texture garbage when the source and target regions of the exemplar patch are not uniform, is presented. A structure that efficiently merges the existing POCS-based and stationary patch-based methods is presented. The experiments confirmed that the proposed method can improve the quality of the synthesized image by suppressing the generation of texture garbage.

Author Contributions

Conceptualization, S. W. Lee and B. -J. Yun; Software, S. W. Lee; Validation, S. W. Lee and B. -J. Yun; Formal Analysis, S. W. Lee; Writing—Original Draft Preparation, S. W. Lee; Writing—Review & Editing, B. -J. Yun.

References

T. F. Chan and J. Shen, “Non-texture inpainting by curvature-driven diffusions,” Journal of Visual Communication and Image Representation, vol. 12, no. 4, pp. 436-449, 2001. [https://doi.org/10.1006/jvci.2001.0487]
M. Bertalmio, A. L. Bertozzi, and G. Sapiro, “Navier-strokes, fluid dynamics and image and video inpainting,” Proceedings of Computer Society Conference on Computer Vision and Pattern Recognition, vol. 1, pp. 355-362, 2001.
C. Ballester, V. Caselles, J. Verdera, M. Bertalmio, and G. Sapiro, “A variational model for filling-in gray level and color images,” Proceedings of International Conference on Computer Vision, vol. 1, pp. 10-16, 2001.
C. Guillemot and O. L. Meur, “Image inpainting: Overview and recent advances,” IEEE Signal Processing Magazine, vol. 31, no. 1, pp. 127-144, 2014. [https://doi.org/10.1109/MSP.2013.2273004]
L. Liang, C. Liu, Y. -Q. Xu, B. Guo, and H. -Y. Shum, “Real-time texture synthesis by patch-based sampling,” ACM Transaction on Graphics, vol. 20, no. 3, pp. 127-150, 2001. [https://doi.org/10.1145/501786.501787]
A. A. Efros and T. K. Leung, “Texture synthesis by non-parametric sampling,” Proceedings of International Conference on Computer Vision, vol. 2, pp. 1033-1038, 1999. [https://doi.org/10.1109/ICCV.1999.790383]
M. Ashikhmin, “Synthesizing natural textures,” Proceedings of Symposium on Interactive 3D Graphics, pp. 217-226, 2001. [https://doi.org/10.1145/364338.364405]
A. Criminisi, P. Perez, and K. Toyama, “Region filling and object removal by exemplar-based image inpainting,” IEEE Transactions on Image Processing, vol. 13, no. 9, pp. 1200-1212, 2004. [https://doi.org/10.1109/TIP.2004.833105]
J. -J. Kim and S. -W. Lee, “Effective exemplar-based image inpainting using patch extrapolation,” Journal of Korea Contents Association, vol. 14, no. 2, pp. 1-9, 2014 (in Korean). [https://doi.org/10.5392/JKCA.2014.14.02.001]
Y. I. Kong and S. -W. Lee, “Texture garbage elimination algorithm for exemplar-based image inpainting,” Journal of Broadcasting Engineering, vol. 24, no. 1, 2019 (in Korean).

Figure 1:

Experimental results for a road sign image: (a) original image (b) object-removed image (c) conventional method (d) proposed method

Figure 2:

Experimental results for a seagull image: (a) original image (b) object-removed image (c) conventional method (d) proposed method

Table 1:

Definitions of symbols

Symbol	Definition	Notes
Ψ_P	target patch centered at point p
$ψ p^$	patch with highest priority
$ψ p^S ψ p^U$	filled (empty) region in $ψ p^$	$ψ p^S = ψ p^⋂ S, ψ p^U = ψ p^⋂ U$
Ψ_q	source patch centered at point q
$ψ q^$	best-match patch in source region	exemplar
$ψ q S ψ q U$	region in Ψ_q corresponding to $ψ p^S ψ p^U$

Table 2:

Proposed inpainting algorithm.

∙ Extract the manually selected initial front δU⁰
∙ Repeat until done:
Identify the fill front δU^t . If U^t = ∅, exit.
Compute priorities P(p) ∀p ∈ δU^t.
Find the patch

ψ p^

with the maximum priority.
If γ ≥ γ_th , find the exemplar

ψ q^

∈ S that minimizes
d(

ψ p^’

, ψ_q), where

ψ p^’

= POCS(

ψ p^S

) is the extrapolated patch
from

ψ p^S

using POCS.
Else, find the exemplar

ψ q^

∈ S that satisfies |E(

ψ q S

)-
E(

ψ q U

)| ≤ β ∙ STD(

ψ q S

) and minimizes d(

ψ p^S, ψ q S

).
Copy image data from

ψ q^U

ψ p^U

Update C(p) ∀p ∈

ψ p^U