Generation of Triangle Meshes from Time-of-Flight Data for Surface Registration

Abstract

One approach to intra-operative registration in computerassisted medical interventions involves matching intra-operatively acquired organ surfaces with pre-operatively generated high resolution surfaces. The matching is based on so-called curvature descriptors assigned to the vertices of the two meshes. Therefore, high compliance of the input meshes with respect to curvature properties is essential. Time-of-Flight cameras can provide the required surface data during the intervention as a point cloud. Although different methods for generation of triangle meshes from range data have been proposed in the literature, their effect on the quality of the mesh with respect to curvature properties has not yet been investigated. In this paper, we evaluate six of these methods and derive application-specific recommendations for their usage.

Introduction

One of the main challenges related to image-guided procedures is the registration of pre-operative images (e.g. from Computed Tomography (CT) data) with the patient’s anatomy during the intervention. In this context, Time-of-Flight (ToF) cameras [ 1 ] are gaining increasing attention for acquisition of intra-operative range images of the target organ(s). As range images can be converted to surface representations, pre- and intra-operative data can be registered by means of surface matching. One approach to this matching was recently proposed in [ 2 ]: First, so-called curvature descriptors representing surface curvature characteristics are computed for each vertex of both surfaces. Next, correspondences between the descriptors are established in such a way that a global similarity metric is maximized. Finally, a transformation between the surfaces is computed.

As a consequence, high compliance between generated ToF surfaces and preoperatively generated surfaces is essential. ToF surfaces are subject to various errors including systematic errors (e.g. wiggling error [ 1 ]), noise and errors induced by mesh triangulation. The latter may be relevant due to the limited ToF image resolution (currently up to 204 204 pixels). In this paper, we focus on the errors of mesh triangulation and isolate their influence on the overall error from the effect of other error sources. As the vertices, generated from ToF data, are arranged in a rectangular grid, the intuitive representation is a quad mesh.

Normal vectors of triangle planes facilitate curvature computation, which motivates us to create a triangle mesh. Different triangulations potentially yield different face normals (Fig. 1a). Despite the huge amount of literature on point cloud triangulation in general, the specific issue of triangulating a quad mesh has not been addressed. Therefore, the purpose of this paper is to compare methods for triangle mesh generation from ToF data with respect to their ability to preserve curvature. To measure this quality, we compare ToF surfaces quantitatively and qualitatively to high resolution ground truth data generated from CT images. 2 2.1

Methods

Methods for triangle mesh generation

To generate a triangle mesh representation from a given quad mesh, the following six triangulation methods were investigated: { Naive triangulation: (Fig. 1b) Into each quad, a diagonal edge (dashed lines) is inserted from the upper-left vertex to the lower-right vertex (or vice versa). { Delaunay based triangulation: (Fig. 1c) This variant, introduced by Park et al. [ 3 ], determines the direction of the diagonal edge according to the wellknown Delaunay triangulation: For each quad, an additional edge is inserted such that the Euclidean distance between the opposing vertices is minimized. { Curvature ipping optimization (CFO): This method, introduced by Dyn et al. [ 4 ], modifies a given triangulation (in our case the naive approach) by flipping the diagonal edges such that local curvature differences are minimized.

The following methods interpolate an additional vertex in the middle of each quad of the mesh (Fig. 1d). This allows for creating four triangles instead of two, and refines the mesh. { Four-point scheme based triangulation: (Fig. 1e) In this method the middle vertex interpolation is based on the subdivision scheme presented by Kobbelt [ 5 ]. For interpolation purposes, 16 vertices (black crosses) in a square neighborhood are used. For each row of four vertices a mid-point (dots) is determined. Next, the resulting column of four points is used to interpolate the vertex in the middle (gray cross). { Thin plate spline (TPS) based triangulation: The x and y coordinates, given by the quad mesh, are used in combination with z = 0 as source control points. In conjunction with the known z values (the given distances) x and y coordinates serve as target control points. Thus, a transformation is created which allows for interpolation of an arbitrary point (the mid-point) with known x and y coordinates. { B-Spline based triangulation: Similar to TPS, B-Splines allow for interpolation of an arbitrary vertex on the surface. In contrast to TPS, they do not necessarily interpolate control points. In this work, we interpolate the z values for each vertex on the surface using 16 control points.

Evaluation

For in silico evaluation purposes, ideal range images (i.e. range images without noise) were generated from a set of high-resolution CT surfaces (two livers, a brain and a face) utilizing the ToF simulation framework introduced in [ 6 ]. Next, the six triangulation methods were applied to create surfaces from the range images. Finally, the deviations of the curvature descriptors mean curvature (MC), Gaussian curvature (GC) and curvedness [ 7 ] between the ToF vertices and the corresponding ground truth vertices were computed.

In a similar fashion, an in vitro evaluation was performed on the data, obtained from an experiment described in [ 8 ]. Porcine organs were captured by both, CT scanner and ToF camera. Next, the resulting surfaces were registered using a point-based registration method combined with the iterative closest point (ICP) algorithm. The closest vertex on the CT mesh to a vertex on the ToF surface after registration served as correspondence for our computation. 3

Results

In the in silico experiments, the following results were achieved: Delaunay and CFO perform best for MC, GC, and curvedness deviation on all five organs. Fig. 2 exemplarily illustrates the resulting simulated surfaces with colored MC, including the CT ground truth, for a liver. Fig. 3 shows a box plot for the deviation of MC for the same liver. Regarding the median, the Delaunay method performs best. Regarding all other measures the CFO method yields the best results, followed by the Delaunay method. The evaluation on the in vitro data yields comparable results for all organs. Fig. 4 exemplarily shows our results for MC on an in vitro data set. 4

Discussion

To our knowledge, we are the first to address the effect of quad mesh triangulation on low resolution data. Due to their interpolated vertices, the three types of triangulation based on either four-point scheme, TPS, or B-Spline create artifacts in several regions (Fig. 2e-g), which makes them rather inappropriate for (a) (b) (c) (d) (e) curvature preservation. Additionally, they have the worst outcome regarding curvature deviations (Fig. 3). As shown in Figs. 2b and 4b, the naive triangulation induces a lot of blurring artifacts (from top left to down right – as the edges are inserted) at parts where curvature changes.

Altogether, the curvature deviations between the methods seem relatively small (Fig. 3), but within the small range of MC – here ( 0:06; 0:03) – the (a) CT liver (b) Naive (c) Delaunay (d) CFO (e) TPS (f) Four-Point (g) B-Spline relative deviation is still considerably high (up to 0.035). Additionally, they occur on all in silico data sets and with all curvature descriptors. Consequently, they are unlikely to be a result of chance. Furthermore, they directly influence the registration error and could have considerable impact on that. Consider a work flow aiming for high performance: A low resolution (e.g. 64 48 pixels) ToF camera would decrease the data size – and thus increase performance – significantly, but this case would suffer even more from the triangulation error.

Our study suggests that the Delaunay and CFO approach yield slightly better results than the naive method regarding curvature preservation. However, the in vitro evaluation reveals that the impact of triangulation is rather small (Fig. 4) compared to systematic errors and noise. Therefore, further aspects should be considered when choosing a triangulation method for a given application: The naive method creates regular vertices (i.e. a vertex with six neighbors), which is preferable in some cases of surface processing. As the Delaunay method has negligible additional cost compared to the naive method (just two arithmetic operations and a comparison) and a better visual outcome (Fig. 2b,c), it should be preferred when both, curvature preservation and performance, are important. For high accuracy, we recommend CFO, for it yields the best results in most of the curvature deviation measures, presented in Fig. 3, and shows the best visual outcome in Fig. 2, especially in the enlarged region.

According to our study, curvature properties depend on the method for triangulation, which should thus be chosen carefully.

References

1. Kolb A , et al. Time-of-flight sensors in computer graphics . Eurographics State Art Rep . 2009 ; p. 119 - 34 .

2. dos Santos TR , et al. Correspondences search for surface-based intra-operative registration . Med Image Compute Comput Assist Int . 2010 ; 6362 : 660 - 7 .

3. Park SC , et al. Direct extraction of a simplified triangular mesh from a range image . Comput Aided Des Appl . 2006 ; 3 ( 5 ): 597 - 602 .

4. Dyn , et al. Optimizing 3D triangulations using discrete curvature analysis . Math Methods Curves Surf . 2000 ; p. 135 - 46 .

5. Kobbelt LP . A subdivision scheme for smooth interpolation of quad-mesh data . Eurographics . 1998 ; p. 1 - 12 .

6. Maier-Hein L , et al. Accounting for anisotropic noise in fine registration of time-offlight range data with high-resolution surface data . MICCAI . 2010 ; 6361 : 251 - 8 .

7. Koenderink , et al. Surface shape and curvature scales . Image Vis Comput . 1992 ; 10 ( 8 ): 557 - 65 .

8. Seitel A , et al. Time-of-Flight Kameras fu¨r die intraoperative Oberfla¨chenerfassung . Proc BVM . 2010 ; p. 11 - 5 .