Kronecker product approximations for image restoration with whole-sample symmetric boundary conditions. (English) Zbl 1239.94011

Summary: Reflexive boundary conditions (BCs) assume that the array values outside the viewable region are given by a symmetry of the array values inside. The reflection guarantees the continuity of the image. In fact, there are usually two choices for the symmetry: symmetry around the meshpoint and symmetry around the midpoint. The first is called whole-sample symmetry in signal and image processing, the second is half-sample. Many researchers have developed some fast algorithms for the problems of image restoration with the half-sample symmetric BCs over the years. However, little attention has been given to the whole-sample symmetric BCs. In this paper, we consider the use of the whole-sample symmetric boundary conditions in image restoration. The blurring matrices constructed from the point spread functions (PSFs) for the BCs have block Toeplitz-plus-PseudoHankel with Toeplitz-plus-PseudoHankel blocks structures. Recently, regardless of symmetric properties of the PSFs, a technique of Kronecker product approximations was successfully applied to restore images with the zero BCs, half-sample symmetric BCs and anti-reflexive BCs, respectively. All these results extend quite naturally to the whole-sample symmetric BCs, since the resulting matrices have similar structures. It is interesting to note that when the size of the true PSF is small, the computational complexity of the algorithm obtained for the Kronecker product approximation of the resulting matrix in this paper is very small. It is clear that in this case all calculations in the algorithm are implemented only at the upper left corner submatrices of the big matrices. Finally, detailed experimental results reporting the performance of the proposed algorithm are presented.


94A08 Image processing (compression, reconstruction, etc.) in information and communication theory


Full Text: DOI


[1] Aghdasi, F.; Ward, R., Reduction of boundary artifacts in image restoration, IEEE trans. image process., 5, 4, 611-618, (1996)
[2] Andrew, H.; Hunt, B., Digital image restoration, (1977), Prentice-Hall Englewood Cliffs, NJ · Zbl 0379.62098
[3] Banham, M.; Katsaggelos, A., Digital image restoration, IEEE signal process. mag., 14, 2, 24-41, (1997)
[4] Bonettini, S.; Ruggiero, V., An alternating extragradient method for total variation-based image restoration from Poisson data, Inverse probl., 27, 095001, (2011), 26 pp · Zbl 1252.94008
[5] Boukerrou, K.; Kurz, L., Suppression of “salt and pepper” noise based on youden designs, Inform. sci., 110, 217-235, (1998)
[6] Cai, J.F.; Osher, S.; Shen, Z.W., Split Bregman methods and frame based image restoration, Multiscale model. simul., 8, 2, 337-369, (2010) · Zbl 1189.94014
[7] Capizzano, S.S., A note on anti-reflective boundary conditions and fast deblurring models, SIAM J. sci. comput., 25, 1307-1325, (2003) · Zbl 1062.65152
[8] Chan, T.F.; Shen, J., Image processing and analysis: variational, PDE, wavelet, and stochastic methods, (2005), SIAM Philadelphia · Zbl 1095.68127
[9] F. Chen, L. Yu, Image deblurring with odd symmetry discrete Neumann boundary condition, in: Proceedings of the Sixth International Conference on Machine Learning and Cybernetics, Hong Kong, 2007.
[10] Christiansen, M.; Hanke, M., Deblurring methods using antireflective boundary conditions, SIAM J. sci. comput., 30, 2, 855-872, (2008) · Zbl 1167.65361
[11] Chung, J.; Nagy, J.G., An efficient iterative approach for large-scale separable nonlinear inverse problems, SIAM J. sci. comput., 31, 6, 4654-4674, (2010) · Zbl 1205.65160
[12] Donatelli, M.; Capizzano, S.S., Anti-reflective boundary conditions and re-blurring, Inverse probl., 21, 169-182, (2005) · Zbl 1088.94510
[13] Dong, Y.; Hintermüller, M.; Rincon-Camacho, M.M., Automated regularization parameter selection in multi-scale total variation models for image restoration, J. math. imaging vis., 40, 82-104, (2011) · Zbl 1255.68230
[14] Dowski, E.; Cathey, W., Extended depth of field through wavefront coding, Appl. optics, 34, 1859-1866, (1995)
[15] Engl, H.; Hanke, M.; Neubauer, A., Regularization of inverse problems, (1996), Kluwer Academic Publishers The Netherlands · Zbl 0859.65054
[16] Fan, Y.W.; Nagy, J.G., Synthetic boundary conditions for image deblurring, Linear algebra appl., 434, 11, 2244-2268, (2011) · Zbl 1210.94013
[17] González, A.I.; Graña, M.; Cabello, J.R.; D’Anjou, A.; Albizuri, F.X., Experimental results of an evolution-based adaptation strategy for VQ image filtering, Inform. sci., 176, 2988-3010, (2006)
[18] Hamidi, A.E.; Ménard, M.; Lugiez, M.; Ghannam, C., Weighted and extended total variation for image restoration and decomposition, Pattern recognit., 43, 1564-1576, (2010) · Zbl 1191.68567
[19] Hanke, M.; Nagy, J.G.; Vogel, C.R., Quasi-Newton approach to nonnegative image restorations, Linear algebra appl., 316, 223-236, (2000) · Zbl 0960.65071
[20] Hansen, P.C., Rank defficient and discrete ill-posed problems: numerical aspects of linear inversion, (1997), SIAM Philadelphia
[21] Hansen, P.C.; Nagy, J.G.; O’Leary, D.P., Deblurring images: matrices, spectra, and filtering, (2006), SIAM Philadelphia · Zbl 1112.68127
[22] Hansen, P.C., Discrete inverse problems: insight and algorithms, (2010), SIAM Philadelphia · Zbl 1197.65054
[23] Jeon, G.; Anisetti, M.; Bellandi, V.; Damiani, E.; Jeong, J., Designing of a type-2 fuzzy logic filter for improving edge-preserving restoration of interlaced-to-progressive conversion, Inform. sci., 179, 13, 2194-2207, (2009)
[24] J. Kamm, Singular value decomposition-based methods for signal and image processing, Ph. D. Thesis, Southern Methodist University, USA, 1998.
[25] Kamm, J.; Nagy, J.G., Optimal Kronecker product approximation of block Toeplitz matrices, SIAM J. matrix analysis appl., 22, 155-172, (2000) · Zbl 0969.65033
[26] Lagendijk, R.L.; Biemond, J.; Boekee, D.E., Identification and restoration of noisy blurred images using the expectation-maximization algorithm, IEEE trans. acoust. speech signal process., 38, 7, 1180-1191, (1990) · Zbl 0713.93060
[27] Lay, K.T.; Katsaggelos, A.K., Identification and restoration based on the expectation-maximization algorithm, Opt. eng., 29, 5, 436-445, (1990)
[28] Li, X., Fine-granularity and spatially-adaptive regularization for projection-based image deblurring, IEEE trans. image process., 20, 4, 971-983, (2011) · Zbl 1372.94152
[29] Lim, C.L.; Honarvar, B.; Thung, K.H.; Paramesran, R., Fast computation of exact Zernike moments using cascaded digital filters, Inform. sci., 181, 17, 3638-3651, (2011)
[30] Lin, T.C., A new adaptive center weighted Median filter for suppressing impulsive noise in images, Inform. sci., 177, 1073-1087, (2007)
[31] Lin, T.C., Switching-based filter based on dempsters combination rule for image processing, Inform. sci., 180, 4892-4908, (2010)
[32] Loan, C.F.V.; Pitsianis, N.P., Approximation with Kronecker products, (), 293-314 · Zbl 0813.65078
[33] Martucci, S., Symmetric convolution and the discrete sine and cosine transforms, IEEE trans. signal process., 42, 1038-1051, (1994)
[34] Michailovich, O.V., An iterative shrinkage approach to total-variation image restoration, IEEE trans. image process., 20, 5, 1281-1299, (2011) · Zbl 1372.94178
[35] Nagy, J.G.; Ng, M.K.; Perrone, L., Kronecker product approximations for image restoration with reflexive boundary conditions, SIAM J. matrix anal. appl., 25, 829-841, (2003) · Zbl 1068.65055
[36] Nagy, J.G.; Palmer, K.; Perrone, L., Iterative methods for image deblurring: a Matlab object-oriented approach, Numer. algor., 36, 73-93, (2004) · Zbl 1048.65039
[37] Ng, M.K.; Chan, R.; Tang, W., A fast algorithm for deblurring models with Neumann boundary conditions, SIAM J. sci. comput., 21, 851-866, (2000) · Zbl 0951.65038
[38] Ng, M.K.; Weiss, P.; Yuan, X., Solving constrained total-variation image restoration and reconstruction problems via alternating direction methods, SIAM J. sci. comput., 32, 5, 2710-2736, (2010) · Zbl 1217.65071
[39] Nobuhara, H.; Bede, B.; Hirota, K., On various eigen fuzzy sets and their application to image reconstruction, Inform. sci., 176, 2988-3010, (2006) · Zbl 1102.68697
[40] Pang, Z.; Yang, Y., A projected gradient algorithm based on the augmented Lagrangian strategy for image restoration and texture extraction, Image vision comput., 29, 117-126, (2011)
[41] Perrone, L., Kronecker product approximations for image restoration with anti-reflective boundary conditions, Numer. lin. alg. appl., 13, 1-22, (2006) · Zbl 1174.94309
[42] N.P. Pitsianis, The Kronecker product in approximation and fast transform generation, Ph. D. Thesis, Cornell University, Ithaca, NY, 1997.
[43] Reeves, S.J.; Mersereau, R.M., Blur identification by the method of generalized cross-validation, IEEE trans. image process., 1, 7, 301-311, (1992)
[44] Rojas, M.; Steihaug, T., An interior-point trust-region-based method for large-scale non-negative regularization, Inverse probl., 18, 1291-1307, (2002) · Zbl 1015.90062
[45] Shaked, E.; Michailovich, O., Iterative shrinkage approach to restoration of optical imagery, IEEE trans. image process., 20, 2, 405-416, (2011) · Zbl 1372.94231
[46] Strakhov, V.N.; Vorontsov, S.V., Digital image deblurring with SOR, Inverse probl., 24, 2, p.02502, (2008) · Zbl 1278.65031
[47] Strang, G., The discrete cosine transform, SIAM rev., 41, 135-147, (1999) · Zbl 0939.42021
[48] Vogel, C.R., Computational methods for inverse problems, (2002), SIAM Philadelphia · Zbl 1008.65103
[49] Wang, Z.; Bovik, A.C., Mean squared error: love it or leave it? A new look at signal fidelity measures, IEEE signal process. mag., 26, 1, 98-117, (2009)
[50] Zhang, W.; Ye, Z.; Zhao, T.; Chen, Y.; Yu, F., Point spread function characteristics analysis of the wavefront coding system, Optics exp., 15, 4, 1543-1552, (2007)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.