Research of image inpainting algorithm based on image segmentation

Abstract

Image inpainting is an effective method to repair damaged image. In this paper, we mainly studied some typical image inpainting models and analyzed these corresponding repair qualities. Firstly, we studied three typical algorithms based on PDE (Partial Differential Equation) model to repair images whose damaged areas are relative small. And then we studied the image inpainting algorithm based on texture synthesis. This kind of inpainting algorithm is suitable for image with large damaged area. Finally, we studied Criminisi inpainting algorithm based on image segmentation in detail, on which we proposed an improved priority formula image repair algorithm, the simulation results indicate that the improved algorithm of this paper showed better performance in repair quality from both subjective and objective aspects.

Keywords

Image segmentation image inpainting texture synthesis criminisi algorithm

1. Introduction

Image quality would be inevitably affected by environmental factor, some information or area would be lost in the procedure of shooting and processing [1], so image inpainting is an important research field, it is one way to reconstruct images’ damaged area or it is an effective method to remove the noise and targets in images. Nowadays, image inpainting has been used widely in object removal [2], damaged painting reconstruction, image compression and coding [3], error concealment [4]. According to the definition of image inpainting, an image can be divided into two parts, one part is the undamaged area, which is also called the known region of the image; the other is the damaged area and it is the inpainting area of the image [5]. The processing of image inpainting is to fill the missing information with the full pixel information in the image. At present, the methods of image inpainting are mainly divided into three categories: diffusion-based inpainting [6], exemplar-based inpainting [7] and hybrid inpainting [8]. Usually, the image inpainting algorithm could be evaluated from two aspects. The first is to evaluate the effectiveness by human eye, that is subjective evaluation, and the second is objective evaluation criteria to evaluate the efficiency of the algorithm, which mainly including Peak Signal to Noise Ratio (PSNR) [9].

There are some classical image inpainting algorithms based on PDE (Partial Differential Equation) models [10]. For example BSCB algorithm [11] (Bertalmio, Sapiro, Caselles, Ballester) applying numerical iteration to solve the transmission equation and adding a variety of anisotropic diffusion equation to avoid the intersection of multiple isophotes in the area to be repaired, which could extend the edge of the restoration area to the inner restoration area according to the original angle. Total variation (TV) repair model [12] can overcome the disadvantage that the linear filter would smooth the edge of the image when it is used to suppress the noise. While Curvature-Drive Diffusion (CDD) model [13] is an improved algorithm for TV models, which aims to solve the problem of visual discontinuity in TV model. As for the repair results, TV has the fastest repair speed and CDD is the slowest. However, CDD has the highest PSNR value and TV algorithm is the smallest one. The aforementioned three models are suitable for images with obvious structure information and small damaged areas. While Criminisi algorithm [14] combines the advantages of structure and texture based image restoration methods, and it can complete texture synthesis and structural repair at the same time, which is suitable for images with obvious texture information and large damaged areas. However, the image inpainting quality still needs to be improved.

The rest of this paper is organized as follows. Section 2 presents fundamental principle of Criminisi algorithm. In Section 3, we propose an improved priority formula for Criminisi algorithm. Section 4 introduces the simulation results from both subjective and objective aspects in detail, and Section 5 gives the conclusions of this paper.

2. Fundamental principle of Criminisi algorithm

The main idea of the Criminisi algorithm [14] is to determine the priority of the repair block by using the restoration priority method based on the isophotes; Secondly, according to a certain search strategy, the best matching block is sought for the inpainting block with the highest priority in the undamaged area [15]. Thirdly, the pixel information in the best matching block is filled in the area to be repaired. Finally, repeat the above procedures until the entire damaged area is filled in. The schematic diagram is shown in Fig. 1.

Figure 1.

Schematic diagram of criminisi algorithm.

As shown in Fig. 1, $I$ represents the whole image, $\Omega$ is the area of the repair area, $\partial\Omega$ indicates the edge of the repair area; $\Phi$ is the undamaged area of the image, which is the known part of the image. The specific algorithm steps are as follows:

Step 1: Calculating the highest priority pixel block in the area to be repaired. Select a point $p\in\partial\Omega$ on the edge, block’s priority $P(p)$ is defined as follow:

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

In Eq. (1), $C(p)$ is the confidence item and $D(p)$ is the data item [16], which is defined as follows:

$\displaystyle C(p)=\frac{\sum\limits_{q\in\Psi_{p}\cap\Phi}C(q)}{|\Psi_{p}|}$ (2)

$\displaystyle D(p)=\frac{\nabla I^{\bot}_{p}\cdot n_{p}}{\beta}$ (3)

Where $\Psi_{p}\in\Omega$ is a square template, $|\Psi_{p}|$ represents the area of $\Psi_{p}$ ; $\beta$ means normalized factor, for a typical grayscale image, $\beta=255$ ; $n_{p}$ is the normal vector of point $p$ , and $p$ is on the edge $\partial\Omega$ of the region to be repaired. In addition, $\nabla I^{\bot}_{p}$ is the isophote of point $p$ , which is perpendicular to the point $p$ gradient, and it can be defined as follow:

$\displaystyle\nabla I^{\bot}_{p}={\displaystyle\frac{(-I_{y}(p),I_{x}(p))}{% \sqrt{I_{x}(p)^{2}+I_{y}(p)^{2}}}}$ (4)

In Eq. (4), $I_{x}$ represents the partial differential of the pixel point $p$ in the $x$ direction, and $I_{y}$ represents the partial differential of the pixel point $p$ in the $y$ direction.

Step 2: Searching the best matching pixel block for the target block in the area with known information, and their corresponding pixels are used to fill in the repair area. Searching the best matching block $\Psi_{q}$ according to the texture matching SSD standard, and then filling in the whole $\Psi_{p}$ area, this could be defined as:

$\displaystyle\textit{SSD}(\Psi_{p},\Psi_{q})=\sum(p-q)^{2},\forall p\in\Psi_{p% },q\in\Psi_{q},\Psi_{q}\in\Phi$ (5)

Step 3: After the filling is finished, we need to update the confidence level $C(p)$ of the image. When the highest priority pixel block $\Psi_{p}$ is filled in, the confidence level $C(p)$ of the restored pointwill be updated, and it is the new confidence level of the center pointof the new block that needs to be repaired:

$\displaystyle C(p)=C(\hat{p}),\forall\hat{p}\in(\Psi_{p}\cap\Omega)$ (6)

Step 4: Repeating the above steps until the entire damaged area is repaired.

3. The improved Criminisi algorithm

Criminisi algorithm’s priority is calculated in an unreasonable manner, it is easy to cause inaccuracy of the inpainting order [17]. Therefore, in this paper, we propose an improved calculation algorithm of the priority on the basis of the Criminisi algorithm.

To describe the question easier, we repeat the calculating formula of the priority in the Criminisi algorithm:

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

By analyzing the image reconstruction principle of Criminisi algorithm, we can see that there is a close relationship between the final repaired image and the sequence of the inpainting points for the quality. With the progress of image reconstruction, the damaged area becomes smaller. When calculating the priority, the value of the data item $D(p)$ will decrease and gradually become zero, which will lead to error in calculating the priority, and it will directly affect the quality of the final repaired image. So we need to improve the pixel priority’s calculation method.

In this paper, based on the multiplication of the confidence level term and the data term of the Criminisi algorithm, the data item and confidence level in the priority are transformed into the form of weighted sums, and factoris introduced for $C(p)$ , the proposed improved formula for the priority is:

$\displaystyle P(p)=C(p)D(p)+C(p)^{\alpha},\alpha\in\text{R}^{+}$ (8)

Figure 2.

Image inpainting result of ‘Chunhua’.

Figure 3.

The influence of $\alpha$ value on the effect of image reconstruction.

By bringing in factor, the proportion of the data item $D(p)$ in the priority calculation formula will increase, and $P(p)$ will not reduce to zero as discussed in the above section, so that the influence of the confidence level $C(p)$ on the priority $P(p)$ will reduce, and the importance of the data item will increase, thereby it is probably to improve the accuracy of the inpainting effect of the texture part of the image.

4. Simulation results and analysis

Figure 2 shows the results of the reconstruction of the damaged image ‘Chunhua’. Figure 3 shows the results of the proposed algorithm with $\alpha=0.1$ , 0.9, 6, and 17, respectively. It can be seen from the observation that when $\alpha$ increases from 0.1 to 0.9, the inpainting effect will become better, from Table 1, we also know that when $\alpha$ increase from 1 to 20, the inpainting effect become worse, and when $\alpha$ is equal to 0.9, the inpainting effect is the best.

Table 1 gives the corresponding PSNR value when factor $\alpha$ takes different values.

Table 1
The influence of different factor $\alpha$ on PSNR value

$\alpha$	0.1	0.3	0.5	0.7	0.9	1.2	6	20
PSNR(dB)	33.8944	34.0600	34.5855	34.8843	34.8894	34.3988	32.1604	27.1555

Table 2

The Comparison of PSNR values for different inpainting algorithm (dB)

Test images	Criminisi algorithm [14]	Ref.[17] algorithm	The proposed algorithm
Hua	29.4824	29.7543	30.2969
Chunhua	27.1555	33.5737	34.8894
Barb	34.1397	39.0400	39.2865
Lena	31.5520	33.1189	33.2393

Figure 4.

Image inpainting results of ‘Hua’.

Figure 5.

Image inpainting results of ‘Barb’.

In order to further verify the superiority and effectiveness of the proposed algorithm, we used Criminisi algorithm [14], Ref.[17] algorithm and the proposed algorithm in this paper to repair three kinds damaged images of ‘Hua’, ‘Barb’ and ‘Lena’. We made some comparison of the inpainting results from both objective and subjective aspects. The inpainting effect on the three broken images of ‘Hua’, ‘Barb’ and ‘Lena’ were shown in Figs 4–6, respectively. By comparing the repaired parts of the damaged image, we found that the proposed algorithm in this paper could repair the edges of the three damaged images well. Meanwhile, the left arm portion of the damaged image of ‘Barb’ and the hat portion of ‘Lena’, which showed that the inpainting effect of the proposed algorithm is better than that of Criminisi algorithm [14] and the algorithm in Ref.[17] (in this section, factor $\alpha=$ 0.9).

Figure 6.

Image inpainting results of ‘Lena’.

From objective aspect, we compared several algorithms’ PSNR. The comparison results were showed in Table 2, the proposed algorithm showed at least 0.8 dB higher than Criminisi algorithm [14], and 0.1 $\sim$ 1.3 dB higher than algorithm in Ref.[17], which obviously indicated the inpainting effectiveness of the proposed algorithm in this paper.

In a word, through the subjective effects of the inpainting results shown in Figs 4–6 and the objective PSNR indicated in Table 2, compared with the Criminisi algorithm [14] and the algorithm in Ref.[17], we can see that the improved algorithm proposed in this paper shows better image inpainting effectiveness.

5. Conclusions

Several image inpainting algorithms based on image segmentation are discussed in this paper. We compared their performance and summarized their advantages and disadvantages. This paper focuses on the sample-based inpainting algorithm proposed by Criminisi, we propose an improved formula of the priority calculation, add $C(P)$ to the multiplication operation, and improve the importance of the data item $D(p)$ by introducing the factor $\alpha$ , which can reduce the error matching of sample blocks and improve the inpainting effect of the image’s texture details.

Footnotes

Acknowledgments

This work has been supported in part by Hunan Provincial Natural Science Foundation of China (2017JJ3099, 2016JJ2064), the National Science Foundation of China (51704115, 61772195), the Science and Technology Program of Hunan Province (2016TP1021), the Open Fund of Education Department of Hunan Province (15K051), and the Fund of Education Department of Hunan Province (16C0723).

References

M.N.

and Vetterli

, The contourlet transform: an efficient directional multiresolution image representation, IEEE Transactions on Image Processing 14(12) (2005), 2091–2106.

and Ma

, An effective method for removing large object, IEEE International Congress on Image and Signal Processing, (2011), 80–84.

Xiong

and Sun

, Block-Based Image Compression With Parameter-Assistant Inpainting, IEEE Transactions on Image Processing 19(6) (2010), 1651–1657.

Ebdelli

and Le

M.O.

, Video inpainting with short-term windows: application to object removal and error concealment, IEEE Transactions on Image Processing 24(10) (2015), 3034–3047.

Kondekar

A.A.

and Zope

P.H.

, Image Inpainting, International Journal of Engineering Research & Applications 4(9) (2014), 157–166.

Biradar

R.L.

and Kohir

V.V.

, A novel image inpainting technique based on median diffusion, Sadhana 38(4) (2013),621–644.

Buyssens

and Daisy

, Exemplar-based inpainting: technical review and new heuristics for better geometric reconstructions, IEEE Transactions on Image Processing 24(6) (2015), 1809–1824.

Bertalmio

and Vese

, Simultaneous structure and texture image inpainting, IEEE Transactions on Image Processing 12(8) (2003), 882–889.

Yang

X.H.

and Guo

B.L.

, Image inpainting algorithm based on weighted fractal under the structure-measurement constraint, Journal of XIDIAN Universit 39(6) (2012), 84–91.

10.

Alvarez

and Mazorra

, Signal and Image Restoration Using Shock Filters and Anisotropic Diffusion, Siam Journal on Numerical Analysis 31(2) (1994), 590–605.

11.

Ballester

and Bertalmio

, Filling-in by joint interpolation of vector fields and gray levels, IEEE Transactions on Image Processing 10(8) (2001),1200–1211.

12.

Rudin

L.I.

Osher

and Fatemi

, Nonlinear total variation based noise removal algorithms, Eleventh International Conference of the Center for Nonlinear Studies on Experimental Mathematics: Computational Issues in Nonlinear Science: Computational Issues in Nonlinear Science. Elsevier North-Holland, Inc. (1992), 259–268.

13.

Chan

, Non-texture inpainting by curvature driven diffusion, J. Visual Comm.image Rep 12 (2001),436–449.

14.

Criminisi

Prez

and Toyama

, Object Removal by Exemplar-Based Inpainting, IEEE Computer Society Conference on Computer Vision & Pattern Recognition. IEEE Computer Society (2003), 721.

15.

A.J.

and Niu

W.L.

, Image inpainting based on improved Criminisi algorithm, Computer Engineering and Application 50(18) (2014), 167–170.

16.

Hassan

E.T.

and Abbas

H.M.

, Image inpainting based on image segmentation and segment classification, IEEE International Conference on Control System, Computing and Engineering, (2014), 28–33.

17.

Han

M.Z.