Internal:Adaptive Meshing For APBNRR

Problem Description

Reducing the error for Non-Rigid Registration (NRR) applications depends among other factors on the Equi-distribution of the registration points within the mesh. The goal of this project is to explore metric adaptive methods from CFD and apply them if possible in the area of NRR.

Background

see section 2.2 in about why equidistribution might help

Mesh Requirements

In a set of application specific mesh requirements for NRR were presented.

• (R1) Equi-distribution of the registration points w.r.t. mesh vertex cells  :

  small number of registration points (e.g., less than 10, but greater than 0) within the vertex cell complex makes the formulation more sensitive to outliers and introduces additional displacement error

• (R2) Minimization of the approximation error at registration points :

  error of the displacements recovered at registration points can be reduced locally by using smaller mesh elements.

• (R3) Prevention of tetrahedron inversion during mesh deformation:

  while the interpolation error shown does not depend on the tetrahedron shape, inversion or collapse of a tetrahedron will result in an unrealistic deformation field, e.g., points inside the different tetrahedra can map to the same image location. We can attempt to remedy this problem by adjusting element size locally according to the expected deformation.

Alongside the application-specific requirements we would also like to adhere to the following generic requirements which are related with FEM calculations and image-based mesh generatio in general

• (R4) The mesh boundary (triangulation) should be close to the surface of the image.
• (R5) Mesh size should be minimized to reduce the computational costs.
• (R6) Mesh elements should not have small angles

some of these rules work against each other. For example we require small elements (R2) to reduce the error but we also need a small size (R5) of a mesh.

Methods

Method 1 :Isotropic Sizing Functions based on knn

Already in two attempts were made.

1. Creating new splitting rules in a BCC-based mesh generator and
2. Creating a sizing function for TetGen and NETGEN.

The sizing function of the second approach is based on a distance criterion. In particular:

The sizing value at each mesh vertex was initialized with the distance to the kth registration point closest to it, to reflect the density of the registration point distribution. The idea here is that the shape of a perfect mesh vertex cell complex is close to a ball with the radius prescribed by the background mesh. Where vertex cell complex is defined as the union of all the elements attached to a vertex.

Method 2 : Metric-based Anisotropic adaptation based on knn

The method above creates adaptive meshes but is does not capture the density of the landmarks efficienty due to the reason than only the k-th point is used and the relative locations of the rest of the k-1 landmarks is ignored. Going back to the paper

The idea here is that the shape of a perfect mesh vertex cell complex is close to a ball with the radius prescribed by the background mesh.

Building upon this observation one could create bounding volumes arround each vertex that meet the density requirements of the problem. For linear tetrahedral meshes which is the interset in this work boundaing volumes can be replaced with bounding ellipsoids and specifically the smallest bounding ellipsoid that is centered at a vertex and encloses the k-closest registration points. See for example Figure 1.

Figure 1 Comparison of two methods

The smallest bounding ellipsoid is a geometrical construction that used a lot in optimization and specifically in interger programing [CITE]. As such there are existing algorithms like the Khachiyan algorithm which we use here in order to consutrct such ellipsoids. The choise of ellipsoid has another significant advantage: It has a natural mapping to the set of positive-definite matrices. This means that for every ellipsoid we can construct a 3x3 positive-definite matrix that corresponds to it.

Another field where positive-definite matrices are used is in metric-adaptive mesh adaptation where an a posteriori error estimate of the interpolation error guides the mesh adaptation . One of the popular methods is to construct a metric tensor expressed as positive definite matrices based on the Hessian reconstructed from a scalar variable.

In this work however we have a purely geometrical approach where we uise the metric derived from the ellipsoids directly as a way to control the density of the mesh and ultimately the error between the registred and the intra-operative image. Section XX presents the results.

Future Work

As part of the mesh adaptation , the quality of the mesh is improved significantly . This is possible since the mesh adaptation software is not constrained by the Delaunay criterion and moreorev is has mesh improvment cababilities not yet implemented in the image to mesh tools. It would be of interested to study the effect of adaptation on the condition number of stiffness matrix of the solver as well as to the running time of the solver.