A graph distance metric based on the maximal common subgraph

被引：426

作者：

Bunke, H ^{[1
]}

Shearer, K

机构：

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

[2] Curtin Univ Technol, Dept Comp Sci, Perth, WA 6001, Australia

来源：

PATTERN RECOGNITION LETTERS | 1998年 / 19卷 / 3-4期

关键词：

error-tolerant graph matching; distance measure; maximal common subgraph; graph edit distance; metric;

D O I：

10.1016/S0167-8655(97)00179-7

中图分类号：

TP18 [人工智能理论];

学科分类号：

081104 ; 0812 ; 0835 ; 1405 ;

摘要：

Error-tolerant graph matching is a powerful concept that has various applications in pattern recognition and machine vision. In the present paper, a new distance measure on graphs is proposed. It is based on the maximal common subgraph of two graphs. The new measure is superior to edit distance based measures in that no particular edit operations together with their costs need to be defined. It is formally shown that the new distance measure is a metric. Potential algorithms for the efficient computation of the new measure are discussed. (C) 1998 Elsevier Science B.V. All rights reserved.

引用

页码：255 / 259

页数：5

共 20 条

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

Bunke, H .

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

[2]

BUNKE H, 1997, J PATTERN RECOGNITIO, V11, P169

[3] ICONIC INDEXING BY 2-D STRINGS [J].

CHANG, SK ;

SHI, QY ;

YAN, CW .

IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE, 1987, 9 (03) :413-428

[4] RECOGNIZING 3-D OBJECTS BY FORWARD CHECKING CONSTRAINED TREE-SEARCH [J].

CHO, CJ ;

KIM, JH .

PATTERN RECOGNITION LETTERS, 1992, 13 (08) :587-597

[5] 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

[6]

CORDELLA L, 1997, PREP GBR 97 IAPR WOR

[7] 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

[8]

LEE JP, 1990, EYE, V4, P1

[9] SPATIAL REASONING AND SIMILARITY RETRIEVAL OF IMAGES USING 2D C-STRING KNOWLEDGE REPRESENTATION [J].

LEE, SY ;

HSU, FJ .

PATTERN RECOGNITION, 1992, 25 (03) :305-318

[10]

Levi G., 1973, CALCOLO, V9, P341, DOI DOI 10.1007/BF02575586

← 1 2 →