基于在线有向无环图的船舶轨迹压缩算法

为了解决船舶轨迹数据的压缩问题, 提出了一种船舶轨迹在线压缩算法; 使用多次滑动推算船位判断方法清洗船舶轨迹, 使用在线有向无环图在干净轨迹上建立压缩路径树并输出采样点; 为了提高轨迹队列和路径树在内存中的查询速度, 使用哈希表对其进行管理; 为了验证提出算法的效果, 比较了真实船舶自动识别系统数据与方向保留算法、道格拉斯-普克算法的压缩时间和误差, 采用可视化方法分析了原始轨迹、清洗轨迹和压缩轨迹。试验结果表明: 在压缩时间方面, 方向保留算法和道格拉斯-普克算法的压缩时间分别约为提出算法的1.1、1.3倍, 说明提出的算法比其他2种算法的处理时间更短; 提出的算法在压缩过程中保留了时间信息, 平均同步欧氏距离误差在任何压缩率下都能保持在10 m以下, 最大同步欧氏距离误差在压缩率为1%时仅有127 m, 而其他2种算法的平均同步欧氏距离误差和最大同步欧氏距离误差不受控制, 会随机变化; 在垂直距离误差方面, 提出的算法与道格拉斯-普克算法在压缩率不小于5%的条件下, 都能保证垂直距离误差小于20 m, 而方向保留算法的垂直距离误差会随机变化; 在显示效果方面, 提出的算法能有效清除轨迹噪声点, 压缩轨迹能够较好地代表原始轨迹的宏观交通流情况。可见, 提出的算法能更高效地保留原始轨迹的形状和时间信息。 

Compression algorithm of ship trajectory based on online directed acyclic graph

To solve the problem of ship trajectory data compression, an online ship trajectory compression algorithm was proposed. An estimation method of multiple sliding reckoning the ship position was used to clean the ship trajectory, and the online directed acyclic graph was used to build the compression path tree on the clean trajectory and to output the sampling points. The Hash table was used to manage the trajectory queue and path tree in memory in order to improve their query speeds. To verify the effect of the proposed algorithm, the compression times and errors of real ship automatic identification system, direction-preserving algorithm and Douglas-Peucker algorithm were compared, and the original trajectory, clean trajectory and compression trajectory were analyzed by the visual method. Experiment result shows that in terms of the compression time, the compression times of direction-preserving algorithm and Douglas-Puck algorithm are about 1.1 and 1.3 times of the proposed algorithm, respectively, indicating that the execution time of the proposed algorithm is shorter than the other two algorithms. The proposed algorithm retains the time information in the compression process, and the average synchronized Euclidean distance error is less than 10 m at any compression rate. The maximum synchronized Euclidean distance error is only 127 m when the compression ratio is 1%, while the average synchronized Euclidean distance errors and the maximum synchronized Euclidean distance errors of the other two algorithms can not be controlled, and change randomly. In terms of perpendicular distance error, both the proposed algorithm and Douglas-Puck algorithm can guarantee that the perpendicular distance errors less than 20 m when the compression rate is not less than 5%, while the perpendicular distance error of direction-preserving algorithm changes randomly. In terms of display effect, the proposed algorithm can effectively remove the noise points of trajectory, and the compression trajectory can better represent the macroscopic traffic flow of original trajectory. Therefore, the proposed algorithm can preserve the shape and time informations of original trajectory more efficiently.