Efficient Graph Matching for Video Indexing
作者： K. Shearer , H. Bunke , S. Venkatesh , D. Kieronska
DOI: 10.1007/978-3-7091-6487-7_6
关键词: Preprocessor 、 Theoretical computer science 、 Computer science 、 Search engine indexing 、 Graph database 、 Computational complexity theory 、 Time complexity 、 Matching (graph theory) 、 Subgraph isomorphism problem 、 Image retrieval
摘要: Traditionally graph algorithms have been of restricted use due to their exponential computational complexity in the general case. Recently a new class for subgraph isomorphism detection has proposed, one these having quadratic time complexity. These preprocessing step allow rapid matching an input against database model graphs. We present algorithm largest common that provides significant performance improvement over previous algorithms. This is based on work preprocessed by Messmer and Bunke [3].
core.ac.uk
springer.com
sci-hub.st 参考文章(14)
Suh-Yin Lee, Ming-Chwen Yang, Ju-Wei Chen, Signature file as a spatial filter for iconic image database Journal of Visual Languages and Computing. ,vol. 3, pp. 373- 397 ,(1992) , 10.1016/1045-926X(92)90008-A
H Bunke, G Allermann, Inexact graph matching for structural pattern recognition Pattern Recognition Letters. ,vol. 1, pp. 245- 253 ,(1983) , 10.1016/0167-8655(83)90033-8
Si Wei Lu, Ying Ren, Ching Y. Suen, Hierarchical attributed graph representation and recognition of handwritten Chinese characters Pattern Recognition. ,vol. 24, pp. 617- 632 ,(1991) , 10.1016/0031-3203(91)90029-5
Shi-Kuo Chang, Qing-Yun Shi, Cheng-Wen Yan, Iconic Indexing by 2-D Strings IEEE Transactions on Pattern Analysis and Machine Intelligence. ,vol. PAMI-9, pp. 413- 428 ,(1987) , 10.1109/TPAMI.1987.4767923
E.K. Wong, Model matching in robot vision by subgraph isomorphism Pattern Recognition. ,vol. 25, pp. 287- 303 ,(1992) , 10.1016/0031-3203(92)90111-U
Kim Shearer, Svetha Venkatesh, Dorota Kieronska, Spatial Indexing for Video Databases Journal of Visual Communication and Image Representation. ,vol. 7, pp. 325- 335 ,(1996) , 10.1006/JVCI.1996.0028
Hideyuki Tamura, Naokazu Yokoya, Image database systems: A survey Pattern Recognition. ,vol. 17, pp. 29- 43 ,(1984) , 10.1016/0031-3203(84)90033-5
G. Levi, A note on the derivation of maximal common subgraphs of two directed or undirected graphs Calcolo. ,vol. 9, pp. 341- 352 ,(1973) , 10.1007/BF02575586
H. Bunke, B. T. Messmer, Recent Advances in Graph Matching International Journal of Pattern Recognition and Artificial Intelligence. ,vol. 11, pp. 169- 203 ,(1997) , 10.1142/S0218001497000081
Suh-Yin Lee, Fang-Jung Hsu, Spatial reasoning and similarity retrieval of images using 2D C-string knowledge representation Pattern Recognition. ,vol. 25, pp. 305- 318 ,(1992) , 10.1016/0031-3203(92)90112-V