1. 定义

轨迹去噪：过滤掉轨迹中不需要的GPS点，保留需要的GPS点，然后组成新的子轨迹。

2. 算法描述

情况1：轨迹的GPS点是由传感器采集的特定时间点的位置信息，由于信号干扰等因素可能会造成GPS点与车辆的真实位置存在较大偏差。偏差过大的GPS点会影响后续的轨迹计算和可视化，这类偏差过大的GPS点被称为轨迹的噪点，需要从轨迹中剔除掉。图1所示的轨迹中，红色的GPS点都是噪点。

图1 轨迹噪点示意图[1]
算法1：识别情况1中噪点的关键在于设计一个合理的偏差的度量(Metric)，文献[1]中用相邻两GPS点之间的平均速度(Average Speed)作为度量，如果相邻两个GPS的平均速度大于一个不合理的常量(Threshold)，则认为后一个GPS点为噪点，比如出租车的行驶速度一般不超过200KM/H。剔除掉噪点之后剩余的多个连续的轨迹段就是去噪后的子轨迹，如图1中的p1->p4，p6->p9。

需要注意的是，图1中的p10和p11的平均速度可能小于，这种情况下p10相对p9是噪点，但是p11相对p10不是噪点，p10->p11就会被作为一个子轨迹(虽然是由两个相邻噪点组成的),出现连续多个噪点相距都很近的情况极其少，所以这类子轨迹一般不会太长，只需要在去噪后生成的自轨迹中把长度点数量小于一个值(GPS Number)的轨迹丢弃即可。

算法实现参考3.1。

情况2：用户只关心某特定空间区域内的轨迹，区域以外的GPS点则直接丢弃。
算法2：给定多边形空间区域(Spatial Boundary)，从原始的轨迹中截取该区域内连续的轨迹段组成子轨迹。

情况3：用户只关心某特定时间范围内的轨迹，时间范围之外的GPS点则直接丢弃。
算法3：给定目标时间范围(Time Boundary)，截取包含在该时间范围内的连续轨迹段生成子轨迹。

3. 代码实现

代码是用Scala实现的，完整项目请查看我的Github
接口类

trait AbstractTrajectoryFilter {
  /**
   * Filter the sub-trajectories from raw long trajectory
   *
   * @param trajectory raw trajectory
   * @return sub-trajectories
   */
  def filter(trajectory: Trajectory): Array[Trajectory]
}

3.1 轨迹去噪（算法1）

class TrajectoryNoiseFilter(maxSpeedMPS: Double) extends AbstractTrajectoryFilter {

  override def filter(trajectory: Trajectory): Array[Trajectory] = {
    val gpsCoordinates = trajectory.getCoordinatesGPS

    var startIndex = 0
    var currIndex = 0
    val subTrajectories = new ArrayBuffer[Trajectory]()
    while (currIndex < gpsCoordinates.length - 1) {
      val speed = calSpeed(gpsCoordinates(currIndex), gpsCoordinates(currIndex + 1))
      if (speed > maxSpeedMPS) {
        if (startIndex < currIndex) {
          val subCoordinates = gpsCoordinates.slice(startIndex, currIndex + 1)
          subTrajectories += new Trajectory(trajectory.oid, subCoordinates)
        }
        startIndex = currIndex + 2 //ignore the noisy coordinate
        currIndex = startIndex
      } else {
        currIndex += 1
      }
    }

    if (startIndex < gpsCoordinates.length - 1) {
      subTrajectories += new Trajectory(trajectory.oid, gpsCoordinates.slice(startIndex, gpsCoordinates.length))
    }
    subTrajectories.toArray
  }

  private def calSpeed(from: CoordinateGPS, to: CoordinateGPS): Double = {
    val timeIntervalInSec = to.time.toInstant.getEpochSecond - from.time.toInstant.getEpochSecond
    val distanceInMeter = DistanceCalculator.distInMeter(from, to)
    distanceInMeter / timeIntervalInSec
  }

3.2 轨迹时间过滤（算法2）

class TrajectorySpatialFilter(spatialBound: Polygon) extends AbstractTrajectoryFilter {

  override def filter(trajectory: Trajectory): Array[Trajectory] = {
    val gpsCoordinates = trajectory.getCoordinatesGPS

    var startIndex = -1
    val subTrajectories = new ArrayBuffer[Trajectory]()
    for (index <- gpsCoordinates.indices.dropRight(1)) {
      if (spatialBound.contains(trajectory.getPointN(index))) {
        if (startIndex == -1) {
          //enter spatial bound
          startIndex = index
        }
      } else {
        if (startIndex != -1) {
          //leave spatial bound
          if (startIndex < index - 1) {
            subTrajectories += new Trajectory(trajectory.oid, gpsCoordinates.slice(startIndex, index))
          }
          startIndex = -1
        }
      }
    }

    if (startIndex != -1 && startIndex < gpsCoordinates.length - 1) {
      //the last sub trajectory
      subTrajectories += new Trajectory(trajectory.oid, gpsCoordinates.slice(startIndex, gpsCoordinates.length))
    }
    subTrajectories.toArray
  }
}

3.3 轨迹时间过滤（算法3）

class TrajectoryTemporalFilter(timeBound: (Timestamp, Timestamp)) extends AbstractTrajectoryFilter {

  override def filter(trajectory: Trajectory): Array[Trajectory] = {
    if (!trajectory.getStartTime.before(timeBound._2) || !trajectory.getEndTime.after(timeBound._1)) {
      return Array.empty
    }

    val gpsCoordinates = trajectory.getCoordinatesGPS
    val startIndex = gpsCoordinates.indexWhere(_.time.after(timeBound._1))
    val endIndex = gpsCoordinates.lastIndexWhere(_.time.before(timeBound._2))
    assert(startIndex != -1 && endIndex != -1)

    Array(new Trajectory(trajectory.oid, gpsCoordinates.slice(startIndex, endIndex + 1)))
  }
}

4. 总结

轨迹去噪就根据目标需求，将不需要的GPS点剔除，并将连续的GPS点组成子轨迹。不同算法的差异在于对"不需要的GPS点"的定义不同。

参考文献

[1] Zheng Y. Trajectory data mining: an overview[J]. ACM Transactions on Intelligent Systems and Technology (TIST), 2015, 6(3): 1-41.