# A Nonmonotone Gradient Algorithm for Total Variation Image Denoising Problems

Authors: Peng Wang; Shifang Yuan; Xiangyun Xie; Shengwu Xiong
Journal: Mathematical Problems in Engineering
 (2016)

---

## Abstract

The total variation (TV) model has been studied extensively because it is able to preserve sharp attributes and capture some sparsely critical information in images. However, TV denoising problem is usually ill-conditioned that the classical monotone projected gradient method cannot solve the problem efficiently. Therefore, a new strategy based on nonmonotone approach is digged out as accelerated spectral project gradient (ASPG) for solving TV. Furthermore, traditional TV is handled by vectorizing, which makes the scheme far more complicated for designing algorithms. In order to simplify the computing process, a new technique is developed in view of matrix rather than traditional vector. Numerical results proved that our ASPG algorithm is better than some state-of-the-art algorithms in both accuracy and convergence speed.


---

## Body

## 1. Introduction

Blur and noise are unavoidable during the acquisition and transmission of images, and this may be introduced by the poor lighting conditions, faulty camera or unperfect transmission channels, and so on. It is interesting and challenging to restore the ideal image from its degraded version. Several effective mathematical models and algorithms have emerged such as partial differential equations [1], sparse-land models [2, 3], and regularization [2].This paper mainly elaborated on one of the most popular and effective tools for image denoising problem named TV [3–5], as it has been shown to preserve sharp edges both experimentally and theoretically. In view of the good performance in image processing, TV has been extensively studied in many image processing fields such as denoising [3, 4], deblurring [6], and inpainting [5, 7]. Meanwhile, various algorithms [3, 5–8] for solving TV are also proposed. Even though there are so many algorithms, most of them are merely related to vectorization [3, 6]. As images are two-dimensional signals, it is more intuitive and suitable to process by matrix than by vector. Furthermore, it is more efficient and simpler for image processing in a matrix view. In this work, some universal and useful properties of TV are given in matrix version, while it also applies to other algorithms even without any modification.Over the last few decades, there have been many different variations of the projected gradient method (PG) to solve TV denoising problems [9–11]. Generally, the classical PG method has complexity result of O(1/k) as one of its drawbacks [12], where k is the iteration counter. Many authors devoted themselves into enhancing PG. Birgin et al. [13, 14] imposed a nonmonotone technique to classical PG and developed the spectral projected gradient (SPG) method. Nesterov [15] gave a concise and efficient strategy which improved the convergence speed of PG to O(1/k2). Recently, similar techniques were tactfully managed to different traditional algorithms [8, 10, 11, 16, 17] and corresponding optimal complexity results were obtained: Beck and Teboulle [10] proposed a fast duality-based gradient projection methods to solve TV; Chambolle and Pock [11] and Goldfarb et al. [16] accelerated the classical primal-dual algorithm and alternating direction augmented Lagrangian methods, respectively; more recently, Ouyang et al. [17] adopted the same technique to enhance the convergence of alternating direction method of multipliers (ADMM). Though so many studies have been done based on Nesterov’s theory, to the best of our knowledge, no work explores the possibility between Nesterov’s scheme [15] and the spectral projected gradient algorithm. Although the SPG approach is interesting, the strong disturbance always occurs before its convergence and thus casts a shadow over the approach; meanwhile, the key thought in Nesterov’s work [15] is that a combination of past iterates is used to compute the next iterate. This work is purposed to reduce the SPG’s disturbance by Nesterov’s method and propose an accelerated spectral projected gradient (ASPG) for TV denoising problem.


## 2. Primal-Dual Framework of Total Variation Denoising

In this section, we consider the TV denoising problem which is formulated as(1)minu∈Ωu-b2+2λuTV,where u and b denote an ideal and the noised image, respectively, the box region Ω is practically selected as [0,1] or [0,255] to constrain the value of u, and uTV is called TV seminorm usually divided into isotropic and anisotropic types which are, respectively, defined as the paper of Chambolle [9]. It is worth mentioning that our approach can be applied to TVI and TVA. However, for the sake of compactness, we will put emphasis on TVI.


### 2.1. Notations and Outline

To smooth the process, some main notations are introduced here. The standard inner product in Euclidean spaceRm×n is defined as 〈A,B〉=tr⁡(ATB). Denote the right linear space in Euclidean space R(m-1)×n×Rm×(n-1)={[A,B]∣A∈R(m-1)×n,B∈Rm×(n-1)}. For convenience, we write C=R(m-1)×n×Rm×(n-1). Thus, we can define the inner product as(2)A1,B1,A2,B1=tr⁡A2TA1+tr⁡B2TB1,∀Ai,Bi∈Rm-1×n×Rm×n-1,i=1,2.The rest of this paper is organized as follows: In the following subsections, some important operators in matrix version for solving TV, followed by the algorithm for TV-based image denoising, are explained. In Section3, the spectral projected gradient algorithm is first recapped and then the accelerated version ASPG is derived by it. To show the effectiveness of the proposed approach, numerical comparisons with existing state-of-the-art methods are carried out in Section 4. Finally, Section 5 contains the conclusion.


### 2.2. Some Preliminaries for TV Denoising

In this section, we will define some useful operators which are necessary for our algorithm. The operators are defined in matrix version instead of the traditional vector version [3, 6], which makes TV more understandable and concise.(a) Subset. S is a subset in the inner product space C as follows: (3)S=P1,P2∣P1,P2∈C,p1i,j2+p2i,j2≤1fori=1:m-1,j=1:n-1,p1i,n≤1,fori=1:m-1,p2m,j≤1,forj=1:n-1,where pk,(i,j) is the entry of Pk  (fork=1,2).(b) Projected Operator. In this paper, two kinds of projection operators PΩ(u) and PS(P) are necessary: An image u projected onto a box set Ω≡[b1,b2] is easily computed:(4)PΩui,j=b1ifui,j<b1ui,jifb1≤ui,j≤b2b2ifui,j>b2.Taking P=(P1,P2)∈C, for TVI problem, (PSP)i,j∈S is given by (5)
P
S
P
1
i
,
j
=
P
1
i
,
j
max
⁡
1
,
P
1
i
,
n
i
f
i
=
1
:
m
-
1
P
1
i
,
j
max
⁡
1
,
P
1
i
,
j
2
+
P
2
i
,
j
2
o
t
h
e
r
w
i
s
e
,
P
S
P
2
i
,
j
=
P
2
i
,
j
max
⁡
1
,
P
2
i
,
n
i
f
i
=
1
:
m
-
1
P
2
i
,
j
m
a
x
1
,
P
1
i
,
j
2
+
P
2
i
,
j
2
o
t
h
e
r
w
i
s
e
,while for TVA problem the projected operator is defined as(6)PSP1i,j=P1i,jmax⁡1,P1i,j;PSP2i,j=P2i,jmax⁡1,P2i,j.(c) Gradient Operator. If an image u∈Rm×n, the gradient is an element in Du∈C defined as Du=(Dxu,Dyu) with (7)Dxui,j=ui,j-ui+1,j,i=1:m-1,j=1:n;Dyui,j=ui,j-ui,j+1,i=1:m,j=1:n-1.(d) Divergence Operator. The divergence of a vector P=(P1,P2)∈S is an array in Rm×n computed by(8)div⁡Pi,j=p1,i,j-p1,i-1,j+p2,i,j-p2,i,j-1,which implies that p1,(0,j)=p1,(m,j)=p2,(i,0)=p2,(i,n)≡0 for i=1:m, j=1:n.It should be mentioned that the operators(b), (c), and (d) are defined with the assumption of periodic boundary which is adopted in the rest of this paper.


### 2.3. The Primal Dual Solution of TV

As the denoising problem (1) is not differentiable, the traditional optimal methods are not applicable. Though there are so many techniques to overcome the difficulty, we employ the scheme of Chambolle [9, 18] for its effectiveness and simpleness.Now, we give the TV-based image denoising algorithm in primal-dual view which mainly contains two steps.Algorithm 1 (TV-based image denoising (TVID)).
Input: b : observed image λ : regularization parameter Step  0: TakeP0=(0(m-1)×n,0m×(n-1)). Step  1:u=PΩ(b-λdiv⁡P) Compute Step  2:P∗=argminP∈Sb-λdiv⁡PF2-u∗-b+λdiv⁡PF2 Output:u∗=PΩ(b-λdiv⁡P∗)Theorem 2.
The TVID algorithm can obtain an analytic solution of the TV image denoising problem (1).Proof.
According to the primal-dual approach [9, 18], the TV seminorm can be written as follows:(9)uTV=supP∈S⁡u,div⁡P.Substituting (9) into (1), then we get(10)minu∈ΩmaxP∈Su-b2+2λu,div⁡P.By the min-max theorem, the above equation is equivalent to(11)maxP∈Sminu∈Ωu-b2+2λu,div⁡P.Obviously, the inner part of the above equation,(12)minu∈Ωu-b2+2λu,div⁡P,has an analytic solution:(13)u∗=PΩb-λdiv⁡P,where PΩ(ζ) denotes the projection of ζ onto the convex set Ω.


## 2.1. Notations and Outline

To smooth the process, some main notations are introduced here. The standard inner product in Euclidean spaceRm×n is defined as 〈A,B〉=tr⁡(ATB). Denote the right linear space in Euclidean space R(m-1)×n×Rm×(n-1)={[A,B]∣A∈R(m-1)×n,B∈Rm×(n-1)}. For convenience, we write C=R(m-1)×n×Rm×(n-1). Thus, we can define the inner product as(2)A1,B1,A2,B1=tr⁡A2TA1+tr⁡B2TB1,∀Ai,Bi∈Rm-1×n×Rm×n-1,i=1,2.The rest of this paper is organized as follows: In the following subsections, some important operators in matrix version for solving TV, followed by the algorithm for TV-based image denoising, are explained. In Section3, the spectral projected gradient algorithm is first recapped and then the accelerated version ASPG is derived by it. To show the effectiveness of the proposed approach, numerical comparisons with existing state-of-the-art methods are carried out in Section 4. Finally, Section 5 contains the conclusion.


## 2.2. Some Preliminaries for TV Denoising

In this section, we will define some useful operators which are necessary for our algorithm. The operators are defined in matrix version instead of the traditional vector version [3, 6], which makes TV more understandable and concise.(a) Subset. S is a subset in the inner product space C as follows: (3)S=P1,P2∣P1,P2∈C,p1i,j2+p2i,j2≤1fori=1:m-1,j=1:n-1,p1i,n≤1,fori=1:m-1,p2m,j≤1,forj=1:n-1,where pk,(i,j) is the entry of Pk  (fork=1,2).(b) Projected Operator. In this paper, two kinds of projection operators PΩ(u) and PS(P) are necessary: An image u projected onto a box set Ω≡[b1,b2] is easily computed:(4)PΩui,j=b1ifui,j<b1ui,jifb1≤ui,j≤b2b2ifui,j>b2.Taking P=(P1,P2)∈C, for TVI problem, (PSP)i,j∈S is given by (5)
P
S
P
1
i
,
j
=
P
1
i
,
j
max
⁡
1
,
P
1
i
,
n
i
f
i
=
1
:
m
-
1
P
1
i
,
j
max
⁡
1
,
P
1
i
,
j
2
+
P
2
i
,
j
2
o
t
h
e
r
w
i
s
e
,
P
S
P
2
i
,
j
=
P
2
i
,
j
max
⁡
1
,
P
2
i
,
n
i
f
i
=
1
:
m
-
1
P
2
i
,
j
m
a
x
1
,
P
1
i
,
j
2
+
P
2
i
,
j
2
o
t
h
e
r
w
i
s
e
,while for TVA problem the projected operator is defined as(6)PSP1i,j=P1i,jmax⁡1,P1i,j;PSP2i,j=P2i,jmax⁡1,P2i,j.(c) Gradient Operator. If an image u∈Rm×n, the gradient is an element in Du∈C defined as Du=(Dxu,Dyu) with (7)Dxui,j=ui,j-ui+1,j,i=1:m-1,j=1:n;Dyui,j=ui,j-ui,j+1,i=1:m,j=1:n-1.(d) Divergence Operator. The divergence of a vector P=(P1,P2)∈S is an array in Rm×n computed by(8)div⁡Pi,j=p1,i,j-p1,i-1,j+p2,i,j-p2,i,j-1,which implies that p1,(0,j)=p1,(m,j)=p2,(i,0)=p2,(i,n)≡0 for i=1:m, j=1:n.It should be mentioned that the operators(b), (c), and (d) are defined with the assumption of periodic boundary which is adopted in the rest of this paper.


## 2.3. The Primal Dual Solution of TV

As the denoising problem (1) is not differentiable, the traditional optimal methods are not applicable. Though there are so many techniques to overcome the difficulty, we employ the scheme of Chambolle [9, 18] for its effectiveness and simpleness.Now, we give the TV-based image denoising algorithm in primal-dual view which mainly contains two steps.Algorithm 1 (TV-based image denoising (TVID)).
Input: b : observed image λ : regularization parameter Step  0: TakeP0=(0(m-1)×n,0m×(n-1)). Step  1:u=PΩ(b-λdiv⁡P) Compute Step  2:P∗=argminP∈Sb-λdiv⁡PF2-u∗-b+λdiv⁡PF2 Output:u∗=PΩ(b-λdiv⁡P∗)Theorem 2.
The TVID algorithm can obtain an analytic solution of the TV image denoising problem (1).Proof.
According to the primal-dual approach [9, 18], the TV seminorm can be written as follows:(9)uTV=supP∈S⁡u,div⁡P.Substituting (9) into (1), then we get(10)minu∈ΩmaxP∈Su-b2+2λu,div⁡P.By the min-max theorem, the above equation is equivalent to(11)maxP∈Sminu∈Ωu-b2+2λu,div⁡P.Obviously, the inner part of the above equation,(12)minu∈Ωu-b2+2λu,div⁡P,has an analytic solution:(13)u∗=PΩb-λdiv⁡P,where PΩ(ζ) denotes the projection of ζ onto the convex set Ω.


## 3. Accelerated Spectral Projected Gradient Based TV Denoising

In this section, first there will be a brief on spectral projected gradient method [14]. Next an accelerated strategy will be used to enhance SPG.


### 3.1. Introduction to Spectral Projected Gradient Method

By combining Barzilai-Borwein nonmonotone [19] ideas with traditional projected gradient algorithm, Birgin et al. [13, 14] developed a new gradient algorithm that is SPG, which is suitable for convex optimization problems with projection easy to be computed on feasible set. By incorporating a spectral step length and a nonmonotone globalization strategy, SPG speeds up the traditional PG and maintains it to be simple and easy to code.The SPG method aims to minimizef on a closed and convex set Ω; that is,(14)minx∈Ωfx.As the traditional projection method, the SPG method has the form(15)xk+1=xk+αkdk,where αk is the step length, and the search direction dk has been defined as [14](16)dk=PΩxk-λk∇fxk-xk.In the classical SPG method, the nonmonotone decrease criterion is realized by an integer parameter M≥1 which guarantees the object function decrease every M iterations. In the line search stage, a sufficient decrease parameter γ∈(0,1) is used to satisfy Armijo criterion. Besides, some other parameters are also required: safeguarding parameters 0<αmin<αmax<∞ for the spectral step length and safeguarding parameters 0<σ1<σ2<1 for the quadratic interpolation. For later reference, we now recall the theorem by Birgin et al. [14] in which convergence of classical SPG is shown.Theorem 3 (see [14]).
The spectral projected algorithm is well defined, and any accumulation point of the sequence{xk} that it generates is a constrained stationary point of (14).


### 3.2. Accelerated SPG for TVID

In this section, we will elaborate our algorithm on TV denoising problem (1). From algorithm TVID, problem (1) can be solved if and only if Step 2 is solved. Thus, we proposed an accelerated spectral projected gradient (ASPG) for solving Step 2. The proposed ASPG mainly consists of two parts: a nonmonotone projected gradient for finding the feasible solutions and a combination of the former two iterations for reducing the turbulence of the algorithm and accelerating the convergence speed. In order to solve Step 2 in algorithm TVID, substituting (13) into (11) and simplifying yield(17)minP∈SGP=b-λdiv⁡PF2-u∗-b+λdiv⁡PF2.And the gradient of (17) is(18)∇GP=-2λDPΩb-λdiv⁡P,where D(·) can be computed by the gradient operator in Section 2.2. Substituting (18) into (16) and simplifying them together with (13), we get the search direction of ASPG:(19)dk=PSPk+2λαkDuk-Pk,where PS(·) is defined as the projected operator in Section 2.2.The nonmonotone linear search and the spectral step length are updated just as the classical SPG [14]. Following nonmonotone line search, ASPG adopts Nesterov’s [15] technique to improve the performance of classical SPG. Finally, it should be mentioned that the ASPG algorithm is used for the dual step in TVID algorithm; that is, the variation P in ASPG is an element of the inner product space C. Consequently, the inner product involving ASPG should be computed as (2).Algorithm 4 (accelerated spectral projected gradient (ASPG)).
Input:Q0∈C, integer M≥1, α0∈[αmin,αmax]
the regularization parameterλ an integerIter and the observed image b Step  0: TakeP1=Q0=(0(m-1)×n,0m×(n-1)), t1=1 Step  1:(k=1,…,Iter) Compute Step  2: Iterate
u k = P Ω b - λ  div ⁡ P k d k = P S P k + 2 λ α k D u k - P k; Step  2.1: Nonmonotone Line Search Compute G m a x = max ⁡ { G ( P k - j ) ∣ 0 ≤ j ≤ min ⁡ k , M - 1 } and setτ←1
Step  2.1.1: IfG(Pk+τdk)≤Gmax⁡-2γτλ〈dk,D(uk)〉 then setτk←τ and stop
Step  2.1.2: Compute τ t = λ τ 2 d k , D u k / 2 G P k + τ d k - G P k + 2 λ τ d k , D u k Ifτt∈[σ1,σ2τ] then set τ←τt Otherwise, setτ←τ/2. Go to Step2.1.1 Step  2.2:Qk=PS(Pk+αdk) Step  3:
t k + 1 = ( 1 + 1 + 4 t k 2 ) / 2; P k + 1 = Q k + ( ( t k - 1 ) / t k + 1 ) Q k - Q k - 1; Step  4: Compute the spectral step length
S k = P k + 1 - P k; Y k = - 2 λ ( D ( u k + 1 ) - D ( u k ) ) If〈Yk,Sk〉≤0 then set αk+1←αmax⁡ Otherwise α k + 1 = max ⁡ α min ⁡ , min ⁡ S k , S k / Y k , S k , α max ⁡ Output:u∗=PΩ(b-λdiv⁡PIter)


### 3.3. Convergence Analysis of ASPG

Since our method can be seen as an accelerated version of classical SPG in the dual space, its convergence can be deduced from Theorem3. Now, we summarize the convergence of ASPG in the following theorem.Theorem 5.
The ASPG for TVID is well defined, and any accumulation point of the sequence{Pk} is a constrained stationary point of (17); furthermore, the output u∗ of ASPG is a stationary point of TVID problem (1).Proof.
By (13), u∗ generated by ASPG is a stationary point of (1) if and only if P is a stationary of (17).
Equation (18) shows that the kth gradient of (17) can be gotten by uk; that is, ∇G(Pk)=-2λD(PΩ(uk)). Substituting it into (16), we get the search direction of ASPG that is (19). This means that the search direction of ASPG is the same as that of the SPG direction except that (19) is in the dual space C. Furthermore, the definition of gradient operator D(·) shows that D(uk) is an element of C. Therefore, the inner product 〈dk,D(uk)〉 can be computed by (2). Moreover, both the nonmonotone line search and the spectral step length mainly involve the inner products 〈dk,D(uk)〉, 〈Sk,Sk〉, and 〈Sk,Yk〉. Consequently, the nonmonotone line search and the spectral step length of ASPG are just different from those of the classical SPG in the inner product.
Step3 in ASPG is an additional step besides the classical SPG. It can be known that the step is a linear combination of the previous two results, which will not change the convergence of the whole algorithm. Therefore, from Theorem 3, it follows that P is a stationary of (17). This implies the conclusion.


## 3.1. Introduction to Spectral Projected Gradient Method

By combining Barzilai-Borwein nonmonotone [19] ideas with traditional projected gradient algorithm, Birgin et al. [13, 14] developed a new gradient algorithm that is SPG, which is suitable for convex optimization problems with projection easy to be computed on feasible set. By incorporating a spectral step length and a nonmonotone globalization strategy, SPG speeds up the traditional PG and maintains it to be simple and easy to code.The SPG method aims to minimizef on a closed and convex set Ω; that is,(14)minx∈Ωfx.As the traditional projection method, the SPG method has the form(15)xk+1=xk+αkdk,where αk is the step length, and the search direction dk has been defined as [14](16)dk=PΩxk-λk∇fxk-xk.In the classical SPG method, the nonmonotone decrease criterion is realized by an integer parameter M≥1 which guarantees the object function decrease every M iterations. In the line search stage, a sufficient decrease parameter γ∈(0,1) is used to satisfy Armijo criterion. Besides, some other parameters are also required: safeguarding parameters 0<αmin<αmax<∞ for the spectral step length and safeguarding parameters 0<σ1<σ2<1 for the quadratic interpolation. For later reference, we now recall the theorem by Birgin et al. [14] in which convergence of classical SPG is shown.Theorem 3 (see [14]).
The spectral projected algorithm is well defined, and any accumulation point of the sequence{xk} that it generates is a constrained stationary point of (14).


## 3.2. Accelerated SPG for TVID

In this section, we will elaborate our algorithm on TV denoising problem (1). From algorithm TVID, problem (1) can be solved if and only if Step 2 is solved. Thus, we proposed an accelerated spectral projected gradient (ASPG) for solving Step 2. The proposed ASPG mainly consists of two parts: a nonmonotone projected gradient for finding the feasible solutions and a combination of the former two iterations for reducing the turbulence of the algorithm and accelerating the convergence speed. In order to solve Step 2 in algorithm TVID, substituting (13) into (11) and simplifying yield(17)minP∈SGP=b-λdiv⁡PF2-u∗-b+λdiv⁡PF2.And the gradient of (17) is(18)∇GP=-2λDPΩb-λdiv⁡P,where D(·) can be computed by the gradient operator in Section 2.2. Substituting (18) into (16) and simplifying them together with (13), we get the search direction of ASPG:(19)dk=PSPk+2λαkDuk-Pk,where PS(·) is defined as the projected operator in Section 2.2.The nonmonotone linear search and the spectral step length are updated just as the classical SPG [14]. Following nonmonotone line search, ASPG adopts Nesterov’s [15] technique to improve the performance of classical SPG. Finally, it should be mentioned that the ASPG algorithm is used for the dual step in TVID algorithm; that is, the variation P in ASPG is an element of the inner product space C. Consequently, the inner product involving ASPG should be computed as (2).Algorithm 4 (accelerated spectral projected gradient (ASPG)).
Input:Q0∈C, integer M≥1, α0∈[αmin,αmax]
the regularization parameterλ an integerIter and the observed image b Step  0: TakeP1=Q0=(0(m-1)×n,0m×(n-1)), t1=1 Step  1:(k=1,…,Iter) Compute Step  2: Iterate
u k = P Ω b - λ  div ⁡ P k d k = P S P k + 2 λ α k D u k - P k; Step  2.1: Nonmonotone Line Search Compute G m a x = max ⁡ { G ( P k - j ) ∣ 0 ≤ j ≤ min ⁡ k , M - 1 } and setτ←1
Step  2.1.1: IfG(Pk+τdk)≤Gmax⁡-2γτλ〈dk,D(uk)〉 then setτk←τ and stop
Step  2.1.2: Compute τ t = λ τ 2 d k , D u k / 2 G P k + τ d k - G P k + 2 λ τ d k , D u k Ifτt∈[σ1,σ2τ] then set τ←τt Otherwise, setτ←τ/2. Go to Step2.1.1 Step  2.2:Qk=PS(Pk+αdk) Step  3:
t k + 1 = ( 1 + 1 + 4 t k 2 ) / 2; P k + 1 = Q k + ( ( t k - 1 ) / t k + 1 ) Q k - Q k - 1; Step  4: Compute the spectral step length
S k = P k + 1 - P k; Y k = - 2 λ ( D ( u k + 1 ) - D ( u k ) ) If〈Yk,Sk〉≤0 then set αk+1←αmax⁡ Otherwise α k + 1 = max ⁡ α min ⁡ , min ⁡ S k , S k / Y k , S k , α max ⁡ Output:u∗=PΩ(b-λdiv⁡PIter)


## 3.3. Convergence Analysis of ASPG

Since our method can be seen as an accelerated version of classical SPG in the dual space, its convergence can be deduced from Theorem3. Now, we summarize the convergence of ASPG in the following theorem.Theorem 5.
The ASPG for TVID is well defined, and any accumulation point of the sequence{Pk} is a constrained stationary point of (17); furthermore, the output u∗ of ASPG is a stationary point of TVID problem (1).Proof.
By (13), u∗ generated by ASPG is a stationary point of (1) if and only if P is a stationary of (17).
Equation (18) shows that the kth gradient of (17) can be gotten by uk; that is, ∇G(Pk)=-2λD(PΩ(uk)). Substituting it into (16), we get the search direction of ASPG that is (19). This means that the search direction of ASPG is the same as that of the SPG direction except that (19) is in the dual space C. Furthermore, the definition of gradient operator D(·) shows that D(uk) is an element of C. Therefore, the inner product 〈dk,D(uk)〉 can be computed by (2). Moreover, both the nonmonotone line search and the spectral step length mainly involve the inner products 〈dk,D(uk)〉, 〈Sk,Sk〉, and 〈Sk,Yk〉. Consequently, the nonmonotone line search and the spectral step length of ASPG are just different from those of the classical SPG in the inner product.
Step3 in ASPG is an additional step besides the classical SPG. It can be known that the step is a linear combination of the previous two results, which will not change the convergence of the whole algorithm. Therefore, from Theorem 3, it follows that P is a stationary of (17). This implies the conclusion.


## 4. Numerical Experiments

In this section, the proposed ASPG algorithm (ASPG _Proposed) is employed to solve the TVID problem, followed by the comparison with some state-of-the-art algorithms: the classical projected gradient given by Chambolle (PG_Chambolle) [9], Birgin’s spectral projected gradient [13, 14] (SPG_Birgin), and the fast gradient projection by Beck and Teboulle [10] (FPG_Beck). The effect of these experiments is measured by relative error, peak signal-to-noise ratio (PSNR), and structural similarity index measurement (SSIM). The test images are 256-by-256 images as shown in Figure 1: (a) Barbara, (b) Boats, (c) Satellite, and (d) Peppers. All the image pixel values are scaled to the interval [0,1].Figure 1
Original image.
(a)
Barbara (b)
Boats (c)
Satellite (d)
PepperIn the following, the applicability of the proposed algorithm on image denoising problems is illustrated. The degraded images are generated by adding Gaussian noise with zero mean and standard deviation of size0.05 to the original images (Figure 1). Throughout the experiments, the parameters involved in SPG and ASPG are set as follows: αmin⁡=10-30, αmax⁡=1030, σ1=0.1, σ2=0.9, γ=10-4, and M=3. For the value of the regularization parameter λ for all schemes, tune it manually and choose the one that gives the most satisfactory results for all four images.The PSNR and the relative error of the four images with different algorithms are shown in Table1. To exclude the random fact to the results, the last column of Table 1 shows the average metrics of the four tested images, and the metrics of the best method for each test case are highlighted in boldface. Similar to FPG_Beck improving PG_Chambolle by Nesterov’s strategy, the proposed ASPG improves the classical SPG_Birgin. Table 1 illustrates that ASPG and FPG_Beck are better than SPG_Birgin and PG_Chambolle, respectively. This fact shows that the accelerated scheme is valid for the ASPG as well as the FPG_Beck. Furthermore, we can find that ASPG is superior to FPG_Beck in that the former is based on the nonmonotonic line search. Table 1 shows that, among all the algorithms, the proposed ASPG algorithm performs the best in both PSNR and relative error.Table 1
Numerical comparison for images (a)–(d) in Figure1.
Barbara Boats Satellite Pepper Average PSNR Error PSNR Error PSNR Error PSNR Error PSNR Error PG_Chambolle 28.8919 0.0735 29.1882 0.0654 29.5731 0.1077 29.4148 0.0662 29.2670 0.0782 SPG_Birgin 29.7996 0.0662 30.4961 0.0562 32.4344 0.0775 30.8096 0.0564 30.8849 0.0641 FPG_Beck 28.9254 0.0732 29.2779 0.0647 31.2876 0.0884 29.4227 0.0661 29.7284 0.0731 ASPG 30.2991 0.0625 31.3927 0.0507 32.6485 0.0756 32.0317 0.0490 31.5930 0.0594The following goes with a deep comparison of the mentioned algorithms. To illustrate this more clearly, in Figure2, relative error, PSNR, and SSIM value are introduced here, which are related to the iterative times for noised Barbara (generated from Figure 1(a)). From Figure 2, we can see that the classical SPG has strong disturbance before its convergence while the ASPG reduces the disturbance and accelerates the convergence speed. Meanwhile, Figure 2 also illustrates that the nonmonotone line search improves all the metrics PSNR, relative error, and SSIM. One more point to mention is that here we only show the relative error, PSNR, and SSIM value which are generated from the degraded version of Figure 1(a), while, for the other figures (i.e., Figures 1(b), 1(c), and 1(d)), they are just different in value compared with that of Figure 1(a), but the performance priority of PG_Chambolle, SPG_Birgin, FPG_Beck, and ASPG is the same, which all verify that ASPG is the best. Finally, Figure 3(a) is corrupted from Figure 1(a). Figures 3(b)–3(d) illustrate the denoised results which processed by SPG_Birgin, FPG_Beck, and ASPG.Figure 2
The evaluation index.
(a)
Relative error (b)
PSNR (c)
SSIMFigure 3
Denoised by different algorithms.
(a)
Barbara, noised (b)
Denoised, SPG (c)
Denoised, FPG (d)
Denoised, ASPGRemote sensing images are widely used in so many fields [20–23]. However, noise is unavoided during the acquisition and transmission of images. To restore the the ideal image from its degraded version is an interesting field of remote sensing image processing. Here, we employ the proposed ASPG algorithm to denoise a remote sensing image (Figure 4). The results are shown as that from Figures 4(a)–4(f), and a selected area is magnified to better prove them in more detail. Both the original and magnified areas are highlighted in green.Figure 4
Remote sensing image denoising.
(a)
Ground truth (b)
Noised (c)
PG (PSNR = 28.3365) (d)
SPG (PSNR = 28.8468) (e)
FPG (PSNR = 28.2593) (f)
ASPG (PSNR = 28.8547)


## 5. Conclusions

In this paper, an accelerated scheme for spectral project gradient is proposed for TV denoising problems. To handle TV in matrix space, a concise version for total variation model is introduced. Numerical examples have been done to verify the performance of algorithm, which show that it is much better than that of some existing state-of-the-art methods.



---

*Source: 4310612-2016-09-15.xml*