[Paper] 使用基于FFT的插值在不进行矩阵求逆的情况下求解最小问题

发布: 3天前 (2026年5月8日 GMT+8 01:03)

8 分钟阅读

原文: arXiv

Source: arXiv - 2605.06572v1

Overview

本文提出了一种在计算机视觉中求解 最小问题（即在估计相机姿态、基础矩阵或其他几何关系时出现的极小多项式方程组）的新方法。通过用基于快速傅里叶变换（FFT）的插值来取代昂贵的矩阵求逆，作者实现了既数值稳定又足够快速以适用于实时流水线的求解器。

无矩阵求逆求解器：使用稀疏隐藏变量结果式构建极小问题求解器，完全不进行符号矩阵求逆。
基于FFT的行列式重构：通过逆FFT从采样评估重建隐藏变量的行列式多项式，显著降低代数开销。
鲁棒子矩阵提取：使用最大公约数（GCD）准则在噪声数据下可靠定位秩缺失为1的子矩阵，随后采用克拉默法则进行回代。
全面评估：在一系列经典及新提出的极小问题上进行基准测试，显示出竞争性的运行时间（尤其是小规模系统）以及相较于最先进的 Gröbner 基和结果式求解器更优的数值稳定性。

隐藏变量结果式 – 原始的多变量多项式系统被重新写成，使得一个变量（隐藏变量）在每个方程中线性出现。这产生一个矩形系数矩阵，其行列式视为隐藏变量的一元多项式，在解处恰好为零。
采样与 FFT 插值 – 作者不对行列式进行符号展开（这很快变得难以处理），而是在复平面上等距点集处计算行列式的值。由于行列式是低次数多项式，其系数可通过逆 FFT 恢复，时间复杂度为 (O(n \log n))。
求根 – 重建的一元多项式使用标准的特征值或伴随矩阵方法求解，得到隐藏变量的所有候选值。
秩‑1 子矩阵检测 – 对每个候选值，实例化原始系数矩阵。作者定位一个在隐藏变量正确时应变为秩‑1 的子矩阵。基于最大公约数的测试用于区分真实的秩亏损和数值噪声。
通过克拉默法则回代 – 一旦识别出正确的子矩阵，使用克拉默法则解析地恢复其余未知量，避免任何矩阵求逆。

整个流程纯粹是数值计算（无符号代数），且可以离线预先计算一次，以生成轻量级的运行时求解器。

问题（例如，5‑point essential）	离线构建时间	运行时间（ms）	平均误差（像素）
5‑point essential（小）	~0.3 s	0.12	0.31
6‑point radial distortion	~0.9 s	0.27	0.45
8‑point homography（大）	~2.4 s	0.68	0.62

数值稳定性：在合成噪声水平（0–2 px）下，基于 FFT 的求解器保持的误差增长可与最佳 Gröbner‑basis 方法相媲美，且显著优于依赖符号展开的朴素 resultant 求解器。
小规模问题的运行时优势：对于未知数 ≤ 6 的问题，FFT‑based 方法比领先的 Gröbner‑basis 求解器快 2–4 倍，主要因为它在运行时避免了昂贵的矩阵约简。
可扩展性：虽然该方法的优势在非常大规模系统（≥ 10 个未知数）中会因行列式多项式的更高次数而减弱，但仍保持竞争力，且运行时间从未超过传统求解器。

实时 SLAM / AR: 许多 SLAM 前端需要以 > 30 Hz 的频率求解最小姿态问题。所提出的求解器可以以最少的代码改动嵌入现有流水线，并提供一种可预测、低延迟的 Gröbner‑basis 库替代方案。
嵌入式 / 移动设备: 无矩阵求逆的特性降低了浮点运算次数和内存带宽需求，这在资源受限的 CPU/GPU 上尤为有价值。
对噪声的鲁棒性: 基于 GCD 的子矩阵测试为开发者提供了内置的合理性检查，降低了在数据噪声大或含有异常值时出现灾难性失败的可能性。
易于集成: 由于离线构建只需一次性成本，开发者可以预先为一系列最小问题计算求解器，并以静态库形式发布，类似于现有的“自动生成”求解器（例如来自 OpenCV 或 COLMAP 工具包的）。

作者提出的未来研究方向包括将 FFT 插值与针对高次数问题的选择性符号化简相结合的混合方案，以及探索自适应采样策略，以进一步降低嵌入式平台上的运行时间。