精读笔记
Problem Setting
这篇论文真正处理的是 robust geometric model estimation 里的有限预算搜索问题，而不是提出新的几何模型或新的 consensus objective。经典最大共识的难点在于 inlier set 和 model 参数互相依赖：没有好模型找不到 inliers，没有 inliers 又估不出好模型。RANSAC 通过随机 minimal sampling 绕过这个循环，但代价随 outlier ratio 和 minimal sample size 急剧上升；LO-RANSAC、GC-RANSAC、MAGSAC 等改善的是 sampling 后的 scoring/refinement/noise handling，并没有根本移除随机 hypothesis generation。这里的关键矛盾是：需要全局探索以避免局部错误结构，但又不能像 deterministic global consensus maximization 那样承担指数级或强问题特化的搜索成本。
Motivation
作者的核心动机是：真实匹配的 inliers 通常不是在模型空间中均匀分布的，而是在某个合适模型的 residual space 里表现为密集、稳定、可逐步追踪的区域。如果这个结构可用，那么没有必要大量随机抽 minimal sets；可以从粗模型出发，通过残差排序逐渐收缩支持集，把模型推向更密集的 residual basin。现有路线缺的是一种实用的 deterministic exploration：比 RANSAC 少随机性，比 branch-and-bound 少全局优化负担。DS-SAC 正是试图填这个空位。
Core Idea
DS-SAC 的核心不是“多了 forward/backward/search/partition 几个模块”，而是改变了 hypothesis generation 的组织方式：从 sample-first 变成 density-first。RANSAC 的信息流是先随机抽小集合、估模型、再用全体点验证；DS-SAC 反过来先用大量点给出粗模型，再用全体点对当前模型的残差排序来决定下一次支持集，从而让所有点持续参与搜索路径的塑形。
这个设计引入的 inductive bias 是：正确模型附近的 inliers 会在 residual ranking 中形成连续且可吸附的密集核。forward search 相当于沿支持集百分位做 annealing，把高噪声/外点逐步剥离；backward search 则避免过度收缩后只拟合一个过小核心；signed-residual partitioning 提供低成本的多区域探索。它和 prior 的本质区别不在 objective，而在用 residual-density trajectory 替代 random minimal-set trajectory，因此更像一种 deterministic test-time search policy。
Method
方法上最重要的是三层机制。第一，percentile residual search：每次根据当前模型对全体点排序，取前 p% 重估模型。它解决的是随机采样浪费问题，核心变化是把候选模型生成变成一条由残差密度诱导的连续路径。第二，inlier optimization：在每个 percentile 更新后，再按固定阈值取 inliers 重估。它解决 percentile objective 和最终 consensus objective 不一致的问题，否则模型可能只追逐低残差小簇。第三，recursive signed-residual partitioning：用当前较好模型的 signed residual 把点集二分并递归搜索。它解决单一路径容易陷入错误 basin 的问题，但这是启发式全局探索，不是严格全局最优保证。
post-tuning 只是最终阈值松到紧的 refinement，更像 LO-RANSAC 式局部打磨；precomputing linear coefficients、solver selection、bundle optimization 都属于实现层面的效率/精度增强，不应被视为核心算法贡献。
Key Insight / Why It Works
最可能真正有效的部分是 residual ranking 诱导出的 curriculum。DS-SAC 本质上利用了一个几何估计里的 latent structure：如果当前模型没有完全崩坏，那么真实 inliers 会在残差排序前部富集；逐步减小支持集比例会提高 inlier purity，重估模型后又会进一步改善排序，形成正反馈。这和 EM、graduated non-convexity、trimmed least squares、iterative reweighted fitting 有亲缘关系，只是作者把它包装成 sample consensus 的替代搜索过程。
forward search 是核心贡献；backward search 是防止 shrink 过头的补偿机制；post-tuning 是辅助。recursive partitioning 的价值取决于 signed residual 是否真的把不同 basin 分开，这一点文中论证不足。它可能在 epipolar/homography 任务上好用，因为 residual sign 对几何约束有一定方向性，但不一定能泛化到任意 robust fitting。
这篇的增益很可能来自 better inductive bias + test-time compute redistribution，而不是新的数学最优性。它把 compute 从随机 minimal hypotheses 转移到排序、重估和局部路径跟踪上；在 SuperPoint+LightGlue 这类匹配质量较高、inlier basin 已经存在的数据上，这种策略很划算。若匹配质量差到 all-point initialization 完全不可用，或错误匹配形成更强密集簇，DS-SAC 的确定性反而可能比 RANSAC 更脆弱，因为缺少随机跳出机制。
Relation To Prior Work
DS-SAC 最接近的技术谱系不是纯 RANSAC，而是 trimmed estimation / deterministic local search / LO-style iterative re-estimation 的组合。它与 LO-RANSAC、GC-RANSAC 的共同点是反复从当前支持集重估模型；区别是 LO/GC 依赖随机好假设触发局部优化，而 DS-SAC 把整个搜索过程都改成残差密度驱动。和 MAGSAC 的区别在于，MAGSAC 主要处理 noise scale uncertainty，DS-SAC 主要处理 hypothesis generation efficiency。
和 deterministic consensus maximization 相比，DS-SAC 没有 branch-and-bound 的 bound、也没有 convex relaxation 的全局性；它是启发式 deterministic search，不是 exact solver。看似新的部分里，percentile shrink 与 inlier re-estimation 有明显已有思想重组的味道；实质新增的信息在于：把 residual-density path、反向扩张和 signed-residual recursive partition 组合成一个可替代 RANSAC sampling loop 的完整框架，并在标准几何估计任务上做了系统验证。
Dataset / Evaluation
评估覆盖 homography、fundamental matrix、essential matrix，数据来自室内、室外、驾驶、AR/localization 等多场景，使用 SuperPoint+LightGlue 匹配，任务范围足以支撑“几何视觉鲁棒估计”这一应用 claim。多数据集平均也避免了单个 benchmark 主导结论，整体实验设计比只在小规模匹配集上报结果更有说服力。
但 evaluation 仍有明显限制。第一，所有方法固定 1000 iterations，对 RANSAC 系方法是自然预算，对 DS-SAC 则不是同一意义上的预算；公平性应按 wall-clock、成功率、质量-时间曲线共同看。第二，baseline 实现来自不同库，优化程度、编译设置、local refinement、threshold convention 可能影响 runtime 和 accuracy。第三，缺少极端 outlier、退化、多模型、多重复结构场景的 breakdown；这些才是验证 density-search 是否稳健的关键。第四，文中没有充分隔离 bundle optimization、post-tuning、precomputation 对结果的贡献，因此核心机制的独立收益仍不够清楚。
Limitation
最大隐含前提是 residual space 中存在可由粗初始化追踪到的 inlier density basin。这个前提在现代 learned matching 后通常成立，但它不是 robust estimation 的普遍真理；如果 outliers 有结构性、错误匹配形成大密度簇，DS-SAC 可能会确定性地追到错误模型。换言之，它把随机采样失败风险转化成了 basin attraction 失败风险。
scalability 方面，论文给出 O(N²) worst-case / O(N log N) balanced-case 的迭代分析，但这个分析较粗，主要数 partition/search steps，没有充分计入每步全体残差计算、排序/选择、模型求解和非线性 refinement 的真实代价。所谓 polynomial 并不等于大规模上天然优于高度优化的 RANSAC family。
泛化 claim 也应谨慎。方法依赖模型可 least-squares 重估、残差可排序、signed residual 可二分、阈值 T 有意义；这些条件在 H/F/E 估计中自然，但迁移到其他视觉几何或非几何 robust fitting 时不一定成立。增益来源不清：可能部分来自工程实现、solver choice、precomputation 和 evaluation protocol，而不完全来自 density search 本身。
Takeaway
- 最值得记住的是：RANSAC 的核心瓶颈可以不只通过 smarter sampling 解决，也可以通过重新组织 test-time search，把 compute 用在 residual-density trajectory 上。
- 这个方向未来可能演化成 hybrid deterministic-random estimators：先用 density search 找 basin，再用少量随机/多启动机制处理 basin failure。
- 第二，percentile shrink/expand 是一个可迁移的机制：在任何“好解附近样本残差会富集”的问题里，都可以作为 trimmed fitting 的动态路径，而不是固定 trimming ratio。
- 第三，recursive partitioning 提示了一个方向：用当前模型诱导的数据空间切分来近似全局探索，但这部分需要更强的理论或失败案例分析。
一句话总结
DS-SAC 是介于 RANSAC 随机采样和昂贵确定性共识优化之间的一种 residual-density-driven test-time search 方法，真正贡献在于用确定性的支持集路径重组 hypothesis generation，而不是提出新的几何目标函数。