Superposición-Agregar versus Superposición-Guardar

24

¿Qué diferencias u otros criterios se pueden usar para ayudar a decidir entre usar overlap-add y overlap-save para el filtrado? Tanto overlap-add como overlap-save se describen como algoritmos para realizar una convolución rápida basada en FFT de flujos de datos con núcleos de filtro FIR. ¿Cuáles son las diferencias de latencia, eficiencia computacional o localidad de caché (etc.), si las hay? ¿O son lo mismo?

hotpaw2
fuente

Respuestas:

27

Esencialmente, el sistema operativo es un poco más eficiente ya que no requiere la adición de transitorios superpuestos. Sin embargo, es posible que desee utilizar OA si necesita reutilizar las FFT con relleno de cero en lugar de muestras repetidas.

Aquí hay un resumen rápido de un artículo que escribí hace un tiempo

La convolución rápida se refiere al uso en bloque de la convolución circular para lograr la convolución lineal. La convolución rápida puede lograrse mediante métodos OA u OS. El SO también se conoce como "solapamiento superpuesto". En el filtrado de OA, cada bloque de datos de señal contiene tantas muestras como permita que la convolución circular sea equivalente a la convolución lineal. El bloque de datos de señal se rellena con ceros antes de la FFT para evitar que la respuesta al impulso del filtro se "enrolle" al final de la secuencia. El filtrado OA agrega el transitorio de entrada de un bloque con el transitorio de entrada de entrada del bloque anterior. En el filtrado del sistema operativo, que se muestra en la Figura 1, no se realiza relleno de cero en los datos de entrada, por lo tanto, la convolución circular no es equivalente a la convolución lineal. Las porciones que se "envuelven" son inútiles y se descartan. Para compensar esto, la última parte del bloque de entrada anterior se usa como el comienzo del siguiente bloque. El sistema operativo no requiere la adición de transitorios, por lo que es más rápido que OA.

Mark Borgerding
fuente
¡Excelente artículo! =)
Phonon
Puede haber algunas optimizaciones en la forma en que se calcula el DFT sobre la porción de relleno de cero del búfer OA, que le da una ventaja al método OA. Esto dependería de su procesador y paquete FFT. Además, podría escribir su propio algoritmo FFT específicamente para el OA que tenga en cuenta el pad cero.
orodbhen
@orodbhen, ¿conoce algún paquete de FFT?
Mark Borgerding
@MarkBorgerding En OpenCV puede especificar el número de filas cero, pero eso es específico de 2D. En cuanto a qué optimizaciones implícitas están presentes en ese u otros paquetes de FFT, no lo sé. Puedo pensar en muchos casos en los que una FFT personalizada para explotar la escasez sería útil, pero yo no he seguido ese camino. Aún no.
orodbhen
1
Es bueno que hayas citado porque el enlace está roto :(
Mehrdad