Recognition of Shapes by Editing Shock Graphs
Recognition of Shapes by Editing Shock Graphs
复制标题
DOI：
10.1109/iccv.2001.10050
复制
发表时间：
2001
期刊：
影响因子：
--
通讯作者：
Thomas B. Sebastian;P. Klein;B. Kimia
中科院分区：
文献类型：
--
作者：
Thomas B. Sebastian;P. Klein;B. Kimia
提出了一种新的识别框架，该框架基于二维形状轮廓的激波图匹配，其中两个形状之间的距离定义为一个形状到另一个形状变形的最小动作路径的代价。三个关键思想使这一框架的实施切实可行。首先，通过在形状上定义等价类来划分形状空间，其中具有相同激波图拓扑的两个形状被认为是等价的。其次，通过定义具有相同激波图转变序列的所有变形作为等价，对变形空间进行离散化。激波过渡是沿变形的激波图形拓扑发生变化的点。第三，采用图编辑距离算法，在所有可能的转移序列空间中进行搜索，在多项式时间内找到全局最优的转移序列。实验结果表明，该方法在存在遮挡、局部清晰度和变形、阴影和高光、视点变化和边界扰动等各种视觉变换的情况下是有效的。索引到包含大约100个形状的两个独立数据库中，结果是前三个匹配和接下来的三个匹配的准确性。
This paper presents a novel recognition framework which is based on matching shock graphs of 2D shape outlines, where the distance between two shapes is defined to be the cost of the least action path deforming one shape to another. Three key ideas render the implementation of this framework practical. First, the shape space is partitioned by defining an equivalence class on shapes, where two shapes with the same shock graph topology are considered to be equivalent. Second, the space of deformations is discretized by defining all deformations with the same sequence of shock graph transitions as equivalent. Shock transitions are points along the deformation where the shock graph topology changes. Third, we employ a graph edit distance algorithm that searches in the space of all possible transition sequences and finds the globally optimal sequence in polynomial time. The effectiveness of the proposed technique in the presence of a variety of visual transformations including occlusion, articulation and deformation of parts, shadow and highlights, viewpoint variation, and boundary perturbations is demonstrated. Indexing into two separate databases of roughly 100 shapes results in accuracy for top three matches and for the next three matches.