IEEE Transactions on Pattern Analysis and Machine Intelligence 27(3), 365–378 (2005)īoeres, M.C., Ribeiro, C.C., Bloch, I.: A randomized heuristic for scene recognition by graph matching. Robles-Kelly, A., Hancock, E.R.: Graph edit distance from spectral seriation. Springer, Heidelberg (2004)Īmbauen, R., Fischer, S., Bunke, H.: Graph edit distance with node splitting and merging and its application to diatom identification. (eds.) Structural, Syntactic, and Statistical Pattern Recognition. In: Fred, A., Caelli, T.M., Duin, R., Campilho, A., de Ridder, D. Neuhaus, M., Bunke, H.: An error-tolerant approximate matching algorithm for attributed planar graphs and its application to fingerprint classification. Neuhaus, M., Bunke, H.: Edit distance based kernel functions for structural pattern classification.
IEEE Transactions on Systems, Man, and Cybernetics (Part B) 13(3), 353–363 (1983) Sanfeliu, A., Fu, K.S.: A distance measure between attributed relational graphs for pattern recognition. IEEE Transactions on Pattern Analysis and Machine Intelligence 27(7), 1100–1111 (2005)īunke, H., Allermann, G.: Inexact graph matching for structural pattern recognition. Gori, M., Maggini, M., Sarti, L.: Exact and approximate graph matching using random walks. Pattern Recognition 28(7), 997–1009 (1995)Ĭross, A., Wilson, R., Hancock, E.: Inexact graph matching using genetic search. Suganthan, P.N., Teoh, E.K., Mital, D.P.: Pattern recognition by graph matching using the potts MFT neural networks. IEEE Transactions on Pattern Analysis and Machine Intelligence 17(8), 749–764 (1995) Pattern Recognition 36(10), 2213–2223 (2003)Ĭhristmas, W.J., Kittler, J., Petrou, M.: Structural matching in computer vision using probabilistic relaxation. Luo, B., Wilson, R., Hancock, E.R.: Spectral embedding of graphs. IEEE Transactions on Pattern Analysis and Machine Intelligence 10(5), 695–703 (1988) Umeyama, S.: An eigendecomposition approach to weighted graph matching problems. Journal of Pattern Recognition and Artificial Intelligence 18(3), 265–298 (2004) This process is experimental and the keywords may be updated as the learning algorithm improves.Ĭonte, D., Foggia, P., Sansone, C., Vento, M.: Thirty years of graph matching in pattern recognition. These keywords were added by machine and not by the authors. Also we show that classification accuracy remains nearly unaffected. In experiments on semi-artificial and real data we demonstrate the speedup of our proposed method over a traditional tree search based algorithm for graph edit distance computation. The reason for its suboptimality is that implied edge operations are not considered during the process of finding the optimal node assignment. Our proposed algorithm runs in polynomial time, but provides only suboptimal edit distance results. In this paper we propose an approach for the efficient compuation of edit distance based on bipartite graph matching by means of Munkres’ algorithm, sometimes referred to as the Hungarian algorithm. One of the most flexible error-tolerant graph similarity measures is based on graph edit distance.
Hence, such computations are feasible for rather small graphs only. One of the main drawbacks of graph representations is that the computation of standard graph similarity measures is exponential in the number of involved nodes. In contrast to string representations, graphs allow us to describe relational information in the patterns under consideration.
In the field of structural pattern recognition graphs constitute a very common and powerful way of representing patterns.