Solving Archaeological Jigsaw Puzzles
Written by David Conrad   
Sunday, 13 January 2019

Archaeological artifacts are usually found in bits - and the broken fragments suffer from all sorts of degradation that makes it difficult to reassemble them. Recent research has come up with a novel algorithm for automatic reassembly that performed remarkably well on broken artifacts and frescoes. 

archpuzzles

Jigsaw puzzle solving is a NP-complete problem that crops up in many areas. Israeli researchers Niv Derech and Ayellet Tal of Technion and Ilan Shimshoni of the University of Haifa decided to concentrate on archaeology:

because the archaeological domain exposes the limits of current computer vision techniques. Archaeological artifacts are not “clean” and “nicely-behaved”; rather they are broken, eroded, noisy, and ultimately extremely challenging to algorithms that analyze or reassemble them. Therefore, from the point of view of vision, archaeology serves as an extremely challenging application area.

The algorithm they proposed is based on four key ideas:

First, in order to address fragment abrasion, we propose to extrapolate each fragment prior to reassembly. This reduces the continuity problem (predicting how to 'continue' the fragment) we are facing into a matching problem. Second, we suggest a transformation sampling method, which is based on the notion of configuration space, and is especially tailored to our problem. . Third, at the core of any puzzle solving algorithm lies the question of what makes a good match. We propose a new measure, which takes into account the special characteristics of the domain: the gaps between the pieces, color fading, spurious edges, the fact that the length of the matching boundary varies, and the imprecise transformations. Finally, our placement considers not only the above scores, but also our confidence in the match, which is influenced by the uniqueness of the match and the fragment size.

archalgo

 

The researchers evaluated their algorithm on dozens of real archaeological objects from the British Museum and frescoes from churches around the world. They found that it performed remarkably well, successfully reassembling the vast majority of these broken artifacts and frescoes.

archpuzzlesq

More details are given in their paper, Solving Archaeological Puzzles, which is available on arXiv.

More Information

Solving Archaeological Puzzles

Related Articles

Faster Jigsaw Solving

DARPA Shredder Challenge

Unshuffling A Square Is NP-Complete

Picture-Hanging Puzzles

To be informed about new articles on I Programmer, sign up for our weekly newsletter, subscribe to the RSS feed and follow us on Twitter, Facebook or Linkedin.

Banner


The University of Tübingen's Self-Driving Cars Course
22/03/2024

The recorded lectures and the written material of a course on Self-Driving Cars at the University of Tübingen have been made available for free. It's a first class opportunity to learn the in an [ ... ]



Couchbase's Coding Assistant Goes GA
11/03/2024

Capella iQ, the AI coding assistant for developers that makes interacting with Couchbase using natural language possible, has gone from private beta to being generally available.


More News

raspberry pi books

 

Comments




or email your comment to: comments@i-programmer.info

Last Updated ( Sunday, 13 January 2019 )