快速計算卷積的方法

有人知道計算卷積的最快方法嗎？不幸的是，我處理的矩陣非常大（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

快速計算卷積的方法

回答

相關問題