schnellste Methode für über die schnellste Methode Faltung

Question

Jeder weiß, Berechnung für Faltung Berechnung? Leider ist die Matrix, mit der ich mich beschäftige sehr groß (500x500x200) und wenn ich convn in MATLAB verwende dauert es sehr lange (ich muss diese Berechnung in einer verschachtelten Schleife durchlaufen). Also habe ich Faltung mit FFT verwendet und es ist jetzt schneller. Aber ich suche immer noch nach einer schnelleren Methode. Irgendeine Idee?

Answer 1

Wenn Ihr Kernel ist zerlegbar, wird die größte Geschwindigkeit gewinnt, indem mehrere aufeinanderfolgende 1D Faltungen realisiert werden.

Steve Eddins von MathWorks beschreibt, wie die Vorteile der Assoziativität der Faltung nehmen Faltung zu beschleunigen, wenn der Kernel in einem MATLAB Kontext auf his blog trennbar ist. Für einen P-by-Q Kernel ist die rechnerische Vorteil der Durchführung zwei getrennte und aufeinanderfolgende Faltungen vs. 2D Faltungs PQ/(P+Q), die für einen 9x9-Kernel und ~ 11x für einen 15x15-Kernel 4,5x entspricht. EDIT: Eine interessante unwissentlich Demonstration dieser Unterschied wurde in this Q&A gegeben.

Um herauszufinden, ob der Kernel trennbar ist (d. H. Das äußere Produkt von zwei Vektoren) das Blog goes on to describe, wie Sie überprüfen, ob Ihr Kernel mit SVD trennbar ist und wie Sie die 1D-Kernel erhalten. Ihr Beispiel ist für einen 2D-Kernel. Für eine Lösung für N-dimensionale trennbare Faltung, überprüfen Sie this FEX submission.

---

Eine weitere Ressource wert ist this SIMD (SSE3/SSE4) implementation of 3D convolution by Intel den Hinweis auf, die sowohl source und presentation enthält. Der Code ist für 16-Bit-Ganzzahlen. Wenn Sie nicht zur GPU wechseln (z. B.), ist es wahrscheinlich schwierig, schneller zu werden als Intels Implementierungen, zu denen auch Intel MKL gehört. Es gibt ein Beispiel für eine 3D-Faltung (Float mit einfacher Genauigkeit) im unteren Bereich von this page of the MKL documentation (feste Verbindung, jetzt gespiegelt in https://stackoverflow.com/a/27074295/2778484).

Answer 2

könnten Sie versuchen, die Overlap-Add-Überlappungen speichern Methoden. Sie müssen Ihr Eingangssignal in kleinere Stücke zerlegen und dann eine der oben genannten Methoden anwenden.

Eine FFT ist sehr wahrscheinlich - und ich könnte falsch sein - die schnellste Methode, vor allem, wenn Sie in C integrierte Routinen in MATLAB oder eine Bibliothek ++ verwenden. Abgesehen davon sollte das Aufbrechen des Eingangssignals in kleinere Stücke eine gute Wette sein.

Answer 3

ich habe 2 Art und Weise fastconv

und 2 betther als 1

1- Gürteltier calc Sie Armadillo-Bibliothek für calcING conv mit diesem Code

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

2-Nutzung fftw verwenden können ans sigpack and armadillo library zum schnellen Convertieren auf diese Weise müssen Sie inft fft Ihres Codes im Konstruktor

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); 
}