The DOI matches its Crossref record; 36 of the 36 references it cites were found in a registry or an index.
Factorized graph matching
Open accessAbstract
Graph matching plays a central role in solving correspondence problems in computer vision. Graph matching problems that incorporate pair-wise constraints can be cast as a quadratic assignment problem (QAP). Unfortunately, QAP is NP-hard and many algorithms have been proposed to solve different relaxations. This paper presents factorized graph matching (FGM), a novel framework for interpreting and optimizing graph matching problems. In this work we show that the affinity matrix can be factorized as a Kronecker product of smaller matrices. There are three main benefits of using this factorization in graph matching: (1) There is no need to compute the costly (in space and time) pair-wise affinity matrix; (2) The factorization provides a taxonomy for graph matching and reveals the connection among several methods; (3) Using the factorization we derive a new approximation of the original problem that improves state-of-the-art algorithms in graph matching. Experimental results in synthetic and real databases illustrate the benefits of FGM. The code is available at http://humansensing.cs.cmu.edu/fgm.
Overview
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
(1979) · Cited by 43,841
An algorithm for quadratic programming
Frank, M., & Wolfe, P. (1956) · Naval Research Logistics Quarterly · doi:10.1002/nav.3800030109 · Cited by 3,030
The PASCAL visual object classes challenge 2006 (VOC2006) results
Everingham, M., Zisserman, A., Williams, C. K. I., & Gool, L. V. (2006) · Cited by 2,079
Burkard, R., Dell'Amico, M., & Martello, S. (2009) · Society for Industrial and Applied Mathematics eBooks · doi:10.1137/1.9780898717754 · Cited by 1,394
THIRTY YEARS OF GRAPH MATCHING IN PATTERN RECOGNITION
CONTE, D., FOGGIA, P., SANSONE, C., & VENTO, M. (2004) · International Journal of Pattern Recognition and Artificial Intelligence · doi:10.1142/s0218001404003228 · Cited by 1,370
A spectral technique for correspondence problems using pairwise constraints
Leordeanu, M., & Hebert, M. (2005) · Tenth IEEE International Conference on Computer Vision (ICCV'05) Volume 1 · doi:10.1109/iccv.2005.20 · Cited by 1,222
Yuille, A. L., & Rangarajan, A. (2003) · Neural Computation · doi:10.1162/08997660360581958 · Cited by 1,151
A graduated assignment algorithm for graph matching
Gold, S., & Rangarajan, A. (1996) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/34.491619 · Cited by 1,090
A Relationship Between Arbitrary Positive Matrices and Doubly Stochastic Matrices
Sinkhorn, R. (1964) · The Annals of Mathematical Statistics · doi:10.1214/aoms/1177703591 · Cited by 1,032
Introduction to Numerical Continuation Methods
Allgower, E. L., & Georg, K. (2003) · Society for Industrial and Applied Mathematics eBooks · doi:10.1137/1.9780898719154 · Cited by 876
Shape Matching and Object Recognition Using Low Distortion Correspondences
Berg, A. C., Berg, T. L., & Malik, J. (2005) · 2005 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR'05) · doi:10.1109/cvpr.2005.320 · Cited by 845
A survey for the quadratic assignment problem
Loiola, E. M., de Abreu, N. M. M., Boaventura-Netto, P. O., Hahn, P., & Querido, T. (2007) · European Journal of Operational Research · doi:10.1016/j.ejor.2005.09.032 · Cited by 741
An eigendecomposition approach to weighted graph matching problems
Umeyama, S. (1988) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/34.6778 · Cited by 727
Reweighted Random Walks for Graph Matching
Cho, M., Lee, J., & Lee, K. M. (2010) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-15555-0_36 · Cited by 455
Cour, T., Srinivasan, P., & Shi, J. (2007) · Advances in Neural Information Processing Systems 19 · doi:10.7551/mitpress/7503.003.0044 · Cited by 443
Feature Correspondence Via Graph Matching: Models and Global Optimization
Torresani, L., Kolmogorov, V., & Rother, C. (2008) · Lecture Notes in Computer Science · doi:10.1007/978-3-540-88688-4_44 · Cited by 388
A Path Following Algorithm for the Graph Matching Problem
Zaslavskiy, M., Bach, F., & Vert, J.-P. (2009) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2008.245 · Cited by 385
Caetano, T. S., McAuley, J. J., Cheng, L., Le, Q. V., & Smola, A. J. (2009) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2009.28 · Cited by 383
Probabilistic graph and hypergraph matching
Zass, R., & Shashua, A. (2008) · 2008 IEEE Conference on Computer Vision and Pattern Recognition · doi:10.1109/cvpr.2008.4587500 · Cited by 369
A Tensor-Based Algorithm for High-Order Graph Matching
Duchenne, O., Bach, F., Kweon, I.-S., & Ponce, J. (2011) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2011.110 · Cited by 358
An Integer Projected Fixed Point Method for Graph Matching and MAP Inference
Leordeanu, M., Hebert, M., & Sukthankar, R. (2009) · Cited by 284
A graph-matching kernel for object categorization
Duchenne, O., Joulin, A., & Ponce, J. (2011) · 2011 International Conference on Computer Vision · doi:10.1109/iccv.2011.6126445 · Cited by 243
A linear programming approach for the weighted graph matching problem
Almohamad, H. A., & Duffuaa, S. O. (1993) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/34.211474 · Cited by 241
Learning spatiotemporal graphs of human activities
Brendel, W., & Todorovic, S. (2011) · 2011 International Conference on Computer Vision · doi:10.1109/iccv.2011.6126316 · Cited by 231
Unsupervised Learning for Graph Matching
Leordeanu, M., Sukthankar, R., & Hebert, M. (2012) · International Journal of Computer Vision · doi:10.1007/s11263-011-0442-2 · Cited by 201
A modified Frank-Wolfe algorithm for solving the traffic assignment problem
Fukushima, M. (1984) · Transportation Research Part B Methodological · doi:10.1016/0191-2615(84)90029-8 · Cited by 184
Discovering Texture Regularity as a Higher-Order Correspondence Problem
Hays, J., Leordeanu, M., Efros, A. A., & Liu, Y. (2006) · Lecture Notes in Computer Science · doi:10.1007/11744047_40 · Cited by 183
Recognizing and Tracking Human Action
Sullivan, J., & Carlsson, S. (2002) · Lecture notes in computer science · doi:10.1007/3-540-47969-4_42 · Cited by 171
Probabilistic Subgraph Matching Based on Convex Relaxation
Schellewald, C., & Schnörr, C. (2005) · Lecture Notes in Computer Science · doi:10.1007/11585978_12 · Cited by 162
A “string of feature graphs” model for recognition of complex activities in natural videos
Gaur, U., Zhu, Y., Bi, S., & Roy–Chowdhury, A. K. (2011) · IEEE/CVF International Conference on Computer Vision (ICCV) · doi:10.1109/iccv.2011.6126548 · Cited by 145
Chertok, M., & Keller, Y. (2010) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2010.51 · Cited by 107
A POCS-based graph matching algorithm
van Wyk, B. J., & van Wyk, M. A. (2004) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2004.95 · Cited by 73
Chertok, M., & Keller, Y. (2010) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2009.121 · Cited by 45
Linear Scale and Rotation Invariant Matching
Jiang, H., Yu, S. X., & Martin, D. R. (2010) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2010.212 · Cited by 42
A Global Optimization Algorithm for Concave Quadratic Programming Problems
Bomze, I. M., & Danninger, G. (1993) · SIAM Journal on Optimization · doi:10.1137/0803042 · Cited by 37
Schellewald, C., Roth, S., & Schnörr, C. (2001) · Lecture notes in computer science · doi:10.1007/3-540-45404-7_48 · Cited by 20
Cited by
SOSNet: Second Order Similarity Regularization for Local Descriptor Learning
Tian, Y., Yu, X., Fan, B., Wu, F., Heijnen, H., & Balntas, V. (2019) · 2019 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR) · doi:10.1109/cvpr.2019.01127 · Cited by 366
Iterative Closest Graph Matching for Non-rigid 3d/2d Coronary Arteries Registration
Zhu, J., Li, H., Ai, D., Yang, Q., Fan, J., Huang, Y., Song, H., Han, Y., & Yang, J. (2021) · Computer Methods and Programs in Biomedicine · doi:10.1016/j.cmpb.2020.105901 · Cited by 22
Metadata
- Authors
- Zhou, F., & De la Torre, F.
- Venue
- 2012 IEEE Conference on Computer Vision and Pattern Recognition
- Publisher
- IEEE
- Published
- 2012-06
- Pages
- 127-134
- ISSN
- 1063-6919 (ISSN-L)
- OpenAlex
- W2076080556
- Cited by
- 272
- References
- 36
- FWCI
- 16.41
- Type
- conference paper
- Language
- en
- Open access
- green
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.