快速计算卷积的方法

有人知道计算卷积的最快方法吗？不幸的是，我处理的矩阵非常大（500x500x200），如果我在MATLAB中使用convn需要很长时间（我必须在嵌套循环中迭代该计算）。所以，我用FFT进行卷积运算，现在速度更快。但是，我仍然在寻找更快的方法。任何想法？快速计算卷积的方法

来源

2013-12-12 Nicole

CUFFT很不错，但可能无法做一个矩阵不是2的对齐。你也需要硬件，并且知道你在做什么。 – IdeaHat

如果你的内核是可分离的，最大的速度增益将通过执行多个连续的1D卷积来实现。

MathWorks的Steve Eddins描述了如何利用卷积的相关性来加速卷积，当内核在MATLAB上下文中可分离时，可以使用his blog。对于P-by-Q内核，执行两个分离和顺序卷积与二维卷积的计算优势是PQ/(P+Q)，其对应于9x9内核的4.5x和对于15x15内核的约11x。编辑：在this Q&A中给出了这种差异的有趣的不知情的证明。

如何确定内核是否可分离（即两个向量的外积）博客goes on to describe如何检查内核是否可与SVD分离以及如何获取1D内核。他们的例子是2D内核。对于N维可分离卷积的解决方案，请检查this FEX submission。

另一个资源值得指出的是this SIMD (SSE3/SSE4) implementation of 3D convolution by Intel，其包括source和presentation。该代码是16位整数。除非您转移到GPU（例如cuFFT），否则它可能很难比英特尔的实施更快，其中还包括Intel MKL。在this page of the MKL documentation（链接固定，现在镜像在https://stackoverflow.com/a/27074295/2778484）底部有一个3D卷积（单精度浮动）的例子。

来源

2013-12-12 23:01:03 chappjc

就像一个有趣的一边，函数'imfilter'实际上隐含地这样做。它需要一个2d数组作为内核，但会在应用过滤器之前检查它是否可分离。另外，如前所述，如果您正在进行循环卷积，FFT也会很快。 – Justin

@jucestain这是一个很好的观点。 [我之前已经注意到了这一点]（http://stackoverflow.com/a/19284313/2778484），因为如果您试图过滤一堆二维图像，并在循环中调用'imfilter'，同样的2D内核，而不是给它的图像堆栈，即使它支持这样做。如果它检测到3D数据，即使2D内核可分离（功能或错误？），它也会声明内核不可分离。 – chappjc

不幸的是我的矩阵似乎是不可分割的！并且不能使用该功能。 – Nicole

您可以尝试重叠添加和重叠保存方法。它们涉及将输入信号分解为更小的块，然后使用上述任一方法。

FFT最有可能 - 而且我可能是错的 - 最快的方法，特别是如果您在MATLAB或C++库中使用内置例程。除此之外，将输入信号分成更小的块应该是一个不错的选择。

来源

2013-12-12 21:34:58 Sriram

因为我想使用卷积进行模式匹配，所以我认为分解矩阵是有问题的！ – Nicole

@Nicole如果你可以使用信号处理工具箱，'fftfilt'应该能够为你做繁重的工作。 http://www.mathworks.de/de/help/signal/ref/fftfilt.html – blackbird

@blackbird：但我如何使用该命令，而不是在matlab convn？假设我有a = rand（500,500,100）和b = rand（20,20,20） – Nicole

我有2个的方式来calc下fastconv

和2 betther大于1个

1-犰狳可以使用犰狳库与此代码calcing CONV

cx_vec signal(1024,fill::randn); 
cx_vec code(300,fill::randn); 
cx_vec ans = conv(signal,code);

2使用FFTW ans sigpack和armadillo库以这种方式获取快速转储，您必须在构造函数中初始化fft代码

FastConvolution::FastConvolution(cx_vec inpCode) 
{ 
    filterCode = inpCode; 
    fft_w = NULL; 
} 


cx_vec FastConvolution::filter(cx_vec inpData) 
{ 
int length = inpData.size()+filterCode.size(); 
    if((length & (length - 1)) == 0) 
    { 

    } 
    else 
    { 
     length = pow(2 , (int)log2(length) + 1); 
    } 
    if(length != fftCode.size()) 
     initCode(length); 

    static cx_vec zeroPadedData; 
    if(length!= zeroPadedData.size()) 
    { 
     zeroPadedData.resize(length); 
    } 
    zeroPadedData.fill(0); 
    zeroPadedData.subvec(0,inpData.size()-1) = inpData; 


    cx_vec fftSignal = fft_w->fft_cx(zeroPadedData); 
    cx_vec mullAns = fftSignal % fftCode; 
    cx_vec ans = fft_w->ifft_cx(mullAns); 
    return ans.subvec(filterCode.size(),inpData.size()+filterCode.size()-1); 
} 

void FastConvolution::initCode(int length) 
{ 
    if(fft_w != NULL) 
    { 
     delete fft_w; 
    } 
    fft_w = new sp::FFTW(length,FFTW_ESTIMATE); 
    cx_vec conjCode(length,fill::zeros); 
    fftCode.resize(length); 
    for(int i = 0; i < filterCode.size();i++) 
    { 
     conjCode.at(i) = filterCode.at(filterCode.size() - i - 1); 
    } 
    conjCode = conj(conjCode); 
    fftCode = fft_w->fft_cx(conjCode); 
}

来源

2017-10-18 06:38:06 javad

快速计算卷积的方法

回答

相关问题