Biomedical Engineering Reference
In-Depth Information
(d) Find all voxels which are inside the deformed mesh and the position of their
center inside the mesh (the tetrahedron containing the center and the barycentric
coordinates of the center in that tetrahedron); perform linear interpolation of the
nodal displacements using the barycentric coordinates, to find the corresponding
point in the moving image.
Compared with the transformations used in image-based registration, this trans-
formation is clearly much more computationally expensive, especially steps (b)
(finding voxels which are inside the mesh) and step (d) (3D scattered data interpo-
lation). Nevertheless, this transformation has to be applied only once, while the
transformations used in image-based registration methods are applied multiple
times as part of the optimization process.
3 Algorithm Implementation and Transformation Example
We performed an initial implementation of the above algorithm inMatlab, as it provides
a function (tsearchn) for performing the most complicated part of the implementation—
the 3D scattered data interpolation. The interpolation function expects a Delauney
tessellation which has to be generated with another function (delaunayn). One side
effect of using this function is that the generated tessellation includes the convex hull of
the nodes, and therefore areas that are outside the finite element mesh are included in the
tessellation. In our case, these areas were small and did not have a great influence on the
results.
The deformed image is generated slice by slice and saved in Dicom format. Only
the part of the preoperative image needed for generating the current slice is read in
memory, and this information is updated every time a new slice is generated. In this
way, we can apply the transformation to very large 3D images even on computers
with limited amounts of memory (RAM).
Two transformation results obtained using the implemented algorithm are
presented in Fig.
2
. The voxel intensity was interpolated using cubic interpolation.
For the first case, the preoperative image had 256
60 voxels and the
tessellation used for displacement interpolation had 112,008 tetrahedrons. For the
second case, the preoperative image had 512
256
176 voxels and the tessella-
tion used for displacement interpolation had 94,137 tetrahedrons.
The runtime increases linearly with the number of voxels in the image, from
32 min for the first case to more than 6 h for the second case. More than 99% of the
computation time was spent finding the position of voxel centers inside the tessel-
lation (steps b and d). The computations were done on a Intel Core 2 Quad CPU at
2.83 GHz with 4 GB RAM running Windows XP.
To add more realism to the computed deformed image one additional step can be
performed at the beginning of the algorithm—the deletion of the preoperative
image region corresponding to the removed skull in the craniotomy area. This is
512
