EUROPEAN JOURNAL OF PURE AND APPLIED MATHEMATICS
Vol. 15, No. 4, 2022, 2011-2021
ISSN 1307-5543 – ejpam.com
Published by New York Business Global

Efficient New Conjugate Gradient Methods for
Removing Impulse Noise Images

Basim A. Hassan1,∗, Hameed M. Sadiq1

1 Department of Mathematics, College of Computers Sciences and Mathematics,
University of Mosul, Iraq

Abstract. In most applications, denoising image is fundamental to subsequent image processing
operations. In this research, we derivation a new formula of conjugate gradient methods based on
the quadratic model. The fact that the search direction created at each iteration of the proposed
approach is descending and independent of the line search makes it interesting. The use of Wolfe
conditions also determines the global convergence of the suggested approach. To prove the viability
of the suggested approach, comparison tests on impulse noise reduction are given.

2020 Mathematics Subject Classifications: 90C30, 65K05, 49M37

Key Words and Phrases: Optimization, impulse noise, Conjugate gradient method, Global
convergence

1. Introduction

Image denoising is a fundamental problem in image processing operations. One of its
more investigated domains is image denoising which plays an adequate contribution in
many applications. There are two main models to represent impulse noise [17]. One type
of noise is known as salt-and-pepper noise, in which the noisy pixels can only accept the
maximum and minimum pixel values possible within the dynamic range of the source im-
age. The random-valued noise, which may have any random value between the maximum
and minimum pixel values of dynamic range, is another type of impulsive noise [18]. One of
the most significant issues in picture processing is the removal of above both noise. The av-
erage filter and its variations [7] may find the noisy pixels but return them badly when the
noise ratio is large. These two approaches are quite common for this purpose. Unaltered
gray levels exist in unharmed pixels. While the variational technique is capable of keeping
the features and edges well, every pixel’s gray level, including those that aren’t damaged,
is altered, see [19]. The recovered picture may also lose its details and become distorted.

∗Corresponding author.
DOI: https://doi.org/10.29020/nybg.ejpam.v15i4.4568

Email addresses: basimah@uomosul.edu.iq (B. A. Hassan),
hameedsadiq1975@gmail.com (H. M. Sadiq)

https://www.ejpam.com 2011 © 2022 EJPAM All rights reserved.



B. A. Hassan, H. M. Sadiq / Eur. J. Pure Appl. Math, 15 (4) (2022), 2011-2021 2012

The two-phase method in [6] unify the advantages of both methods and we will give a brief
description here. In the following, we let xi,j for (i, j) ∈ A = 1, 2, 3, ...,M × 1, 2, 3, ..., N ,
be the gray level of a true M by N. Let the set of indices of the noisy pixels uncover in
the first phase denote by N, where N ⊂ A. Let ui,j = [ui,j ](i,j)∈N be a column vector

of length c ordered lexicographically (c is the number of elements of N), and yi,j denote
the observed pixel value at position (i, j). Then, the second phase it to recover the noisy
pixels by minimizing the following edge-preserving regularization function:

fα(u) =
∑

(i,j)∈N

[
|ui,j − yi,j |+

β

2
(2× S1

i,j + S2
i,j)

]
(1)

where S1
i,j = 2

∑
(m,n)∈Pi,j∩Nc φα(ui,j − ym,n), S

2
i,j =

∑
(m,n)∈Pi,j∩N φα(ui,j − ym,n) and φα

is an edge-preserving potential function having the parameter α. Examples of such φα(x)
are: φα(x) =

√
α+ x2, α > 0. However, because of the |ui,j − yi,j | term, the functional

of problem (1) is nonsmooth. It is commonly accepted that this nonsmooth term can
separate from (1) because, on the one hand, it keeps the minimizer u close to the original
picture y, ensuring that the original image’s unaltered pixels are preserved. However, the
two-phase approach simply cleans the noisy pixels, leaving the unharmed pixels unaltered,
making issue (1) functional. Consequently, the nonsmooth term is not necessary. The
word ”data-fitting” in [4] should be removed, according to Cai et al. With this process,
fα(u) may be converted into a smooth function that can be effectively reduced. As a
result, the objective function that we will reduce in this essay has the following shape:

fα(u) =
∑

(i,j)∈N

[
(2× S1

i,j + S2
i,j)
]

(2)

Nowadays, conjugate gradient (CG) methods are regarded as popular and efficient algo-
rithms to deal problems noise of image. In general, the method has the following form:

Minf(u);u ∈ Rn (3)

where f is a continuously differentiable function. This problem may be effectively solved
using an iterative technique at the (k + 1) iteration by using the iteration form shown
below:

uk+1 = uk + αkdk (4)

where uk is the current iterate point, dk is a direction of f at uk, and αk > 0 is step size
obtained by a one-dimensional line search. step size αk is obtained using several forms of
line search, i.e., exact line search with quadratic model [20] as follows:

αk = −
gTk dk

dTkQdk
(5)

The strong Wolfe inexact line search is frequently taken into consideration in the conver-
gence analysis implementation of nonlinear conjugate gradient techniques since exact line



B. A. Hassan, H. M. Sadiq / Eur. J. Pure Appl. Math, 15 (4) (2022), 2011-2021 2013

search for searching αk is typically costly and impracticable. It seeks to identify a step
size αk that satisfies the two strong Wolfe requirements listed below [5], namely:

f(uk + αkdk) ≤ f(uk) + δαkg
T
k dk (6)∣∣g(uk + αkdk)

Tdk
∣∣ ≤ σ

∣∣gTk dk∣∣ (7)

where 0 < δ < σ < 1 are arbitrary constants and gk = ∇f(xk). The search direction dk is
computed by:

dk+1 = −gk+1 + βksk (8)

βk is the conjugate gradient parameter that evaluates the performance and global conver-
gence characteristics of several conjugate gradient technique types. The nonlinear con-
jugate gradient parameters include some well-known ones like the Fletcher and Reeves
(FR)[10], conjugate descent (CD)[9], Dai and Yuan (DY) [8]. These parameters are given
by the following formulae:

βFR
k =

gTk+1gk+1

gTk gk
, βCD

k = −
gTk+1gk+1

dTk gk
βDY
k =

gTk+1gk+1

dTk yk
, (9)

More information about other conjugate gradient methods [16].
Al-Baali [1] extended this result to an inexact line search and showed that the method

generates sufficient descent direction under the strong Wolfe conditions using the con-
straint σ < 1/2. The global convergence properties of FR, DY, and CD methods with
exalt line are strong, but they are prone to taking many short steps without making
sufficient advancement to the minimum by Hager and Zhang [11].

To provide a broader context for developing conjugate gradient methods, Perry ex-
tended the classical conjugate condition to:

dTk+1yk = −(Hk+1gk+1)
T yk = −gk+1(Hk+1yk) = −gTk+1sk = 0 (10)

Many efforts have been made in few recent years to design new formulas for conjugate gra-
dient method which are not only satisfied global convergence but also improve numerical
performance for method. Remainder the conjugate gradient methods have many applica-
tion in real life In our work, we found a new formula for conjugate gradient method with
Wolfe–Powell generate a descent direction at each iteration in section 2 and the new for-
mula for conjugate gradient method which is satisfied the global convergence in section 3 .
In section 4, we present the numerical behavior of the method. The last section proposes
one conclusion.

2. Propose new conjugate gradient method:

We will discuss the new parameter choice. Now using the quadratic formula for the
objective function f(x) we have:

fk+1 = fk + sTk gk +
1

2
sTkQ(uk)sk (11)



B. A. Hassan, H. M. Sadiq / Eur. J. Pure Appl. Math, 15 (4) (2022), 2011-2021 2014

where Q(uk) is the Hessian matrix of second-order derivatives. we derivative both sides
of (11) for sk, is presented as follows:

∇fk+1 = gk +Q(uk)sk = 0 (12)

Using (5) and (12) in (11), we have:

sTkQ(uk)sk = fk − fk+1 +
1

2
sTk yk (13)

After some algebra from (11) and (13), as a result:

βk =

1
2g

T
k+1yk +

(fk−fk+1)

sTk yk
gTk+1yk

dTk yk
. (14)

If exact line search is utilized, then βk is such that:

βBV 1
k =

1
2∥gk+1∥2 + (fk−fk+1)

sTk yk
∥gk+1∥2

dTk yk
. (15)

In particular, conclude:

βBV 2
k =

1
2∥gk+1∥2 − (fk−fk+1)

sTk gk
∥gk+1∥2

−dTk gk
(16)

and

βBV 3
k =

1
2∥gk+1∥2 + (fk−fk+1)

ak∥gk∥2
∥gk+1∥2

∥gk∥2
. (17)

Thus, BV1, BV2 and BV3 are the new parameters of conjugate gradient.
Based on the above discussions, the presented algorithm is stated as follows:

Step 1: Given a starting point u1. set k = 0 and d◦ = −g◦.
Step 2: Compute βk by (15), (16) and (17).
Step 3: Compute dk by (8) and (15). If ∥gk∥ = 0, then stop.
Step 4: Evaluate αk satisfy the conditions (6) and (7).
Step 5: Update the new point by the recurrence expression (4).
Step 6: If f(uk+1) < f(uk) and ∥gk∥ < ε then stop. otherwise go to Step 2 with k = k+1.

An important feature for any minimization algorithm is the descent or the sufficient
descent property. The following theorem indicates that search direction dk satisfies descent
property of our algorithms.

Theorem 1. In the algorithm (4), (8), (15), assume that αk determined by the Wolfe
line search (6)-(7) then the direction dk+1 given by (8) is a descent direction.



B. A. Hassan, H. M. Sadiq / Eur. J. Pure Appl. Math, 15 (4) (2022), 2011-2021 2015

Proof. If k = 0, then d1 = −g1, so dT1 g1 = −∥g1∥2 < 0. suppose that dTk gk < 0 for all
k. Multiply (8) by gTk+1, will give:

dTk+1gk+1 = −∥gk+1∥2 + βBV 1
k dTk gk+1 (18)

Since
∥gk+1∥2 = βkd

T
k yk (19)

Now, put (19) in (18) we obtain:

dTk+1gk+1 = −βkd
T
k yk + βkd

T
k gk+1 = βk[−dTk yk + dTk gk+1] = βkd

T
k gk < 0 (20)

The proof is complete. The proof descent property of BV2 and BV3 is similar to proof
BV1.

3. Convergence Analysis:

In order to establish the global convergence property of the method, we make the
following standard assumptions for the objective function:

• For any initial point x1 ∈ Rn, the level set O = {x ∈ Rn\f(x) < f(x1)} is bounded.

• f(x) is continuously differentiable in a neighborhood U of Ω , and its gradient g(x)
is Lipschitz continuous, namely, there exists a constant L > 0 such that:

∥g(x)− g(y)∥ = L ∥x− y∥ ,∀x, y ∈ U. (21)

To proceed, the well-known Zoutendijk condition [22] is reviewed in the following.

Lemma 1. Suppose that Assumptions holds true. For any CG iterative algorithm defined
by (4), where dk is defined by (8), and the step-size αk is obtained by the Wolfe line search.
Then:

∞∑
k=1

(gTk dk)
2

∥dk∥2
< ∞. (22)

In the following theorem, the convergence property of new Algorithm is proved.

Theorem 2. Suppose the all assumptions holds true. Consider the sequence{gk} and {dk}
generated by the proposed method, where βk is given by (15), and αk satisfies the Wolfe
line search, then,

lim
k−→∞

inf ∥gk∥ = 0 (23)

Proof. By contradiction, suppose that (23) is not correct. Therefore, there exists a
constant ε > 0 such that:

∥gk+1∥ > ε (24)

Upon squaring both sides of (8), we obtain:



B. A. Hassan, H. M. Sadiq / Eur. J. Pure Appl. Math, 15 (4) (2022), 2011-2021 2016

∥dk+1∥2 + ∥gk+1∥2 + 2dTk+1gk+1 = (βk)
2 ∥dk∥2 (25)

Next, dividing both sides of the above inequality by (gTk+1dk+1)
2, we have:

∥dk+1∥2

(dTk+1gk+1)2
=

(βk)
2∥dk∥2

(dTk+1gk+1)2
− 2

(dTk+1gk+1)2
− ∥gk+1∥2

(dTk+1gk+1)2

=
(βk)

2∥dk∥2

(dTk+1gk+1)2
−

(
1

∥gk+1∥2
+

∥gk+1∥
(dTk+1gk+1)

)2

+
1

∥gk+1∥2

(26)

which reduces to:
∥dk+1∥2

(dTk+1gk+1)2
=

(βk)
2∥dk∥2

(dTk+1gk+1)2
+

1

∥gk+1∥2
(27)

However, from (20) we have βk =
dTk+1gk+1

dTk gk
, Substituting in (27), we obtain:

∥dk+1∥2

(dTk+1gk+1)2
=

(dTk+1gk+1)
2

(dTk gk)
2

∥dk∥2

(dTk+1gk+1)2
+

1

∥gk+1∥2

=
∥dk∥2

(dTk gk)
2
+

1

∥gk+1∥2

(28)

Notice that ∥d1∥2 = −gT1 d1 = ∥g1∥2, which implies:

∥dk+1∥2

(dTk+1gk+1)2
=

k+1∑
i=1

1

∥gi∥2
. (29)

Then we get from (29) and (24) that:

(dTk gk)
2

∥dk∥2
=

∈2

k
. (30)

Therefore:
∞∑
k=1

(gTk dk)
2

∥dk∥2
= ∞. (31)

This result contradicts (22), The proof is completed. Global convergence property of BV2,
BV3 algorithm are similar those of BV1 algorithm.

4. Numerical experiments

To illustrate the effectiveness of the suggested approach for salt-and-pepper impulse
noise, we present some numerical results in this section. Table 1 lists the experimental
outcomes. We report the number of iterations (NI), the number of function evaluations



B. A. Hassan, H. M. Sadiq / Eur. J. Pure Appl. Math, 15 (4) (2022), 2011-2021 2017

(NOF) and the evaluation indexes used in the experiments were the PSNR (peak signal
to noise ratio) see [3], which is defined as:

PSNR = 10log10
2552

1
MN

∑
i,j (u

r
i,j − u∗i,j)

2
(32)

where uri,j and u∗i,j denote the pixel values of the restored image and the original image.
We stop the iteration if the inequality:

|f(uk)− f(uk−1)|
|f(uk)|

= 10−4 and ∥f(uk)∥ = 10−4(1 + |f(uk)|) (33)

are satisfied. In the experiment, a picture that has been lost or become hazy is recovered
or recreated. Four different images are employed for the experiment, which includes,
placeLena, House, Cameraman and Elaine by employing test images in [2],[21] results
of experiment to images shown in Table (1). Images show that new Algorithm and FR
Algorithm have good performance to solve the image restoration and it can successfully
do this problem, for more details in this field see [12–15].

The numerical results show that for some situations, the suggested solution outper-
forms the FR method.

Table 1: Numerical results of FR, BV1, BV2 and BV3 algorithms.

In terms of the number of iterations and function evaluations, as well as the peak signal
to noise ratio, the recommended algorithms surpass the FR technique, as shown in Table
(1).

5. Conclusions

We presented a powerful conjugate gradient technique. In addition to meeting the
adequate descent criterion, the proposed approach is globally convergent. According to
numerical findings, the approach operates well in practice and is superior than the widely
used FR method. We also looked at our approach’s aptitude for resolving several practical
problems. In this manner, a typical issue from applications for image processing was taken
into account. We demonstrated the acceptability of the image that our approach restored.



B. A. Hassan, H. M. Sadiq / Eur. J. Pure Appl. Math, 15 (4) (2022), 2011-2021 2018

Figure 1: Demonstrates the results of algorithms FR, BV1, BV2 and BV3 of 256× 256 Lena image.

Figure 2: Demonstrates the results of algorithms FR, BV1, BV2 and BV3 of 256× 256 House image.



B. A. Hassan, H. M. Sadiq / Eur. J. Pure Appl. Math, 15 (4) (2022), 2011-2021 2019

Figure 3: Demonstrates the results of algorithms FR, BV1, BV2 and BV3 of 256× 256 Elaine image.

Figure 4: Demonstrates the results of algorithms FR, BV1, BV2 and BV3 of 256× 256 Cameraman image.



REFERENCES 2020

References

[1] Mehiddin Al-Baali. Descent property and global convergence of the fletcher—reeves
method with inexact line search. IMA Journal of Numerical Analysis, 5(1):121–124,
1985.

[2] Neculai Andrei. An unconstrained optimization test functions collection. Adv. Model.
Optim, 10(1):147–161, 2008.

[3] Alan C Bovik. Handbook of image and video processing. Academic press, 2010.

[4] Jian-Feng Cai, Raymond Chan, and Benedetta Morini. Minimization of an edge-
preserving regularization functional by conjugate gradient type methods. In Image
Processing Based on Partial Differential Equations, pages 109–122. Springer, 2007.

[5] Jian-Feng Cai, Raymond H Chan, and Mila Nikolova. Fast two-phase image deblur-
ring under impulse noise. Journal of Mathematical Imaging and Vision, 36(1):46–53,
2010.

[6] Raymond H Chan, Chung-Wa Ho, and Mila Nikolova. Salt-and-pepper noise removal
by median-type noise detectors and detail-preserving regularization. IEEE Transac-
tions on image processing, 14(10):1479–1485, 2005.

[7] Tao Chen and Hong Ren Wu. Adaptive impulse detection using center-weighted
median filters. IEEE signal processing letters, 8(1):1–3, 2001.

[8] Yu-Hong Dai and Yaxiang Yuan. A nonlinear conjugate gradient method with a
strong global convergence property. SIAM Journal on optimization, 10(1):177–182,
1999.

[9] John E Dennis Jr. Practical methods of optimization, vol. 1: Unconstrained opti-
mization (r. fletcher), 1982.

[10] Reeves Fletcher and Colin M Reeves. Function minimization by conjugate gradients.
The computer journal, 7(2):149–154, 1964.

[11] William W Hager and Hongchao Zhang. A survey of nonlinear conjugate gradient
methods. Pacific journal of Optimization, 2(1):35–58, 2006.

[12] Basim A Hassan, Fadhil Alfarag, and Snezana Djordjevic. New step sizes of the
gradient methods for unconstrained optimization problem. Italian Journal of Pure
and Applied Mathematics, page 583.

[13] Basim A Hassan and Abdulrahman R Ayoob. An adaptive quasi-newton equation
for unconstrained optimization. In 2021 2nd Information Technology To Enhance
e-learning and Other Application (IT-ELA), pages 1–5. IEEE, 2021.



REFERENCES 2021

[14] Basim A Hassan and Abdulrahman R Ayoob. On the new quasi-newton equation
for unconstrained optimization. In 2022 8th International Engineering Conference
on Sustainable Technology and Development (IEC), pages 168–172. IEEE, 2022.

[15] Basim A Hassan and Ranen M. Sulaiman. Using a new type of formula conjugate on
the gradient methods. Indonesian Journal of Electrical Engineering and Computer
Science, 27(1):86–91, 2022.

[16] P Kaelo, P Mtagulwa, and MV Thuto. A globally convergent hybrid conjugate gra-
dient method with strong wolfe conditions for unconstrained optimization. Mathe-
matical Sciences, 14(1):1–9, 2020.

[17] Morteza Kimiaei and Majid Rostami. Impulse noise removal based on new hybrid
conjugate gradient approach. Kybernetika, 52(5):791–823, 2016.

[18] Peter Mtagulwa and P Kaelo. A convergent modified hs-dy hybrid conjugate gra-
dient method for unconstrained optimization problems. Journal of Information and
Optimization Sciences, 40(1):97–113, 2019.

[19] Mila Nikolova. A variational approach to remove outliers and impulse noise. Journal
of Mathematical Imaging and Vision, 20(1):99–120, 2004.

[20] Jorge Nocedal and Stephen J Wright. Numerical optimization, 2006.

[21] Gaohang Yu, Liqun Qi, Yimin Sun, and Yi Zhou. Impulse noise removal by a non-
monotone adaptive gradient method. Signal processing, 90(10):2891–2897, 2010.

[22] G Zoutendijk. Nonlinear programming, computational methods. Integer and nonlin-
ear programming, pages 37–86, 1970.