Detección de latidos y FFT

13

Estoy trabajando en un juego de plataformas que incluye música con detección de ritmo. Actualmente estoy detectando ritmos comprobando cuándo la amplitud actual excede una muestra histórica. Esto no funciona bien con géneros musicales, como el rock, que tienen una amplitud bastante estable.

Así que busqué más y encontré algoritmos que dividen el sonido en múltiples bandas usando FFT ... luego encontré el algoritmo Cooley-Tukey FFt

El único problema que tengo es que soy bastante nuevo en audio y no tengo idea de cómo usarlo para dividir la señal en varias señales.

Entonces mi pregunta es:

¿Cómo se usa una FFT para dividir una señal en múltiples bandas?

También para los chicos interesados, este es mi algoritmo en C #:

// C = threshold, N = size of history buffer / 1024
    public void PlaceBeatMarkers(float C, int N)
    {
        List<float> instantEnergyList = new List<float>();
        short[] samples = soundData.Samples;

        float timePerSample = 1 / (float)soundData.SampleRate;
        int sampleIndex = 0;
        int nextSamples = 1024;

        // Calculate instant energy for every 1024 samples.
        while (sampleIndex + nextSamples < samples.Length)
        {

            float instantEnergy = 0;

            for (int i = 0; i < nextSamples; i++)
            {
                instantEnergy += Math.Abs((float)samples[sampleIndex + i]);
            }

            instantEnergy /= nextSamples;
            instantEnergyList.Add(instantEnergy);

            if(sampleIndex + nextSamples >= samples.Length)
                nextSamples = samples.Length - sampleIndex - 1;

            sampleIndex += nextSamples;
        }


        int index = N;
        int numInBuffer = index;
        float historyBuffer = 0;

        //Fill the history buffer with n * instant energy
        for (int i = 0; i < index; i++)
        {
            historyBuffer += instantEnergyList[i];
        }

        // If instantEnergy / samples in buffer < instantEnergy for the next sample then add beatmarker.
        while (index + 1 < instantEnergyList.Count)
        {
            if(instantEnergyList[index + 1] > (historyBuffer / numInBuffer) * C)
                beatMarkers.Add((index + 1) * 1024 * timePerSample); 
            historyBuffer -= instantEnergyList[index - numInBuffer];
            historyBuffer += instantEnergyList[index + 1];
            index++;
        }
    }
game-design c# software-engineering algorithm audio Quincy
fuente
Supongo que un buen punto de partida son las entradas FFT y DSP de wikipedia . La entrada de detección de latidos es escasa pero tiene enlaces a un artículo en gamedev.net
Tobias Kienzler

Respuestas:

14

Bueno, si su señal de entrada es real (como en cada muestra es un número real), el espectro será simétrico y complejo. Explotando la simetría, generalmente los algoritmos FFT empaquetan el resultado al devolverle solo la mitad positiva del espectro. La parte real de cada banda está en las muestras pares y la parte imaginaria en las muestras impares. O, a veces, las partes reales se agrupan en la primera mitad de la respuesta y las partes imaginarias en la segunda mitad.

En las fórmulas, si X [k] = FFT (x [n]), le da un vector i [n] = x [n], y obtiene una salida o [m], entonces

X[k] = o[2k] + j·o[2k+1]

(aunque a veces obtienes X [k] = o [k] + j · o [k + K / 2], donde K es la longitud de tu ventana, 1024 en tu ejemplo). Por cierto, j es la unidad imaginaria, sqrt (-1).

La magnitud de una banda se calcula como la raíz del producto de esta banda con su complejo conjugado:

|X[k]| = sqrt( X[k] · X[k]* )

Y la energía se define como el cuadrado de la magnitud.

Si llamamos a = o [2k] yb = o [2k + 1], obtenemos

X[k] = a + j·b

por lo tanto

E[k] = |X[k]|^2 = (a+j·b)·(a-j·b) = a·a + b·b

Desenrollando todo, si obtuviste o [m] como salida del algoritmo FFT, la energía en la banda k es:

E[k] = o[2k] · o[2k] + o[2k+1] · o[2k+1]

(Nota: utilicé el símbolo · para indicar la multiplicación en lugar de la habitual * para evitar confusiones con el operador de conjugación)

La frecuencia de la banda k, suponiendo una frecuencia de muestreo de 44.1Khz y una ventana de 1024 muestras, es

freq(k) = k / 1024 * 44100 [Hz]

Entonces, por ejemplo, su primera banda k = 0 representa 0 Hz, k = 1 es 43 Hz, y la última k = 511 es 22KHz (la frecuencia de Nyquist).

Espero que esto responda a tu pregunta sobre cómo obtienes la energía de la señal por banda usando el FFT.

Anexo : Responda su pregunta en el comentario y suponga que está utilizando el código del enlace que publicó en la pregunta (El algoritmo de Cooley-Tukey en C): Digamos que tiene sus datos de entrada como un vector de entradas cortas:

// len is 1024 in this example.  It MUST be a power of 2
// centerFreq is given in Hz, for example 43.0
double EnergyForBand( short *input, int len, double centerFreq)
{
  int i;
  int band;
  complex *xin;
  complex *xout;
  double magnitude;
  double samplingFreq = 44100.0; 

  // 1. Get the input as a vector of complex samples
  xin = (complex *)malloc(sizeof(struct complex_t) * len);

  for (i=0;i<len;i++) {
    xin[i].re = (double)input[i];
    xin[i].im = 0;
  }

  // 2. Transform the signal
  xout = FFT_simple(xin, len);

  // 3. Find the band ( Note: floor(x+0.5) = round(x) )
  band = (int) floor(centerFreq * len / samplingFreq + 0.5); 

  // 4. Get the magnitude
  magnitude = complex_magnitude( xout[band] );

  // 5. Don't leak memory
  free( xin );
  free( xout );

  // 6. Return energy
  return magnitude * magnitude;
}

Mi C está un poco oxidado (estoy codificando principalmente en C ++ hoy en día), pero espero no haber cometido ningún gran error con este código. Por supuesto, si estuviera interesado en la energía de otras bandas, no tiene sentido transformar la ventana completa para cada una de ellas, eso sería una pérdida de tiempo de CPU. En ese caso, realice la transformación una vez y obtenga todos los valores que necesita de xout.

CeeJay
fuente
Oh, acabo de echar un vistazo al código que vinculaste, ya te da los resultados en forma "compleja" e incluso te proporciona una función para calcular la magnitud de un número complejo. Entonces solo tendría que calcular el cuadrado de esa magnitud para cada elemento del vector de salida, no necesita preocuparse por ordenar los resultados.
CeeJay
Como ejemplo, si tengo todas las 1024 muestras de la ventana 0-1024 y las obtuve como valores reales, entonces no hay parte compleja. y quiero calcular la energía allí en la banda de frecuencia 43Hz. ¿Cómo lo integraría entonces? (Solo necesito que me devuelvan la parte real, la parte positiva) Si pudieras hacerlo en un seudocódigo, te profundizaré para siempre y entonces podría comprender el concepto un poco :)
Quincy
El código que escribí usa la biblioteca C que vinculaste, que ya contiene una estructura "compleja". Esto hace innecesario el desenvolvimiento que describí en mi pregunta (y el código lo refleja)
CeeJay
0

No he hecho esto o leí mucho sobre eso, pero mi primer disparo es algo como esto:

En primer lugar, deberá aplicar una función de ventana para obtener un espectro dependiente del tiempo con la FFT. El ritmo generalmente se encuentra en las frecuencias más bajas, así que aplique otra FFT con una ventana de tiempo más grande en las intensidades de algunas de estas frecuencias (para simplificar, comience con solo 1 a, por ejemplo, 100 Hz y vea si eso es lo suficientemente confiable). Encuentre el pico en este espectro y esa frecuencia es una conjetura para el ritmo.

Tobias Kienzler
fuente
No es en realidad la detección de ritmo con la que tengo problemas, pero entiendo cómo funciona FFT. Soy realmente nuevo en el procesamiento de señales y cosas como: "aplicar una función de ventana para obtener un espectro dependiente del tiempo con el FFT" no tienen ningún sentido para mí. Gracias de todos modos :)
Quincy