Source-linked AI summary
Learning to Match Features with Seeded Graph Matching Network
Hongkai Chen, Zixin Luo, Jiahui Zhang, Lei Zhou, Xuyang Bai, Zeyu Hu, Chiew-Lan Tai, Long Quan
TL;DR
Feature matching across images must handle dense correspondence reasoning without the prohibitive cost of fully connected attention. SGMNet uses reliable seed matches as bottlenecks for sparse graph message passing, and experiments report competitive or higher accuracy with improved efficiency.
Problem
Dense graph matching can require O(N^2C) computation and O(N^2) memory, while prior outlier-rejection methods cannot find more matches than nearest-neighbor matching and neglect local descriptors.
Method
SGMNet generates reliable seed matches and uses them in a sparsified graph neural network with Attentional Pooling, Seed Filtering, and Attentional Unpooling.
Results
SGMNet achieves competitive or higher accuracy on different tasks and datasets while requiring modest computation and memory; for 10k features, it runs 7 times faster and uses 50% less GPU memory than SuperGlue.
Takeaways & Limitations
Seed-bottlenecked message passing provides a compact attention pattern for efficient image matching and downstream tasks.
Takeaways & Limitations
The method targets the limitations of dense graph matching and prior correspondence-based rejection, whose stated costs and constraints motivate its design.
Abstract
from arXiv · showhide
Matching local features across images is a fundamental problem in computer vision. Targeting towards high accuracy and efficiency, we propose Seeded Graph Matching Network, a graph neural network with sparse structure to reduce redundant connectivity and learn compact representation. The network consists of 1) Seeding Module, which initializes the matching by generating a small set of reliable matches as seeds. 2) Seeded Graph Neural Network, which utilizes seed matches to pass messages within/across images and predicts assignment costs. Three novel operations are proposed as basic elements for message passing: 1) Attentional Pooling, which aggregates keypoint features within the image to seed matches. 2) Seed Filtering, which enhances seed features and exchanges messages across images. 3) Attentional Unpooling, which propagates seed features back to original keypoints. Experiments show that our method reduces computational and memory complexity significantly compared with typical attention-based networks while competitive or higher performance is achieved.
1. Introduction
Reliable cross-image correspondences support camera-pose and scene-structure recovery, but dense graph matching is costly and may exchange redundant messages. SGMNet addresses these issues with seed-guided sparse message passing and reports competitive accuracy with substantially better efficiency.
- Reliable correspondences support relative camera-pose and scene-structure recovery in SfM, MVS, and SLAM.
- Learned outlier-rejection methods operate on pre-matched correspondences and neglect original local visual descriptors.
- Dense graph matching exchanges visual and geometric context but incurs O(N^2C) computation and O(N^2) memory for N keypoints and channel width C.
- Dense connectivity may create redundant message exchange because many keypoints are unrepeatable and most SuperGlue edges tend to have zero strength.
- SGMNet seeds matching with a small set of reliable correspondences, then uses Attentional Pooling, Seed Filtering, and Attentional Unpooling for sparse message passing.
- Seed bottlenecks reduce attention complexity from O(N^2C) to O(NKC), where K is the number of seeds and K ≪ N.
- 7 times faster and 50% less GPU memory are reported for SGMNet than SuperGlue when matching 10k features, with competitive or higher accuracy.
2. Related Works
Related work spans learned descriptors and matching, efficient attention, and graph matching. SGMNet adapts seed-based graph matching to produce compact message passing for large keypoint sets.
- Learnable image matching improves local descriptors, keypoints, outlier rejection, and robust estimation within geometry-based vision tasks.
- SuperGlue integrates feature matching and outlier rejection in a GNN but suffers excessive fully connected attention cost for many features.
- SGMNet retains end-to-end matching and refinement while reducing computation and memory through an attention block designed for image matching.
- Efficient-attention research reduces quadratic cost through sparse patterns, pruning, grouping, or pooling, but generally targets self-attention rather than cross-attention.
- SGMNet uses reliable seed correspondences as bottlenecks between original point sets to pass cross-image messages at low cost.
- The network generates seed matches and uses them to guide message passing across keypoint graphs, enabling large keypoint sets with lower memory and computation.
3. Methodology
SGMNet matches keypoints by using reliable seed correspondences as bottlenecks for sparse graph message passing. Its pooling, seed filtering, and unpooling operations update full keypoint features while reducing redundant communication and supporting iterative refinement.
- Overview: SGMNet formulates keypoint matching as graph matching but uses seed correspondences instead of fully connected graphs to reduce memory and computation.The network takes keypoints and visual descriptors from two images, embeds positions, and combines them with descriptors for initial representations.
- Seeding Module: The Seeding Module generates putative nearest-neighbor matches, scores them with inverse distance ratios, and applies NMS for spatial coverage.It outputs seed index lists for both images; a reseeding module later regenerates seeds from the updated assignment matrix.
- Seeded Graph Neural Network: Each Seeded GNN unit pools context from full keypoint sets into seed matches, filters seed features, and unpools renewed messages back to original keypoints.Weighted attentional aggregation adjusts the contribution of attended features, while attentional unpooling broadcasts pooled contexts to every keypoint.
- Seed Filtering: Seed filtering exchanges intra- and inter-graph messages and predicts inlier scores used to weight seed features during unpooling.Applying inlier scores suppresses information from false seeds and supports robustness to seeding noise.
- Assignment and Refinement: Final updated features form a correlation-based assignment matrix, and Sinkhorn normalization with a dustbin channel produces matches after confidence-based outlier removal.The architecture can stack processing units and use reseeding for further refinement before final assignment.
4. Experiments
Experiments evaluate SGMNet on image matching, visual localization, and scalability, comparing accuracy and efficiency with classical, filter-based, and graph-neural-network methods. The method is generally competitive or better while reducing runtime and memory, especially for large keypoint sets.
- Image Matching: SGMNet is evaluated on YFCC100M, FM-Bench, and ScanNet using pose, recall, correspondence, matching-score, and precision metrics.FM-Bench covers driving, indoor SLAM, and wide-baseline reconstruction scenarios.
- Image Matching: Across YFCC100M, ScanNet, and wide-baseline FM-Bench subsets, SGMNet is mostly competitive with state-of-the-art methods and produces many inlier correspondences.Its advantages diminish on the easier small-baseline TUM and KITTI subsets.
- Visual Localization: On Aachen Day-Night, SGMNet performs better than SuperGlue with RootSIFT, remains competitive with SuperPoint and ContextDesc, and consistently outperforms OANet.The reported results support generalization to challenging visual-localization applications.
- Scalability: At 10k keypoints without Sinkhorn iterations, SGMNet reduces runtime by one magnitude compared with SuperGlue.The comparison reports runtime on a GTX 1080 GPU and attributes the improvement to the graph-neural-network design.
- Scalability: With 1k keypoints and batch size 16, SGMNet consumes less than 9GB GPU memory for training versus up to 23GB for SuperGlue.During testing, SGMNet uses half as much memory as SuperGlue when keypoint count exceeds 2k.
- Scalability: As more RootSIFT keypoints are used on Aachen Day-Night, accuracy increases for both SGMNet and SuperGlue, while SGMNet retains an efficiency advantage.This supports using larger keypoint sets when matching cost remains manageable.
5. Discussions
Discussion experiments examine component contributions, comparisons with filter-based methods, and alternative seeding or pooling designs. The results support reliable seeding and seed-based pooling as important choices for efficient matching.
- Ablation Study: Ablation results show that every tested component contributes notably to final performance on YFCC100M with RootSIFT.The authors particularly identify reliable seeding as important for guiding message passing across images.
- Comparison with Filter-based Methods: With 4k keypoints, SGMNet achieves the best performance among compared filter-based methods while running 4 times faster than SuperGlue with 10 Sinkhorn iterations.Filter-based methods remain faster at inference, but have a considerable performance gap relative to graph-neural-network methods.
- Design Analysis: Learnable seeding provides limited improvement over the simple heuristic strategy, while general pooling operations are ineffective alternatives to seed-based pooling.The tested alternatives include diffPool and set transformer designs.
6. Conclusion
The paper concludes that SGMNet enables efficient image matching through compact attention patterns. Across tasks and datasets, it reaches competitive or higher accuracy with modest computation and memory costs.
- Conclusion: SGMNet uses newly developed operations to perform message passing with a compact attention pattern.The conclusion frames this design as the basis for efficient image matching.
- Conclusion: Experiments show competitive or higher feature-matching and downstream-task accuracy against state-of-the-art methods with modest computation and memory costs.The conclusion summarizes results across different tasks and datasets.
A.1 Training Details
Training uses GL3D-derived image pairs with geometric correspondence labels, fixed optimization settings, and implementation choices for seeding, attention, and benchmark evaluation. Additional visualizations illustrate how SGMNet handles noisy seeds.
- Training Data: Ground-truth matches are defined using reprojection distances: mutual-nearest keypoints below 3 pixels match, while points exceeding 10 pixels from every counterpart are unmatchable.Depth maps are used to reproject keypoints between images.
- Training Parameters: Training uses Adam with learning rate 10^-4, decay after 300k iterations, and blocked gradients between initial and refinement stages for the first 140k iterations.All weighted attention operations use four heads.
- Network Details: Initial seeding combines mutual-nearest-neighbor checking, ratio testing, and non-maximum suppression, while reseeding samples top-k assignments from a Sinkhorn-derived matrix.The implementation uses 10 Sinkhorn iterations for reseeding and 100 iterations elsewhere.
- Evaluation Implementation: Benchmark implementations use OpenCV or official feature extractors and follow dataset-specific pipelines for YFCC100M, ScanNet, FM-Bench, and Aachen Day-Night.The FM-Bench Python reimplementation tends to produce higher accuracy than the original implementation, especially on wide-baseline datasets.
- Qualitative Analysis: Visualizations compare raw putative matches, seed correspondences, and final SGMNet matches, showing that the network can discover patterns even from heavily noisy seeds.These patterns guide message passing across keypoints for robust matching.
B Designs of SGMNet
SGMNet balances matching quality and efficiency through learned seeding and seed-based pooling, while experiments compare alternative pooling designs and seeding strategies.
- Learned Seeding: SGMNet selects top-k correspondences by learned inlier likelihood scores for seeding instead of ratio scores.A lightweight permutation-invariant network predicts each correspondence’s inlier likelihood.
- Learned Seeding: A lightweight PointCN block slightly increases seed precision but does not meaningfully improve pose estimation.The result is reported in Table 7 using RootSIFT on YFCC100M.
- Design Trade-off: The authors identify more complex seeding strategies as a possible route to higher matching quality, but retain the current method for its performance–cost balance.The stated design choice prioritizes efficient matching.
- Pooling Designs: SGMNet’s efficiency relies on pooling original keypoints before message passing, with DiffPool and ISA evaluated as alternatives.These designs replace the proposed attentional pooling or seed-based attention operations.
- Pooling Designs: DiffPool and ISA provide only marginal improvements over baselines, whereas seed-based attentional pooling and unpooling are critical to SGMNet’s success.The comparison uses 128 pooled elements and up to 2k keypoints on YFCC100M.
C Fast Convergence
SGMNet converges faster than SuperGlue, and its accuracy depends on choosing a seed count proportional to the number of keypoints.
- Convergence: SGMNet takes fewer training iterations to reach convergence than SuperGlue.The comparison is shown in the training curves of Figure 8.
- Seed Number: An approximately proportional relationship between keypoint and seed counts yields the best performance.The effect is evaluated across different keypoint and seed counts on YFCC100M.
- Seed Number: Too many seeds may provide less reliable guidance, while too few cause severe information loss.Thus, seed count affects both efficiency and accuracy.
D.2 Robustness to Seed Noise
SGMNet remains effective with noisy seed correspondences, although weighted unpooling improves robustness as seed precision declines.
- Robustness: SGMNet maintains high matching quality even when seed correspondences contain substantial noise.The robustness test pads ground-truth inlier seeds with randomly sampled noise at different precision levels.
- Robustness: Without weighted unpooling, SGMNet’s pose estimation accuracy declines more rapidly as seed precision decreases.This indicates lower robustness to seed noise for the unweighted variant.
D.3 SfM Experiment
In the Alamo SfM experiment, SGMNet achieves reconstruction completeness comparable to SuperGlue while keeping matching time feasible for the full pipeline.
- Reconstruction: Both SuperGlue and SGMNet produce more complete reconstructions than vanilla nearest-neighbor matching and heuristic pruning.The comparison is reported for the Alamo scene from the 1DSFM dataset.
- Efficiency: SuperGlue substantially lengthens the total SfM pipeline time, whereas SGMNet keeps matching time at a feasible level.The experiment reports both matching time and whole-pipeline time.