Wavelet inpainting by fractional order total variation

Abstract

Image inpainting in the wavelet domain refers to the recovery of an image from incomplete wavelet coefficients. In this paper, we propose a wavelet inpainting model by using fractional order total variation regularization approach. Moreover, we use a simple but very efficient primal–dual algorithm to calculate the optimal solution. In the light of saddle-point theory, the convergence of new algorithm is guaranteed. Experimental results are presented to show performance of the proposed algorithm.

1 Introduction

Image inpainting, also known as image completion or disocclusion, is an active research area in image processing. It refers to the problem of filling in missing or damaged regions in image, either in the pixel domain or in a transformed domain.

Inpainting in the image domain, which uses the values of the available pixels to fill the missing pixels, has been widely investigated in the last two decades. Bertalmo et al. (2000) introduced the partial differential equations (PDEs) to smoothly propagate the information from the neighboring pixels into the areas contain the unknown pixels. Chan and Shen (2001a) considered a total variational (TV) inpainting model. The TV inpainting model fills in the missing regions such that the TV is minimized, and its use is motivated by the wide applications of TV in image restoration. Further, higher order methods such as the curvature-driven diffusion (CDD) (Chan and Shen 2001b) and Euler’s elastic based variational model (Chan and Shen 2002) were also applied to the inpainting problem in order to overcome the block effects caused by the TV model. These edge-preserved methods are unable to recover the texture regions efficiently. Therefore, the exemplar-based texture synthesis techniques (Criminisi et al. 2004; Aujol et al. 2011) were developed for recovering the textured images. Other techniques such as morphological component analysis is also applied on simultaneous cartoon and texture image inpainting by Elad et al. (2005). In Gilboa and Osher (2008), Chen and Cheng (2010), Peyre et al. (2011), non-local total variation was further investigated and applied in various image restoration problem including the inpainting task. These non-local techniques are more suitable for recovering the texture and fine details of images than the previous local methods. In Jin and Ye (2015), a patch-based image inpainting method using a low-rank Hankel structured matrix completion approach was further investigated. All these works concentrate on image inpainting in the pixel domain.

Inpainting in transformed domains is totally different because each single corruption of data can, in general, affect the whole image, and thus an inpainting region in the pixel domain is not well defined. Transformed domain inpainting arises in practical applications because images are usually formatted, transmitted and stored in a transformed domain. In such situations, the transform is either a discrete cosine transform (DCT) or a discrete wavelet transform (DWT). In Fig. 1, we show the layout of 3-scale wavelet decomposition. The higher frequency subbands, such as”HH_1, HH_2, LH_1, HL_1, LH_2,HL_2” in Fig. 1, do not greatly affect visual quality, while the loss of other high frequencies in the coarsest subband (”HL_3,LH_3” in Fig. 1) create Gibbs artifacts or other blur effects. During storage and transmission, certain coefficients may be lost or corrupted, which naturally leads to the transformed domain inpainting problem. In Cai et al. (2008) used tight-frame approach for inpainting and showed that it was equivalent to using an $l_1$ regularization on the tight-frame coefficients. In He and Wang (2014), a weighted sparse restoration model based on the wavelet frame are proposed. This new algorithm can be considered as the incorporation of prior structural information of the wavelet frame coefficients into the traditional $l_1$ model.

Fig. 1

3-scale wavelet decomposition

An alternative class of approaches is to use a hybrid method to control both image and wavelet domains. We start with a standard image model

$$\begin{aligned} f=u+\eta \end{aligned}$$

In the following, images are transformed from the pixel domain to a wavelet domain through a wavelet transform. The wavelet coefficients of the noisy image f under an orthogonal wavelet transform W are given by $\hat{{f}}=Wf$. The observed wavelet coefficients $\hat{{f}}$ are given by $\hat{{f}}$ but with the missing ones set to zero, i.e.

$$\begin{aligned} {\hat{f}}_i =\left\{ {{\begin{array}{l} {{\hat{f}}_i ,\;\; i\in I\;\;\;} \\ {0,\;\;i\in \Omega \backslash I\;} \\ \end{array} }} \right. \end{aligned}$$

Here, $\Omega$ is the complete index set in the wavelet domain, and $I\subset \Omega$ is the set of available wavelet coefficients. Then, an observed image f is obtained by the inverse wavelet transform $f=W^{T}\hat{{f}}$.

Durand and Froment (2003) considered to reconstruct the wavelet coefficients using the total variation norm. To fill in the corrupted coefficients in the wavelet domain in such a way that sharp edges in the image domain are preserved, Chan et al. (2006) proposed the following to minimize the objective function:

$$\begin{aligned} J(u)=\left\| u \right\| _{TV} +\frac{\lambda }{2}\sum _{i\in I} {(\hat{{f}}_i -\hat{{u}}_i )^{2}} \end{aligned}$$

(1)

where

$$\begin{aligned} \left\| u \right\| _{TV} =\sum _{(r,s)\in \Omega } {\left( \left| {(D_x u)_{r,s} } \right| ^{2}+\left| {(D_y u)_{r,s} } \right| ^{2}\right) } \end{aligned}$$

is the TV norm. $D_z$ is the forward difference operator in the z-direction for $z\in \{x,y\}, \lambda$ is a regularization parameter $I\subset \Omega$ be the uncorrupted known index set. By using the dual formulation of the TV norm, the minimization of (1) becomes the minimax problem

$$\begin{aligned} \mathop {\min }\limits _u \mathop {\max }\limits _p \;u^{T}\hbox {div}p+\frac{\lambda }{2}\sum _{i\in I} {(\hat{{f}}_i -\hat{{u}}_i )} ^{2} \end{aligned}$$

(2)

where the discrete divergence of pis a vector defined as

$$\begin{aligned} (\hbox {div}p)_{r,s} \equiv p_{r,s}^x -p_{r-1,s}^x +p_{r,s}^y -p_{r,s-1}^y \end{aligned}$$

with $p_{0,s}^x =p_{r,0}^y =0$ for $r,s=1,\ldots ,n$. It is a method that combines coefficients in the wavelet domain and regularization in the image domain.

Although the classical total variation is surprisingly efficient for recovering some lost wavelet coefficients as presented in Chan et al. (2006), it is well known that the total variation regularization is not suitable for images with fine structures, details and textures. In Zhang and Chan (2010), Zhang et al. (2010), extended the TV wavelet inpainting model to the corresponding non-local (NL) form, and proposed an efficient iterative algorithm called Bregmanized operator splitting (BOS) to solve the NLTV wavelet inpainting models (NLTV-BOS). In fact, these models discussed above are all established as special cases of variational image restoration problem. However, these time-consuming non-local methods cannot eliminate the staircase effect and even cause extra blocky artifacts. For the staircase effect elimination, high-order derivative based models perform well, but they often cause blurring of the edges. As a compromise between the first-order TV regularized models and the high-order derivative based models, some fractional-order derivative based models have been introduced in Liu and Chang (1997), Chen et al. (1990, 2011), Pu et al. (2010), Idczak and Kamocki (2015), Bai and Feng (2007) for additive noise removal and image restoration. They can ease the conflict between staircase elimination and edge preservation by choosing the order of derivative properly. Moreover, the fractional-order derivative operator has a “non-local” behavior because the fractional-order derivative at a point depends upon the characteristics of the entire function and not just the values in the vicinity of the point, which is beneficial to improve the performance of texture preservation. The numerical results in literatures (Chen et al. 2013; Zhang et al. 2012; Zhang and Chen 2015) have demonstrated that the fractional-order derivative performs well for eliminating staircase effect and preserving textures.

In this paper, motivated by these works, in order to recover textures and geometry structures simultaneously regularization for different loss cases, we extend the total variation based wavelet inpainting to the fractional order total variation based wavelet inpainting. Moreover, for new model, we also propose a fast iterative algorithm based on the primal–dual method. The primal–dual algorithm was first presented by Arrow et al. (1958) and named as the primal–dual hybrid gradient (PDHG) method in Zhu and Chan (2008). In this method, each iteration updates both a primal and a dual variable. It is thus able to avoid some of the difficulties that arise when working only on the primal or dual side (Chambolle 2004; Esser et al. 2010). The convergence of the primal–dual algorithm has been studied in He and Yuan (2012), Bonettini and Ruggiero (2012). In our paper, the primal–dual algorithm is used to solve the fractional-order total variation inpainting model. The efficiency of this simple model for natural images is validated by a large amount of numerical simulations. Our experiments show that even with substantial loss of wavelet coefficients (up to 50%, including low frequencies), our model may also reconstruct the original image remarkably well, especially in retaining geometric structures. The challenges for fractional regularization in practice include choosing an appropriate order, and finding a stable and efficient algorithm.

The remainder of this paper is organized as follows: Sect. 2 describes the notations for discrete fractional-order derivative. In Sect. 3, we propose a fractional order primal–dual model for image inpainting and detail the proposed algorithm with a convergence analysis. Section 4 reports our simulation results with comparisons, and Sect. 5 concludes this work.

2 Fractional-order derivative

To simplify, our images will be 2-dimensional matrices of size $N\times N$. We denote by X the Euclidean space $\mathbb {R}^{N\times N}$. For any $u=(u_{i,j} )_{i,j=1}^N \in X$, we denote $u_{i,j} =0$ for $i,j<1$ or $i,j>N$.

From Grünwald–Letnikov fractional derivative definition (Zhang et al. 2012), the discrete fractional- order gradient $\nabla ^{\alpha }u$ is a vector in $Y=X\times X$ given by

$$\begin{aligned} \nabla ^{\alpha }u:=\left[ (\nabla ^{\alpha }u)_{i,j} \right] _{i,j=1}^N =\left( \left[ \left( \Delta _1^\alpha u\right) _{i,j} \right] _{i,j=1}^N , \left[ \left( \Delta _2^\alpha u\right) _{i,j} \right] _{i,j=1}^N \right) \end{aligned}$$

(3)

with

$$\begin{aligned} (\Delta _1^\alpha u)_{i,j}= & {} \sum _{k=0}^{K-1} {(-1)^{k}C_k^\alpha u_{i-k,j} ,} \\ (\Delta _2^\alpha u)_{i,j}= & {} \sum _{k=0}^{K-1} {(-1)^{k}C_k^\alpha u_{i,j-k} ,} \quad i,j=1,\ldots ,N \end{aligned}$$

where $C_k^\alpha =\frac{\Gamma (\alpha +1)}{\Gamma (k+1)\Gamma (\alpha -k+1)}$ and $\Gamma (x)$ is the Gamma function. In additional, the coefficients $C^{(\alpha )}$ can also be obtained recursively from

$$\begin{aligned} C_0^{(\alpha )} =1, \quad C_k^{(\alpha )} =\left( {1-\frac{\alpha +1}{k}} \right) C_{k-1}^{(\alpha )} , \quad k=1,2,\ldots \end{aligned}$$

When $\alpha =1,\;C_k^1 =0$ for $k>1$.

For any $p=(p^{1},p^{2})\in Y$ the discrete fractional-order divergence is defined as

$$\begin{aligned} ({\textit{div}}^{\alpha }p)_{i,j}= & {} (-1)^{\alpha }\sum _{k=0}^{K-1} {(-1)^{k}C_k^\alpha p_{i+k,j}^1 } \nonumber \\&+\,(-1)^{\alpha }\sum _{k=0}^{K-1} {(-1)^{k}C_k^\alpha p_{i,j+k}^2 } \end{aligned}$$

(4)

One can check easily that (3) and (4) satisfy the property as follows:

$$\begin{aligned} \left\langle {p,\nabla ^{\alpha }u} \right\rangle _Y =\left\langle {\overline{(-1)^{\alpha }} div^{\alpha }p,u} \right\rangle _X ,\forall u\in X,p\in Y \end{aligned}$$

where $\left\langle {u,v} \right\rangle _X =\sum _{i,j=1}^N {u_{i,j} v_{i,j} ,\forall u,v\in X}$ and $\left\langle {p,q} \right\rangle _Y =\sum _{i,j=1}^N {(p_{i,j}^1 q_{i,j}^1 +p_{i,j}^2 q_{i,j}^2 ),\forall p} =(p^{1},p^{2}),q=(q^{1},q^{2})\in Y$, are the inner products of X and Y, respectively.

Let $J(u)=\left\| {\nabla ^{\alpha }u} \right\| _1$. Then, its conjugate function $J_P^{*} (p)$ satisfies the following property:

$$\begin{aligned} J_P^{*} (p)=\left\{ {{\begin{array}{l} {0,} \\ {+\infty ,} \\ \end{array} }} \right. \;{\begin{array}{l} {p\in P} \\ {p\notin P} \\ \end{array} } \end{aligned}$$

where $P=\left\{ {p\in Y:\left\| p \right\| _\infty \le 1} \right\}$ and $\left\| p \right\| _\infty$ denotes the discrete maximum norm defined as

$$\begin{aligned} \left\| p \right\| _\infty =\mathop {\max \left| {p_{i,j} } \right| }\limits _{i,j} ,\;\;\;\left| {p_{i,j} } \right| =\sqrt{\left( p_{i,j}^1 \right) ^{2}+\left( p_{i,j}^2 \right) ^{2}}. \end{aligned}$$

3 Proposed algorithm

Based on the model (2), we propose a wavelet inpainting model by fractional-order total variation as follows:

$$\begin{aligned} \mathop {\min }\limits _u \mathop {\max }\limits _p \left\langle {\nabla ^{\alpha }u,p} \right\rangle +\frac{\lambda }{2}\sum _{i\in I} {(\hat{{f}}_i -\hat{{u}}_i )^{2}} -J_P^{*} (p) \end{aligned}$$

(5)

There are many numerical algorithms for solving the variation problem related to image inpainting. However, they suffer from slow running or high computational complexity or lack of knowledge on the selection of the regularization parameter. In this paper, by referring the primal–dual algorithm for solving saddle-point problems, we propose a primal–dual formulation to solve the fractional-order wavelet inpainting model (5).

3.1 Primal–dual method for solving saddle-point problems

For clear description, we give some preliminaries on the first-order primal–dual method summarized in Chambolle and Pock (2010). We consider the saddle-point problem

$$\begin{aligned} \mathop {\min }\limits _{x\in X} \mathop {\max }\limits _{y\in Y} \left\langle {Ax,y} \right\rangle +G(x)-F^{{*}}(y) \end{aligned}$$

(6)

where $G:X\rightarrow \left[ {0,+\infty } \right)$ and $F^{{*}}:Y\rightarrow \left[ {0,+\infty } \right)$ are proper convex, lower-semicontinuous (l.s.c.) functions, $F^{{*}}$ being itself the convex conjugate of a convex l.s.c. function F.

This saddle-point problem is a primal–dual formulation of the following nonlinear primal problem

$$\begin{aligned} \mathop {\min }\limits _{x\in X} F(Kx)+G(x) \end{aligned}$$

Or of the corresponding dual problem

$$\begin{aligned} \mathop {\max }\limits _{y\in Y} -(G^{{*}}(-A^{{*}}y)+F^{{*}}(y)) \end{aligned}$$

To solve the saddle-point problem (6), Chambolle and Pock (2010) proposed a primal–dual algorithm. Let the primal variable x be fixed. Taking the derivative of the dual variable y, we have

$$\begin{aligned} y=(I+\partial F^{{*}})^{-1}(y+Ax) \end{aligned}$$

Similarly, by taking the derivative of the primal variable x with the fixed dual variable y, we have

$$\begin{aligned} x=(I+\partial G)^{-1}(x-A^{{*}}y) \end{aligned}$$

where $\partial F^{{*}}$ and $\partial G$ are the subgradients of functions $F^{{*}}$ and G.

In the sense that their resolvent operator through

$$\begin{aligned} x= & {} (I+\tau \partial G)^{-1}(y) \\= & {} \arg \mathop {\min }\limits _x \left\{ {\frac{\left\| {x-y} \right\| ^{2}}{2\tau }+G(x)} \right\} \\ \end{aligned}$$

has a closed-form representation.

As analyzed in He and Yuan (2012), Bonettini and Ruggiero (2012), Chambolle and Pock (2010), the saddle-point problem (6) can be regarded as the primal–dual formulation of a nonlinear programming problem, and this fact has inspired some primal–dual algorithms for TV image restoration problems. We refer to, e.g., Zhang et al. (2011) for their numerical efficiency.

3.2 New algorithm

Let $\chi$ be a diagonal matrix with $\chi _{i,j} =1$ if $(i,j)\in I$ and $\chi _{i,j} =0$ if $(i,j)\in \Omega \backslash I$. The minimization problem in (5) can be rewritten as

$$\begin{aligned} \mathop {\min }\limits _u \mathop {\max }\limits _p \left\langle {\nabla ^{\alpha }u,p} \right\rangle +\frac{\lambda }{2}\left\| {\chi (\hat{{u}}-\hat{{f}})} \right\| _2^2 -J_P^{*} (p) \end{aligned}$$

(7)

For convenience, we assume that two variables u and ${\hat{u}}$ can be transformed into each other by ${\hat{u}}=Wu$ and $u=W^{T}\hat{{u}}$. Therefore, the minimization problem (7) becomes

$$\begin{aligned} \mathop {\min }\limits _u \mathop {\max }\limits _p \left\langle {\nabla ^{\alpha }u,p} \right\rangle +\frac{\lambda }{2}\left\| {\chi W(u-f)} \right\| _2^2 -J_P^{*} (p) \end{aligned}$$

(8)

In the form of the general saddle-point problem (6), we see that $A=\nabla ^{\alpha }, G(u)=\frac{\lambda }{2}\left\| {\chi W(u-f)} \right\| _2^2 , F^{{*}}(p)=J_P^{*} (p)$. The minimization problem of (8) can be solved exactly as

$$\begin{aligned} u=f-\frac{A^{T}p}{\lambda \chi W^{T}W} \end{aligned}$$

(9)

Substituting (9) into (8) yields the following dual problem:

$$\begin{aligned} \mathop {\max }\limits _p -\left( \left\| {A^{T}p-\lambda \chi W^{T}Wu} \right\| _2^2 +F^{{*}}(p)\right) \end{aligned}$$

where $-A^{T}$ is the corresponding discretization of the fractional-order divergence.

Since $F^{{*}}$ is the indicator function of a convex set, the resolvent operator reduces to pointwise Euclidean projectors onto $L^{2}$ balls

$$\begin{aligned} p= & {} (I+\sigma \partial F^{{*}})^{-1}({\tilde{p}})\Leftrightarrow p_{i,j} \nonumber \\= & {} \frac{{\tilde{p}}_{i,j} }{\max \{1,\left| {{\tilde{p}}_{i,j} } \right| \}},\hbox { where }{\tilde{p}}=p+\sigma \nabla ^{\alpha }u \end{aligned}$$

(10)

The resolvent operator with respect to G poses simple pointwise quadratic problems. The solution is trivially given by

$$\begin{aligned} u= & {} (I+\tau \partial G)^{-1}({\tilde{u}})\Leftrightarrow u_{i,j} =\frac{{\tilde{u}}_{i,j} +\chi \tau \lambda W^{T}Wf_{i,j} }{1+\chi \tau \lambda W^{T}W} \nonumber \\= & {} \left\{ {{\begin{array}{cc} {\frac{{\tilde{u}}_{i,j} +\tau \lambda W^{T}Wf_{i,j} }{1+\tau \lambda W^{T}W},} &{}{(j,k)\in I} \\ {{\tilde{u}}_{i,j} ,}&{}{(j,k)\in \Omega \backslash I} \\ \end{array} }} \right. \end{aligned}$$

(11)

where ${\tilde{u}}=u-\tau \nabla ^{\alpha {*}}p$. When wavelet transform matrix Wis orthogonal, $W^{T}W=I$. This method can also be generalized to non-orthogonal wavelet transforms, for example, bi-orthogonal wavelet transforms (Cohen et al. 1992), redundant transforms (Kingsbury 2001) and tight frames (Ron and Shen 1997). In these cases, Wis not orthogonal, but still has full rank, and hence $W^{T}W$ is invertible.

Unifying all the schemes together, we obtain the following algorithm:

Fig. 2

Original images: a Barbara image, b Lena image, c Peppers image, d Baboon image, e Boat image, f Goldhill image

Fig. 3

The Barbara image with 10% of wavelet coefficients lost: a received image, b restored image with $\alpha =0.8$ (PSNR $=29.37$ dB), c restored image with $\alpha =1.2$ (PSNR $=34.55$ dB), d restored image with $\alpha =1.4$ (PSNR $=$34.50 dB)

Fig. 4

The Lena image with 10% of wavelet coefficients lost: a received image, b restored image with $\alpha =0.8$ (PSNR $=32.28$ dB), c restored image with $\alpha =1.2$ (PSNR $=33.45$ dB), d restored image with $\alpha =1.4$ (PSNR $=34.86$ dB)

Fig. 5

The peppers image with 50% of wavelet coefficients lost: a receirved image, b restored image with $\alpha =0.8$ (PSNR $=20.19$ dB), c restored image with $\alpha =1.2$ (PSNR $=20.25$ dB), d restored image with $\alpha =1.4$ (PSNR $=21.60$ dB)

Fig. 6

The Baboon image with 50% of wavelet coefficients lost: a received image, b restored image with $\alpha ={0.8}$ (PSNR $=21.15$ dB), c restored image with $\alpha ={1.2}$ (PSNR $=21.72$ dB), d restored image with $\alpha ={1.4}$ (PSNR $=22.01$ dB)

Fig. 7

The Barbara image with additive noise for 10% of wavelet coefficients lost ($\sigma =10)$: a observed image, b restored image with $\alpha =0.8$ by FOTV-PD (PSNR $=23.74$ dB), c restored image with $\alpha =1.2$ by FOTV- PD (PSNR $=24.28$ dB), d restored image $\alpha =1.4$ by FOTV-PD (PSNR $=24.65$ dB), e restored image by TV-PD (PSNR $=22.61$ dB), f restored image by NLTV-BOS(PSNR $=23.59$ dB), g Zoom of (d), h Zoom of (e), i Zoom of (f)

Fig. 8

The Lena image with additive noise for 10% of wavelet coefficients lost ($\sigma =10)$: a observed image, b restored image with $\alpha =0.8$ by FOTV-PD (PSNR $=24.92$ dB), c restored image with $\alpha =1.2$ by FOTV-PD (PSNR $=25.03$ dB), d restored image with $\alpha =1.4$ by FOTV-PD (PSNR $=25.46$ dB), e restored image by TV-PD(PSNR $=22.97$ dB), f restored image by NLTV-BOS (PSNR $=23.52$ dB), g Zoom of (d), h Zoom of (e), i Zoom of (f)

Fig. 9

Peppers image with additive noise for 50% wavelet coefficients randomly lost ($\sigma =10)$. a Received image, b restored image with $\alpha =0.8$ by FOTV-PD (PSNR $=17.99$ dB), c restored image with $\alpha =1.2$ by FOTV-PD (PSNR $=20.18$ dB), d restored image with $\alpha =1.4$ by FOTV-PD (PSNR $=20.68$ dB), e restored image by TV-PD (PSNR $=17.18$ dB), f restored image by NLTV-BOS (PSNR $=19.65$ dB), g Zoom of (d), h Zoom of (e), i Zoom of (f)

Fig. 10

Baboon image with additive noise for 50% wavelet coefficients randomly lost. a Received image, b restored image with $\alpha =0.8$ by FOTV-PD (PSNR $=20.56$ dB), c restored image with $\alpha =1.2$ by FOTV-PD (PSNR $=20.31$ dB), d restored image with $\alpha =1.4$ by FOTV-PD (PSNR $=21.06$ dB), e restored image by TV-PD (PSNR $=18.23$ dB), f restored image by NLTV-BOS (PSNR $=19.37$ dB), g Zoom of (d), h Zoom of (e), i Zoom of (f)

Fig. 11

Whole LH subband ($32 \times 32$) loss a received image, b the result by FOTV-PD ($\alpha =1.2$, PSNR $=33.36$ dB, CPU time $=15.46$ s), c restored image by TV-PD(PSNR $=30.92$ dB, CPU time $=13.39$ s), d restored image by NLTV-BOS (PSNR $=31.33$ dB, CPU time $=500.23$ s)

Fig. 12

Whole HL subband ($32 \times 32$) loss: a received image, b the result by FOTV-PD ($\alpha =1.2$ PSNR $=29.02$ dB, CPU time $=14.29$ s), c restored image by TV-PD (PSNR $=28.08$ dB, CPU time $=11.27$ s), d the result by NLTV-BOS (PSNR $=30.09$ dB, CPU time $=450.71$ s)

Fig. 13

The Boat image with additive noise for whole LH subband loss($\sigma =15)$. a Received image, b the result by FOTV-PD ($\alpha =1.2$, PSNR $=26.75$ dB, CPU time $=12.19$ s), c restored image by TV-PD(PSNR $=24.32$ dB, CPU time $=22.36$ s), d the result by NLTV-BOS (PSNR $=25.48$ dB, CPU time $=535.23$ s)

Fig. 14

The Goldhill image with additive noise for whole HL subband loss ($\sigma =15)$. a Received image, b the result by FOTV-PD ($\alpha =1.2$, PSNR $=25.12$ dB, CPU time $=20.92$ s), c restored image by TV-PD (PSNR $=22.19$ dB, CPU time $=35.47$. d the result by NLTV-BOS (PSNR $=24.48$ dB, CPU time $=524.59$ s)

The parameters $\tau ^{n}, \sigma ^{n}$ play a crucial role for the efficiency of the algorithm. Thus, it is important to prove the convergence of the algorithm under conditions as flexible as possible (Bonettini and Ruggiero 2012). Next we discuss the convergence of the proposed algorithm. In order to guarantee the convergence, suppose a parameter $L=\left\| {\nabla ^{\alpha }} \right\|$. It has been proven in Bonettini and Ruggiero (2012) that the primal–dual algorithm converges to the saddle-point subject to a constraint of the parameter L.

Let $w_i =(-1)^{i}C_i^\alpha$. Then, we have

$$\begin{aligned} \left\| {\overline{(-1)^{\alpha }} div^{\alpha }p} \right\| ^{2}= & {} \sum _{i,j} \left( w_0 p_{i,j}^1 +w_1 p_{i+1,j}^1 +\cdots +w_{K-1} p_{i+K-1,j}^1\right. \\&\left. \quad +\,w_0 p_{i,j}^2 +w_1 p_{i,j+1}^2 +\cdots +w_{K-1} p_{i,j+K-1}^2 \right) ^{2}\\&\le 2K\times \sum _{i,j} \left[ (w_0 p_{i,j}^1 )^{2}+(w_0 p_{i,j}^2 )^{2}+\,(w_1 p_{i+1,j}^1 )^{2}\right. \\&\quad \left. +\,(w_1 p_{i,j+1}^2 )^{2} +\cdots +(w_{K-1} p_{i+K-1,j}^1 )^{2}\right. \\&\quad \left. +\,(w_{K-1} p_{i,j+K-1}^2 )^{2}\right] \\&\le 2K\times \left( w_0^2 +w_1^2 +\cdots +w_{K-1}^2 \right) \left\| p \right\| ^{2} \end{aligned}$$

Therefore

$$\begin{aligned} L=\left\| {\nabla ^{\alpha }} \right\| =\max \left\| {\overline{(-1)^{\alpha }} div^{\alpha }p} \right\| \le \sqrt{2K\sum \nolimits _{i=0}^{K-1} {w_i^2 } } \end{aligned}$$

which guarantees the convergence of new algorithm.

For primal–dual pair (u, p), the partial primal–dual gap G(u, p) is defined by

$$\begin{aligned} G(u,p)= & {} \left\{ {\mathop {\max }\limits _{{p}'} \left\langle {{p}',Au} \right\rangle +\frac{\lambda }{2}\left\| {\chi W(u-f)} \right\| _2^2 -F^{{*}}({p}')} \right\} \\&\quad -\left\{ {\mathop {\min }\limits _{{u}'} \left\langle {p,A{u}'} \right\rangle +\frac{\lambda }{2}\left\| {\chi W({u}'-f)} \right\| _2^2 -F^{{*}}(p)} \right\} \end{aligned}$$

The primal–dual gap G(u, p) is a measure of closeness of the primal–dual (u, p) to the primal–dual solution, and we use it to design the stopping criterion for our numerical algorithm in this paper.

4 Experimental results

In this section, we evaluate the performance of the proposed algorithm-FOTV-PD and compare it with TV-PD (Chan et al. 2006) and NLTV-BOS (Zhang and Chan 2010) in wavelet inpainting by PSNR value and subjective image quality. Six images (size of $256\times 256$): Barbara, Lena, Peppers, Baboon, Boat and Goldhill are used for our tests in Fig. 2. The reconstruction results are shown in this section and also quantitatively evaluated by the peak signal to noise ratio (PSNR) defined by

$$\begin{aligned} PSNR:=10\log _{10} \left[ {\mathop {\max }\limits _{1\le i,j\le N} \left| {(u_0 )_{i,j} } \right| ^{2}/\frac{1}{N^{2}}\sum _{i=1}^N {\sum _{j=1}^N {[(u_0 )_{i,j} -u_{i,j} ]^{2}} } } \right] \end{aligned}$$

where $u_0$ is the original image without noise and u is the inpainted image. In all the following experiments, we apply the Daubechies 7–9 biorthogonal wavelets with symmetric extension for three algorithms. We use the WaveLab to implement the forward and the backward biorthogonal wavelet transforms. 3-scale wavelet decomposition is used for the images in the test.

For the FOTV-PD algorithm, the proper selection of the fraction depends on the image to inpaint. We illustrate the inpainted images with $\alpha =0.8,\;1.2,\;1.4$ respectively. As represented, the smaller $\alpha$ leads to the blocky (staircase) effects and the larger $\alpha$ will make restored image too smooth. $\alpha =1.4$ is appropriate for nonsmooth problems because the diffusion coefficients are close to zero in regions representing large gradients of the fields, allowing discontinuities at those regions.

The steplength $\sigma ^{n}$ and $\tau ^{n}$ are chosen for the convergence (He and Yuan 2012). Indeed, the proposed steplength choices are

$$\begin{aligned} \sigma ^{n}= & {} 0.2+0.08n\\ \tau ^{n}= & {} \frac{\lambda ^{n}}{1-\lambda ^{n}},\hbox { with }\lambda ^{n}=\left( 0.5-\frac{5}{15+n}\right) \sigma ^{n}. \end{aligned}$$

For the weight function w(x, y) in the NLTV-BOS regularization, we use the same setting as that adopted in Zhang and Chan (2010), i.e., the patch size and the searching window for the semi-local weight are fixed at 5 and 15. The 10 best neighbors and 4 nearest neighbors are chosen for the weight computation of each pixel.

Experiment 1

Barbara and Lena noiseless with 10% wavelet coefficients lost:

Figures 3 and 4 show the Barbara and Lena images with 10% wavelet coefficients lost randomly and its restored image. We illustrate the inpainted images with $\alpha =0.8, \;{1.2}, \;{1.4}$ respectively. In Fig. 3b, PSNR of the inpainted images with $\alpha =0.8$ is 29.37 dB. Fig. 3c is obtained by $\alpha =1.2$ with PSNR $=34.55$ dB and Fig. 3d with PSNR $=34.50$ dB is obtained by $\alpha =1.4$. In Fig. 4b, PSNR of the inpainted images with $\alpha =0.8$ is 32.28 dB. Figure 4c is obtained by $\alpha =1.2$ with PSNR $=33.45$ dB and Fig. 4d with PSNR $=34.86$ dB is obtained by $\alpha =1.4$.

Experiment 2

Peppers and Baboon noiseless with 50% wavelet coefficients lost:

In Fig. 5 shows the Peppers image with 50% wavelet coefficients lost randomly and its restored image. We illustrate the inpainted images with $\alpha =0.8, \;{1.2}, \;{1.4}$ respectively. In Fig. 5b, PSNR of the inpainted images with $\alpha =0.8$ is 20.19 dB. Figure. 5c is obtained by $\alpha =1.2$ with PSNR $=20.25$ dB and Fig. 5d with PSNR $=21.60$ dB is obtained by $\alpha =1.4$. In Fig. 6b, PSNR of the inpainted images with $\alpha =0.8$ is 21.15dB. Figure 6c is obtained by $\alpha =1.2$ with PSNR $=21.72$ dB and Fig. 6d with PSNR $=22.01$ dB is obtained by $\alpha =1.4$.

Experiment 3

Barbara and Lena with additive noise for 10% wavelet coefficients lost:

In order to show that the proposed algorithm is capable of denoising as a by-product of the inpainting, we added a zero mean white Gaussian noise ($\sigma ={10})$ to the images Barbara and Lena with 10% of wavelet coefficients lost randomly and then applied the FOTV-PD algorithm. Figures 7 and 8 show the inpainting result. We illustrate the inpainted images with $\alpha {=0.8}, \;{1.2}, \;{1.4}$ by FOTV-PD respectively. It is observed that FOTV-PD outperforms TV-PD and NLTV-BOS regularization in terms of PSNR and visual image quality, especially for the repeating cloth pattern.

Experiment 4

Peppers and Baboon with additive noise for 50% wavelet coefficients lost:

In Figs. 9 and 10, We add the white Gaussian noise with ($\sigma ={10})$ to Peppers and Baboon images with 50% of wavelet coefficients lost randomly. The images and their zoomed show that FOTV-PD can remove almost all the staircase effects and recover cleaner edges than TV-PD and NLTV-BOS.

Experiment 5

Lena and peppers with the two cases of wavelet coefficients missing:

In Figs. 11 and 12, the Lena and Peppers images are used to test three algorithms. The two cases of wavelet coefficients missing: the whole LH and HL loss are considered. The corresponding PSNR values and CPU time are also shown. The images and their zoomed in views show that these algorithms can remove small oscillations created by lost coefficients, while the PSNR of NLTV-BOS and FOTV-PD give about 2 db higher than TV-PD. The CPU time of FOTV-PD is less than NLTV-BOS.

Experiment 6

Boat and Goldhill with additive noise for the two cases of wavelet coefficients missing:

In Figs. 13 and 14, we add the white Gaussian noise with ($\sigma ={15})$ to Boat and Goldhill images for testing three algorithms. The two cases of wavelet coefficients missing: the whole LH and HL loss are considered. The FOTV-PD regularization gives a higher PSNR than TV-PD and NLTV-BOS. The CPU time of FOTV-PD is less than NLTV-BOS.

Tables 1, 2 and 3 give the results of our experiments. In summary, in Figs. 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13 and 14, the results show that the larger the parameter $\alpha$ is, the better the textures are preserved. The resultant images show that our method can remove the noise and keep more details of the image. It is observed that our method (FOTV-PD) is more efficient than the NLTV-BOS algorithm in the CPU time though the PSNR values are more or less the same. The FOTV-PD regularization gives a higher PSNR and less staircase effect than TV-PD.

Table 1 Comparison of noise free cases (PSNR:dB)

Table 2 Comparison of noise cases ($\sigma =10$, PSNR:dB)

Table 3 PSNR and CPU time for different methods (different $\sigma$, PSNR:dB, CPU:s)

5 Conclusion

In this paper we have presented a FOTV model for wavelet inpainting problem. We applied the primal–dual algorithm to optimize the model. We discussed different loss cases in the wavelet domain, with and without noise. The numerical examples have shown that the new algorithm is very effective not only for restoring geometric features but also for filling in some image patterns. In future, on one hand, further theoretical work should attempt to document the performance of the method in filling in missing samples when the object truly has a sparse representation. On the other hand, in new algorithms, the selection of parameters is crucial for restoration quality. In our future work, we will discuss the adaptive parameter selection methods for the fractional-order total variation models.