Efficient algorithms for mixed noise removal via nonlocal low-rank regularization

Ashley Prater-Bennette; Minghao Rostami; Lixin Shen; Erin E. Tripp; Jiangyu Yu

doi:10.3934/ipi.2025021

Article Contents

2026, Volume 20: 156-180. Doi: 10.3934/ipi.2025021

This volume Previous Article On the transmission eigenvalues for scattering by a clamped planar region Next Article A direct comparison of fast 3D CGO-based algorithms for electrical impedance tomography: $ \mathbf{t^{exp}} $ and $ \mathbf{t^0} $ vs. the "$ \mathbf{t^B} $ method" on simulated and experimental data

Efficient algorithms for mixed noise removal via nonlocal low-rank regularization

1.
Air Force Research Laboratory, Rome, NY 13441, USA
2.
SUNY at Binghamton, Binghamton, NY 13902, USA
3.
Syracuse University, Syracuse, NY 13244, USA
4.
Hamilton College, Clinton, NY 13323, USA

^*Corresponding author: Lixin Shen
^*Corresponding author: Lixin Shen

Received: July 2024

Revised: March 2025

Early access: May 15, 2025

Published online: May 15, 2025

The work of Rostami was supported in part by the National Science Foundation (NSF) under grants DMS-1818833 and DMS-2146191 (CAREER). The work of L. Shen was supported in part by the National Science Foundation under grant DMS-2208385.

Abstract / Introduction Full Text(HTML) Figure(10) / Table(4) Related Papers Cited by

Abstract

This paper addresses an image denoising problem where observed images are contaminated by a mix of Gaussian and impulse noise. The proposed approach involves solving an optimization problem with an objective function that combines a convex content-dependent fidelity term and a nonlocal low-rank regularization term. Both terms are constructed using patch matrices formed from similar patches of the image. Based on the unique properties of these terms, we propose two different strategies to efficiently solve the problem. We also provide convergence analysis for both methods. Our numerical experiments demonstrate that the proposed two-phase approach performs well in terms of three quantitative metrics: peak signal-to-noise ratio (PSNR), structural similarity (SSIM), and feature similarity (FSIM), as well as in the visual quality of the restored images.

Keywords:

Impulse noise removal,
low-rank regularization,
proximal difference-of-convex algorithm,
forward-backward splitting algorithm.

Mathematics Subject Classification: Primary: 68U10, 94A08, 90C26; Secondary: 15A03, 46N10, 65F22.

Citation:

Full Text(HTML)

Figure 1. The testing images (a) "Barbara", (b) "House", (c) "Boat", and (c) "Baboon"

Download: Full-size image PowerPoint slide

Figure 2. The PSNR values of the denoised images from salt and pepper noise by various methods for the images of (a) "Barbara", (b) "House" and (c) "Boat"

Download: Full-size image PowerPoint slide

Figure 3. (a) The noisy "Barbara" image with Gaussian noise ($ \sigma = 20 $) and salt-and-pepper noise at level 50. The denoised images are obtained using (b) NLR-TP, (c) Algorithm 1-S1, and (d) Algorithm 1-S2. The second row displays the corresponding zoomed-in regions of the images in the first row

Download: Full-size image PowerPoint slide

Figure 4. (a) The noisy "House" image with Gaussian noise ($ \sigma = 20 $) and salt-and-pepper noise at level 50. The denoised images are obtained using (b) NLR-TP, (c) Algorithm 1-S1, and (d) Algorithm 1-S2. The second row displays the corresponding zoomed-in regions of the images in the first row

Download: Full-size image PowerPoint slide

Figure 5. (a) The noisy "Boat" image with Gaussian noise ($ \sigma = 10 $) and salt-and-pepper noise at level 50. The denoised images are obtained using (b) NLR-TP, (c) Algorithm 1-S1, and (d) Algorithm 1-S2. The second row displays the corresponding zoomed-in regions of the images in the first row

Download: Full-size image PowerPoint slide

Figure 6. The PSNR values of the denoised images from random valued noise by various methods for the images of (a) "Barbara", (b) "House" and (c) "Boat"

Download: Full-size image PowerPoint slide

Figure 7. (a) The noisy "Barbara" image with Gaussian noise ($ \sigma = 25 $) and random-valued impluse noise at level 45. The denoised images are obtained using (b) NLR-TP, (c) Algorithm 1-S1, and (d) Algorithm 1-S2. The second row displays the corresponding zoomed-in regions of the images in the first row

Download: Full-size image PowerPoint slide

Figure 8. (a) The noisy "House" image with Gaussian noise ($ \sigma = 25 $) and random-valued impluse noise at level 45. The denoised images are obtained using (b) NLR-TP, (c) Algorithm 1-S1, and (d) Algorithm 1-S2. The second row displays the corresponding zoomed-in regions of the images in the first row

Download: Full-size image PowerPoint slide

Figure 9. (a) The noisy "Boat" image with Gaussian noise ($ \sigma = 25 $) and random-valued impluse noise at level 45. The denoised images are obtained using (b) NLR-TP, (c) Algorithm 1-S1, and (d) Algorithm 1-S2. The second row displays the corresponding zoomed-in regions of the images in the first row

Download: Full-size image PowerPoint slide

Figure 10. (a) The noisy "Baboon" image with Gaussian noise ($ \sigma = 20 $) and salt-and-pepper noise at level 30. The denoised images are obtained using (b) NLR-TP, (c) Algorithm 1-S1, and (d) Algorithm 1-S2. The second row displays the corresponding zoomed-in regions of the images in the first row

Download: Full-size image PowerPoint slide

Table 1. Parameters set for mixed salt-and-pepper noise and Gaussian noise

Algorithm	Algorithm 1-S1				Algorithm 1-S2
Noise Type	$ \eta $	$ \lambda $	$ \epsilon $	block size	$ \eta $	$ \lambda $	$ \epsilon $	block size
Images: Barbara and House
sp20+gs10	1	4.0e-4	0.01	10	1	2e-4	0.01	10
sp30+gs10	1	3.5e-4	0.01	10	1	2e-4	0.01	10
sp50+gs10	1	3.4e-4	0.01	12	1	1.8e-4	0.01	12
sp20+gs20	1	1.1e-4	0.01	12	1	5e-5	0.01	12
sp30+gs20	1	1e-4	0.01	12	1	5e-5	0.01	12
sp50+gs20	1	9e-5	0.01	12	1	5e-5	0.01	12
Image: Boat
sp20+gs10	1	5e-4	0.1	10	3	2.3e-3	0.8	10
sp30+gs10	1	8e-4	0.1	10	3	2.1e-3	0.1	10
sp50+gs10	1	1.3e-3	1	15	5	1.5e-3	1	15
sp20+gs20	7	5.5e-3	0.01	10	0.5	1.3e-3	0.5	10
sp30+gs20	7	9e-3	1	10	0.5	1.2e-3	0.5	10
sp50+gs20	9	1.5e-4	0.01	15	5	7e-4	1	15

| Show Table

DownLoad: CSV

Table 2. Comparison of NLR-TP and Algorithm 1

Algorithm	NLR-TP	Algorithm 1-S1	Algorithm 1-S2
Noise Type	(PSNR, SSIM, FSIM)	(PSNR, SSIM, FSIM)	(PSNR, SSIM, FSIM)
The "Barbara" image
sp20+gs10	(34.50, 0.9731, 0.9806)	(34.53, 0.9735, 0.9816)	(34.62, 0.9741, 0.9821)
sp30+gs10	(33.87, 0.9700, 0.9783)	(34.09, 0.9714, 0.9801)	(34.15, 0.9718, 0.9804)
sp50+gs10	(31.92, 0.9563, 0.9705)	(32.83, 0.9629, 0.9742)	(32.87, 0.9640, 0.9737)
sp20+gs20	(31.34, 0.9481, 0.9637)	(31.40, 0.9478, 0.9649)	(31.44, 0.9490, 0.9648)
sp30+gs20	(30.90, 0.9451, 0.9606)	(31.02, 0.9441, 0.9649)	(31.00, 0.9458, 0.9617)
sp50+gs20	(30.01, 0.9334, 0.9537)	(30.06, 0.9312, 0.9551)	(30.04, 0.9337, 0.9549)
The "House" image
sp20+gs10	(38.99, 0.9598, 0.9760)	(38.97, 0.9588, 0.9766)	(39.12, 0.9618, 0.9777)
sp30+gs10	(38.17, 0.9550, 0.9732)	(38.38, 0.9518, 0.9719)	(38.67, 0.9580, 0.9750)
sp50+gs10	(36.58, 0.9430, 0.9704)	(37.31, 0.9410, 0.9677)	(37.65, 0.9505, 0.9705)
sp20+gs20	(35.76, 0.9290, 0.9542)	(35.69, 0.9227, 0.9472)	(35.77, 0.9297, 0.9543)
sp30+gs20	(35.34, 0.9257, 0.9528)	(35.34, 0.9187, 0.9438)	(35.37, 0.9248, 0.9520)
sp50+gs20	(34.73, 0.9150, 0.9457)	(34.73, 0.9114, 0.9397)	(34.74, 0.9119, 0.9425)
The "Boat" image
Bsp20+gs10	(32.84, 0.9565, 0.9768)	(32.78, 0.9565, 0.9777)	(32.85, 0.9553, 0.9771)
Bsp30+gs10	(32.22, 0.9497, 0.9724)	(32.24, 0.9511, 0.9738)	(32.23, 0.9501, 0.9731)
Bsp50+gs10	(30.57, 0.9298, 0.9612)	(30.54, 0.9311, 0.9614)	(30.65, 0.9307, 0.9618)
Bsp20+gs20	(29.91, 0.9099, 0.9484)	(29.82, 0.9028, 0.9490)	(29.81, 0.9067, 0.9484)
Bsp30+gs20	(29.47, 0.9023, 0.9439)	(29.31, 0.8904, 0.9431)	(29.30, 0.8951, 0.9401)
Bsp50+gs20	(28.31, 0.8726, 0.9255)	(28.20, 0.8736, 0.9291)	(28.26, 0.8736, 0.9294)

| Show Table

DownLoad: CSV

Table 3. Parameter sets for denoising the image with Algorithm 1

Algorithm	Algorithm 1-S1				Algorithm 1-S2
Noise Type	$ \eta $	$ \frac{1}{\lambda} $	$ \epsilon $	block size	$ \eta $	$ \frac{1}{\lambda} $	$ \epsilon $	block size
Image: Barbara Figure 1(a)
rv15+gs15	1	7.0e-5	1e-2	12	1.7	1.7e-4	0.01	12
rv25+gs15	1	5.0e-5	1e-2	12	1.7	1.8e-4	0.01	12
rv45+gs15	1	3.0e-5	1e-2	12	1.7	1.8e-4	0.01	12
rv15+gs25	1	3.0e-5	1e-2	12	1.7	1.0e-4	0.01	12
rv25+gs25	1	2.2e-5	1e-2	12	1.7	1.0e-4	0.01	12
rv45+gs25	1	1.5e-5	1e-2	12	1.7	1.0e-5	0.01	12
Image: House Figure 1(b)
rv15+gs15	1	7.0e-5	1e-3	18	1.7	1.6e-4	1e-1	18
rv25+gs15	1	5.0e-5	1e-3	18	1.7	1.2e-4	1e-1	18
rv45+gs15	1	2.0e-5	1e-3	18	1.7	1.2e-4	1e-2	18
rv15+gs25	1	2.2e-5	1e-3	18	1.7	1.0e-4	1e-2	12
rv25+gs25	1	1.8e-5	1e-3	18	1.7	7.0e-5	1e-1	15
rv45+gs25	1	9.0e-6	1e-3	18	1.7	8.0e-5	1e-2	12
Image: Boat Figure 1(c)
rv15+gs15	1	1e-3	1	12	1.5	7e-4	2.5	10
rv25+gs15	1	5e-4	1	12	1.2	3e-4	2.5	10
rv45+gs15	1	2.0e-4	1	12	1	3e-4	2.5	15
rv15+gs25	1	2.5e-4	1	10	1.5	2.5e-4	5	10
rv25+gs25	1	2.0e-4	1	10	1.5	1.5e-4	5	10
rv45+gs25	1	1.25e-4	1	10	1.5	1e-4	5	15

| Show Table

DownLoad: CSV

Table 4. Comparison of NLR-TP and Algorithm 1

Algorithm	NLR-TP	Algorithm 1-S1	Algorithm 1-S2
Noise Type	(PSNR, SSIM, FSIM)	(PSNR, SSIM, FSIM)	(PSNR, SSIM, FSIM)
The "Barbara" image
rv15+gs15	(29.78, 0.9393, 0.9600)	(30.41, 0.9437, 0.9633)	(30.40, 0.9443, 0.9631)
rv25+gs15	(28.57, 0.9261, 0.9543)	(29.14, 0.9304, 0.9581)	(28.98, 0.9246, 0.9519)
rv45+gs15	(25.16, 0.8564, 0.9252)	(25.33, 0.8567, 0.9302)	(26.00, 0.8775, 0.9322)
rv15+gs25	(28.16, 0.9074, 0.9415)	(28.89, 0.9178, 0.9468)	(28.57, 0.9068, 0.9439)
rv25+gs25	(27.10, 0.8839, 0.9324)	(27.64, 0.8919, 0.9375)	(27.52, 0.8837, 0.9349)
rv45+gs25	(23.99, 0.7946, 0.8905)	(24.61, 0.8075, 0.9028)	(24.81, 0.8151, 0.8979)
The "House" image
rv15+gs15	(36.69, 0.9358, 0.9589)	(36.68, 0.9339, 0.9587)	(36.69, 0.9358, 0.9601)
rv25+gs15	(36.01, 0.9238, 0.9488)	(36.10, 0.9248, 0.9504)	(36.18, 0.9301, 0.9558)
rv45+gs15	(33.08, 0.9022, 0.9332)	(33.68, 0.9036, 0.9359)	(33.74, 0.9057, 0.9337)
rv15+gs25	(33.84, 0.9086, 0.9415)	(34.42, 0.9065, 0.9351)	(34.17, 0.9029, 0.9337)
rv25+gs25	(33.33, 0.8966, 0.9299)	(33.61, 0.8986, 0.9282)	(33.50, 0.8976, 0.9269)
rv45+gs25	(29.69, 0.8627, 0.9046)	(30.41, 0.8725, 0.9086)	(30.56, 0.8636, 0.9078)
The "Boat" image
rv15+gs15	(29.65, 0.9126, 0.9519)	(29.65, 0.9077, 0.9503)	(29.66, 0.9063, 0.9502)
rv25+gs15	(28.59, 0.8870, 0.9367)	(28.69, 0.8932, 0.9419)	(28.64, 0.8927, 0.9417)
rv45+gs15	(26.34, 0.8378, 0.9110)	(26.43, 0.8366, 0.9103)	(28.42, 0.8379, 0.9115)
rv15+gs25	(27.81, 0.8607, 0.9252)	(27.85, 0.8554, 0.9228)	(27.89, 0.8558, 0.9240)
rv25+gs25	(26.98, 0.8314, 0.9068)	(27.01, 0.8326, 0.9097)	(27.99, 0.8341, 0.9117)
rv45+gs25	(24.77, 0.7559, 0.8675)	(24.87, 0.7506, 0.8635)	(24.85, 0.7544, 0.8686)

| Show Table

DownLoad: CSV

Related Papers

Cited by

References

[1]	H. Attouch, J. Bolte and P. Redont, Proximal alternating alternating minimization and projection methods for nonconvex problems: An approach based on the Kurdyka-Łojasiewicz inequality, Mathematics of Operations Research, 35 (2010), 438-457. doi: 10.1287/moor.1100.0449.
[2]	H. Attouch, J. Bolte and B. F. Svaiter, Convergence of descent methods for semi-algebraic and tame problems: Proximal algorithms, forward-backward splitting, and regularized Gauss-Seidel methods, Mathematical Programming, Ser. A, 137 (2013), 91-129. doi: 10.1007/s10107-011-0484-9.
[3]	A. Beck, First-order Methods in Optimization, MOS-SIAM Ser. Optim., 25, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA; Mathematical Optimization Society, Philadelphia, PA, 2017.
[4]	J.-F. Cai, E. Candes and Z. Shen, A singular value thresholding algorithm for matrix completion, SIAM Journal on Optimization, 20 (2010), 1956-1982. doi: 10.1137/080738970.
[5]	J.-F. Cai, R. Chan, L. Shen and Z. Shen, Simultaneously inpainting in image and transformed domains, Numerische Mathematik, 112 (2009), 509-533. doi: 10.1007/s00211-009-0222-x.
[6]	J.-F. Cai, R. H. Chan and M. Nikolova, Two-phase methods for deblurring images corrupted by impulse plus Gaussian noise, Inverse Problems and Imaging, 2 (2008), 187-204. doi: 10.3934/ipi.2008.2.187.
[7]	J.-F. Cai, R. H. Chan, L. Shen and Z. Shen, Convergence analysis of tight framelet approach for missing data recovery, Advances in Computational Mathematics, 31 (2009), 87-113. doi: 10.1007/s10444-008-9084-5.
[8]	E. Candes, M. B. Wakin and S. Boyd, Enhancing sparsity by reweighted $\ell^1$ minimization, Journal of Fourier Analysis and Applications, 14 (2008), 877-905. doi: 10.1007/s00041-008-9045-x.
[9]	K. Chen, H. Dong and K.-S. Chan, Reduced rank regression via adaptive nuclear norm penalization, Biometrika, 100 (2013), 901-920.
[10]	T. Chen and H. R. Wu, Adaptive impulse detection using center-weighted median filters, IEEE Signal Processing Letters, 8 (2001), 1-3. doi: 10.1109/97.889633.
[11]	K. Dabov, A. Foi, V. Katkovnik and K. Egiazarian, Image denoising by sparse 3D transform-domain collaborative filtering, IEEE Transanctions on Image Processing, 16 (2007), 2080-2095. doi: 10.1109/TIP.2007.901238.
[12]	M. Fazel, H. Hindi and S. Boyd, Log-det heuristic for matrix rank minimization with applications to Hankel and Euclidean distance matrices, Proceedings of American Control Conference, 3 (2003), 2156-2162.
[13]	S. Gu, L. Zhang, W. Zuo and X. Feng, Weighted nuclear norm minimization with application to image denoising, Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, 2014, 2862-2869.
[14]	O. Güler, Foundations of Optimization, Grad. Texts in Math., 258, Springer, New York, 2010.
[15]	T. Huang, W. Dong, X. Xie, G. Shi and X. Bai, Mixed noise removal via laplacian scale mixture modeling and nonlocal low-rank approximation, IEEE Transactions on Image Processing, 26 (2017), 3171-3186.
[16]	H. Hwang and R. A. Haddad, Adaptive median filters: New algorithms and results, IEEE Transactions on Image Processing, 4 (1995), 499-502.
[17]	J. Jiang, L. Zhang and J. Yang, Mixed noise removal by weighted encoding with sparse nonlocal regularization, IEEE Transactions on Image Processing, 23 (2014), 2651-2662.
[18]	A. S. Lewis and H. S. Sendov, Nonsmooth analysis of singular values. Part Ⅰ: Theory, Set-Valued Analysis, 13 (2005), 213-241. doi: 10.1007/s11228-004-7197-7.
[19]	Y.-R. Li, L. Shen, D. Q. Dai and B. W. Suter, Framelet algorithms for de-blurring images corrupted by impulse plus gaussian noise, IEEE Transactions on Image Processing, 20 (2011), 1822-1837.
[20]	L. Liu, L. Chen, C. L. P. Chen and Y. Y. Tang, et al., Weighted joint sparse representation for removing mixed noise in image, IEEE Transactions on Cybernetics, 47 (2016), 600-611.
[21]	L. Mirsky, A trace inequality of John von Neumann, Monatshefte fur Mathematik, 79 (1975), 303-306. doi: 10.1007/BF01647331.
[22]	J.-J. Moreau, Fonctions convexes duales et points proximaux dans un espace hilbertien, C.R. Acad. Sci. Paris Sér. A Math., 255 (1962), 2897-2899.
[23]	A. Prater-Bennette, L. Shen and E. E. Tripp, The proximity operator of the log-sum penalty, Journal of Scientific Computing, 93 (2022), Paper No. 67, 34 pp.
[24]	Z. Wang, A. C. Bovik, H. R. Sheikh and E. P. Simoncelli, Image quality assessment: From error visibility to structural similarity, IEEE Transactions on Image Processing, 13 (2004), 600-612.
[25]	B. Wen, X. Chen and T. K. Pong, A proximal difference-of-convex algorithm with extrapolation, Computational Optimization and Applications, 69 (2018), 297-324.
[26]	Y. Xiao, T. Zeng, J. Yu and M. K. Ng, Restoration of images corrupted by mixed Gaussian-impulse noise via l1-l0 minimization, Pattern Recognition, 44 (2011), 1708-1720.
[27]	C. Xu, X. Liu, J. Zheng, L. Shen, Q. Jiang and J. Lu, Nonlocal low-rank regularized two-phase approach for mixed noise removal, Inverse Problems, 37 (2021), Paper No. 085001, 25 pp.
[28]	L. Zhang, L. Zhang, X. Mou and D. Zhang, FSIM: A feature similarity index for image quality assessment, IEEE Transactions on Image Processing, 20 (2011), 2378-2386.