A Graduated Non-Convexity Technique for Dealing Large Point Spread Functions
Source abstract
Abstract
This paper focuses on reducing the computational cost of a GNC Algorithm for deblurring images when dealing with full symmetric Toeplitz block matrices composed of Toeplitz blocks. Such a case is widespread in real cases when the PSF has a vast range. The analysis in this paper centers around the class of gamma matrices, which can perform vector multiplications quickly. The paper presents a theoretical and experimental analysis of how γ-matrices can accurately approximate symmetric Toeplitz matrices. The proposed approach involves adding a minimization step for a new approximation of the energy function to the GNC technique. Specifically, we replace the Toeplitz matrices found in the blocks of the blur operator with γ-matrices in this approximation. The experimental results demonstrate that the new GNC algorithm proposed in this paper reduces computation time by over 20% compared with its previous version. The image reconstruction quality, however, remains unchanged.
Source: crossref · Quality: baseline
Research context
OpenAlex topics: Sparse and Compressive Sensing Techniques · Medical Image Segmentation Techniques · Image and Signal Denoising Methods
SciVX discovery tags are terminology-based. OpenAlex topics are source-provided classifications.
Affiliations
Dipartimento di Matematica e Informatica, Università degli Studi di Perugia, Via Vanvitelli, 1, I-06123 Perugia, Italy
Dipartimento di Matematica e Informatica “Ulisse Dini”, Università degli Studi di Firenze, Viale Morgagni, 67/a, I-50134 Firenze, Italy
References (53)
Show source-provided references
1. Underwater Image Enhancement by Attenuated Color Channel Correction and Detail Preserved Contrast Enhancement10.1109/JOE.2022.3140563 ↗
2. Underwater Image Enhancement with Hyper-Laplacian Reflectance Priors10.1109/TIP.2022.3196546 ↗
3. Image Reconstruction and Restoration: Overview of CommonEstimation Structures and Problems10.1109/29.45551 ↗
4. Half-Quadratic Image Restoration with a Non-Parallelism Constraint10.1007/s10851-017-0731-7 ↗
5. Convex Approximation Technique for Interacting Line Elements Deblurring: A New Approach10.1007/s10851-011-0319-6 ↗
6. Constrained restoration and the recovery of discontinuities10.1109/34.120331 ↗
7. Stochastic Relaxation, Gibbs Distributions, and the Bayesian Restoration of Images10.1109/TPAMI.1984.4767596 ↗
8. Blake, A., and Zisserman, A. (1987). Visual Reconstruction, MIT Press.10.7551/mitpress/7132.001.0001 ↗
9. Bedini, L., Gerace, I., Pepe, M., Salerno, E., and Tonazzini, A. (1992). Stochastic and Deterministic Algorithms for Image Reconstruction with Implicitly Referred Discontinuities, Istituto di Elaborazione della Informazione, C.N.R.. Internal report n. r/2/85.
10. Comparison of the efficiency of deterministic and stochastic algorithms for visual reconstruction10.1109/34.23109 ↗
11. A Deterministic Algorithm for Reconstruction Images with Interacting Discontinuities10.1006/cgip.1994.1011 ↗
12. Markovian Reconstruction Using a GNC Approach10.1109/83.784433 ↗
13. Evangelopoulos, X., Brockmeier, A.J., Mu, T., and Goulermas, J.Y. (2017, January 27–29). A Graduated Non-Convexity Relaxation for Large-Scale Seriation. Proceedings of the 2017 SIAM International Conference on Data Mining, Houston, TX, USA.10.1137/1.9781611974973.52 ↗
14. Hazan, E., Levy, K.Y., and Shalev-Shwartz, S. (2016, January 20–22). On Graduated Optimization for Stochastic Non-Convex Problems. Proceedings of the 33rd International Conference on Machine Learning, New York, NY, USA.
15. GNCCP–Graduated NonConvexity and Concavity Procedure10.1109/TPAMI.2013.223 ↗
16. MAP Inference with MRF by Graduated Non-Convexity and Concavity Procedure
17. Dynamical Pose Estimation with Graduated Non-Convexity for Outlier Robustness10.4173/mic.2022.2.3 ↗
18. Graduated Non-Convexity for Robust Spatial Perception: From Non-Minimal Solvers to Global Outlier Rejection10.1109/LRA.2020.2965893 ↗
19. On a matrix algebra related to the discrete Hartley transform10.1137/0614035 ↗
20. The numerical solution of an elliptic P.D.E. with periodic boundary conditions in a rectangular region by the spectral resolution method10.1016/0771-050X(82)90046-8 ↗
21. A Preconditioned Finite Element Method for the p-Laplacian Parabolic Equation10.1002/anac.200310013 ↗
22. Circulant matrix methods for the numerical solution of partial differential equations by FFT convolutions10.1016/0307-904X(88)90022-4 ↗
23. Utilization of Circulant Matrix Theory in Periodic Autonomous Difference Equations
24. Existence of periodic solutions in a linear higher-order system of difference equations10.1016/j.camwa.2013.06.018 ↗
25. Image reconstruction based on circulant matrices10.1016/j.image.2018.01.010 ↗
26. Henriques, J.F. (2015). Circulant Structures in Computer Vision. [Ph.D. Thesis, Department of Electrical and Computer Engineering, Faculty of Science and Technology].
27. Hardness results and spectral techniques for combinatorial problems on circulant graphs10.1016/S0024-3795(98)10126-X ↗
28. A Spectral Technique to Solve the Chromatic Number Problem in Circulant Graphs
29. The Travelling Salesman Problem in symmetric circulant matrices with two stripes10.1017/S0960129508006609 ↗
30. The Traveling Salesman Problem in Circulant Weighted Graphs with Two Stripes10.1016/j.entcs.2006.07.032 ↗
31. Characterizing the Integrality Gap of the Subtour LP for the Circulant Traveling Salesman Problem10.1137/19M1245840 ↗
32. The Two-Stripe Symmetric Circulant TSP is in P10.1007/978-3-031-06901-7_24 ↗
33. Applications of left circulant matrices in signal and image processing10.1142/S0217984908014791 ↗
34. Fast multilinear singular value decomposition for structured tensors10.1137/060655936 ↗
35. Fast Hankel tensor-vector product and applications to exponential data fitting10.1002/nla.1970 ↗
36. Exponential data fitting using multilinear algebra: The single-channel and the multi-channel case10.1002/nla.453 ↗
37. Hankel tensors: Associated Hankel matrices and Vandermonde decomposition10.4310/CMS.2015.v13.n1.a6 ↗
38. A Fast Discrete Transform for a Class of Simultaneously Diagonalizable Matrices
39. Structure Preserving Preconditioners for Image Deblurring10.1007/s10915-016-0350-2 ↗
40. On Regularization Parameters Estimation in Edge-Preserving Image Reconstruction10.1007/978-3-540-69848-7_93 ↗
41. Boccuto, A., and Gerace, I. (2016, January 27–28). Image reconstruction with a non-parallelism constraint. Proceedings of the International Workshop on Computational Intelligence for Multimedia Understanding, Reggio Calabria, Italy.10.1109/IWCIM.2016.7801174 ↗
42. On ℓ1 Data Fitting and Concave Regularization for Image Recovery10.1137/10080172X ↗
43. Efficient Reconstruction of Piecewise Constant Images Using Nonsmooth Nonconvex Minimization10.1137/070692285 ↗
44. On the symmetric doubly stochastic inverse eigenvalue problem10.1016/j.laa.2013.12.005 ↗
45. Boccuto, A., Gerace, I., Giorgetti, V., and Greco, F. (2021). Gamma-matrices: A new class of simultaneously diagonalizable matrices. arXiv, Available online: https://arxiv.org/abs/2107.05890.
46. Davis, P.J. (1979). Circulant Matrices, John Wiley & Sons.
47. Bose, A., and Saha, K. (2019). Random Circulant Matrices, CRC Press, Taylor & Francis Group.10.1201/9780429435508 ↗
48. Eigenvectors of block circulant and alternating circulant matrices
49. Boccuto, A., Gerace, I., and Giorgetti, V. (2022). Image Deblurring: A Class of Matrices Approximating Toeplitz Matrices. viXra, Available online: https://rxiv.org/abs/2201.0155.
50. Toeplitz equations by conjugate gradients with circulant preconditioner10.1137/0910009 ↗
51. Sylvester Tikhonov-regularization methods in image restoration10.1016/j.cam.2006.05.028 ↗
52. Edge-preserving restoration in 2-D fluorescence microscopy10.1016/S0968-4328(96)00040-6 ↗
53. Gerace, I., and Pandolfi, R. (2003, January 17–19). A color image restoration with adjacent parallel lines inhibition. Proceedings of the 12th International Conference on Image Analysis and Processing, Mantova, Italy.