{'fraction_non_alphanumeric': 0.03174163783160323, 'fraction_numerical': 0.010657439446366782, 'mean_word_length': 4.677317967522263, 'pattern_counts': {'":': 0, '<': 1, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 1, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Automatic 3D Reconstruction of Manifold Meshes via Delaunay Triangulation and Mesh Sweeping

In this paper we propose a new approach to incrementally initialize a manifold surface for automatic 3D reconstruction from images. More precisely we focus on the automatic initialization of a 3D mesh as close as possible to the final solution; indeed many approaches require a good initial solution for further refinement via multi-view stereo techniques. Our novel algorithm automatically estimates an initial manifold mesh for surface evolving multi-view stereo algorithms, where the manifold property needs to be enforced. It bootstraps from 3D points extracted via Structure from Motion, then iterates between a state-of-the-art manifold reconstruction step and a novel mesh sweeping algorithm that looks for new 3D points in the neighborhood of the reconstructed manifold to be added in the manifold reconstruction. The experimental results show quantitatively that the mesh sweeping improves the resolution and the accuracy of the manifold reconstruction, allowing a better convergence of state-of-the-art surface evolution multi-view stereo algorithms.


Introduction
Reconstructing the observed scene from a set of images is a widely studied problems in computer vision: it is known as Structure from Motion (SfM), when the aim is to reconstruct both the scene (the structure) and the camera poses (the motion), or as multi-view stereo (MVS), when camera poses are known. While SfM techniques provide a sparse reconstruction of the environment, MVS aims at reconstructing a dense and accurate model of the observed scene.
Since the datasets of [25] and [28] were made available, dense MVS has been faced with different approaches, some of which reaching very accurate results; however, some issues are still open, e.g., the initialization and the management of untextured regions and the handling of false matches. According to the representation of the 3D model, MVS methods can be subdivided in point-based, volumetric and mesh-based methods. Point-based methods estimate the depth of each image pixel, reconstructing a point cloud [7,30]; they provide accurate and dense point clouds, but the outcome is often redundant where the surface is flat, and they are not able to reconstruct untextured area. Volumetric methods, first proposed by [2], build the reconstruction by discretizing the space and labeling as matter or free space the voxels, as in [2], or the tetrahedra, as in [13]. Voxel-based methods require a huge amount of memory, and even if attempts to make the representation more compact exist [27], they are still not suitable for large-scale reconstruction. Tetrahedron-based methods are more compact, but the accuracy of the reconstruction still needs to be refined to reach state-of-the-art results. This latter approach is often used as an initialization to mesh-based methods in [33,32,24].
Mesh-based methods have been proven to be suitable to build continuous, high accurate reconstructions of both small objects and large-scale scenes [32,33,24]. These methods refine an existing mesh by minimizing an image similarity measure such as the Zero Mean Cross Correlation (ZNCC) [32,20,35] or the Sum of Squared Differences (SSD) [4,3]. The initialization of the existing mesh is one of the major issues in state-of-the-art mesh-based MVS methods. For single object reconstruction, as in the Middelbury dataset [25], the initial mesh is usually estimated by the visual hull [14], but this is not applicable in more complex scene such as the ones in [28] or in large-scale scenarios.
One of the most effective and scalable mesh-based algorithm for multi-view stereo was proposed by Vu et al. [33]; in their work, the authors initialize the mesh evolution algorithm by extracting a very dense and noisy point cloud, then building a Delaunay triangulation out of it, and estimating the initial mesh via a s-t cut algorithm based on the work of [13]. This last work inspired other extensions such as [11]. The main problem with this approach is that the s-t cut does not guarantee the output mesh to be a manifold while the surface evolution algorithm needs this property; indeed Vu et al. need to manually check the outcome of the s-t cut before surface evolution.
Some mesh-based algorithms, e.g., [19,16], initialize the reconstruction with a point-based MVS such as CMVS [7] together with Poisson Reconstruction [12]. This process automatically provides an initialization usually close to be manifold, but still without guarantees, and it has issues related to redundancy of the points and non-scalability. In the literature, some methods to estimate a manifold mesh exist, but most of them rely on silhouettes [31,6,5], thus they are limited to small objects, or they are not scalable due to the usage of voxel-based reconstruction [10]. A suitable approach to estimate a manifold mesh has been recently proposed in [15,17,21,22]: the authors incrementally reconstruct the scene from very sparse data which are the outcome of SfM algorithms. For many applications the reconstruction relying only on these points is sufficient, but for a surface evolution approach, it needs resolution and accuracy improvements. Indeed, to avoid getting stuck in local minima during the evolution process, also Vu et al. need to densify the point cloud extracted by the SfM algorithm.
In this paper we propose a novel and fully automatic approach to estimate a manifold, suitable for being a good initialization for a surface evolution mesh-based MVS algorithm. We bootstrap from a manifold reconstructed in a similar fashion to [17], and we refine it by iteratively sweeping the triangles of the manifold around their neighborhood looking for good stereo matches. This approach takes inspiration from the multi-directions plane-sweep of [8], where the authors sweep a set of planes choosing fixed directions related to the direction of the walls identified from Structure from Motion points; for each pixel and each plane they collect the matching costs among the views and choose the best stereo matching cost to estimate depth maps. Another interesting method that performs local plane sweeping is presented in [26], where, again, the output is a depth map. In the proposed approach we estimate directly a manifold mesh; the directions of the planes are automatically driven by the data, and we avoid to sweep on the whole scene, since we look for new 3D points in the neighborhood of the iteratively reconstructed manifold. Differently from [8], we directly recover a consistent dense 3D mesh instead of independent depth maps.
In Section 2 we summarize the reconstruction and refinement algorithm that builds incrementally a manifold and refines it. In Section 3 we show the results of our approach, underlying the improvement of the reconstruction accuracy thanks to the sweeping algorithm on both simulated and real datasets. In Section 4 we conclude pointing out possible future work. Figure 1. The manifold property: the vertex V in (a) is regular (ABCDEF is a closed path without cycles), while in (b) and (c) the vertex V is not regular since, in the former case the path ABCDEF GHI is not closed, and in the latter ABCDEF GHF has two cycles.

Proposed algorithm
In the proposed system, we iteratively alternate manifold reconstruction and mesh sweeping. First we describe how we estimate the initial mesh, then how we extract new points through mesh sweeping and how we add them, incrementally, to the manifold.

Manifold Reconstruction
Let recall that the manifold property holds if and only if the neighborhood of each surface point is homeomorphic to a disk. So a mesh, which is a discrete surface, is manifold if and only if each vertex v is regular, i.e., if and only if the edges opposite to v form a closed path without loops [17]. We show in Figure 1 (a) one example of a regular vertex and in Figure 1(b) and 1(c) two cases where the vertices are not regular and thus they break the manifold property.
In literature [9,17], reconstruction from sparse data involves the estimation of a mesh which usually partitions the 3D Delaunay Triangulation of a set of sparse points between two sets: free space and matter. In this case, the sources of non-manifoldness can be induced by tetrahedra intersecting at a vertex, and by tetrahedra with a common edge (nonmanifold edge). In both cases the non-manifoldness can be fixed, in principle, by cloning and offsetting the vertex of intersection, but two big drawbacks arise: this process would invalidate the Delaunay property, that we need to keep valid in an incremental setting, and, since many non-manifold vertices are generated, rearranging the triangulation and the visibility information for each non-manifold point becomes inefficient. For these two reasons we need a different approach to enforce the manifoldness.
We reconstruct a first manifold with the algorithm proposed in [17], slightly modified by a weighting scheme as in [22,21], bootstrapping from the camera poses, the reconstructed points and the visibility estimated by a Structure from Motion algorithm 1 . The manifold is reconstructed such that it partitions the 3D triangulation of the SfM points between the set O of outside tetrahedra, i.e., the subset of the free space outside the manifold (not all the free space tetrahedra will be part of the space outside the manifold), Example of manifold sweeping with respect to the camera C and the complementary set I of inside tetrahedra (i.e., the remaining tetrahedra that represent the matter together with the free space tetrahedra which would invalidate the manifold property). A weight is associated to each tetrahedron and it keeps track of the visibility information, i.e., the camera-to-point viewing rays; in the following, a tetrahedron belongs to free space if its weight is higher than a threshold t w (in our case t w = 4.0). The manifold is obtained by three steps. (1) Point Insertion: build the 3D Delaunay triangulation of the 3D SfM points. (2) Ray tracing and tetrahedra weighting: for each camera-to-point viewing ray, add a weight w 1 = 4.0 to the intersected tetrahedra and a weight w 2 = 0.5 to their neighboring tetrahedra. Such weighting scheme acts as a smoother of the visibility and avoids the creation of visual artifacts (see [18] for a detailed discussion about visual artifacts). (3) Growing: initialize a queue Q starting from the tetrahedron with the higher weight. Then: (a) pick the tetrahedron with highest weight from Q and add it to O only if the resulting surface between O and I remains manifold; (b) add the neighboring tetrahedra to the queue Q, otherwise discard it; (c) continue iteratively until Q is empty.

Mesh Sweeping
After each manifold reconstruction step, we apply the novel mesh sweeping algorithm to look for new 3D points in the neighborhood of the manifold mesh, which we assume to be close to the true model of the scene. These points will be added to the reconstruction at the next manifold reconstruction iteration.
For each camera, we sweep the visible part of mesh M along the viewpoint direction (see Figure 2). Given a camera located in C, is the distance swept (let note that is fixed for all the facets). In our case we fixed N = 20.
Since all the visible vertices of each triangle are swept by the same amount along the camera-to-point direction, no self-intersections among facets has been induced.
The sweeping process produces a set of N + 1 meshes M = {M 1 , · · · , M j , · · · , M N +1 }. For each mesh M j we perform pairwise stereo matching between each camera C and the two nearest cameras. Let I C be the image seen by C, and I k the image seen by the camera C k , that is one of the two cameras nearest to C, therefore k ∈ {1, 2}. For each camera k and mesh j, we compute I j k as the reprojection of image I k through the mesh M j into camera C. Then, we compute the Normalized Cross Correlation (NCC) image I C and the reprojection I j k . The NCC is computed pixel-by-pixel and is weighted by a Gaussian kernel as in [20] (the σ for the Gaussian kernel is σ = 8px). The last step aims at collecting the new 3D points. We create a n r xn c grid over the N images of pixel-by-pixel NCCs computed for each mesh M j . We collect in each tile the image point with the best NCC above a threshold t NCC = 0.98 among all the N images; therefore, we obtain at most n r xn c points. For each collected point, we retrieve its 3D position from the corresponding mesh that generated it.
We are able to perform the whole process image-based, i.e., we act on the image and not on the mesh, so that the most complex computations become independent from the size of the mesh, and they are self-adaptive with respect to the image resolution. This also allows our approach to be adaptive in term of mesh resolution output.
Mesh sweeping requires some parameters. N and α need to be fixed in order to keep the sweeping local and, at the same time, to induce an appreciable sweeping of the mesh w.r.t. the image resolution. The values of N or α are also related to the observed scene and the image resolution, but the sweeping algorithm is quite robust against these two pa- rameters. On the other hand, σ, t N CC , n r and n c concur to determine the trade off between precision and recall of the newly estimated 3D points. The threshold t N CC needs to be high so to avoid outliers, even if a good choice of the tile sizes, e.g., 100x100px, manages to make the algorithm robust to outliers and to small variations of parameter setting. Finally, the value of σ is usually related the the image resolution, but in our experiments, with different resolutions, we found that the same value of 8px is a good compromise between cross-correlation sensitivity and smoothness.

Incremental refinement of the manifold
To refine the initial mesh, we iterate between the mesh sweeping algorithm, which outputs a set P of new 3D points, and the incremental reconstruction (described in this section) until convergence is reached (i.e., no more points are available to be added or the number of iteration is greater than it max = 15).
The insertion of a point p ∈ P into the Delaunay triangulation causes the removal of a set D of tetrahedra breaking the Delaunay property. The surface between O \ D and I ∪ D is not guaranteed to be manifold anymore. In order to avoid this, as the authors in [17], we define a list of tetrahedra E ⊃ D and apply the Shrinking procedure, i.e., the inverse of Growing: we subtract iteratively from O only the tetrahedra ∆ ∈ E keeping the manifoldness valid. After this process, it is likely that D ∩ O = ∅. Whenever D ∩ O = ∅ the point p is not added to the triangulation and it is discarded. Once all points in P have been processed, the queue Q is initialized with the tetrahedra ∆ ∈ T \ O such that ∆ ∩ δO = ∅, and the Growing process starts as explained in Section 2.1.

Experimental evaluation
The proposed algorithm provides an automatic initialization for mesh-based dense MVS algorithms. We implemented our approach in C++ using the CGAL library [29] for all the computations involving the Delaunay Triangulation and manifold extraction. This allows us to exploit efficient data structures and algorithms for the initial manifold reconstruction tasks. Conversely, the proposed mesh sweeping algorithm exploits the power of GPU computing; we implemented the main steps with the GLSL shading language of OpenGL [23]: a geometry shader computes the normal; the vertex shaders sweep the mesh along the camera viewing rays; the fragment shaders implement the reprojection from one image to an another through the mesh surface, the NCC computation and the thresholding.
We performed experiments on both synthetic and real datasets on a 4 Core i7-920 CPU at 2.6Ghz (8M Cache), with 24GB of DDR3 SDRAM and NVIDIA TitanX. Synthetic experiments aim at showing the effectiveness of the mesh sweeping approach to refine a rough manifold. The experiments on real data show the scalability of the proposed method and its effectiveness compared to CMVS [7], used as automatic initialization in mesh-based algorithms [19,16] together with Poisson reconstruction [12].
In Figure 4 we provide quantitative evaluation for the two synthetic datasets. The ground-truth meshes we used to generate the image are two pyramids without the squared base facet (Figure 4(b)), pointing downward for the first dataset, and upward in the second one; the dimensions of these pyramid are 2x2m of squared base and 0.3m height. The initial point cloud in both cases is made up by the four vertices of the base. We bootstraps from only these four points, to show the impact of the proposed approach even if few sparse points are available. In both cases the initial manifold extracted is a square corresponding to the base of the pyramid (Figure 4(c)). The final reconstructions are shown in Figure 4(d) even if some little artifacts are created due to the noise in the matching process, the extracted surface is close to the ground-truth. We computed the distance of the meshes with respect to the ground truth by comparing the depth of each pixel from the first camera, similarly to the comparison method proposed in [28]. In Table 1 we compare the accuracy of the initial mesh with the accuracy after the proposed mesh sweeping: our method improves significantly the initial mesh; this result is also supported by the improvement on the error distributions in Figure 5, where the errors are reported as a percentage of depths such that their error e w.r.t. the ground truth is e < m * Sigma (Sigma = 0.06m). In Table 2 we applied the photometric refinement of [33] to the two meshes and we show the results: the convergence of the refinement after the mesh sweeping is faster and the the reconstruction more accurate. We tested the proposed approach on the fountain-P11 dataset provided in [28]: the ground-truth is available and the evaluation is performed by comparing the depth map generated from the 6th point of view as suggested in [28], such that the results of the comparison are independent from the quality of the camera calibration (a detailed discussion is available in [28]). We initialized the manifold reconstruction with the sparse point cloud data estimated with Visu-alSFM [34]. Table 3 shows the accuracy of the initial manifold, estimated in a similar fashion to [22], the manifold after the mesh sweeping and the reconstruction performed by CMVS+Poisson, where the octree depth of the Poisson reconstruction is 11 (see [12]). In Figure 6 we report the cumulative distribution of the errors for each algorithm with the same convention as before. As Figure 7 shows, the initial manifold represents accurately the wall, while some parts of the fountain present artifacts, indeed, the accuracy of this initial guess is lower than the outcome of CMVS+Poisson. The mesh sweeping refinement improves the mesh accuracy, both respect to the initial mesh and to CMVS+Poisson reconstruction, even if the resolution of the latter is significantly higher. Our approach avoids to reconstruct redundant data, differently from the point-based CMVS, which reconstruct as much points as possible, even if they are coplanar. Table 4 shows that the proposed approach improves the convergence of the variational photo- metric refinement described in [33] leading to a more accurate reconstruction. The mean timing per-iteration is 318s for mesh sweeping and 55s for manifold reconstruction: the mesh sweeping is the most demanding task, but thanks to its GPU implementation it would easily take advantage from more powerful hardware. Finally we tested the scalability of the proposed approach with a real dataset, named Dagstuhl, of 68 1600x1200 images (see Figure 8). We tested the algorithm considering different subsets of frames to understand experimentally the dependence with the number of cameras of the proposed algorithm and the two steps (manifold reconstruction and mesh sweeping) separately. As Figure 9 points out, both steps and the whole algorithm show experimentally a linear relation with the number of cameras; this suggests that our approach is scalable and suitable for large-scene reconstructions.

Future Works and Conclusion
In this paper we proposed a new approach to reconstruct an initialization for mesh-based multi-view stereo algorithm such that the whole pipeline is fully automatic, taking into account that state-of-the-art algorithms are not able to evolve correctly non-manifold meshes. We build a first rough mesh with an incremental manifold reconstruction algorithm, then, we iterate between the novel mesh sweeping refinement and the manifold reconstruction. The former sweeps the mesh along the cameras viewing direction and seeks new pairwise stereo matches in these swept meshes; the corresponding 3D points and visibility information are added to the incremental manifold surface algorithm. Our approach improves the initial mesh accuracy and resolution, and also with respect to the reconstruction based on  CMVS+Poisson, usually adopted as mesh-based MVS initialization. The presented algorithm has the strong advantage of being suitable for large scale, resolution-adaptive, and incremental 3D reconstruction scenarios, while keeping the manifold properties.
As future work we would improve the robustness with respect to untextured regions, in particular when more than one main untextured plane is present, and we would like to test other stereo matching measures. Moreover we would like to test in our scenarios some ideas from [1], such as the addition of the ghost primitives.