问题标签 [convolution]

I'm storing many files of various lengths into a block-oriented medium (fixed-size e.g. 1024 bytes). When reading back the file, each block will either be missing or correct (no bit errors or the like). The missing blocks are random, and there's not necessarily any sequence to the missing blocks. I'd like to be able to reassemble the entire file, as long as the number of missing blocks is below some threshold, which probably varies with the encoding scheme.

Most of the literature I've seen deals with sequences of bit errors in a stream of data, so that wouldn't seem to apply.

A simple approach is to take N blocks at a time, then store a block containing the XOR of the N blocks. If one of the N blocks is missing but the check block is not, then the missing block can be reconstructed.

Are there error-correcting schemes which are well suited to this problem? Links to literature or code are appreciated.

我想将离散信号与离散滤波器进行卷积。信号和滤波器是 F# 中的浮点序列。

我能弄清楚如何做到这一点的唯一方法是使用两个嵌套的 for 循环和一个可变数组来存储结果，但感觉不是很实用。

以下是我将如何做到这一点：

I'm porting a library of image manipulation routines into C from Java and I'm getting some very small differences when I compare the results. Is it reasonable that these differences are in the different languages' handling of float values or do I still have work to do!

The routine is Convolution with a 3 x 3 kernel, it's operated on a bitmap represented by a linear array of pixels, a width and a depth. You need not understand this code exactly to answer my question, it's just here for reference.

Java code;

Clamp restricts the bands' values to the range [0..255] and Color.red is equivalent to (pixel & 0x00FF0000) >> 16.

The C code goes like this;

It's a little different xOffsets provides the xOffset for the kernel element for example.

The main point is that my results are out by at most one bit. The following are pixel values;

Do you believe this is a problem with my code or rather a difference in the language?

Kind regards,

Gav

我正在尝试评估一些基本图像过滤算法的复杂性。我想知道你是否可以验证这个理论；

对于像 Inverse 这样的基本逐像素过滤器，操作的数量随着输入的大小（以像素为单位）线性增长，并且

令 S = 图像边长令 M = # 像素输入

逆序为 O(M) 或 O(S^2)。

另一方面，卷积滤波器有一个参数 R，它决定了在为每个滤波器建立下一个像素值时要卷积的邻域的大小。

设 R = 卷积滤波器的半径

卷积顺序为 O(M*((R+R*2)^2) = O(M*(4R^2) = O(MR^2)

或者我应该让 N = 卷积滤波器（邻域）的大小（以像素为单位）？

O(M*(N)) = O(MN)

最终，卷积滤波器线性依赖于像素数和邻域中像素数的乘积。

如果您有任何指向已记录该文件的论文的链接，我们将不胜感激。

亲切的问候，

加文

我将不得不在 Python 中实现两个函数的卷积，但 SciPy/Numpy 似乎只有两个数组卷积的函数。

在我尝试使用卷积的正则积分表达式来实现这一点之前，我想问一下是否有人知道执行这些操作的已经可用的模块。

如果做不到这一点，SciPy 提供的几种集成中哪一种最适合这个？

谢谢！

这不是一个“编程”问题。但我确信这是在这个社区中广为人知和理解的东西。

我有一个图像 x 和一个小得多的图像 y，我需要通过乘以它们的 FFT 来对两者进行卷积。但由于它们的大小不同，我不知道如何进行频域乘法。

我采用 x 的（二维）FFT（它是一个维度为 4096 x 4096 的整数矩阵），它给出了频域表示 X（它是一个复数矩阵，我认为它的维度是 2048 x 2048 ）。

同样，我采用（y 的二维 FFT（它是一个 64 x 64 维的整数矩阵），它给出了频域表示 Y（它也是一个复数矩阵，我认为它的维数是 32 × 32)。

我在 Numerical Recipes 中使用了fourn 函数，所以我的输入矩阵 x 和 y 必须折叠成一维数组，这些数组被它们的离散傅里叶变换 X 和 Y 所取代。关键是即使这是一个图像的二维问题，我正在处理一维数组。

如果我试图对两个尺寸完全相同的图像 x 和 y 进行卷积。这一切都非常简单：

但是如果 X 和 Y 的长度不同，我该如何做乘法呢？

一种可能性是将 y 填充为与 x 具有相同的尺寸。但这似乎非常低效。另一种可能性是填充 Y 使其具有与 X 相同的尺寸。但我不知道这在频率空间中意味着什么。

这是问这个问题的另一种方式：如果我想使用 FFT 对两个尺寸非常不同的图像进行卷积，以便可以对其光谱进行乘法（频域表示），我该如何进行乘法运算？

谢谢，

〜迈克尔。

我必须对许多图像的每一行应用卷积过滤器。经典的是 1024x1024 像素的 360 幅图像。在我的用例中，它是 720 张 560x600 像素的图像。

问题是我的代码比文章中宣传的要慢得多。

我已经实现了朴素卷积，它需要 2m 30s。然后我使用 fftw 切换到 FFT。我使用了 complex 2 complex，在每个转换中过滤两行。我现在20多岁。

问题是文章在 10 多岁左右做广告，对于经典条件甚至更少。所以我想问问这里的专家是否有更快的方法来计算卷积。

数值方法建议避免在 dft 中进行排序并相应地调整频域滤波器功能。但是没有代码示例如何做到这一点。

也许我会浪费时间复制数据。使用 real 2 real 转换，我不必将数据复制到复杂的值中。但无论如何我必须用 0 填充。

编辑：请参阅下面我自己的答案以获取进度反馈和有关解决此问题的更多信息。

问题（精确的重新表述）：

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

我知道我的问题并不是真正的编程问题，而是出于编程需求。有没有人碰巧知道对角线运动模糊的卷积矩阵。3x3、4x4 或 5x5 都很好。

谢谢，

我正在寻找一些实现 3d 卷积的源代码。理想情况下，我需要 C++ 代码或 CUDA 代码。如果有人能指出一个好的和快速的实现，我将不胜感激:-)

干杯

我想使用 python 提高卷积的性能，并希望对如何最好地提高性能有所了解。

我目前正在使用 scipy 执行卷积，使用的代码有点像下面的代码片段：

我正在处理图像数据，使用灰度（0 到 255 之间的整数值），我目前每个卷积得到大约四分之一秒。我的想法是执行以下操作之一：

使用 corepy，最好进行一些优化 使用 icc 和 ikml 重新编译 numpy。使用 python-cuda。

我想知道是否有人对这些方法有任何经验（典型的收益是什么，是否值得花时间），或者是否有人知道更好的库来使用 Numpy 执行卷积。

谢谢！

编辑：

通过使用 Numpy 在 C 中重写 python 循环，加速大约 10 倍。