  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.
