| 基于约束的部分枚举策略的空间关系图匹配算法研究 |
| |
| 引用本文： | 徐晓刚,孙正兴,刘文印.基于约束的部分枚举策略的空间关系图匹配算法研究[J].东南大学学报,2003,19(3):236-239. |
| |
| 作者姓名： | 徐晓刚 孙正兴 刘文印 |
| |
| 作者单位： | [1]南京大学计算机软件新技术国家重点实验室，南京210093 [2]香港城市大学计算机科学系，中国香港 |
| |
| 基金项目： | TheNationalNaturalScienceFoundationofChina(6990 3 0 0 6)andgrantfromtheResearchGrantsCounciloftheHongKongSpecialAdministrativeRegion,China (CityU 10 73 0 2E) |
| |
| 摘 要： | 本提出了一种基于约束的部分枚举空间关系图匹配策略．该策略通过使用在匹配过程中动态生成的2类匹配约束条件智能预测当前匹配状态的后继有效的枚举状态以跳过无效的中间匹配状态，达到状态空间剪枝的目的，可以有效降低空间关系图匹配过程中状态搜索空间．根据理论分析，该策略在最好情况下的时间复杂度为O(n^2)，在几乎很少发生的最坏情况下时间复杂度为O(n!)；其空间复杂度都是O(n)．所提出的方法已在笔研发的手绘草图识别系统Smart Sketchpad中取得了很好的识别效果．
|
| 关 键 词： | 图形识别 空间关系图 图匹配算法 部分枚举 状态搜索空间 匹配策略 |
Matching spatial relation graphs using a constrained partial permutation strategy |
| |
| Xu Xiaogang,Sun Zhengxing,Liu Wenyin.Matching spatial relation graphs using a constrained partial permutation strategy[J].Journal of Southeast University(English Edition),2003,19(3):236-239. |
| |
| Authors: | Xu Xiaogang Sun Zhengxing Liu Wenyin |
| |
| Abstract: | 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. |
| |
| Keywords: | spatial relation graph graph matching constrained partial permutation graphics recognition |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
