Skip to navigation – Site map

HomeIssues12ArticlesSemantic-based automated reassemb...

Articles

Semantic-based automated reassembly of heritage fragments

Marie-Morgane Paumard

Abstracts

Artificial intelligence provides archeologists and conservators with solutions to many problems. Among them, artifact reconstruction would surely benefit from smart automation. After the spread of the vision-based reassembly techniques, that use either fractures or pattern continuity, the last decade has seen the rise of semantic-based algorithms that allow performing computer vision tasks using the meaning of what is represented. We expect that such methods would help to solve some of the most difficult heritage problems that cannot be addressed by traditional methods, often because the fragments are too eroded to make continuity-based deductions.

Top of page

Full text

Introduction

1The archaeological site of Vaux-de-la-Celle (Fig.1), in the Val d'Oise, is an exceptional Gallo-Roman sanctuary made up of the ruins of a temple with two cells surrounded by a circulation gallery, pools, and a theater that can accommodate up to 8,000 people (Barrière 2019).

Fig.1 Vaux-de-la-Celle

Fig.1 Vaux-de-la-Celle

The blocks from Vaux-de-la-Celle (a) are stored for future reassembly of the temple (b, c).

©La Gazette Val d’Oise, ©Le Parisien, ©Association APSAGE.

2The first fanum is dated to the middle of the first century AD and the architectural ensemble was built a few decades later. During the 3rd century, the site was gradually abandoned after the 3rd century and its monuments served as a stone quarry until modern times. The first excavations were undertaken in 1935 by Pierre Orième. From 1960, the team of volunteers led by Pierre-Henri Mitard discovered most of the known remains: theater, main temple and annex temples, settlements, sacred area. The existence of an agglomeration was brought to light in the early 1990s. The 5,000 ritual and everyday objects discovered, as well as the sculpted blocks, are kept at the Archaeological Museum of Val d'Oise. Archaeologists now want to reassemble the building from the hundreds of sculpted blocks. The task was too complex for people to undertake, and it is thanks to advances in artificial intelligence that computer reassembly is now possible. This reassembly problem gave rise to the Archepuz-3D research project, funded by the Heritage Science Foundation, which aims to develop a 3D assembly algorithm of archaeological blocks. Vaux-de-la-Celle is one of the two sites selected for the project. Its sculpted blocks are being digitized by photogrammetry and 3D acquisition, and will ultimately constitute a dataset. In December 2019, 55 blocks were digitized. The other site selected is the Roc-aux-Sorciers, a rock shelter dating from the Upper Paleolithic, whose sculpted ceiling has collapsed (Pinçon 2009).

3Sets of heritage fragments are characterized by the erosion of the pieces, the absence of certain pieces, and the mixture of pieces from several objects, which increases the difficulty of the reassembly. The automatic methods seek to match the contours (Papaioannou 2017, Sizikova 2017) and visual continuities of the fragments (Son 2014, Paikin 2015). When they are damaged, it is no longer possible and experts use semantics to make sense of the whole. Having an algorithm capable of understanding semantics would overcome the limitations of current models. In recent years, deep learning algorithms have learned to use semantic features to perform different tasks, such as detecting cancer cells and translating documents. Our goal is to design a similar method to solve all types of archeological jigsaw puzzles. The method presented here is as effective as the experts on a simple semantic task, solving the 9-square 2D fragment jigsaw puzzle. Algorithms that use visual semantic reasoning are recent and are improving little by little. Ultimately, the semantic methods should be versatile and allow the reassembly of many archaeological sites.

4Our contributions include an extension of the 3×3 problem introduced by Doersch et al. (Doersch 2015) that allows solving jigsaw puzzles from pairwise relations: we proposed three reassembly solving methods (greedy, exact, and heuristic). We extended the original setup to deal with missing fragments and outsider fragments, which are frequent in archaeology (Paumard 2020). We also propose a new dataset of 14,000 heritage images, a refined neural network architecture, few metrics to assess the reassembly quality, and merging functions (Paumard 2018). In this article, we present the basics of deep learning and the main ideas of our methods to focus on the results and the potential applications for archaeologists and conservators.

Theoretical notions of deep learning

5Given data, a deep learning algorithm is trained to answer a question, such as: where are the faces in each photography? To solve a jigsaw puzzle, a relevant question is: what is the relative position of two fragments? The answer can then be: the first fragment is above and to the right of the second. An algorithm based on this question learns to organize the pairs of fragments into nine categories (that we call “classes”). The first eight correspond to the main position relations (cardinal and intercardinal directions). The ninth class indicates that the two fragments are not adjacent.

6To predict the class, we use a neural network, which applies a succession of operations to the data, to obtain an answer to the question. A neural network is organized in several layers, each containing thousands of nodes; each node contains an operation. The nine nodes in the last layer correspond to the classes and return the probability that it is the correct answer. In the beginning, the operations of the node are randomly initialized and the prediction errors are high. To minimize them, we must optimize each node operation. Theoretically, if the number of nodes is sufficient and the operations are well-chosen, the network can answer any question.

7Deep learning consists of automatically associating each node with a relevant operation to answer the question. The network is asked to predict answers for a large number of images and compare its predictions to the solutions. Then, it adjusts slightly the nodes operations to decrease the last prediction errors. The network is thus optimized by trial and error until the prediction error is acceptable. Therefore, when the dataset is too limited (either in quantity or diversity of pictures), the neural network is not able to generalize well and will provide weak answers to new problems.

8At the end of the learning phase, the neural network can predict responses for unknown data. The accuracy of the answer depends on the difficulty of the question, the number of layers and nodes in the neural network, and the data on which the network has been trained.

Method

9Solving a jigsaw puzzle amounts to predicting the relative position of all pairs of fragments and finding the best arrangement (Fig.2). For this purpose, we use a dual-head convolutional network that extracts the features of a pair of fragments made of the central fragment and one of the lateral fragments. The features are then concatenated and abstracted so that the last layer predicts the spatial relation between them. Once the predictions have been made for all pairs, we can solve the puzzle: we only have to find the best arrangement among all available assemblies. If we assume that the neural network is perfect (i.e., it always assigns the highest probability to the correct class), the correct reassembly is the one that maximizes the sum of the probabilities at the output of the neural network. This calculation is performed using the shortest path algorithm in the pruned graph that links fragments to positions. The graph is weighted by the neural network predictions. We proposed two other reassembly algorithms: a greedy one that places the fragments in scores order and an exact one that explores all the possible reassemblies (Paumard 2018).

Fig.2 Resolution method

Fig.2 Resolution method

The green lateral fragment is compared to the red central fragment: the features of each fragment are extracted (b) and then the neural network predicts the relative position (c). Here, the most likely position is to the left of the red fragment. The predictions are organized in a graph (d): each line contains all the remaining positions. Thus, the position of the blue fragment depends on the location of the green fragment. The final resolution (e) is obtained after traversing the graph.

©Marie-Morgane Paumard.

10To train the neural network, we need to have enough data for which we know the answer. Since it is not possible to disassemble many real 3D objects, we train the network on images. There are three other reasons for our use of 2D. First, thanks to the relative depth maps or different lights, we capture in 2D all the asperities of a 3D face. Secondly, in the case of the Vaux de la Celle site, only one face of the block is sculpted, so a 2D representation is sufficient. For the corner blocks, we project the two faces side by side. Thirdly, using 2D images undoubtedly improves the computation time. To induce neural networks to use semantics, we smooth the contours and remove continuities from the patterns by trimming the fragments by a quarter of their surface.

11The training dataset was created from royalty-free photographs of works at the Metropolitan Museum of Art (MET). This dataset contains images of frescoes and sculptures, which is closer to the applications of our project than the other datasets. Besides, the lenses used by the MET for photography do not induce distortions on the green channel, which would have been learned instead of semantics by the neural network (Kraus 2018).

12Each image is divided into 9 parts separated by a 48-pixels gap, mimicking an erosion of the fragments (Fig.3). Then, we extract the center fragment and one of its 8 neighbors. Each fragment is of size 96×96 pixels, and we randomly move the location of the fragment by ±7 pixels in each direction. To populate the 9th class, we use random fragments extracted from other images.

Fig.3 Dataset preparation

Fig.3 Dataset preparation

The orange outline shows the puzzle limit and the white outlines show the lateral fragments that are used. The green outline shows the central fragment.

©Marie-Morgane Paumard.

Results

13In this section, we present the scores obtained on the MET dataset for the neural network training (1) and then for the MET reassembly (2). Last, we use the trained neural network to assemble fragments from other heritage datasets (3).

14First, the neural network is trained to classify 10000 training images, from which 9 fragments are extracted. The network can predict the correct position for 65% of the fragment pairs, which is similar to the performance of an expert. We outscore the previous state-of-the-art algorithms by 25% (Doersch 2015) and show that the neural network is very effective to identify the supernumerary fragments (assigned to the ninth class). The main difficulty of single-class prediction lies in the background fragments. As we cut the images square, some pieces of the jigsaw puzzle only contain plain background and no part of the artifact. Therefore, the background fragments are interchangeable, and the algorithm cannot find the original position of the background fragments.

15Second, we apply the reassembly algorithms to the MET dataset. We use two metrics: how many fragments are well placed and how many puzzles are perfectly solved. We obtain 90% of well-placed fragments and 30% of perfectly solved images, which represents a relative improvement of 15% compared to a greedy algorithm. We also outperform Noroozi and Favaro (Noroozi 2016) by at least 10% depending on the model parameters. We performed analyses on the impact of missing and supernumerary fragments. We found out that the major limitation was computation power, as the scores drop slowly with fragments addition or removal. Besides, we changed the parameters of the photo-shot (distance, angle, lens, lighting) and we did not observe a drop in performance, which proves that our algorithm is robust to these variations and that it makes use of semantics. Last, we analyzed the three major types of images of the MET dataset: artifacts, engraving and texts, and painting. Each type is almost homogeneously distributed. We found out that the puzzle-wise score of paintings is surprisingly low (12%). It means it is harder to reassemble painting puzzles despite their semantic consistency. By contrast, artifacts score almost 40% and engravings reach 25%. A comparative analysis on the fragments-wise score revealed that most of the reassemblies of the paintings only had very few misplaced fragments. We deepened the study of text reassembly and we demonstrated that our algorithm based its answers on the borders, margins, frames, columns, and titles.

16Last, we reassemble images from four datasets using the neural network trained on MET images (Fig.4). The first dataset is ImageNet, which is the standard dataset for computer vision tasks. We obtain even better scores on ImageNet compared to MET because the fragments are very diverse and there are no plain background fragments (48% of perfect reassembly). The second dataset was obtained from Google Images “bas-relief” search. It is a reasonable approximation of real heritage puzzles and contains 200 photographs. We reached 40% of perfect reassemblies, notably because there are no background fragments in the images. The third dataset is made of a hundred and so screenshots of scanned blocks from the Vaux-de-la-Celle Gallo-Roman temple. These scans preserve the color and the relief of the blocks.

17We obtain 28% of perfect reassembly, which is close to MET’s scores because the datasets are similar. Well-solved puzzles are rare, but most fragments are usually well-placed. The fourth dataset is made of crops of the Roc-aux-Sorciers frieze. The carved shapes display a low contrast that was not understood by the neural network so we were not able to solve a single puzzle. However, our algorithm correctly places one-third of the fragments, which is still better than a random arrangement.

Fig.4 Results on heritage dataset

Fig.4 Results on heritage dataset

The two images on the left are from the “bas-relief” dataset. The two central images are from Vaux-de-la-Celle’s 3D scans. The two images on the right are from Roc-aux-Sorciers. The red outline points out the misplaced fragments.

©Marie-Morgane Paumard.

18Besides, carvers of Roc-aux-Sorciers used the asperities of the wall to carve their art; therefore, the semantics data are hard to detect on the stones. We recommend preprocessing the images to make the significant shapes appear more clearly to the neural network. This potentially could be automated by preceding our neural network with an algorithm that specializes in significant feature extraction from this type of data. To ensure the quality of the result, it should be tested on enough data—so to say, thousand of (ideally prehistoric) bas-reliefs. An alternative would be to annotate data in such a way that highlights the semantics.

Discussion

19Our model is limited by the comparison of fragments to a single central fragment: the semantics of the set are not taken into account to solve the puzzle. On the other hand, it allows working with missing or supernumerary fragments, contrary to methods that take into account the semantics of the set. We are developing alternatives that combine the strengths of each method. To give a brief insight, our main focus is on iterative reassembly, where the neural network compares the next fragment to place to the current state of the reassembly, rather than to the central fragment only. As of today, we reached a 10% of improvement on the MET reassembly task with the new method (Paumard 2021). An interesting reassembly solver was developed by Bridger et al. (Bridger 2020): the authors obtained excellent reassembly scores on hundred fragments puzzles. However, the space between the fragments is much lower than our 50% (about 5%). Therefore, with low or no erosion, traditional computer vision methods are probably as pertinent to reassemble artifacts and monuments.

20To improve our heritage dataset scores, we can implement several levers. The most helpful would be to digitize more data. An idea to explore would be to generate images that look like Vaux-de-la-Celle and Roc-aux-Sorciers. Then, we should first apply a contour-based algorithm, hoping that the erosion is low. If no pertinent reassembly is found, a more robust solution that combines contours, patterns, and semantics should be considered. The second lever to improve the scores would be to implement new algorithms. A third option would be to design an interactive mode, where archaeologists and algorithms solve together the reassemblies. An additional option would be to improve the quality of the data, in both training and testing datasets. For example, we could present grazing-ligh images to the neural network so it can better "understand" the relief. The use of multispectral data or depth map in adjunction with the RGB data should also improve the reassembly precision. Such additional data should always be contained by the digitized object; it cannot be manually added, otherwise it is necessary to develop an algorithm to handdle it from the semantics, which is a very similar problem to the reassembly. A major drawback is that training on such extensive data is vital, without which the algorithm cannot use it to solve new problems from the other datasets. Therefore, one should always favor data as similar as possible to the training data.

21The two main extensions are the number of fragments and the case of 3D puzzles. Bigger jigsaw puzzles can be addressed by designing a meta solver that would merge 3×3 reassemblies, by implementing a neural network that can compare more fragments, or by designing a reassembly algorithm that can cope with more data. On the 3D reassembly, we face several issues. First, the lack of real data, i.e., blocks that can be broken into pieces that we would know how to reassemble. A solution would be to generate artificial fractures on 3D scans with modeling software. However, the handcrafted data should be realistic enough to allow transferring the abstractions learned by the neural network to real blocks. Second, learning from 3D data requires a lot of computation power, so we may have to decrease the resolution of the digitized fragments. Third, understanding the semantic of 3D data is more complex than 2D data, and we expect algorithms to not be able to reach the current accuracy scores. An alternative to 3D models would be to use a 2D depth map. Such depth maps are similar to the images from Vaux-de-la-Celle, that we reassembled correctly.

22Beyond archaeology, semantic-based reassembly has many other applications such as genome biology, medicine or forensic science. In a broader perspective, this work mixes visual understanding (neural networks) and choice space exploration (search algorithms). Such hybrid approaches are potent and can be applied to a wide range of domains, from autonomous driving to medical advisory.

Top of page

Bibliography

Barrière, V., Blondeau, C., Collinot, F. (2019). Les Vaux-de-la-Celle, une aventure archéologique.

Bridger, D., Danon, D., Tal, A. (2020). Solving Jigsaw Puzzles with Eroded Boundaries. Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR).

Doersch, C., Gupta, A., Efros, A.A. (2015). Unsupervised Visual Representation Learning by Context Prediction. IEEE International Conference on Computer Vision (ICCV).

Kraus, R. (2018). A museum without walls: How the Met is bringing its ancient collection online. Mashable, https://mashable.com/article/the-met-museum-api.

Noroozi, M., Favaro, P. (2016). Unsupervised Learning of Visual Representations by Solving Jigsaw Puzzles. The European Conference on Computer Vision (ECCV).

Paumard, M.-M., Picard, D., Tabia, H. (2018). Image Reassembly Combining Deep Learning and Shortest Path Problem. The European Conference on Computer Vision (ECCV).

Paumard, M.-M., Picard, D., Tabia, H. (2020). Deepzzle: Solving Visual Jigsaw Puzzles with Deep Learning and Shortest Path Optimization. IEEE Transactions on Image Processing (TIP).

Paumard, M.-M. (2021). Solving jigsaw puzzles with deep learning. Ph.D. dissertation.

Paikin, G., Tal, A. (2015). Solving multiple square jigsaw puzzles with missing pieces. Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR).

Papaioannou, G., Schreck, T., Andreadis, A., Mavridis, P., Gregor, R., Sipiran, I., Vardis, K. (2017). From reassembly to object completion: A complete systems pipeline. Journal on Computing and Cultural Heritage (JOCCH).

Pinçon, G. (2009). Le Roc-aux-Sorciers : art et parure du Magdalénien. Catalogue des collections, https://catalogue-roc-aux-sorciers.fr.

Sizikova, E., Funkhouser, T. (2017). Wall painting reconstruction using a genetic algorithm. Journal on Computing and Cultural Heritage (JOCCH).

Son, K., Hays, J., Cooper, D.B. (2014). Solving square jigsaw puzzles with loop constraints. The European Conference on Computer Vision (ECCV).

Top of page

List of illustrations

Title Fig.1 Vaux-de-la-Celle
Caption The blocks from Vaux-de-la-Celle (a) are stored for future reassembly of the temple (b, c).
Credits ©La Gazette Val d’Oise, ©Le Parisien, ©Association APSAGE.
URL http://journals.openedition.org/ceroart/docannexe/image/8053/img-1.jpg
File image/jpeg, 450k
Title Fig.2 Resolution method
Caption The green lateral fragment is compared to the red central fragment: the features of each fragment are extracted (b) and then the neural network predicts the relative position (c). Here, the most likely position is to the left of the red fragment. The predictions are organized in a graph (d): each line contains all the remaining positions. Thus, the position of the blue fragment depends on the location of the green fragment. The final resolution (e) is obtained after traversing the graph.
Credits ©Marie-Morgane Paumard.
URL http://journals.openedition.org/ceroart/docannexe/image/8053/img-2.jpg
File image/jpeg, 110k
Title Fig.3 Dataset preparation
Caption The orange outline shows the puzzle limit and the white outlines show the lateral fragments that are used. The green outline shows the central fragment.
Credits ©Marie-Morgane Paumard.
URL http://journals.openedition.org/ceroart/docannexe/image/8053/img-3.jpg
File image/jpeg, 569k
Title Fig.4 Results on heritage dataset
Caption The two images on the left are from the “bas-relief” dataset. The two central images are from Vaux-de-la-Celle’s 3D scans. The two images on the right are from Roc-aux-Sorciers. The red outline points out the misplaced fragments.
Credits ©Marie-Morgane Paumard.
URL http://journals.openedition.org/ceroart/docannexe/image/8053/img-4.jpg
File image/jpeg, 262k
Top of page

References

Electronic reference

Marie-Morgane Paumard, Semantic-based automated reassembly of heritage fragmentsCeROArt [Online], 12 | 2020, Online since 31 August 2021, connection on 18 September 2021. URL: http://journals.openedition.org/ceroart/8053; DOI: https://doi.org/10.4000/ceroart.8053

Top of page

About the author

Marie-Morgane Paumard

Graduated from École Normale Supérieure de Rennes, Dr. Marie-Morgane Paumard specialized in deep learning and operations research. During her Ph.D., she proposed methods to automatically assemble heritage fragments. Her thesis was funded by the Fondation des Sciences du Patrimoine and was defended in December 2020 in the ETIS and LIGM laboratories, Paris area, France. She received the French L'Oréal-UNESCO Young Talents award for Women in Science in October 2020 for her doctoral work.

Top of page

Copyright

Licence Creative Commons
CeROArt – Conservation, exposition, restauration d'objets d'arts est mis à disposition selon les termes de la licence Creative Commons Attribution - Pas d'Utilisation Commerciale - Pas de Modification 4.0 International.

Top of page
  • DOAJ - Directory of Open Access Journals
  • OpenEdition Journals
Search OpenEdition Search

You will be redirected to OpenEdition Search