SGM 视差子像素估计 - 如何？

Question

几周前，我实现了一个简单的块匹配立体算法，但结果很糟糕。所以我在互联网上搜索以找到更好的算法。在那里我找到了半全局匹配 (SGM)，由 Heiko Hirschmueller 出版。它获得了与处理时间相关的最佳结果之一。

我已经实现了该算法并获得了非常好的结果（与简单的块匹配相比），正如您在此处看到的：

我使用计算出的视差值将 2D 点重新投影到 3D，结果如下

在 SGM 结束时，我有一个数组，其中包含每个像素的汇总成本。视差相当于成本值最低的指标。

问题是，搜索最小值只会返回离散值。这导致点云中的单独层。换句话说：圆形表面被切割成许多层（见点云）。

Heiko 在他的论文中提到，通过将多项式函数拟合到成本数组中并将最低点作为视差，可以很容易地获得亚像素精度。

该问题不限于立体视觉，因此换句话说，任务如下：

• given：值数组，表示多项式函数。
• 想要：多项式函数的最低点。

我不知道该怎么做。我需要一个快速算法，因为我必须为图像中的每个像素运行此代码

例如：500x500 像素，每个成本 60-200 => 算法必须运行 15000000-50000000 次！！）。

我不需要实时解决方案！我当前的 SGM 实现（L2R 和 R2L 匹配，还没有 cuda 或多线程）需要大约 20 秒来处理 500x500 像素的图像；）。

我不要求图书馆！我尝试实现我自己的独立计算机视觉库 :)。

感谢您的帮助！

亲切的问候，安德烈亚斯

Answer 1

找到一般多项式中精确的最低点是一个难题，因为它相当于找到多项式导数的根。特别是，如果您的多项式是 6 次，则导数是五次多项式，已知它不能通过根式求解。因此，您需要：使用限制族来拟合函数，计算导数的根，例如 prod_i(x-ri)p(q) 的积分，其中 deg(p)<=4，或者使用迭代方法来查找近似最小值（牛顿法，梯度下降）。