Attributed hypergraph matching on a Riemannian manifold | Machine Vision and Applications Skip to main content
Springer Nature Link
Log in

Attributed hypergraph matching on a Riemannian manifold

  • Original Paper
  • Published:
Machine Vision and Applications Aims and scope Submit manuscript

Abstract

If we consider a matching that preserves high-order relationships among points in the same set, we can int-roduce a hypergraph-matching technique to search for correspondence according to high-order feature values. While graph matching has been widely studied, there is limited research available regarding hypergraph matching. In this paper, we formulate hypergraph matching in terms of tensors. Then, we reduce the hypergraph matching to a bipartite matching problem that can be solved in polynomial time. We then extend this hypergraph matching to attributed hypergraph matching using a combination of different attributes with different orders. We perform analyses that demonstrate that this method is robust when handling noisy or missing data and can achieve inexact graph matching. To the best of our knowledge, while attributed graph-matching and hypergraph-matching have been heavily researched, methods for attributed hypergraph matching have not been proposed before.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (Japan)

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8
Fig. 9
Fig. 10
Fig. 11
Fig. 12
Fig. 13
Fig. 14
Fig. 15
Fig. 16
Fig. 17

Similar content being viewed by others

References

  1. Papadimitriou, C.H.: Computational complexity. Addison-Wesley, USA (1995)

    Google Scholar 

  2. Russell, S., Norvig, P.: Artificial intelligence—a modern approach, 2nd edn. Prentice Hall, New Jersey (2003)

    Google Scholar 

  3. Conte, D., Foggia, P., Sansone, C., Vento, M.: Thirty years of graph matching in pattern recognition. Int. J. Pattern Recognit. Artif. Intell. 18(3), 265–298 (2004)

    Article  Google Scholar 

  4. Riesen, K., Jiang, X., Bunke, H.: Exact and inexact graph matching: methodology and applications. Managing and mining graph data, pp. 217–247. Springer, New York (2010)

    Google Scholar 

  5. Cordella, L.P., Foggia, P., Sansone, C., Vento, M.: A (Sub)graph isomorphism algorithm for matching large graphs. IEEE Trans Pattern Anal. Mach. Intell. 26(20), 1367–1372 (2004)

    Article  Google Scholar 

  6. Campbell, D.M., Radford, D.: Tree isomorphism algorithms: speed vs. clarity. Math Assoc. Am. 64(4), 252–261 (1991)

    MATH  MathSciNet  Google Scholar 

  7. Filotti, I.S., Mayer, J.N.: A polynomial-time algorithm for determining the isomorphism of graphs of fixed genus. In: Proceedings of the Twelfth Annual ACM Symposium on Theory of Computer, pp. 236–243. ACM, New York (1980)

  8. McKay, B.D.: Practical graph isomorphism. Congr. Numerantium 30, 45–87 (1981)

    MathSciNet  Google Scholar 

  9. Ullmann, J.R.: An algorithm for subgraph isoorphism. J. Assoc. Comput. Mach. 13(1), l31–42 (1976)

    Article  MathSciNet  Google Scholar 

  10. Feige, U.: Approximating maximum clique by removing subgraphs. SIAM J. Discret. Math. 18(2), 219–225 (2005)

    Article  MathSciNet  Google Scholar 

  11. Bunke, H.: Error-tolerant graph matching: a formal framework and algorithms. Lect. Notes Comput. Sci. 1451(1998), 1–14 (1998)

    Article  MathSciNet  Google Scholar 

  12. Abdulkader, A.M.: Parallel algorithm for labeled graph matching. PhD Thesis, Colorado School of Mines (1998)

  13. Shapiro L.G., Haralick R.M.: Structural descriptions and inexact matching. IEEE Trans. Pattern Anal. Mach. Intell. 3(5), 504–519 (1981)

    Google Scholar 

  14. Jain, B.J., Wysotzki, F.: Solving inexact graph isomorphism problems using neural networks. Neurocomputing 63, 45–67 (2005)

    Article  Google Scholar 

  15. Wilson, R.C., Hancock, E.R.: Structural matching by discrete relaxation. IEEE Trans. Pattern Anal. Mach. Intell. 19(6), 634–648 (1997)

    Article  Google Scholar 

  16. Cross, A.D.J., Wilson, R.C., Hancock, E.R.: Inexact graph matching using genetic search. Pattern Recognit. 30(6), 953–970 (1997)

    Google Scholar 

  17. Freeman, J.A., Skapura, D.M.: Chapter 4: The BAM and the Hopfield memory. Neural networks algorithms, applications, and programming techniques, pp. 127–168. Addison Wesley, USA (1991)

    Google Scholar 

  18. Lebrun, J., Gosselin, P.H., Philipp-Foliguet, S.: Inexact graph matching based on kernels for object retrieval in image databases. Image Vis. Comput. 29(1), 716–729 (2011)

    Article  Google Scholar 

  19. Chertok, M., Keller, Y.: Efficient high order matching. IEEE Trans. Pattern Anal. Mach. Intell. 32(12), 2205–2215 (2010)

    Article  Google Scholar 

  20. Bunke, H., Dickinson, P., Karetzl, M., Neuhaus, M., Stettler, M.: Matching of hypergraphs—algorithms, applications, and experiments. Appl. Pattern Recognit. 91, 131–154 (2008)

    Google Scholar 

  21. Zass, R., Shashua, A.: Probabilistic graph and hypergraph matching. IEEE Conference on Computer Vision and Pattern Recognition, pp. 1–8. Alaska (2008)

  22. Duchenne, O., Bach, F., Kweon, I.S., Ponce, J.: A tensor-based algorithm for high-order graph matching. IEEE Trans. Pattern Anal. Mach. Intell. 33(12), 2383–2395 (2011)

    Article  Google Scholar 

  23. Tsai, W.H., Fu, K.S.: Error-correcting isomorphism for attributed relational graphs for pattern analysis. IEEE Trans. Syst. Man Cybern. SMC–9, 757–768 (1979)

    Article  Google Scholar 

  24. van Wyk, M.A., Durrani, T.S., van Wyj, B.J.: A RKHS interpolator-base graph matching algorithm. IEEE Trans. Pattern Anal. Mach. Intell. 24(7), 988–995 (2002)

    Article  Google Scholar 

  25. van Wyk M.A., Clark J.: An algorithm for approximate least-squares attributed graph matching. In: Problems in applied mathematics and computational intelligence, pp. 67–72 (2001)

  26. Ho, K., Hull, J.J., Srihari, S.N.: Decision combination in multiple classifier systems. IEEE Trans. Pattern Anal. Mach. Intell. 16(1), 66–75 (1994)

    Article  Google Scholar 

  27. Burkard, R.E., Dell’Amico, M., Martello, S.: Assignment problems. Society for Industrial and Applied Mathematics, USA (2009)

  28. Leordeanu, M., Hebert, H.: A spectral technique for correspondence problems using pairwise constraints. IEEE Int. Conf. Comput. Vis. 2, 1482–1489 (2005)

    Google Scholar 

  29. Leordeanu, M., Zanfir, A., Sminchisescu, C.: Semi-supervised learning and optimization for hypergraph matching. In: IEEE International Conference on Computer Vision, pp. 2274–2281. Barcelona (2011)

  30. Cho, M., Lee, J., Lee, K.M.: Reweighted random walks for graph matching. In: European Conference on Computer Vision, pp. 1633–1640. Crete, Greece (2010)

  31. Lee, J., Cho, M., Lee, K.M.: Hyper-graph matching via reweighted random walks. In: IEEE Conference on Pattern Recognition, pp. 1633–1640. Providence, RI (2011)

  32. Gold, S., Rangarajan, A.: A graduated assignment algorithm for graph matching. IEEE Trans. Pattern Anal. Mach. Intell. 18(4), 377–388 (1996)

    Article  Google Scholar 

  33. Luo, B., Hancock, E.: Structural graph matching using the EM algorithm and singular value decomposition. In: The Asian Conference on Computer Vision, pp. 1–6. Melbourne (2002)

  34. Umeyama, S.: An Eigendecomposition approach to weighted graph matching problems. IEEE Trans. Pattern Anal. Mach. Intell. 10(5), 695–703 (1988)

    Article  MATH  Google Scholar 

  35. Kolda, T.G., Bader, B.W.: Tensor decompositions and applications. SIAM Rev. 51(3), 455–500 (2009)

    Article  MATH  MathSciNet  Google Scholar 

  36. Lu, J., Caelli, T., Yang, J.: A graph decomposition approach to least squares attributed graph matching. International Conference on Pattern Recognition, vol. 2, pp. 471–474. Cambridge (2004)

  37. Kuhn, H.W.: The Hungarian method for the assignment problem. Naval Res. Logist. Q. 2, 83–97 (1955)

    Article  Google Scholar 

  38. Zheng, K.J., Peng, Jg, Ying, S.H.: A new approach to weighted graph matching. IEICE Trans. Inf. Syst. E92–D(8), 1580–1583 (2009)

    Article  Google Scholar 

  39. Deng, L.Y., Lin, D.K.J., Wang, J.: A measurement of multi-factor orthogonality. Stat. Probab. Lett. 28, 203–209 (1996)

    Article  MATH  MathSciNet  Google Scholar 

  40. Wang, J.M., Fuh, C.S., Chen, S.W.: Video stabilization for a hand-held camera based on 3D motion model. In: IEEE International Conference on Image Processing, pp. 3477–3480. Cairo (2009)

Download references

Author information

Authors and Affiliations

  1. Department of Computer Science and Information Engineering, National Taiwan University, No. 1, Sec. 4, Roosevelt Rd., Taipei, 10617, Taiwan, ROC

    J. M. Wang & C. S. Fuh

  2. Department of Computer Science and Information Engineering, National Taiwan Normal University, No. 88, Sec. 4, Tingzhou Rd., Wenshan District, Taipei, 116, Taiwan, ROC

    S. W. Chen

Authors
  1. J. M. Wang
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. S. W. Chen
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. C. S. Fuh
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to S. W. Chen.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Wang, J.M., Chen, S.W. & Fuh, C.S. Attributed hypergraph matching on a Riemannian manifold. Machine Vision and Applications 25, 823–844 (2014). https://doi.org/10.1007/s00138-014-0598-1

Download citation

  • Received:

  • Revised:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00138-014-0598-1

Keywords

Search

Navigation