Computation of crowded geodesics on the universal Teichmueller space for planar shape matching in computer vision

通用 Teichmueller 空间上的拥挤测地线计算，用于计算机视觉中的平面形状匹配

• 批准号: 1318427
• 负责人: Akil Narayan
• 金额: $ 32.57万
• 依托单位: University of Massachusetts, Dartmouth
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2013
• 资助国家: 美国
• 起止时间: 2013-08-01 至 2015-10-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1318427&HistoricalAwards=false
• 关键词: Computation; crowded; geodesics; universal; Teichmueller

Quantifying the (dis)similarity between two shapes is a central problem in computer vision. One distance metric on the space of planar shapes is realized by identifying this space as a subset of the Universal Teichmueller Space, and equipping it with the Weil-Petersson metric. This results in a metric that is scale- and translation-invariant on shapes, and has unique geodesic flow between two shape endpoints. The work of this proposal develops robust computational methods for the computation of metric distances and geodesics between shapes on this space. The major difficulty lies in computations involving "crowded" shapes, i.e., those with elongated, winding, or extended protrusions. Such shapes stymie finite-precision computations because direct algorithms suffer from severe roundoff error. The major thrusts of this proposal develop algorithmic methodologies to address roundoff error and related issues: The Zipper conformal mapping algorithm will be augmented to produce accurate conformal maps for crowded shapes. The velocity field representation on a geodesic will be rewritten into a form that is resistant to roundoff error. The geodesic equation will be transformed into a expression that takes advantage of the aforementioned velocity field transformation, and can effectively flow between crowded shapes. The final phase of this project will demonstrate accurate geodesic flow and distance computations between crowded shapes. The methods developed under this project can be applied to several related problems in scientific computing: solutions to differential equations on irregular geometries through conformal mapping, conservative integration methods with ill-conditioned particle systems, and moving-mesh kernel approximations.The work of this project can contribute to far-reaching applications in scientific and computer vision problems: automated object recognition (e.g. projectile identification), outline classification (determination of an animal's species), medical imaging (usage of MRI to diagnose dementia and related diseases), and artificial intelligence (visual recognition and interpretation) to name a few. All computational deliverables (computer code, example simulations, documentation) will be made publicly available. Through the engagement of students in related research tasks, this project will contribute to the educational development of future engineers, mathematicians, and computer scientists.

量化两个形状之间的（不）相似性是计算机视觉中的一个核心问题。平面形状空间上的一个距离度量是通过将该空间识别为通用Teichmueller空间的子集并为其配备Weil-Petersson度量来实现的。这导致了一个度量，是规模和比例不变的形状，并具有独特的测地线流之间的两个形状端点。该提案的工作开发了强大的计算方法，用于计算该空间上形状之间的度量距离和测地线。主要困难在于涉及“拥挤”形状的计算，即，那些具有细长的、缠绕的或延伸的突起的。这种形状阻碍了有限精度的计算，因为直接算法遭受严重的舍入误差。该提案的主要目标是开发算法方法来解决圆形误差和相关问题：Zipper保角映射算法将被增强，以产生拥挤形状的精确保角映射。速度场在测地线上的表示将被改写成一种能抵抗旋转误差的形式。测地线方程将被转换成一个表达式，该表达式利用了前面提到的速度场变换，并且可以在拥挤的形状之间有效地流动。这个项目的最后阶段将展示精确的测地线流和拥挤形状之间的距离计算。该项目开发的方法可以应用于科学计算中的几个相关问题：通过保角映射解决不规则几何形状的微分方程，病态粒子系统的保守积分方法，以及移动网格核近似。该项目的工作可以在科学和计算机视觉问题中产生深远的应用：自动物体识别（例如，抛射体识别）、轮廓分类（确定动物的种类）、医学成像（使用MRI诊断痴呆症和相关疾病）和人工智能（视觉识别和解释）。所有计算交付成果（计算机代码、示例模拟、文档）都将公开提供。通过学生参与相关的研究任务，该项目将有助于未来的工程师，数学家和计算机科学家的教育发展。