|Table of Contents|

[1] Xu Xiaogang, Sun Zhengxing, Liu Wenyin,. Matching spatial relation graphs using a constrainedpartial permutation strategy [J]. Journal of Southeast University (English Edition), 2003, 19 (3): 236-239. [doi:10.3969/j.issn.1003-7985.2003.03.007]
Copy

Matching spatial relation graphs using a constrainedpartial permutation strategy()
基于约束的部分枚举策略的空间关系图匹配算法研究
Share：

Journal of Southeast University (English Edition)[ISSN:1003-7985/CN:32-1325/N]

Volumn:
19
Issue:
2003 3
Page:
236-239
Research Field:
Computer Science and Engineering
Publishing date:
2003-09-30

Info

Title:
Matching spatial relation graphs using a constrainedpartial permutation strategy
基于约束的部分枚举策略的空间关系图匹配算法研究
Author(s):
Xu Xiaogang1;  Sun Zhengxing1;  Liu Wenyin2
1Department of Computer Science and Technology, Nanjing University, Nanjing 210093, China
2Department of Computer Science, City University of Hong Kong, Hong Kong, China
徐晓刚1;  孙正兴1;  刘文印2
1南京大学计算机软件新技术国家重点实验室, 南京 210093; 2香港城市大学计算机科学系, 中国香港
Keywords:
spatial relation graph;  graph matching;  constrained partial permutation;  graphics recognition
空间关系图;  图匹配;  约束的部分枚举;  图形识别
PACS:
TP391.4
DOI:
10.3969/j.issn.1003-7985.2003.03.007
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(n2) 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).所提出的方法已在笔者研发的手绘草图识别系统Smart Sketchpad中取得了很好的识别效果.

References:

[1] Foggia P, Sansone C, Vento M. A database of graphs for isomorphism and sub-graph isomorphism benchmarking [A]. In: Proc of 3rd IAPR-TC15 Workshop on Graph-Based Representations in Pattern Recognition [C]. Ischia, 2001.
[2] Bunke H. Recent developments in graph matching [A]. In: Proc of 15th International Conference on Pattern Recognition [C]. Barcelona, 2000, 2: 117-124.
[3] Ullman J. An algorithm for sub-graph isomorphism [J]. Journal of the Association for Computing Machinery, 1976, 23(1): 31-42.
[4] Corneil D G, Gotlieb C C. An efficient algorithm or graph isomorphism [J]. Journal of the Association of Computing Machinery, 1970, 17(1): 51-64.
[5] Schmidt D C, Druffel L E. A fast backtracking algorithm to test directed graphs for isomorphism using distance matrices[J]. Journal of the Association of Computing Machinery, 1976, 23(3): 433-445.
[6] Mckay B D. Practical graph isomorphism [J]. Congressus Numerantium, 1981, 30(1): 45-87.
[7] Cordella L P, Foggia P, Sansone C, et al. Evaluating performance of the VF graph matching algorithm [A]. In: Proc of 10th International Conference on Image Analysis and Processing[C]. 1999. 1172-1177.
[8] Cordella L P, Foggia P, Sansone C. An improved algorithm for matching large graphs [A]. In: Proc of 3rd IAPR-TC15 Workshop on Graph-Based Representation in Pattern Recognition[C]. Ischia, 2001.
[9] Xu X G, Sun Z X, Peng B B, et al. A SRG-based online composite graphic recognition strategy for sketch-based user interface [A]. In: Proc of the 1st International Conference on Machine Learning and Cybernetics[C]. Beijing, 2002. 723-728.
[10] Liu W Y, Qian W, Xiao R, et al. Smart sketchpad — an on-line graphics recognition system [A]. In: Proc of the ICDAR2001 Conference [C]. 2001. 1050-1054.
[11] Liu W Y, Jin X Y, Sun Z X. Sketch-based user interface for inputting graphic objects on small screen devices [J]. Lecture Notes in Computer Science, 2002, 2390: 67-80.
[12] Xu X G, Liu W Y, Jin X Y, et al. Sketch-based user interface for creative tasks [A]. In: Proc of 5th Asia Pacific Conference on Computer Human Interaction[C]. Beijing, 2002. 560-570.

Memo

Memo:
Biographies: Xu Xiaogang(1977—), male, master; Sun Zhengxing(corresponding author), male, doctor, associate professor, szx@nju.edu.cn.
Last Update: 2003-09-20