基于最优子序列双射的骨架树匹配  

Skeleton tree matching based on optimal subsequence bijection

作　　者：陈展展[1] 汤进[1] 罗斌[1] 孔敏[1] 

机构地区：[1]安徽大学计算智能与信号处理教育部重点实验室,合肥230039

出　　处：《计算机工程与应用》2011年第1期162-165,共4页Computer Engineering and Applications

基　　金：国家自然科学基金No.60772122;安徽省教育厅自然科学研究重点项目No.KJ2008A033;No.KJ2007A072~~

摘　　要：基于图描述的骨架图匹配大多考虑骨架图的拓扑结构,使得匹配精度受到影响。先通过骨架构造以骨架中心为根节点的骨架树,使用骨架中心到骨架端点测地路径等信息来描述骨架树的叶子节点,利用改进的最优子序列双射时序匹配算法来确定两幅骨架树叶子节点的匹配关系,该算法不考虑骨架树的拓扑结构,只匹配骨架树的叶子节点。通过匹配实验结果和检索实验结果,表明该方法有效地提高了匹配精度。Most graph-based skeleton matching algorithms consider the topological structure of skeleton graph,which affects matching accuracy.An improved algorithm is proposed for skeleton matching.This algorithm constructs the skeleton tree with root node based on the center of skeleton at first,then describes leaf nodes with information of geodesic path from the skeleton center to endpoints.An Improved Optimal Subsequence Bijection（IOSB） time series matching algorithm is proposed to determine the relations between the leaf nodes of two skeleton trees.It does not consider the topological structure of skeleton tree.It only matches leaf nodes.The experimental results show that this method can improve the matching accuracy.

关 键 词：骨架树 图匹配 测地路径 时序匹配 

分 类 号：TP391.41[自动化与计算机技术—计算机应用技术]