Geo-positioning is focused on understanding where a connected or mobile device is at a certain point in time. There are multiple ways to derive the location of a mobile device, such as A-GPS, Wi-Fi, Cellular ID, Bluetooth or a hybrid combination of all of these. Wi-Fi and GPS (GNSS more generically) are often widely available, but due to a variety of factors they are not always reliable on their own. As you evaluate various positioning methods, make sure that you have a solid understanding of how to measure and compare the location reported, and how to understand reported error estimates.
How to Evaluate Location Accuracy
When measuring location accuracy, there are some important steps to follow to ensure you have the necessary data. Each of these steps are expanded on within this post.
- Survey a large number of indoor and outdoor test location points and collect ground truth, or the actual location, for all the test points. This will serve as your comparison point once each method has returned location.
- Compute and generate a Cumulative Distribution Function (CDF) plot of positioning errors across multiple percentiles.
- Compute and evaluate legitimacy of reported Horizontal Positioning Error (HPE) metrics, validated with ground truth for device location.
How to Measure Error in Location
It is important to understand error when measuring the accuracy of a location. The two main measures of error listed below are commonly misused, but it is important to distinguish and understand how they’re different.
-
Actual Error: The difference in distance between the actual location of a device (also known as Ground Truth) and the location that is reported from a positioning system. This may also be referred to as True Error or Absolute Error.
- Estimated Error: The measure of uncertainty in the accuracy provided by a positioning system. This is measured in meters relative to latitude and longitude coordinates.
The graphic below demonstrates how calculated location compares to the estimated horizontal accuracy.
How to Compare Location Methods and Understand Positioning Performance Metrics
For example, what does it mean when a positioning system reports an accuracy of 14 meters? This depends on the statistical method and metrics being used to evaluate accuracy. If you are comparing the accuracy of two different systems, it’s key to use the same metrics to evaluate performance.
The most common positioning performance metrics are:
- Cumulative Distribution Function (CDF) of Positioning Error
- Horizontal Estimate of Positioning Error (HPE)
Cumulative Distribution Function (CDF) of Positioning Error
This metric is computed by measuring the absolute distance between the reported location estimate and the exact location of the target device. To use CDF effectively, you need to determine the latitude and longitude that is classified as ground truth yourself, and need to be very confident in their accuracy. This step is one reason why using this metric for performance evaluation is the considered more complex and time-consuming.
To ensure a reliable and accurate performance evaluation, it is also important to use a statistically significant sample size of test points and locations. For example, we recommend that at least several thousand test points be used when evaluating accuracy for a given city.
Once the absolute location error (distance from ground truth) is computed for each test location, a CDF of errors can be created to get a statistical picture of location performance. An easy way to do this, is to sort all location errors in ascending order, then compute the CDF of errors at different percentiles. For example, 50% of the errors would be in the middle of the sorted list, so a CDF error of 30 meters at 50% means that half of the locations have an error of 30 meters or less.
When comparing accuracy performance using a CDF of errors, it is important to compare results at a few percentiles. The most commonly used are:
- 50% - Median error.
- 68% - One standard deviation (sigma) from the mean error.
- 80% - FCC requirements for E-911 call accuracy are set at this percentile.
- 95% - Two standard deviations (two sigma) from the mean error. This means only 5% of locations will have a higher error.
- 99 % - Three standard deviations (three sigma) from the mean error. This means only 1% of locations will have a higher error.
It is often convenient to plot a positioning error for all percentiles (1% to 100%) to study how positioning systems perform. Here is an example:
Comparing Cumulative Distribution Function (CDF) of Positioning Error in Location Systems
Comparing CDF error results from different location systems can be difficult due to varying algorithms and trade-offs between yield (percentage of time a location is returned) and accuracy (distance to ground truth). When comparing CDFs between location systems, the best way to get an accurate comparison is to ensure that the same procedure is used for measuring CDF error results so there is an accurate, apple to apples comparison. A few methods that Skyhook has seen used for improving accuracy metrics over yield include:
- Not including an error value for individual location requests which produced poor or no results.
- Not including an error value for individual location requests with single access point locations, or a low number of access points.
These methods simply exclude locations with poor performance to make the system seem better than it is. Neither of these approaches will provide the whole picture/accurate information about the system. Saying that, while many systems do not return single access point locations intentionally, this and other similar logic needs to be taken into account to accurately compare different systems or methods.
To build the best one-size-fits-all location solution, Skyhook has chosen to implement algorithms and fallback logic to maximize yield. This results in the algorithm always giving the best possible location of any sort, instead of returning a failed location in the majority of cases.
This gives our customers and partners the ability to use the best available location result depending on the use case, while also allowing the option to filter out locations above a certain error estimation value. Therefore, when evaluating performance, we recommend that failed location results get assigned a high error (for example 100,000 meters) before computing the CDF, in addition to computing the yield (percent of failed locations).
Horizontal Estimate of Positioning Error (HPE)
Another metric used for evaluating positioning performance is based on estimating error, instead of computing it (as in the previous section). Known as HPE, Accuracy, and Uncertainty, this metric reflects an estimate that is a location fix within a certain geographical shape and confidence level. It is often calculated by the positioning system and reported together with estimated location. As a result, the definition and quality of this metric heavily depends on the positioning system being used.
There are many different definitions for reporting an estimate of the positioning error. Here are the most common definitions:
- Uncertainty Circle at 68% confidence - This is characterized as a circle with radius R around the coordinates of the reported location fix. Statistically it means that 68% of the time the location fix will be within this circle with radius R.
- Uncertainty Circle at 95% confidence - This is characterized as a circle with radius R around the coordinates of the reported location fix. Statistically it means that 95% of the time the location fix will be within this circle with radius R.
Keep in mind that a system that is reporting a horizontal error estimate at 95% confidence, will report a larger circle radius compared to system reporting error estimate at 68% confidence. This does not mean that the accuracy is worse. See this visualized in the graphic below.
- Uncertainty Ellipse - This is characterized as coordinates of an ellipsoid point (the origin), distances r1 and r2 and an angle of orientation A. It describes formally the set of points on the ellipsoid that fall within or on the boundary of an ellipse with a semi-major axis of length r1 oriented at angle A (0 to 180o) measured clockwise from north and semi-minor axis of length r2, the distances being the geodesic distance over the ellipsoid.
- Polygons – Polygons are arbitrary shapes described by an ordered series of points. They are not very common, since they can be very difficult to display, despite being technically possible.
Using Horizontal Estimate of Positioning Error
The perceived advantage of HPE for accuracy comparisons is that it doesn’t require a survey or knowing the ground truth of each test point. That makes performance evaluations using this method much easier, but less reliable. In nearly all cases, Skyhook recommends evaluating using ground truth instead of error estimate as most companies don’t have large enough sample sets to make the comparison statistically relevant. Typically, this metric is computed based on statistical quality and correlation of measurements used to derive a location fix. For example, if Wi-Fi measurements used to compute a location fix agree with each other, the HPE will be low. If GPS pseudo-range measurements from different satellites point to different locations, the reported HPE will be high.
Location vendors may report a very low HPE at a 68% confidence circle radius (5 meters, for example) but that doesn’t necessarily mean the actual location error is low. To gain confidence in reported HPE from a location system and use it as a measure of accuracy, it is critical to first evaluate the HPE metric itself.
There are two measures for qualifying HPE. Both require first surveying test points for ground truth:
- HPE Containment - computes the percentage of locations with an HPE larger than the real location error. If HPE is reported at 68% confidence for example, at least 68% of locations should report an HPE radius that is larger than the absolute location error. The percent of locations that fall within the reported HPE shape (circle) is defined as HPE containment. If that containment is much lower than the target shape definition (example 68%), then the HPE estimate is not good and can’t be used for estimating location accuracy.
- HPE Correlation (Pearson correlation) - measures how well the HPE estimate correlates with real location error. Low correlation indicates that reported HPE doesn’t predict well the real location error. HPE correlations above 0.5 are good.
SUMMARY:
The best practices for evaluating accuracy are:
- Survey a large number of indoor and outdoor test points and collect ground truth for them.
- Compute and generate a CDF plot of positioning errors across multiple percentiles.
- Compute and evaluate HPE metrics (Containment and Correlation).
If you are comparing the performance of error estimation between different positioning systems or methods:
- Make sure to use the same metric for both systems. For example Skyhook can report HPE at 68% and 95% containment).
- Make sure the metric reported by each system is reliable (i.e. confirm with ground truth)
There are different ways to understand location metrics and to determine the accuracy of a provider or method. These best practices should serve as a guide for anyone looking to better understand positioning accuracy, and error. If you’re looking for more information on gaining access to Skyhook’s location positioning technology, we’d be happy to share additional information.
