从手机的加速度计检测周期性数据 [英] Detecting periodic data from the phone's accelerometer

问题描述

我正在开发一个 Android 应用程序，我需要检测用户上下文(如果步行或开车最少)

I am developing an Android app and I am need to detect user context (if walking or driving at minimal)

我使用加速度计和所有轴的总和来检测加速度矢量.它工作得很好，我可以在走路时看到一些周期值.但我需要以编程方式检测这些 poeriods.

I am using accelerometer and sum of all axes to detect the accleration vector. It is working pretty well in the way I can see some periodics values while walking. But I need to detect these poeriods programmatically.

请问有什么数学函数可以检测一组值中的周期吗?我听说傅立叶变换可以用于那个，但我真的不知道如何实现它.看起来很复杂:)

Please is there any kind of math function to detect period in set of values? I heard Fourier transformation is usable for that, but I really dont know how to implement it. It looks pretty complicated :)

请帮忙

推荐答案

检测数据周期性的最简单方法是 自相关.这也很容易实现.要获得 i 处的自相关，您只需将数据的每个数据点与每个移动了 i 的数据点相乘.这是一些伪代码:

The simplest way to detect periodicity of data is autocorrelation. This is also fairly simple to implement. To get the autocorrelation at i you simply multiply each data point of your data with each data point shifted by i. Here is some pseudocode:

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 "periodicity" is at the index with the highes value. This way you can extract any periodic parts (there usually is more than one).

另外，我建议您不要尝试在应用程序中实现自己的 FFT.虽然这个算法非常适合学习，但有很多错误是难以测试的，而且你的实现也可能比那些已经可用的要慢得多.如果可以在您的系统上使用，我建议您使用 FFTW 这在任何方面都无法击败，当它涉及到 FFT 实现.

Also I would suggest you do not try implement your own FFT in an application. Although this algorithm is very good for learning, there is much one can do wrong which is hard to test and it is also likely that your implementation will be much slower than those which are already available. If it is possible on your system I would suggest you use the FFTW which is impossible to beat in any respect, when it comes to FFT implementations.

解释，为什么这甚至适用于不完全重复的值:

Explanation, why this works even on values which do not repeat exactely:

计算自相关的通常且完全正确的方法是从数据中减去均值.假设您有 [1, 2, 1.2, 1.8 ].然后你可以从每个样本中提取 1.5，留下 [-.5, .5, -.3, .3 ].现在，如果在零偏移处将其与自身相乘，则负数将乘以负数，正数乘以正数，产生 (-.5)^2 + (.5)^2 + (-.3)^2+ (.3)^2=.68.在一个负数的偏移量将乘以正数产生 (-.5)*(.5) + (.5)*(-.3) + (-.3)*(.3) + (.3)*(-.5)=-.64.在两个偏移量处，负数将乘以负数，正数乘以正数.在偏移量为 3 时，类似于偏移量为 1 的情况再次发生.如您所见，偏移量为 0 和 2(周期)时为正值，而在 1 和 4 处为负值.

The usual and fully correct way to calculate the autocorrelation is, to substract the mean from your data. Let's say you have [1, 2, 1.2, 1.8 ]. Then you could extract 1.5 from each sample leaving you with [-.5, .5, -.3, .3 ]. Now if you multiply this with itself at an ofset of zero, negatives will be multiplied by negatives and positives by positives, yielding (-.5)^2 + (.5)^2 + (-.3)^2 + (.3)^2=.68. At an offset of one negatives will be multiplied with positives yielding (-.5)*(.5) + (.5)*(-.3) + (-.3)*(.3) + (.3)*(-.5)=-.64. At an offset of two again negatives will be multiplied by negatives and positives by positives. At offset of three something similar to the situation for an offset of one happens again. As you can see, you get positive values at offsets of 0 and 2 (the periods) and negative values at 1 and 4.

现在只检测周期，不需要减去平均值.如果您将样本保留原样，则每次添加时都会添加 suqared 均值.由于将为每个计算的系数添加相同的值，因此比较将产生与您第一次减去平均值时相同的结果.在最坏的情况下，您的数据类型可能会溢出(如果您使用某种整数类型)，或者当值开始变大时可能会出现舍入错误(如果您使用浮点数，通常这不是问题).如果发生这种情况，请先减去平均值，然后尝试结果是否更好.

Now to only detect the period it is not necessary to substract the mean. If you just leave the samples as-is, the suqared mean will be added at each addition. Since the same value will be added for each calculated coefficient, the comparison will yield the same results as if you first subtracted the mean. At worst either your datatype might run over (in case you use some kind of integral type), or you might get round off errors when the values start getting to big (in case you use float, usually this is not a problem). In case this happens first substract the mean and try if your results get better.

使用自相关与某种快速傅立叶变换的最大缺点是速度.Autocorelation 需要 O(n^2)，而 FFT 只需要 O(n log(n)).如果您需要经常计算非常长序列的周期，自相关可能不适用于您的情况.

The strongest drawback of using autocorrelation vs. some kind of fast fourier transformation is the the speed. Autocorelation takes O(n^2) where as a FFT only takes O(n log(n)). In case you need to calculate the period of very long sequences very often, autocorelation might not work in your case.

如果你想知道傅立叶变换是如何工作的，以及所有这些关于实部、虚部、幅度和相位的东西(例如看看 Manu 发布的代码)意味着什么，我建议你有一个看看这本书.

If you want to know how the fourier transformation works, and what all this stuff about real part, and imaginary part, magnitude and phase (have a look at the code posted by Manu for example) means, I suggest you have a look at this book.

在大多数情况下，数据既不是完全周期性的，也不是完全无序和非周期性的.通常，您的数据将由几个具有不同强度的周期性组件组成.一个时期是一个时差，您可以通过它移动数据以使其与其自身相似.如果将数据移动一定量，自相关计算数据的相似程度.因此，它为您提供所有可能时期的强度.这意味着，不存在重复值索引"，因为当数据完全周期性时，所有索引都会重复.具有最强值的索引为您提供数据与其自身最相似的偏移.因此，该索引给出了时间偏移，而不是数据的索引.为了理解这一点，重要的是要了解如何将时间序列视为由完美周期函数(正弦基函数)的总和组成.

In most cases data is neither fully periodic nor fully chaotic and aperiodic. Usually your data will be composed of several periodic compenents, with varying strength. A period is a time difference by which you can shift your data to make it similar to itself. The autocorrelation calculates how similar the data is, if you shift it by a certain amount. Thus it gives you the strength of all possible periods. This means, there is not "index of repeating value", because when the data is perfectly periodic, all indexes will repeat. The index with the strongest value, gives you the shift, at which the data is most similar to itself. Thus this index gives a time offset, not an index into your data. In order to understand this, it is important to understand, how a time series can be thought of as being made up of the sum of perfectly periodic functions (sinusoidal base functions).

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

If you need to detect this for very long time series, it is usually also best to slide a window over your data and just check for the period of this smaller data frame. However you have to be aware that your window will add additional periods to your data, of which you have to be aware.

我在上次编辑中发布的链接中有更多内容.

More in the link I posted in the last edit.

这篇关于从手机的加速度计检测周期性数据的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！