El método más rápido para calcular la convolución

Question

Tengo que aplicar un filtro de convolución en cada fila de muchas imágenes.El clásico son las imágenes 360 de 1024x1024 píxeles.En mi caso de uso son 720 imágenes de 560x600 píxeles.

El problema es que mi código es mucho más lento de lo que se anuncia en los artículos.

He implementado la convolución ingenua y tarda 2 m 30 s.Luego cambié a FFT usando fftw.Utilicé complejo 2 complejo, filtrando dos filas en cada transformación.Ahora tengo alrededor de 20 años.

El caso es que los artículos se anuncian en torno a los 10 y menos aún para la condición clásica.Así que me gustaría preguntar a los expertos aquí si podría haber una manera más rápida de calcular la convolución.

Las recetas numéricas sugieren evitar la clasificación realizada en el dft y adaptar la función de filtro en el dominio de frecuencia en consecuencia.Pero no hay ningún ejemplo de código de cómo se podría hacer esto.

Quizás pierdo tiempo copiando datos.Con la transformación real 2 real no tendría que copiar los datos en valores complejos.Pero tengo que rellenar con 0 de todos modos.

EDITAR:Consulte mi propia respuesta a continuación para obtener comentarios sobre el progreso y más información sobre cómo resolver este problema.

Pregunta (reformulación precisa):

Estoy buscando un algoritmo o un fragmento de código para aplicar una convolución muy rápida a una función discreta no periódica (de 512 a 2048 valores).Aparentemente, la transformada de Fourier en tiempo discreto es el camino a seguir.Sin embargo, me gustaría evitar la copia y conversión de datos a complejos, y evitar el reordenamiento de mariposas.

Answer 1

FFT es la técnica más rápida conocida por la convolución de señales, y FFTW es la biblioteca libre más rápida disponible para el cálculo de la FFT.

La clave para que usted obtenga el máximo rendimiento (fuera de hardware de la GPU ... es una buena sugerencia) será para rellenar sus señales a una potencia de dos. Al utilizar FFTW utilizar el 'paciente' ajuste de la hora de crear su plan para obtener el mejor rendimiento. Es muy poco probable que va a rodar a mano una implementación más rápida que lo que ofrece FFTW (olvidarse de N. R.). También asegúrese de estar utilizando la versión real de la FFT 1D hacia adelante y no la versión Complejo; y sólo usar precisión simple (coma flotante) si es posible.

Si FFTW no es así enfriamiento para usted, entonces me gustaría ver en la biblioteca IPP (muy asequible) de Intel. La mano han sintonizado de FFT para los procesadores Intel que se han optimizado para las imágenes con diferentes profundidades de bits.

Paul area CenterSpace Software

Answer 2

Es posible que desee añadir procesamiento de imágenes como una etiqueta.

Sin embargo, este artículo puede ser de interés, especialmente con el supuesto de la imagen es un poder o 2. También se puede ver dónde optimizar la FFT. Espero que los artículos que usted está viendo algunas suposiciones hechas y luego se optimizan las ecuaciones para las personas.

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

Si quieres ir más rápido es posible que desee utilizar la GPU para hacer realidad el trabajo.

Este libro puede ser útil para usted, si vas con la GPU: http://www.springerlink.com/content/kd6qm361pq8mmlx2/

Answer 3

Esta respuesta es para obtener retroalimentación informe sobre este tema.

Editar 11 Okt .:

El tiempo de ejecución Medí no refleja el tiempo efectivo de la FFT. Me di cuenta de que cuando termina mi programa, la CPU todavía está ocupado en el sistema de tiempo de hasta un 42% durante 10 s. Cuando espero hasta que la CPU es de nuevo a 0%, antes de reiniciar mi programa que a continuación, obtener el tiempo de ejecución 15.35s que viene del procesamiento de la GPU. Consigo mismo tiempo, si comento hacia fuera el filtrado de FFT.

Así que la FFT es, de hecho, actualmente más rápido que la GPU y simplemente estaba obstaculizada por una tarea de sistema de la competencia. No sé aún lo que esta tarea es el sistema. Sospecho que resulta de la asignación de un enorme bloque del montón donde copio el resultado del proceso antes de escribir en el disco. Para los datos de entrada utilizo un mapa de memoria.

Ahora voy a cambiar mi código para obtener una medición exacta del tiempo de procesamiento FFT. Por lo que es más rápido sigue siendo la realidad porque no hay espacio para optimizar el procesamiento de la GPU, como por ejemplo, la canalización de la transferencia de datos a procesar.