Yin基音检测算法：寻求差分函数的高性能替代方案

嘿，作为信号处理领域的从业者，我太懂你遇到的这个问题了——Yin算法里的差分函数用双重循环实现的话，窗口一大就会慢到让人头疼，毕竟时间复杂度是O(n²)，完全扛不住大窗口的计算需求。咱们来一步步拆解优化思路：

先搞懂差分函数的数学本质 #

你贴的差分函数公式展开后其实可以转化为更高效的计算形式：

sum_{n=0}^{N-τ-1} (x[n] - x[n+τ])² = sum(x[n]²) + sum(x[n+τ]²) - 2*sum(x[n]x[n+τ])

其中：

• sum(x[n]²) 和 sum(x[n+τ]²) 其实是同一个值（窗口内音频信号的能量，因为只是平移了τ个采样点，窗口内的能量不变）
• sum(x[n]x[n+τ]) 是信号的自相关函数，而自相关可以用FFT快速计算，时间复杂度直接降到O(n log n)，这比双重循环快了不止一个量级！

具体优化步骤 #

1. 预计算信号能量：先算出整个窗口内信号的能量值，后面直接复用就行。
2. 用FFT计算自相关：通过FFT的卷积定理，自相关等于信号FFT与其共轭FFT的乘积的逆FFT。
3. 代入公式生成差分函数结果：用预计算的能量和自相关结果，代入展开后的公式得到差分函数的每个τ对应的值。

优化后的代码示例（C++） #

这里假设你有可用的FFT库（比如FFTW或者Eigen的FFT模块，也可以用STL的<complex>配合第三方库），下面是核心逻辑的示例：

#include <vector>
#include <complex>
#include <cmath>

// 假设你有一个FFT工具函数，输入实向量，输出复向量的FFT
std::vector<std::complex<double>> fft(const std::vector<double>& data);
// 逆FFT工具函数，输入复向量，输出实向量
std::vector<double> ifft(const std::vector<std::complex<double>>& data);

std::vector<double> optimized_difference(const std::vector<double>& data) {
    int N = data.size();
    int yin_buffer_size = N / 2;
    std::vector<double> yin_buffer(yin_buffer_size, 0.0);

    // 步骤1：计算信号能量
    double signal_energy = 0.0;
    for (double sample : data) {
        signal_energy += sample * sample;
    }

    // 步骤2：用FFT计算自相关
    // 先补零到2N长度（避免循环卷积的混叠）
    std::vector<double> padded_data(2 * N, 0.0);
    std::copy(data.begin(), data.end(), padded_data.begin());
    auto fft_data = fft(padded_data);
    // 计算共轭乘积
    std::vector<std::complex<double>> fft_conj_product(2 * N);
    for (int i = 0; i < 2 * N; ++i) {
        fft_conj_product[i] = fft_data[i] * std::conj(fft_data[i]);
    }
    // 逆FFT得到自相关
    auto autocorrelation = ifft(fft_conj_product);

    // 步骤3：代入公式生成差分函数
    for (int tau = 1; tau < yin_buffer_size; ++tau) {
        // 自相关的第τ个值就是sum(x[n]x[n+τ])
        double ac = autocorrelation[tau];
        yin_buffer[tau] = signal_energy + signal_energy - 2 * ac;
    }

    return yin_buffer;
}

额外的小优化 #

• 避免重复计算：原代码里每次循环都计算delta*delta并累加，其实展开后能减少很多重复运算，上面的公式已经帮你做到了。
• 选择高效的FFT库：如果用FFTW，记得初始化计划（plan）来加速多次FFT计算；Eigen的FFT模块则更轻量，适合嵌入式或小型项目。
• 窗口函数：如果你的音频窗口没有加窗，可以考虑先加汉明窗，减少频谱泄漏，同时也能间接提升基音检测的准确性。

这样优化后，哪怕窗口大小到几千甚至上万，计算速度也会比原代码快很多，完全能满足实时基音检测的需求！

内容的提问来源于stack exchange，提问作者Jedi Nerd