Keywords

These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

1 Introduction

Cultural heritage safekeeping and preservation is a topic of great relevance in all those countries with long history. Aging, extreme weather events and devaluation policies of the cultural heritage value by the local governments involve preservation and requalification actions. For the protection of cultural heritage, these actions should not reduce the reliability of cultural sites and they should not affect the local touristic industry. In the last decades, several projects and papers proposed ICT technologies for cultural heritage improvements and requalification. In particular Virtual Reconstruction and Augmented Reality (AR) results the most interesting and innovative tools for preservation and keeping of historical, architectural and artistic memory of many sites that are in danger of disappearing [1]. These techniques can be used to improve the user experience on the site, overlapping the augmented content, such as information or 3D models, directly on the real objects. In this way, making users interactive on site, the fruition of a cultural content is more interesting and engaging [2]. Furthermore, thanks to Virtual Reality (VR), it is possible to show fictional or past environments, as well as monuments or cities, as they were in past ages. There are several techniques for the creation of a 3D model starting from real objects.

A first approach for the 3D reconstruction of this environment was attempted using photogrammetry [3]. This technique allows the definition of position, shape and dimensions of objects extracting information coming from photographic images appropriately captured through a low-cost procedure that generates a medium-high quality model in terms of precision and details. Another technique for 3D models reconstruction regards 3D scanners. 3D scanning of surfaces allows the capture of huge points cloud datasets that can be used in a Computer Aided Design environment to build accurate 3D models of meaningful objects in the reconstructed scene. This technique is generally expensive but generates very accurate model. The process is time consuming because, after a preliminary data cleaning and registration phase, a digital representation of the original surface has to be computed through a process of surface reconstruction that generates polygonal meshes. The choice between photogrammetry using low-cost device and 3D scanner leads to a trade-off between costs and accuracy. The goal of this work is to find a novel approach based on genetic algorithms for the quality improvement of 3D objects reconstructed by photogrammetric techniques.

2 Photogrammetry

There are several techniques for the 3D acquisition and reconstruction; in particular, they could be grouped into two categories: range-based [4] and image-based [5]. In particular, the most used range-based technique is laser scanning, while photogrammetry is the most used image-based technique.

2.1 Acquisition Techniques

A range-based technique uses an active optical sensor which is able to return a large number of 3D coordinates by measuring key distances on the object to reconstruct. This technique reaches micron resolutions but it needs complex algorithms for the reconstruction of the 3D points cloud [6]. According to literature [7], the work-flow of a real object acquisition using an active optical sensor is:

  • acquisition of different clouds of points or range-map in order to detect the whole scene;

  • registration and alignment of data in a single reference system;

  • reduction of noise and data errors in overlapping areas;

  • creation of a structured polygon model;

  • registration of image data (textures) to the geometric model.

An image-based technique uses images for the reconstruction of 3D models. Photogrammetry is the technique that allows the reconstruction of 3D objects from photographs. Starting from homologous points detected in the images, this technique is used to evaluate key metrics about size, shape and position of an object or scene [8, 9]. Compared to laser scanning, which requires a dedicated acquisition hardware, the pictures for photogrammetrry could be acquired with a smartphone camera which generally is less costly then an active optical sensor; this make photogrammetry a candidate technique for a low cost 3D reconstruction. In order to achieve an optimal image acquisition process, some tips are listed below:

  • images should be acquired with a good quality camera sensor, although smartphones camera could provide good results;

  • it is important to take pictures all around the object. Each portion of the object must appear in at least three photos and each photo must have an overlapping margin of about 60% with the near ones;

  • it is recommended to make several close-up shots to photograph particular portions of the surface (e.g. decorations);

  • zoom should not be used or at least it is necessary to maintain the same level of zoom for all the photos;

  • it is better to take a lot of pictures to eventually select the best and to discard the others;

  • it is necessary to avoid different light condition and different day time (in case of object exposed to sun light);

  • photo resolution has an important impact on the computational complexity for the model generation (higher resolution requires higher computing power).

After images acquisition, the work-flow to evaluate key metrics of the acquired object or scene is [10]:

  • camera calibration to evaluate internal orientation;

  • triangulation of images to evaluate external orientation;

  • creation of 3D scene to derive an unstructured, sparse or dense points cloud;

  • creation of a structured polygon model.

The output of the steps described above is the mesh representing all the key points evaluated (see Sect. 2.2). Table 1 compares the image-based and range-based modelling features [10]. All the aspects shown in the Table 1 make photogrammetry an extremely low cost technique which returns a good model in terms of resolution and quality. Range-based modelling shows some limits on the 3D reconstruction of architectural structures, such as houses or churches; on the other hand, it is possible to use aerial photogrammetry, through an Unmanned Aerial Vehicle (UAV), that allows to obtain a set of images necessary to the next processing.

Table 1. Difference between image-based and range-based modelling features
Full size table

2.2 Reconstruction Techniques

The main technique used to reconstruct a 3D object starting from photogrammetric images is the Structured-from-Motion (SfM) [12]. This method allows to automatically reconstruct a three-dimensional scene from a set of two-dimensional digital images. Figure 1 shows the whole process of 3D object reconstruction. The SfM technique is based on automatic detection of key points (features) in three or more images using the Scale-Invariant Feature Transform (SIFT) [13] or similar algorithm, which are used to perform an image matching. Then, a bundle adjustment procedure is performed [14] to evaluate both camera focal length (internal orientation) and the shot position for each image (external orientation). The output of this step is a set of key points coordinates used to reconstruct a sparse points cloud of the acquired object. A dense points cloud is then generated increasing the number of neighbours of each element of the sparse points cloud. Finally, a 3D model is obtained by converting a simple points cloud in a set of vertices and faces that correspond to a mesh. In this final phase, the model may be also cleaned and textured. A qualitative comparison between the obtained models, based on the number of points in the sparse points cloud, dense points cloud and after the mesh registration, was performed (Table 2); to do this, three low-cost software have been compared:

  • Python™ Photogrammetric Toolbox (PPT): Free software with local elaboration

  • Photoscan: Commercial software with local elaboration (used in 30 days free demo mode)

  • Autodesk® Remake: Commercial software with remote elaboration (used in free education license)

The points cloud obtained from the three software are shown in the Fig. 2.

Fig. 1.
figure 1

3D object reconstruction process using SfM method

Full size image
Table 2. Qualitative comparison between obtained 3D model
Full size table
Fig. 2.
figure 2

(a) PPT Sparse Cloud (b) PPT Dense Cloud (c) PPT Mesh (d) PhotoScan Sparse Cloud (e) PhotoScan Dense Cloud (f) PhotoScan Mesh (g) Remake Mesh

Full size image
Fig. 3.
figure 3

Comparison between the two techniques: (a) object reconstructed using photogrammetric technique with photos by smartphone camera; (b) object reconstructed using Artec Eva 3D Scanner

Full size image

3 Mesh Improvement

After the comparison shown in the previous section, we chose the object reconstructed using Autodesk® Remake software because it was the best trade-off in terms of software cost and quality of rendering. Since photogrammetric systems are cheaper than range-based systems, in this work we try to compare the models obtained by using different photogrammetric sensors; in particular we used a smartphone camera and the Artec Eva 3D scanner. As shown in the images (Fig. 3(a) and (b)), the photogrammetric objects obtained with the two sensors show a great difference in terms of quality of rendering. As could be seen, the best quality is reached using the 3D scanner, but this technique is both time consuming and more expensive than a smartphone which is accessible to all; moreover, 3D scanner reconstruction needs a computer with higher computational capabilities. Our objective is to apply subdivision algorithms to improve the quality of the mesh acquired by photogrammetry using low-cost device so that the resulting 3D model has similar accuracy and resolution as a 3D-scanned model.

3.1 Subdivision Algorithms

The Surface Subdivision allows the surface smoothing by polygonal meshes. The final smooth surface is computed from the initial mesh by the recursive subdivision of each polygonal face into smaller faces that better approximate the smooth surface. The Surface Subdivision is based on Chaikin algorithm [15]: starting from an initial curve with certain points \(P_0\),\(P_0\),...,\(P_n\), new vertices are created between points \(P_i\),\(P_{i+1}\) for each subdivision step. The new points are computed with Eqs. 1 and 2:

$$\begin{aligned} q_{2i}^{k+1} = \dfrac{3}{4}p_i^k + \dfrac{1}{4}p_{i+1}^k \end{aligned}$$
(1)
$$\begin{aligned} q_{2i+1}^{k+1} = \dfrac{1}{4}p_i^k + \dfrac{3}{4}p_{i+1}^k \end{aligned}$$
(2)

Finally, the new curve is created using only the new vertices, as shown in Fig. 4

Fig. 4.
figure 4

Result of Chaikin algorithm

Full size image

A subdivision algorithm can be classify according to some parameters:

  • Subdivision rules

  • Primal (Fig. 5(a)-(b)): a new vertex for every edge of the given mesh is inserted; then, the new vertices are connected [16];

  • Dual (Fig. 5(c)-(d)): each vertex is divided to create new vertices for each near edge of the first vertex.

  • Subdivision types

  • Static: for each subdivision step the same rule is used;

  • Dynamic: for each subdivision step different rules are used.

  • Mesh type

  • Triangular;

  • Quadrangular.

  • Subdivision methods

  • Approximation method: if the final mesh does not contain initial vertices;

  • Interpolation method: if the final mesh contains initial vertices.

Fig. 5.
figure 5

Subdivision Rules. (a) Primal schema for triangular mesh (b) Primal schema for quadrangular mesh (c) Dual schema for triangular mesh (d) Dual schema for quadrangular mesh

Full size image

These algorithms consider also the smoothness as the continuity property of limit surfaces (\(C^0\), \(C^1\), ..., \(C^n\)) [17]. In this work, the algorithms used to implement the surface subdivision are based on primal rule; they are reported in Table 3.

Table 3. Algorithm used to implement the surface subdivision
Full size table

4 Genetic Algorithm

An optimization problem can be solved using one of different methods proposed in literature. Many of them are inspired from natural processes. This kind of methods, called evolutionary computation, generally starts with an initial population that evolve to achieve the global optimum of an objective function. The most popular evolutionary technique is Genetic Algorithm (GA) that uses operators that come from genetic variation and natural selection [23]. The firsts implementations of Genetic Algorithms can be found in late 1950’s [24, 25]. However, this field doesn’t emerge since 1980’s when the computational power of computers starts to increase and algorithms were improved [23]. To improve the mesh obtained by photogrammetric acquisition using a low-cost device in terms of resolution and accuracy, a multi-objective genetic algorithm [26, 27] was designed. Our genetic algorithm is designed to find the best combination of subdivision algorithm, and its parameters, to apply to the model obtained by photogrammetry in order to reduce the distance between this model and a gold standard represented by the object obtained from 3D scanner. The workflow of the proposed approach is developed through the following steps:

  1. 1.

    initialization of the population of the GA;

  2. 2.

    the fitness function is evaluated for each element of the population:

    1. (a)

      application of a surface subdivision algorithm to the photogrammetric model;

    2. (b)

      Hausdorff distance evaluation between the original model and the model obtained in previous step;

  3. 3.

    application of selection and mutation to the population;

  4. 4.

    fitness function evaluation for the new individuals:

    1. (a)

      application of a surface subdivision algorithm to the photogrammetric model;

    2. (b)

      Hausdorff distance evaluation between the original model and the model obtained in previous step;

  5. 5.

    repeat from step 3 until the satisfaction of one of the output conditions;

  6. 6.

    Hausdorff distance evaluation between the model returned by 3D scanners and the photogrammetric model processed with the combination of surface subdivision algorithm and parameters resulting from GA.

Where:

  • the population is randomly initialized;

  • the selection operator is tournament with size equals to 3;

  • the crossover technique is two-point crossover;

  • the mutation can be performed on each bit of the gene.

The fitness function is composed by two objectives:

  • number of points: points number of the cloud obtained after the execution of a subdivision surface algorithm;

  • Hausdorff distance [28]: the distance between the mesh obtained after the subdivision surface algorithm elaboration and the initial mesh (see Sect. 4.1).

Each individual is described by a chromosome with three genes coding:

  • \(X_1\) - the surface subdivision algorithm (in Butterfly, Catmull-Clark, LS3Loop, Loop, Midpoint);

  • \(X_2\) - number of surface subdivision algorithm iterations (an integer ranging in [0, 3]);

  • \(X_3\) - percentage threshold (an integer ranging in [0, 7]) evaluated considering Eq. 3, which is the percentage of the diagonal of a bounding box containing the object mesh.

    $$\begin{aligned} threshold = \dfrac{X_3 + 1}{8} \end{aligned}$$
    (3)

Operators employed in the GA set up were:

  • generations limit number: 100;

  • crossover with a probability of 0.5;

  • mutation with probability of 0.2 for each individual;

  • each bit can be mutated with probability of 0.05;

  • individuals for each generation: 50;

  • stop criteria: maximum generations numbers (100) or 20 consecutive generations with the same fitness score.

4.1 The Hausdorff Distance

Considering two meshes and their vertices, for each vertex of the first landmark mesh (X) the distance from the closest vertex in the second comparison mesh (Y) is evaluated; the output of this algorithm is a list of distances. In this work, we used the algorithm of Hausdorff distance implemented in Meshlab, an advanced 3D mesh processing software system that is oriented to the management and processing of unstructured large meshes and provides a set of tools for editing, cleaning, healing, inspecting, rendering, and converting these kinds of meshes. The output of the Meshlab implementation of Hausdorff distance is the maximum distance found in the comparison process (Eq. 4).

$$\begin{aligned} \mathop {\sup }\limits _{x\in X} \inf _{y\in Y} \mathrm {d}(x,y) \end{aligned}$$
(4)

In general, Hausdorff distance is a symmetrical measure (\(d(X,Y) = d(Y,X)\)); in detail, its definition is in Eq. 5.

$$\begin{aligned} d_H(X,Y) = max\{\mathop {\sup }\limits _{x\in X} \inf _{y\in Y} \mathrm {d}(x,y), \mathop {\sup }\limits _{y\in Y} \inf _{x\in X} \mathrm {d}(x,y)\} \end{aligned}$$
(5)

5 Results

The initial mesh, which is the input of the genetic algorithm, acquired by a smartphone camera and reconstructed by Autodesk® Remake Educational Edition software, is characterised by 17027 vertices (bounding box diagonal = 1390.367432). The mesh used as ground truth, acquired by the Artec Eva 3D Scanner and reconstructed by Artec Eva image-based modelling commercial software, is characterised by 51701 vertices (bounding box diagonal = 1403.514160).

The Hausdorff distance, used to compare the differences between the previous two meshes, considering 3D scanner mesh as reference, has a mean value of 3.778587 (min: 0.000366, Max: 34.477371, RMS: 5.043168). The designed multi-objective genetic algorithm output is reported in Table 4.

Table 4. The best individual from the GA
Full size table

The subdivision algorithm is not computationally intensive because its execution is 473 ms, on a system configured with a CPU Intel® Core™i3-2350M (2.3 GHz, 3 MB L3 cache), an integrated GPU Intel® HD Graphics 3000 and 4 GB DDR3 Memory. The percentage variation in the results table represents the Hausdorff distance variation between the difference obtained comparing 3D-scanned and the initial photogrammetric meshes and comparing 3D-scanned and the genetic algorithm output meshes.

6 Discussion and Conclusion

The results obtained show that the surface subdivision algorithms increases the points number of mesh (+441.281%), while the relative Hausdorff distance values show a mesh improvement as report the percentage reduction of the distances mean (−0.015%). Considering these results, there was a little mesh improvement of 3D object quality but it was not considerable in terms of object rendering. Probably it depends on the position of the points generated by the surface subdivision algorithms which are randomly placed by the algorithms themselves. To overcome this issue, in future work we will try to better design the GA taking into account new parameters, such as the points positioning and distribution. Another possible way to improve the performance of our genetic algorithm is to apply a different method for maintaining the population: the steady state approach [23]; in fact, this allows the replacement of worst, or oldest, individuals in the population by children as soon as they are created.