Actualmente estoy implementando una FFT bidimensional para datos de entrada reales usando opencl (más específicamente una rápida convolución 2D usando FFTs, entonces solo necesito algo que se comporte de manera similar para aplicar la convolución). La FFT 2D se implementa utilizando una FFT 1D en las filas y luego una FFT 1D en las columnas.Eficaz FFT 2D en datos de entrada real?
Para hacer esto más eficiente, estoy tratando de usar las simetrías de las FFT con entrada real para poder calcular FFT más pequeñas. Descubrí que puedo combinar dos filas en una, usando el primer componente real, el segundo como componente imaginario, hago la primera FFT 1D en la fila resultante y luego uso las propiedades de simetría para construir los resultados de las FFT 1D del individuo filas de eso. Entonces lo que estoy haciendo es básicamente lo siguiente:
Deje f y g ser filas de la matriz.
- Construct
x = f + i * g - transformar para obtener
F(x) = F(f) + i * F(g) - Use simetrías para extraer
F(f)yF(g)deF(x)
no puedo sin embargo, sólo de entrada los resultados directamente en la segunda 1D FFT, porque en ese caso, no transformaría toda la matriz, sino dos submatrices en su lugar. Sin embargo, extraer los datos entre las transformaciones significa almacenar más datos (n/2+1 entradas necesarias para expresar el resultado de una 1D FFT en la entrada real) o combinar los elementos en el índice 0 y el índice n/2 en un elemento (combinando usando el mismo truco, ya que ambos los números tienen la garantía de ser reales) y usan la misma cantidad de almacenamiento, pero tienen que hacer un caso especial para eso en mi convolución.
Como trato de volver a utilizar los almacenamientos intermedios tanto como sea posible (debido a la RAM limitada disponible en el gpu) el uso de más almacenamiento no es una buena solución. Además, mis algoritmos no están equipados para trabajar en tamaños matriciales que no son potencia de 2/múltiplos de 16 (varía de kernel a kernel). Prefiero evitar la introducción de casos especiales, ya que estos harían que mis núcleos sean más complejos y perjudicarán la eficiencia (ya estoy teniendo problemas para minimizar el recuento de registros utilizado por cada kernel).
Así que mi pregunta es si hay un enfoque elegante para este problema, es decir, uno que funcione sin usar más memoria o casos especiales para ciertos elementos?
Idealmente me gustaría poder hacer toda la FFT sin dividir mis datos combinados en el medio de la FFT, pero no estoy seguro de que sea posible.
¿Saldrá en rústica pronto? –
¿De verdad necesitas hacer una FFT compleja? Probablemente no. – phkahler
buena pregunta, tuve casi el mismo problema al hacer fft para detectar esteganografía. pero entonces no me di cuenta ... de que existe stackoverflow;/ – dfens