Inexact graph matching using a genetic algorithm for image recognition

被引：20

作者：

Auwatanamongkol, Surapong ^{[1
]}

机构：

[1] Natl Inst Dev Adm, Sch Appl Stat, Dept Comp Sci, Bangkok 10240, Thailand

来源：

PATTERN RECOGNITION LETTERS | 2007年 / 28卷 / 12期

关键词：

genetic algorithm; inexact graph matching; image recognition and classification;

D O I：

10.1016/j.patrec.2007.02.013

中图分类号：

TP18 [人工智能理论];

学科分类号：

081104 ; 0812 ; 0835 ; 1405 ;

摘要：

Exact graph matching using a genetic algorithm for image recognition has been introduced in previously published work. The algorithm was based on angle matching between two given graphs. It has proven to be quite effective in exact graph matching. However, the algorithm needs some modifications in order to handle cases where the number of nodes, shapes and rotations of the two graphs are different. This paper presents modifications such as the introduction of node exemption, inexact matching between straight lines and curves in the graphs and consideration of rotational degrees of the graphs. Each angle in a graph is also given a weight to indicate the significant degree of identifying the graph. A multi-objective function is used to reflect the similarity between two graphs. The experiments designed to evaluate the algorithm have shown very promising results. It is highly accurate in matching graphs with dissimilarities in shape, number of nodes and degrees of rotation. (c) 2007 Elsevier B.V. All rights reserved.

引用

页码：1428 / 1437

页数：10

共 21 条

[1]

Auwatanamongkol S, 2000, IEEE C EVOL COMPUTAT, P822, DOI 10.1109/CEC.2000.870384

[2]

Back T., 1994, Proceedings of the First IEEE Conference on Evolutionary Computation. IEEE World Congress on Computational Intelligence (Cat. No.94TH0650-2), P57, DOI 10.1109/ICEC.1994.350042

[3]

BENGOETXEA E, 2001, P MED IM UND AN, P89

[4]

CESAR R, 2002, INT C PATTERN RECOGN

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

COUGHLAN J, 2004, P 2004 IEEE C COMP V

[7] Graph matching with a dual-step EM algorithm [J].

Cross, ADJ ;

Hancock, ER .

IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE, 1998, 20 (11) :1236-1253

[8] Inexact graph matching using genetic search [J].

Cross, ADJ ;

Wilson, RC ;

Hancock, ER .

PATTERN RECOGNITION, 1997, 30 (06) :953-970

[9] Convergence of a hill-climbing genetic algorithm for graph matching [J].

Cross, ADJ ;

Myers, R ;

Hancock, ER .

PATTERN RECOGNITION, 2000, 33 (11) :1863-1880

[10] Symbolic graph matching with the EM algorithm [J].

Finch, AM ;

Wilson, RC ;

Hancock, ER .

PATTERN RECOGNITION, 1998, 31 (11) :1777-1790

← 1 2 3 →