In the usual structure from motion setting, the camera orientations and a 3D point structure is estimated first. These estimates are then used as the basis of a full 3D surface model estimation. If the method of [64, 65, 66, 106] was used for this, only the camera orientation would be applied. Hence the information from the already estimated structure is discarded.
We here propose using this 3D point structure by forming a much better initial guess.
This is done by applying the method of Morris and Kanade [137], to make an optimal trian-gulation of the 3D point structure already at hand. This triangulated mesh is then used as an
11.4 Results 101
initialization for the level set. Since the elements of the 3D point structure are assumed to lie on the surface, this mesh can be seen as a piecewise linear approximation to the surface (c.f.
Figure 11.2). A practical consideration in this regard is how to convert the mesh to a signed distance field, the latter being an initialization for the level set method. This is done with a modified version of [150] described in [26], whereby the signed distance from each voxel to the mesh is calculated. The sign is positive if the voxel is outside the mesh, and negative if it is inside.
The first advantage of this approach is that the initial guess is very likely to be much closer to the true surface, c.f. Figure 11.2. Hence the run time is reduced considerably, in that smaller changes inSis need . In our experiments the order of magnitude of speed up is from whole to half days to approximately 1 hour.
Secondly, the proposed approach has the advantage of not needing the inward force G(Φ(x)). Hence the prior on the surface becomes:
αC . (11.4)
The difference is that if the data does impose a force onS, due to the above mentioned reasons, then it should try to smooth out instead of go inward. This makes the approach much more resistant to image noise and surface parts with low variability.
11.4 Results
To validate the proposed approach, we used 5 images of a face as illustrated in Figure 11.3(a).
This data set was noisy, in that it is unlikely that the subject was completely still. Secondly, there are many patches with very low or no variance. As such this is a rather challenging data set for a surface reconstruction algorithm, but it is by no means below the standard of what is expected in a structure and motion setting. The quality of the data also makes a solution with an inward force,G, infeasible as seen in Figure 11.4. It is seen how the surface has
’gone through’ the true surface,S∗. In later iterations the holes get bigger, and eventually the smoothness constraint of (11.3) will pull the surface fromS∗, whereupon it will collapse under its own curvature.
The proposed approach was also applied. It was initialized with the mesh depicted in Figure 11.3(b). This mesh is optimally triangulated based on a 3D point structure estimated by structure from motion from a series of automatically identified landmarks. The result is seen in Figure 11.5(a), where it is noted that the algorithm converges to an acceptable result, despite the quality of the data.
To improve the results, the use of more advanced regularization was investigated. It turned out that most of the problematic data was at low variance patches. Hence, it was tried to smooth patches,Ni, with lowΦ(x)more. From a histogram ofΦ(x), it was deducted that 0.5 was a good cut off. Hence (11.3) was modified to
∂S
∂t =
−∇Φ(x)·n+αC Φ(x)≥0.5
−0.5· ∇Φ(x)·n+ 1.5·αC Φ(x)<0.5 . (11.5)
(a) (b)
Figure 11.3: (a) A sub image from the face sequence of 5 images. The subject moved slightly during the taking of the images. (b) The initialization used with the face data set, when the proposed method is applied.
The result is seen in Figure 11.5(b). In the results of Figures 11.5(a) and 11.5(b)αwas set to 0.25. Here it is seen that this extended regularization improves the result, implying that extended regularization is a fruitful path.
11.5 Discussion
A new approach for PDE based surface estimation has been presented for use in the usual structure from motion framework. This approach uses the estimated 3D point structure to initialize the optimization, whereby a significant speed up and resistance to poor data is achieved. Both these issues are vital when performing structure and motion on real data.
11.5 Discussion 103
Figure 11.4: An intermediate iteration in face sequence, when using an inward force,G. It is seen how the surface has ’gone through’ the true surface,S∗. In later iterations the holes will get bigger, and eventually the smoothness constraint of (11.3) will pull the surface from S∗, whereupon it will collapse under its own curvature.
Acknowledgments
The authors owe great thanks to Henrik Malm, Fredrik Kahl and Björn Johanson delivering the data.
(a) (b)
Figure 11.5: (a) Proposed method on the face data set, see Figure 11.3(a). (b) Proposed method on the face data set, see Figure 11.3(a). Here the extended regularization of (11.5) was used.
C
HAPTER12
Pseudo–Normals for Signed Distance Computation
by:Henrik Aanæs and J. Andreas Bærentzen
Often times reviews can seem harsh to the author. So it was nice to get this comment in regards to this work.
This is a difficult problem, one that I personally have looked at before, and abandoned without a suitable solution. This appears to be that solution.
Anonymous Reviewer 3.
Abstract
The face normals of triangular meshes have long been used to determine whether a point is in- or outside of a given mesh. However, since normals are a differential entity they are not defined at the vertices and edges of a mesh. The latter causes problems in general algorithms for determining the relation of a point to a mesh.
At the vertices and edges of a triangle mesh, the surface is notC1continuous. Hence, the normal is undefined at these loci. Thürmer and Wüthrich proposed the angle weighted pseudo–normal as a way to deal with this problem. In this paper, we undertake showing that the angle weighted pseudo–normal has an important property, namely that it allows us to discriminate between points that are inside and points that are outside the mesh.
This result is used for proposing a simple and efficient algorithm for computing the signed distance field from a mesh. Moreover, our result is an additional argument for the angle weighted pseudo–normals being the natural extension of the face normals.
12.1 Introduction
When relating 3D triangular mesh structures to other geometric entities, it is often necessary to know how far a given point is from the mesh. Wether the given point is in- or out side of the mesh can also have significant importance, e.g. in collision detection this determines whether the object is hit or not. This entity is efficiently represented as a real number where the absolute value denotes the distance and the sign whether the point is outside or not – negative denoting inside – yielding a signed distance.
Another important use of how a point relates to a mesh is in generating signed distance fields, i.e. a discrete field where each entry contains the signed distance. This implicit repre-sentation of a surface is among others used with the level–set method proposed by Osher and Sethian [146]. So if you, e.g. have a surface represented as a mesh and you want to apply a method implemented via the level set framework, such a conversion is needed. It is this signed distance field computation that will be the applicational focus of this paper.
For closed, orientable, and smooth surfaces we can use the normals to find out if a given pointpis inside or outside. Say we find a point on the surfacecso that no other point is closer top. Then, we know that the normal at cwill point either directly away from or directly towardspdepending on whether we are inside or outside the surface. Hence, the inner product betweenr=p−cand the normal will tell us whetherpis inside or outside.
When the surface is a triangle mesh, the situation is somewhat different because a mesh is not smooth everywhere: At edges and vertices the normal is not defined. To overcome this problem, we need to define a pseudo–normal for vertices and edges with the property that the sign of the inner product determines whetherpis inside or outside. It turns out, that the required pseudo–normal is the angle weighted pseudo–normal proposed by Thürmer and Wüthrich [201] and independently by Sequin [190]. This normal is computed for a vertex as the weighted sum of all normals to faces that contain the vertex. The weight is the angle between those two edges of the face that contain the vertex, hence the name.
Our main contribution is proving that the angle weighted normal fullfills our requirement, i.e. that the sign of the inner product between a vector from a closest mesh pointcto the corresponding pointpand the angle weighted normal does indeed discriminate between inside and outside. A number of other pseudo–normals have previously been proposed. For most of these it is easy to show that they do not have this property.
This theoretical result is relevant for any application where it is required to find out whether a point is inside or outside a triangle mesh. The application that motivated our own work was the computation of discrete 3D distance fields. Another obvious application is collision detection or path planning. However, our result also strengthens the argument that the angle weighted pseudo–normal is a natural choice whenever it is necessary to define a normal at the vertex of a triangle mesh and no analytical normal is available. Another argument due to Thürmer et al. [201] is the fact that the angle weighted pseudo-normal depends only on geometry and is invariant to tesselation.
The paper is organized as follows; first the angle weighted pseudo–normal is introduced in Section 12.2 and compared to other pseudo–normals proposed in the literature. The central proof is presented in Section 12.3 followed by a description of how this result can be used for computing signed distance fields in Section 12.4.