**Commenced**in January 2007

**Frequency:**Monthly

**Edition:**International

**Paper Count:**32799

##### 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.