面向可视分析的轨迹简化和语义增强方法

SimpliFly: A Methodology for Simplification and Thematic Enhancement of Trajectories

Katerina Vrotsou, Halldor Janetzko, …, Natalia Andrienko, and Gennady Andienko

1、论文的出发点和主要贡献
轨迹描述的是运动物体，通常包含三类特征数据：（1）运动相关属性（速度、加速度、转向角…）；（2）运动物体属性（车、船、人、动物…）；（3）运动环境属性（天气）。因此作为多变量数据的轨迹，信息负荷很大，直接可视化会导致三方面问题：
（1）感知的局限性
微小的图元或变化肉眼难以分辨
（2）认知局限性
用户很难记住所有的信息，而实际上他们只关注于特定的信息
（3）性能
过多的点和线会妨碍交互
因此，对于轨迹数据适当的简化将给可视分析带来很大的好处。

论文提出了两种面向可视分析的轨迹简化方法：基于密度的简化和基于属性的简化。在此基础上，为了突出用户关注的属性特征提出了将可视化方法和计算方法相结合的增强方法。

2、轨迹简化方法

文中共描述了三类简化方法，其中后两种是本文提出的简化方法。

（1）基于几何的简化方法（GBS）

此类方法主要是减少几何顶点，减少轨迹段。基本思想是找到对轨迹形状贡献较大的重要的顶点，忽略不重要的点。因此GBS是纯粹的几何简化，而不关心轨迹的语义信息。最常用的简化算法为Douglas-Peucker 算法。

（2）基于密度的简化方法（DBS）

此类算法的基本思想是将超过屏幕分辨率或感知极限的点用密度聚类，然后以聚类中心代替聚类从而实现简化目的。在三维空间中，直接绘制聚类当视点变化时需要重新计算，因此在数据空间中计算聚类更加合理。论文采用了OPTICS算法实现基于密度的简化。简化过程主要包含三步，首先设定聚类的点数，计算聚类点之间的距离得到距离统计图；然后取合适的距离作为阈值对轨迹上的点进行聚类；最后用聚类中心表示轨迹顶点。计算过程中，由于轨迹具有时序性，因此聚类要按照轨迹点的时间顺序依次计算。下图给出了DBS的简化过程

图1 DBS的简化过程

（3）基于属性的简化方法（PBS）

此类方法的基本思路是利用区域化方法对轨迹结构进行简化，也就是说将一大群空间对象聚合成少量的具有相似属性的连续区域。经过PBS简化，在同一聚类中的运动对象具有相似的属性值。论文应用了REDCAP算法，用户选择感兴趣的属性对轨迹进行层次聚类，聚类完成后，由用户选择适当的聚类层次的聚类结果作为最终简化轨迹。图2描述了整个简化过程。

图2 PBS简化过程

作者针对这三类简化方法，对相同轨迹数据进行简化，图3给出了三类简化方法的对比结果。

图3 三类简化方法的对比效果

从中可以看出，GBS方法能保持轨迹的结构特征，但不适合复杂的线，如自相交。DBS对复杂的线结构做得更好，能保留轨迹的位置语义（面向感知）。PBS着眼于结构和语义属性，确定运动对象的行为方式（面向认知）。特别是DBS方法对于小范围的复杂轨迹能较好地简化。

3、语义增强

为了突出轨迹中特定的属性，论文提出了将属性描述为向量，计算向量之间的聚类，最后将聚类的值映射为颜色饱和度，实现可视编码。尽管方法简单但是对于聚类算法的选择，需要谨慎。图4给出了语义增强的可视化效果。

4、总结

论文提出了两类面向可视分析的轨迹简化算法和语义增强方法，低了感知和认知负担，减少了视觉遮挡，消除了任务无关的细节，提高了可视分析效率。但是，方法中存在不少参数的设定和聚类算法的选择，因此应用上需要谨慎。尽管目前的轨迹方法较多，但是面向可视分析的确实还不多见，尽管论文并没有提出实质性的算法，但是值得借鉴。简单起见，这里没有描述方法的细节，有兴趣的可以阅读原文，发表在TVCG2015年第一期。