In this paper a novel general methodology is introduced for the computer-aided reconstruction of the magnificent wall-paintings of the Greek island Thera (Santorini), painted in the middle of the second millennium BC. These wall-paintings are excavated in fragments and, as a result, their reconstruction is a painstaking and a time-consuming process. Therefore, in order to facilitate and speed up this process a proper system has been developed based on the introduced methodology. According to this methodology each fragment is photographed, its picture is introduced to the computer, its contour is obtained and subsequently all fragments contours are compared in a manner proposed herein. Both the system and the methodology presented here, extract the maximum possible information from the contour shape of fragments of an arbitrary initially unbroken plane object, to point out possible fragments matching. This methodology has been applied to two excavated fragmented wall-paintings consisting of 262 fragments, with full success but most important it has been used to reconstruct, for the first time, unpublished wall-paintings parts from a set of 936 fragments. 2 The discovery of the wall-paintings at Akrotiri of the Greek island Thera (Santorini), is of outstanding importance for human knowledge of the early Aegean world and not only. According to prominent archaeologists these wall-paintings rank alongside the greatest archaeological discoveries. The late professor Marinatos originated the excavations, which are now successfully continued by Professor Christos Doumas. As with the treasures of Pompeii and Herculaneum, the wall-paintings of Thera were preserved due to the seal of the pumice from the great eruption of a volcano [1]. As a rule, the walls decorated with paintings no longer survive. They collapsed together with their painted coat before the volcanic eruption, due to particularly strong earthquakes. Thus, a single painting is usually scattered into many fragments mixed with the fragments of other wall-paintings, too. The restoration of the wall-paintings from the fragments is a very painstaking and time consuming process frequently demanding many months or even years of dedicated, experienced personnel work for a single wallpainting restoration. Therefore, the development of a system that will contribute to the automatic restoration of these wall-paintings is of fundamental importance for this archaeological research, but for many others too, which face the problem of an image reconstruction from excavated fragments. Each excavated wall-painting fragment after being cleaned, is being photographed with a very strict protocol, so that very similar illumination conditions, a fixed distance of the fragment plane from the camera focus and minimal photo distortion are ensured. Subsequently, the obtained image is processed and eventually each photographed fragment is embedded into a white background frame, which we call the absolute frame of reference of the specific fragment (see Figure 2 ). The problem tackled in this paper may be considered to be associated with automatic jigsaw puzzle solving, too. However, as we will point out below, the two problems solutions manifest drastic and essential differences. In fact, a number of papers deal with automatic puzzle solving: In [31] a set of critical points, the isthmus point and the isthmus critical points that define a feature used in matching partial boundaries is employed. A similar global feature of isthmus is used for automatic jigsaw puzzle solving in [32] . In [29] a global jigsaw puzzle assembly algorithm is used consisting of two major substeps. The frame of the puzzle is assembled first and it is used as a starting point for assembling the entire puzzle; the global assembly is made via a method analogous to the "traveling salesman problem". In The problem of automatic reconstruction of the prehistoric city of Thera wall-paintings is in essence drastically different than the one of automatic jigsaw puzzle solving. In fact, 1. No a priori knowledge concerning the shape of each piece (fragment) is given and therefore one cannot presuppose the existence of breakpoints on the boundary curve of it. Actually, in practice, many fragments boundary curves have no breakpoints. As a consequence, division of the piece boundary in sides is totally meaningless, as well as corner detection. 2. No frame pieces exist, i.e. pieces whose at least one side is a straight line segment. Hence, the strategy of starting the puzzle solution from the frame reconstruction is equally meaningless and the jigsaw puzzle solution cannot be considered equivalent to the traveling salesman problem. 8. Finally, very frequently, many different wall-paintings are excavated mixed altogether, due to the collapse of the two or three floor building whose walls were initially decorated by those paintings. Hence, one may state that the problem of the automatic jigsaw puzzle solution is a "subcase" of the problem tackled in this paper. In fact, one may define the approach introduced here as an attempt to extract the maximum possible information from the contour of a set of fragments in order to achieve the initial image/object reconstruction. Therefore, the method introduced here and the related system can be very well employed to reconstruct any broken into fragments object employing contour shape information only. Although the method and system presented here have proven very powerful in reconstructing wall paintings for the first time, we must stress that, if one wishes to develop a complete system of automatic reconstruction of an image from its constituent fragments, one may take into account many other parameters, too, such as a) matching between internal contours of the fragments b) colour continuation between actually adjacent fragments, c) continuation of the thematic content d) crack continuation e) geological texture of the side opposite to the painted one, etc.
In REF , the problem of fragmented wall-paintings reconstruction is treated, in the case where the only available information is the set of 2D fragments" images; the approach is effective but it suffers from the intrinsic restriction that there is no available three-dimensional information of the constituent parts.
Contour-shape based reconstruction of fragmented, 1600 bc wall paintings
IEEE Transaction on Signal Processing
Computer Science Mathematics