Sobreposição-adição versus sobreposição-economia

24

Quais diferenças ou outros critérios podem ser usados ​​para ajudar a decidir entre o uso de sobreposição de adição e sobreposição de economia para filtragem? Tanto a sobreposição de adição quanto a sobreposição de economia são descritas como algoritmos para realizar convolução rápida baseada em FFT de fluxos de dados com kernels de filtro FIR. Quais são as diferenças de latência, eficiência computacional ou localidade de cache (etc.), se houver? Ou eles são a mesma coisa?

hotpaw2
fonte

Respostas:

27

Essencialmente, o sistema operacional é um pouco mais eficiente, pois não requer a adição de transientes sobrepostos. No entanto, convém usar o OA se precisar reutilizar as FFTs com preenchimento zero em vez de amostras repetidas.

Aqui está uma rápida visão geral de um artigo que escrevi há algum tempo

Convolução rápida refere-se ao uso em bloco de convolução circular para realizar convolução linear. A convolução rápida pode ser realizada pelos métodos OA ou OS. O SO também é conhecido como "sobreposição de sucata". Na filtragem de OA, cada bloco de dados de sinal contém apenas o número de amostras que permite que a convolução circular seja equivalente à convolução linear. O bloco de dados do sinal é preenchido com zero antes da FFT para impedir que a resposta de impulso do filtro se "enrole" no final da sequência. A filtragem OA adiciona o transiente de entrada de um bloco com o transiente de entrada de fora do bloco anterior. Na filtragem do SO, mostrada na Figura 1, nenhum preenchimento zero é realizado nos dados de entrada, portanto, a convolução circular não é equivalente à convolução linear. As porções que "envolvem" são inúteis e descartadas. Para compensar isso, a última parte do bloco de entrada anterior é usada como o início do próximo bloco. O SO não requer adição de transientes, tornando-o mais rápido que o OA.

Mark Borgerding
fonte
Ótimo artigo! =)
Phonon
Pode haver algumas otimizações na maneira como a DFT sobre a parte preenchida com zero do buffer OA é calculada, o que dá uma vantagem ao método OA. Isso dependeria do seu processador e do pacote FFT. Além disso, você pode escrever seu próprio algoritmo FFT especificamente para o OA que leva em consideração o zero-pad.
orodbhen
@orodbhen, você conhece algum desses pacotes FFT?
Mark Borgerding
@ MarkBorgerding No OpenCV, você pode especificar o número de zero linhas, mas isso é específico para 2D. Quanto às otimizações implícitas presentes nesse ou em outros pacotes FFT, não sei. Posso pensar em muitos casos em que uma FFT personalizada para explorar a escassez seria útil, mas eu mesmo não segui esse caminho. Ainda não.
orodbhen
1
Ainda bem que você citou porque o link está quebrado :(
Mehrdad