Méthode la plus rapide pour le calcul de la convolution

Ce que quelqu'un sait à propos de la méthode la plus rapide pour le calcul de la convolution? Malheureusement, la matrice qui j'ai affaire avec est très grand (500x500x200) et si j'utilise convn dans MATLAB, il prend du temps (j'ai d'itérer ce calcul dans une boucle imbriquée). Donc, j'ai utilisé le produit de convolution avec la FFT et il est plus rapide maintenant. Mais, je suis toujours à la recherche d'une méthode plus rapide. Une idée?

CUFFT est assez bon, mais peut ne pas être en mesure de faire une matrice qui n'est pas la puissance de 2 alignés. Aussi vous avez besoin d'un matériel et un peu de savoir ce que vous faites.

OriginalL'auteur Nicole | 2013-12-12

  1. 15

    Si votre noyau est séparable, les plus grands gains de vitesse sera réalisé par la réalisation de plusieurs séquentielle 1D circonvolutions.

    Steve Eddins de MathWorks explique comment tirer parti de l'associativité de la convolution pour accélérer la convolution lorsque le noyau est séparable en MATLAB contexte sur son blog. Pour un P-by-Q noyau, le calcul de l'avantage de l'exécution de deux séquentielle et de circonvolutions vs 2D de convolution est PQ/(P+Q), ce qui correspond à 4,5 x pour une 9x9 noyau et ~11x pour une 15x15 noyau. MODIFIER: Une intéressante démonstration involontaire de cette différence a été donné dans cette Q&A.

    Pour savoir si le noyau est séparable (c'est à dire le produit extérieur de deux vecteurs) le blog pour décrire les comment vérifier si votre noyau est séparable avec SVD et comment obtenir les 1D noyaux. Leur exemple est un 2D noyau. Une solution de N-dimensions séparable de convolution, vérifiez cette FEX présentation.

    Une autre ressource est intéressant de souligner est cette SIMD (SSE3/SSE4) la mise en œuvre de la 3D convolution par Intel, qui comprend à la fois source et un présentation. Le code est de 16 bits entiers. À moins que vous vous déplacez sur GPU (par exemple cuFFT), il est sans doute difficile d'obtenir plus rapidement que l'Intel implémentations, qui comprend également Intel MKL. Il est un exemple de 3D de convolution (simple précision float) au bas de sur cette page de la documentation MKL (lien fixe, maintenant, en miroir dans https://stackoverflow.com/a/27074295/2778484).

    Juste un aparté intéressant, la fonction imfilter ne fait implicitement. Il faut un tableau 2d pour le noyau, mais va vérifier pour voir si elle est séparable avant d'appliquer le filtre. Aussi, comme déjà mentionné, si vous faites la circulaire circonvolutions FFT va être rapide.
    C'est un excellent point. j'ai remarqué cela avant comme la raison pour laquelle imfilter est plus rapide lorsqu'elle est appelée dans une boucle si vous essayez de filtrer une pile d'images en 2D chacun avec la même 2D noyau au lieu de donner la pile d'images, même si elle prend en charge le faire. S'il détecte des données 3D, il déclare que le noyau non-séparables, même si la 2D noyau est séparable (fonctionnalité ou un bug?).
    Malheureusement, ma matrice semble être de l'onu-separatable !! et ne peut pas utiliser cette fonction.
    Qu'est-ce que le noyau? La matrice de données ne doit pas être quelque chose de particulier, juste le noyau.
    +1 pour une complète et bien documentée de la réponse!

    OriginalL'auteur chappjc

  2. 2

    Vous pouvez essayer de le chevauchement-ajouter et overlap-save méthodes. Ils impliquent la rupture de votre signal d'entrée en petits morceaux, puis en utilisant l'une des méthodes ci-dessus.

    Une FFT est le plus probable - et j'ai peut-être tort - la méthode la plus rapide, surtout si vous êtes en utilisant des routines intégrées dans MATLAB ou une bibliothèque en C++. En dehors de cela, la rupture du signal d'entrée en morceaux plus petits que devrait être un bon pari.

    Depuis que je veux utiliser la convolution de la correspondance de modèle, je pense à la rupture de la matrice sera discutable !
    Si vous pouvez utiliser la boîte à outils de Traitement du Signal, fftfilt devrait être en mesure de faire le gros du travail pour vous. mathworks.de/de/help/signal/ref/fftfilt.html
    Mais comment je peux utiliser cette commande au lieu de convn dans matlab? Supposons que j'ai un = rand(500,500,100) et b = rand(20,20,20)
    Je suis désolé, je n'avait pas remarqué que vous voulez calculer en trois dimensions de la convolution. Je dois passer sur celui-là.

    OriginalL'auteur Sriram

  3. 0

    j'ai 2 façon de calc fastconv

    et 2 betther de 1

    1 - tatou
    vous pouvez utiliser tatou bibliothèque pour calcing conv avec ce code

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

    2-utilisation fftw sna sigpack et tatou bibliothèque pour calcing rapide conv de cette façon, vous devez init fft de votre code dans le constructeur

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

    OriginalL'auteur javad