标签: convolution

我必须在许多图像的每一行上应用卷积滤镜.经典是1024x1024像素的360度图像.在我的用例中,它是720像素560x600像素.

问题是我的代码比文章中广告的要慢得多.

我实施了天真的卷积,需要2分30秒.然后我使用fftw切换到FFT.我使用了复数2复数,在每个变换中过滤两行.我现在20多岁了.

事情是,文章广告大约10s甚至更少的经典条件.所以我想问一下这里的专家是否有更快的方法来计算卷积.

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

也许我浪费时间复制数据.使用真正的2实数变换,我不必将数据复制到complexe值中.但无论如何我必须用0填充.

编辑:请参阅下面的答案,了解进度反馈以及解决此问题的更多信息.

问题(精确重新制定):

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

我需要卷积两个一维信号,一个平均有500个点(这个是Hanning窗口函数),另一个是125000.每次运行,我需要应用三次卷积运算.我已经有一个基于scipy文档运行的实现.如果你愿意,你可以在这里看到代码(Delphi代码提前):

function Convolve(const signal_1, signal_2 : ExtArray) : ExtArray;
var
  capital_k : Integer;
  capital_m : Integer;
  smallest : Integer;
  y : ExtArray;
  n : Integer;
  k : Integer;
  lower, upper : Integer;
begin
  capital_k := Length(signal_1) + Length(signal_2) - 1;
  capital_m := Math.Max(Length(signal_1), Length(signal_2));
  smallest := Math.Min(Length(signal_1), Length(signal_2));
  SetLength(y, capital_k);
  for n := 0 to Length(y) - 1 do begin
    y[n] := 0;
    lower := Math.Max(n - capital_m, 0);
    upper := Math.Min(n, capital_k);
    for k := lower to upper do …

我正在做一些关于在Python中卷积图像的事情,为了速度,我选择了opencv 2.4.9.

Opencv提供了一种名为filter2D的方法来执行此操作,这里是它的文档:http://docs.opencv.org/modules/imgproc/doc/filtering.html？highlightlight = filter2d#filter2d

在文档中,它说:

用内核卷积图像.

但我有疑问(由别的东西引起)所以我做了一些实验:

首先,我做一个正常的3x3矩阵一个使用numpy的是:

  [[ 1.,  5.,  0.], 
   [ 7.,  2.,  9.], 
   [ 2.,  3.,  4.]]

Run Code Online (Sandbox Code Playgroud)

然后,我将2x2矩阵b作为内核:

>>> b

  [[ 1.,  2.],
   [ 3.,  4.]]

Run Code Online (Sandbox Code Playgroud)

最后,为了清楚地看到卷积和相关之间的差异,将b旋转180度,b将如下所示:

  [[ 4.,  3.],
   [ 2.,  1.]]

Run Code Online (Sandbox Code Playgroud)

现在,所有的前期工作都已完成.我们可以开始实验了.

步骤1.使用scipy.ndimage.convolve:ndconv = ndimage.convolve(a, b, mode = 'constant')和ndconv是:

  [[ 35.,  33.,  18.],
   [ 41.,  45.,  44.],
   [ 17.,  24., …

Run Code Online (Sandbox Code Playgroud)

我正在使用 Radix-2 Cooley-Tukey FFT/FFT-inverse 实现卷积，我的输出是正确的，但在完成时发生了偏移。

我的解决方案是将输入大小和内核大小都零填充到 2^m 以获得最小可能的 m，使用 FFT 转换输入和内核，然后将两个元素相乘并使用 FFT 逆将结果转换回。

作为由此产生的问题的示例：

 0  1  2  3  0  0  0  0
 4  5  6  7  0  0  0  0
 8  9 10 11  0  0  0  0
12 13 14 15  0  0  0  0
 0  0  0  0  0  0  0  0
 0  0  0  0  0  0  0  0
 0  0  0  0  0  0  0  0
 0  0  0  0  0  0  0  0

带有身份核

0 …

我正在尝试用 python 编写一个脚本来检测任何给定输入音频文件中是否存在简单的警报声音。我解释了我的解决方案，如果有人可以确认它是一个好的解决方案，我将不胜感激。任何其他可以在 python 中实现的解决方案都是值得赞赏的。

我这样做的方法是通过计算两个信号的 FFT（一个是相反的）来计算两个信号的互相关，然后将它们相乘，然后计算结果的 IFFT。然后找到结果的峰值并将其与预先指定的阈值进行比较，以确定是否检测到警报声音。

这是我的代码：

import scipy.fftpack as fftpack
def similarity(template, test):
    corr = fftpack.irfft(fftpack.rfft(test , 2 * test.size ) *    \
           fftpack.rfft(template[:-1] , 2 * template.size ))           

    return max(abs(corr))

template 和 test 是信号数据的一维列表。rfft 的第二个参数用于填充零以计算 FFT。但是，我不确定应该添加多少个零。另外，在应用 FFT 之前我应该​​对给定信号进行归一化吗？例如，根据模板信号的峰值对其进行归一化？

我正在为我的项目制作一个卷积滤波器，并且我设法将其制作为任何大小的矩阵，但随着它变得更大，我注意到并非所有位都发生了变化。以下是显示问题的图片：

第一张是原图 滤镜：模糊 9x9

过滤器：边缘检测 9x9：

正如您所看到的，有一个小条纹从未改变，并且随着矩阵变大，条纹也会变大（在 3x3 中它不可见）

我的卷积矩阵类：

    public class ConvMatrix
{
    public int Factor = 1;
    public int Height, Width;
    public int Offset = 0;
    public int[,] Arr;

    //later I assign functions to set these variables
    ...
}

过滤功能：

    Bitmap Conv3x3(Bitmap b, ConvMatrix m)
{
    if (0 == m.Factor)
        return b;

    Bitmap bSrc = (Bitmap)b.Clone();
    BitmapData bmData = b.LockBits(new Rectangle(0, 0, b.Width, b.Height),
                        ImageLockMode.ReadWrite,
                        PixelFormat.Format24bppRgb);
    BitmapData bmSrc = bSrc.LockBits(new Rectangle(0, 0, bSrc.Width, bSrc.Height),
                       ImageLockMode.ReadWrite,
                       PixelFormat.Format24bppRgb);
    int stride …

我已经训练了一个卷积神经网络(CNN),其中包含我在二进制文件中的以下数据(标签,文件名,数据(像素)):

[array([2, 1, 0, 2, 1, 0, 2, 1, 0, 2, 1, 0, 2, 1, 0, 2, 1, 0, 2, 1, 0, 2, 1,
           0, 2, 1, 0, 2, 1, 0]), array(['10_c.jpg', '10_m.jpg', '10_n.jpg', '1_c.jpg',
           '1_m.jpg', '1_n.jpg', '2_c.jpg', '2_m.jpg',
           '2_n.jpg', '3_c.jpg', '3_m.jpg', '3_n.jpg',
           '4_c.jpg', '4_m.jpg', '4_n.jpg', '5_c.jpg',
           '5_m.jpg', '5_n.jpg', '6_c.jpg', '6_m.jpg',
           '6_n.jpg', '7_c.jpg', '7_m.jpg', '7_n.jpg',
           '8_c.jpg', '8_m.jpg', '8_n.jpg', '9_c.jpg',
           '9_m.jpg', '9_n.jpg'], 
          dtype='<U15'), array([[255, 252, 255, ..., 255, 255, 255],
           [136, 137, 138, ..., 114, 110, 111],
           [200, 200, 199, ..., …

我想用depthwise_conv2d从Tensorflow。据我所知，它为每个通道执行常规的2D卷积，每个卷积都有depth_multiplier许多功能。

然后，如果depth_multiplier = 1，我应该期望输入通道的数量与输出通道的数量相同。但是为什么我可以有256个输入通道和512个输出通道？额外渠道从何而来？

我在我的图像和卷​​积核周围使用零填充，将它们转换为傅立叶域，然后将它们反转回来以获得卷积图像，请参见下面的代码。然而，结果是错误的。我期待一个模糊的图像，但输出是四个移位的四分之一。为什么输出错误，我该如何修复代码？

输入图像：

卷积结果：

from PIL import Image,ImageDraw,ImageOps,ImageFilter
import numpy as np 
from scipy import fftpack
from copy import deepcopy
import imageio
## STEP 1 ##
im1=Image.open("pika.jpeg")
im1=ImageOps.grayscale(im1)
im1.show()
print("s",im1.size)
## working on this image array
im_W=np.array(im1).T
print("before",im_W.shape)
if(im_W.shape[0]%2==0):
im_W=np.pad(im_W, ((1,0),(0,0)), 'constant')
if(im_W.shape[1]%2==0):
im_W=np.pad(im_W, ((0,0),(1,0)), 'constant')
print("after",im_W.shape)
Boxblur=np.array([[1/9,1/9,1/9],[1/9,1/9,1/9],[1/9,1/9,1/9]])
dim=Boxblur.shape[0]

##padding before frequency domain multipication
pad_size=(Boxblur.shape[0]-1)/2
pad_size=int(pad_size)
##padded the image(starts here)

p_im=np.pad(im_W, ((pad_size,pad_size),(pad_size,pad_size)), 'constant')
t_b=(p_im.shape[0]-dim)/2
l_r=(p_im.shape[1]-dim)/2
t_b=int(t_b)
l_r=int(l_r)

##padded the image(ends here)

## padded the kernel(starts here)
k_im=np.pad(Boxblur, ((t_b,t_b),(l_r,l_r)), 'constant')
print("hjhj",k_im)
print("kernel",k_im.shape) …

问题：给定一个已排序的数组 A，找出 A 中元素的所有可能差异，其中每个元素都是 [1, ..., n] 范围内的整数。此外，您可以假设没有重复项。所以数组的最大大小将 <= n。

注意：由于上述限制，可能的总差异将在 [1, ..., n-1] 的范围内。

示例（对于 N=12）：

输入：1、6、10、12
输出：2、4、5、6、9、11

问题与此类似，除了 n 是否。该问题中的元素数量，而不是元素的上限。

在同一个问题中也有一个答案，这个：https : //stackoverflow.com/a/8455336/2109808 这家伙声称它确实可以使用 fft 和自卷积在 O(nlogn) 中完成，但我不明白它，当我在在线卷积计算器上尝试它时，它似乎也不正确（就像这个）。

那么，有谁知道如何在 O(nlogn) 中实现这一点？

先感谢您 ：）