Matching spatial relation graphs using a constrained partial permutation strategy  

基于约束的部分枚举策略的空间关系图匹配算法研究(英文)

作　　者：徐晓刚[1] 孙正兴[1] 刘文印[2] 

机构地区：[1]南京大学计算机软件新技术国家重点实验室,南京210093 [2]香港城市大学计算机科学系

出　　处：《Journal of Southeast University(English Edition)》2003年第3期236-239,共4页东南大学学报（英文版）

基　　金：TheNationalNaturalScienceFoundationofChina(6990 3 0 0 6)andgrantfromtheResearchGrantsCounciloftheHongKongSpecialAdministrativeRegion,China (CityU 10 73 0 2E)

摘　　要：A constrained partial permutation strategy is proposed for matching spatial relation graph (SRG), which is used in our sketch input and recognition system Smart Sketchpad for representing the spatial relationship among the components of a graphic object. Using two kinds of matching constraints dynamically generated in the matching process, the proposed approach can prune most improper mappings between SRGs during the matching process. According to our theoretical analysis in this paper, the time complexity of our approach is O(n 2) in the best case, and O(n!) in the worst case, which occurs infrequently. The spatial complexity is always O(n) for all cases. Implemented in Smart Sketchpad, our proposed strategy is of good performance.本文提出了一种基于约束的部分枚举空间关系图匹配策略 .该策略通过使用在匹配过程中动态生成的 2类匹配约束条件智能预测当前匹配状态的后继有效的枚举状态以跳过无效的中间匹配状态 ,达到状态空间剪枝的目的 ,可以有效降低空间关系图匹配过程中状态搜索空间 .根据理论分析 ,该策略在最好情况下的时间复杂度为O(n2 ) ,在几乎很少发生的最坏情况下时间复杂度为O(n !) ;其空间复杂度都是O(n) .所提出的方法已在笔者研发的手绘草图识别系统SmartSketch pad中取得了很好的识别效果 .

关 键 词：spatial relation graph graph matching constrained partial permutation graphics recognition 

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