A Novel Information System for the Automatic Reconstruction of Highly Fragmented Objects with Application to the Reassembly of Prehistoric Wall Paintings and Vessels

Abstract

This paper presents a set of novel methodologies and the corresponding information system, which has been developed for processing 2D and 3D representations of fragmented archaeological finds, by means of which automated virtual and, eventually, actual reconstruction of the finds may be accomplished. The aforementioned system has been designed in order to provide ensembles of potentially matching fragments, together with a corresponding matching probability. One of the main novelties of the presented methodologies and the associated information systems is the use of many mathematical criteria, properly ordered, leading to fragmented pieces’ matching. These criteria employ notions and theorems of Differential Geometry, Calculus of Variations, and Algebra. The systems have been tested to the reassembly of parts of important archaeological finds, such as segments of wall paintings of the Minoan and the Mycenaean era. On the basis of these methodologies, parts of prehistoric wall paintings have been spotted for the first time, while the information systems’ matching proposals have been confirmed by scholars.

1 Introduction: The Goal of the Present Work

In the present paper, new methodologies are presented in the fields of pattern analysis, pattern recognition, and curve and surface fitting. These methodologies support the development of an integrated information system that successfully tackles the actual problem of fragmented objects’ automated reconstruction/reassembly. The main motive and the final goal of the aforementioned development are the preservation of the cultural heritage, in the sense that the corresponding information system may substantially contribute to the reassembly of important archaeological finds excavated in numerous fragments. In fact, both the introduced methodologies, as well as the associated information systems, have been so far applied in the automated reassembly of (a) parts of frescos excavated at Akrotiri , Thira , in hundreds or even thousands of fragments and (b) parts of prehistoric wall paintings unearthed in Tiryns and Mycenae , the excavation of which was first supervised by Heinrich Schliemann. The Mycenaean fragments which are stored in the laboratories of the National Archaeological Museum of Athens, as well as the Akrotiri fragments, are of great importance for archaeology, history, and cultural preservation.

2 Reassembly of Fragmented Objects on the Basis of Their 2D Images

2.1 The Developed Method for the Virtual Reassembly of Fragmented Wall Paintings

At first, we have photographed numerous fragments of wall paintings carefully embedded in thin sand with the coated surface on top. Next, we have applied the following steps:

• Step 1. We have applied a specifically developed image segmentation method [1] in order to extract the image of the upper painted surface of each fragment from its background.

• Step 2. Next, we have extracted the contour of each fragment 2D representation, and we have refined it by means of dedicated morphological filters [2].

• Step 3. We have generated all rotated versions of each fragment’s representation by angles ${\theta}_i=\frac{i}{360},i=1,2,\dots, 259$.

• Step 4. We have the fragment with the larger upper surface as the “fixed” one. Then, we have brought each other fragment representation in virtual contact with the fixed fragment; we did this for all rotated versions of the second fragment, which for this reason we called “rotated” fragment.

For each such tested pair of fragments and at the specific virtual contact position of them, we have applied the following criteria:

2.1.1 Criterion 1

On the contour of the fixed fragment, which we call “fixed contour”, we have defined all chains of L _C consecutive pixels; for each such chain, we use the term “fixed chain”. Next, we have dynamically constructed the counterpart chain on the contour of the rotated fragment, of maximum acceptable length L. Then, we have computed the sum of angles μ on the fixed and rotating chains, where each angle is evaluated via the internal product of the unit tangent vector at each point of the corresponding chain with $\overrightarrow{i}$ (the x-axis unit vector). Subsequently, by means of Calculus of Variations , we have demonstrated that this sum of angles must always satisfy the following inequality:

$$\begin{array}{l}\mu \le {\mu }_{\text{max}}=\sqrt{d^2+{\left(\frac{2\mathrm{Inner}\mathrm{space}\left(0\mathrm{x}\mathrm{E}\mathrm{F}07\right)E}{d}\right)}^2}arctan\left(\frac{2\mathrm{Inner}\mathrm{space}\left(0\mathrm{x}\mathrm{E}\mathrm{F}07\right)E}{d^2}\right)\hfill \\ +\left(L-\sqrt{d^2+{\left(\frac{2\mathrm{Inner}\mathrm{space}\left(0\mathrm{x}\mathrm{E}\mathrm{F}07\right)E}{d}\right)}^2}\right)\mathrm{\pi }/2\hfill \end{array}$$

(62.1)

where E is the maximum area enclosed by fixed and rotating chain and d is the Euclidean distance between the beginning and the end of the fixed chain. If this inequality is not satisfied, then we decide that the specific relative position of the two fragments is not an acceptable matching one, and hence, we proceed to the next relative position of the two fragments, or if all relative positions have been taken into consideration, we select another couple of fragments for testing.

On the contrary, if inequality (62.1) indeed holds, we proceed to the next criterion.

2.1.2 Criterion 2

For each relative position of the two fragments in hand that criterion 1 is satisfied, we check if an overlap between their 2D representations exists. If such a virtual overlap does exist, then we estimate the minimum necessary parallel translation, say $\overrightarrow{\delta}$, needed to lift the overlapping.

After applying this parallel translation $\overrightarrow{\delta}$ to the rotated fragment, we proceed to the next and final criterion.

2.1.3 Criterion 3: The Final Matching One

At this relative position of the two fragments in which both criteria 1 and 2 are satisfied, we compute the area α of the 2D domain enclosed by the fixed and rotated chains, and we demand that this area is smaller than the maximum area E, namely, that the following inequality holds:

$$ \alpha \le E $$

(62.2)

If this inequality is indeed satisfied at the current position, we assume that the two fragments do match at this position. Otherwise, we proceed to the next relative position of the two fragments in hand, or if all relative positions of these two fragments have been taken into consideration, we select another couple of fragments for testing.

2.2 Application of the Method to the Virtual Reassembly of Akrotir i, Thira , Wall Paintings’ Parts

We have applied the aforementioned methodology and the associated information system we have developed in the virtual reassembly of wall paintings excavated in Thir a (Santorini). These wall paintings were painted in the middle of the seventeenth century BC and are excavated in particularly numerous fragments. Parts of these wall paintings were successfully reassembled by the developed system for the first time , and a number of them are presented below (Fig. 62.1).

Fig. 62.1

Example of wall painting parts automatically reconstructed by the 2D system for the first time

3 Reassembly of Fragmented Objects on the Basis of Their 3D Representations

3.1 Automated Reconstruction of Fragmented Objects with an Almost Flat Surface: The Wall Paintings Case

At first, we have performed a 3D scanning of the fragments of interest, by means of an IMETRIC GMBH scanner, specially configured for safe capturing of archaeological finds’ representations. The scanning system consists of two cameras and a high-quality DLP projector with 3–7 μm resolution.

Subsequently, we developed a method [3, 4] which automatically offers the upper almost flat surface of each fragment. The method employs an auxiliary geometric shape consisting of three equidistant planes to spot the almost flat surface bounded by the outer planes and best approximated by the middle one (Δ). We have also determined the axis (I _m) vertical to plane Δ with the minimum moment of inertia. We did that in order to rotate each fragment via Euler angles in such a way that its I _m axis becomes parallel to axis z ^’ z. Next, we have generated a set of rotated versions of each fragment around its I _m axis via a sequence of angles θ _m = m δθ, where δθ is a very small angle, say 1^°, and m = 1, 2, … so that the entire 360^° angle is spanned. We emphasize that the aforementioned procedure is applied once for each fragment separately before applying the matching process that will be described below.

• Step 1. For each tested pair of fragments, we have considered the one with the larger upper surface as the “fixed” one, which is compared with all the previously generated rotated versions of the other, called “rotated”.

• Step 2. We have selected a comparison length L _c; with the term “comparison length”, we intend to describe the length of the contours of the almost flat surfaces of the two fragments, which virtually are in contact at an actual matching position. We have applied the developed methodology for a large class of comparison lengths, ranging from 1.5 cm to 10 cm approximately.

• Step 3. We have also chosen the average distance h between the lateral surfaces of the two fragments at an acceptable position. We let the value of h range from 0.2 to 1.2 mm. Intimately connected to L _c and h is “the maximum acceptable volume” τ ^T of the 3D domain bounded by the lateral surfaces of the two fragments, which are in contact at this position.

For each pair of tested fragments and each choice of L _c and h, we have virtually placed the rotated fragment in contact with the fixed one exhaustively. In each such position tested for probable matching, we have applied the following criteria, three of which are necessary and one is sufficient:

3.1.1 Criterion 1

We check the discrepancy of the geometric characteristics of the two compared fragments’ upper contours locally. This discrepancy must always be smaller than an upper bound estimated by means of Principles of Calculus of Variations and of Differential Geometry. In fact, we have proved that the following inequalities must always hold at an actual matching position:

$$ \gamma \le {\gamma}_{\mathrm{ap}} $$

(62.3)

$$ {L}^{\mathrm{R}}<\_{L}_{\mathrm{max}}^{\mathrm{R}} $$

(62.4)

where γ is the angular distance of the two fragments’ upper contours at the specific relative position of them, γ _ap is the maximum acceptable such angular distance, L ^R is the length of the rotated contour “in contact” with the fixed one, and ${L}_{\mathrm{max}}^{\mathrm{R}}$ is the maximum acceptable contour length; quantities γ and ${L}_{\mathrm{max}}^{\mathrm{R}}$ have been evaluated by means of Calculus of Variations .

If one of the two inequalities (62.3) and (62.4) is not satisfied, then we de facto assume that the tested relative position of the two fragments is not an acceptable match, so we proceed in testing the next relative position.

If, on the contrary, both inequalities (62.3) and (62.4) are satisfied, we proceed to testing if the second criterion holds at the specific position of the two fragments.

3.1.2 Criterion 2

Let E ^F, E ^R be the lateral surfaces of the two fragments being “in contact” at their current relative position. We check the discrepancy of geometrical characteristics of E ^F and E ^R once more by means of Calculus of Variations and Differential Geometry.

In particular, we consider the surface integral of angles:

$$ \mu ={\oint}_{\partial V}\arctan \left(\frac{\overrightarrow{n}\cdot j\hat{\mkern6mu} }{\overrightarrow{n}\cdot j\hat{\mkern6mu}}\right)\mathrm{d}S $$

(62.5)

where ∂V is the closed surface, which bounds the domain V formed by E ^F and E ^R, $\overrightarrow{n}$ is the unit vector normal to ∂V outwards to V, and $\widehat{i},\widehat{j}$ are the unit vectors of the x and y coordinate axis, respectively. Then, we have established that the following inequality must always hold at an acceptable matching position:

$$ \mid \frac{\mu }{\varDelta \theta \varDelta z}\mid \le \mid \ln \left(\frac{r_T}{r_0}\right)\mid +\mid \frac{\varDelta \theta}{2}+\frac{\varDelta z}{6{\tau}^T}\left[-{r_0}^2+\frac{1}{\varDelta \theta \varDelta z}\underset{\theta_0}{\overset{\theta_T}{\int }}\left( Tr{\left(\theta, T\right)}^2- Sr{\left(\theta, S\right)}^2\right)\mathrm{d}\theta \right]\kern0.125em \mid $$

(62.6)

where r _T, r ₀ are the distances of the lateral surfaces of V from axis Ι _m of the fixed fragment, Δθ = θ _T − θ ₀ is the dihedral angle with which axis Ι _m “sees” surface E ^R, Δz is the height of domain V, and r(θ, Τ), r(θ, S) are the upper and lower contour curves of E ^R.

If inequality (62.6) is violated in the current relative position, then we deduce that this does not correspond to an actual matching, and, thus, we move on the next position.

On the contrary, if (62.6) holds, then we proceed in testing the validity of the subsequent criterion 3 at the specific position of the two fragments.

3.1.3 Criterion 3

At each relative position of the two fragments tested for matching at which criteria 1 and 2 are already satisfied, we check if a virtual overlapping between the two fragments occurs. If such an overlapping does take place, then we lift it in an optimal manner, by computing the corresponding minimum necessary parallel translation, say $\overrightarrow{\delta}$.

Next, we apply this parallel translation $\overrightarrow{\delta}$ to the rotated fragment and we reapply in this position criteria 1 and 2. If one of them is not satisfied in this new relative position of the two fragments, then we drop this position and we proceed to the next one to be tested. If both criteria 1 and 2 are satisfied, we proceed to checking the next and final criterion.

3.1.4 Criterion 4: The Final, Sufficient One

At this relative position of the two fragments, we form the 3D domain V bounded by the lateral surfaces E ^F and E ^R of the fixed and rotated fragment, respectively, as shown in Fig. 62.2.

Fig. 62.2

An example demonstrating the content of the criterion 2. r(θ, S) is the distance of the arbirtrary point of Γ ^R with coordinates (θ, S) from the fixed fragment’s central axis. r(θ, T) is the distance of points which bound the end of the domain enclosed by the fragments ’ lateral surfaces in contact

We compute the volume of V, say τ, and if τ is smaller than a predefined threshold τ ^T, then we decide that the current relative position of the two fragments is an acceptable one. We point out that the value τ ^T is intimately connected with the actual comparison length L _c and the maximum acceptable distance h between E ^F and E ^R at an actual matching position. This value of h and, thus, of τ ^T has been chosen by repeatedly checking the feeling of the scholars about the acceptance of a matching position.

We have applied this method and the associated information system we have developed in the virtual reassembly of frescos’ fragments excavated at the Mycenaean palace of Tiryns by H. Schliemann in 1885–1886 (H. Schliemann, Tiryns , Leipsig 1886, pls V, VI, XI) and the German Institute in the years 1909–1910 (D. Rodenwaldt, Die Fresken des Palastes, Tiryns II, Athens 1912, pl. III, XXI). These fragments are housed in the Prehistoric Collection of the National Archaeological Museum of Athens (inv. nos 1596, 1655, 1668, 5881–3) and have been scanned by the authors for the first time.

Among the scanned fragments, the developed system offered nine islands (denoted by I) of matching fragments; four of these islands are shown in the following figures (Figs. 62.3, 62.4, 62.5 and 62.6).

Fig. 62.3

Matching results and verification of island I₃. (a) The actual island formed by conservators according to the system suggestion. (b ₁, c ₁) Pairwise matches proposed by the system and the subsequent merge of the 3D representation of the two fragments at the matching position. (b ₂, c ₂₎ Visualization of Euclidean distances between fragments surfaces at the matching positions depicted in b ₁ and c _1, respectively

Fig. 62.4

Example of matching results and verification of island I₇. (a) The actual island formed by conservators according to the system suggestion. (b ₁) Pairwise matches proposed by the system and the subsequent merge of the 3D representation of the two fragments at the matching position. (b ₂) Visualization of Euclidean distances between fragments surfaces at the matching positions depicted in b ₁

Fig. 62.5

Matching results and verification of island I₈. (a) The actual island formed by conservators according to the system suggestion. (b ₁) Pairwise matches proposed by the system and the subsequent merge of the 3D representation of the two fragments at the matching position. (b ₂) Visualization of Euclidean distances between fragments surfaces at the matching positions depicted in b ₁

Fig. 62.6

Matching results and verification of island I₁₁. (a) The actual island formed by conservators according to the system suggestion. (b ₁) Pairwise matches proposed by the system and the subsequent merge of the 3D representation of the two fragments at the matching position. (b ₂) Visualization of Euclidean distances between fragments surfaces at the matching positions depicted in b ₁

3.2 Automated Reconstruction of Fragmented Objects of an Arbitrary Shape: The Case of Prehistoric Vessels

We have extended the previous methodology so as to include the case where the upper surface of the fragment has an arbitrary shape; in particular, we have dealt with the case of fragmented vessels. Indeed, we have considered that, in this case, the upper bound of domain V is the ensemble of the planes tangent to the upper surface of each fragment at the upper contour points of it. Then, we have established criteria analogous to those introduced in Subsection 62.3, which are necessary for accepting the matching of two fragments in a certain position. Therefore, these criteria act like “rejection filters” for each tested relative position of the two fragments, and they have been once more obtained by application of Principles of Calculus of Variations and Differential Geometry, which are however more complicated than the previous ones, due to the nature of the problem in hand.

The final, irrevocable criterion for accepting that two fragments do match at a certain relative position is a slightly complicated version of criterion 4 of Subsection 62.3. The related analysis, together with the corresponding application results will be the subject of a forthcoming publication.

4 Conclusion

In the present work, we have developed two distinct methodologies for testing the match of both the 2D and 3D representations of any two fragments. Both methodologies use a series of mathematically established criteria based on Calculus of Variations , which lead to the conclusion of whether two fragments match at a certain relative position. These criteria are either rejecting, in the sense that they conclude that two fragments do not match in a certain position, or sufficient, when they offer an irrevocable decision about matching. The application of these methods was accomplished through the development of corresponding original information systems, implementing the aforementioned criteria in a proper order. These systems offered islands of matching fragments which have been spotted and virtually reconstructed for the first time, such as fragments of very important prehistoric wall paintings unearthed at Akrotiri , Thira , Tiryns , and Mycenae .