[Feature]: Implement Sequential Probability Ratio Test (SPRT) for PnP RANSAC
#1,073 建立於 2026年8月4日
倉庫指標
- 星標
- (675 顆星)
- PR 合併指標
- (PR 指標待抓取)
描述
🚀 Feature Description
Integrate a Sequential Probability Ratio Test (SPRT) mechanism into the RANSAC loop for PnP pose estimation solvers (AP3P and EPnP). SPRT allows the solver to quickly discard hypothesis models that are statistically unlikely to be correct by examining a small subset of points before performing a full inlier count. This improves the probability of finding the global optimum within a fixed time budget by increasing the number of hypotheses that can be evaluated.
📂 Feature Category
Performance Optimization
💡 Motivation
Current benchmarks indicate a performance divergence between kornia-rs and OpenCV as the inlier ratio increases. While kornia-rs demonstrates superior speed and accuracy at low inlier ratios (10%–30%), it loses its accuracy edge at higher ratios.
Comparison at 50% Inlier Ratio:
| Solver | $R_{err}^\circ$ | $t_{err}$ | Latency (ms) |
|---|---|---|---|
k_ap3p (avg) |
$\approx 0.48$ | $\approx 0.044$ | $\approx 9.0$ |
opencv_ap3p |
$0.237$ | $0.020$ | $2.5$ |
k_epnp (avg) |
$\approx 0.71$ | $\approx 0.067$ | $\approx 11.0$ |
opencv_epnp |
$0.386$ | $0.036$ | $8.9$ |
The significant gap in accuracy (approximately $2\times$ higher error for kornia-rs at 50% inliers) suggests that the current RANSAC implementation fails to converge to the best model as effectively as OpenCV. The implementation of SPRT is expected to bridge this gap by efficiently pruning poor candidates and focusing the search on high-quality models.
💭 Proposed Solution
- SPRT Integration: Implement the SPRT logic within the main RANSAC loop for both AP3P and EPnP implementations.
- Early Rejection Logic:
- Define a small, fixed-size sample of points for an initial "quick-check".
- Compute the log-likelihood ratio of the model being an inlier vs. an outlier.
- Implement thresholds for early rejection (poor model) and early acceptance (high-confidence model) to avoid full verification of suboptimal hypotheses.
- Consistency: Ensure the implementation aligns with recent refactors regarding borrowed buffers and domain fields in the
ioandimagemodules. - Verification: Validate the implementation using the existing benchmark suite to ensure accuracy at 50%+ inlier ratios matches or exceeds OpenCV.
📚 Library Reference
- Refer to the OpenCV implementation of
solvePnPRansac, specifically the logic used for early termination of model verification via the Sequential Probability Ratio Test.
🔄 Alternatives Considered
- Increasing Iteration Count: Increasing the number of RANSAC iterations would increase latency without guaranteeing convergence to the most accurate model.
- Modified Sampling Strategy: Altering how points are sampled may provide marginal gains but does not address the efficiency of the verification phase.
Additional Context
══════════════════════════════════════════════════════════════════════════
Solver Ratio Inliers/Tot Recall R_err° t_err ms
──────────────────────────────────────────────────────────────────────────
k_ap3p_lo0 10% 61.0/600 1.02 0.268 0.0276 29.9
k_ap3p_lo1 10% 60.8/600 1.01 0.253 0.0294 29.7
k_ap3p_lo2 10% 61.2/600 1.02 0.242 0.0188 30.1
k_ap3p_lo3 10% 60.8/600 1.01 0.238 0.0324 29.2
k_epnp_lo0 10% 56.4/600 0.94 1.284 0.1254 160.9
k_epnp_lo1 10% 61.0/600 1.02 0.241 0.0211 162.3
k_epnp_lo2 10% 61.0/600 1.02 0.239 0.0224 162.0
k_epnp_lo3 10% 56.6/600 0.94 1.258 0.1259 161.0
opencv_ap3p 10% 60.6/600 1.01 0.315 0.0268 208.1
opencv_epnp 10% 30.6/600 0.51 12.450 1.1784 393.4
──────────────────────────────────────────────────────────────────────────
k_ap3p_lo0 20% 120.6/600 1.01 0.227 0.0278 6.5
k_ap3p_lo1 20% 120.6/600 1.01 0.233 0.0320 7.8
k_ap3p_lo2 20% 120.6/600 1.01 0.233 0.0320 7.1
k_ap3p_lo3 20% 120.6/600 1.01 0.238 0.0329 6.8
k_epnp_lo0 20% 120.6/600 1.01 0.234 0.0259 91.0
k_epnp_lo1 20% 120.6/600 1.01 0.270 0.0287 72.1
k_epnp_lo2 20% 120.6/600 1.01 0.243 0.0287 73.8
k_epnp_lo3 20% 120.6/600 1.01 0.271 0.0300 75.9
opencv_ap3p 20% 119.6/600 1.00 0.286 0.0292 91.1
opencv_epnp 20% 118.6/600 0.99 0.280 0.0286 389.2
──────────────────────────────────────────────────────────────────────────
k_ap3p_lo0 30% 180.4/600 1.00 0.111 0.0121 4.7
k_ap3p_lo1 30% 180.4/600 1.00 0.129 0.0129 7.2
k_ap3p_lo2 30% 180.4/600 1.00 0.117 0.0138 5.9
k_ap3p_lo3 30% 180.4/600 1.00 0.122 0.0127 6.5
k_epnp_lo0 30% 180.4/600 1.00 0.089 0.0107 18.1
k_epnp_lo1 30% 180.4/600 1.00 0.124 0.0135 20.2
k_epnp_lo2 30% 180.4/600 1.00 0.116 0.0130 19.4
k_epnp_lo3 30% 180.4/600 1.00 0.127 0.0138 19.1
opencv_ap3p 30% 178.4/600 0.99 0.188 0.0155 18.8
opencv_epnp 30% 179.2/600 1.00 0.128 0.0138 113.4
──────────────────────────────────────────────────────────────────────────
k_ap3p_lo0 50% 299.4/600 1.00 0.482 0.0439 6.7
k_ap3p_lo1 50% 299.4/600 1.00 0.488 0.0444 11.6
k_ap3p_lo2 50% 299.4/600 1.00 0.483 0.0440 9.6
k_ap3p_lo3 50% 299.4/600 1.00 0.488 0.0444 9.7
k_epnp_lo0 50% 299.4/600 1.00 0.689 0.0652 8.4
k_epnp_lo1 50% 299.4/600 1.00 0.720 0.0697 13.2
k_epnp_lo2 50% 299.4/600 1.00 0.714 0.0693 11.0
k_epnp_lo3 50% 299.4/600 1.00 0.709 0.0688 11.0
opencv_ap3p 50% 297.6/600 0.99 0.237 0.0203 2.5
opencv_epnp 50% 299.0/600 1.00 0.386 0.0364 8.9
══════════════════════════════════════════════════════════════════════════
🤝 Contribution Intent
- I plan to submit a PR to implement this feature
- I'm requesting this feature but not planning to implement it