[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 Xiaogang¹;  Sun Zhengxing¹;  Liu Wenyin²

¹Department of Computer Science and Technology, Nanjing University, Nanjing 210093, China
²Department of Computer Science, City University of Hong Kong, Hong Kong, China

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(n²) 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.

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.

Common functions