We revisit the problem of forming a coherent image by assembling independent pieces, also known as the jigsaw puzzle. Namely, we are interested in assembling tile panels, a relevant task for art historians, currently facing many disassembled panels. Existing jigsaw solving algorithms rely strongly on texture alignment to locally decide if two pieces belong together and build the complete jigsaw from local decisions. However, pieces in tile panels are handmade, independently painted, with poorly aligned patterns. In this scenario, existing algorithms suffer from severe degradation. We here introduce a new heat diffusion based affinity measure to mitigate the misalignment between two abutting pieces. We also introduce a global optimization approach to minimize the impact of wrong local decisions. We present experiments on Portuguese tile panels, where our affinity measure performs considerably better that state of the art and we can assemble large parts of a panel.
