American Institute of Mathematical Sciences

Advanced
  • Previous Article
    Approximate marginalization of absorption and scattering in fluorescence diffuse optical tomography
  • IPI Home
  • This Issue
  • Next Article
    A divide-alternate-and-conquer approach for localization and shape identification of multiple scatterers in heterogeneous media using dynamic XFEM
February  2016, 10(1): 195-225. doi: 10.3934/ipi.2016.10.195

Preconditioned conjugate gradient method for boundary artifact-free image deblurring

Nam-Yong Lee 1, and  Bradley J. Lucier 2,

1. 

Department of Applied Mathematics, Inje University, Gimhae, Gyeongnam 621-749, South Korea
2. 

Department of Mathematics, Purdue University, West Lafayette, IN47906, United States

Received  May 2013 Revised  September 2015 Published  February 2016

Several methods have been proposed to reduce boundary artifacts in image deblurring. Some of those methods impose certain assumptions on image pixels outside the field-of-view; the most important of these assume reflective or anti-reflective boundary conditions. Boundary condition methods, including reflective and anti-reflective ones, however, often fail to reduce boundary artifacts, and, in some cases, generate their own artifacts, especially when the image to be deblurred does not accurately satisfy the imposed condition. To overcome these difficulties, we suggest using free boundary conditions, which do not impose any restrictions on image pixels outside the field-of-view, and preconditioned conjugate gradient methods, where preconditioners are designed to compensate for the non-uniformity in contributions from image pixels to the observation. Our simulation studies show that the proposed method outperforms reflective and anti-reflective boundary condition methods in removing boundary artifacts. The simulation studies also show that the proposed method can be applicable to arbitrarily shaped images and has the benefit of recovering damaged parts in blurred images.
Keywords: Boundary artifacts, image deblurring, convolution, preconditioner..
Mathematics Subject Classification: Primary: 65F08, 65K10, 68U1.
Citation: Nam-Yong Lee, Bradley J. Lucier. Preconditioned conjugate gradient method for boundary artifact-free image deblurring. Inverse Problems & Imaging, 2016, 10 (1) : 195-225. doi: 10.3934/ipi.2016.10.195
References:
[1]

F. Aghdasi and R. K. Ward, Reduction of boundary artifacts in image restoration,, IEEE Trans. Image Processing, 5 (1996), 611.  doi: 10.1109/83.491337.  Google Scholar

[2]

M. S. C. Almeida and M. A. T. Figueiredo, Frame-based image deblurring with unknown boundary conditions using the alternating direction method of multipliers,, in Proceedings of ICIP, (2013), 582.  doi: 10.1109/ICIP.2013.6738120.  Google Scholar

[3]

A. Arićo, M. Donatelli and S. Serra-Capizzano, Spectral analysis of the anti-reflective algebra,, Linear Algebra Appl., 428 (2008), 657.  doi: 10.1016/j.laa.2007.08.020.  Google Scholar

[4]

M. Bertalmio, G. Sapiro, V. Caselles and C. Ballester, Image inpainting,, SIGGRAPH, (2000), 417.  doi: 10.1145/344779.344972.  Google Scholar

[5]

M. Bertero and P. Boccacci, A simple method for the reduction of boundary effects in the Richardson-Lucy approach to image deconvolution,, Astron. Astrophys., 437 (2005), 369.  doi: 10.1051/0004-6361:20052717.  Google Scholar

[6]

D. Calvetti, J. P. Kaipio and E. Someralo, Aristotelian prior boundary conditions,, Inter. J. Mathematics and Computer Science, 1 (2006), 63.   Google Scholar

[7]

M. Donatelli, C. Estatico, A. Martinelli and S. Serra-Capizzano, Improved image deblurring with anti-reflective boundary conditions and re-blurring,, Inverse Problems, 22 (2006), 2035.  doi: 10.1088/0266-5611/22/6/008.  Google Scholar

[8]

Y. W. Fan and J. G. Nagy, Synthetic boundary conditions for image deblurring,, Linear Algebra Appl., 434 (2011), 2244.  doi: 10.1016/j.laa.2009.12.021.  Google Scholar

[9]

C. W. Groetsch, The Theory of Tikhonov Regularization for Fredholm Integral Equations of the First Kind,, Pitman, (1984).   Google Scholar

[10]

M. Hanke and P. C. Hansen, Regularization methods for large-scale problems,, Surveys Math. Indust., 3 (1993), 253.   Google Scholar

[11]

M. R. Hestenes and E. Stiefel, Methods of conjugate gradients for solving linear systems,, Journal of Research of the National Bureau of Standards, 49 (1952), 409.  doi: 10.6028/jres.049.044.  Google Scholar

[12]

A. K. Jain, Fundamentals of Digital Image Processing,, Prentice-Hall, (1989).   Google Scholar

[13]

R. Liu and J. Jia, Reducing boundary artifacts in image deconvolution,, in Proceedings of ICIP, (2008), 505.   Google Scholar

[14]

L. B. Lucy, An iterative techniques for the rectification of observed distributions,, Astronomical Journal, 79 (1974), 745.  doi: 10.1086/111605.  Google Scholar

[15]

M. K. Ng, R. H. Chan and W.-C. Tang, A fast algorithm for deblurring models with Neumann boundary conditions,, SIAM J. Sci. Comput., 21 (1999), 851.  doi: 10.1137/S1064827598341384.  Google Scholar

[16]

W. H. Richardson, Bayesian-based iterative method of image restoration,, J. Opt. Soc. Am., 62 (1972), 55.  doi: 10.1364/JOSA.62.000055.  Google Scholar

[17]

Y. Saad, Iterative Methods for Sparse Linear Systems,, SIAM Publications, (2003).  doi: 10.1137/1.9780898718003.  Google Scholar

[18]

S. Serra-Capizzano, A note on anti-reflective boundary conditions and fast deblurring models,, SIAM J. Sci. Comput., 25 (2003), 1307.  doi: 10.1137/S1064827502410244.  Google Scholar

[19]

A. M. Tekalp and M. I. Sezan, Quantitative analysis of artifacts in linear space-invariant image restoration,, Multidimensional Syst. Signal Processing, 1 (1990), 143.  doi: 10.1007/BF01816547.  Google Scholar

[20]

R. Vio, J. Bardsley, M. Donatelli and W. Wamsteker, Dealing with edge effects least-squares image deconvolution problems,, Astron. Astrophys, 442 (2005), 397.  doi: 10.1051/0004-6361:20053414.  Google Scholar

[21]

J. W. Woods, J. Biemond and A. M. Kekalp, Boundary value problem in image restoration,, Proc. Sixth Int. Conf. Acoust. Speech Signal Processing, 10 (1985), 692.  doi: 10.1109/ICASSP.1985.1168354.  Google Scholar

show all references

References:
[1]

F. Aghdasi and R. K. Ward, Reduction of boundary artifacts in image restoration,, IEEE Trans. Image Processing, 5 (1996), 611.  doi: 10.1109/83.491337.  Google Scholar

[2]

M. S. C. Almeida and M. A. T. Figueiredo, Frame-based image deblurring with unknown boundary conditions using the alternating direction method of multipliers,, in Proceedings of ICIP, (2013), 582.  doi: 10.1109/ICIP.2013.6738120.  Google Scholar

[3]

A. Arićo, M. Donatelli and S. Serra-Capizzano, Spectral analysis of the anti-reflective algebra,, Linear Algebra Appl., 428 (2008), 657.  doi: 10.1016/j.laa.2007.08.020.  Google Scholar

[4]

M. Bertalmio, G. Sapiro, V. Caselles and C. Ballester, Image inpainting,, SIGGRAPH, (2000), 417.  doi: 10.1145/344779.344972.  Google Scholar

[5]

M. Bertero and P. Boccacci, A simple method for the reduction of boundary effects in the Richardson-Lucy approach to image deconvolution,, Astron. Astrophys., 437 (2005), 369.  doi: 10.1051/0004-6361:20052717.  Google Scholar

[6]

D. Calvetti, J. P. Kaipio and E. Someralo, Aristotelian prior boundary conditions,, Inter. J. Mathematics and Computer Science, 1 (2006), 63.   Google Scholar

[7]

M. Donatelli, C. Estatico, A. Martinelli and S. Serra-Capizzano, Improved image deblurring with anti-reflective boundary conditions and re-blurring,, Inverse Problems, 22 (2006), 2035.  doi: 10.1088/0266-5611/22/6/008.  Google Scholar

[8]

Y. W. Fan and J. G. Nagy, Synthetic boundary conditions for image deblurring,, Linear Algebra Appl., 434 (2011), 2244.  doi: 10.1016/j.laa.2009.12.021.  Google Scholar

[9]

C. W. Groetsch, The Theory of Tikhonov Regularization for Fredholm Integral Equations of the First Kind,, Pitman, (1984).   Google Scholar

[10]

M. Hanke and P. C. Hansen, Regularization methods for large-scale problems,, Surveys Math. Indust., 3 (1993), 253.   Google Scholar

[11]

M. R. Hestenes and E. Stiefel, Methods of conjugate gradients for solving linear systems,, Journal of Research of the National Bureau of Standards, 49 (1952), 409.  doi: 10.6028/jres.049.044.  Google Scholar

[12]

A. K. Jain, Fundamentals of Digital Image Processing,, Prentice-Hall, (1989).   Google Scholar

[13]

R. Liu and J. Jia, Reducing boundary artifacts in image deconvolution,, in Proceedings of ICIP, (2008), 505.   Google Scholar

[14]

L. B. Lucy, An iterative techniques for the rectification of observed distributions,, Astronomical Journal, 79 (1974), 745.  doi: 10.1086/111605.  Google Scholar

[15]

M. K. Ng, R. H. Chan and W.-C. Tang, A fast algorithm for deblurring models with Neumann boundary conditions,, SIAM J. Sci. Comput., 21 (1999), 851.  doi: 10.1137/S1064827598341384.  Google Scholar

[16]

W. H. Richardson, Bayesian-based iterative method of image restoration,, J. Opt. Soc. Am., 62 (1972), 55.  doi: 10.1364/JOSA.62.000055.  Google Scholar

[17]

Y. Saad, Iterative Methods for Sparse Linear Systems,, SIAM Publications, (2003).  doi: 10.1137/1.9780898718003.  Google Scholar

[18]

S. Serra-Capizzano, A note on anti-reflective boundary conditions and fast deblurring models,, SIAM J. Sci. Comput., 25 (2003), 1307.  doi: 10.1137/S1064827502410244.  Google Scholar

[19]

A. M. Tekalp and M. I. Sezan, Quantitative analysis of artifacts in linear space-invariant image restoration,, Multidimensional Syst. Signal Processing, 1 (1990), 143.  doi: 10.1007/BF01816547.  Google Scholar

[20]

R. Vio, J. Bardsley, M. Donatelli and W. Wamsteker, Dealing with edge effects least-squares image deconvolution problems,, Astron. Astrophys, 442 (2005), 397.  doi: 10.1051/0004-6361:20053414.  Google Scholar

[21]

J. W. Woods, J. Biemond and A. M. Kekalp, Boundary value problem in image restoration,, Proc. Sixth Int. Conf. Acoust. Speech Signal Processing, 10 (1985), 692.  doi: 10.1109/ICASSP.1985.1168354.  Google Scholar

[1]

Mehdi Bastani, Davod Khojasteh Salkuyeh. On the GSOR iteration method for image restoration. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 27-43. doi: 10.3934/naco.2020013
[2]

Abdelghafour Atlas, Mostafa Bendahmane, Fahd Karami, Driss Meskine, Omar Oubbih. A nonlinear fractional reaction-diffusion system applied to image denoising and decomposition. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020321
[3]

Jia Cai, Guanglong Xu, Zhensheng Hu. Sketch-based image retrieval via CAT loss with elastic net regularization. Mathematical Foundations of Computing, 2020, 3 (4) : 219-227. doi: 10.3934/mfc.2020013
[4]

Marco Ghimenti, Anna Maria Micheletti. Compactness results for linearly perturbed Yamabe problem on manifolds with boundary. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020453
[5]

Antoine Benoit. Weak well-posedness of hyperbolic boundary value problems in a strip: when instabilities do not reflect the geometry. Communications on Pure & Applied Analysis, 2020, 19 (12) : 5475-5486. doi: 10.3934/cpaa.2020248
[6]

Shenglan Xie, Maoan Han, Peng Zhu. A posteriori error estimate of weak Galerkin fem for second order elliptic problem with mixed boundary condition. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020340
[7]

Mehdi Badsi. Collisional sheath solutions of a bi-species Vlasov-Poisson-Boltzmann boundary value problem. Kinetic & Related Models, , () : -. doi: 10.3934/krm.2020052
[8]

Mokhtar Bouloudene, Manar A. Alqudah, Fahd Jarad, Yassine Adjabi, Thabet Abdeljawad. Nonlinear singular $ p $ -Laplacian boundary value problems in the frame of conformable derivative. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020442
[9]

Mengni Li. Global regularity for a class of Monge-Ampère type equations with nonzero boundary conditions. Communications on Pure & Applied Analysis, 2021, 20 (1) : 301-317. doi: 10.3934/cpaa.2020267
[10]

Cheng Peng, Zhaohui Tang, Weihua Gui, Qing Chen, Jing He. A bidirectional weighted boundary distance algorithm for time series similarity computation based on optimized sliding window size. Journal of Industrial & Management Optimization, 2021, 17 (1) : 205-220. doi: 10.3934/jimo.2019107

2019 Impact Factor: 1.373

Tools

Metrics

  • PDF downloads (62)
  • HTML views (0)
  • Cited by (0)

Other articles
by authors

[Back to Top]

Copyright © 2020 American Institute of Mathematical Sciences