1. Title of paper A Novel Hybrid Scheme Using Genetic Algorithms and Deep Learning for the Reconstruction of Portuguese Tile Panels 2. Authors Daniel Rika Dept. of Computer Science Bar-Ilan University Ramat-Gan 52900, Israel danielrika@gmail.com Dror Sholomon Dept. of Computer Science Bar-Ilan University Ramat-Gan 52900, Israel dror.sholomon@gmail.com Eli (Omid) David Dept. of Computer Science Bar-Ilan University Ramat-Gan 52900, Israel mail@elidavid.com Nathan S. Netanyahu Dept. of Computer Science Bar-Ilan University Ramat-Gan 52900, Israel nathan@cs.biu.ac.il +972-3-531-7721 3. Corresponding Author Daniel Rika 4. Abstract This paper presents a novel scheme, based on a unique combination of genetic algorithms (GAs) and deep learning (DL), for the automatic reconstruction of Portuguese tile panels, a challenging real-world variant of the jigsaw puzzle problem (JPP) with important national heritage implications. Specifically, we introduce an enhanced GA-based puzzle solver, whose integration with a novel DL-based compatibility measure (DLCM) yields state-of-the-art performance, regarding the above application. Current compatibility measures consider typically (the chromatic information of) edge pixels (between adjacent tiles), and help achieve high accuracy for the synthetic JPP variant. However, such measures exhibit rather poor performance when applied to the Portuguese tile panels, which are susceptible to various real-world effects, e.g., monochromatic panels, non-squared tiles, edge degradation, etc. To overcome such difficulties, we have developed a novel DLCM to extract high-level texture/color statistics from the entire tile information. Integrating this measure with our enhanced GA-based puzzle solver, we have demonstrated, for the first time, how to deal most effectively with large-scale real-world problems, such as the Portuguese tile problem. Specifically, we have achieved 82% accuracy for the reconstruction of Portuguese tile panels with unknown piece rotation and puzzle dimension (compared to merely 3.5% average accuracy achieved by the best method known for solving this problem variant). The proposed method outperforms even human experts in several cases, correcting their mistakes in the manual tile assembly. 5. Criteria List (B) The result is equal to or better than a result that was accepted as a new scientific result at the time when it was published in a peer-reviewed scientific journal. (E) The result is equal to or better than the most recent human-created solution to a long-standing problem for which there has been a succession of increasingly better human-created solutions. (F) The result is equal to or better than a result that was considered an achievement in its field at the time it was first discovered. (G) The result solves a problem of indisputable difficulty in its field. 6. Statement on Criteria Criterion B: The best algorithm known for the Portuguese tile problem, drawing explicitly on a journal publication, is due to Andalo et al. (F. A. Andaló, G. Carneiro, G. Taubin, S. Goldenstein, and L. Velho, "Automatic Reconstruction of Ancient Portuguese Tile Panels", Technical Report A773/2016, Instituto Nacional de Matematica Pura e Applicada, Brazil), who employed their PSQP method, "PSQP: Puzzle Solving by Quadratic Programming" (Andalo et al., IEEE PAMI, 2017), for the Portuguese tile problem. The largest reconstructed Portuguese panel handled by their method contains only 72 pieces, assuming that both the panel dimensions and pieces orientations were known. Our algorithm not only performs very well without these two constraints (i.e., without assuming known panel dimensions and piece rotations), but it successfully reconstructs Portuguese tile panels with more than 300 pieces. It is thus obvious that our newly proposed algorithm is superior to the PSQP method, as far as the Portuguese tile problem is concerned. Additionally, by solving puzzles of hundreds of pieces, our method could be applied to other real-world problems. Criterion E: The National Tile Museum of Lisbon has collected over the years hundreds of thousands of tiles from Portuguese panels that had to be removed for various reasons. Currently, these tiles are stored in numerous boxes at the Museum, waiting to be (manually) reassembled. Unfortunately, reconstructing manually the many tile panels by a substantially understaffed team of humans is rather infeasible, as it would take too much time and require a lot of physical space, given that a tile size is in the range of 20-30 cm. More importantly, a reconstruction could be erratic, as was demonstrated by our algorithm, which spotted a number of mistakes in "human created" solutions. Thus, the reconstruction capability of out method surpasses that of human experts in preserving Portuguese tile panels, i.e., our method performs in a more accurate and consistent manner than human experts, as far as this problem domain is concerned. Criterion F: Fonseca (J. T. Fonseca. 2012. Montagem Automática de Painéis de Azulejos. M.Sc. Thesis, Instituto Superior Técnico, Universidade Técnica de Lisboa.) acquired tile images and adapted their shape to squares; he then applied an augmented Lagrange multipliers technique to an equivalent optimization problem and a greedy approach for puzzles with known and unknown piece orientations, respectively. He obtained 57.8% and 39.1% accuracy for these cases, respectively, on panels containing only a few dozen tiles. In comparison, Gallagher’s method (A. C. Gallagher. 2012. Jigsaw Puzzles with Pieces of Unknown Orientation. In IEEE Conference on Computer Vision and Pattern Recognition. 382–389.) achieves corresponding accuracy levels of 64.5% and 49.4%. Andalo et al. (F. A. Andaló, G. Carneiro, G. Taubin, S. Goldenstein, and L. Velho. 2016. "Automatic Reconstruction of Ancient Portuguese Tile Panels", Technical Report A773/2016, Instituto Nacional de Matematica Pura e Applicada, Brazil) reported perfect reconstruction of panels cantaining only 72 pieces using their PSQP method for known tile orientation. In contrast, our novel hybrid scheme reconstructs Portuguese panels containing 300 pieces and more without making a priori assumptions (as to the panel dimensions or piece orientations), achieving (over) 96% and (over) 82% accuracy for known and unknown piece orientation, respectively, and for significantly lower-resoultion tiles, i.e., our scheme provides better results than those obtained by all of the above methods. Criterion G: The Portuguese tile problem is a real-world version of the Jigsaw puzzle problem (JPP), which has been investigated for decades, and has been reported at many importants venues. Unlike the well-defined classical JPP, where a digital image is split into N-by-M non-overlapping squared pieces, the real-world setting of the Portuguese tile problem poses various difficult challenges. For example, the data consist of ceramic tiles with a lot of defects, such as uneven shading/chromatic effects due to a long exposure to sunlight of some of the tiles, degradation of edge boundaries (between adjacent tiles) which severely affect the standard comtability measures of the classical JPP, etc. As indicated before, to the best of our knowledge -- the largest Portuguese tile panel successfully reconstructed consists of merely 72 pieces, using a rather restricted algorithm. On the other hand, our algorithm successfully reconstructs Portuguese panels with more than 300 pieces without knowning in advance the panel's dimension or the piece orientations. 7. Citation D. Rika, D. Sholomon, E. O. David , and N. S. Netanyahu, 2019. The Genetic and Evolutionary Computation Conference (GECCO): A Novel Hybrid Scheme Using Genetic Algorithms and Deep Learning for the Reconstruction of Portuguese Tile Panels. To appear. 8. Prize Money Any prize money is to be divided evenly among the co-authors. 9. Authors' Statement to the Judges There are three significant points that make our research entry so special: (1) Better than humans. Our current module is capable, not only, of reconstructing successfully Portuguese tile panels on a large-scale basis (a task that humans would find hard to deal with over time), but it also outperforms human expertise in terms of reconstruction accuracy. Specifically, we present in our paper examples of three panels where our algorithm found mistakes due to human/manual assembly; indeed, these mistakes were acknowledged by the (Director of the) National Tile Museum in Lisbon, Portugal, who had supplied us with these panels. The notion that our algorithm could make an important difference for numerous visitors at the Museum is testament to its superior performance over humans! (2) Cultural heritage. The reconstruction of ancient frescoes and wall paintings from numerous large repositories of fragmented artifacts, compiled over time due to natural deterioration, is of utmost importance in preserving world cultural heritage. The significance of our automated systems is that it is expected to assist in such a highly-valued world-wide effort, in a more effective and accurate manner than manual (i.e., human) reconstruction. (3) General purpose. We introduced a new generic approach based on a uinque hybrid scheme that could handle successfully other real-world reconstruction problem, such as shredded documents, broken pottery, etc. 10. General Type GA - Genetic Algorithm 11. The date of publication In press