OpenTerrain

← May 19th 2015 Samsung S5 | ● | May 25th 2015 Least Squares Fitting →

The GPS receivers of smart phones have undergone a considerable evolution: From devices that produce noisy signals with a largely varying accuracy influenced by local conditions and software bugs. To devices with good accuracy and consistent accuracy.

Good accuracy means that GPS positions have an accuracy of ca. 5m under optimal conditions and about 15m under not so optimal conditions. Good accuracy also means that the the GPS startup time, until the device delivers its first signal, is only a couple of seconds and almost immediately afterwards.

Even with those improved accuracies a GPS device of a smartphone is way less accurate than professional devices equipped with so called differential GPS receivers with accuracies in the cm range. This means we have to deal with the following signal characteristics:

• The signal will fluctuate from measurement to measurement with steps of up to 5 meters.
• The signal will wander over time with changing local conditions (visibility of satellites, atmospheric conditions, changing canopy etc. pp.)

While we can’t change the local conditions or factor them out like the differential receivers do, we can deal with the fluctuations of the signal due to the receiver noise. There are two types of fluctuations:

• Fluctuations on startup where overall accuracy is still converging to a better estimate.
• Fluctations during continued use.

To understand the problem better, we assume a GPS signal interval of 3 seconds and a fluctuation of 2.5 meters on the average from measurement to measurement. When standing still, this means that the receiver reports an average speed of 2.5m/3s. That’s 3km/h, almost walking speed. A modern device does not show that velocity, because they are smoothing the locations internally, but nevertheless, the positions fluctuate. For example on my Samsung S5 I get a variation peaking up to 0.3km/h. On my LG L7II, which is one generation beyond, I get a variation peaking up to about 1km/h.

Even with those smaller variations, the recorded tracks looks ugly. How do we get rid of those variations? How do we smooth out the noise?

Considering the GPS receiver as a device that produces a time series of noisy but statistically unrelated measurements, this particular problem has been studied intensively, in particular in the area of sensors and nautical navigation. There exist the following well established solutions to this problem:

• Kalman filterering
• Least Squares Regression
• Sliding Window Averaging
• Outlier removal

Kalman filtering is by far the most sophisticated approach, because it can combine the actual velocity and the recorded location measurements into the actual position with the most statistical and physical likelyhood. On the other hand it makes assumptions on the physical process that when not implemented and understood properly can easily lead to a divergence.

Opposed to that, the least squares methods do only analyze the positional information to find the best fit to the recorded measurements. This may be a less accurate approach, but it is less likely to fail due improper assumptions on the physical model. Note that this does not mean that least squares methods cannot cope with velocity changes, in fact this can be covered by not using a linear least squares fit but a fit on a quadratic model.

The sliding window approach is inferior to the above two methods and cannot be used as a predictor of the actual GPS location, but is quickly coded of course.

Same for the outlier removal approach, which is not able to smooth the GPS locations. This is a prerequisite for derivative calculations like velocity and acceleration.

Given the above principle algorithmic classes, the question is which one do we use to smooth our curve GPS locations to get rid of the 5m variations? Better question is, does the improved accuracy of the Kalman filter justify the coding effort? If we were using a differential GPS we would have to use a Kalman filter to achieve the mentioned accuracies. For a smartphone GPS we do not assume a high accuracy, so it is kind of pointless to apply a extremely sophisticated technique to acquired data that is compromised, anyways.

So let’s look on how to apply a least squares fit to the recorded GPS locations.

← May 19th 2015 Samsung S5 | ● | May 25th 2015 Least Squares Fitting →