CRII: AF: Measuring similarity between geometric objects

CRII：AF：测量几何对象之间的相似性

• 批准号: 1566624
• 负责人: Amir Nayyeri
• 金额: $ 17.48万
• 依托单位: Oregon State University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2016
• 资助国家: 美国
• 起止时间: 2016-05-01 至 2019-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1566624&HistoricalAwards=false
• 关键词: CRII; AF; Measuring; similarity; between

Measuring similarity between geometric objects is a common task in many applications: detecting change in a medical scan, recognizing and indexing content in an image or video, comparing protein structures, or automatically picking the right object from a conveyor belt. Input images, shapes, or models come in different representations that have to be transformed to compare them to a large database of possibilities. This project explores transformations of certain classes (nearly affine transformations) using tools like limited Frechet distance and small metric distortions. Specific proposed problems include computing Frechet distances between terrains and between polygons with holes. Both fixed parameter tractable exact algorithms and polygonal time approximation algorithms will be studied for these problems. The project will also consider the hardness of approximation. For the topic of metric distortions, the proposed problems include computing metric distortions between simple polygons and between discrete point sets. Both exact and approximation algorithms will be studied. The goal is not only to understand the mathematics behind exact transformations, but also to see if approximate transformations will allow faster algorithms with some quality guarantees; most application of similarity measure at present is heuristic, and does not come with guarantees. Measuring similarity between geometric objects is a fundamental problem and has many applications, so this project, and the students that it trains, will have potential impact on theory and practice in many areas.

在许多应用程序中，测量几何对象之间的相似性是一项常见的任务：检测医疗扫描的变化，识别和索引图像或视频中的内容，比较蛋白质结构，或自动从输送带中选择正确的对象。输入图像，形状或模型具有不同的表示形式，必须对其进行转换以将它们与大型可能性数据库进行比较。该项目使用有限的Frechet距离和小型度量失真等工具探索了某些类别（几乎仿射转换）的转换。具体提出的问题包括计算地形之间的特雷希特距离以及带有孔的多边形之间的距离。对于这些问题，将研究固定参数可拖动的精确算法和多边形时间近似算法。该项目还将考虑近似的硬度。对于度量失真的主题，提出的问题包括计算简单多边形之间以及离散点集之间的度量扭曲。将研究精确和近似算法。目标不仅是了解精确转换背后的数学，而且还要了解近似转换是否允许具有一些质量保证的算法更快；目前，大多数相似度措施的应用都是启发式方法，并且没有保证。测量几何对象之间的相似性是一个基本问题，并且有许多应用，因此该项目以及它训练的学生将对许多领域的理论和实践产生潜在的影响。