Journal Home > Volume 1 , Issue 4
Computational Visual Media 2015, 1(4): 291-307 https://doi.org/10.1007/s41095-015-0030-4
Research Article | Open Access | Issue | Published: 07 January 2016

Inexact graph matching using a hierarchy of matching processes

Show Author's Information Paul Morrison1,  Ju Jia Zou1( )
School of Computing, Engineering and Mathematics, Western Sydney University, Locked Bag 1797, Penrith, NSW 2751, Australia.
Keywords:
shape matching, Keywords graph matching, inexact graph matching, graph edit distance, graph edit operations
Cite this article:
Morrison P, Zou JJ. Inexact graph matching using a hierarchy of matching processes. Computational Visual Media, 2015, 1(4): 291-307. https://doi.org/10.1007/s41095-015-0030-4
Download citation
EndNote(RIS)
BibTeX

634

Views

33

Downloads

Citations

8

Crossref

N/A

WoS

8

Scopus

0

CSCD

Abstract Full text About this article

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.


menu
Abstract
Full text
Outline
About this article

Inexact graph matching using a hierarchy of matching processes

Show Author's information Paul Morrison1, Ju Jia Zou1( )
School of Computing, Engineering and Mathematics, Western Sydney University, Locked Bag 1797, Penrith, NSW 2751, Australia.

Abstract

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.

Keywords: shape matching, Keywords graph matching, inexact graph matching, graph edit distance, graph edit operations

References(26)

[1]
Conte, D.; Foggia, P.; Sansone, C.; Vento, M. How and why pattern recognition and computer vision applications use graphs. In: Studies in Computational Intelligence, Vol. 52. Kandel, A.; Bunke, H.; Last, M. Eds. Springer-Verlag Berlin Heidelberg, 85-135, 2007.
DOI
[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.
DOI Google Scholar
[3]
Vento, M.; Foggia, P. Graph matching techniques for computer vision. In: Graph-Based Methods in Computer Vision: Developments and Applications. Bai, X.; Cheng, J.; Hancock, E. Eds. IGI Global, 1-41, 2012.
DOI
[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.
DOI Google Scholar
[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 Google Scholar
[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.
DOI Google Scholar
[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.
DOI Google Scholar
[8]
Berretti, S.; Bimbo, A. D.; Vicario, E. Efficient matching and indexing of graph models in content-based retrieval. IEEE Transactions on Pattern Analysis and Machine Intelligence Vol. 23, No. 10, 1089-1105, 2001.
DOI Google Scholar
[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 Google Scholar
[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 Google Scholar
[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 Google Scholar
[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 Google Scholar
[14]
Livi, L.; Rizzi, A. The graph matching problem. Pattern Analysis and Applications Vol. 16, No. 3, 253-283, 2013.
DOI Google Scholar
[15]
Gregory, L.; Kittler, J. Using graph search techniques for contextual colour retrieval. In: Lecture Notes in Computer Science, Vol. 2396. Caelli, T.; Amin, A.; Duin, R. P. W.; de Ridder, D.; Kamel, M. Eds. Springer-Verlag Berlin Heidelberg, 186-194, 2002.
DOI
[16]
Eppstein, D. Quasiconvex analysis of multivariate recurrence equations for backtracking algorithms. ACM Transactions on Algorithms Vol. 2, No. 4, 492-509, 2006.
DOI Google Scholar
[17]
Fomin, F. V.; Grandoni, F.; Kratsch, D. Measure and conquer: Domination—A case study. In: Lecture Notes in Computer Science, Vol. 3580. Caires, L.; Italiano, G. F.; Monteiro, L.; Palamidessi, C.; Yung, M. Eds. Springer-Verlag Berlin Heidelberg, 191-203, 2005.
DOI
[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.
DOI Google Scholar
[19]
Van Rooij, J. M. M.; Bodlaender, H. L. Exact algorithms for edge domination. Algorithmica Vol. 64, No. 4, 535-563, 2012.
DOI Google Scholar
[20]
Woeginger, G. J. Exact algorithms for NP-hard problems: A survey. In: Lecture Notes in Computer Science, Vol. 2570. Jünger, M.; Reinelt, G.; Rinaldi, G. Eds. Springer-Verlag Berlin Heidelberg, 185-208, 2003.
DOI
[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.
DOI Google Scholar
[22]
Morrison, P. Shape matching based on skeletonisation and inexact graph matching. Ph.D. thesis. Western Sydney University, 2011.
[23]
Russell, S.; Norvig, P. Artificial Intelligence: A Modern Approach. Prentice-Hall, 1995.
[24]
Berretti, S.; Bimbo, A. D.; Pala, P. A graph edit distance based on node merging. In: Lecture Notes in Computer Science, Vol. 3115. Enser, P.; Kompatsiaris, Y.; O’Connor, N. E.; Smeaton, A. F.; Smeulders, A. W. M.Eds. Springer-Verlag Berlin Heidelberg, 464-472, 2004.
DOI
[25]
Sebastian, T. B.; Klein, P. N.; Kimia, B. B. Recognition of shapes by editing shock graphs. In: Proceedings of the 8th IEEE International Conference on Computer Vision, Vol. 1, 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.
DOI Google Scholar
Publication history
Copyright
Acknowledgements
Rights and permissions

Publication history

Revised: 26 October 2015
Accepted: 24 November 2015
Published: 07 January 2016
Issue date: December 2015

Copyright

© The Author(s) 2015

Acknowledgements

The authors wish to express their gratitude to associate professor Weidong (Tom) Cai at the University of Sydney in Australia for his advice and help in relation to the publication of this article.

Rights and permissions

This article is published with open access at Springerlink.com

This article is distributed under the terms of the Creative Commons Attribution License which permits any use, distribution, and reproduction in any medium, provided the original author(s) and the source are credited.

Other papers from this open access journal are available free of charge from http://www.springer.com/journal/41095. To submit a manuscript, please go to https://www.editorialmanager.com/cvmj.

Return