流畅的GPS数据

Question

我正在处理GPS数据，每秒获取一次值并在地图上显示当前位置。问题是有时（特别是精度低时），值会发生很大变化，导致当前位置在地图上“跳跃”到远离的点。

我想了解一些足够简单的方法来避免这种情况。作为第一个想法，我考虑将精度超过某个阈值的值丢弃，但我想可能还有其他更好的方法可以实现。程序通常如何执行此操作？

- Al.

---

我在尝试计算相关值（如速度和坡度）时，感受到“GPS噪声”的负面影响，特别是对于高采样率的轨迹日志来说，这些值非常不连续（因为时间以整数[一秒]分辨率记录）。 - heltonbiker

如果您沿着主要道路导航，可以使用“贴合道路”算法，前提是您有一个良好的、正确的道路数据集。只是一种想法。 - heltonbiker

我也为了最佳准确性而面临这个问题。 - ViruMax

Answer 1

这是一个可以用于此情况的简单卡尔曼滤波器，它来自我在Android设备上的一些工作。

通常的卡尔曼滤波理论涉及向量估计，估计精度由协方差矩阵表示。然而，对于在Android设备上估计位置，通常的理论简化为一个非常简单的情况。Android位置提供者将位置给出为纬度和经度，以及以米为单位的单个数字指定的准确性。这意味着，在卡尔曼滤波中，准确性可以通过一个单独的数字来衡量，即使在卡尔曼滤波中位置由两个数字测量。另外，纬度、经度和米实际上都是不同的单位，但可以忽略这一点，因为如果将缩放因子放入卡尔曼滤波器中将它们转换为相同的单位，则在将结果转换回原始单位时，这些缩放因子最终会被取消掉。

代码可以改进，因为它假设当前位置的最佳估计值是上次已知的位置，并且如果有人在移动，则应该能够使用Android的传感器生成更好的估计值。代码有一个自由参数Q，以每秒米为单位表示，描述在没有任何新位置估计的情况下精度的快速衰减。较高的Q参数意味着精度会更快地衰减。卡尔曼滤波器通常在精度比预期稍微快一点的情况下工作得更好，因此对于在Android手机上走路来说，我发现Q=3米每秒足够了，即使我通常走得比那慢。但是如果乘坐快车旅行，则应该使用更大的数字。

public class KalmanLatLong {
    private final float MinAccuracy = 1;

    private float Q_metres_per_second;    
    private long TimeStamp_milliseconds;
    private double lat;
    private double lng;
    private float variance; // P matrix.  Negative means object uninitialised.  NB: units irrelevant, as long as same units used throughout

    public KalmanLatLong(float Q_metres_per_second) { this.Q_metres_per_second = Q_metres_per_second; variance = -1; }

    public long get_TimeStamp() { return TimeStamp_milliseconds; }
    public double get_lat() { return lat; }
    public double get_lng() { return lng; }
    public float get_accuracy() { return (float)Math.sqrt(variance); }

    public void SetState(double lat, double lng, float accuracy, long TimeStamp_milliseconds) {
        this.lat=lat; this.lng=lng; variance = accuracy * accuracy; this.TimeStamp_milliseconds=TimeStamp_milliseconds;
    }

    /// <summary>
    /// Kalman filter processing for lattitude and longitude
    /// </summary>
    /// <param name="lat_measurement_degrees">new measurement of lattidude</param>
    /// <param name="lng_measurement">new measurement of longitude</param>
    /// <param name="accuracy">measurement of 1 standard deviation error in metres</param>
    /// <param name="TimeStamp_milliseconds">time of measurement</param>
    /// <returns>new state</returns>
    public void Process(double lat_measurement, double lng_measurement, float accuracy, long TimeStamp_milliseconds) {
        if (accuracy < MinAccuracy) accuracy = MinAccuracy;
        if (variance < 0) {
            // if variance < 0, object is unitialised, so initialise with current values
            this.TimeStamp_milliseconds = TimeStamp_milliseconds;
            lat=lat_measurement; lng = lng_measurement; variance = accuracy*accuracy; 
        } else {
            // else apply Kalman filter methodology

            long TimeInc_milliseconds = TimeStamp_milliseconds - this.TimeStamp_milliseconds;
            if (TimeInc_milliseconds > 0) {
                // time has moved on, so the uncertainty in the current position increases
                variance += TimeInc_milliseconds * Q_metres_per_second * Q_metres_per_second / 1000;
                this.TimeStamp_milliseconds = TimeStamp_milliseconds;
                // TO DO: USE VELOCITY INFORMATION HERE TO GET A BETTER ESTIMATE OF CURRENT POSITION
            }

            // Kalman gain matrix K = Covarariance * Inverse(Covariance + MeasurementVariance)
            // NB: because K is dimensionless, it doesn't matter that variance has different units to lat and lng
            float K = variance / (variance + accuracy * accuracy);
            // apply K
            lat += K * (lat_measurement - lat);
            lng += K * (lng_measurement - lng);
            // new Covarariance  matrix is (IdentityMatrix - K) * Covarariance 
            variance = (1 - K) * variance;
        }
    }
}

- Stochastically

---

方差计算不应该是： 方差 += TimeInc_milliseconds * TimeInc_milliseconds * Q_metres_per_second * Q_metres_per_second / 1000000 - Horacio

@Horacio，我知道你为什么这么想，但是不！从数学上讲，这里的不确定性是由一个��纳过程建模的（参见http://en.wikipedia.org/wiki/Wiener_process），而对于一个维纳过程，方差随时间线性增长。变量“Q_metres_per_second”对应于该维基百科文章中“相关过程”部分中的变量“sigma”。 “Q_metres_per_second”是标准差，以米为单位测量，因此它的单位是米而不是米/秒。它对应于1秒经过后分布的标准差。 - Stochastically

我尝试了这种方法和代码，但结果缩短了整个距离太多，使其过于不精确。 - Andreas Rudolph

@Koray 如果你没有准确度信息，那么你就不能使用卡尔曼滤波器。这是卡尔曼滤波器试图做的完全基本的事情。 - Stochastically

哇，@DanielKanaan，在我的一个回答上留了一个近10年的评论！你当然可以尝试使用动态q_meters_per_second，但是如果不小心可能会使结果不稳定。此外，对于可能在一种情况下运行良好的方法，在另一种情况下可能并不适用，因此测试你感兴趣的所有情况都很重要。就像我10年前说的那样，比人们预期的更大的q_meters_per_second通常效果很好。祝你好运！ - Stochastically

Answer 2

你要找的是称为卡尔曼滤波器的东西。它经常用于平滑导航数据。这不一定是简单的，有很多可以调整的地方，但它是一个非常标准的方法，效果很好。有一个可用的KFilter库，它是一个C ++实现。

我的下一个备选方案将是最小二乘拟合。卡尔曼滤波器将平滑数据考虑到速度，而最小二乘拟合方法只使用位置信息。尽管如此，它肯定更容易实现和理解。看起来GNU Scientific Library可能有一个实现。

- Chris Arguin

---

谢谢Chris。是的，我在搜索时了解了Kalman，但它确实超出了我的数学知识范围。您是否知道任何容易阅读（和理解！）的示例代码，或者更好的情况是有一些可以使用的实现？（C / C ++ / Java） - Al.

@Al 很不幸，我对卡尔曼滤波器的唯一接触是通过工作，所以我有一些非常优雅的代码，但无法向您展示。 - Chris Arguin

这是Kalman滤波器的C++实现，网址是http://kalman.sourceforge.net/index.php。 - Rostyslav Druzhchenko

@ChrisArguin 没问题，欢迎。如果结果不错，请告诉我。 - Rostyslav Druzhchenko

@Al. 以及其他认为K滤波器是黑魔法的人：加速度计和陀螺仪（惯性导航系统）具有抗抖动的特点，但很容易漂移。GPS不会漂移，但会出现抖动。K滤波器将统计噪声拒绝数学应用于数据的滑动窗口，将GPS和惯性数据集成到结果中，既不漂移也不抖动。 - Peter Wone

Answer 3

这可能有点晚了...

我为Android编写了KalmanLocationManager，它包装了两个最常见的位置提供程序：网络和GPS，对数据进行卡尔曼滤波，并向LocationListener（就像两个“真正”的提供者）提供更新。

我主要用它来“插值”读数-例如每100毫秒接收更新（位置预测），而不是最大GPS速率的一秒钟，这给我的位置动画更好的帧率。

实际上，它使用三个卡尔曼滤波器，一个用于每个维度：纬度、经度和海拔高度。无论如何，它们是独立的。

这使得矩阵数学变得更容易：我使用了3个不同的2x2矩阵，而不是使用一个6x6状态转移矩阵。实际上，在代码中，我根本不使用矩阵。解决了所有方程式，所有值都是原始的（double）。

源代码可以工作，并且有一个演示活动。对于某些地方缺乏javadoc，我很抱歉，我会赶上的。

- villoren

---

我尝试使用你的库代码，但是得到了一些不期望的结果，我不确定是否做错了什么...（下面是图像URL，蓝色是过滤后的位置路径，橙色是原始位置）https://app.box.com/s/w3uvaz007glp2utvgznmh8vlggvaiifk - umesh

你看到从平均值（橙色线）“生长”的尖峰似乎是网络提供商的更新。你可以尝试绘制原始网络和GPS更新吗？也许根据你想要实现的目标，没有网络更新会更好。顺便问一下，你从哪里获取那些原始的橙色更新数据？ - villoren

橙色点来自GPS提供者，蓝色点来自卡尔曼滤波器，我在地图上绘制了日志。 - umesh

你可以把那些数据以文本格式发给我吗？每个位置更新都有Location.getProvider()字段设置。只需要一个包含所有Location.toString()的文件。 - villoren

Answer 4

你不应该通过单位时间内的位置变化来计算速度。GPS 可能会有不准确的位置，但它具有准确的速度（超过 5 公里/小时）。因此，请使用 GPS 定位时间戳中的速度。另外，你也不应该这样做航向，虽然大多数情况下可以工作。

GPS 位置已经进行了卡尔曼滤波，你可能无法改进，在后处理中通常没有与 GPS 芯片相同的信息。

你可以对其进行平滑处理，但这也会引入误差。

请确保在设备静止时删除位置，这将消除某些设备/配置不会删除的跳跃位置。

- AlexWien

---

您能提供一些参考资料吗？ - Matt Upson

这些句子中包含了许多信息和丰富的专业经验，您需要哪个句子的参考？如果想要了解速度方面的内容，请搜索多普勒效应和GPS。内部卡尔曼滤波？这是基本的GPS知识，任何一篇论文或书籍都会描述GPS芯片的内部工作原理。平滑误差？平滑处理总会引入误差。静止不动？试一试即可。 - AlexWien

站立时的“跳跃”并不是唯一的误差来源。还有信号反射（例如来自山区），导致位置跳动。我的GPS芯片（如Garmin Dakota 20、SonyEricsson Neo）没有过滤掉这些误差...而且如果没有结合气压计，GPS信号的高程值真的就是一个笑话。这些值没有被过滤或者说我不想看到未经过滤的值。 - hgoebl

@AlexWien GPS计算从一个点到一个公差的距离，给你一个球体的厚度，一个以卫星为中心的“壳”。你在这个壳体积的某个地方。这些壳体积的三个交点给出了一个位置体积，其中心是你计算得出的位置。如果你有一组报告的位置，并且你知道传感器处于静止状态，计算重心可以有效地相交更多的壳体积，提高精度。在这种情况下，误差被减小了。 - Peter Wone

GPS定位信息在传输时已经进行了卡尔曼滤波，你可能无法进一步改进。如果你能提供一个证实现代智能手机等设备如此处理的来源，那将非常有用。我个人没有找到相关证据。即使是对设备原始位置进行简单的卡尔曼滤波，也强烈表明这种说法并不正确。原始位置会在周围不稳定地跳动，而滤波后的位置通常会保持在真实（已知）位置附近。 - sobri

Answer 5

我通常使用加速度计。在短时间内位置的突然变化意味着高加速度。如果这在加速度计遥测中没有反映出来，几乎可以确定是由于计算位置所用的“最佳三颗”卫星发生了变化（我称之为GPS瞬间跳跃）。

当资产静止不动并因GPS瞬间跳跃而跳动时，如果逐步计算重心，您实际上正在相交越来越大的一组外壳，从而提高了精度。

在资产不静止的情况下，您必须根据速度、航向和线性和旋转（如果有陀螺仪）加速度数据估计其可能的下一个位置和方向。这基本上就是著名的K滤波器所做的。您可以在AHRS上以约150美元的价格得到整个硬件，其中包含除GPS模块之外的所有内容，并带有连接插孔。它具有自己的CPU和Kalman滤波板；结果稳定且相当好。惯性导航高度抵抗抖动但随时间漂移。GPS容易受到抖动的影响，但不会随时间漂移，它们实际上是相互补偿的。

- Peter Wone

Answer 6

一种使用较少数学/理论的方法是每次取样2、5、7或10个数据点，并确定哪些是异常值。一种比卡尔曼滤波器不太准确的异常值测量方法是使用以下算法，对所有成对数据点之间的距离进行计算并排除最远离其他点的那个值。通常这些值会被替换为最接近要替换的异常值的值。

例如，在五个采样点A、B、C、D、E上平滑：

ATOTAL = AB AC AD AE之间距离的总和

BTOTAL = AB BC BD BE之间距离的总和

CTOTAL = AC BC CD CE之间距离的总和

DTOTAL = DA DB DC DE之间距离的总和

ETOTAL = EA EB EC DE之间距离的总和

如果BTOTAL最大，则将点B替换为D，如果BD=min{AB、BC、BD、BE}。

这种平滑方法可以确定异常值，并可以通过使用BD的中点而不是点D来平滑位置线来增强。您的效果可能会有所不同，更严谨的数学解决方案也存在。

- ojblass

---

谢谢，我也会尝试一下。请注意，我想要平滑当前位置，因为它是被显示的并且用于检索某些数据的位置。我不关心过去的点。 我的原始想法是使用加权平均值，但我仍然需要看看哪种方法最好。 - Al.

阿尔，这似乎是一种加权平均的形式。如果您想进行任何平滑处理，您需要使用“过去”的数据点，因为系统需要比当前位置更多的信息才能知道在哪里进行平滑处理。如果您的GPS每秒采集一个数据点，而用户每五秒钟查看一次屏幕，则可以使用5个数据点而不被用户注意到！移动平均值也只会延迟一个数据点。 - Karl

Answer 7

回到卡尔曼滤波器...我在这里找到了一个针对GPS数据的Kalman滤波器的C实现：http://github.com/lacker/ikalman 我还没有尝试过，但看起来很有前途。

- KarateSnowMachine

Answer 8

关于最小二乘拟合，以下是一些其他的实验内容：

1. 仅因为是最小二乘拟合，并不意味着它必须是线性的。你可以对数据进行二次拟合，这将适用于用户加速的情况。（请注意，我所说的最小二乘拟合是使用坐标作为因变量，时间作为自变量。）

2. 您还可以尝试根据报告的准确度对数据点进行加权。当准确度较低时，将这些数据点的权重降低。

3. 你可能想尝试的另一件事是，如果准确度低，不要显示单个点，而是显示一个圆或其他指示用户基于报告准确度可能处于的范围的东西。（这就是iPhone内置的Google地图应用程序所做的。）

- Alex319

Answer 9

您还可以使用样条插值法。输入您所拥有的值并在已知点之间插值。将其与最小二乘拟合、移动平均或卡尔曼滤波器（如其他答案中提到的）相结合，使您能够计算“已知”点之间的点。

能够在已知值之间插值为您提供一个漂亮的平滑过渡和一个/合理的/近似值，如果您有更高保真度的数据，那么这些数据也会存在。http://en.wikipedia.org/wiki/Spline_interpolation 不同的样条具有不同的特性。我见过最常用的是Akima和Cubic样条。

另一个要考虑的算法是Ramer-Douglas-Peucker线简化算法，它在GPS数据简化中非常常用。（http://en.wikipedia.org/wiki/Ramer-Douglas-Peucker_algorithm）

- Aidos

Answer 10

以下是@Stochastically的Java实现的Javascript版本，供需要的人使用：

class GPSKalmanFilter {
  constructor (decay = 3) {
    this.decay = decay
    this.variance = -1
    this.minAccuracy = 1
  }

  process (lat, lng, accuracy, timestampInMs) {
    if (accuracy < this.minAccuracy) accuracy = this.minAccuracy

    if (this.variance < 0) {
      this.timestampInMs = timestampInMs
      this.lat = lat
      this.lng = lng
      this.variance = accuracy * accuracy
    } else {
      const timeIncMs = timestampInMs - this.timestampInMs

      if (timeIncMs > 0) {
        this.variance += (timeIncMs * this.decay * this.decay) / 1000
        this.timestampInMs = timestampInMs
      }

      const _k = this.variance / (this.variance + (accuracy * accuracy))
      this.lat += _k * (lat - this.lat)
      this.lng += _k * (lng - this.lng)

      this.variance = (1 - _k) * this.variance
    }

    return [this.lng, this.lat]
  }
}

使用示例：

   const kalmanFilter = new GPSKalmanFilter()
   const updatedCoords = []

    for (let index = 0; index < coords.length; index++) {
      const { lat, lng, accuracy, timestampInMs } = coords[index]
      updatedCoords[index] = kalmanFilter.process(lat, lng, accuracy, timestampInMs)
    }

- jdixon04