Nonconvex Total Generalized Variation Model for Image Inpainting

1Introduction

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

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

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

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.

2Proposed Model

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

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:

3Optimization Algorithm

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

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

First of all, the solutions with respect to the dual variables p and q are formulated as

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

Finally, given the relaxation parameter θ∈[0,1], the updates for u˜k+1 and v˜k+1 read as

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

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.

4Numerical Results

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

Fig. 1

Inpainting results obtained by using three different models. (a) original image, (b1)–(b2) damaged images with 30%, 50% missing lines, (c1)–(c2) TV model, (d1)–(d2) TGV model, (e1)–(e2) our scheme.

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.

Fig. 2

Inpainting results obtained by using three different models. (a) original image, (b) damaged noisy image with Gaussian noise ( σ=10), (c) TV model, (d) TGV model, (e) our scheme.

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.

Fig. 3

Inpainting results obtained by using three different models. (a) original image, (b) damaged noisy image with Gaussian noise ( σ=15), (c) TV model, (d) TGV model, (e) our scheme.

Fig. 4

Inpainting results obtained by using three different models. (a) original image, (b1)–(b2) damaged noisy images with Gaussian noise ( σ=10,20), (c1)–(c2) TV model, (d1)–(d2) TGV model, (e1)–(e2) our scheme.

5Conclusion

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.