不依赖矩阵求逆，用快速傅里叶插值解相机几何最小问题。
Solving Minimal Problems Without Matrix Inversion Using FFT-Based Interpolation
- 基于稀疏隐变量结式构造求解器，避免在线求逆。
- 通过FFT插值高效重建行列式多项式，数值稳定且速度更快。
- 适合小规模几何估计，对噪声鲁棒，可替代传统符号方法。
相机几何估计通常需解由多变量多项式方程构成的最小问题，传统基于Gröbner基或结式的方法因在线求逆导致计算困难。本文提出一种无需矩阵求逆的采样法，利用稀疏隐变量结式构建求解器。通过逆快速傅里叶变换插值，从采样值高效重构隐变量的行列式多项式，避免符号展开。求解该多项式得隐变量后，通过识别秩-1不足子矩阵并应用克莱姆法则恢复其余未知量。基于最大公因式准则确保噪声下子矩阵识别的鲁棒性。在多种最小问题上的实验表明，该方法具有强数值稳定性与竞争性运行时间，尤其适用于小规模问题，为传统符号求解器提供实用替代方案。
原文摘要 · Abstract (English)
Estimating camera geometry typically involves solving minimal problems formulated as systems of multivariate polynomial equations, which often pose computational challenges when using existing Gröbner-basis or resultant-based methods due to matrix inversion needed in the online solver. Here we propose a sampling-based, matrix inversion-free method that constructs the solvers using sparse hidden-variable resultants. The determinant polynomial in the hidden variable is efficiently reconstructed via inverse fast Fourier transform interpolation from sampled evaluations, avoiding symbolic expansion. Solving this polynomial yields the hidden variable, and the remaining unknowns are recovered by identifying rank-1 deficient submatrices and applying Cramer's rule. A greatest common divisor-based criterion ensures robust submatrix identification under noise. Experiments on diverse minimal problems demonstrate that the proposed solver achieves strong numerical stability and competitive runtime, particularly for small-scale problems, providing a practical alternative to traditional Gröbner-basis and resultant-based solvers.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。