Researchers from the Isreal Institute of Technology – Technion, have proposed a new method for solving archeological puzzles. In fact, the proposed method is a general puzzle solving method which they applied in the archeology context.
Puzzles have always been a big challenge both for humans as well as for computers (computational solvers trying to efficiently solve different puzzles). But “puzzle” is a rather general term and therefore puzzles can differ very much one from another. Even the most common type of puzzles (where pieces are all square and build up a natural image
can be solved) are not easy to be solved.
But puzzles can be much more difficult than that. Take for example restoring shredded documents or restoring archeological artifacts.
In the latter case, to tackle the problem of restoring archeological artifacts, the researchers proposed a fully-automatic and general algorithm for puzzle solving. There are a number of challenges that come along with the problem of restoring artifacts in archeology: the fragments (or pieces) are of general shape; fragments are abraded (especially at boundaries where strongest matching cues exist) and the domain of valid transformations is continuous.
To overcome these challenges, they propose 4 key ideas: 1) to extrapolate each fragment (to reduce the continuity problem), 2) they suggest a specific transformation sampling method, 3) they propose a new dissimilarity measure based on: the gaps between the pieces, color fading, spurious edges, the fact that the length of the matching boundary varies, and the imprecise transformations and 4) to use confidence in the match while placing the fragments.
This kind of solution seems promising but it can be successful only if the first part does the job well. Correct extrapolation of the edges of each fragment is crucial for the matching that will be done at a later stage.
The researchers define the extrapolation as predicting a k-pixel wide ring around the fragment. To do so they used a patch-based synthesis method. Then they define valid transformations – “where the pixels of the original fragments do not overlap after applying the transformation, but the extrapolated pixels of the fragments do”. Finally, they compute dissimilarity score to find good matches based mostly on the edge color features and they use a greedy placement strategy.
Their results show that the proposed method is able to solve puzzles of archeological fragments. The full paper can be read on arxiv.