Comparative Analysis of Classical and Parallel Inpainting Algorithms Based on Affine Combinations of Projections on Convex Sets

Authors: Irina Maria Artinescu, Costin Radu Boldea, Eduard-Ionut Matei

Abstract:

The paper is a comparative study of two classical vari-ants of parallel projection methods for solving the convex feasibility problem with their equivalents that involve variable weights in the construction of the solutions. We used a graphical representation of these methods for inpainting a convex area of an image in order to investigate their effectiveness in image reconstruction applications. We also presented a numerical analysis of the convergence of these four algorithms in terms of the average number of steps and execution time, in classical CPU and, alternativaly, in parallel GPU implementation.

Keywords: convex feasibility problem, convergence analysis, ınpainting, parallel projection methods

References:

[1] I.M. Artinescu, L.O. Mafteiu-Scai: A Scratch Covering Algorithm using Affine Projection Method. Mathematics and Computer Sciences, 12(2), 235–246, 2018.
[2] I.M. Artinescu: A comparative analysis of the convergence regions for different parallel affine projection algorithms. Stud. Univ. Babes-Bolyai Math., 63(3), 401–411, 2018.
[3] S. Agmon: The relaxation method for linear inequalities. Canadian Journal of Mathematics, 6, pp. 382–392, 1954.
[4] H.H. Bauschke, J.M. Borwein: On Projection Algorithms for Solving Convex Feasibility Problems. (SIAM Review) Society for Industrial and Applied Mathematics Review, 38(3), 367–426, 1996.
[5] M. Bertalmio, G. Sapiro, V. Caselles, C. Ballester: Image inpainting.ACM Comput. Graph. (SIGGRAPH 2002). In SIGGRAPH: Proceedings of the 27th annual conference on Computer graphics and interactive techniques, New Orleans, ACM Press/Addison-Wesley, New York, pp. 417–424,2000.
[6] M. Bertalmio, L. Vese, G. Sapiro, S. Osher: Simultaneous structure and texture image inpainting. IEEE Transactions on Image Processing, 12, pp. 882–889, 2003.
[7] Y. Censor, W. Chen, P. Combettes, R. David, G. Herman: On the effectiveness of projection methods for convex feasibility problems with linear inequality constraints. In Computational Optimization and Applications, Kluwer Academic Publishers Norwell, USA, pp. 1065–1088, 2012
[8] G. Cimmino: Calcolo approssimato per le soluzioni dei sistemi di equazioni lineari. La Ricerca Scientifica, 1, pp. 326–333, 1938.
[9] P.L. Combettes: The Convex Feasibility Problem in Image Recovery. Advances in Imaging and Electron Physics, 95, pp. 155–270,1996.
[10] P.L. Combettes: Hilbertian Convex Feasibility Problem: Convergence of Projection Methods. Applied Mathematics and Optimization, 35, pp. 311–330, 1997a.
[11] P.L. Combettes:Convex set theoretic image recovery by extrapolated iterations of parallel subgradient projections. IEEE Transactions on Image Processing, 6(4), pp. 493–506, 1997b.
[12] A. Criminis, P. Perez, K. Toyama: Region Filling and Object Removal by Exemplar-Based Image Inpainting. Transactions on Image Processing,13, pp. 1200–1212, 2004.
[13] P. Gilbert: Iterative methods for the three-dimensional reconstruction of an object from projections. Journal of Theoretical Biology, 36, pp. 105–117, 1972.
[14] R. Gordon, R. Bender, G.T. Herman: Algebraic reconstruction techniques (ART) for three-dimensional electron microscopy and X-ray photography. Journal of Theoretical Biology, 29, pp. 471–481,1970.
[15] L.G. Gubin, B.T. Polyak, E.V. Raik: The method of projections for finding the common point of convex sets. USSR Computational Mathematics and Mathematical Physics, 7(6), pp. 1–24, 1967.
[16] Y.I. Merzlyakov: On a relaxation method of solving systems of linear inequalities. USSR Computational Mathematics and Mathematical Physics, 2, pp. 504–510, 1963.
[17] T.S. Motzkin, I.J. Schoenberg: The relaxation method for linear inequalities. Canadian Journal of Mathematics, 6, pp. 393–404, 1954.
[18] M. Ait Rami, U. Helmke, J.B. Moore: A finite steps algorithm for solving convex feasibility problems. Journal of Global Optimizations, 38, pp. 143–160, 2007.
[19] Zhao X.; Hu J.; Yao T. GPU based iterative cone-beam CT reconstruction using empty space skipping technique. Journal of X-Ray Science and Technology 2013, pp. 53-69.
[20] T. Zheng, X. Cheng, D. Xiaoyun: A Parallel Depth-Aided Exemplar-Based Inpainting for Real-Time View Synthesis on GPU. IEEE 10th International Conference on High Performance Computing and Communications and IEEE International Conference on Embedded and Ubiquitous Computing, pp. 1739–1744,2013.