计算卷积最快方法

Question

我必须在许多图像的各行施加的卷积滤波器。经典的是1024×1024像素360倍的图像。在我的使用情况下，它是720个图像560x600像素。

问题是，我的代码比是在文章标榜要慢得多。

我已经实现了幼稚卷积，并且它需要2米30秒。然后我切换使用FFTW FFT的。我用复杂的2复合物，在每个变换滤波两行。我现在20岁左右。

的事情是，文章围绕广告10秒，甚至经典的条件较少。 所以我想在这里请教专家是否有可能来计算卷积更快的方法。

数值食谱建议避免在DFT进行排序并相应地调整频域滤波器的功能。但没有代码示例如何可以这样做。

也许我失去复制数据的时间。与真正的2实变我也不会将数据复制到配合物值。但我要以0垫反正。

编辑：看我自己的答案下面的进度反馈和进一步的信息，解决这一问题。

。

问（精确再形成）：

我正在寻找算法或一段代码到一个非常快速卷积应用于离散的非周期函数（512至2048的值）。显然，离散傅立叶变换是要走的路。虽然，我想避免数据复制和转化为复杂的，并且避免了蝴蝶重新排序。

Answer 1

FFT是用于卷积的信号已知最快的技术，并且FFTW可用于计算FFT最快自由库。

让你获得最大性能的关键（硬件之外......的GPU是一个很好的建议），将是你的垫信号二的幂。当使用FFTW使用“病人”创建计划，以获得最佳性能时的设置。这是极不可能的，你将手工擀比FFTW提供（忘了N.R.）更快的实现。另外，请务必使用正维FFT和真实版的不是复杂的版本是;如果可以只使用单个（浮点）的精确度。

如果FFTW没有削减它适合你，那么我想看看英特尔的（很实惠）IPP库。该已调谐的手FFT对已与各种位深度的图像优化的英特尔处理器。

保罗结果 CenterSpace 软件

Answer 2

您可能需要添加的图像处理作为标签。

但是，本文可能会感兴趣，尤指在假设的图像是功率或2还可以看到，他们优化FFT。我希望你是在寻找做一些假设，然后将物品优化方程的。

http://www.gamasutra.com/view/feature/3993 /sponsored_feature_implementation_.php

如果你想走得快，你可能想利用GPU来实际做的工作。

这本书可能对你有所帮助，如果你用GPU去： http://www.springerlink.com/content/kd6qm361pq8mmlx2/

Answer 3

这答案是收集关于这一问题的进展报告的反馈意见。

修改10月11日：

我测量并不反映FFT的有效时间的执行时间。我发现我的程序结束时，该CPU仍在忙于在系统时间高达42％，持续10秒。当我等到CPU是回到0％，重新启动我的节目之前，我再拿到这是从GPU处理15.35s执行时间。我得到同样的时间，如果我注释掉FFT滤波。

所以FFT实际上是在目前快那么GPU，并简单地通过一个竞争的系统任务的阻碍。我还不知道这个系统的任务是什么。我怀疑这从一个巨大的堆块，我将其写入磁盘之前复制的处理结果的分配结果。对于输入数据I使用的存储器映射。

现在我会改变我的代码来获得的FFT处理时间的精确测量。使其更快还是实际上因为有空间通过管道数据处理转移到最优化例如像的GPU处理。