Dense Match Summarization for Faster Two-view Estimation

Jonathan Astermark, Anders Heyden, Viktor LarssonCVPR 2025 · DOI

This paper, presented at CVPR 2024 by Jonathan Astermark and colleagues from Lund University, addresses a critical computational bottleneck in modern computer vision: the high cost of using dense image matchers for 3D reconstruction and localization.

Introduction

To determine the relative pose (position and orientation) between two cameras, computer vision systems must find corresponding points between images. While traditional "sparse" methods like SIFT identify a few hundred distinct keypoints, modern "dense" matchers (such as DKM or RoMA) attempt to match nearly every pixel. These dense methods offer superior accuracy and robustness, particularly in low-texture environments like white walls or smooth floors.

However, dense matchers produce a massive volume of data—often exceeding 10,000 matches per image pair. The standard tool for converting these matches into a camera pose is RANSAC (Random Sample Consensus), which works by iteratively testing pose hypotheses. With 10,000+ points, the verification step in RANSAC becomes a major bottleneck, making real-time applications in robotics or augmented reality (AR) difficult.

The Match Summarization Pipeline

The authors propose a two-step "Match Summarization" scheme to bridge the gap between dense matching accuracy and sparse matching speed.

The Match Summarization pipeline: Dense matches are clustered spatially, summarized into geometric constraint matrices, and then used for efficient two-view estimation.
  1. Clustering: The algorithm groups thousands of dense matches into a small number of spatial clusters (typically $K=128$). A single "representative match" is selected for each cluster.
  2. Summarization via $9 \times 9$ Matrices: To avoid losing the geometric information contained in the discarded points, the authors summarize the constraints of all matches within a cluster into a single $9 \times 9$ matrix ($M_k$). By using a mathematical shortcut (Cholesky factorization), this matrix captures the collective "pull" of the entire neighborhood.

During the RANSAC process, the algorithm calculates a "proxy residual" using these $K$ matrices instead of iterating over the full set of 10,000 points. This allows RANSAC to operate on a sparse set while maintaining the geometric weight of the full dense match field.

Experimental Results

The method was evaluated across major benchmarks including MegaDepth-1500 (outdoor), ScanNet-1500 (indoor), and WxBS (wide baseline). It was tested with various state-of-the-art matchers like DKM, RoMA, and ASpanFormer.

Comparison of full dense matching (top) versus the proposed summarization (bottom). Summarization reduces RANSAC runtime from 98ms to 2.3ms with negligible impact on pose error.

Key Findings:

  • Significant Speedup: The RANSAC stage becomes 10x to 100x faster. On the MegaDepth dataset using DKM matches, RANSAC runtime dropped from 98 ms to just 2.3 ms.
  • Accuracy Preservation: Despite the massive data reduction, pose accuracy (measured as AUC at 5°) remains nearly identical to the full dense baseline. In some instances, summarized dense matches even outperformed sparse state-of-the-art methods like SuperPoint+LightGlue.
  • Matcher Agnostic: The summarization technique works regardless of the underlying dense matching algorithm used to generate the initial points.

Conclusion

The core insight of this work is that dense matches contain significant geometric redundancy. By approximating the complex Sampson error with a linear form, the authors can represent any number of points with a fixed-size matrix without increasing the computational cost of RANSAC scoring. While the dense matching step itself remains a computational challenge, this work effectively removes the robust estimation bottleneck, paving the way for more efficient large-scale 3D mapping and real-time localization.

Summary updated

BibTeX
@inproceedings{astermark2025dense,
  author = {Jonathan Astermark and Anders Heyden and Viktor Larsson},
  title = {{Dense Match Summarization for Faster Two-view Estimation}},
  booktitle = {IEEE/CVF Conference on Computer Vision and Pattern Recognition},
  year = {2025},
  doi = {10.1109/cvpr52734.2025.00110},
}
Figure