How can I find distance traveled with a gyroscope and accelerometer?

Question

I want to build an app that calculates accurate Distance travelled by iPhone (not long distance) using Gyro+Accelerometer. No need for GPS here.

How should I approach this problem?

Solution 1

Basic calculus behind this problem is in the expression

(and similar expressions for displacements in y and z) and basic geometry is the Pythagorean theorem

So, once you have your accelerometer signals passed through a low-pass filter and binned in time with sampling interval dt, you can find the displacement in x as (pardon my C...)

float dx=0.0f;
float vx=0.0f;
for (int i=1; i<n; i++)
 {
   vx+=(acceleration_x[i-1] + acceleration_x[i])/2.0f*dt;
   dx+=vx*dt;
 }

and similarly for dy and dz. Here

float acceleration_x[n];

contains x-acceleration values from start to end of measurement at times 0, dt, 2*dt, 3*dt, ... (n-1)*dt.

To find the total displacement, you just do

dl=sqrt(dx*dx + dy*dy + dz*dz);

Gyroscope is not necessary for this, but if you are measuring linear distances, you can use the gyroscope reading to control that rotation of the device was not too large. If rotation was too strong, make the user re-do the measurement.

Solution 2

You get position by integrating the linear acceleration twice but the error is horrible. It is useless in practice.

Here is an explanation why (Google Tech Talk) at 23:20. I highly recommend this video.

Similar questions:

• track small movements of iphone with no GPS

• What is the real world accuracy of phone accelerometers when used for positioning?

• how to calculate phone's movement in the vertical direction from rest?

• iOS: Movement Precision in 3D Space

• How to use Accelerometer to measure distance for Android Application Development

• Distance moved by Accelerometer

---

Update (24 Feb 2013): @Simon Yes, if you know more about the movement, for example a person walking and the sensor is on his foot, then you can do a lot more. These are called

     domain specific assumptions.

They break miserably if the assumptions do not hold and can be quite cumbersome to implement. Nevertheless, if they work, you can do fun things. See the links in my answer Android accelerometer accuracy (Inertial navigation) at indoor positioning.

Solution 3

You should use the Core Motion interface like described in Simple iPhone motion detect. Especially all rotations can be tracked very accurately. If you plan to do something related to linear movements this is very hard stuff. Have a look at Getting displacement from accelerometer data with Core Motion.

Solution 4

I took a crack at this and gave up (late at night, didn't seem to be getting anywhere). This is for a Unity3d project.

If anyone wants to pick up where I left off, I would be happy to elaborate on what all this stuff does.

Basically after some of what turned out to be false positives, I thought I'd try and filter this using a low pass filter, then attempted to remove bounces by finding a trend, then (acc_x[i-1]+acc_x[i])/2.

It looks like the false positive is still coming from the tilt, which I attempted to remove..

If this code is useful or leads you someplace, please let me know!

using UnityEngine;
using System.Collections.Generic;

/// <summary>
/// [email protected]
/// </summary>
public class AccelerometerInput : MonoBehaviour 
{

    Transform myTransform;
    Gyroscope gyro;
    GyroCam gyroCam;

    void Awake()
    {
        gyroCam= FindObjectOfType<GyroCam> ();
        myTransform = transform;
        if (SystemInfo.supportsGyroscope) {
            gyro = Input.gyro;
            gyro.enabled = true;
        }
    }

    bool shouldBeInitialized = false; 
    void Update () 
    {

        transform.Translate (GetAccelerometer ());// * Time.deltaTime * speed);

        //GetComponent<Rigidbody> ().AddForce (GetAccelerometer ());

    }

    public float speed = 10.0F;

    public Vector3 dir;
    public float f;
    Vector3 GetAccelerometer()
    {

        dir = Input.acceleration;

        dir.x *= gyro.attitude.x;
        dir.z *= gyro.attitude.z;

        if (Mathf.Abs (dir.x) < .001f)
            dir.x = 0;
        dir.y = 0;
        if (Mathf.Abs (dir.z) < .001f)
            dir.z = 0;

        RecordPointsForFilter (dir);

        //print ("Direction : " + dir.ToString("F7"));

        return TestPointsForVelocity();
    }

    Vector3[] points = new Vector3[20];
    int index;
    void RecordPointsForFilter(Vector3 recentPoint)
    {
        if (index >= 20)
            index = 0;
        points [index] = EvaluateTrend (recentPoint);;
        index++;
    }

    //try to remove bounces
    float xTrend = 0;
    float zTrend = 0;
    float lastTrendyX = 0;
    float lastTrendyZ = 0;
    Vector3 EvaluateTrend(Vector3 recentPoint)
    {

        //if the last few points were positive, and this point is negative, don't pass it along
        //accumulate points into a trend
        if (recentPoint.x > 0)
            xTrend += .01f;
        else
            xTrend -= .1f;

        if (recentPoint.z > 0)
            zTrend += .1f;
        else
            zTrend -= .1f;

        //if point matches trend, keep it
        if (xTrend > 0) {
            if (recentPoint.x > 0)
                lastTrendyX = recentPoint.x;
        } else  // xTrend < 0
            if (recentPoint.x < 0)
            lastTrendyX = recentPoint.x;

        if (zTrend > 0) {
            if (recentPoint.z > 0)
                lastTrendyZ = recentPoint.z;
        } else  // xTrend < 0
            if (recentPoint.z < 0)
                lastTrendyZ = recentPoint.z;

        return new Vector3( lastTrendyX, 0, lastTrendyZ);
    }

    Vector3 TestPointsForVelocity()
    {
        float x = 0;
        float z = 0;

        float xAcc = 0;
        float zAcc = 0;

        int successfulHits = 0;
        for(int i = 0; i < points.Length; i++)
        {
            if(points[i]!=null)
            {
                successfulHits ++;
                xAcc += points[i].x;
                zAcc += points[i].z;
            }
        }

        x = xAcc / successfulHits;
        z = zAcc / successfulHits;

        return new Vector3 (x, 0, z);

    }
}

View more solutions

Comments

[Kay]

Nice. I just saw that the questioner has never cast a vote nor accepted an answer, so +1 from me :-) In practice I ran into trouble after a few seconds because of error propagation even with Simpson rule for integration.

[drlemon]

Thanks Kay, I had a suspicion that the devil is in the details, I am sure that it is not impossible to fix. Off the top of my head, accelerometer's response may be nonlinear in amplitude at high frequencies, or they may not be subtracting gravity accurately enough. In both cases, filtering out problem frequencies (probably, everything above 30 Hz must be suppressed) and runtime calibration (hold still for 1 second and measure drift to compensate for it) should help. I guess I have to try it on my Android now.

[drlemon]

Do you know if anyone has tried to find the source of the horrible systematic errors? Does suppressing high frequencies or pre-measurement calibration help?

[Ali]

Watch the video from 23:20, the Google Tech Talk I linked in my answer. It explains why you get that horrible error. Neither filtering nor calibration will help.

[Kay]

It's still an unresolved problem to get accurate results i.e. something you can really use for a game or whatever. Like Ali said David Sachs has done some very research on Android (s. Ali's link to its Google Tech Talk). You might find useful ideas in the link I provided in my answer below. Be prepared to do some heavy maths (Kalman filter and derivatives).

[drlemon]

I don't think they explain anything. He says "There are some ways to improve the linear movement estimate... but any kind of orientation errors are really important, all sorts of error couple in, including things like the cross axis error between the accelerometer and the gyroscope". To me, it looks like they just don't know what is going on, because if they did, they could suggest something to make the results better. Thanks for the video, very informative! I'll have to play with that accelerometer now when I have time.

[Ali]

Upvoted. It's amazing how many times this question pops up and people keep re-inventing the wheel in the shape of a square... :(

[Kay]

@Ali Yes, I plan to write a blog article within the next months about clearing this up and publishing my results (didn't find the solution but some nice workaround) and then post an abstract as FAQ here at SO. Off-topic: I don't know how to contact you by this chat thing :( Are you doing iPhone programming as well? I've got a request (via SO :) for contracting (Prague) but I am busy. Drop me an email via my web-site if you are interested. BTW: Congrats for hitting 2k rep :)))

[Ali]

Thanks :) I just dropped you and e-mail, so you will have my e-mail address for future reference. I was also thinking about writing an article clearing this mess up. Unfortunately, I do not have the time to do so. :( Anyhow, please inform me when you are done with yours, so I can tell people about it!

[Ashwin]

@drlemon : why are you doing - (acc_x[i-1]+acc_x[i])/2?

[Ashwin]

@drlemon : shouldn't this be more accurate? stackoverflow.com/questions/12926459/…

[Simon]

is there any other way to do it precisely? What kind of other electronical devices could be used to get precise measurement?

[Ali]

@Simon Depending on your application you may find my answer helpful (pedometer or RSSI-based localization). The source of the inaccuracy is the white noise of the gyros; with a ring laser gyro (1 pound plus batteries :) ) you can achieve better accuracy and that's what they do on airplanes.

[Simon]

@Ali and what do you think about: x-io.co.uk/products/x-imu it's a bit expensive, but maybe it's worth to build something like this based on Arduino components? How accurate can it be?

[Ali]

@Simon It doesn't help, it's just another MEMS gyro with good marketing. Check the datasheet. However, it is significantly easier to use it as a programmer on the application side, as the hardware does all the complicated things for you. If want to do the double integral, you would need a ring laser gyro instead of the MEMS gyro.

[Simon]

@Ali I've already read about that ring laser gyro (u mentioned it previously), but I think it's a bit out of my range :). I'd like to build something small and quite cheap, so my first thought was to use hardware in phones. The more I read, the more I'm realizing it is too complicated. Later I thought that maybe some external hardware would be better, but as you pointed out, it's the same problem. But int their presentations, it looks quite impressive and is quite accurate (especially presenation with stairs). How much better/worse/faster could it be than hardware + software in Android/IPhone?

[Ali]

@Simon Where is this presentation? Honestly, I didn't spent too much time on that website. I just noticed that it is also a MEMS gyro so same problem. I highly doubt you can do anything significant that could improve the situation: MEMS gyros are not accurate enough to do the double integral.

[Ali]

@Simon OK, I will watch it but I can only do so later. Please give me some time.

[Simon]

I'm gathering information in my spare time, so I'm not expecting you will do it instantly :) Take your time.

[Ali]

@Simon This discussion was accidentally lost. I guess you have moved on, in any case, I updated my answer to respond to your question.

[AlexWien]

the video tells 20cm per second drift, for linear distance estimation. i will not call this horrible. a vehicle driving with 15m/s having only 20cm drift, would not be considered having a horrible drift!

[Ali]

@AlexWien Watch it again from 24:40. The true problem is the orientation error. In that example the drift is 8.5 meters in the first second and it is growing quadratically. That is horrible even for the scenario you described.

[mojuba]

Ali, you seem to have flooded SO with your negative answers under a dozen of identical questions. Although I find your links useful, thanks for that, but I also find it strange that you promote a negative answer to an open question. Look around, there are some interesting answers to it here on SO. What is your motivation really?

[Ali]

@mojuba In a retrospect, I agree, the duplicate questions should have been closed. These days I vote for closing a duplicate question instead of giving the same answer over and over again. I agree with you on this one. As for the "Look around, there are some interesting answers to it here on SO." please give me some links where they indeed solved the issues associated this double integral calculation.

[Ali]

@mojuba "What is your motivation really?" I am giving these answer in a hope that they are useful. I wasted significant time and effort trying to solve the double integral problem and concluded it cannot be done. For me, that time is wasted but I hope I can help others not to waste their time. I only have good intentions. I emphasize again, the duplicate questions should have been closed, I agree with you on that one.

[Ali]

@mojuba By the way, I have been planning to write up what you can do instead of the infamous double integral, just been too busy lately to do so.

[Aki]

@Ali: Any hint about what you can do instead of this? I need to overcome the limitations of this technique as well

[Ali]

@Aki I should know more about your application. But it always boils down to this: use orientation and / or make domain specific assumptions.

[Aki]

@Ali: what would be the domain specific assumptions for tracking a boxer wearing 2 sensors on his gloves?

[Aki]

I mean, it's not like a car, I am using 9 DOF and will be looking for sensor fusion algorithms, but as said in the GoogleTech talk, double integrals are nasty. My only hope would be to use DSAs with Kalman but I can't find any. What if those assumptions are broken sometimes?

[Ali]

@Aki Oh, I tried something similar. Your primary problem will be more serious than the double integral: data loss. At each hit, you will get a huge spike, way outside the range that the sensor can measure. In my situation the solution was to make a video and do image processing... :( In case of the boxer, each hit is also a shock for the sensor; even if you calibrated it perfectly, after a few hits, the measured values are off again. Sorry for the bad news.

[Aki]

@Ali: Well if the spike is there it can at least be used to know when a hit happened, then just forget about the data and fake it by extrapolating previous data? Would it be possible to simply choose not to process spike data and still get accurate results for the rest of the session?

[Ali]

@Aki I highly doubt. :( In my experience, image / video processing is much more fruitful for these type of applications (or at least it was in my case).

[Aki]

@Ali: You are lucky ;). I do need a way around this. I'll keep experimenting until I get something useful. Thanks for your guidance!

[zirinisp]

@Aki What if the application was measure kitesurfing jump height, would the domain specific assumptions be simpler. We should be able to find out the launch and land of the board from the vibration when the board moves on the water. The height of the launch and land point is 90% the same height. Will that help?