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

Question

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

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



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



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

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

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

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

给定 : 值数组，表示多项式函数。

通缉 :多项式函数的最低点。

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

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

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

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

感谢您的帮助!

亲切的问候，
安德烈亚斯

Answer 1

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