1. Complete title: CoInGP: Convolutional Inpainting with Genetic Programming --------------------- 2. Authors' names, addresses, e-mails and phone numbers: Domagoj Jakobovic Dept. of Electronics, Microelectronics, Computer and Intelligent Systems Faculty of Electrical Engineering and Computing, Unska 3, 10000 Zagreb, Croatia domagoj.jakobovic@fer.hr +385 1612 9967 Luca Manzoni Dipartimento di Matematica e Geoscienze, Università degli Studi di Trieste, Via Valerio 12/1, 34127 Trieste, Italy lmanzoni@units.it +39 040 558 2674 Luca Mariot Cyber Security Research Group, Delft University of Technology, Mekelweg 2, Delft, The Netherlands l.mariot@tudelft.nl +31 623 952 460 Stjepan Picek Cyber Security Research Group, Delft University of Technology, Mekelweg 2, Delft, The Netherlands s.picek@tudelft.nl +385 9822 6407 Mauro Castelli NOVA Information Management School (NOVA IMS), Universidade Nova de Lisboa, Campus de Campolide, 1070-312, Lisboa, Portugal mcastelli@novaims.unl.pt +34 2138 2861 0208 --------------------- 3. Corresponding author Luca Mariot --------------------- 4. Abstract We investigate the use of Genetic Programming (GP) as a convolutional predictor for missing pixels in images. The training phase is performed by sweeping a sliding window over an image, where the pixels on the border represent the inputs of a GP tree. The output of the tree is taken as the predicted value for the central pixel. We consider two topologies for the sliding window, namely the Moore and the Von Neumann neighborhood. The best GP tree scoring the lowest prediction error over the training set is then used to predict the pixels in the test set. We experimentally assess our approach through two experiments. In the first one, we train a GP tree over a subset of 1000 complete images from the MNIST dataset. The results show that GP can learn the distribution of the pixels with respect to a simple baseline predictor, with no significant differences observed between the two neighborhoods. In the second experiment, we train a GP convolutional predictor on two degraded images, removing around 20% of their pixels. In this case, we observe that the Moore neighborhood works better, although the Von Neumann neighborhood allows for a larger training set. --------------------- 5. Relevant criteria D, G --------------------- 6. Criteria statement (D) Our paper shows that GP is able to evolve trees that can be used to reliably predict the missing pixels in an image by exploiting the information contained in the surrounding pixels. As such, this work demonstrates a further application of the principle set forth by Efros and Leung that the information conveyed by pixels in an image is generally local, meaning that the probability distribution of a given pixel given the intensities of its neighbors is independent from the rest of the image. This allows to design small convolutional operators to slide over an image whose missing pixels need to be restored, by training the operator on the available pixels. Up to now, the most popular approach to design such operators is based on the use of Convolutional Neural Networks (CNNs). Our work, on the other hand, show that inpainting operators can also be designed starting from a different premise than neural networks, namely using evolutionary computing. Since inpainting is a relevant goal in the field of image processing independently of how it is performed, we therefore believe that our work completely qualifies for the criterion (D). As a further motivation, this paper has been accepted at the GECCO'21 conference, receiving reviews that favorably judged the novelty of our approach. (G) Image inpainting is a particular instance of a more general prediction problem, which usually goes by the name of imputation in the signal processing and statistics literature. The goal is to fill in the missing points in an observed signal/dataset by using the information in the available points. Since images can be thought of as two-dimensional spatial signals, predicting the values of missing or damaged pixels corresponds to imputation. There is a vast literature that considers the problem of image inpainting, showing that it is quite relevant in the field of image processing. Further, the plethora of different approaches that have been proposed and tried to solve the inpainting problem in the past few decades shows also that it is quite difficult to address with computational methods, not only to obtain realistic restored images, but also to investigate the problem from a more theoretical perspective. In our paper, we showed that GP proved to be an effective tool for obtaining plausible restored images with low RMSE from the original ones, and also for learning the distribution the missing pixels from a dataset of images. This second aspect in particular is interesting to give theoretical insights on the problem of image inpainting, especially considering that models learned by GP are usually more interpretable than the widely adopted neural network models. For these reasons, we think that our work also fits entirely into criterion (G). --------------------- 7. Full citation Jakobovic D., Manzoni L., Mariot L., Picek S., Castelli M. (2021) CoInGP: Convolutional Inpainting with Genetic Programming. In: GECCO '21, Proceedings. In press. DOI: 10.1145/3449639.3459346 --------------------- 8. Prize statement Any prize money, if any, is to be divided equally among the co-authors. --------------------- 9. Best statement As mentioned above, inpainting is a very relevant problem in the image processing research field, and under the specific working hypotheses assumed in our paper, we showed that GP is able both to learn the distribution of missing pixels in a dataset of images and to plausibly reconstruct single images by exploiting the available pixels in them. Besides the bare results obtained in the paper, we also think that our work opens up to a whole new host of research directions where GP could be investigated as an effective convolutional predictor, both in the context of images and more general signals. Indeed, already in the paper we observed that the predictions errors tends to concentrate on the edges of the test images, where the pixels' intensities change abruptly. Far from being an issue, this remark could actually make our CoInGP method also useful for other image processing filters, such as edge detection. Moreover, the convolutional strategy is general enough that one could think to apply CoInGP to other imputation problems on different signals, such as time series, audio signals and videos. These are all use cases where other machine learning models such as convolutional neural networks have been widely proposed, but where on the other hand evolutionary methods such as GP have been little studied. Hence, in perspective we think that our CoInGP method could draw much interest from the evolutionary computing community on several interesting new problems. --------------------- 10. Methods used GP (Genetic Programming) --------------------- 11. Publication date In press