accelerate fft for accelerometer data

[fisherwagon]

HI,
This is my first post.
My goal is do develop an app that displays the frequency of a repetitive motion applied to the iPhone (ex: moving the phone back and forth in the x-direction). People have recommended that I use fft to achieve this. My questions are as follows:

1. I have heard that some apps use the accelerate framework to analyze audio, is there any reason why this would not work for accelerometer data.
2. I am looking for a good introduction/tutorial on fft, and the accelerate framework.
3. Any other thoughts, considerations I have to take, etc...

Thanks for your feedback.

[lgehrig1]

Originally Posted by fisherwagon

HI,
This is my first post.
My goal is do develop an app that displays the frequency of a repetitive motion applied to the iPhone (ex: moving the phone back and forth in the x-direction). People have recommended that I use fft to achieve this. My questions are as follows:

1. I have heard that some apps use the accelerate framework to analyze audio, is there any reason why this would not work for accelerometer data.
2. I am looking for a good introduction/tutorial on fft, and the accelerate framework.
3. Any other thoughts, considerations I have to take, etc...

Thanks for your feedback.

1. The accelerate framework would work fine. FFT doesn't care where the data comes from - it simply converts from the time domain to the frequency domain. You can FFT anything measured as a function of time. You can FFT anything measured as a function of anything, really, but it wouldn't make as much sense

2. Yeah - if you aren't already familiar with Fourier transforms I'd suggest hitting Wikipedia & Wolfram Research (if you've got a good math background) ... and if you don't have a strong math background (to include preferably calculus but at least algebra) ... find a tutor at a local uni.

[fisherwagon]

Thanks for the reply!
I have decent math skills and have read up a little on fft.

1. Most resources I have seen talk about complex number input to fft. Because my accelerometer data is all real should I just enter 0 as the imaginary portion, or am I missing something?

2. I have been playing with Fast Fourier Transform Calculator , and I have been getting confusing results.

if you enter the following time domain data, with a sample rate of 1Hz, and perform the transform...
0.000
0.707
1.000
0.707
0.000
-0.707
-1.000
-0.707
0.000
0.707
1.000
0.707
0.000
-0.707
-1.000
-0.707
... you get complex data for the frequency domain (the magnitude of the complex vector is equal to the amplitude of a specific frequency?).
How do I know which frequency matches each output? I Should be getting one frequency with a much larger amplitude than the others (because the input is a sine wave), but I do not.
THANKS

[lgehrig1]

Originally Posted by fisherwagon

Thanks for the reply!
I have decent math skills and have read up a little on fft.

1. Most resources I have seen talk about complex number input to fft. Because my accelerometer data is all real should I just enter 0 as the imaginary portion, or am I missing something?

Zero is perfectly acceptable for your imaginary portion.

Originally Posted by fisherwagon

2. I have been playing with Fast Fourier Transform Calculator , and I have been getting confusing results.

if you enter the following time domain data, with a sample rate of 1Hz, and perform the transform...
0.000
0.707
1.000
0.707
0.000
-0.707
-1.000
-0.707
0.000
0.707
1.000
0.707
0.000
-0.707
-1.000
-0.707
... you get complex data for the frequency domain (the magnitude of the complex vector is equal to the amplitude of a specific frequency?).
How do I know which frequency matches each output? I Should be getting one frequency with a much larger amplitude than the others (because the input is a sine wave), but I do not.
THANKS

Okay ... the average of your data is zero. And one of the interesting features of a Fourier Transform is that the "zero" (first) element is the average. So I suspect you're choosing a bad window function - and I have no idea what a "window function" is, but selecting anything other than "None" doesn't give you zero as the first term! I suspect the window function improves performance, but (seriously) with 16 terms you don't need an FFT I never studied the math between the Fast part of FFT - I've used FFT libraries and coded simple discrete Fourier transforms - they go remarkably fast on GHz machines

You select no window and you've got your spikes at 0.125 Hz, 0.375 Hz (small), 0.625 Hz (small), and 0.875 Hz. This corresponds perfectly to your period of 8 seconds (0.125 Hz = 1 / 8 sec). Because another feature of Fourier transforms (ONLY where the input only comes from the set of Reals) is that they reflect across the middle: 0.875 Hz is your 1.00 Hz measure - your 0.125 Hz spike.

And 0.375 Hz is a harmonic. And error, because you have discrete measurements not a continuous smooth input. And more error, because it's IEEE floating point. It's easy enough to ignore because it's swamped by your straight 0.125 Hz input signal. The real world won't be as generous - if you strum a guitar you get signals on the notes BUT ALSO harmonics; both signals are valid. But if you're looking for frequency spikes I doubt you'll need to worry.

[fisherwagon]

Thanks. Very helpful.
the 16 values were kindof an easy test to get a predictable outcome.
I played with the fft in matlab today, and things are starting to make a little more sense.
Next, I need to read some vDSP documentation, I guess.

[fisherwagon]

Spent some more time on this.
I sorta understand what the functions do, but I am doing something wrong.
Every time I log the complex split arrays, I only get zeros.
I want to input a set of real values (originalReal), and get the frequency domain info.
Thanks for your help.

#import "DataAnalyzerViewController.h"
#define FBOX(x) [NSNumber numberWithFloat:x]


@implementation DataAnalyzerViewController

-(IBAction) start{
    
   
    NSMutableArray *originalReal = [NSMutableArray arrayWithObjects:
                                FBOX(0), FBOX(4), FBOX(5),FBOX(4), FBOX(0), FBOX(-4),FBOX(-5), FBOX(-4), FBOX(0), FBOX(4), FBOX(5),FBOX(4), FBOX(0), FBOX(-4),FBOX(-5), FBOX(-4), nil];
    
    COMPLEX_SPLIT   A;
    FFTSetup        setupReal;
    int n=16;
    int log2n=4;
    int stride=1;
    int nOver2=n/2;
    float scale;
    
    A.realp = (float *) malloc(nOver2 * sizeof(float));
    A.imagp = (float *) malloc(nOver2 * sizeof(float));
    
    vDSP_ctoz((COMPLEX *) originalReal, 2, &A, 1, nOver2);
    
    NSLog(@"originalReal: %@",originalReal);
    NSLog(@"A: %p", &A);
    
    int i=0;
    for(; i<nOver2; i++){
        NSLog(@"A[%d]=%f, %f", i, A.realp[i], A.imagp[i]);
    }
    
    setupReal = vDSP_create_fftsetup(log2n, FFT_RADIX2);
    
    if (setupReal == NULL) {
        
        printf("\nFFT_Setup failed to allocate enough memory  for"
               
               "the real FFT.\n");
        exit(0);
    }
    
    i=0;
    for(; i<nOver2; i++){
        NSLog(@"A[%d]=%f, %f", i, A.realp[i], A.imagp[i]);
    }

    vDSP_fft_zrip(setupReal, &A, stride, log2n, FFT_FORWARD);

    scale = (float) 1.0/(2*n);
    vDSP_vsmul(A.realp, 1 ,&scale, A.realp, 1, nOver2);
    vDSP_vsmul(A.imagp, 1 ,&scale, A.imagp, 1, nOver2);

    i=0;
    for(; i<nOver2; i++){
        NSLog(@"A[%d]=%f, %f", i, A.realp[i], A.imagp[i]);
    }
}

[shimmy]

Hey, did you ever finish this ? Do you mind posting some guidance about what you've learned? I want to do the exact same thing -- do a fourier transform on accelerometer data.

Accelerometer gives 3D data (x, y, z) but the Accelerate Framework only has 1 or 2 D transforms... Do you just do 1 D for each of the three directions? Or perhaps combine them as an acceleration vector in some way?

OR are you supposed to use the discrete form, since it's a sample?

[fisherwagon]

Originally Posted by shimmy

Hey, did you ever finish this ? Do you mind posting some guidance about what you've learned? I want to do the exact same thing -- do a fourier transform on accelerometer data.

Accelerometer gives 3D data (x, y, z) but the Accelerate Framework only has 1 or 2 D transforms... Do you just do 1 D for each of the three directions? Or perhaps combine them as an acceleration vector in some way?

OR are you supposed to use the discrete form, since it's a sample?

I did eventually get the fft working, but ended up using an algorithm which I made (not an fft variant) to get the desired result. I'm no expert, but here is what I can tell you:
You cannot plug in x, y, and z data into one fft. You have to manipulate the data to get one output. I eventually chose to analyse one axis. If you want to get three separate frequency outputs (one for each axis) you will have to use three ffts.
What your goal?

[shimmy]

Well I want to find the frequencies based on the accelerometer output when you shake the device, for scientific research. I don't think there's anyway around it, and it's definitely do-able. In fact, I just saw an app on the app-store that had pretty much exactly what I want to integrate into my app... too bad I can't get source code for that... Unfortunately, I can't make heads or tails of the Accelerate framework and the documentation is pretty weak.

[fisherwagon]

Yes. Making the fft work was awful. Things you might consider:
1. Do you really need more than one axis? I just did a lab analysing motor vibrations, and only one axis was needed for that.
2. If you have matlab, you might want to use the iphone to collect the data and then plug your results into matlab's fft. There is good documentation for matlab fft. In any event, figuring out how to use matlab's fft was a good preparation to learning iphone fft.

What kind of sampling rates can you get with an iphone accelerometer? If I still have my fft test project at home I may be able to send it to you.

[shimmy]

1. I don't know exactly what I need, although I imagine I might as well take what I can get. (that's research for you...) The shaking is pretty uncontrolled, so I think I probably need all the axes. That said, the question is irrelevant right now, since I don't have the FFT working yet.

2. I appreciate the suggestion, and I'll look into it, but I don't have my own copy of Matlab and my ultimate goal is to have everything integrated into a usable app.

iPhone accelerometer can get very fast sampling rates. I think I was using 60x per second, but I think you can go even faster.

I'd be grateful for any help. Sample code is key.

Thanks

[shimmy]

Ok, just watched a very useful WWDC10 video discussing this, so cleared up a lot of the basics.

What does FFT_RADIX2 do in the setup?

[RLScott]

Originally Posted by shimmy

iPhone accelerometer can get very fast sampling rates. I think I was using 60x per second, but I think you can go even faster.

A high sample rate will not help you get better frequency resolution for the kind of frequencies involved in physical shaking. The theory says that the total sample period is what determines the frequency resolution. For example, if you want freuquency bins that are 0.1 Hz apart, you need to use a sample that is 10 seconds long. The sample rate is irrelevant (up to the Nyquist frequency). So you might as well use a lower sample rate to make it easy on your code.

[tuppari]

Originally Posted by shimmy

Well I want to find the frequencies based on the accelerometer output when you shake the device, for scientific research. I don't think there's anyway around it, and it's definitely do-able. In fact, I just saw an app on the app-store that had pretty much exactly what I want to integrate into my app... too bad I can't get source code for that... Unfortunately, I can't make heads or tails of the Accelerate framework and the documentation is pretty weak.

hii friend,i am interested to get the frequencies using accelerometer(same idea as yours)in my final project.can you please share some info regarding that.how to do that and what coding i have to do in matlab?can you please send any documents regarding that.thanks fot the help

[tuppari]

hii shimmy i am working on the same idea as yours.to get the frequencies using accelerometer when a device is in vibration.can you please share some info regarding this.

[shimmy]

Originally Posted by tuppari

hii shimmy i am working on the same idea as yours.to get the frequencies using accelerometer when a device is in vibration.can you please share some info regarding this.

Sorry, still struggling to get it working.

[tuppari]

Originally Posted by shimmy

Sorry, still struggling to get it working.

if possible can you share any info which you came across,any doc.please

[Duncan C]

Originally Posted by RLScott

A high sample rate will not help you get better frequency resolution for the kind of frequencies involved in physical shaking. The theory says that the total sample period is what determines the frequency resolution. For example, if you want freuquency bins that are 0.1 Hz apart, you need to use a sample that is 10 seconds long. The sample rate is irrelevant (up to the Nyquist frequency). So you might as well use a lower sample rate to make it easy on your code.

The sample rate is NOT irrelevant. The theory says that you need to sample at the Nyquist frequency in order to capture the entire frequency domain of the input signal. If you sample at less than the Nyquist frequency, you will miss high the higher frequency harmonics in your sample signal. (For those who aren't familiar with it, the Nyquist frequency is the sampling rate you need to use in order to capture a given maximum frequency. The Nyquist rate is twice the highest frequency you need to capture. So if you want to capture 20 kHz input signals, you should sample at 40 kHz.

[Duncan C]

Originally Posted by fisherwagon

I did eventually get the fft working, but ended up using an algorithm which I made (not an fft variant) to get the desired result. I'm no expert, but here is what I can tell you:
You cannot plug in x, y, and z data into one fft. You have to manipulate the data to get one output. I eventually chose to analyse one axis. If you want to get three separate frequency outputs (one for each axis) you will have to use three ffts.
What your goal?

You could convert x/y/z accelerometer data to a vector with

sqrt(x^2 + y^2 + z^2)

That would give you the magnitude of the vibration in 3-space. (It's the 3D version of the pythagorean theorem, which lets you calculate distance from x and y changes, but using x, y, and z).

That would probably give the best results, at the cost of being slower, since square root is a transcendental function, and much slower than simple math.


Disclaimer: I'm guessing here based on math knowledge. I'm a software guy, not a sound engineer or signal processing expert.

[RLScott]

Originally Posted by Duncan C

The sample rate is NOT irrelevant. The theory says that you need to sample at the Nyquist frequency in order to capture the entire frequency domain of the input signal. If you sample at less than the Nyquist frequency, you will miss high the higher frequency harmonics in your sample signal. (For those who aren't familiar with it, the Nyquist frequency is the sampling rate you need to use in order to capture a given maximum frequency. The Nyquist rate is twice the highest frequency you need to capture. So if you want to capture 20 kHz input signals, you should sample at 40 kHz.

If the goal is to get the whole frequency spectrum, then you are right. A higher sampling rate is better in that it captures higher frequencies. But if the question is resolution at a particular frequency, then sampling faster will not help. The resolution is totally determined by the total sample period. (e.g. 4096 samples at 22050 samples per second gives the same frequency resolution as 8192 samples at 44100 samples per second.)

Also, regarding taking the magnitude of the acceleration data, it is worth noting that a perfectly circular motion in the x-y plane has a meaningful frequency, but the magnitude of that acceleration data is a constant with no frequency components at all. But in that case both the x and the y acceleration data, taken one at a time, do yield meaningful FFT analysis.

[Duncan C]

Originally Posted by RLScott

If the goal is to get the whole frequency spectrum, then you are right. A higher sampling rate is better in that it captures higher frequencies. But if the question is resolution at a particular frequency, then sampling faster will not help. The resolution is totally determined by the total sample period. (e.g. 4096 samples at 22050 samples per second gives the same frequency resolution as 8192 samples at 44100 samples per second.)

Also, regarding taking the magnitude of the acceleration data, it is worth noting that a perfectly circular motion in the x-y plane has a meaningful frequency, but the magnitude of that acceleration data is a constant with no frequency components at all. But in that case both the x and the y acceleration data, taken one at a time, do yield meaningful FFT analysis.

True enough. How you manipulate the data very much depends on the specific application. Cyclic motion is a different problem than vibration.

[RLScott]

Originally Posted by Duncan C

True enough. How you manipulate the data very much depends on the specific application. Cyclic motion is a different problem than vibration.

Agreed.

[tuppari]

Originally Posted by fisherwagon

Yes. Making the fft work was awful. Things you might consider:
1. Do you really need more than one axis? I just did a lab analysing motor vibrations, and only one axis was needed for that.
2. If you have matlab, you might want to use the iphone to collect the data and then plug your results into matlab's fft. There is good documentation for matlab fft. In any event, figuring out how to use matlab's fft was a good preparation to learning iphone fft.

What kind of sampling rates can you get with an iphone accelerometer? If I still have my fft test project at home I may be able to send it to you.

hey fisherwagon,iam trying to capture the motor vibrations using accelerometer,can you please send the info which you have along with the fft project you did.

regards,
Tuppari

[RLScott]

Originally Posted by tuppari

hey fisherwagon,iam trying to capture the motor vibrations using accelerometer,can you please send the info which you have along with the fft project you did.

regards,
Tuppari

I think the bandwidth required to capture motor vibrations is too high for the accelerometer. You might be better off using the microphone for that.

[shimmy]

So doing the FFT is not as complicated as it seems, once you get the concept of packing (ctoz, ztoc) down; following the documentation's sample code helps a lot, assuming you understand the math behind Fourier transform. However, I'm stumped on a seemingly simple point. If I do a forward Fourier transform, on samples that were taken say, 60 times per second, then in the transformed data I get an array of values which represent the amplitude of the fourier transform. What are the x-axis values? They represent the frequencies, but are the values just spaced by the reciprocal of the sampling frequency? OR something else? I'm not sure if I'm being very clear.