Detection of periodic data from a telephone accelerometer

Question

I am developing an Android application and I need to determine the context of the user (when walking or driving at a minimum level)

I use the accelerometer and the sum of all axes to determine the accretion vector. It works very well, as I can see some periodicals while walking. But I have to programmatically determine these programs.

Is there any math function to determine the period in a set of values? I heard that the Fourier transform is applicable for this, but I really don't know how to implement it. It looks pretty complicated :)

Please, help

Answer 1

The easiest way to determine the frequency of data is autocorrelation . It is also quite simple to implement. To get autocorrelation in i , you simply multiply each data point of your data by each data point shifted by i . Here are a few pseudo codes:

 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 

This will give you an array of values. The highest “frequency” is the index with the highest value. Thus, you can extract any periodic parts (usually there are more than one).

Also, I suggest you not try to implement your own FFT in the application. Although this algorithm is very good for learning, there are many errors that are difficult to verify, and it is also likely that your implementation will be much slower than those that are already available. If this is possible on your system, I would suggest you use FFTW , which cannot be surpassed in any respect when it comes to implementing FFT.

EDIT:

An explanation of why this works even for values ​​that are not completely repeated:

The usual and completely correct way to calculate autocorrelation is to subtract the average from your data. Let's say you have [1, 2, 1.2, 1.8 ] . You can then extract 1.5 from each sample, leaving you with [-.5, .5, -.3, .3 ] . Now, if you multiply this by yourself with zero, the negatives will be multiplied by negative and positive positive values, giving (-.5)^2 + (.5)^2 + (-.3)^2 + (.3)^2=.68 . If one negative is shifted, it will be multiplied by positive values ​​giving (-.5)*(.5) + (.5)*(-.3) + (-.3)*(.3) + (.3)*(-.5)=-.64 . When you shift two again, the negatives will be multiplied by negative and positive positives. With the displacement of three, something similar happens for the displacement of one. As you can see, you get positive values ​​at offsets 0 and 2 (periods) and negative values ​​at 1 and 4.

Now, to determine only the period, there is no need to subtract the average value. If you just leave the samples as they are, an average will be added each time you add. Since the same value will be added for each coefficient calculated, the comparison will give the same results as you if you subtract the average first. In the worst case, your data type may end (if you use some kind of integral type), or you can bypass errors when the values ​​start to get large (in case you use a float, this is usually not a problem). In case this happens, first subtract the average and try if your results improve.

The biggest drawback of using autocorrelation compared to some kind of fast Fourier transform is speed. Autocorrelation takes O(n^2) , where only O(n log(n)) is required as FFT. If you need to very often calculate the period of very long sequences, autoscaling may not work in your case.

If you want to know how the Fourier transform works, and that all these things are about the real part and the imaginary part, magnitude and phase (see, for example, the code sent to Manu), I suggest you have a look at this book .

EDIT2:

In most cases, the data is neither completely periodic nor completely chaotic and aperiodic. Usually your data consists of several periodic additions with different strengths. A period is a time difference with which you can move your data to make it look like yourself. Autocorrelation calculates how similar the data is if you change it by a certain amount. Thus, it gives you the power of all possible periods. This means that there is no “repeating value index” because when the data is completely periodic, all indices will be repeated. The index with the strongest value gives you a shift at which the data is most similar to itself. So this index gives a temporary offset, not an index in your data. To understand this, it is important to understand how time series can be considered as consisting of a sum of perfectly periodic functions (sinusoidal basic functions).

If you need to detect this for very long time series, it is usually best to shift the window above your data and simply check the period of this smaller data frame. However, you should be aware that your window will add additional periods to your data that you should be aware of.

More details in the link that I posted in the last editor.

Answer 2

There is also a way to calculate the autocorrelation of your data using FFT, which reduces complexity from O(n^2) to O(n log n) . The main idea is that you take your periodic data samples, convert them using an FFT, then calculate the power spectrum, multiplying each FFT coefficient by its complex conjugation, and then take the inverse FFT of the power spectrum. You can find an existing code for calculating the power spectrum without much difficulty. For example, look at the Android library Moonblink . This library contains the FFTPACK JAVA translation (a good FFT library), as well as some DSP classes for calculating power spectra. The autocorrelation method I have used successfully is the McLeod Pitch Method (MPM), the java source code for which is available here . I edited a method in the McLeodPitchMethod class that allows it to calculate the pitch using an autocorrelation algorithm with FFT optimization:

 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; } } 

Where transformer is a private instance of the FFTTransformer class from the FFTTransformer java transform, and transformerEven is a private instance of the FFTTransformer_Even class. Calling McLeodPitchMethod.getPitch() with your data will give a very efficient estimate of the frequency.

Answer 3

The following is an example of calculating the android Fourier transform using the FFT class from 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); } } 

Further information here: http://www.digiphd.com/android-java-reconstruction-fast-fourier-transform-real-signal-libgdx-fft/