Deteksi detak dan FFT

13

Saya sedang mengerjakan game platformer yang mencakup musik dengan deteksi ketukan. Saat ini saya mendeteksi ketukan dengan memeriksa kapan amplitudo saat ini melebihi sampel historis. Ini tidak bekerja dengan baik dengan genre musik, seperti rock, yang memiliki amplitudo yang cukup mantap.

Jadi saya melihat lebih jauh dan menemukan algoritma yang membelah suara menjadi beberapa band menggunakan FFT ... kemudian saya menemukan algoritma Cooley-Tukey FFt

Satu-satunya masalah yang saya alami adalah bahwa saya cukup baru untuk audio dan saya tidak tahu bagaimana menggunakannya untuk membagi sinyal menjadi beberapa sinyal.

Jadi pertanyaan saya adalah:

Bagaimana Anda menggunakan FFT untuk membagi sinyal menjadi beberapa band?

Juga untuk orang-orang yang tertarik, ini adalah algoritma saya di 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
sumber
Saya kira titik awal yang baik adalah entri FFT dan DSP wikipedia . Entri pendeteksi ketukan jarang tetapi tautan ke sebuah artikel di gamedev.net
Tobias Kienzler

Jawaban:

14

Nah, jika sinyal input Anda nyata (seperti, setiap sampel adalah bilangan real), spektrumnya akan simetris dan kompleks. Mengeksploitasi simetri, biasanya algoritma FFT mengemas hasilnya dengan memberikan Anda kembali hanya setengah positif dari spektrum. Bagian nyata dari masing-masing band adalah dalam sampel genap dan bagian imajiner dalam sampel aneh. Atau kadang-kadang bagian-bagian yang nyata dikemas bersama di paruh pertama respons dan bagian imajiner di babak kedua.

Dalam rumus, jika X [k] = FFT (x [n]), Anda memberinya vektor i [n] = x [n], dan mendapatkan output o [m], maka

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

(meskipun terkadang Anda mendapatkan X [k] = o [k] + j · o [k + K / 2], di mana K adalah panjang jendela Anda, 1024 dalam contoh Anda). Omong-omong, j adalah unit imajiner, sqrt (-1).

Besarnya pita dihitung sebagai akar dari produk pita ini dengan konjugat kompleksnya:

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

Dan energi didefinisikan sebagai kuadrat besarnya.

Jika kita memanggil a = o [2k] dan b = o [2k + 1], kita dapatkan

X[k] = a + j·b

karena itu

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

Membuka gulungan semuanya, jika Anda mendapatkan o [m] sebagai output dari algoritma FFT, energi dalam band k adalah:

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

(Catatan: Saya menggunakan simbol · untuk menunjukkan perkalian alih-alih yang biasa * untuk menghindari kebingungan dengan operator konjugasi)

Frekuensi pita k, dengan asumsi frekuensi pengambilan sampel 44.1KHz dan jendela 1024 sampel, adalah

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

Jadi, misalnya, band pertama Anda k = 0 mewakili 0 Hz, k = 1 adalah 43 Hz, dan yang terakhir k = 511 adalah 22KHz (frekuensi Nyquist).

Saya harap ini menjawab pertanyaan Anda tentang bagaimana Anda mendapatkan energi dari sinyal per band menggunakan FFT.

Tambahan : Menjawab pertanyaan Anda di komentar, dan dengan asumsi Anda menggunakan kode dari tautan yang Anda poskan dalam pertanyaan (Algoritma Cooley-Tukey dalam C): Katakanlah Anda memiliki data input Anda sebagai vektor int pendek:

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

C saya agak berkarat (saya kebanyakan mengkode dalam C ++ saat ini), tapi saya harap saya tidak membuat kesalahan besar dengan kode ini. Tentu saja jika Anda tertarik pada energi dari band lain, tidak masuk akal untuk mengubah seluruh jendela untuk masing-masing, itu akan membuang-buang waktu CPU. Dalam hal itu lakukan transformasi sekali dan dapatkan semua nilai yang Anda butuhkan dari xout.

CeeJay
sumber
Oh, saya baru saja melihat kode yang Anda tautkan, itu sudah memberi Anda hasil dalam bentuk "kompleks" dan bahkan memberi Anda fungsi untuk menghitung besarnya bilangan kompleks. Maka Anda hanya perlu menghitung kuadrat sebesar itu untuk setiap elemen vektor output, tidak perlu khawatir tentang penyortiran hasil.
CeeJay
Sebagai contoh jika saya memiliki semua sampel 1024 dari jendela 0-1024 dan saya mendapatkannya sebagai nilai nyata, jadi tidak ada bagian yang kompleks. dan saya ingin menghitung energi di sana pada pita frekuensi 43Hz. Bagaimana saya mengintegrasikannya? (Saya hanya perlu bagian nyata kembali, bagian postive) Jika Anda bisa melakukannya dalam pseudocode saya akan berada di kedalaman Anda selamanya dan kemudian saya mungkin benar-benar memahami konsep ini sedikit :)
Quincy
Kode yang saya tulis menggunakan pustaka C yang Anda tautkan, yang sudah berisi struktur "kompleks". Ini membuat pembatalan yang saya jelaskan dalam pertanyaan saya tidak perlu (dan kodenya mencerminkan itu)
CeeJay
0

Saya belum melakukan ini atau membaca banyak tentang hal itu sendiri, tetapi kesempatan pertama saya adalah seperti ini:

Pertama-tama, Anda harus menerapkan fungsi jendela untuk mendapatkan spektrum tergantung waktu dengan FFT. Ketukan biasanya terletak pada frekuensi yang lebih rendah, jadi terapkan FFT lain dengan jendela waktu yang lebih besar pada intensitas beberapa frekuensi ini (untuk kesederhanaan mulailah dengan hanya 1 pada misalnya 100 Hz dan lihat apakah itu cukup dapat diandalkan). Temukan puncak dalam spektrum ini dan frekuensi itu adalah perkiraan untuk ketukan.

Tobias Kienzler
sumber
Sebenarnya bukan deteksi ketukan yang saya alami tetapi memahami bagaimana FFT bekerja. Saya benar-benar baru dalam pemrosesan sinyal dan hal-hal seperti: "terapkan fungsi jendela untuk mendapatkan spektrum bergantung waktu dengan FFT" tidak masuk akal bagi saya. Bagaimanapun, terima kasih :)
Quincy