因为我不想自己做,所以我正在寻找一个好的 Java 的 FFT 实现。首先,我在这里使用了这个FFT Princeton,但它使用对象,我的分析器告诉我,由于这个事实,它并不是很快。所以我再次用谷歌搜索,找到了这个:FFT Columbia,速度更快。也许你们中有人知道另一种 FFT 实现?我想要一个“最好的”,因为我的应用程序必须处理大量的声音数据,而用户不喜欢等待......;-)
问候。
迟到了 - 这里是一个纯 Java 解决方案,适用于那些无法使用 JNI 的人。JTransforms
我用 Java 编写了一个 FFT 函数。
我已将其发布在公共领域,因此您可以在任何地方使用这些功能(也适用于个人或商业项目)。只需在致谢名单中引用我并向我发送您作品的链接即可。
完全可靠。我已经根据 Mathematica 的 FFT 检查了它的输出,直到小数点后第 15 位为止它们始终是正确的。我认为这是 Java 的一个优秀的 FFT 实现。我在J2SE 1.6版本上写的,并在J2SE 1.5-1.6版本上测试过。
如果你计算一下指令的数量(它比完美的计算复杂度函数估计简单得多),你可以清楚地看到这个版本很棒,即使它根本没有优化。如果有足够的请求,我计划发布优化版本。
如果有帮助请告诉我,并告诉我您喜欢的任何评论。
我在这里分享相同的代码:
/**
* @author Orlando Selenu
* Originally written in the Summer of 2008
* Based on the algorithms originally published by E. Oran Brigham "The Fast Fourier Transform" 1973, in ALGOL60 and FORTRAN
*/
public class FFTbase {
/**
* The Fast Fourier Transform (generic version, with NO optimizations).
*
* @param inputReal
* an array of length n, the real part
* @param inputImag
* an array of length n, the imaginary part
* @param DIRECT
* TRUE = direct transform, FALSE = inverse transform
* @return a new array of length 2n
*/
public static double[] fft(final double[] inputReal, double[] inputImag,
boolean DIRECT) {
// - n is the dimension of the problem
// - nu is its logarithm in base e
int n = inputReal.length;
// If n is a power of 2, then ld is an integer (_without_ decimals)
double ld = Math.log(n) / Math.log(2.0);
// Here I check if n is a power of 2. If exist decimals in ld, I quit
// from the function returning null.
if (((int) ld) - ld != 0) {
System.out.println("The number of elements is not a power of 2.");
return null;
}
// Declaration and initialization of the variables
// ld should be an integer, actually, so I don't lose any information in
// the cast
int nu = (int) ld;
int n2 = n / 2;
int nu1 = nu - 1;
double[] xReal = new double[n];
double[] xImag = new double[n];
double tReal, tImag, p, arg, c, s;
// Here I check if I'm going to do the direct transform or the inverse
// transform.
double constant;
if (DIRECT)
constant = -2 * Math.PI;
else
constant = 2 * Math.PI;
// I don't want to overwrite the input arrays, so here I copy them. This
// choice adds \Theta(2n) to the complexity.
for (int i = 0; i < n; i++) {
xReal[i] = inputReal[i];
xImag[i] = inputImag[i];
}
// First phase - calculation
int k = 0;
for (int l = 1; l <= nu; l++) {
while (k < n) {
for (int i = 1; i <= n2; i++) {
p = bitreverseReference(k >> nu1, nu);
// direct FFT or inverse FFT
arg = constant * p / n;
c = Math.cos(arg);
s = Math.sin(arg);
tReal = xReal[k + n2] * c + xImag[k + n2] * s;
tImag = xImag[k + n2] * c - xReal[k + n2] * s;
xReal[k + n2] = xReal[k] - tReal;
xImag[k + n2] = xImag[k] - tImag;
xReal[k] += tReal;
xImag[k] += tImag;
k++;
}
k += n2;
}
k = 0;
nu1--;
n2 /= 2;
}
// Second phase - recombination
k = 0;
int r;
while (k < n) {
r = bitreverseReference(k, nu);
if (r > k) {
tReal = xReal[k];
tImag = xImag[k];
xReal[k] = xReal[r];
xImag[k] = xImag[r];
xReal[r] = tReal;
xImag[r] = tImag;
}
k++;
}
// Here I have to mix xReal and xImag to have an array (yes, it should
// be possible to do this stuff in the earlier parts of the code, but
// it's here to readability).
double[] newArray = new double[xReal.length * 2];
double radice = 1 / Math.sqrt(n);
for (int i = 0; i < newArray.length; i += 2) {
int i2 = i / 2;
// I used Stephen Wolfram's Mathematica as a reference so I'm going
// to normalize the output while I'm copying the elements.
newArray[i] = xReal[i2] * radice;
newArray[i + 1] = xImag[i2] * radice;
}
return newArray;
}
/**
* The reference bit reverse function.
*/
private static int bitreverseReference(int j, int nu) {
int j2;
int j1 = j;
int k = 0;
for (int i = 1; i <= nu; i++) {
j2 = j1 / 2;
k = 2 * k + j1 - 2 * j2;
j1 = j2;
}
return k;
}
}
编辑:2022 年 5 月 5 日。好吧......十多年后,我在 GitHub 上发布代码以避免丢失:https://github.com/hedoluna/fft 请随时贡献并向我发送您的意见:) 谢谢!
我想这取决于你正在处理的内容。如果您要在很长一段时间内计算 FFT,您可能会发现它确实需要一段时间,具体取决于您想要的频率点数量。然而,在大多数情况下,音频被认为是非平稳的(即信号均值和方差随时间变化很大),因此采用大型 FFT(周期图 PSD 估计)并不是准确的表示。或者,您可以使用短时傅里叶变换,将信号分解为更小的帧并计算 FFT。帧大小取决于统计数据变化的速度,对于语音通常为 20-40 毫秒,对于音乐我认为它会稍高一些。
如果您从麦克风采样,此方法很好,因为它允许您一次缓冲每一帧,计算 fft 并给出用户感觉的“实时”交互。因为 20ms 很快,因为我们无法真正感知那么小的时间差。
我开发了一个小基准来测试 FFTW 和 KissFFT c 库在语音信号上的差异。是的,FFTW 是高度优化的,但是当您仅拍摄短帧、为用户更新数据并仅使用较小的 fft 大小时,它们都非常相似。以下是如何使用 badlogic games 的 LibGdx 在 Android 中实现 KissFFT 库 的示例。我在几个月前开发的 Android 应用程序中使用重叠框架实现了这个库,名为“Android 语音增强”。
进行 FFT。如果该库可用,它可以通过 JNI 重定向到 FFTW;如果没有,则将使用纯 Java 实现。