CCF: AF: Small: Volumetric Mesh Mapping

CCF：AF：小：体积网格映射

• 批准号: 0916235
• 负责人: Arie Kaufman
• 金额: $ 50万
• 依托单位: SUNY at Stony Brook
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2009
• 资助国家: 美国
• 起止时间: 2009-07-15 至 2013-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0916235&HistoricalAwards=false
• 关键词: CCF; AF; Small; Volumetric; Mesh

With the rapid development of volumetric acquisition and computational technologies in numerous applications, such as industrial inspection and medical imaging, there is a growing need for tools for processing such datasets to analyze the topology and geometry, including volumetric mapping to canonical structures, volumetric registration, volumetric feature extraction, geometric database indexing, volumetric parameterization, etc. In this project the PI and his team will develop rigorous algorithms for computing the topology and geometry for general mesh volumes, a nontrivial and fundamentally more challenging problem than for surfaces. To capture the tunnels, handles, and voids of a volume, homology and cohomology groups need to be computed; to describe the tangling, twisting, and linking patterns among the handles, tunnels, and voids, fundamental groups need to be computed as well. Because it is NP-hard to verify whether two fundamental groups are isomorphic, conventional algebraic topological methods are inadequate and geometric structures such as Ricci flows need to be incorporated. Thus, a major focus of this project is development of computational algorithms for Ricci flows. On the other hand, it is highly desirable to map one or more volumes to a canonical domain, in order to support database indexing and volume registration, yet it is an open problem to obtain canonical geometric structures for volumes using computational methodologies. The PIs are confident that Ricci flows are the key to solving this problem, too. Project outcomes will include rigorous computational algorithms for processing volumetric data based on 3-manifold topology and geometric structures, which will be developed in a sequence of interrelated steps as follows: design and implementation of algorithms to compute topological invariants, including homology, cohomology groups, and fundamental groups; design and implementation of algorithms to compute canonical geometric structures, Riemannian metrics with constant section curvatures for discrete 3-manifolds, based on curvature flow and differential forms; design and implementation of algorithms to incorporate canonical geometric structures to the topological invariants, such as finding the closed geodesics and minimal surfaces as homotopy class representatives; design and implementation of algorithms for volumetric mapping to canonical structures, volumetric registration, volumetric feature extraction, and volumetric parameterization; design and implementation of parallel version of the above algorithms, and use of a GPU cluster for speed up; and investigation of the complexity, the stability, and the convergence rate of the above algorithms.Broader Impacts: The PIs will build and disseminate a concrete set of software tools for computing and visualizing the topology and geometric structures for mesh volumes, including volumetric parameterization, volumetric registration, volumetric mapping to canonical structures, fundamental groups computation, and topological and geometric feature extraction. Diverse disciplines such as engineering, science, medicine, computer graphics, vision, scientific computing, and mathematics, as well as a host of industrial applications, will directly benefit from these tools, which can be used for volumetric texture mapping, spline volume construction, volumetric deformation, etc.

随着体积采集和计算技术在诸如工业检查和医学成像的许多应用中的快速发展，越来越需要用于处理这样的数据集以分析拓扑和几何结构的工具，包括到规范结构的体积映射、体积配准、体积特征提取、几何数据库索引、体积参数化、在这个项目中，PI和他的团队将开发严格的算法，用于计算一般网格体积的拓扑和几何结构，这是一个非常重要的问题，从根本上说比表面更具挑战性。 为了捕捉一个体积的隧道、把手和空洞，需要计算同调群和上同调群;为了描述把手、隧道和空洞之间的缠结、扭曲和连接模式，也需要计算基本群。 由于验证两个基本群是否同构是NP难的，传统的代数拓扑方法是不够的，需要结合几何结构，如Ricci流。 因此，这个项目的一个主要重点是发展计算算法的里奇流。 另一方面，为了支持数据库索引和体积配准，非常希望将一个或多个体积映射到规范域，但是使用计算方法获得体积的规范几何结构是一个开放的问题。 PI相信Ricci流也是解决这个问题的关键。 项目成果将包括用于处理基于三维拓扑和几何结构的体积数据的严格计算算法，这些算法将按照以下一系列相互关联的步骤开发：设计和实施计算拓扑不变量的算法，包括同调、上同调群和基本群;基于曲率流和微分形式，设计和实现计算离散三维流形的正则几何结构、具有常截面曲率的黎曼度量的算法;设计和实现将规范几何结构与拓扑不变量结合的算法，例如找到闭合测地线和最小曲面作为同伦类代表;设计和实现用于将体积映射到规范结构、体积配准、体积特征提取和体积参数化的算法;设计并实现了上述算法的并行版本，并使用GPU集群进行加速;并对上述算法的复杂度、稳定性和收敛速度进行了研究。PI将建立和传播一套具体的软件工具，用于计算和可视化网格体积的拓扑和几何结构，包括体积参数化、体积配准、体积映射到规范结构、基本群计算以及拓扑和几何特征提取。 工程、科学、医学、计算机图形学、视觉、科学计算和数学等不同学科以及许多工业应用将直接受益于这些工具，这些工具可用于体积纹理映射、样条体构造、体积变形等。