Computational geometry for polygonal reconfiguration, pattern analysis and recognition and music information retrieval

用于多边形重构、模式分析和识别以及音乐信息检索的计算几何

• 批准号: 9293-2009
• 负责人: Toussaint, Godfried
• 金额: $ 2.19万
• 依托单位: McGill University
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2009
• 资助国家: 加拿大
• 起止时间: 2009-01-01 至 2010-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=420798
• 关键词: Computational; geometry; polygonal; reconfiguration; pattern

The proposed research aims to develop efficient algorithms for solving geometric problems that arise in the following areas. (1) The exploration of algorithms for the reconfiguration of different types of linkages in 2 and 3 dimensional space, under various restrictions on the types of motions allowed. Another goal is to explore under what conditions linkages are "stuck" in the sense that they cannot be reconfigured to a flat convex configuration. These results are relevant, not only to robotics, but to protein folding in molecular biology. (2) One of the most promising approaches to pattern recognition is the nearest-neighbor decision rule (also referred to as instance-based learning). It is proposed to improve the space and time efficiency of state-of-the-art nearest neighbor rule algorithms, by incorporating proximity graphs. A second objective is to develop new measures of string similarity and polygonal chain similarity for pattern recognition problems. (3) It is proposed to explore the application of computational geometric tools to problems that arise in music information retrieval and music theory. These problems range from measuring the similarity of rhythms and melodies, to performing cluster and phylogenetic analyses of families of rhythms, with the goal of obtaining a deeper understanding of both, music theory and practical applications to music information retrieval. (4) Traditionally the scientific analysis of textiles has been carried out on several physical structural levels of the fabrics. However, a scientific analysis of the geometric structure of the patterns that appear on the textiles has been largely ignored. We propose a new approach to the scientific study of textiles that breaks with this tradition: the phylogenetic analysis of geometric patterns that decorate the textiles. At the heart of our approach is the design of a measure of dissimilarity between two textile patterns, that mimics the way in which biologists measure the dissimilarity between two DNA molecular sequences, i.e., the minimum number of mutations (simple local and global transformations) required to transform one textile pattern into the other. This research will have an impact of image-based search on the internet, as well as textile retrieval systems for use in museums and libraries.

拟议的研究旨在开发有效的算法来解决以下领域中出现的几何问题。 (1) 探索在允许的运动类型受到各种限制的情况下，在 2 维和 3 维空间中重新配置不同类型连杆的算法。另一个目标是探索在什么条件下连杆会“卡住”，因为它们无法重新配置为平坦的凸配置。这些结果不仅与机器人技术相关，而且与分子生物学中的蛋白质折叠相关。 (2) 最有前途的模式识别方法之一是最近邻决策规则（也称为基于实例的学习）。提出通过合并邻近图来提高最先进的最近邻规则算法的空间和时间效率。第二个目标是为模式识别问题开发字符串相似性和多边形链相似性的新度量。 (3)建议探索计算几何工具在音乐信息检索和音乐理论中出现的问题的应用。这些问题的范围从测量节奏和旋律的相似性，到对节奏族进行聚类和系统发育分析，目的是更深入地了解音乐理论和音乐信息检索的实际应用。 (4) 传统上，纺织品的科学分析是在织物的几个物理结构层面上进行的。然而，对纺织品上出现的图案的几何结构的科学分析在很大程度上被忽视了。我们提出了一种打破这一传统的纺织品科学研究新方法：对装饰纺织品的几何图案进行系统发育分析。我们方法的核心是设计两种纺织品图案之间的差异性测量方法，它模仿生物学家测量两个 DNA 分子序列之间的差异性的方式，即所需的最小突变数量（简单的局部和全局转换）将一种纺织图案转变为另一种图案。这项研究将对互联网上基于图像的搜索以及博物馆和图书馆使用的纺织品检索系统产生影响。