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 and 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-618. doi: 10.1109/83.491337.

[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-585. doi: 10.1109/ICIP.2013.6738120.

[3]

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

[4]

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

[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-374. doi: 10.1051/0004-6361:20052717.

[6]

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

[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-2053. doi: 10.1088/0266-5611/22/6/008.

[8]

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

[9]

C. W. Groetsch, The Theory of Tikhonov Regularization for Fredholm Integral Equations of the First Kind, Pitman, Boston, 1984.

[10]

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

[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-436. doi: 10.6028/jres.049.044.

[12]

A. K. Jain, Fundamentals of Digital Image Processing, Prentice-Hall, Englewood Cliffs, NJ, 1989.

[13]

R. Liu and J. Jia, Reducing boundary artifacts in image deconvolution, in Proceedings of ICIP, 2008, 505-508.

[14]

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

[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-866. doi: 10.1137/S1064827598341384.

[16]

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

[17]

Y. Saad, Iterative Methods for Sparse Linear Systems, SIAM Publications, Philadelphia, 2003. doi: 10.1137/1.9780898718003.

[18]

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

[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-177. doi: 10.1007/BF01816547.

[20]

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

[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-695. doi: 10.1109/ICASSP.1985.1168354.

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-618. doi: 10.1109/83.491337.

[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-585. doi: 10.1109/ICIP.2013.6738120.

[3]

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

[4]

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

[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-374. doi: 10.1051/0004-6361:20052717.

[6]

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

[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-2053. doi: 10.1088/0266-5611/22/6/008.

[8]

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

[9]

C. W. Groetsch, The Theory of Tikhonov Regularization for Fredholm Integral Equations of the First Kind, Pitman, Boston, 1984.

[10]

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

[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-436. doi: 10.6028/jres.049.044.

[12]

A. K. Jain, Fundamentals of Digital Image Processing, Prentice-Hall, Englewood Cliffs, NJ, 1989.

[13]

R. Liu and J. Jia, Reducing boundary artifacts in image deconvolution, in Proceedings of ICIP, 2008, 505-508.

[14]

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

[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-866. doi: 10.1137/S1064827598341384.

[16]

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

[17]

Y. Saad, Iterative Methods for Sparse Linear Systems, SIAM Publications, Philadelphia, 2003. doi: 10.1137/1.9780898718003.

[18]

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

[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-177. doi: 10.1007/BF01816547.

[20]

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

[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-695. doi: 10.1109/ICASSP.1985.1168354.

[1]

Dominique Zosso, Jing An, James Stevick, Nicholas Takaki, Morgan Weiss, Liane S. Slaughter, Huan H. Cao, Paul S. Weiss, Andrea L. Bertozzi. Image segmentation with dynamic artifacts detection and bias correction. Inverse Problems and Imaging, 2017, 11 (3) : 577-600. doi: 10.3934/ipi.2017027
[2]

Jie Huang, Marco Donatelli, Raymond H. Chan. Nonstationary iterated thresholding algorithms for image deblurring. Inverse Problems and Imaging, 2013, 7 (3) : 717-736. doi: 10.3934/ipi.2013.7.717
[3]

Yuan Shen, Lei Ji. Partial convolution for total variation deblurring and denoising by new linearized alternating direction method of multipliers with extension step. Journal of Industrial and Management Optimization, 2019, 15 (1) : 159-175. doi: 10.3934/jimo.2018037
[4]

Xiao-Fei Peng, Wen Li. A new Bramble-Pasciak-like preconditioner for saddle point problems. Numerical Algebra, Control and Optimization, 2012, 2 (4) : 823-838. doi: 10.3934/naco.2012.2.823
[5]

Yang Zhang. Artifacts in the inversion of the broken ray transform in the plane. Inverse Problems and Imaging, 2020, 14 (1) : 1-26. doi: 10.3934/ipi.2019061
[6]

Christopher Goodrich, Carlos Lizama. Positivity, monotonicity, and convexity for convolution operators. Discrete and Continuous Dynamical Systems, 2020, 40 (8) : 4961-4983. doi: 10.3934/dcds.2020207
[7]

Xiangtuan Xiong, Jinmei Li, Jin Wen. Some novel linear regularization methods for a deblurring problem. Inverse Problems and Imaging, 2017, 11 (2) : 403-426. doi: 10.3934/ipi.2017019
[8]

Zhichang Guo, Wenjuan Yao, Jiebao Sun, Boying Wu. Nonlinear fractional diffusion model for deblurring images with textures. Inverse Problems and Imaging, 2019, 13 (6) : 1161-1188. doi: 10.3934/ipi.2019052
[9]

Yongjian Liu, Zhenhai Liu, Dumitru Motreanu. Differential inclusion problems with convolution and discontinuous nonlinearities. Evolution Equations and Control Theory, 2020, 9 (4) : 1057-1071. doi: 10.3934/eect.2020056
[10]

W. R. Madych. Behavior in $ L^\infty $ of convolution transforms with dilated kernels. Mathematical Foundations of Computing, 2022  doi: 10.3934/mfc.2022005
[11]

Melody Alsaker, Benjamin Bladow, Scott E. Campbell, Emma M. Kar. Automated filtering in the nonlinear Fourier domain of systematic artifacts in 2D electrical impedance tomography. Inverse Problems and Imaging, 2022, 16 (3) : 647-671. doi: 10.3934/ipi.2021066
[12]

Huimin Liang, Peixuan Weng, Yanling Tian. Bility and traveling wavefronts for a convolution model of mistletoes and birds with nonlocal diffusion. Discrete and Continuous Dynamical Systems - B, 2017, 22 (6) : 2207-2231. doi: 10.3934/dcdsb.2017093
[13]

Baoli Yin, Yang Liu, Hong Li, Zhimin Zhang. Approximation methods for the distributed order calculus using the convolution quadrature. Discrete and Continuous Dynamical Systems - B, 2021, 26 (3) : 1447-1468. doi: 10.3934/dcdsb.2020168
[14]

Hironobu Sasaki. Small data scattering for the Klein-Gordon equation with cubic convolution nonlinearity. Discrete and Continuous Dynamical Systems, 2006, 15 (3) : 973-981. doi: 10.3934/dcds.2006.15.973
[15]

Seung Jun Chang, Jae Gil Choi. Generalized transforms and generalized convolution products associated with Gaussian paths on function space. Communications on Pure and Applied Analysis, 2020, 19 (1) : 371-389. doi: 10.3934/cpaa.2020019
[16]

Jong-Shenq Guo, Ying-Chih Lin. Traveling wave solution for a lattice dynamical system with convolution type nonlinearity. Discrete and Continuous Dynamical Systems, 2012, 32 (1) : 101-124. doi: 10.3934/dcds.2012.32.101
[17]

Zhaoquan Xu, Chufen Wu. Spreading speeds for a class of non-local convolution differential equation. Discrete and Continuous Dynamical Systems - B, 2020, 25 (11) : 4479-4492. doi: 10.3934/dcdsb.2020108
[18]

Tomoyuki Tanaka, Kyouhei Wakasa. On the critical decay for the wave equation with a cubic convolution in 3D. Discrete and Continuous Dynamical Systems, 2021, 41 (10) : 4545-4566. doi: 10.3934/dcds.2021048
[19]

Nils Dabrock, Yves van Gennip. A note on "Anisotropic total variation regularized $L^1$-approximation and denoising/deblurring of 2D bar codes". Inverse Problems and Imaging, 2018, 12 (2) : 525-526. doi: 10.3934/ipi.2018022
[20]

Rustum Choksi, Yves van Gennip, Adam Oberman. Anisotropic total variation regularized $L^1$ approximation and denoising/deblurring of 2D bar codes. Inverse Problems and Imaging, 2011, 5 (3) : 591-617. doi: 10.3934/ipi.2011.5.591

2020 Impact Factor: 1.639

Tools

Metrics

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

Other articles
by authors

[Back to Top]

Copyright © 2022 American Institute of Mathematical Sciences | Privacy Policy