Beaterkennung und FFT

13

Ich arbeite an einem Platformer-Spiel, das Musik mit Beat-Erkennung enthält. Momentan erkenne ich Beats, indem ich überprüfe, ob die aktuelle Amplitude eine historische Stichprobe überschreitet. Dies funktioniert nicht gut mit Musikgenres wie Rock, die eine ziemlich konstante Amplitude haben.

Also habe ich weiter gesucht und Algorithmen gefunden, die den Sound mit FFT in mehrere Bänder aufteilen ... dann habe ich die gefunden aufteilen. Cooley-Tukey FFt-Algorithmus gefunden

Das einzige Problem, das ich habe, ist, dass ich für Audio ziemlich neu bin und keine Ahnung habe, wie ich das verwenden soll, um das Signal in mehrere Signale aufzuteilen.

Meine Frage lautet also:

Wie verwendet man eine FFT, um ein Signal in mehrere Bänder aufzuteilen?

Auch für die Interessierten ist dies mein Algorithmus in 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
quelle
Ich denke, ein guter Ausgangspunkt sind die FFT- und DSP- Einträge von Wikipedia . Der Eintrag zu Beat Detection ist spärlich, verlinkt aber auf einen Artikel bei gamedev.net
Tobias Kienzler

Antworten:

14

Nun, wenn Ihr Eingangssignal real ist (wie in, ist jedes Sample eine reelle Zahl), ist das Spektrum symmetrisch und komplex. Wenn Sie die Symmetrie ausnutzen, packen normalerweise FFT-Algorithmen das Ergebnis, indem Sie nur die positive Hälfte des Spektrums zurückgeben. Der Realteil jeder Band ist in den geraden Samples und der Imaginärteil in den ungeraden Samples. Oder manchmal werden die Realteile in der ersten Hälfte der Antwort und die Imaginärteile in der zweiten Hälfte zusammengepackt.

Wenn in Formeln X [k] = FFT (x [n]) ist, geben Sie ihm einen Vektor i [n] = x [n] und erhalten eine Ausgabe von o [m]

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

(obwohl Sie manchmal X [k] = o [k] + j · o [k + K / 2] erhalten, wobei K die Länge Ihres Fensters ist, 1024 in Ihrem Beispiel). Übrigens ist j die imaginäre Einheit sqrt (-1).

Die Größe einer Bande wird als Wurzel des Produkts dieser Bande mit ihrem komplexen Konjugat berechnet:

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

Und die Energie ist definiert als das Quadrat der Größe.

Wenn wir a = o [2k] und b = o [2k + 1] nennen, erhalten wir

X[k] = a + j·b

deshalb

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

Wenn Sie das Ganze abrollen und als Ausgabe des FFT-Algorithmus o [m] erhalten, ist die Energie im Band k:

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

(Hinweis: Ich habe das Symbol · anstelle des üblichen * verwendet, um Verwechslungen mit dem Konjugationsoperator zu vermeiden.)

Die Frequenz des Bandes k unter der Annahme einer Abtastfrequenz von 44,1 kHz und eines Fensters von 1024 Abtastwerten beträgt

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

So steht beispielsweise Ihr erstes Band k = 0 für 0 Hz, k = 1 für 43 Hz und das letzte k = 511 für 22 kHz (die Nyquist-Frequenz).

Ich hoffe, dies beantwortet Ihre Frage, wie Sie die Energie des Signals pro Band mithilfe der FFT erhalten.

Nachtrag : Beantworten Sie Ihre Frage im Kommentar und setzen Sie voraus, dass Sie den Code aus dem Link verwenden, den Sie in der Frage gepostet haben (Der Cooley-Tukey-Algorithmus in C).

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

Mein C ist ein bisschen verrostet (ich programmiere heutzutage hauptsächlich in C ++), aber ich hoffe, dass ich mit diesem Code keinen großen Fehler gemacht habe. Wenn Sie sich für die Energie anderer Bands interessieren, macht es natürlich keinen Sinn, das gesamte Fenster für jede von ihnen zu transformieren, das wäre eine Verschwendung von CPU-Zeit. Führen Sie in diesem Fall die Transformation einmal durch und holen Sie sich alle benötigten Werte von xout.

CeeJay
quelle
Oh, ich habe mir nur den Code angesehen, den Sie verlinkt haben. Er gibt Ihnen bereits die Ergebnisse in "komplexer" Form und bietet Ihnen sogar eine Funktion zur Berechnung der Größe einer komplexen Zahl. Dann müssten Sie nur das Quadrat dieser Größe für jedes Element des Ausgabevektors berechnen, ohne sich um das Sortieren der Ergebnisse kümmern zu müssen.
CeeJay
Wenn ich als Beispiel alle 1024 Samples aus dem Fenster 0-1024 habe und sie als reale Werte erhalten habe, ist das kein komplexer Teil. und ich will die energie da drin auf dem frequenzband 43Hz berechnen. Wie würde ich es dann integrieren? (Ich brauche nur den Realteil zurück, den Postivteil) Wenn du es in irgendeinem Pseudocode machen könntest, wäre ich für immer in deiner Tiefe und dann könnte ich das Konzept tatsächlich ein bisschen verstehen :)
Quincy
Der von mir geschriebene Code verwendet die von Ihnen verknüpfte C-Bibliothek, die bereits eine "komplexe" Struktur enthält. Dies macht das in meiner Frage beschriebene
Auspacken
0

Ich habe das noch nicht gemacht oder viel darüber gelesen, aber meine erste Einstellung ist ungefähr so:

Zunächst müssen Sie eine Fensterfunktion anwenden, um mit der FFT ein zeitabhängiges Spektrum zu erhalten. Der Beat liegt normalerweise in den niedrigeren Frequenzen, also wenden Sie eine andere FFT mit einem größeren Zeitfenster auf die Intensitäten einiger dieser Frequenzen an (beginnen Sie der Einfachheit halber mit nur 1 bei z. B. 100 Hz und prüfen Sie, ob dies zuverlässig genug ist). Finden Sie den Peak in diesem Spektrum und diese Frequenz ist eine Vermutung für den Beat.

Tobias Kienzler
quelle
Es ist nicht wirklich die Beat-Erkennung, mit der ich Probleme habe, aber ich verstehe, wie FFT funktioniert. Ich bin wirklich neu in der Signalverarbeitung und Dinge wie: "Wende eine Fensterfunktion an, um mit der FFT ein zeitabhängiges Spektrum zu erhalten" ergeben für mich keinen Sinn. Trotzdem danke :)
Quincy