Error correcting graph matching: On the influence of the underlying cost function

被引：140

作者：

Bunke, H ^{[1
]}

机构：

[1] Univ Bern, Inst Informat & Angew Math, CH-3012 Bern, Switzerland

来源：

IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE | 1999年 / 21卷 / 09期

关键词：

graph; subgraph; maximum common subgraph; graph isomorphism; subgraph isomorphism; graph matching; error correcting graph matching; cost function; edit operation; graph edit distance;

D O I：

10.1109/34.790431

中图分类号：

TP18 [人工智能理论];

学科分类号：

081104 ; 0812 ; 0835 ; 1405 ;

摘要：

This paper investigates the influence of the cost function on the optimal match between two graphs. It is shown that, for a given cost function, there are an infinite number of other cost functions that lead, for any given pair of graphs, to the same optimal error correcting matching. Furthermore, it is shown that well-known concepts from graph theory, such as graph isomorphism, subgraph isomorphism, and maximum common subgraph, are special cases of optimal error correcting graph matching under particular cost functions.

引用

页码：917 / 922

页数：6

共 17 条

[1] On a relation between graph edit distance and maximum common subgraph [J].

Bunke, H .

PATTERN RECOGNITION LETTERS, 1997, 18 (08) :689-694

[2] STRUCTURAL MATCHING IN COMPUTER VISION USING PROBABILISTIC RELAXATION [J].

CHRISTMAS, WJ ;

KITTLER, J ;

PETROU, M .

IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE, 1995, 17 (08) :749-764

[3]

Herault L., 1990, Proceeding ofBritish Machine Vision Conference, P319

[4] STEREO CORRESPONDENCE THROUGH FEATURE GROUPING AND MAXIMAL CLIQUES [J].

HORAUD, R ;

SKORDAS, T .

IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE, 1989, 11 (11) :1168-1180

[5]

LEE JP, 1990, EYE, V4, P1

[6]

LU SW, 1991, PATTERN RECOGN, V24, P617, DOI 10.1016/0031-3203(91)90029-5

[7] A new algorithm for error-tolerant subgraph isomorphism detection [J].

Messmer, BT ;

Bunke, H .

IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE, 1998, 20 (05) :493-504

[8] RULEGRAPHS FOR GRAPH MATCHING IN PATTERN-RECOGNITION [J].

PEARCE, A ;

CAELLI, T ;

BISCHOF, WF .

PATTERN RECOGNITION, 1994, 27 (09) :1231-1247

[9] Classes of cost functions for string edit distance [J].

Rice, SV ;

Bunke, H ;

Nartker, TA .

ALGORITHMICA, 1997, 18 (02) :271-280

[10] A SHAPE-ANALYSIS MODEL WITH APPLICATIONS TO A CHARACTER-RECOGNITION SYSTEM [J].

ROCHA, J ;

PAVLIDIS, T .

IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE, 1994, 16 (04) :393-404

← 1 2 →