nach oben

International Journal of Computer Vision

Erschienen in:

01.09.2014

Graph Matching by Simplified Convex-Concave Relaxation Procedure

verfasst von: Zhi-Yong Liu, Hong Qiao, Xu Yang, Steven C. H. Hoi

Erschienen in: International Journal of Computer Vision | Ausgabe 3/2014

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

The convex and concave relaxation procedure (CCRP) was recently proposed and exhibited state-of-the-art performance on the graph matching problem. However, CCRP involves explicitly both convex and concave relaxations which typically are difficult to find, and thus greatly limit its practical applications. In this paper we propose a simplified CCRP scheme, which can be proved to realize exactly CCRP, but with a much simpler formulation without needing the concave relaxation in an explicit way, thus significantly simplifying the process of developing CCRP algorithms. The simplified CCRP can be generally applied to any optimizations over the partial permutation matrix, as long as the convex relaxation can be found. Based on two convex relaxations, we obtain two graph matching algorithms defined on adjacency matrix and affinity matrix, respectively. Extensive experimental results witness the simplicity as well as state-of-the-art performance of the two simplified CCRP graph matching algorithms.

Nächster Artikel SymStereo: Stereo Matching using Induced Symmetry

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Nur mit Berechtigung zugänglich

The convex relaxation (7) is derived by adding some dummy nodes into the smaller graph to obtain an equal-sized matching problem, such that \(\mathbf {X}\) is constrained as a permutation instead of a partial permutation matrix. Such an expansion is appropriate in case \(\mathbf {K}\) is constructed following (4), because it is straightforward to check that adding dummy nodes will not change the problem. However, if we define the partial matching based on objective function (1) by similarly adding some dummy nodes such that the convex relaxation (5) still holds, it can be shown that it in general changes the objective function.

For convenience sake and without loss of generality, we consider minimization problem here, since the maximization problem such as (2) can be transferred to be a minimization one by setting \(\mathbf {K}\leftarrow -\mathbf {K}\).

Actually, if \(\zeta \) is further increased from \(\eta \) to be \(1\), the resulted \(\mathbf {P}\in \Pi \) will retain since it remains to be a local minimum of the concave function \(F_{\zeta }(\mathbf {P})\).

Codes of SM and RRWM are available at http://cv.snu.ac.kr/research/~RRWM/.

http://www.f-zhou.com/gm.html.

http://109.101.234.42/code.php.

All of the codes of the ten algorithms are available at http://www.escience.cn/people/zyliu/SCCRP.html.

http://vasc.ri.cmu.edu/idb/html/motion/.

http://109.101.234.42/code.php.

Blake, A., & Zisserman, A. (1987). Visual Reconstruction. Cambridge, MA, USA: MIT Press.

Boyd, S., & Vandenberghe, L. (2004). Convex Optimization. New York: Cambridge University Press.CrossRefMATH

Cho, M., Alahari, K., Ponce, J., et al. (2013). Learning graphs to match. In: ICCV 2013-IEEE International Conference on Computer Vision.

Cho, M., Lee, J., & Lee, K. M. (2010). Reweighted random walks for graph matching. In: Computer Vision-ECCV 2010. Berlin: Springer.

Cho, M., Lee, K.M. (2012). Progressive graph matching: Making a move of graphs via probabilistic voting. In: Computer Vision and Pattern Recognition (CVPR), 2012 IEEE Conference on, pp. 398–405. IEEE.

Conte, D., Foggia, P., Sansone, C., & Vento, M. (2004). Thirty years of graph matching in pattern recognition. International Journal of Pattern Recognition and Artificial Intelligence, 18(3), 265–298.CrossRef

Cour, T., Srinivasan, P., & Shi, J. (2007). Balanced graph matching. Advances in Neural Information Processing Systems, 19, 313.

Demirci, M. F., Shokoufandeh, A., Keselman, Y., Bretzner, L., & Dickinson, S. (2006). Object recognition as many-to-many feature matching. International Journal of Computer Vision, 69(2), 203–222.CrossRef

Duchenne, O., Joulin, A., Ponce, J. (2011). A graph-matching kernel for object categorization. IEEE International Conference on Computer Vision pp. 1792–1799.

Egozi, A., Keller, Y., & Guterman, H. (2013). A probabilistic approach to spectral graph matching. IEEE Transactions on Pattern Analysis and Machine Intelligence, 35(1), 18–27.CrossRef

Fischler, M. A., & Elschlager, R. A. (1973). The representation and matching of pictorial structures. IEEE Transactions on Computers, C–22(1), 67–92.CrossRef

Frank, M., & Wolfe, P. (1956). An algorithm for quadratic programming. Naval Research Logistics Quarterly, 3(1–2), 95–110.CrossRefMathSciNet

Geiger, D., & Yuille, A. (1991). A common framework for image segmentation. International Journal of Computer Vision, 6(3), 227–243.CrossRef

Gold, S., & Rangarajan, A. (1996). A graduated assignment algorithm for graph matching. IEEE Transactions on Pattern Analysis and Machine Intelligence, 18(4), 377–388.CrossRef

Kuhn, H. W. (1955). The hungarian method for the assignment problem. Naval Research Logistics Quarterly, 2(1–2), 83–97.CrossRefMathSciNet

Leordeanu, M., & Hebert, M. (2005). A spectral technique for correspondence problems using pairwise constraints. Tenth IEEE International Conference on Computer Vision, 2, 1482–1489.CrossRef

Leordeanu, M., Herbert, M., Sukthankar, R. (2009). An integer projected fixed point method for graph matching and map inference. Advances in Neural Information Processing Systems p. 1114C1122.

Leordeanu, M., Sukthankar, R., & Hebert, M. (2012). Unsupervised learning for graph matching. International journal of computer vision, 96(1), 28–45.CrossRefMATHMathSciNet

Liu, C. L., Yin, F., Wang, D. H., & Wang, Q. F. (2011). Casia online and offline chinese handwriting databases. In: Preceedings of the International Conference on Document Analysis and Recognition, 2011, 37–41.

Liu, Z. Y., & Qiao, H. (2012). A convex-concave relaxation procedure based subgraph matching algorithm. Journal of Machine Learning Research: W&CP, 25, 237–252.

Liu, Z. Y., Qiao, H., & Xu, L. (2012). An extended path following algorithm for graph matching problem. IEEE Transactions on Pattern Analysis and Machine Intelligence, 34(7), 1451–1456.CrossRef

Maciel, J., & Costeira, J. P. (2003). A global solution to sparse correspondence problems. IEEE Transactions on Pattern Analysis and Machine Intelligence, 25(2), 187–199.

Philbin, G., Sivic, J., & Zisserman, A. (2011). Geometric latent dirichlet allocation on a matching graph for large-scale image datasets. International Journal of Computer Vision, 95(2), 138–153.CrossRefMATHMathSciNet

Ravikumar, P., Lakerty, J. (2006). Quadratic programming relaxations for metric labeling and markov random field map estimation. International Conference on Machine Learning.

Rose, K. (1998). Deterministic annealing for clustering, compression, classification, regression, and related optimization problems. Proceedings of the IEEE, 86(11), 2210–2239.CrossRef

Suh, Y., Cho, M., & Lee, K. M. (2012). Graph matching via sequential monte carlo. In: Computer Vision-ECCV 2012. Berlin: Springer.

Tian, Y., Yan, J., Zhang, H., Zhang, Y., Yang, X., & Zha, H. (2012). On the convergence of graph matching: graduated assignment revisited. In: Computer Vision-ECCV 2012. Berlin: Springer.

Torresani, L., Kolmogorov, V., Rother, C. (2008). Feature correspondence via graph matching: Models and global optimization. In D. Forsyth, P. Torr, A. Ziseerman (eds.), ECCV 2008, Part II, LNCS 5303, (pp. 596–609).

Umeyama, S. (1988). An eigendecomposition approach to weighted graph matching problems. IEEE Transactions on Pattern Analysis and Machine Intelligence, 10(5), 695–703.CrossRefMATH

Zaslavskiy, M., Bach, F., & Vert, J. P. (2009). A path following algorithm for the graph matching problem. IEEE Transactions on Pattern Analysis and Machine Intelligence, 31(12), 2227–2242.CrossRef

Zhou, F., De la Torre, F. (2012). Factorized graph matching. In: IEEE International Conference on Computer Vision and Pattern Recognition, pp. 127–134.

Zhou, F., De la Torre, F. (2013). Deformable graph matching. In: Computer Vision and Pattern Recognition (CVPR), 2013 IEEE Conference on, pp. 2922–2929. IEEE.

Titel: Graph Matching by Simplified Convex-Concave Relaxation Procedure
verfasst von: Zhi-Yong Liu
Hong Qiao
Xu Yang
Steven C. H. Hoi
Publikationsdatum: 01.09.2014
Verlag: Springer US
Erschienen in: International Journal of Computer Vision / Ausgabe 3/2014
Print ISSN: 0920-5691
Elektronische ISSN: 1573-1405
DOI: https://doi.org/10.1007/s11263-014-0707-7

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Weitere Artikel der Ausgabe 3/2014

Infinitesimal Plane-Based Pose Estimation

Reduced Analytic Dependency Modeling: Robust Fusion for Visual Recognition

SymStereo: Stereo Matching using Induced Symmetry

Sparse Representation Based Fisher Discrimination Dictionary Learning for Image Classification

Premium Partner