БПФ библиотека в Android Sdk
Я работаю с проектом Android. Мне нужен алгоритм FFT для обработки данных акселерометра Android. Есть ли библиотека FFT в Android SDK?
5 ответов
Вы можете использовать этот класс, который достаточно быстр для аудио анализа в реальном времени
public class FFT {
int n, m;
// Lookup tables. Only need to recompute when size of FFT changes.
double[] cos;
double[] sin;
public FFT(int n) {
this.n = n;
this.m = (int) (Math.log(n) / Math.log(2));
// Make sure n is a power of 2
if (n != (1 << m))
throw new RuntimeException("FFT length must be power of 2");
// precompute tables
cos = new double[n / 2];
sin = new double[n / 2];
for (int i = 0; i < n / 2; i++) {
cos[i] = Math.cos(-2 * Math.PI * i / n);
sin[i] = Math.sin(-2 * Math.PI * i / n);
}
}
public void fft(double[] x, double[] y) {
int i, j, k, n1, n2, a;
double c, s, t1, t2;
// Bit-reverse
j = 0;
n2 = n / 2;
for (i = 1; i < n - 1; i++) {
n1 = n2;
while (j >= n1) {
j = j - n1;
n1 = n1 / 2;
}
j = j + n1;
if (i < j) {
t1 = x[i];
x[i] = x[j];
x[j] = t1;
t1 = y[i];
y[i] = y[j];
y[j] = t1;
}
}
// FFT
n1 = 0;
n2 = 1;
for (i = 0; i < m; i++) {
n1 = n2;
n2 = n2 + n2;
a = 0;
for (j = 0; j < n1; j++) {
c = cos[a];
s = sin[a];
a += 1 << (m - i - 1);
for (k = j; k < n; k = k + n2) {
t1 = c * x[k + n1] - s * y[k + n1];
t2 = s * x[k + n1] + c * y[k + n1];
x[k + n1] = x[k] - t1;
y[k + n1] = y[k] - t2;
x[k] = x[k] + t1;
y[k] = y[k] + t2;
}
}
}
}
}
Предупреждение: этот код, похоже, является производным от него и имеет лицензию GPLv2.
Использование класса по адресу: https://www.ee.columbia.edu/~ronw/code/MEAPsoft/doc/html/FFT_8java-source.html
Краткое объяснение: вызовите fft(), предоставив x как данные амплитуды, y как массив из всех нулей, после того, как функция вернет ваш первый ответ, будет [0]=x[0]^2+y[0]^2.
Полное объяснение: БПФ является комплексным преобразованием, оно принимает N комплексных чисел и производит N комплексных чисел. Таким образом, x [0] - действительная часть первого числа, y [0] - сложная часть. Эта функция вычисляет на месте, поэтому, когда функция возвращает x, y будет иметь действительные и сложные части преобразования.
Одним из типичных применений является расчет спектра мощности звука. Ваши аудиосэмплы имеют только реальную часть, ваша сложная часть равна 0. Чтобы вычислить спектр мощности, вы добавляете квадрат реальной и сложной частей P [0]=x[0]^2+y[0]^2.
Также важно отметить, что преобразование Фурье при применении к действительным числам приводит к симметричному результату (x [0] == x [x.lenth-1]). Данные в точке x [x.length / 2] имеют данные с частоты f = 0 Гц. x [0] == x [x.length-1] содержит данные для частоты, равной частоте дискретизации (например, если вы выбрали частоту 44000 Гц, это означает, что f [0] относится к 22 кГц).
Полная процедура:
- создать массив p [n] с 512 выборками с нулями
- Соберите 1024 аудиосэмпла, напишите их на х
- Установите y [n] = 0 для всех n
- рассчитать FFT (х, у)
- вычислите p[n]+=x[n+512]^2+y[n+512]^2 для всех n= от 0 до 512
- перейти к 2, чтобы принять другую партию (после 50 партий перейти к следующему шагу)
- сюжет р
- перейти к 1
Чем настроить фиксированный номер на свой вкус.
Число 512 определяет окно выборки, я не буду это объяснять. Просто не уменьшайте это слишком сильно.
Число 1024 должно всегда быть двойным от последнего числа.
Число 50 определяет частоту обновления. Если ваша частота дискретизации составляет 44000 выборок в секунду, частота обновления будет равна: R=44000/1024/50 = 0,85 секунды.
kissfft - достаточно приличная библиотека, которая компилируется на Android. Он имеет более универсальную лицензию, чем FFTW (хотя, по общему признанию, FFTW лучше).
Вы можете найти привязку андроида для kissfft в libgdx https://github.com/libgdx/libgdx/blob/0.9.9/extensions/gdx-audio/src/com/badlogic/gdx/audio/analysis/KissFFT.java
Или, если вы хотите использовать решение на основе чистого Java, попробуйте jTransforms https://sites.google.com/site/piotrwendykier/software/jtransforms
Используйте этот класс (тот, из которого получен ответ EricLarch).
Примечания по использованию
Эта функция заменяет ваши входные массивы выходом FFT.
вход
- N = количество точек данных (размер вашего входного массива должен быть степенью 2)
- X = реальная часть ваших данных для преобразования
- Y = мнимая часть данных для преобразования
т.е. если вы вводите (1 + 8i, 2 + 3j, 7-i, -10-3i)
- N = 4
- Х = (1, 2, 7, -10)
- Y = (8, 3, -1, -3)
Выход
- X = действительная часть вывода БПФ
- Y = мнимая часть вывода БПФ
Чтобы получить ваш классический график БПФ, вам нужно рассчитать величину действительной и мнимой частей.
Что-то вроде:
public double[] fftCalculator(double[] re, double[] im) {
if (re.length != im.length) return null;
FFT fft = new FFT(re.length);
fft.fft(re, im);
double[] fftMag = new double[re.length];
for (int i = 0; i < re.length; i++) {
fftMag[i] = Math.pow(re[i], 2) + Math.pow(im[i], 2);
}
return fftMag;
}
Также смотрите этот ответ Stackru о том, как получить частоты, если ваш исходный вход был величиной в зависимости от времени.
Да, есть JTransforms это поддерживается на github здесь и доступно как плагин Maven здесь.
Использовать с:
compile group: 'com.github.wendykierp', name: 'JTransforms', version: '3.1'
Но с более поздними версиями Gradle вам нужно использовать что-то вроде:
dependencies {
...
implementation 'com.github.wendykierp:JTransforms:3.1'
}
@J Wang Ваша выходная величина кажется лучше, чем ответ, данный в цепочке, которую вы связали, однако она все еще равна квадрату величины... величина комплексного числа
z = a + ib
рассчитывается как
|z|=sqrt(a^2+b^2)
ответ в связанном потоке предполагает, что для чисто реальных входов выходы должны использовать 2 или a для выхода, потому что значения для
a_(i+N/2) = -a_(i),
с b_(i) = a_(i+N/2) это означает, что сложная часть в их таблице находится во второй половине выходной таблицы.
т.е. вторая половина выходной таблицы для входной таблицы вещественных чисел является сопряжением действительного...
так z = a-ia придавать величину
|z|=sqrt(2a^2) = sqrt(2)a
так что стоит отметить факторы масштабирования... Я бы порекомендовал поискать все это в книге или в вики, чтобы быть уверенным.
К сожалению, верхний ответ работает только для массива, размер которого является степенью 2, что очень ограничивает.
Я использовал библиотеку Jtransforms, и она отлично работает, вы можете сравнить ее с функцией, используемой Matlab.
вот мой код с комментариями, относящимися к тому, как Matlab преобразует любой сигнал и получает частотные амплитуды ( https://la.mathworks.com/help/matlab/ref/fft.html)
сначала добавьте следующее в build.gradle (приложение)
implementation 'com.github.wendykierp:JTransforms:3.1'
и вот это код для преобразования простой синусоиды, работает как шарм
double Fs = 8000;
double T = 1/Fs;
int L = 1600;
double freq = 338;
double sinValue_re_im[] = new double[L*2]; // because FFT takes an array where its positions alternate between real and imaginary
for( int i = 0; i < L; i++)
{
sinValue_re_im[2*i] = Math.sin( 2*Math.PI*freq*(i * T) ); // real part
sinValue_re_im[2*i+1] = 0; //imaginary part
}
// matlab
// tf = fft(y1);
DoubleFFT_1D fft = new DoubleFFT_1D(L);
fft.complexForward(sinValue_re_im);
double[] tf = sinValue_re_im.clone();
// matlab
// P2 = abs(tf/L);
double[] P2 = new double[L];
for(int i=0; i<L; i++){
double re = tf[2*i]/L;
double im = tf[2*i+1]/L;
P2[i] = sqrt(re*re+im*im);
}
// P1 = P2(1:L/2+1);
double[] P1 = new double[L/2]; // single-sided: the second half of P2 has the same values as the first half
System.arraycopy(P2, 0, P1, 0, L/2);
// P1(2:end-1) = 2*P1(2:end-1);
System.arraycopy(P1, 1, P1, 1, L/2-2);
for(int i=1; i<P1.length-1; i++){
P1[i] = 2*P1[i];
}
// f = Fs*(0:(L/2))/L;
double[] f = new double[L/2 + 1];
for(int i=0; i<L/2+1;i++){
f[i] = Fs*((double) i)/L;
}