¿Conoces una FFT buena y eficiente?

Estoy tratando de encontrar una transformada de Fourier (FFT) muy rápida y eficiente. ¿Alguien sabe de algunos buenos? Necesito ejecutarlo en el iPhone, así que no debe ser intensivo. En cambio, tal vez conozcas uno que tenga forma de onda, necesito resolución de frecuencia pero solo una banda estrecha (rango de audio vocal de hasta 10 kHz máx. ... incluso 10 kHz podrían ser demasiado altos). También estoy pensando en truncar esta FFT para mantener la resolución de frecuencia mientras elimino la banda de frecuencia no deseada. Esto es para un iphone¿Conoces una FFT buena y eficiente?

... He echado un vistazo a la FFT en Aurio touch pero parece que esta es una FFT int, pero mi aplicación usa flotadores ..... ¿le daría un gran aumento de rendimiento para probar y adaptar el programa a una FFT int o no (que realmente no tengo ganas de hacer ... además, aurio touch usa una FFT de radix 2 que no es tan buena).

Fuente

2009-10-20 yan bellavance

Teniendo en cuenta la transformación de ondas no se calcula de la misma manera que la DFT, yo diría que no hay algoritmo FFT wavelet-similares. – rlbond

¿Qué tal un fft tipo Wavelet en el sentido de que en lugar de tener una matriz cuadrada (4096by4096 para una FFT de 4096 muestras) usamos 4096 muestras de tiempo por 1024 recipientes de frecuencia ... esto no cubriría toda la banda de nyquist y también lo haría mantenga la resolución de frecuencia deseada sin necesidad de calcularlos todos ... este es el aspecto de escalas de resolución múltiple de las ondas pequeñas pero con una sola escala ... así que es como si estuviera aplicando un filtro ... que es parte de WFT –

El rendimiento de la FFTW establece el estándar para FFT de longitud arbitraria, especialmente para la no potencia de 2 longitudes en 2 y mayores dimensiones. La licencia comercial para FFTW es de $ 5000, que puede o no ajustarse a su presupuesto.

Sin embargo, parece que tiene un problema de procesamiento de la señal 1D, en cuyo caso tiene algunas opciones más, y si puede agregar más información o muestrear sus datos a potencias de 2, entonces muchas bibliotecas ofrecerán rendimiento razonable. Consulte este list de los algoritmos de FFT que FFTW utilizó para la comparación: muchos son gratuitos y otros pueden ser adecuados. Probablemente comenzaría con el viejo numeric recipes que ofrece una potencia fácil de 2, 1D implementación de FFT gratis y algo de mecanografía, y sería muy eficiente en la memoria.

BTW - para voz, probablemente solo necesite ir a 3-4Khz .... 10Khz está muy arriba para la voz humana .

Fuente

2009-10-20 06:17:12 Paul

Estoy de acuerdo, pero con una FFT estándar, la resolución de frecuencia de banda inferior se ve afectada por una reducción del tamaño de FFT porque los contenedores de frecuencia se vuelven demasiado grandes –

gracias, miraré esos enlaces ya que siempre estoy en potencia de 2 longitudes –

Dale la Transformación más rápida de Fourier en el Oeste (FFTW) a go, El rendimiento es bueno en comparación con otros, pero no es completamente gratis. Vea los detalles sobre el uso comercial here. Obviamente, al ser una biblioteca c, no debería tener problemas para vincularla como una biblioteca estática a su aplicación iphone.

Fuente

2009-10-20 04:44:38 hhafez

Utiliza memoria compartida FYI, no puede ejecutarla de forma segura en paralelo. no estoy seguro si esto es un problema en el iPhone o no (¿no?) –

Si no te importa liberar tu aplicación bajo GPLv2 (no puedes usar GPLv3 para una aplicación de iPhone), es completamente gratis. Si eso no es compatible con su modelo de negocio, deberá verificar las opciones comerciales. –

He envuelto la biblioteca FFT de Ooura en Objective-C. El código de Ooura tiene un rendimiento comparable al de FFTW, pero es totalmente gratuito.

Este código usa precisión doble y tiene varios tipos de ventanas incorporadas (rectangular, Blackwell, Triangle, Hamming). Utilizo el código FFT de Ooura para implementar Welch's method, que generará un espectro mucho más uniforme cuando se lo vea a lo largo del tiempo.

Compruebe hacia fuera en: http://github.com/alexbw/iPhoneFFT

Fuente

2009-12-05 19:44:36 alexbw

solo seguimiento (tres años después) - debe intentar NO usar iPhoneFFT en su proyecto. Apple ha lanzado vDSP y Accelerate.h en el iPhone, y debería usar funciones como vDSP_fft_zrip() para calcular las FFT. Son un GRAN negocio más rápido que cualquier cosa que haya escrito. – alexbw

De hecho grandes piezas de trabajo Alex, comprobé Octave y Oscope ambos. Me pregunto si hay alguna biblioteca iOS que envuelva con éxito vDSP para detectar sonidos humanos; ahora déjame decirte que no sé si significa detección de tono o pase de banda o qué. –

Eso en sí mismo es una pregunta de investigación abierta en informática (para hacerlo de manera confiable).Si está interesado en un sonido determinado, grabe un montón de ejemplos y observe sus espectrogramas. Eso debería ayudarlo a construir un filtro que pueda responder selectivamente a él. – alexbw

Aquí hay un enlace principal fuente de programa digital de Ooura:

http://www.kurims.kyoto-u.ac.jp/~ooura/

He estado usando muchas de las FFT de Ooura lo largo de los años, debería enviar él un "domo" por lo menos, y yo uso su real radix-4 en varias aplicaciones de iPad y iPhone en desarrollo. Traduje el código para operar con una sola precisión de 32 bits para el rendimiento en ARM. Al observar el conjunto producido con XCode 3.2.2, se vectoriza con las instrucciones de NEON SIMD muy bien. En realidad, estaba medio decepcionado, ya que estaba dispuesto a vectorizar un poco el código para obtener aún más rendimiento. Estas optimizaciones no se pueden tener sin primero traducir la FFT a una sola precisión, obviamente.

Aunque utilicé Objective-C durante muchos años, desarrollé activamente su uso, e incluso enseñé un curso de programación orientado a objetos que lo usaba, no preparé ese envoltorio (aunque hice lo mismo en 1992 con una FFT diferente) por razones de rendimiento.

No he probado FFTW contra la FFT de Ooura en al menos 10 años, pero cuando lo hice, la biblioteca de Ooura era más rápida para 1024 puntos FFT reales. Sin embargo, es bastante posible que FFTW pueda hacerlo mucho mejor ahora, pero licenciarlo y compilarlo en forma cruzada para ARM es inconveniente y siempre he encontrado que FFTW es demasiado voluminoso e intrusivo para mis necesidades de DSP. VecLib de Apple es muy bueno, pero desafortunadamente no lo han portado a iPhoneOS. Me abrió una de estas solicitudes en bugreporter y tú también puedes: https://bugreport.apple.com/

Fuente

2010-05-02 07:30:46 ctpenrose

FFTW debe ser mucho más rápido para longitudes que no son números redondos en binario, p. Ej. para primos. –

The iPhone OS4 SDK will include the Accelerate framework, que (por fin) nos dan funciones FFT escritos por Apple

Accelerate ofrece cientos de funciones matemáticas optimizado para iPhone y el iPod tocar, incluyendo rutinas de procesamiento de señales, rápido transformadas de Fourier, vector básico y operaciones de la matriz, y funciones estándar de la industria para matrices de factorización y los sistemas de resolver ecuaciones lineales.

Fuente

2010-05-02 17:16:38 alexbw

Como se ha respondido anteriormente, Accelerate Framework ahora proporciona algunas API que pueden serle de ayuda.

Comprobar:

Accelerate Framework Reference

vDSP Reference

Using Fourier Transforms

Fuente

2013-03-25 21:27:55 dwbrito