A spectral technique for correspondence problems using pairwise constraints

By Marius Leordeanu, Martial Hebert. Tenth IEEE International Conference on Computer Vision (ICCV'05) Volume 1, 2005

1,338 citations recorded by the source corpus.

We present an efficient spectral method for finding consistent correspondences between two sets of features. We build the adjacency matrix M of a graph whose nodes represent the potential correspondences and the weights on the links represent pairwise agreements between potential correspondences. Correct assignments are likely to establish links among each other and thus form a strongly connected cluster. Incorrect correspondences establish links with the other correspondences only accidentally, so they are unlikely to belong to strongly connected clusters. We recover the correct assignments based on how strongly they belong to the main cluster of M, by using the principal eigenvector of M and imposing the mapping constraints required by the overall correspondence mapping (one-to-one or one-to-many). The experimental evaluation shows that our method is robust to outliers, accurate in terms of matching rate, while being much faster than existing methods

Subfields: Computer Vision and Pattern Recognition

View Paper: https://www.semanticscholar.org/paper/56ca893694e7a36f913d508105ce6391f7f6f7f0

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computer Vision and Pattern Recognition

Citations in the corpus

Discovering discriminative action parts from mid-level video representations (2012, methodology): “Approximate solutions for this problem in vision include LP/SDP relaxations [24], spectral methods [18, 8], and MRF inference [29].”
Attributed Graph Mining and Matching: An Attempt to Define and Extract Soft Attributed Patterns (2014, methodology): “Thus, based on [17], the two competing approaches of LS and LT are obtained by applying spectral techniques [15] and TRW-S [14], respectively, to solve the matching optimization argmaxx C(x).”
Registration of 3D Point Clouds and Meshes: A Survey from Rigid to Nonrigid (2013, methodology): “To explicitly model such a relationship, spectral techniques [2], [97] and a game theoretical framework [96] consider the objective function: xM̂x where M̂ summarizes the QAP cost above.”
Deformable Spatial Pyramid Matching for Fast Dense Correspondences (2013, methodology): “Thus, researchers have explored various computationally efficient solutions, including hierarchical optimization [15], randomized search [2], 1D approximations of 2D layout [11], spectral relaxations [13], and approximate graph matching [5].”
Image Matching from Handcrafted to Deep Features: A Survey (2020, methodology): “Leordeanu and Hebert (2005) proposed to replace the one-to-one mapping constraint and the binary constraint by constraining ‖vec(X)‖22 = 1.”
Gromov–Wasserstein Distances and the Metric Approach to Object Matching (2011, neutral): “Other examples are [3, 5, 31, 62, 69, 70, 80, 94, 96].”
Learning Spectral Descriptors for Deformable Shape Correspondence (2014, methodology): “We put the descriptor to the actual test of generating correspondences using a method similar to [30].”
A scalable active framework for region annotation in 3D shape collections (2016, methodology): “We solve Equation 3 using a spectral optimization method [Leordeanu and Hebert 2005], obtaining per-point labels f for all shapes.”
The Visual Object Tracking VOT2014 Challenge Results (2014, neutral): “The optimal matching from candidate superpixels is found from the affinity matrix applying the spectral technique [38].”
Factorized Graph Matching (2016, methodology): “To handle more complex problems in computer vision, Leordeanu and Hebert [27] approximated Eq.”
Clique-graph matching by preserving global & local structure (2015, background): “…precise salient point localization, deformation of the correlation between pairwise points due to the viewpoint change, affine transformation, etc. Previous literatures on this task mainly focus on nodeto-node mapping by leveraging the first & second order attributes [8, 16, 12, 11].”
Machine Learning and Radiology (2012, methodology): “Leordeanu and Hebert employed spectral technique to decompose the affinity matrix Q of all possible assignments (Leordeanu and Hebert, 2005).”
Deformable Medical Image Registration: A Survey (2013, methodology): “Leordeanu and Hebert [287] proposed a spectral technique to solve the matching problem.”
Probabilistic graph and hypergraph matching (2008, methodology): “The matching is then obtained from the leading eigenvector of the SDP solution; [11] approximate the non-convex quadratic cost as an eigenvector problem, by further relaxations of the constraints; [8] extend this spectral method by incorporating more of the original constraints while staying in the…”