×

Inexact graph matching using a hierarchy of matching processes. (English) Zbl 1428.68223

Summary: Inexact graph matching algorithms have proved to be useful in many applications, such as character recognition, shape analysis, and image analysis. Inexact graph matching is, however, inherently an NP-hard problem with exponential computational complexity. Much of the previous research has focused on solving this problem using heuristics or estimations. Unfortunately, many of these techniques do not guarantee that an optimal solution will be found. It is the aim of the proposed algorithm to reduce the complexity of the inexact graph matching process, while still producing an optimal solution for a known application. This is achieved by greatly simplifying each individual matching process, and compensating for lost robustness by producing a hierarchy of matching processes. The creation of each matching process in the hierarchy is driven by an application-specific criterion that operates at the subgraph scale. To our knowledge, this problem has never before been approached in this manner. Results show that the proposed algorithm is faster than two existing methods based on graph edit operations. The proposed algorithm produces accurate results in terms of matching graphs, and shows promise for the application of shape matching. The proposed algorithm can easily be extended to produce a sub-optimal solution if required.

MSC:

68R10 Graph theory (including graph drawing) in computer science
68T20 Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Conte, D.; Foggia, P.; Sansone, C.; Vento, M.; Kandel, A. (ed.); Bunke, H. (ed.); Last, M. (ed.), How and why pattern recognition and computer vision applications use graphs., 85-135 (2007), Berlin Heidelberg · Zbl 1138.68506
[2] Hu, S.-M.; Zhang, F.-L.; Wang, M.; Martin, R. R.; Wang, J. PatchNet: A patch-based image representation for interactive library-driven image editing. ACM Transactions on Graphics Vol. 32, No. 6, Article No. 196, 2013.
[3] Vento, M.; Foggia, P.; Bai, X. (ed.); Cheng, J. (ed.); Hancock, E. (ed.), Graph matching techniques for computer vision., 1-41 (2012)
[4] Wang, M.; Lai, Y.-K.; Liang, Y.; Martin, R. R.; Hu, S.-M. BiggerPicture: Data-driven image extrapolation using graph matching. ACM Transactions on Graphics Vol. 33, No. 6, Article No. 173, 2014.
[5] Bai, X.; Latecki, L. J. Path similarity skeleton graph matching. IEEE Transactions on Pattern Analysis and Machine Intelligence Vol. 30, No. 7, 1282-1292, 2008. · doi:10.1109/TPAMI.2007.70769
[6] Tsai, W.-H.; Fu, K.-S. Error-correcting isomorphisms of attributed relational graphs for pattern analysis. IEEE Transactions on Systems, Man and Cybernetics Vol. 9, No. 12, 757-768, 1979. · Zbl 0422.68042 · doi:10.1109/TSMC.1979.4310127
[7] Tsai W.-H.; Fu, K.-S. Subgraph error-correcting isomorphisms for syntactic pattern recognition. IEEE Transactions on Systems, Man and Cybernetics Vol. 13, No. 1, 48-62, 1983. · Zbl 0498.68055 · doi:10.1109/TSMC.1983.6313029
[8] Berretti, S.; Bimbo, A. D.; Vicario, E. Efficient matching and indexing of graph models in contentbased retrieval. IEEE Transactions on Pattern Analysis and Machine Intelligence Vol. 23, No. 10, 1089-1105, 2001. · doi:10.1109/34.954600
[9] Nilsson, N. J. Problem-solving Methods in Artificial Intelligence. McGraw-Hill Pub. Co., 1971.
[10] Christmas, W. J.; Kittler, J.; Petrou, M. Structural matching in computer vision using probabilistic relaxation. IEEE Transactions on Pattern Analysis and Machine Intelligence Vol. 17, No. 8, 749-764, 1995. · doi:10.1109/34.400565
[11] Gold, S.; Rangarajan, A. A graduated assignment algorithm for graph matching. IEEE Transactions on Pattern Analysis and Machine Intelligence Vol. 18, No. 4, 377-388, 1996. · doi:10.1109/34.491619
[12] Conte, D.; Foggia, P.; Sansone, C.; Vento, M. Thirty years of graph matching in pattern recognition. International Journal of Pattern Recognition and Artificial Intelligence Vol. 18, No. 3, 265-298, 2004. · doi:10.1142/S0218001404003228
[13] Foggia, P.; Percannella, G.; Vento, M. Graph matching and learning in pattern recognition in the last 10 years. International Journal of Pattern Recognition and Artificial Intelligence Vol. 28, No. 1, 1450001, 2014. · doi:10.1142/S0218001414500013
[14] Livi, L.; Rizzi, A. The graph matching problem. Pattern Analysis and Applications Vol. 16, No. 3, 253-283, 2013. · Zbl 1284.68470 · doi:10.1007/s10044-012-0284-8
[15] Gregory, L.; Kittler, J.; Caelli, T. (ed.); Amin, A. (ed.); Duin, R. P. W. (ed.); de Ridder, D. (ed.); Kamel, M. (ed.), Using graph search techniques for contextual colour retrieval., 186-194 (2002), Berlin Heidelberg · Zbl 1073.68752
[16] Eppstein, D. Quasiconvex analysis of multivariate recurrence equations for backtracking algorithms. ACM Transactions on Algorithms Vol. 2, No. 4, 492-509, 2006. · Zbl 1321.68558 · doi:10.1145/1198513.1198515
[17] Fomin, F. V.; Grandoni, F.; Kratsch, D.; Caires, L. (ed.); Italiano, G. F. (ed.); Monteiro, L. (ed.); Palamidessi, C. (ed.); Yung, M. (ed.), Measure and conquer: Domination—A case study., 191-203 (2005), Berlin Heidelberg · Zbl 1082.68866
[18] Fomin, F. V.; Grandoni, F.; Kratsch, D.; Lokshtanov, D.; Saurabh, S. Computing optimal steiner trees in polynomial space. Algorithmica Vol. 65, No. 3, 584-604, 2013. · Zbl 1269.05049 · doi:10.1007/s00453-012-9612-z
[19] Van Rooij, J. M. M.; Bodlaender, H. L. Exact algorithms for edge domination. Algorithmica Vol. 64, No. 4, 535-563, 2012. · Zbl 1264.68211 · doi:10.1007/s00453-011-9546-x
[20] Woeginger, G. J.; Jünger, M. (ed.); Reinelt, G. (ed.); Rinaldi, G. (ed.), Exact algorithms for NP-hard problems: A survey., 185-208 (2003), Berlin Heidelberg
[21] Eshera, M. A.; Fu, K.-S. A graph distance measure for image analysis. IEEE Transactions on Systems, Man and Cybernetics Vol. 14, No. 3, 398-408, 1984. · Zbl 0555.68058 · doi:10.1109/TSMC.1984.6313232
[22] Morrison, P., Shape matching based on skeletonisation and inexact graph matching. (2011)
[23] Russell, S.; Norvig, P. Artificial Intelligence: A Modern Approach. Prentice-Hall, 1995. · Zbl 0835.68093
[24] Berretti, S.; Bimbo, A. D.; Pala, P.; Enser, P. (ed.); Kompatsiaris, Y. (ed.); O’Connor, N. E. (ed.); Smeaton, A. F. (ed.); Smeulders, A. W. M. (ed.), A graph edit distance based on node merging., 464-472 (2004), Berlin Heidelberg
[25] Sebastian, T. B.; Klein, P. N.; Kimia, B. B., Recognition of shapes by editing shock graphs., 755-762 (2001)
[26] Morrison, P.; Zou, J. J. Triangle refinement in a constrained Delaunay triangulation skeleton. Pattern Recognition Vol. 40, No. 10, 2754-2765, 2007. · Zbl 1132.68794 · doi:10.1016/j.patcog.2006.12.021
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.