The research of image inpainting is an important and challenging topic in image processing and computer vision. As is well known to all, it has played a very significant role in the fields of artwork restoration, redundant target removal, image segmentation and video processing.

The objective of image inpainting is to reconstruct the missing or damaged portions of image. For solving this inverse problem, there have emerged numerous models based on the variational, partial differential equation (PDE), wavelet, as well as Bayesian methods. Notice that the terminology of digital inpainting was initially introduced by Bertalmio et al. (2000), who proposed the typical third-order nonlinear PDE inpainting approach. Subsequently, Chan and Shen (2001) developed a novel PDE model based on curvature driven diffusion, and the total variation (TV) model (Chan and Shen, 2002). The authors in Masnou and Morel (1998), Chan et al. (2002) investigated the Euler’s elastica and curvature based variational inpainting models. Moreover, considering inpainting in the transformed domain, the works (Chan et al., 2006, 2009) discussed the TV minimization wavelet domain models for image inpainting. Among these models, one of the remarkable variational solvers based on Rudin et al. (1992) is the TV inpainting model (1) minu{TV(u)+λ2∫Ω∖D(u−f)2dx}, where Ω denotes the complete image domain, D is the missing or damaged region to be inpainted, f and u are the degraded image and the unknown true data respectively, TV(u)=∫Ω|∇u|dx is the total variation function, and λ means a regulable parameter.

As demonstrated in various applications, TV framework (Rudin et al., 1992; Chan and Shen, 2002; Prasath, 2017) can preserve the geometric features well, but the obtained results often suffer from the piecewise constant in smooth regions. To eliminate the unexpected staircase effect, several powerful regularizer techniques, such as the higher-order derivatives (Chan et al., 2000; Lysaker et al., 2003), nonlocal TV (Gilboa and Osher, 2008; Liu and Huang, 2014) and total generalized variation (TGV) (Bredies et al., 2010; Knoll et al., 2011; Liu, 2018, 2019) based schemes have been widely researched with great success. It is noteworthy that the concept of TGV regularizer was originally introduced by Bredies et al. (2010). In practical applications, considering that images can be well approximated by the affine functions, the second-order TGV models are particularly favoured by numerous researchers. Applied to deal with the problem of image inpainting, the TGV regularized model can be written as (2) minu{TGVα2(u)+λ2∫Ω∖D(u−f)2dx}, where the weight α=(α0,α1) , with α0 , α1 being two positive parameters. This technique reduces the blocky artifacts efficiently, but it sometimes causes the edge blurring.

With the aim of maintaining the sharp and neat edges, the studies (Black and Rangarajan, 1996; Roth and Black, 2009) demonstrate that the introduction of nonconvex potential functions is the right choice. Thus, on the basis of TV model, nonconvex TV regularizer methods (Nikolova et al., 2010, 2013; Bauss et al., 2013) have attracted much attention of authors and become a hot research issue. It is worth noting that this solver has the superiority in preserving sharp discontinuities, but it leads to the serious staircase artifacts in smooth regions, even more than the TV based techniques. In view of the foregoing, the preliminary articles stated in Ochs et al. (2013, 2015), Zhang et al. (2017), which provide the combination of TGV regularizer and nonconvex prior, have achieved the reasonable and smooth denoising results with sharp discontinuities.

As for image inpainting, this paper aims to overcome the shortcomings of existing inpainting models, and constructs a novel nonconvex TGV (NTGV) regularization strategy. By intimately combining the advantages of TGV regularizer and edge-preserving nonconvex function, the developed scheme is formulated as the following concise form (3) minu{NTGVα2(u)+λ2∫Ω∖D(u−f)2dx}. It is noteworthy that the concrete formulation will be detailed in the next section.

The main contributions of the current article are listed as follows. First of all, we propose a novel nonconvex regularization model that closely integrates the superiorities of TGV regularizer and nonconvex logarithmic function. The usage of nonconvex penalizers in the TGV seminorm helps to obtain a more realistic image with sharp edges and no staircasing. Secondly, to optimize the resulting nonconvex model, this paper presents in detail a modified primal-dual framework by combining the iteratively reweighted minimization algorithm. All numerical simulations consistently illustrate the superiority of the introduced method for image inpainting over the related efficient solvers, with respect to both visual and measurable comparisons.

Finally, we give a briefly outline of the following sections. Section 2 is devoted to the overview of some basic mathematical preliminaries, and the proposal of a new nonconvex inpainting model. In Section 3, we minutely describe the process of deducing the designed optimization algorithm: primal-dual method. Several experimental simulations and comparisons, which are detailed in Section 4, aim to demonstrate the outstanding performance of the proposed strategy. In conclusion, we end this article with some summative remarks in Section 5.

In this section, we firstly give a brief overview of several necessary definitions and notations, and then put forward a new nonconvex image inpainting model. For later convenience, we begin with the definition of total variation as follows.

Let Ω⊂Rd denote a bounded open domain, and let u be a real valued function on Ω such that u∈L1(Ω) . Then the total variation of u is defined by (4) TV(u)=sup{∫Ωudivϑdx|ϑ∈Cc1(Ω,Rd),‖ϑ‖∞⩽1}. As a generalization of TV, the second-order TGV takes the following form (5) TGVα2(u)=sup{∫Ωudiv2ϑdx|ϑ∈Cc2(Ω,Sd×d),‖ϑ‖∞⩽α0,‖divϑ‖∞⩽α1}, where α=(α0,α1)>0 0$]]> stands for a positive weight, and Sd×d denotes the space of all symmetric d×d tensors. The respective definitions of the divergence operators and infinity norms can be formulated as (divϑ)i=∑j=1d∂ϑij∂xj , 1⩽i⩽d , div2ϑ=∑i,j=1d∂2ϑij∂xi∂xj , and ‖ϑ‖∞=supx∈Ω( ∑i,j=1d|ϑij(x)|2)1/2,‖divϑ‖∞=supx∈Ω( ∑i=1d|(divϑ)i(x)|2)1/2. More details regarding the concept of TGV are reported in Bredies et al. (2010). Therefore, the primal formulation of the second-order TGV can be defined as (6) TGVα2(u)=minv{α1∫Ω|∇u−v|dx+α0∫Ω|ε(v)|dx}, where v=(v1,v2)T and ε(v)=12(∇v+∇vT) represents the symmetric derivative. More explicitly, the operators ∇u and ε(v) have the following formations ∇u=∂xu∂yu,ε(v)=∂xv112(∂yv1+∂xv2)12(∂yv1+∂xv2)∂yv2. The regularizer (6), together with the fidelity term, leads to the TGV based image inpainting model as (7) minu,v{α1∫Ω|∇u−v|dx+α0∫Ω|ε(v)|dx+λ2∫Ω∖D(u−f)2dx}.

Furthermore, choosing a nonconvex potential function F(|t|)=log(1+β|t|) and acting on the above TGV regularizer, this results in our nonconvex TGV inpainting model as follows: (8) minu,v{α1∫Ωlog(1+β|∇u−v|)dx+α0∫Ωlog(1+β|ε(v)|)dx+λ2∫Ω∖D(u−f)2dx} with β being an adjustable weighting parameter.

This section is devoted to the proposal of our resulting numerical algorithm in detail, which is tailed for solving the optimization problem (8), by artfully combining the classical iteratively reweighted ℓ1 algorithm and primal-dual technique.

It is common knowledge that, for tackling the nonconvex functions, the so-called iteratively reweighted ℓ1 algorithm (Candès et al., 2008; Ochs et al., 2015) has been demonstrated to be a standard solver. By this method, solving our nonconvex model amounts to minimizing the following surrogate convex optimization problem (9) minu,v{α1w1k‖∇u−v‖1+α0w0k‖ε(v)‖1+λ2∑i,j∈Ω∖D(ui,j−fi,j)2}, where two weights w1k and w0k are calculated in the latest k-th iteration, and endowed with the following concise formulas (10) w1k=β1+β|∇uk|,w0k=β1+β|ε(vk)|.

To obtain a fast and global optimal solution of (9), we resort to the popular primal-dual method, as proposed in Chambolle and Pock (2011), Esser et al. (2010). This technique has shown the superior capability of solving large-scale convex optimization problems in image processing and computer vision. Thanks to the Legendre-Fenchel transform, the nonsmooth problem (9) can be transformed into a convex-concave saddle-point formulation as follows (11) minu,vmaxp∈P,q∈Q{⟨∇u−v,p⟩+⟨ε(v),q⟩+λ2∑i,j∈Ω∖D(ui,j−fi,j)2}, with the introduced two dual variables p and q. Their feasible sets related with two variables are characterized by (12) P={p=(p1,p2)T|‖p‖∞⩽α1w1k}, (13) Q=q=q11q12q21q22|‖q‖∞⩽α0w0k, where the induced infinity norm of p is defined as ‖p‖∞=maxi,j|pi,j| with |pi,j|=(p1i,j)2+(p2i,j)2 , and the similar manipulation applies to the infinity norm of q.

First of all, the solutions with respect to the dual variables p and q are formulated as (14) pk+1=PP(pk+δ(∇u˜k−v˜k)),qk+1=PQ(qk+δε(v˜k)), where PP(t) is the Euclidean projection of t onto the convex set P. For numerical computation, the projection operators PP and PQ for p and q are equipped with the forms of (15) PP(p˜k)=p˜kmax(1,|p˜k|/α1w1k),PQ(q˜k)=q˜kmax(1,|q˜k|/α0w0k).

Subsequently, we turn our attention to the solution of the primal variable u. Notice that the resolvent operator relating with the fidelity term has a simple quadratic framework, we have (16) uk+1=uk+τ(div(pk+1)+λf)1+τλ,if(i,j)∈Ω∖D,uk+τdiv(pk+1),if(i,j)∈D. Likewise, the solution to the primal variable v is trivially given by (17) vk+1=vk+τ(divh(qk+1)+pk+1), where div and divh denote two divergence operators, subject to div=−∇∗ and divh=−ε∗ with A∗ being the adjoint of A . This, together with the definition of divergence, leads to (18) div(p)=∂xp1+∂yp2,divh(q)=∂xq11+∂yq12∂xq21+∂yq22.

Finally, given the relaxation parameter θ∈[0,1] , the updates for u˜k+1 and v˜k+1 read as (19) u˜k+1=uk+1+θ(uk+1−u˜k), (20) v˜k+1=vk+1+θ(vk+1−v˜k).

Putting the above pieces together, we achieve a highly efficient primal-dual method, which is designed to deal with the resulting objective function. More precisely, starting with the initial setups u0 , u˜0 , v0 , v˜0 , p0 , q0 , δ, τ and θ, the optimization problem (9) is calculated according to the following framework (21) pk+1=PP(pk+δ(∇u˜k−v˜k)),qk+1=PQ(qk+δε(v˜k)),uk+1=uk+τ(div(pk+1)+λf)1+τλ|Ω∖D+(uk+τdiv(pk+1))|D,vk+1=vk+τ(divh(qk+1)+pk+1),u˜k+1=uk+1+θ(uk+1−u˜k),v˜k+1=vk+1+θ(vk+1−v˜k).

It is noteworthy that, as for the computational complexity, the computation costs for the dual variables p, q and the primal variables u, v are all linear, namely they need O(mn) operations for an m×n image. Furthermore, similarly to the discussions (Chambolle and Pock, 2011), the convergence properties of the proposed algorithm are also guaranteed.

Our purpose in this section is to show the visual and quantitative evaluations of the developed nonconvex strategy for image inpainting. We also evaluate the inpainting performance compared to several state-of-the-art convex counterparts, in terms of both visual quality and restoration accuracy. It is worth noticing that the compared models are performed by using the primal-dual algorithm. All experimental simulations are implemented in MATLAB R2011b running on a PC with an Intel(R) Core(TM) i5 CPU at 3.20 GHz and 4 GB of memory under Windows 7.

The steps δ, τ and the parameter θ used in our numerical experiments are chosen as L=12 , δ=10/L , τ=0.1/L and θ=1 , this setting usually results in good convergence. The iterations of all tested methods are terminated when the condition ‖uk+1−uk‖2/‖uk‖2<3×10−4 is met. After recovering the image, the commonly used peak signal-to-noise ratio (PSNR) index is employed as a measure of image restoration quality. The criterion can be defined as (22) PSNR=10log10(2552mn‖u−u˜‖22), with u and u˜ representing the clean and recovered images respectively, and m×n being the size of an image. Meanwhile, we use the Pratt’s figure of merit (FOM) criterion (Pratt, 2001), which is borrowed to evaluate the edge-preserving ability of different approaches. Besides, the structural similarity (SSIM) (Wang et al., 2004) and feature similarity (FSIM) (Zhang et al., 2011) indexes are also employed for image structure information assessment. Generally speaking, the larger the PSNR, FOM, SSIM and FSIM values, the better the performance.

Figure 1 illustrates the efficiency of our model for image inpainting compared to two recently developed methods, i.e. the TV and TGV based convex models. The original Peppers image is 256 × 256 pixels wide with 8-bit gray levels. Figures 1(b1) and 1(b2) represent the damaged images with 30% and 50% missing lines, where the lost lines have been chosen randomly. Subsequently, the second row of Fig. 1 indicates the restorations of 30% lost lines by three different models, while the last row corresponds to the outcomes of 50% missing lines. We remark that two damaged images are processed by our strategy with the equivalent parameters λ=180 , α0=1 and β=0.8 . The different values of parameter α1 are set as α1=0.6 and 0.8 for two degraded images. Moreover, we present in Table 1 the quantitative comparisons coming from three different methods.

To further show the superiority, we take Lena image sized by 256 × 256 pixels as an example for image inpainting. The original image is corrupted by an imposed text, and noisy because of Gaussian noise with standard deviation σ=10 . This results in the degraded version shown in Fig. 2(b). As we already have mentioned, the inpainted results obtained by our proposed strategy are compared to the ones by the TV, TGV based methods. The intuitive comparison and measurable evaluation are provided in detail in Fig. 2 and Table 2, respectively. It is worthwhile to point out that our strategy is implemented by setting the parameters λ=19 and α1=0.8 . The values of other unmentioned parameters are exactly the same as in the previous experiment.

As far as the inpainting of high resolution image is concerned, here we select Man image of size 1024 × 1024 as an instance. The damaged image, which is presented in Fig. 3(b), is deteriorated by an imposed mask, and noisy because of Gaussian noise with standard deviation 15. Regarding this degeneration, the performance of our nonconvex model is demonstrated by comparing with those of the TV and TGV methods. This results in the visual inpainted outcomes, which are shown in the second row of Fig. 3 in turn. Meanwhile, the quantitative evaluations of different approaches are also detailed in Table 3. A point worth emphasizing is that all parameters are valued equivalently just as in the second simulation, except for the coefficient λ is changed to 16 in this situation.

Finally, we extend the application of our developed strategy for colour image inpainting. Here colour Turtle image has dimensions of 500 × 318 pixels. To generate two test destroyed images, we add an imposed text to the clean image, and then corrupt it by Gaussian noise with standard deviation 10 and 20, respectively. More specifically, Fig. 4 intuitively displays the inpainting performance of the TV, TGV based convex models and the proposed scheme. We remark that, in the case of standard deviation 10, the introduced new scheme is performed with the experimental setup as λ=16 , α1=0.6 , α0=1 and β=1.3 . As for the counterpart of standard deviation 20, we tune the parameter λ to be 7, and leave other settings unchanged. Meanwhile, Table 4 shows the measurable comparison between two efficient competitors and our novel strategy in terms of PSNR, FOM, SSIM and FSIM values.

To summarise, as can be observed from Figs. 1–4, TV solver preserves the edge details well but it tends to yield the typical staircase artifacts. We have observed that although the TGV model can suppress the blocky effect, it has the sometimes undesirable edge blurring. As expected, our results exhibit no staircasing in homogeneous regions and simultaneously possess sharp edges. Moreover, the quantitative comparisons listed in Tables 1–4, with respect to the larger PSNR, FOM, SSIM and FSIM values, consistently demonstrate the outstanding performance of our proposed model for image inpainting over other compared methods.

By introducing a nonconvex potential function into the total generalized variation regularizer, this paper constructs a novel nonconvex model for image inpainting. This aims to capture the small features and prevent the distortion phenomenon. To optimize the resulting variational model, we develop in detail an extremely efficient primal-dual method by integrating the classical iteratively reweighted ℓ1 algorithm. Note that the inclusion of nonconvex constraint increases the amount of calculation, this yields little additional computation cost to handling the minimization. However, in terms of overcoming the staircase effect, maintaining edges, and improving restoration accuracy, extensive numerical experiments consistently illustrate the competitive superiority of the newly developed model for image inpainting.