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 距离。针对这些问题，将研究固定参数易处理的精确算法和多边形时间逼近算法。该项目还将考虑近似的硬度。对于度量扭曲主题，提出的问题包括计算简单多边形之间和离散点集之间的度量扭曲。将研究精确算法和近似算法。目标不仅是了解精确变换背后的数学原理，还要了解近似变换是否可以在一定质量保证的情况下实现更快的算法；目前相似性度量的大多数应用都是启发式的，并且没有保证。测量几何对象之间的相似性是一个基本问题，具有许多应用，因此该项目及其培养的学生将对许多领域的理论和实践产生潜在影响。