平面简单闭合曲线的树编辑距离算法及其比较

本文探讨了一种针对平面内简单封闭形状的树编辑距离算法，旨在提供一种图形算法方法来比较这些复杂图形。作者团队由计算机视觉研究员和算法专家组成，他们之前的尝试是基于金和拉格拉jan提出的启发式方法，该方法通过解决一个二次规划问题来比较图形。这种方法存在一些局限性，因此金提出了采用树编辑距离作为替代方案。 在论文中，作者定义了他们版本的树编辑距离（区别于文献中已有的定义），这是一种衡量两个嵌入在平面上的树结构之间差异的方法。传统的树编辑距离通常涉及到插入、删除或修改节点以使两棵树结构变得相似。然而，这里的方法更加专注于简单封闭曲线的特性，将形状转换为其对应的骨架树，即曲线轮廓上的关键点及其连接关系构成的树形结构。 作者首先提出将形状表示为其骨架树，这是一个关键步骤，因为这样可以简化形状比较的复杂度，使其更容易处理。然后，他们设计了一个多项式时间的算法，用于计算两个骨架树之间的树编辑距离。这个算法考虑了树的拓扑结构和节点间的关系，旨在找到从一棵树到另一棵所需的最小编辑操作序列，包括节点添加、移除或替换，以使得两棵树在某种程度上变得一致。 算法的核心在于寻找最有效的编辑路径，这可能涉及到局部优化策略，同时也需确保算法的时间效率，以便在实际应用中能够快速有效地进行形状比较。由于骨骼树的特性，这种方法对于识别形状的相似性和变化非常有用，特别是在计算机视觉领域，如图像分割、物体识别和形状匹配中。 总结来说，本文的主要贡献是引入了一种新的树编辑距离算法，专为平面内的简单封闭形状设计，它通过树形结构的比较解决了之前图形比较方法的不足，为形状分析提供了更为精确和高效的工具。通过骨架树的构建和编辑距离的计算，该算法为计算机视觉研究者提供了一种标准化且实用的图形比较框架。