Overlap-Add contre Overlap-Save

24

Quelles différences ou autres critères peuvent être utilisés pour aider à décider entre l'utilisation de chevauchement-ajout et chevauchement-sauvegarde pour le filtrage? Les deux ajouts et chevauchements sont décrits comme des algorithmes pour effectuer une convolution rapide basée sur la FFT de flux de données avec des noyaux de filtre FIR. Quelles sont les différences de latence, d'efficacité de calcul ou de localité de mise en cache (etc.), le cas échéant? Ou sont-ils les mêmes?

hotpaw2
la source

Réponses:

27

Essentiellement, le système d'exploitation est légèrement plus efficace car il ne nécessite pas l'ajout des transitoires qui se chevauchent. Cependant, vous pouvez utiliser OA si vous devez réutiliser les FFT avec un remplissage nul plutôt que des échantillons répétés.

Voici un bref aperçu d' un article que j'ai écrit il y a un moment

La convolution rapide fait référence à l'utilisation par blocs de la convolution circulaire pour réaliser la convolution linéaire. Une convolution rapide peut être réalisée par des méthodes OA ou OS. Le système d'exploitation est également appelé «rebut de chevauchement». Dans le filtrage OA, chaque bloc de données de signal contient uniquement autant d'échantillons que la convolution circulaire est équivalente à la convolution linéaire. Le bloc de données de signal est complété par un zéro avant la FFT pour empêcher la réponse impulsionnelle du filtre de «boucler» à la fin de la séquence. Le filtrage OA ajoute le transitoire d'entrée d'un bloc avec le transitoire d'entrée du bloc précédent. Dans le filtrage OS, illustré sur la figure 1, aucun remplissage nul n'est effectué sur les données d'entrée, donc la convolution circulaire n'est pas équivalente à la convolution linéaire. Les portions qui «s'enroulent» sont inutiles et jetées. Pour compenser cela, la dernière partie du bloc d'entrée précédent est utilisée comme début du bloc suivant. Le système d'exploitation ne nécessite aucun ajout de transitoires, ce qui le rend plus rapide que OA.

Mark Borgerding
la source
Excellent article! =)
Phonon
Il peut y avoir des optimisations dans la façon dont la DFT sur la partie à remplissage nul du tampon OA, qui donnent un avantage à la méthode OA. Cela dépend de votre processeur et de votre package FFT. En outre, vous pouvez éventuellement écrire votre propre algorithme FFT spécifiquement pour l'OA qui prend en compte le zéro-pad.
orodbhen
@orodbhen, connaissez-vous un tel package FFT?
Mark Borgerding
@MarkBorgerding Dans OpenCV, vous pouvez spécifier le nombre de lignes nulles, mais cela est spécifique à la 2D. En ce qui concerne les optimisations implicites présentes dans ce ou d'autres packages FFT, je ne sais pas. Je peux penser à beaucoup de cas où une FFT personnalisée pour exploiter la parcimonie serait utile mais je n'ai pas emprunté cette voie moi-même. Pas encore.
orodbhen
1
C'est une bonne chose que vous ayez cité car le lien est rompu :(
Mehrdad