Méthode la plus rapide pour calculer la convolution

Question

J'ai pour appliquer un filtre de convolution sur chaque ligne de nombreuses images.Le classique est de 360 images de 1024x1024 pixels.Dans mon cas d'utilisation, il est de 720 images 560x600 pixels.

Le problème est que mon code est beaucoup plus lent que ce qui est annoncé dans les articles.

J'ai mis en œuvre la naïveté de convolution, et il faut 2m de 30 ans.J'ai ensuite passé à la FFT en utilisant fftw.J'ai utilisé le complexe 2 complexe, filtrage de deux lignes de chaque transformation.Je suis maintenant autour de 20 ans.

Le truc, c'est que les articles de la publicité autour de 10s et encore moins pour les classiques condition.Donc, je voudrais demander aux experts ici si il pourrait y avoir un moyen plus rapide pour calculer le produit de convolution.

Numérique recettes suggèrent d'éviter le tri fait dans la dft et d'adapter le domaine de fréquence du filtre de fonction en conséquence.Mais il n'y a pas de code d'exemple de la manière dont cela pourrait être fait.

Peut-être que je perds du temps dans la copie de données.Avec real 2 real transformer je n'aurais pas à copier les données dans le complexe de valeurs.Mais je dois pad avec 0 de toute façon.

EDIT:voir ma propre réponse ci-dessous pour les progrès de la rétroaction et de plus amples informations sur la résolution de ce problème.

Question (précis de reformulation):

Je suis à la recherche d'un algorithme ou d'un morceau de code à appliquer une très rapide de convolution d'une discrète non la fonction périodique (512 à 2048 valeurs).Apparemment, le temps discret transformée de Fourier est le chemin à parcourir.Cependant, je voudrais éviter de copie des données et à la conversion complexe, et d'éviter le papillon de réorganisation.

Answer 1

La FFT est la manière la plus rapide de la méthode de convolution des signaux, et FFTW est le plus rapide gratuit disponibles de la bibliothèque pour le calcul de la FFT.

La clé pour vous d'obtenir le maximum de performance (à l'extérieur du matériel ...le GPU est une bonne suggestion) seront à votre pad signaux à une puissance de deux.Lors de l'utilisation de FFTW utiliser le "patient" paramètre lors de la création de votre plan pour obtenir les meilleures performances.Il est très peu probable que vous aurez la main-rouleau de mettre en œuvre plus rapidement que ce que FFTW offre (oublier N. R.).Assurez-vous également d'utiliser la Vraie version de la FFT 1D et pas le Complexe de la version;et ne l'utiliser seul (à virgule flottante) précision si vous le pouvez.

Si FFTW est pas de coupe c'est pour vous, alors je regarde Intel (très abordable) IPP de la bibliothèque.Le fait d'avoir part à l'écoute de la FFT pour les processeurs Intel qui ont été optimisés pour les images avec différentes profondeurs de bits.

Paul
CenterSpace Logiciel

Answer 2

Vous pouvez ajouter de traitement d'image comme une balise.

Mais, cet article peut vous intéresser, esp, avec l'hypothèse que l'image est un pouvoir ou 2.Vous pouvez également voir où ils permettent d'optimiser la FFT.Je m'attends à ce que les articles que vous recherchez à fait quelques hypothèses et ensuite optimisé, les équations de ceux-ci.

http://www.gamasutra.com/view/feature/3993/sponsored_feature_implementation_.php

Si vous voulez aller plus vite, vous pouvez utiliser le GPU pour faire le travail.

Ce livre peut être utile pour vous, si vous allez avec le GPU:http://www.springerlink.com/content/kd6qm361pq8mmlx2/

Answer 3

Cette réponse est de collecter rapport d'avancement commentaires sur cette question.

Edit 11 oct.:

Le temps d'exécution j'ai mesuré ne correspond pas à l'heure de prise d'effet de la FFT.J'ai remarqué que lorsque mon programme se termine, le CPU est occupé à temps de système jusqu'à 42% pendant 10s.Quand je attendre jusqu'à ce que le CPU est à 0%, avant de redémarrer mon programme j'ai ensuite le 15.35 s temps d'exécution qui vient de la GPU.Je reçois le même temps, si j'en commentaire la FFT, filtrage.

Donc, la FFT est en effet actuellement plus vite que le GPU et a simplement été entravée par un système concurrent de la tâche.Je ne sais pas encore ce que cette tâche système est.Je soupçonne qu'il résulte de l'attribution d'un énorme tas de bloc où je copie le résultat du traitement avant de les écrire sur le disque.Pour les données d'entrée-je utiliser une carte mémoire.

Je vais modifier mon code pour obtenir une mesure précise de la FFT en temps de traitement.Le rendant plus rapide est toujours d'actualité, car il ya de la place pour optimiser le traitement GPU comme, par exemple, en canalisant le transfert de données à traiter.