Надежный и быстрый FFT на Java
Так как я не хочу делать это самостоятельно, я ищу хорошую реализацию FFT для Java. Сначала я использовал этот FFT Принстон, но он использует объекты, и мой профилировщик сказал мне, что это не очень быстро из-за этого факта. Так что я снова погуглил и нашел этот: FFT Columbia, который быстрее. Может, один из вас, ребята, знает другую реализацию FFT? Я хотел бы иметь "лучший", потому что мое приложение должно обрабатывать огромное количество звуковых данных, а пользователям не нравится ждать...;-)
С уважением.
5 ответов
FFTW является "самым быстрым преобразованием Фурье на западе" и имеет несколько оболочек Java:
Надеюсь, это поможет!
Поздно к вечеринке - здесь, как чистое решение для Java, для тех, где JNI не вариант. JTransforms
Я написал функцию для БПФ на Java: http://www.wikijava.org/wiki/The_Fast_Fourier_Transform_in_Java_%28part_1%29
Он находится в общественном достоянии, поэтому вы можете использовать эти функции везде (в личных или бизнес-проектах). Просто цитируйте меня в комментариях и отправьте мне ссылку на вашу работу, и все в порядке.
Это полностью надежно. Я проверил его выходные данные по БПФ Mathematica, и они всегда были верны до 15-го десятичного знака. Я думаю, что это очень хорошая реализация FFT для Java. Я написал его на версии J2SE 1.6 и протестировал на версии J2SE 1.5-1.6.
Если вы посчитаете количество инструкций (это намного проще, чем идеальная функция вычисления вычислительной сложности), вы можете ясно увидеть, что эта версия великолепна, даже если она вообще не оптимизирована. Я планирую опубликовать оптимизированную версию, если будет достаточно запросов.
Дайте мне знать, если это было полезно, и скажите мне любой комментарий, который вам нравится.
Я разделяю тот же код прямо здесь:
/**
* @author Orlando Selenu
*
*/
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 readibility).
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 bitreverse 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;
}
}
Я думаю, это зависит от того, что вы обрабатываете. Если вы рассчитываете БПФ за большой промежуток времени, вы можете обнаружить, что это займет некоторое время, в зависимости от того, сколько частотных точек вы хотите. Тем не менее, в большинстве случаев для аудио он считается нестационарным (то есть среднее значение сигналов и дисперсия сильно изменяются со временем), поэтому взятие одного большого FFT ( оценка PSD периодограммы) не является точным представлением. В качестве альтернативы вы можете использовать кратковременное преобразование Фурье, при котором вы разбиваете сигнал на более мелкие кадры и вычисляете БПФ. Размер кадра варьируется в зависимости от того, насколько быстро меняется статистика, для речи она обычно составляет 20-40 мс, для музыки я предполагаю, что она немного выше.
Этот метод хорош, если вы делаете выборку с микрофона, потому что он позволяет вам буферизовать каждый кадр за раз, вычислять fft и давать то, что пользователь чувствует как взаимодействие в режиме реального времени. Потому что 20 мс - это быстро, потому что мы не можем реально почувствовать такую маленькую разницу во времени
Я разработал небольшой тест для проверки различий между c-библиотеками FFTW и KissFFT в речевом сигнале. Да, FFTW высоко оптимизирован, но когда вы берете только короткие кадры, обновляете данные для пользователя и используете только маленький размер fft, они оба очень похожи. Вот пример того, как реализовать библиотеки KissFFT в Android с помощью LibGdx в играх badlogic. Я реализовал эту библиотеку, используя перекрывающиеся фреймы, в приложении для Android, которое я разработал несколько месяцев назад под названием " Улучшение речи для Android".