关于FFT分析音频的小归纳

最近工作上在做关于音乐游戏的内容，其中需要分析音频找节奏点（或者说是重音点）。

学习了一系列相关知识后，了解到一段音乐的波形图可以分解成不同频率的波形图，也就是由时域到频域的转换。

借用其他博主的图就比较容易理解了，如下所示。

波从时域到频域的转换可以通过傅里叶变换实现，关于傅里叶变换的知识可以从最上面的链接学习或者自行查找（傅里叶真厉害！！！）。

计算机处理的音频在时域上是离散的数据，我们可以使用离散傅里叶变换DFT（傅里叶变换在时域和频域上都呈离散的形式）获得频域上的离散数据。

快速傅立叶变换FFT是DFT的快速算法，其核心思路就是分治法的DFT，具体推导可以查看上面的第二个链接。

FFT 代码如下：

　　　　 static void BitReverse(Complex[] cpData, int n)
        {
            Complex temp;
            int lim = 0;
            while ((1 << lim) < n) lim++;
            for (int i = 0; i < n; i++)
            {
                int t = 0;
                for (int j = 0; j < lim; j++)
                {

                    if (((i >> j) & 1) != 0)
                        t |= (1 << (lim - j - 1));
                }
                if (i < t)
                {
                    temp = cpData[i];
                    cpData[i] = cpData[t];
                    cpData[t] = temp;
                } // i < t 防止交换两次
            }
        }

        static void FFT1(Complex[] cpData, bool forward)
        {
            var n = cpData.Length;

            BitReverse(cpData, n);//位反转

            Complex[] omg = new Complex[n];
            for (int i = 0; i < n; i++)
            {
                omg[i] = new Complex((float)Math.Cos(2 * Math.PI * i / n), (float)Math.Sin(2 * Math.PI * i / n));
            }
             Complex temp ;
            for (int step = 2; step <= n; step *= 2)
            {
                int m = step / 2;
                for (int j = 0; j < n; j += step)
                    for (int i = 0; i < m; i++)
                    {//蝶形运算
                        if(forward)
                            temp = omg[n / step * i] * cpData[j + i + m];
                        else
                            temp = omg[n / step * i].Conjugate() * cpData[j + i + m];
                        cpData[j + i + m] = cpData[j + i] - temp;
                        cpData[j + i] = cpData[j + i] + temp;
                    }
            }
        }

Complex是封装的复数类，偷懒不是自己写的，来自这位老哥https://blog.csdn.net/u011583927/article/details/46974341

这个FFT，new了好多对象，效率不是很高。。。

再贴一个直接把复数的实部虚部轮流放在一个数组里直接算的，能快一些。

　　　　 static void Reverse(float[] data, int n)
        {

            int j = 0, k = 0;
            var top = n / 2;
            while (true)
            {

                var t = data[j + 2];
                data[j + 2] = data[k + n];
                data[k + n] = t;
                t = data[j + 3];
                data[j + 3] = data[k + n + 1];
                data[k + n + 1] = t;
                if (j > k)
                {
                    t = data[j];
                    data[j] = data[k];
                    data[k] = t;
                    t = data[j + 1];
                    data[j + 1] = data[k + 1];
                    data[k + 1] = t;

                    t = data[j + n + 2];
                    data[j + n + 2] = data[k + n + 2];
                    data[k + n + 2] = t;
                    t = data[j + n + 3];
                    data[j + n + 3] = data[k + n + 3];
                    data[k + n + 3] = t;
                }

                k += 4;
                if (k >= n)
                    break;

                var h = top;
                while (j >= h)
                {
                    j -= h;
                    h /= 2;
                }
                j += h;
            }
        }
        static void FFT2(float[] data, bool forward)
        {
            var n = data.Length;
            n /= 2;

            Reverse(data, n);


            float sign = forward ? 1 : -1;
            var mmax = 1;
            while (n > mmax)
            {
                var istep = 2 * mmax;
                var theta = sign * (float)Math.PI / mmax;
                float wr = 1, wi = 0;
                var wpr = (float)Math.Cos(theta);
                var wpi = (float)Math.Sin(theta);
                for (var m = 0; m < istep; m += 2)
                {
                    for (var k = m; k < 2 * n; k += 2 * istep)
                    {
                        var j = k + istep;
                        var tempr = wr * data[j] - wi * data[j + 1];
                        var tempi = wi * data[j] + wr * data[j + 1];
                        data[j] = data[k] - tempr;
                        data[j + 1] = data[k + 1] - tempi;
                        data[k] = data[k] + tempr;
                        data[k + 1] = data[k + 1] + tempi;
                    }
                    var t = wr;
                    wr = wr * wpr - wi * wpi;
                    wi = wi * wpr + t * wpi;
                }
                mmax = istep;
            }

        }

　　　　 static void Main(string[] args)
        {

            int n =1024*512;
            float[] data = new float[2 * n];
            for (int i = 0; i < n; i++)
            {
                data[2 * i] = i;
                data[2 * i + 1] = 0;
            }

            Complex[] cpData = new Complex[n];
            for (int i = 0; i < n; i++)
            {
                cpData[i] = new Complex(data[2 * i], data[2 * i + 1]);
            }

            long s = DateTime.Now.Ticks;
            FFT1(cpData, true);
            Console.WriteLine("time:" + (DateTime.Now.Ticks - s) / 10000);

            s = DateTime.Now.Ticks;
            FFT2(data, true);
            Console.WriteLine("time:" + (DateTime.Now.Ticks - s) / 10000);

            Console.Read();
        }

 速度上还是差挺多的。。。

好了获得频率数据之后的流程就不再那么烧脑了（都怪自己早早把傅里叶变换还给课本了）。。。

找节奏点的逻辑大概如下（代码有点多就不贴了）：

1.根据采样率依次获取数据，每次通过FFT得到一组复数数组。

2.计算出复数的模长，可以表示此频率下的声音大小，可以把一定范围的声音累加起来，可以用来表示低音、中音、高音。

3.对比每一帧的数据变化就可以判断出节奏点（声音变化大，可以表示是一个节奏点）。

其实能得到频域的值，针对不同的功能，大家后面就可以自由发挥了。