Source-linked AI summary
Multi-Image Matching via Fast Alternating Minimization
Xiaowei Zhou, Menglong Zhu, Kostas Daniilidis
TL;DR
The paper addresses globally consistent feature matching across multiple images despite noisy and incomplete pairwise correspondences. It formulates matching as low-rank matrix recovery and solves it with fast alternating minimization. Experiments report competitive matching performance with substantially lower computation, and demonstrate matching across object instances for category-specific model reconstruction.
Problem
Multi-image matching must combine pairwise feature affinities with cycle consistency, whereas noisy, missing, and partially overlapping features make consistent correspondences difficult to identify.
Method
The method formulates joint matching as low-rank matrix recovery, uses nuclear-norm relaxation, and applies alternating minimization in a low-dimensional variable space.
Results
The proposed method achieves competitive performance while requiring much less computation than MatchLift, including when the true rank is unknown.
Takeaways & Limitations
Joint matching supports matching images of different object instances and provides a first step toward reconstructing category-specific object models from image collections.
Takeaways & Limitations
The method's computational complexity depends critically on selecting k, which must exceed the true rank; rank estimation can be inaccurate for noisy and incomplete input.
Abstract
from arXiv · showhide
In this paper we propose a global optimization-based approach to jointly matching a set of images. The estimated correspondences simultaneously maximize pairwise feature affinities and cycle consistency across multiple images. Unlike previous convex methods relying on semidefinite programming, we formulate the problem as a low-rank matrix recovery problem and show that the desired semidefiniteness of a solution can be spontaneously fulfilled. The low-rank formulation enables us to derive a fast alternating minimization algorithm in order to handle practical problems with thousands of features. Both simulation and real experiments demonstrate that the proposed algorithm can achieve a competitive performance with an order of magnitude speedup compared to the state-of-the-art algorithm. In the end, we demonstrate the applicability of the proposed method to match the images of different object instances and as a result the potential to reconstruct category-specific object models from those images.
1. Introduction
Multi-image matching extends pairwise correspondence estimation to settings where cycle consistency and multi-way information are essential. The paper proposes a low-rank formulation and fast alternating minimization algorithm that jointly optimizes affinities and consistency.
- Multi-image correspondences are needed for applications including nonrigid structure from motion, where two frames may be insufficient for reconstruction.
- Cycle consistency requires composing matches around image loops to yield identity, but noisy, missing, and partially overlapping features make consistent cycles difficult to identify.
- The proposed method delays correspondence decisions while jointly optimizing pairwise affinities and multi-image consistency from descriptor similarities or graph-matching affinities.
- The approach formulates matching as low-rank matrix recovery rather than semidefinite programming and shows that desired positive semidefiniteness can arise spontaneously.
- A fast alternating minimization algorithm solves the low-rank problem, with experiments covering simulated and real benchmarks and matching images of different object instances.
2. Related work
Prior joint-matching methods select cycle-consistent matches or impose cycle consistency explicitly, but they rely on strong assumptions or difficult nonconvex optimization. This work is grounded in low-rank recovery and related global-estimation problems.
- Early methods identify incorrect matches through bad cycles, assuming correct matches dominate the raw pairwise input.
- Explicit cycle-consistency constraints have been applied to sparse feature matching and pixel-wise flow, but the resulting problems are nonconvex and difficult to solve globally.
- The methodology draws on convex relaxation and low-rank structure for accelerating matrix recovery, and relates to global estimation from pairwise estimates such as rotation averaging and model fusion.
3. Preliminaries and notation
The paper represents pairwise feature correspondences with partial permutation matrices and uses cycle consistency to organize matches across all images. A virtual feature universe expresses globally consistent matches compactly.
- 3.1. Pairwise matching: Pairwise matching stores feature similarities in Sij and represents correspondences with partial permutation matrices Xij subject to doubly stochastic constraints.
- 3.1. Pairwise matching: Pairwise correspondences can maximize affinity through a linear assignment problem, while graph matching incorporates feature similarity and spatial rigidity through quadratic assignment formulations.
- 3.2. Cycle consistency: Cycle consistency requires matches composed around image triples to agree, and this condition extends to collections with more images.
- 3.2. Cycle consistency: A virtual universe contains unique features across the collection, with each image mapped to it by Ai; consistent pairwise matches satisfy Xij = AiAj^T.
- 3.2. Cycle consistency: Stacking all pairwise blocks produces a global matrix X whose desired structure is positive semidefinite and low-rank, allowing cycle consistency without checking every cycle and permitting partial matching.
4. Joint matching via rank minimization
The joint-matching objective balances affinity, sparsity, and low rank under structural constraints, using nuclear-norm relaxation for tractability. Positive semidefiniteness is omitted explicitly because sufficiently strong nuclear-norm regularization can encourage it.
- 4.1. Formulation: The formulation maximizes aggregate pairwise affinity while minimizing the rank of the global correspondence matrix to enforce cycle consistency.
- 4.1. Formulation: Relaxations replace binary X with X ∈ [0,1] and rank with the nuclear norm, while sparsity is induced by minimizing the sum of matrix entries.
- 4.1. Formulation: The cost uses W = α1 − S, with α weighting sparsity and λ controlling the nuclear-norm penalty; normalized scores use α = 0.1 in implementation.
- 4.1. Formulation: Additional constraints enforce identity self-matches, symmetry, and values in [0,1], while doubly stochastic constraints were removed in implementation to accelerate computation.
- 4.2. Positive semidefiniteness: The explicit positive-semidefinite constraint is omitted because semidefinite programming is unscalable and sufficiently large λ drives solutions toward nearly positive semidefinite matrices.
- 4.2. Positive semidefiniteness: Table 1 compares one-iteration CPU time for MatchALS, MatchLift, and partial SVD using image count n, per-image point count p, matrix dimension m, and k = 2p for MatchALS.
5. Fast alternating minimization
The paper replaces large-scale nuclear-norm optimization with a low-rank factorization and solves the resulting problem using alternating minimization and ADMM. This reduces optimization to lower-dimensional variables while preserving the intended low-rank solution structure.
- Low-rank formulation: The method factors the matrix as X = AB^T, using smaller-dimensional variables to exploit the problem’s underlying low-rank structure.The change of variables is motivated by more efficient low-rank optimization and does not introduce additional local minima when the factor dimension exceeds the original solution rank.
- Low-rank formulation: The factor dimension k controls both computational complexity and whether the factorization can represent the true solution.The paper therefore analyzes the algorithm before discussing how to select k.
- Alternating minimization: ADMM rewrites the product-constrained problem and alternately updates primal variables before updating the dual variable by gradient ascent.The constraint X ∈ C is retained because its projection can be handled separately.
- Alternating minimization: Each iteration updates the factor variables through regularized least squares and updates X by projection onto the constraint set C.The factor updates have closed-form solutions, while the projection is tractable because the constraints in C are linear.
- Alternating minimization: The algorithm is MatchALS, which takes pairwise affinity scores as input and returns globally consistent matches.Its iterations continue until convergence and include quantization of X using a threshold of 0.5.
8 end
The algorithm reduces per-iteration complexity relative to the SDP-based baseline and uses rank selection and rank reduction to improve practical scalability. It also addresses isolated features by allowing null rows and columns in the recovered correspondence matrix.
- Computational complexity: O(m^2k) flops per MatchALS iteration contrasts with O(m^3) flops per MatchLift iteration, because the methods are dominated by matrix multiplication and eigenvalue decomposition, respectively.The paper also notes that matrix multiplication is parallelizable, whereas parallelizing eigenvalue decomposition remains open.
- Computational complexity: MatchALS and MatchLift require similar iteration counts to converge according to the authors’ observations.This makes the per-iteration complexity comparison especially relevant to runtime.
- Selection of k: The factor dimension k should exceed the true solution rank, but the solution is insensitive to k once k is larger than the underlying rank.The paper reports that noisy and incomplete inputs made spectral rank estimation inaccurate, motivating a heuristic choice of k.
- Rank reduction: Real image collections may contain isolated features, which can inflate the universe size and increase the required computation.The original constraint forces every feature to match a universe point, even when no correspondence exists.
- Rank reduction: Allowing m′ ≤ m permits null rows and columns, automatically pruning isolated features and enabling a smaller k; the paper sets m′ = m in simulation and m′ = 0.7m in real experiments.When m′ < m, switching off isolated features reduces the nuclear norm without sacrificing many affinity scores.
6. Experiments
Experiments show that MatchALS performs competitively with leading joint-matching methods while substantially reducing computation, and extends matching to different object instances for category-specific reconstruction.
- 6.1 Experiments: Synthetic tests use permutation-matrix ground truth with controlled observation ratios, image counts, and corruption rates to evaluate matching error.The universe contains 20 points, with missing observations and false or removed matches simulated at error rate ρe.
- 6.1.1 Matching errors: With sufficiently many images, all methods achieve nearly exact recovery even when the input error rate exceeds 50%.MatchALS and MatchLift perform similarly and outperform the spectral method, especially at low observation ratios.
- 6.1.2 Sensitivity to parameters: MatchALS is insensitive to factor dimension k once k exceeds the true rank, whereas k below the true rank causes alternating minimization to fail.The experiments use k = 2ˆr as a compromise between safety and efficiency; performance is also insensitive to sufficiently large λ.
- 6.2.1 Graffiti datasets: On six Graffiti datasets, joint matching improves over original pairwise matching, with MatchALS and MatchLift performing similarly and better than the spectral method.Performance curves report percentages of correct matches against distance thresholds, and Table 2 summarizes areas under the curves and computation times.
- 6.2.1 Graffiti datasets: MatchALS achieves an average computation speedup of approximately 30 times over MatchLift on the Graffiti datasets.The comparison uses average computation time alongside matching scores derived from the performance-curve areas.
- 6.2.1 Graffiti datasets: Joint matching removes false matches and fills missing correspondences under viewpoint, blur, and illumination changes.Visual comparisons declare matches within five pixels of ground truth correct and show denser true-match lines with fewer false-match lines.
- 6.2.2 Matching different objects: Using deep features and graph matching, the method improves correspondence quality across different sedan and SUV instances.The resulting correspondences support visible 3D structures despite noise and missing points, while more sophisticated reconstruction is outside the paper’s scope.
7. Conclusion
The paper presents an efficient global approach to multi-image matching that jointly optimizes feature affinities and cycle consistency. Experiments support its effectiveness and show potential for matching different object instances toward reconstructing object models.
- The method uses pairwise feature similarities or graph matching scores as input and produces accurate matches with an efficient algorithm.
- The algorithm globally optimizes both feature affinities and cycle consistency across matches.
- Experiments validate the method's effectiveness on multi-image matching.
- Joint matching is demonstrated as a promising first step toward reconstructing object models from crowd-sourced images of different object instances.