Méthode la plus rapide pour calculer la convolution

Question

Je dois 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 s'agit 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 implémenté la convolution naïve, et cela prend 2m 30s. Je suis ensuite passé à FFT en utilisant fftw. J'ai utilisé complexe complexe 2, en filtrant deux lignes dans chaque transformée. J'ai maintenant environ 20 ans.

Le fait est que les articles annoncent autour de 10s et même moins pour la condition classique. J'aimerais donc demander aux experts s'il existe un moyen plus rapide de calculer la convolution.

Les recettes numériques suggèrent d'éviter le tri effectué dans le dft et d'adapter la fonction de filtrage du domaine fréquentiel en conséquence. Mais il n'y a pas d'exemple de code comment cela pourrait être fait.

Peut-être que je perds du temps à copier des données. Avec une vraie transformation réelle de 2, je n'aurais pas à copier les données dans les valeurs du complexe. Mais je dois pad avec 0 de toute façon.

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

Question (reformulation précise):

Je cherche un algorithme ou un morceau de code pour appliquer une convolution très rapide à une fonction discrète non périodique (512 à 2048 valeurs). Apparemment, la transformée de Fourier à temps discret est la voie à suivre. Cependant, je voudrais éviter la copie de données et la conversion au complexe, et éviter le réordonnancement de papillon.

Answer 1

FFT est la technique la plus rapide connue pour les signaux de convolution, et FFTW est la bibliothèque libre la plus rapide disponible pour le calcul de la FFT.

La clé pour que vous obteniez des performances maximales (en dehors du matériel ... le GPU est une bonne suggestion) sera de remplir vos signaux à une puissance de deux. Lorsque vous utilisez FFTW, utilisez le paramètre 'patient' lors de la création de votre plan pour obtenir les meilleures performances. Il est hautement improbable que vous lanciez manuellement une implémentation plus rapide que celle fournie par FFTW (oubliez N.R.). Veillez également à utiliser la version Real de la FFT 1D et non la version Complex; et n'utilisez qu'une seule précision (virgule flottante) si vous le pouvez.

Si FFTW ne le coupe pas pour vous, alors je regarderais la bibliothèque IPP (très abordable) d'Intel. Les FFT ont été réglés à la main pour les processeurs Intel qui ont été optimisés pour des images avec différentes profondeurs de bits.

Paul
CenterSpace Software

Answer 2

Vous souhaiterez peut-être ajouter le traitement d'image en tant que balise.

Mais, cet article peut être intéressant, en supposant que l'image est une puissance ou 2. Vous pouvez également voir où ils optimisent la FFT. Je m'attends à ce que les articles que vous regardez fassent des hypothèses et optimisent ensuite les équations pour ceux-là.

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

Si vous voulez aller plus vite, vous voudrez peut-être 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 recueillir les commentaires du rapport intérimaire sur cette question.

Modifier 11 octobre .:

Le temps d'exécution I mesurée ne reflète pas le temps effectif de la FFT. J'ai remarqué que lorsque mon programme se termine, le processeur est encore occupé dans le temps système jusqu'à 42% pendant 10 secondes. Quand j'attends que le CPU revienne à 0%, avant de redémarrer mon programme, j'obtiens alors le temps d'exécution de 15.35s qui vient du traitement GPU. Je reçois le même temps si je commente le filtrage FFT. Ainsi, la FFT est en fait actuellement plus rapide que le GPU et a été simplement entravée par une tâche système concurrente. Je ne sais pas encore quelle est cette tâche système. Je suppose qu'il résulte de l'allocation d'un énorme bloc de tas où je copie le résultat de traitement avant de l'écrire sur le disque. Pour les données d'entrée, j'utilise une carte mémoire.

Je vais maintenant changer mon code pour obtenir une mesure précise du temps de traitement FFT. Le rendre plus rapide est toujours une réalité car il y a de la place pour optimiser le traitement GPU comme par exemple en pipelining le transfert de données à traiter.