January 10, 2019 feature
A new algorithm for solving archaeological puzzles
A team of researchers at Technion and the University of Haifa have developed a new computer vision approach for solving archaeological puzzles. In their paper, pre-published on arXiv, they introduce a general algorithm that can automatically reassemble fragments of archaeological artifacts.
"Puzzle solving has been an intriguing problem for many years," the researchers write in their paper. "It has numerous application areas, such as in shredded documents, image editing, biology and archaeology."
Researchers have been trying to develop tools that can automatically solve puzzles for decades. The first computational solver, introduced back in 1964, was able to tackle nine-piece puzzles. Today, most state-of-the-art techniques for puzzle solving are designed to work on natural images using color matching, shape matching or a combination of both.
The researchers at Technion and the University of Haifa decided to focus on puzzle solving in the field of archaeology. At the time of their discovery, most archaeological objects are in a poor or fragmentary state. Therefore, archaeologists manually reassemble these fragments so they can examine them further. Computer vision tools could greatly simplify this arduous and time-consuming process by automating archaeological puzzle solving.
"We concentrate on archaeology not only because cultural heritage has been acknowledged worldwide as an important goal, but also because the archaeological domain exposes the limits of current computer vision techniques," the researchers explain in their paper. "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 researchers developed an approach that addresses the three major differences between square-piece puzzles of natural images and images of archaeological artifacts, which are associated with abrasion, color fading and continuity. In archaeological artifacts, abrasion often creates gaps between the pieces, making it harder to match adjacent fragments.
In addition, color fading can result in spurious edges, which need to be distinguished from real edges and gradients. Finally, in natural-image puzzles with square pieces, a fixed number of transformations exist among any pair of pieces, but in archaeological artifacts, valid transformations belong to a continuous space, further complicating the puzzles.
"We propose a novel algorithm that handles these difficulties," the researchers write. "It 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."
According to the researchers, at the core of any puzzle solving lies the question: What makes a good match? To answer this, they used a new measure that takes into consideration the unique characteristics of archaeological puzzles, including the gaps between pieces, color fading, spurious edges, varying lengths of matching boundaries and imprecise transformations. In addition, their algorithm places the pieces based on their confidence in the match, which is influenced by the uniqueness of the match and fragment size.
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 frescos.
H. Freeman et al. Apictorial Jigsaw Puzzles: The Computer Solution of a Problem in Pattern Recognition, IEEE Transactions on Electronic Computers (2007). DOI: 10.1109/PGEC.1964.263781
© 2019 Science X Network