Détection de battements et FFT

13

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++;
        }
    }
Quincy
la source
Je suppose qu'un bon point de départ est les entrées FFT et DSP de Wikipédia. L'entrée de détection de battement est rare mais renvoie
Tobias Kienzler

Réponses:

14

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.

CeeJay
la source
Oh, je viens de jeter un coup d'œil au code que vous avez lié, il vous donne déjà les résultats sous forme "complexe" et vous fournit même une fonction pour calculer l'ampleur d'un nombre complexe. Il vous suffirait alors de calculer le carré de cette ampleur pour chaque élément du vecteur de sortie, pas besoin de vous soucier du tri des résultats.
CeeJay
Par exemple, si j'ai tous les 1024 échantillons de la fenêtre 0-1024 et que je les ai obtenus sous forme de valeurs réelles, donc pas de partie complexe. et je veux calculer l'énergie là-bas sur la bande de fréquence 43Hz. Comment pourrais-je l'intégrer alors? (Je n'ai besoin que de la partie réelle, la partie postive) Si vous pouviez le faire dans un pseudocode, je serai en profondeur pour vous pour toujours et je pourrais en fait comprendre un peu le concept :)
Quincy
Le code que j'ai écrit utilise la bibliothèque C que vous avez liée, qui contient déjà une structure "complexe". Cela rend inutile le déballage que j'ai décrit dans ma question (et le code le reflète)
CeeJay
0

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.

Tobias Kienzler
la source
Ce n'est pas vraiment la détection de battement avec laquelle j'ai du mal mais je comprends le fonctionnement de la FFT. Je suis vraiment nouveau dans le traitement du signal et des choses comme: "appliquer une fonction de fenêtre pour obtenir un spectre dépendant du temps avec la FFT" n'ont aucun sens pour moi. Merci quand même :)
Quincy