Schnellste Methode für die Berechnung der Faltung

Jeder weiß, über die Schnellste Methode für die Berechnung der Faltung? Leider ist die matrix, die ich zu tun habe, ist sehr groß (500x500x200) und wenn ich convn in MATLAB, es dauert eine lange Zeit (ich wiederhole diese Berechnung in einer verschachtelten Schleife). So, ich verwendet Faltung mit FFT und es ist jetzt schneller. Aber, ich bin noch auf der Suche nach einer schnelleren Methode. Irgendeine Idee?

  • CUFFT ist ziemlich gut, aber möglicherweise nicht in der Lage zu tun, eine matrix, die nicht Potenz von 2 ausgerichtet. Auch müssen Sie die hardware und ein bisschen wissen, was Sie tun.
InformationsquelleAutor Nicole | 2013-12-12
  1. 16

    Wenn dein kernel ist teilbar, die größte Geschwindigkeit, die Gewinne werden realisiert durch die Durchführung mehrerer sequenzieller 1D-Faltungen.

    Steve Eddins von MathWorks beschreibt, wie man den Vorteil der Assoziativität der Faltung zu beschleunigen, convolution, wenn der kernel ist teilbar in eine MATLAB-Kontext auf in seinem blog. Für eine P-by-Q kernel, der rechnerische Vorteil, die mindestens zwei separate und sequentielle Faltung vs. 2D-Faltung ist PQ/(P+Q), das entspricht 4,5 x für einen kernel der Größe 9x9 und ~11x für ein 15x15 kernel. BEARBEITEN: Eine interessante geplante demonstration dieser Unterschied war in dieses Q&A.

    Herauszufinden, ob der kernel ist teilbar (d.h. das äußere Produkt zweier Vektoren) der blog geht zu beschreiben, wie Sie überprüfen, ob Ihr kernel ist trennbar mit SVD und wie bekommt man die 1D Kernel. Ihr Beispiel ist für ein 2D-kernel. Eine Lösung für N-dimensionale separierbare Faltung, überprüfen dieser FEX Vorlage.

    Andere Ressource hinzuweisen ist diese SIMD (SSE3/SSE4) Umsetzung von 3D-Faltung von Intel, die sowohl Quelle und ein Präsentation. Der code für 16-bit-Integer. Es sei denn, Sie bewegen sich auf GPU (z.B. cuFFT), ist es wahrscheinlich schwer zu bekommen, schneller als der Intel-Implementierungen, die auch Intel MKL. Es ist ein Beispiel von 3D-Faltung (single-precision-float) an der Unterseite der diese Seite von der MKL Dokumentation (link repariert, jetzt gespiegelt in https://stackoverflow.com/a/27074295/2778484).

    • Gerade als interessante beiseite, die Funktion imfilter tatsächlich tut dies implizit. Es dauert ein 2d-array für den kernel, aber wird überprüfen, um zu sehen, wenn es separierbar ist, bevor Sie den filter anwenden. Auch, wie bereits erwähnt, wenn Sie dabei kreisförmige Windungen FFT wird schnell als gut.
    • Das ist ein sehr guter Punkt. ich habe darauf hingewiesen, diesen vor dem wie der Grund, warum imfilter ist schneller, wenn in einer Schleife aufgerufen, wenn Sie versuchen, Sie zu filter einen Stapel von 2D-Bildern mit jeweils dem gleichen 2D-kernel anstatt es im Stapel der Bilder, obwohl es unterstützt, das zu tun. Wenn er erkennt, 3D-Daten, erklärt er den kernel nicht trennbar, auch wenn die 2D-kernel ist teilbar (feature oder bug?).
    • Leider hat meine matrix zu sein scheint, un-separatable !! und kann nicht funktioniert.
    • Was ist der kernel? Die Daten-matrix nicht alles in allem, nur den kernel.
    • +1 für eine so Gründliche und gut dokumentierte Antwort!
    InformationsquelleAutor chappjc
  2. 2

    Könnten Sie versuchen, die overlap-add und overlap-save-Verfahren. Sie beinhalten das Aufbrechen Ihrer input-signal in kleinere Stücke und dann mit den oben genannten Methoden.

    Einer FFT ist wahrscheinlich - und ich könnte falsch sein - die Schnellste Methode, vor allem wenn Sie mit built-in-Routinen in MATLAB oder einer library in C++. Abgesehen davon, breaking the input signal in kleinere Stücke sollte eine gute Wette.

    • Da möchte ich convolution "pattern-matching", ich denke, dass der Abbau der matrix wird ist fraglich !
    • Wenn Sie mit der Signal Processing Toolbox, fftfilt sollte in der Lage sein zu tun, die schweres heben für Sie. mathworks.de/de/help/signal/ref/fftfilt.html
    • Aber wie kann ich die Verwendung dieses Befehls anstelle von convn in matlab? Angenommen ich habe a = rand(500,500,100) und b = rand(20,20,20)
    • Tut mir Leid, ich konnte nicht feststellen, dass Sie berechnen möchten drei-dimensionale Faltung. Ich pass auf, dass man.
    InformationsquelleAutor Sriram
  3. 0

    habe ich 2 Weg zu calc fastconv

    und 2 betther als 1

    1 - armadillo
    Sie können 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-fftw ans sigpack und armadillo-Bibliothek für calcing schnell conv auf diese Weise müssen Sie die init-fft des 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);
}
    InformationsquelleAutor javad
Schreibe einen Kommentar