CARGO: Multi-Scale Topological Analysis of Time-Evolving Shapes

我们建议为时间演化形状的自动分析发展理论基础和一套实用的计算工具。给定代表三维形状边界的一系列表面，其几何形状和拓扑结构随时间变化，我们建议构建一个高维多分辨率表示，我们将其命名为阿特拉斯过渡图（Atlas Transition Diagram，简称ATD），它将识别和跟踪三维形状随时间和分辨率变化的形态和拓扑特征。我们的ATD还会将一个图表关联到每个特征，从而提供一个表面参数化，自然地遵循家族中每个形状的分支和手柄。这些图表随着时间和分辨率平滑地演变，并在它们的公共边界上拓扑地粘合在一起，以提供连续映射S(r,t,u,v;f)；F)，即给定特征ff，分辨率rr，时间tt和两个参数u和v，将识别表面上的唯一点，并允许我们使用rr和tt跟踪其演变。理论基础和算法设计将导致构建和查询atd的有效系统的实际实现，远远超出了Morse理论，表面分割方法和多分辨率技术的简单扩展，这些技术迄今为止主要用于3D静态表面的探索。进化表面对许多科学和工程学科都很重要，包括医学、发育生物学、细胞生物学、计算流体动力学和计算机辅助设计。例如，它们可以代表肿瘤的生长，飞机机翼上漩涡的位置移动，或者人类胚胎手上手指的萌芽。我们建议开发和整合一套理论和算法工具，用于分析和自动可视化这些演变。这些工具将允许我们将不断演变的表面划分为特征，在这些特征上，表面形状及其演变的高级描述将基于这些特征。此外，它们将允许我们跟踪它们的点，从而跟踪表面属性，随着时间的推移，并通过纹理映射更好地可视化它们的演变，纹理映射随着特征不断演变，并突出它们的边界和自然方向。最后，这些工具将帮助我们支持关于演化表面拓扑变化的时间和性质的查询，这可能对科学数据集的自动分析和检索很重要。为了实现这些结果，我们建议建立一个由时间和分辨率独立或同时控制的表面表示，并将时间/分辨率域分解为表面拓扑（组件数量和通孔数量）及其划分为特征保持不变的单元。为了验证我们的理论贡献并增加其对社区的影响，我们计划为具有三角边界的动画对象开发一个原型实现。我们希望公开这个实现的源代码及其编程接口。我们设想探索与科学、工程、医学和生物学领域的应用程序开发人员的合作，以帮助我们改进和验证这种方法。

DMS-0138420Jarek RossignacWe propose to develop the theoretical foundations and a set of practical computing tools for the automatic analysis of time-evolving shapes. Given a family of surfaces that represent the boundary of a 3D shape whose geometry and topology change with time, we propose to construct a higher-dimensional multiresolution representation, which we have named Atlas Transition Diagram, abbreviated ATD, that will identify and track the morphological and topological features of the 3D shape as they evolve with time and with resolution. Our ATD will also associate a chart to each feature, thus providing a surface-parameterization that naturally follows the branches and handles of each shape in the family. The charts evolve smoothly with time and resolution and are topologically glued together at their common boundaries to provide a continuous mapping, S(r,t,u,v;f); f), that, given a feature ff, a resolution rr, a time tt, and two parameters u and v, will identify a unique point on the surface and will allow us to trace its evolution with rr and tt. The theoretical underpinnings and algorithmic designs that will lead to a practical implementation of an efficient system for building and querying ATDs go far beyond simple extensions of Morse theory, of surface segmentation approaches, and of multi-resolution techniques, which have so far been mainly explored for static surfaces in 3D.Evolving surfaces are important to many scientific and engineering disciplines, including medicine, developmental biology, cell biology, computational fluid dynamics and computer aided design. They may for example represent the growth of a tumor, the shifting in position of a vortex over an airplane wing, or the budding of fingers on the hand of a human embryo. We propose to develop and integrate a collection of theoretical and algorithmic tools for the analysis and automated visualization of such evolutions. These tools will allow us to partition the evolving surface into features upon which a high-level description of the shape of the surface and of its evolution will be based. Furthermore, they will allow us to track their points, and thus surface properties, through time and to better visualize their evolutions through texture maps that continuously evolve with the features and highlight their boundaries and natural orientation. Finally, these tools will help us support queries about the time and nature of topological changes in the evolving surface, which may be important for the automatic analysis and retrieval of scientific datasets. To achieve these results, we propose to build a surface representation that is controlled independently or simultaneously by time and resolution and to decompose the time/resolution domain into cells where the surface topology (number of components and through holes) and its partition into features remain constant. To validate our theoretical contributions and to increase their impact on the community, we plan to develop a prototype implementation for animated objects with triangulated boundaries. We expect to make the source code of this implementation and its programming interface publicly available. We envision exploring collaborations with application developers in Science, Engineering, Medicine and Biology to help us refine and validate this approach.