霍夫变换的累加器填充

Question

我写了一段需要优化的代码。只是想与社区核实一下该代码是否确实是最佳的。它填充霍夫变换的累加器。实际上，我只是复制粘贴了 OpenCV 库中的大部分代码。谢谢！

---

int i,j,n,index;
for (i = 0;i<numrows;i++)
{
    for (j = 0;j<numcols;j++)
    {
            if (img[i*numcols + j] == 100)
        {
            for (n = 300;n<600;n++)
            {   
                index = cvRound(j*tabCos[n] + i * tabSin[n]) + (numrho-1)/2;
                accum[(n+1) * (numrho+2) + index+1]++;
            }
        }
    }
}

Answer 1

我也模糊地附加了一段代码，其中有一个大型且重复的霍夫变换。这部分代码的维护者一直在尝试使用稀疏数组（实际上是一个 C++ std::map ，如果我理解他的演示正确的话，键在单元格索引上）作为累加器，并取得了一些成功。

我认为加速与缓存局部性问题有关，并且它当然取决于数据的稀疏性。

---

更新：上面引用的软件旨在为许多粒子物理实验提供服务，但最初用于试验台项目（即小规模）。当我们开始认真做更大的项目并开始为它们做蒙特卡洛时，即使对于稀疏矩阵，霍夫变换也再次成为了一个瓶颈。

到目前为止，我们还没有解决方案，但一位同事发现 Gandalf 其中包括 "快速霍夫变换"，它似乎以类似四叉树的方式评估变换（在 2D 中，大概您在 3D 中使用八叉树）来减少工作顺序。我们可能会对此进行实验。

进一步更新：一位同事最终在我们的代码中实现了渐进式概率霍夫变换，这似乎是我们目前最快的版本。如果您不需要将每个点分配给一条线，则效果最好。

Answer 2

不，不是。通过简单的指针算术来替换尽可能多的 [] 用法，以迭代有问题的数组。将不变表达式抽象为局部变量。

但是，第一个问题是，您的分析器是否显示此代码是整个应用程序上下文中的瓶颈。如果不是，为什么还要进行微优化呢？

编辑：循环微优化 - 更喜欢第二个，因为不需要数组索引（乘与加）

int ints[100];
int i;
int *pi;

for (i = 0; i < 100; ++i)
{
  printf("%d", ints[i]);
}

for (pi = ints; pi < ints + 100; ++pi)
{
  printf("%d", *pi);
}

Answer 3

根据您的应用程序，有多种方法可以优化霍夫变换，而摆弄低级代码可能是最后一种方法。
我将从随机 HT 或多分辨率 HT 开始，然后采用混合方法合并。
我认为最好先优化算法。最后一步是使用 CAD 内存等硬件优化。