CNPq/NSF, RUI: Surface and Volume Meshes for Volumetric Imaging Data

在许多需要几何对象模型的计算应用中，曲面或体积的离散近似是必要的。这些应用程序通常假设所考虑的几何域被分成小而简单的块（通常是二维的三角形或四边形，以及三维的四面体或六面体），称为有限元。有限元素的集合称为网格。其中一个重要的应用领域是医学成像，其中用于建模解剖的高质量网格，表示为基于体素的图像，对于医学数据的计算机辅助临床分析至关重要。由四边形/六面体（四边形/六面体）单元组成的网格比三角形/四面体单元提供更低的网格复杂性和更好的解决质量。然而，对于任意三维几何图形的四边形/六边形网格的生成是一个难题，并且生成具有可证明质量保证的网格的算法仅适用于某些有限类型的输入。本研究解决了与从体积成像数据中获得的三维几何图形生成四边形表面网格和六面体体积网格相关的几何、组合和算法问题。将利用数字拓扑和图论的工具来设计算法，为基于体素的图像的表面表示生成保证质量的四边形网格。利用作为本研究的一部分开发的四边形表面网格划分算法，将依次设计用于数字体的六面体网格生成的鲁棒方法。许多与四边形/六边形网格生成相关的基本几何问题仍然没有答案。对于由体积成像数据确定的特殊几何类型，对这些问题的正式理解对于设计可实现的算法至关重要，这些算法可以保证网格质量。该研究项目还涉及与医学成像专家合作，他们将通过有限元方法评估和验证所有网格算法，用于人体器官体积MR图像的三维非刚性图像配准。目前大多数图像配准方法都是二维的。通过保证质量的体积网格，可以提高配准精度，这将对医疗数据的临床研究产生巨大影响，并使医疗从业者受益匪浅。

Discrete approximations of a surface or volume are necessary in numerous computational applications that require models of geometric objects. These applications typically assume that the geometric domain under consideration is divided into small, simple pieces (typically triangles or quadrilaterals in two dimensions, and tetrahedra or hexahedra in three) called finite elements. The collection of finite elements is referred to as a mesh. One such important application area is medical imaging, where high-quality meshes for modeling anatomy, represented as voxel-based images, are critical for computer-assisted clinical analysis of medical data. Meshes made of quadrilateral/hexahedral (quad/hex) elements offer lower mesh complexity and better solution quality than their triangular/tetrahedral counterparts. However, the generation of quad/hex meshes for arbitrary three-dimensional geometries is a difficult problem, and algorithms to generate meshes with provable guarantees on quality are available only for some restricted types of input. This research addresses geometric, combinatorial, and algorithmic questions related to the generation of quadrilateral surface meshes and hexahedral volume meshes for three-dimensional geometries obtained from volumetric imaging data.Tools from digital topology and graph theory will be exploited to design algorithms to generate quadrilateral meshes of guaranteed quality for surface representations of voxel-based images. Robust methods for hexahedral mesh generation for digital volumes will in turn be designed by utilizing quadrilateral surface meshing algorithms developed as part of this research. Many fundamental geometric questions related to quad/hex mesh generation remain unanswered. A formal understanding of these questions for the special types of geometries determined by volumetric imaging data is critical for the design of implementable algorithms that provide guarantees on mesh quality. This research project also involves collaboration with medical imaging experts, who will provide evaluation and validation of all meshing algorithms via finite element methods for three-dimensional, non-rigid image registration of volumetric MR images of human organs. Most image registration methods in current practice remain two-dimensional. Improved registration accuracy made possible by guaranteed-quality volume meshes would have enormous impact on clinical studies of medical data and greatly benefit medical practitioners.