Pixel-Accurate Epipolar Guided Matching
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
| Operation | Time Complexity | Space Complexity |
|---|---|---|
| Angular interval computation | ||
| Segment tree construction | ||
| Single epipolar query | ||
| Total matching (all queries) |
| Latency (Cand. Gen. / Desc. Match.) ms. | Candidates Recall | Matching Recall | 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 |
| Latency (Cand. Gen. / Desc. Match.) ms. | Candidates Recall | Matching Recall | 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 |
Image Matching
Image matching finds corresponding points, regions, or objects across images despite changes in viewpoint, scale, lighting, or sensor.
See all 84 papers