Minimum cost subgraph matching using a binary linear program

被引：6

作者：

Lerouge, Julien ^{[1
]}

Hammami, Maroua ^{[1
]}

Heroux, Pierre ^{[1
]}

Adam, Sebastien ^{[1
]}

机构：

[1] Univ Rouen, LITIS EA 4108, BP 12, F-76801 St Etienne, France

来源：

PATTERN RECOGNITION LETTERS | 2016年 / 71卷

关键词：

Subgraph matching; Edit dstance; Error-tolerant; Binary linear programing; Symbol spotting; GRAPH EDIT DISTANCE; OPTIMAL MONOMORPHISM; ISOMORPHISM; ALGORITHM; APPROXIMATION;

D O I：

10.1016/j.patrec.2015.11.026

中图分类号：

TP18 [人工智能理论];

学科分类号：

081104 ; 0812 ; 0835 ; 1405 ;

摘要：

This paper presents a binary linear program for the Minimum Cost Subgraph Matching (MCSM) problem. MCSM is an extension of the subgraph isomorphism problem where the matching tolerates substitutions of attributes and modifications of the graph structure. The objective function proposed in the formulation can take into account rich attributes (e.g. vectors mixing nominal and numerical values) on both vertices and edges. Some experimental results obtained on an application-dependent dataset concerning the spotting of symbols on technical drawings show that the approach obtains better performance than a previous approach which is only substitution-tolerant. (C)2015 Elsevier B.V. All rights reserved.

引用

页码：45 / 51

页数：7

共 22 条

[1] A LINEAR-PROGRAMMING APPROACH FOR THE WEIGHTED GRAPH MATCHING PROBLEM
ALMOHAMAD, HA
DUFFUAA, SO
[J]. IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE, 1993, 15 (05) : 522 - 525
[2] [Anonymous], 1979, Computers and Intractablity: A Guide to the Theory of NP-Completeness
[3] Baja G.S.D., 1996, IMAGE VISION COMPUT, V14, P47
[4] Cordella L. P., 1999, Proceedings 10th International Conference on Image Analysis and Processing, P1172, DOI 10.1109/ICIAP.1999.797762
[5] A (sub)graph isomorphism algorithm for matching large graphs
Cordella, LP
Foggia, P
Sansone, C
Vento, M
[J]. IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE, 2004, 26 (10) : 1367 - 1372
[6] Danna E, 2007, LECT NOTES COMPUT SC, V4513, P280
[7] Generation of synthetic documents for performance evaluation of symbol recognition & spotting systems
Delalandre, Mathieu
Valveny, Ernest
Pridmore, Tony
Karatzas, Dimosthenis
[J]. INTERNATIONAL JOURNAL ON DOCUMENT ANALYSIS AND RECOGNITION, 2010, 13 (03) : 187 - 207
[8] A symbol spotting approach in graphical documents by hashing serialized graphs
Dutta, Anjan
Llados, Josep
Pal, Umapada
[J]. PATTERN RECOGNITION, 2013, 46 (03) : 752 - 768
[9] Approximation of graph edit distance based on Hausdorff matching
Fischer, Andreas
Suen, Ching Y.
Frinken, Volkmar
Riesen, Kaspar
Bunke, Horst
[J]. PATTERN RECOGNITION, 2015, 48 (02) : 331 - 343
[10] GRAPH OPTIMAL MONOMORPHISM ALGORITHMS
GHAHRAMAN, DE
WONG, AKC
AU, T
[J]. IEEE TRANSACTIONS ON SYSTEMS MAN AND CYBERNETICS, 1980, 10 (04): : 181 - 188

← 1 2 3 →