Android上实现频域均衡器
作者简介：leilei, 天天P图AND工程师
本文主要分为三个部分：
1、现有的音控贴纸的创建以及渲染流程
2、从时域信息转化成频域信息的FFT算法实现
3、将生成的均衡器贴在3D眼镜的镜片上
一、现有的音控贴纸的创建以及渲染流程
现有的音控贴纸流程如图：
1）在配置文件里配置音控开关，音控幅度等参数
2）根据配置创建对应的滤镜加入滤镜链
3）帧渲染，实时计算音控因子调整贴纸大小
滤镜链的Filter创建较为复杂，不同的filter可以根据StickerItem里的多项参数决定自身是否需要创建：
应用上常用的Filter一般有BaseFilter，比如常用的CopyFilter；或者继承VideoBaseFilter，比如FaceCopyFilter等。音控素材继承自NormalVideoFilter，不但包含了TriggerCtrlItem可以根据多个参数控制参数更新：
而且包含了视频播放器和音频播放器（不再本次讨论范围了）。
NormalVideoFilter在每次要渲染之前都会更新参数，与音控相关的代码最终调用了TriggerCtrlItem的isAudioTriggered()函数，在这里获取分贝大小：
AudioDataManager是管理声音的单例类，默认提供麦克风录制的声音数据，或者接收并保存其他源的声音数据。
DecibelDetector类会异步处理麦克风声音数据频率是80ms/次，使用android系统的AudioRecord类实现。
二、从时域信息转化成频域信息的FFT算法实现
从第一节里可以看到原本音控的声音分贝数据db，来源于AudioDataManager类，默认麦克风的数据来源于DecibelDetector类，下面看看实现：
这里的BUFFER_SIZE是每次采样获得的时域数据长度。
采样频率32kHz、单声道、16位PCM编码方式得到的一个BUFFER_SIZE长度的short数组，即一次采样得到的声音时域数据。
原本的DB数据是这样来的：
简单来说就是对short数组里的每一项取绝对值、求和取平均、取对数再乘上系数。
基于现有的通路，获取FFT数据的函数：
下面详细介绍一下FFT的实现:
FFT是快速傅立叶算法的简称，要了解FFT，需要先介绍DFT，即离散傅立叶算法。
这里有一张DFT时域频域转化的图：
左边是时域的波形，右边是时域的数据。
网上有比较多的DFT或者FFT的介绍，这里我写一下个人理解，仅供参考：
1）DFT
DFT算法是时域转化频域的核心。FFT算法是其优化，所以先介绍DFT，再介绍FFT。
DFT的公式如下：
这里我简化一下输入和输出：
其中x(n)是输入的short数组，X(k)是DFT输出的频域数组，n的范围是[0 , N)，k的范围是[0 , N).
这样DFT算法就把一个N长度的数组x，转化成了新的N长度的数组X。二者的区别是:
x数组的下标是固定的时间段，X数组的下标是固定的频率段，举个例子：x[0]代表0时刻的振幅，x[1]代表40ms时刻的振幅；X[0]代表频率为0的波的振幅总量，X[1]代表频率为20Hz的波的振幅总量。
```
注意：
1）这里的数组的下标意义源于这段声音本身的属性：采样率，声道等.如果采样频率大，在N不变的情况下数组下标的频率间隔越大。
2）不同的FFT算法只能影响频率数据的精度，不能改变其最大的频域范围。
3）由于存在频率混叠，FFT的得到的最大频率是采样率的一半。FFT的数据只有前N/2的数据有效，后一半的数据与前一半数据完全对称。
```
明确了输入和输出结果后，再来看一下展开的DFT的公式：
k = [0, N)。这里X(0)的计算需要从x[0]到x[N-1]的数据，每计算一个X数据，都要遍历一遍输入数据，时间复杂度是O(N^2)。DFT公式的原理和行列式表示比较复杂，留在下篇文章再讲。
2）FFT
FFT算法可以将DFT优化到O(NlogN)的复杂度，这里介绍一下基2点FFT算法。优化DFT算法的经典思路是分治，基2点FFT算法就是2分的DFT算法的一种：
将一个长度为N的输入子集划分成2个N/2的子集分别计算，直到划分长度为2的N/2个子集，最后计算2点DFT即可。
这里不详细展开公式的计算，简单说一下使用时的关键点：划分子集。FFT的划分不是简单折半划分，需要奇偶划分：
X(k)是下标为[0 - N-1]的数据集，划分成G(k)和H(k)；
G(k)的下标为0, 2, 4, ……, N-4, N-2，而H(k)的下标为1, 3, 5, …… ,N-3, N-1。
这里k的范围变了：k = [0, N/2)。
DFT的计算因子，每一轮计算的都只需要计算k次因子。轮次为logN。
1）X(k)的周期为N
2）G(k),H(k)周期为N/2, k的下标均为[0 , N/2)
3）
将上面的公式用蝶形图表示：
这里将N周期的X集合，分解成了N/2周期的G集合和H集合。若N=2，直接得到结果。下面看看N=8的蝶形图：
可以看到左边x(k)的顺序变了，因为奇偶划分的原因。为了方便计算，在自底向上计算FFT之前需要倒序，倒序算法如下：
蝶形图左边的x(k)的下标即为排序算法结果。xin[k]即为排序好的复数数组x(k)。蝶形计算图如下：
cc为复数乘法，cut为复数减法，sum为复数加法。每一轮计算的中间结果都保存在xin对应位置。最终得到了FFT的X(k)结果。更多的实现细节请参考：https://www.cnblogs.com/Free-Thinker/p/4759949.html
三、将生成的均衡器贴在3D眼镜的镜片上
这部分是基于现有的3D贴纸素材实现的。要将均衡器贴在3D镜片上，需要获取当前3D眼镜的镜片材质，再将均衡器贴在上面。3D贴纸的实现使用了gameplay引擎。这里不详细介绍gameplay了（主要是我也不太懂），简单说明一下：
3D贴纸的素材是以node作为单位，在visitScene(Node *node)函数里会解析每一个node（包括镜片里的素材图）。在配置参数重添加“__audio__”的tag来标示使用，在解析的时候保存好该texture即可。
这样就把上部分渲染好的texture关联到了3D上，最后效果图如下：
四、总结
本篇文章主要介绍了将录音从时域数据转化成频域数据的方法，所有代码和具体实现都是基于Android的，其中FFT的代码源于互联网，FFT的讲解部分多半源于K.R.Rao的《快速傅里叶变换:算法与应用》。FFT算法博大精深，本文主要介绍了基2点的FFT的实现，还有基3点，基4点甚至有2维、3维等等FFT算法，如果读者有兴趣，可以参见该书。对于将均衡器贴在3D模型上，其实涉及到了OpenGL的复杂应用，不过得益于现有应用上的优秀的代码封装，哪怕像我这样的新手也能稍作变化，实现比较炫酷的3D音控效果。
参考文献：
【1】https://www.cnblogs.com/luoqingyu/p/5930181.html
【2】 K.R.Rao 等著，万帅等译《快速傅里叶变换:算法与应用》
【3】https://www.cnblogs.com/Free-Thinker/p/4759949.html
文章后记： 天天P图是由腾讯公司开发的业内领先的图像处理，相机美拍的APP。欢迎扫码或搜索关注我们的微信公众号：“天天P图攻城狮”，那上面将陆续公开分享我们的技术实践，期待一起交流学习！
加入我们： 天天P图技术团队长期招聘： (1) AND / iOS 开发工程师 (2) 图像处理算法工程师 期待对我们感兴趣或者有推荐的技术牛人加入我们（base 上海）！联系方式：ttpic_dev@qq.com