Обнаружение периодических данных от акселерометра телефона

Question

Я занимаюсь разработкой приложения для Android, и мне нужно определить контекст пользователя (если ходьба или вождение минимальны)

Я использую акселерометр и сумму всех осей для определения вектора ускорения. Это работает довольно хорошо, так как я могу видеть некоторые значения периодики во время ходьбы. Но мне нужно определить эти периоды программно.

Пожалуйста, есть ли математическая функция для определения периода в наборе значений? Я слышал, что для этого можно использовать преобразование Фурье, но я действительно не знаю, как его реализовать. Это выглядит довольно сложно:)

Пожалуйста, помогите

Answer 1

Самым простым способом определения периодичности данных является автокорреляция .Это также довольно просто реализовать.Чтобы получить автокорреляцию на i, вы просто умножаете каждую точку данных ваших данных на каждую точку данных, смещенную на i.Вот некоторый псевдокод:

for i = 0 to length( data ) do
  autocorrel[ i ] = 0;
  for j = 0 to length( data ) do
     autocorrel[ i ] += data( j ) * data( ( j + i ) mod length( data ) )
  done
done

Это даст вам массив значений.Наибольшая «периодичность» находится у индекса с наибольшим значением.Таким образом, вы можете извлекать любые периодические части (обычно их больше одной).

Кроме того, я бы посоветовал вам не пытаться внедрять свои собственные БПФ в приложение.Несмотря на то, что этот алгоритм очень хорош для обучения, многое можно сделать неправильно, что сложно проверить, и вполне вероятно, что ваша реализация будет намного медленнее, чем те, которые уже доступны.Если это возможно в вашей системе, я бы посоветовал вам использовать FFTW , который невозможно превзойти, когда дело доходит до реализации FFT.

РЕДАКТИРОВАТЬ:

Объяснение, почему это работает даже для значений, которые не повторяются в точности:

Обычный и полностью правильный способ расчета автокорреляции состоит в том, чтобы вычесть среднее значение из ваших данных.Допустим, у вас есть [1, 2, 1.2, 1.8 ].Затем вы можете извлечь 1,5 из каждого образца, оставив вас с [-.5, .5, -.3, .3 ].Теперь, если вы умножите это на себя при нулевом значении, негативы будут умножены на негативы, а позитивы на позитивы, что даст (-.5)^2 + (.5)^2 + (-.3)^2 + (.3)^2=.68.При смещении в 1 негативы будут умножены на позитивы, дающие (-.5)*(.5) + (.5)*(-.3) + (-.3)*(.3) + (.3)*(-.5)=-.64.При смещении в два раза негативы будут умножаться на негативы, а позитивы - на позитивы.При смещении три снова происходит что-то похожее на ситуацию смещения.Как видите, вы получаете положительные значения со смещением 0 и 2 (периоды) и отрицательные значения при 1 и 4.

Теперь для определения только периода не нужно вычитать среднее значение.Если вы просто оставляете образцы как есть, среднее значение suqared будет добавляться при каждом добавлении.Поскольку для каждого вычисленного коэффициента будет добавлено одно и то же значение, сравнение даст такие же результаты, как если бы вы сначала вычли среднее значение.В худшем случае либо ваш тип данных может быть переполнен (если вы используете какой-то целочисленный тип), либо вы можете получить ошибки округления, когда значения начинают становиться большими (в случае, если вы используете float, обычно это не проблема).Если это произойдет, сначала вычтите среднее значение и попробуйте, если ваши результаты улучшатся.

Самый сильный недостаток использования автокорреляции по сравнению с каким-либо быстрым преобразованием Фурье - это скорость.Автокорреляция занимает O(n^2), тогда как для БПФ - O(n log(n)).Если вам нужно вычислять период очень длинных последовательностей очень часто, автокорреляция может не сработать в вашем случае.

Если вы хотите знать, как работает преобразование Фурье, и что все это говорит о реальной части, имнимая часть, величина и фаза (посмотрите на код, выложенный, например, Ману) означает, я предлагаю вам взглянуть на эту книгу .

EDIT2:

В большинстве случаев данные не являются ни полностью периодическими, ни полностью хаотичными и апериодическими.Обычно ваши данные состоят из нескольких периодических компонентов различной силы.Период - это разница во времени, на которую вы можете сместить ваши данные, чтобы они стали похожими на себя.Автокорреляция вычисляет, насколько похожи данные, если вы сдвинете их на определенную величину.Таким образом, это дает вам силу всех возможных периодов.Это означает, что не существует «индекса повторяющегося значения», потому что, когда данные являются идеально периодическими, все индексы будут повторяться.Индекс с самым сильным значением дает вам сдвиг, при котором данные наиболее похожи на себя.Таким образом, этот индекс дает временной сдвиг, а не индекс ваших данных.Чтобы понять это, важно понять, как временной ряд можно представить как составной из суммы идеально периодических функций (синусоидальных базовых функций).

Если вам нужно обнаружить это для очень длинных временных рядов, обычно также лучше скользить в окне над вашими данными и просто проверять период этого меньшего фрейма данных.Однако вы должны знать, что ваше окно добавит дополнительные периоды к вашим данным, о которых вы должны знать.

Подробнее по ссылке, которую я разместил в последнем редакторе.

Answer 2

Существует также способ вычисления автокорреляции ваших данных с использованием БПФ, который уменьшает сложность с O(n^2) до O(n log n).Основная идея заключается в том, что вы берете свои периодические выборочные данные, преобразуете их с использованием БПФ, затем вычисляете спектр мощности, умножая каждый коэффициент БПФ на его комплексное сопряжение, а затем берете обратное БПФ спектра мощности.Вы можете найти уже существующий код для вычисления спектра мощности без особых трудностей.Например, посмотрите на библиотеку Android Moonblink .Эта библиотека содержит JAVA-перевод FFTPACK (хорошая библиотека FFT), а также имеет несколько классов DSP для вычисления спектров мощности.Метод автокорреляции, который я успешно использовал, - это метод McLeod Pitch (MPM), исходный код Java для которого доступен здесь .Я отредактировал метод в классе McLeodPitchMethod, который позволяет ему вычислять высоту тона, используя алгоритм автокорреляции, оптимизированный для FFT:

private void normalizedSquareDifference(final double[] data) {
    int n = data.length;
    // zero-pad the data so we get a number of autocorrelation function (acf)
    // coefficients equal to the window size
    double[] fft = new double[2*n];
        for(int k=0; k < n; k++){
        fft[k] = data[k];
    }
    transformer.ft(fft);
    // the output of fft is 2n, symmetric complex
    // multiply first n outputs by their complex conjugates
    // to compute the power spectrum
    double[] acf = new double[n];
    acf[0] = fft[0]*fft[0]/(2*n);
    for(int k=1; k <= n-1; k++){
        acf[k] = (fft[2*k-1]*fft[2*k-1] + fft[2*k]*fft[2*k])/(2*n);
    }
    // inverse transform
    transformerEven.bt(acf);
    // the output of the ifft is symmetric real
    // first n coefficients are positive lag acf coefficients
    // now acf contains acf coefficients
    double[] divisorM = new double[n];
    for (int tau = 0; tau < n; tau++) {
        // subtract the first and last squared values from the previous divisor to get the new one;
        double m = tau == 0 ? 2*acf[0] : divisorM[tau-1] - data[n-tau]*data[n-tau] - data[tau-1]*data[tau-1];
        divisorM[tau] = m;
        nsdf[tau] = 2*acf[tau]/m;
    }
}

Где transformer является частным экземпляром класса FFTTransformer изперевод Java FFTPACK, а transformerEven является частным экземпляром класса FFTTransformer_Even.Звонок на номер McLeodPitchMethod.getPitch() с вашими данными даст очень эффективную оценку частоты.

Answer 3

Вот пример вычисления андроида преобразования Фурье с использованием класса FFT из libgdx:

    package com.spec.example;
import android.app.Activity;
import android.os.Bundle;
import com.badlogic.gdx.audio.analysis.FFT;
import java.lang.String;
import android.util.FloatMath;
import android.widget.TextView;

public class spectrogram extends Activity {
    /** Called when the activity is first created. */
    float[] array = {1, 6, 1, 4, 5, 0, 8, 7, 8, 6, 1,0, 5 ,6, 1,8,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0};
    float[] array_hat,res=new float[array.length/2];
    float[] fft_cpx,tmpr,tmpi;
    float[] mod_spec =new float[array.length/2];
    float[] real_mod = new float[array.length];
    float[] imag_mod = new float[array.length];
    double[] real = new double[array.length];
    double[] imag= new double[array.length];
    double[] mag = new double[array.length];
    double[] phase = new double[array.length];
    int n;
    float tmp_val;
    String strings;
    FFT fft = new FFT(32, 8000);
    @Override
    public void onCreate(Bundle savedInstanceState) {
        super.onCreate(savedInstanceState);
        TextView tv = new TextView(this);

       fft.forward(array);
       fft_cpx=fft.getSpectrum();
       tmpi = fft.getImaginaryPart();
       tmpr = fft.getRealPart();
      for(int i=0;i<array.length;i++)
       {
           real[i] = (double) tmpr[i];
           imag[i] = (double) tmpi[i];
           mag[i] = Math.sqrt((real[i]*real[i]) + (imag[i]*imag[i]));
           phase[i]=Math.atan2(imag[i],real[i]);

           /****Reconstruction****/        
           real_mod[i] = (float) (mag[i] * Math.cos(phase[i]));
           imag_mod[i] = (float) (mag[i] * Math.sin(phase[i]));

       }

       fft.inverse(real_mod,imag_mod,res);
   }
}

Подробнее здесь: http://www.digiphd.com/android-java-reconstruction-fast-fourier-transform-real-signal-libgdx-fft/