Détection de battements et FFT

Je travaille sur un jeu de plateforme qui comprend de la musique avec détection de battements. Je détecte actuellement des battements en vérifiant quand l'amplitude actuelle dépasse un échantillon historique. Cela ne fonctionne pas bien avec les genres de musique, comme le rock, qui ont une amplitude assez stable.

J'ai donc regardé plus loin et trouvé des algorithmes divisant le son en plusieurs bandes en utilisant la FFT ... puis j'ai trouvé l' algorithme Cooley-Tukey FFt

Le seul problème que j'ai est que je suis assez nouveau dans l'audio et je n'ai aucune idée de comment l'utiliser pour diviser le signal en plusieurs signaux.

Ma question est donc:

Comment utilisez-vous une FFT pour diviser un signal en plusieurs bandes?

Aussi pour les gars intéressés, voici mon algorithme 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++;
        }
    }

Eh bien, si votre signal d'entrée est réel (comme dans, chaque échantillon est un nombre réel), le spectre sera symétrique et complexe. En exploitant la symétrie, les algorithmes FFT emballent généralement le résultat en ne vous rendant que la moitié positive du spectre. La partie réelle de chaque bande se trouve dans les échantillons pairs et la partie imaginaire dans les échantillons impairs. Ou parfois, les parties réelles sont regroupées dans la première moitié de la réponse et les parties imaginaires dans la seconde moitié.

Dans les formules, si X [k] = FFT (x [n]), vous lui donnez un vecteur i [n] = x [n], et obtenez une sortie o [m], alors

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

(même si parfois vous obtenez X [k] = o [k] + j · o [k + K / 2], où K est la longueur de votre fenêtre, 1024 dans votre exemple). Soit dit en passant, j est l'unité imaginaire, sqrt (-1).

La magnitude d'une bande est calculée comme la racine du produit de cette bande avec son conjugué complexe:

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

Et l'énergie est définie comme le carré de la magnitude.

Si nous appelons a = o [2k] et b = o [2k + 1], nous obtenons

X[k] = a + j·b

par conséquent

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

En déroulant le tout, si vous avez obtenu o [m] en sortie de l'algorithme FFT, l'énergie dans la bande k est:

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

(Remarque: j'ai utilisé le symbole · pour indiquer la multiplication au lieu de l'habituel * afin d'éviter toute confusion avec l'opérateur de conjugaison)

La fréquence de la bande k, en supposant une fréquence d'échantillonnage de 44,1 kHz et une fenêtre de 1024 échantillons, est

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

Ainsi, par exemple, votre première bande k = 0 représente 0 Hz, k = 1 est 43 Hz et la dernière k = 511 est 22 KHz (la fréquence de Nyquist).

J'espère que cela répond à votre question sur la façon d'obtenir l'énergie du signal par bande en utilisant la FFT.

Addendum : Répondre à votre question dans le commentaire, et en supposant que vous utilisez le code du lien que vous avez publié dans la question (l'algorithme Cooley-Tukey en C): Disons que vous avez vos données d'entrée comme vecteur de petites entrées:

// 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;
}

Mon C est un peu rouillé (je code principalement en C ++ de nos jours), mais j'espère que je n'ai pas fait de grosse erreur avec ce code. Bien sûr, si vous étiez intéressé par l'énergie des autres bandes, cela n'a aucun sens de transformer toute la fenêtre pour chacun d'entre eux, ce serait une perte de temps CPU. Dans ce cas, effectuez la transformation une fois et obtenez toutes les valeurs dont vous avez besoin de xout.

Voici une excellente lecture sur la détection des battements dans les jeux.

http://www.badlogicgames.com/wordpress/?p=99

Cela fait partie d'une série de blogs en 8 parties sur la question.

http://www.badlogicgames.com/wordpress/?category_name=onset-detection-tutorial

Je n'ai pas fait ça ou je n'ai pas beaucoup lu à ce sujet moi-même, mais mon premier coup est quelque chose comme ça:

Tout d'abord, vous devrez appliquer une fonction de fenêtre pour obtenir un spectre dépendant du temps avec la FFT. Le rythme se situe généralement dans les basses fréquences, alors appliquez une autre FFT avec une fenêtre temporelle plus grande sur les intensités de certaines de ces fréquences (pour plus de simplicité, commencez avec seulement 1 à 100 Hz par exemple et voyez si cela est suffisamment fiable). Trouvez le pic dans ce spectre et cette fréquence est une estimation du rythme.