Kybernetika 52 no. 5, 791-823, 2016

Impulse noise removal based on new hybrid conjugate gradient approach

Morteza Kimiaei and Majid RostamiDOI: 10.14736/kyb-2016-5-0791


Image denoising is a fundamental problem in image processing operations. In this paper, we present a two-phase scheme for the impulse noise removal. In the first phase, noise candidates are identified by the adaptive median filter (AMF) for salt-and-pepper noise. In the second phase, a new hybrid conjugate gradient method is used to minimize an edge-preserving regularization functional. The second phase of our algorithm inherits advantages of both Dai-Yuan (DY) and Hager-Zhang (HZ) conjugate gradient methods to produce the new direction. The descent property of new direction in each iteration and the global convergence results are established under some standard assumptions. Furthermore, we investigate some conjugate gradient algorithms and the complexity analysis of theirs. Numerical experiments are given to illustrate the efficiency of the new hybrid conjugate gradient (HCGN) method for impulse noise removal.


image processing, unconstrained optimization, conjugate gradient method, impulse noise, Wolfe conditions, complexity analysis


90C30, 90C25, 90C90, 68U10, 03D15


  1. J. Barzilai and J. M. Borwein: Two point step size gradient method. IMA J. Numer. Anal. 8 (1988), 141-148.   DOI:10.1093/imanum/8.1.141
  2. M. Bertalmio, L. A. Vese, G. Sapiro and S. Osher: Simultaneous structure and texture image inpainting. IEEE Trans. Image Processing. 12 (2003), 8, 882-889.   DOI:10.1109/tip.2003.815261
  3. J. F. Cai, R. H. Chan and C. D. Fiore: Minimization of a detail-preserving regularization functional for impulse noise removal. J. Math. Imaging Vision. 27 (2007), 79-91.   DOI:10.1007/s10851-007-0027-4
  4. J. F. Cai, R. H. Chan and B. Morini: Minimization of an edge-preserving regularization functional by conjugate gradient type methods, image processing based on partial differential equations. In: Mathematics and Visualization, Springer, Berlin Heidelberg 2007, pp. 109-122.   DOI:10.1007/978-3-540-33267-1_7
  5. J. F. Cai, R. H. Chan and M. Nikolova: Two-phase approach for deblurring images corrupted by impulse plus Gaussian noise. Inverse Problem and Imaging. 2 (2008), 187-204.   DOI:10.3934/ipi.2008.2.187
  6. J. F. Cai, R. H. Chan and M. Nikolova: Fast two-phase image deblurring under impulse noise. J. Math. Imaging and Vision 36 (2010), 46-53.   DOI:10.1007/s10851-009-0169-7
  7. R. Chan, C. Hu and M. Nikolova: Iterative procedure for removing random-valued impulse noise. IEEE Signal Process. Lett. 11 (2004), 12, 921-924.   DOI:10.1109/lsp.2004.838190
  8. R. H. Chan, C. W. Ho and M. Nikolova: Salt-and-pepper noise removal by median-type noise detectors and detail-preserving regularization. IEEE Trans. Image Process. 14 (2005), 1479-1485.   DOI:10.1109/tip.2005.852196
  9. T. F. Chan, J. Shen and H. Zhou: Total variation wavelet inpainting. J. Math. Imaging Vision 25 (2006), 107-125.   DOI:10.1007/s10851-006-5257-3
  10. T. Chen and H. R. Wu: Adaptive impulse detection using center-weighted median filters. IEEE Signal Process. Lett. 8 (2001), 1-3.   DOI:10.1109/97.889633
  11. Y. H. Dai and Q. Ni: Testing different conjugate gradient methods for large-scale unconstrained optimization. J. Comput. Math. 21 (2003), 311-320.   CrossRef
  12. Y. H. Dai and Y. Yuan: A nonlinear conjugate gradient method with a strong global convergence property. IEEE SIAM J. Optim. 10 (1999), 177-182.   DOI:10.1137/s1052623497318992
  13. E. D. Dolan and J. J. Moré: Benchmarking optimization software with performance profiles. Math. Program. 91 (2002), 2, 201-213.   DOI:10.1007/s101070100263
  14. R. Fletcher and C. Reeves: Function minimization by conjugate gradients. Comput. J. 7 (1964), 149-154.   DOI:10.1093/comjnl/7.2.149
  15. J. C. Gilbert and J. Nocedal: Global convergence properties of conjugate gradient methods for optimization. SIAM J. Optim. 2 (1992), 21-42.   DOI:10.1137/0802003
  16. W. W. Hager and H. Zhang: A new conjugate gradient method with guaranteed descent and an efficient line search. SIAM J. Optim. 16 (2005), 170-192.   DOI:10.1137/030601880
  17. W. W. Hager and H. Zhang: A survey of nonlinear conjugate gradeint methods.$\sim$ hager, 2005.   CrossRef
  18. M. R. Hestenes and E. L. Stiefel: Methods of conjugate gradients for solving linear systems. J. Research Nat. Bur. Standards 49 (1952), 409-436.   DOI:10.6028/jres.049.044
  19. H. Hwang and R. A. Haddad: Adaptive median filters: New algorithms and results. IEEE Trans. Image Process. 4 (1995), 499-502.   DOI:10.1109/83.370679
  20. D. C. Liu and J. Nocedal: On the limited memory BFGS method for large scale optimization. Math. Program. 45 (1989), 503-528.   DOI:10.1007/bf01589116
  21. M. Nikolova: A variational approach to remove outliers and impulse noise. J. Math. Imaging Vision 20 (2004), 1-2, 99-120. Special issue on mathematics and image analysis.   DOI:10.1023/b:jmiv.0000011920.58935.9c
  22. J. Nocedal: Updating quasi-Newton matrices with limited storage. Math. Comput. 35 (1980), 773-782.   DOI:10.1090/s0025-5718-1980-0572855-7
  23. J. Nocedal and S. J. Wright: Numerical Optimization. Springer, New York 2006.   DOI:10.1007/978-0-387-40065-5
  24. B. T. Polyak: The conjugate gradient method in extreme problems. USSR Comp. Math. Math. Phys. 9 (1969), 94-112.   DOI:10.1016/0041-5553(69)90035-4
  25. E. Polyak and G. Ribière: Note sur la convergence de directions conjugées. Francaise Informat Recherche Opertionelle, 3e Année 16 (1969), 35-43.   CrossRef
  26. M. J. D. Powell: Restart procedures of the conjugate gradient method. Math. Prog. 2 (1977), 241-254.   CrossRef
  27. M. J. D. Powell: Nonconvex minimization calculations and the conjugate gradient method. In: Numerical Analysis (Dundee, 1983), Lecture Notes in Mathematics, Springer-Verlag, Berlin 1066 (1984), pp. 122-141.   CrossRef
  28. G. Yua, J. Huanga and Y. Zhou: A descent spectral conjugate gradient method for impulse noise removal. Appl. Math. Lett. 23 (2010), 555-560.   CrossRef
  29. G. Yu, L. Qi, Y. Sun and Y. Zhou: Impulse noise removal by a nonmonotone adaptive gradient method. Signal Process. 90 (2010), 2891-2897.   CrossRef
  30. G. Zoutendijk: Nonlinear programming computational methods. In: Integer and Nonlinear Programming (J. Abadie, ed.), North-Holland, Amsterdam 1970, pp. 37-86.   CrossRef