检测来自手机的加速度计周期性数据

Question

我正在开发Android应用程序，我需要检测用户环境（如走路或以最小的驾驶）

我使用加速度计和总和的所有轴检测accleration矢量。它能够在行走时看到一些周期性值的方式工作得很好。但我需要以编程方式检测这些poeriods。

请有任何数学函数的检测设定值的周期？我听说傅里叶变换是可用的，但我真的不知道如何实现它。它看起来很复杂:)

请帮

Answer 1

的检测数据周期的最简单方法是autocorrelation。这也很容易实现。要获取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 

这会给你一个值的数组。最高的“周期性”在具有高值的指数处。这样你可以提取任何周期性的部分（通常有多个）。

而且我建议你不要尝试在应用程序中实现自己的FFT。虽然这个算法对学习非常有用，但是有很多人可以做错误，这很难测试，而且你的实现可能比已经可用的实现慢得多。如果在您的系统上可能的话，我建议您使用在任何方面都无法击败的FFTW。

编辑：

解释，为什么这个工程即使在不exactely重复值：

通常的和完全正确的方式来计算的自相关性，从您的数据。减去平均值。假设你有[1, 2, 1.2, 1.8 ]。然后，您可以从每个样本中提取1.5，然后使用[-.5, .5, -.3, .3 ]。现在，如果你在零OFSET乘这与本身，底片将由阴性和阳性的阳性相乘，得到(-.5)^2 + (.5)^2 + (-.3)^2 + (.3)^2=.68。在一个负值的偏移处将乘以正数产生(-.5)*(.5) + (.5)*(-.3) + (-.3)*(.3) + (.3)*(-.5)=-.64。在两次偏移的情况下，负值将乘以负值和正值乘以正值。在偏移量为3的情况下，类似于偏移量为1的情况再次发生。正如你所看到的，你在1和4

在0和2偏移量（周期）和负值得到正值我们只检测到它是没有必要的。减去平均周期。如果您只是保留样品，每次添加时都会加入平均值。由于每个计算系数都会加上相同的值，因此比较结果与首先减去平均值的结果相同。在最坏的情况或者您的数据类型可能会运行在（如果你使用某种类型的整体式的），或者当值开始变得到大，你可能会舍入误差（如果你使用float，通常这不是一个问题）。如果发生这种情况，首先减去平均值，并尝试如果你的结果变得更好。

使用自相关与某种快速傅里叶变换的最大缺点是速度。自相关需要O(n^2)作为FFT只需要O(n log(n))。如果您需要经常计算非常长的序列的时间段，自动关联可能不适用于您的情况。

如果你想知道傅里叶变换是如何工作的，以及关于实部，虚部，幅度和相位的所有这些东西（例如看看Manu发布的代码）意味着什么，我建议你有看看this book。

EDIT2：

在大多数情况下，数据既不是完全周期性的，也不是完全混乱和非周期性的。通常你的数据将由几个周期性的组成部分组成，具有不同的强度。一个时间段是一个时间差异，您可以通过该时间差异来移动数据以使其与自己类似。自相关计算数据的相似程度，如果将其移入一定数量。因此它给了你所有可能时期的力量。这意味着，没有“重复值的索引”，因为当数据完全周期性时，所有索引都会重复。具有最强价值的指数为您提供了数据与其本身最相似的转变。因此这个索引给出了时间偏移量，而不是数据的索引。为了理解这一点，理解时间序列如何被认为是由完美周期函数（正弦基函数）的和组成是很重要的。

如果你需要检测这个很长的时间序列，通常最好是在你的数据上滑动一个窗口，然后检查这个较小数据帧的周期。但是，您必须注意，您的窗口将为您的数据添加额外的时间段，您必须注意这些时间段。

更多链接我发布在最后的编辑。

Answer 2

这里是计算傅立叶变换的Android使用从libgdx的FFT类的例子：

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/

Answer 3

还有一种方法可以使用FFT计算数据的自相关，从而将复杂度从O(n^2)降至O(n log n)。基本思想是您可以获取周期性采样数据，使用FFT对其进行转换，然后通过将每个FFT系数乘以其复共轭来计算功率谱，然后对功率谱进行逆FFT。您可以找到预先存在的代码来计算功率谱，而不会有太大困难。例如，看看Moonblink android library。这个库包含一个FFTPACK（一个很好的FFT库）的JAVA翻译，它也有一些用于计算功率谱的DSP类。我使用的自相关方法是McLeod Pitch Method（MPM），其源代码为here。我曾在课堂上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是从Java FFTPACK翻译FFTTransformer类的私有实例，transformerEven是FFTTransformer_Even类的私有实例。 用您的数据拨打电话McLeodPitchMethod.getPitch()将给出一个非常有效的频率估计。