Je travaille avec la corrélation 2D pour les techniques de traitement d'image (reconnaissance de formes etc ...). Je me demandais s'il existe une approche théorique sur la façon de savoir quand utiliser la multiplication dans l'espace des fréquences par rapport à la corrélation dans l'espace-temps. Pour les tailles de 2 x l' espace de fréquence est évidemment plus rapide, mais qu'en est-il des petites tailles principales comme par exemple 11?
Je suppose que cela se fait sur un processeur conventionnel, un cœur, exécutant un thread simple, pas de matériel sophistiqué. S'il y a plus que cela, cela peut probablement être expliqué par des ajustements au raisonnement pour un système plus simple. On ne peut pas en dire beaucoup plus sans un système spécifique à discuter, ni un manuel complet ou un document de recherche pour couvrir un éventail de possibilités.
Je ne m'inquiéterais pas des tailles de puissance de deux. Ça n'a pas d'importance. Algorithmes FFT avec les unités papillon et tout ce qui existe pour des facteurs de 3, ou n'importe quel petit nombre, pas seulement 2. Il existe également des algorithmes intelligents pour les séries de données de grande taille. Je n'aime pas citer Wikipedia à ce sujet en raison de sa nature impermanente, mais de toute façon:
il existe des FFT avec une complexité O (N log N) pour tous les N, même pour les N premiers
Les implémentations de FFT pour N arbitraire peuvent être trouvées dans la bibliothèque GFT FFTW .
La seule manière fiable en termes d'ingénierie sérieuse est de construire et de mesurer, mais nous pouvons certainement nous faire une idée de la théorie, pour voir les relations entre les variables. Nous avons besoin d'estimations du nombre d'opérations arithmétiques impliquées pour chaque méthode.
La multiplication est toujours plus lente que l'ajout sur la plupart des processeurs, même si la différence a considérablement diminué au fil des ans, alors comptons simplement les multiplications. La prise en compte également de l'addition nécessite un peu plus de réflexion et de suivi des choses.
Une convolution simple, multipliant et ajoutant en fait à l'aide du noyau de convolution, se répétant pour chaque pixel de sortie, nécessite des multiplications W² · K², où W est le nombre de pixels le long d'un côté de l'image (en supposant un carré pour la simplicité) et K est la taille du noyau de convolution, en pixels le long d'un côté. Il faut des multiplications K² pour calculer un pixel de sortie en utilisant le noyau et la partie de même taille de l'image d'entrée. Répétez l'opération pour tous les pixels de sortie, qui sont identiques à ceux de l'image d'entrée.
(N mults ) direct = W² · K²
Pour faire le travail dans l'espace de Fourier, il faut transformer Fourier l'image. Cela se fait en appliquant une FFT à chaque colonne séparément, puis à chaque ligne. La FFT pour N points de données prend environ 2N · log (N) multiplications; nous voulons que N soit W, la longueur d'une colonne ou d'une ligne. Tous les logarithmes ici sont en base deux.
Il y a W lignes et W colonnes, donc une fois toutes les FFT terminées, nous avons effectué des multiplications de 2 W · (2 W · log (W)). Doublez cela, car après avoir multiplié par la transformée de Fourier du noyau, nous devons inverser Fourier les données pour revenir à l'image sensible. C'est 8W² · log (W). Bien sûr, la multiplication par la transformée de Fourier du noyau doit être effectuée, une autre multiplication W². (Effectué une fois, pas une fois par pixel de sortie, par ligne ou quoi que ce soit.) Ce sont des multiplications complexes, c'est donc des multiplications réelles de 4 W².
Donc, à moins que je ne me trompe (et je l'ai probablement fait), nous avons
(N mults ) Fourier = 4W² · (2 · log (W) + 1)
Quand voulons-nous faire les choses directement? Lorsque K est suffisamment petit pour rendre W² · K² inférieur à 4W² · (2 · log (W) + 1). Un facteur commun de W² est facilement factorisé. Nous pouvons probablement baisser le "+1" car nous avons affaire à des estimations idéalisées. Le +1 est probablement perdu dans les erreurs par rapport aux implémentations réelles, sans compter les ajouts, les surcharges de boucle, etc. Cela laisse:
K² < 8·log(W)
Il s'agit de la condition approximative pour choisir une approche directe plutôt qu'une approche d'espace de fréquence.
Notez que la corrélation de deux images de même taille est comme une convolution avec un noyau de taille K = W. L'espace de Fourier est toujours le moyen de le faire.
Cela peut être affiné et argumenté pour tenir compte des frais généraux, du pipeline des opcodes, du flotteur par rapport au point fixe et jeté par la fenêtre avec GPGPU et du matériel spécialisé.