Pixel-Accurate Epipolar Guided Matching

Oleksii Nasypanyi; Francois Rameau

cs.CVMar 19, 2026

Pixel-Accurate Epipolar Guided Matching

Authors: Oleksii Nasypanyi, Francois Rameau

Organizations: Stony Brook University,USA · SUNY Korea, Incheon, Korea

Abstract

Keypoint matching can be slow and unreliable in challenging conditions such as repetitive textures or wide-baseline views. In such cases, known geometric relations (e.g., the fundamental matrix) can be used to restrict potential correspondences to a narrow epipolar envelope, thereby reducing the search space and improving robustness. These epipolar-guided matching approaches have proved effective in tasks such as SfM; however, most rely on coarse spatial binning, which introduces approximation errors, requires costly post-processing, and may miss valid correspondences. We address these limitations with an exact formulation that performs candidate selection directly in angular space. In our approach, each keypoint is assigned a tolerance circle which, when viewed from the epipole, defines an angular interval. Matching then becomes a 1D angular interval query, solved efficiently in logarithmic time with a segment tree. This guarantees pixel-level tolerance, supports per-keypoint control, and removes unnecessary descriptor comparisons. Extensive evaluation on ETH3D demonstrates noticeable speedups over existing approaches while recovering exact correspondence sets.

Figures & tables

Figure 1: Overview of the guided matching process. Given a query point in image 1 $\mathbf{p}_{1}^{1}$ , its corresponding epipolar line in image 2 $\mathbf{l}_{2}^{1}$ (yellow) restricts the search space to a narrow envelope of width $2\epsilon$ . Any keypoint lying within this region (e.g., $\mathbf{p}_{4}^{2}$ and $\mathbf{p}_{3}^{2}$ ) is considered a valid candidate for matching. This can be determined by computing the orthogonal distance from each keypoint to the epipolar line, but such brute-force checks are computationally expensive. Instead, we draw circles of diameter $2\epsilon$ around each keypoint in image 2 and test whether the epipolar line intersects any of them (orange stars). Interestingly, this geometric test can be reformulated as a fast 1D angular range query: for each circle, the angle interval formed by the two tangents from the epipole defines a valid angular interval, and a candidate is retained if the epipolar line direction lies within it. Green points indicate inliers, red points are outliers.

Figure 2: Comparison of three epipolar correspondence filtering strategies. Unlike our approach, Epipolar Hashing [ 3 ] and Grid-based [ 29 ] methods return matches outside the true epipolar region (false positives) and miss valid matches within it (false negatives).

Panel of Figure 3 — Figure 3: Epipolar geometry and envelope-based match filtering. Given a point $\mathbf{p}_{1}^{1}$ in the first image, its corresponding epipolar line $\mathbf{l}_{1}^{2}$ is shown in the second image. The grey band illustrates an epipolar envelope of width $2\epsilon$ , used to retain only candidate matches such as $\mathbf{p}_{1}^{2}$ and $\mathbf{p}_{3}^{2}$ .

Operation	Time Complexity	Space Complexity
Angular interval computation	$O(n)$	$O(n)$
Segment tree construction	$O(n\log(n)$	$O(n)$
Single epipolar query	$O(\log(n)+k)$	$O(1)$
Total matching (all queries)	$O(m(\log(n)+\bar{k}))$	$O(n)$

Table 1: Computational Complexity Analysis

Panel of Figure 4 — Figure 4: Illustration of the angular interval query strategy. Given an epipolar line $\mathbf{l}_{1}^{2}$ (orange), inlier points lie within the epipolar envelope (yellow). All angular intervals $\Theta_{j}$ that contain the epipolar line angle $\alpha_{1}$ correspond to valid match candidates, forming the set $\mathscr{C}_{1}^{2}$ . In this example, the points $\mathbf{p}_{1}^{2}$ and $\mathbf{p}_{4}^{2}$ have intervals $\Theta_{1}$ and $\Theta_{4}$ that include $\alpha_{1}$ , and are therefore considered inliers. For the point $\mathbf{p}_{2}^{2}$ , the construction of its interval $\Theta_{2}$ is illustrated via its central direction $\theta_{2}$ and angular radius $\delta_{2}$ . The point $\mathbf{p}_{3}^{2}$ exemplifies a wrap-around case, where the interval spans the $0/\pi$ boundary. It is therefore split into two sub-intervals $\Theta_{3}^{(1)}$ and $\Theta_{3}^{(2)}$ in the segment tree.

Figure 5: Comparison of the number of correctly matched points in a challenging scene with many repetitive structures, such as grass, rooftops, and building facades. (Top) Brute-Force (BF) matching. (Middle) FLANN-based matching. (Bottom) Our epipolar-guided matching. A match is considered correct if the 3D distance between correspondences is below 0.1 meters.

Figure 6: Impact of epipolar tolerance on candidate generation with 25,000 keypoints per image. (Left) Candidate generation execution time. (Right) Candidate set recall.

	Latency (Cand. Gen. / Desc. Match.) ms. $\downarrow$					Candidates Recall $\uparrow$			Matching Recall $\uparrow$					Matches Num.
Sequence	BF	FLANN	Ours	Hash	Grid	Ours	Hash	Grid	BF	FLANN	Ours	Hash	Grid	BF	FLANN	Ours	Hash	Grid
courtyard	0/2961	0/957	34/101	76/87	145/106	1.00	0.94	0.91	0.19	0.18	0.25	0.24	0.25	4891	4661	28900	28917	28807
delivery	0/231	0/212	2/7	11/6	22/7	1.00	0.98	0.89	0.34	0.33	0.46	0.47	0.46	3704	3537	6691	6691	6677
electro	0/27	0/50	2 / 2	2 / 3	4 / 2	1.00	0.85	0.91	0.21	0.19	0.38	0.39	0.40	977	935	5880	5879	5901
facade	0/2808	0/856	35/99	73/83	362/107	1.00	0.89	0.93	0.25	0.22	0.35	0.35	0.34	20335	19752	38282	38350	38265
kicker	0/894	0/321	7/14	13/12	53/15	1.00	0.91	0.92	0.23	0.23	0.54	0.55	0.54	2589	2539	10296	10103	10269

Table 2: Median results across all ETH3D [ 28 ] scenes using GMS (Lowe’s ratio results are reported in the supplementary material). Best results are highlighted in bold . For latency, results are compared based on the total time for candidate generation and descriptor matching.

Figure 7: Impact of the number of keypoints on execution latency. (Left) Total matching time. (Right) Candidate set generation time (descriptor matching time is not included).

Figure 8: Matching recall under varying pose noise. Larger noise values correspond to greater perturbations in relative camera pose.

Figure 9: Point Matching Latency Breakdown.

Figure 10: Comparison of three epipolar correspondence filtering strategies. (Left) Ours. (Middle) Epipolar Hashing. (Right) Grid-based. Green points represent true positive candidates, red - false negatives, and blue - false positives.

Figure 11: Comparison of three epipolar correspondence filtering strategies when the epipole lies inside the image. (Left) Ours. (Middle) Epipolar Hashing. (Right) Grid-based. Green points represent true positive candidates, red - false negatives, blue - false positives. The large light blue point indicates the epipole.

	Latency (Cand. Gen. / Desc. Match.) ms. $\downarrow$					Candidates Recall $\uparrow$			Matching Recall $\uparrow$					Matches Num.
Sequence	BF	FLANN	Ours	Hash	Grid	Ours	Hash	Grid	BF	FLANN	Ours	Hash	Grid	BF	FLANN	Ours	Hash	Grid
courtyard	0/2961	0/957	34/102	76/87	145/106	1.00	0.94	0.91	0.19	0.18	0.29	0.30	0.29	4891	4661	37346	37346	37346
delivery	0/231	0/212	2/8	11/8	22/8	1.00	0.98	0.89	0.34	0.33	0.57	0.57	0.57	3704	3537	10858	10858	10858
electro	0/27	0/50	2 / 2	2 / 2	4 / 2	1.00	0.85	0.91	0.21	0.19	0.67	0.66	0.67	977	935	8534	8578	8531
facade	0/2808	0/856	35/104	73/89	362/90	1.00	0.89	0.93	0.25	0.22	0.39	0.39	0.39	20335	19752	45344	45157	45126
kicker	0/894	0/321	7/15	13/13	53/14	1.00	0.91	0.92	0.23	0.23	0.63	0.63	0.63	2589	2539	14441	14438	14435

Table 3: Median results across all ETH3D [ 28 ] scenes using Lowe’s ratio.

Image Matching

Image matching finds corresponding points, regions, or objects across images despite changes in viewpoint, scale, lighting, or sensor.

See all 84 papers

CLAD: Keypoint Matching Using Global Line Correspondences
Oct 15, 2026Masaki SatohImage Matching Local Feature Matching
Morpho, Inc. Tokyo, Japan
EpiDiffVO: Geometry-Aware Epipolar Diffusion for Robust Visual Odometry
May 19, 2026Prateeth RaoMulti-View Geometry Relative Pose Estimation
International Institute of Information Technology Bangalore, Bengaluru, India
SURE: Semi-dense Uncertainty-REfined Feature Matching
Mar 5, 2026Sicheng Li, Zaiwang Gu, Jie Zhang +3Image Matching
S. Li and X. Jiang are with the School of Electrical and Electronic Engineering, Nanyang Technological University (NTU), Singapore. · J. Zhang and S. Li are with Institute of High Performance Computing, Agency for Science, Technology and Research (A*STAR), Singapore. · J. Cheng and Z. Gu are with the Institute for Infocomm Research (I2R), Agency for Science, Technology and Research (A*STAR), Singapore. +1

Oct 15, 2026J/K move · Enter open · S save

CLAD: Keypoint Matching Using Global Line Correspondences

Masaki Satoh

Morpho, Inc. Tokyo, Japan

Image Matching Local Feature Matching

Open paper AskPDF arXiv

Traditional keypoint descriptors, such as SIFT (Scale-Invariant Feature Transform) and ORB (Oriented FAST and Rotated BRIEF), are computed from local image patches. They may be unreliable in scenes with repetitive patterns or weak textures, where patches at different locations can look similar. We propose the Contextual Line-Assisted Descriptor (CLAD), a keypoint matching method that addresses this problem by using global geometric context from line correspondences. CLAD represents each keypoint with a vector whose elements indicate its proximity to matched lines. It can therefore use the keypoint's spatial relationships to the lines in the scene. We use HOME (Hough-space One-dimensional Matching of Extrema) to detect both clear and weak linear structures and to establish enough line-to-keypoint associations to represent this context. Evaluations on the TUM RGB-D SLAM dataset and outdoor video sequences show that CLAD provides geometrically consistent matches that complement those obtained with traditional local descriptors. In repetitive scenes, where local descriptors may not distinguish similar patches, CLAD uses global structure to improve matching reliability. The method is computationally lightweight and practical to implement.

Abstract

Image Matching

Explore similar work

CLAD: Keypoint Matching Using Global Line Correspondences

EpiDiffVO: Geometry-Aware Epipolar Diffusion for Robust Visual Odometry

SURE: Semi-dense Uncertainty-REfined Feature Matching