规划问道
数据精英年终大冲刺开车啦！
同时报名还可享更多优惠：
任选2套同报，再减200元！
任选3套同报，再减360元！
任选4套同报，再减520元！
任选5套同报，再减700元！
任选6套同报，再减900元！
项目名称：大规模移动轨迹与空间网络的地学可视化方法研究
项目负责人：张翔
依托单位：武汉大学
项目参与人：
杨敏 讲师 武汉大学
成晓强 武汉大学
卢威 武汉大学
杨伟 武汉大学
晏雄锋 武汉大学
冯涛 武汉大学
刘子轩 武汉大学
信睿 武汉大学
项目结题摘要
随着定位技术、移动互联网和社会化媒体的普及，万维网自发产生以移动轨迹（Trajectories）和空间网络（Spatial Networks）为代表的新型大规模地理数据（如迁移轨迹、公交通勤、航线轨迹、社交网络等）。
这类新型数据在分析挖掘社会关系与群体结构、人类行为模式、犯罪行为、交通出行模式等方面展示出极大潜力。可视化方法可以直观揭示移动轨迹和空间网络背后隐含的信息，弥补统计分析方法角度单一，分析结果难以直观理解等制约。然而，随着轨迹或网络数据规模的不断增长，视觉空间的符号冲突将极大降低视觉信息获取与可视挖掘效能，阻碍高层次结构与空间交互模型的显现。
为此，本课题主要针对以下内容开展了研究：
（1）发展了适宜移动轨迹和空间网络数据的化简与综合方法，在压缩数据规模的同时保持原始移动轨迹的运动特征，为后续轨迹数据的高效分析与可视化提供方法基础；
（2）研发了时空轨迹存储检索及群聚模式挖掘方法，合理的数据存储与检索体系能够替身群聚模式挖掘的效率并确保挖掘结果（伴随、汇聚、发散模式等）的相关性；
（3）发展了大规模图形符号绘制的冲突消减方法，通过建立空间冲突探测的层次树模型，可完全解决多尺度符号绘制的空间冲突与压盖，达到百万量级符号冲突消减的亚秒级处理效率；
（4）探索了GPU架构下的大规模动态符号并行绘制技术，通过并行化技术实现了百万量级符号渲染的交互式可视化效率（FPS > 25帧/秒）；
（5）通过空间与语义层次聚合技术、建立主要基于“边聚合”和“边捆绑”技术的交互式轨迹和空间“流”可视化方法，为此类数据可视化中的空间冲突、视觉混乱、难以发现高层次空间交互模式及其多尺度规律等问题提供有效的解决途径；
（6）研发了面向移动轨迹的交互式可视分析网络平台原型系统，支持从发现、搜索、标记、探索、综合、对比的逐级深入的轨迹模式分析与挖掘框架，提升了大规模时空轨迹数据的挖掘效能。
项目结题成果报告
以下研究成果内容摘自项目结题成果报告。该项目报告共计30页，关注城市数据派微信公众号，在微信公众号对话框中输入 24118，即可获得报告全文PDF的下载方式：
(1)主要研究内容。
项目主要针对大规模移动轨迹的数据存储、综合化简、符号化、可视分析算法、数据挖掘、可视化平台等方面开展了研究，具体包括:
(1.1)保持动态信息的移动轨迹综合化简
空间数据的综合化简在地图制图以及计算机视觉领域受到广泛关注，在缩减轨迹数据体量的同时保持重要分析特征尤为重要。现有的综合化简方法主要针对静态地理数据，依据几何特征上的距离、角度、面积以及这些参量背后的地理意义来分析并保留重要的特征点(包括端点、极值点、拐点等)，虽然能够较好地保持原始线状目标的空间形态结构，但是缺乏对时间维信息的考虑。因此，需要研究能够在轨迹线化简时保持重要运动特征如速度、加速度等的综合化简方法。
(1.2)时空轨迹存储检索及群聚模式挖掘
时空轨迹数据蕴含着丰富的信息财富,采用合理的轨迹模式挖掘算法对时空轨迹数据进行多维度的分析对于探索移动物体的运动规律具有十分重要的意义群体 Swarm 运动模式根据轨迹方向的特性可分为方向相同的运动模式和方向不同的运动模式,其中方向相同的轨迹运动模式主要包括领导者运动模式和伴随运动模式，方向不同的轨迹运动模式主要包括聚集运动模式和发散运动模式。由于轨迹群聚模式挖掘对效率要求高,有必要建立针对性的时空轨迹存储检索方法及其相应的挖掘算法。
(1.3)支持移动轨迹的交互式可视分析平台
分析移动物体的轨迹数据对于揭示时间模式和了解过去的事件具有重要意义。实时生成的海量轨迹数据有助于理解人类活动的复杂动态,特别是城市规划智能交通领域。例如可以帮助政府宏观把控城市交通规律，了解城市交通状况从而用于道路与交通路线规划;还可以帮助乘客合理选择出行的时间费用和方式:帮助出租车司机及公司合理优化策略，创造更大经济收益。然而数据规模的增大为现有分析和可视化算法的可伸缩性带来了巨大挑战,多数计算机模型只能针对小样本数据进行分析与展示,这迫切需要交互可视分析技术作为一种新的分析手段。
(1.4)基于图像技术的地图设计语言扩展
移动目标轨迹数据的地学可视化离不开地理底图提供方向感和地理上下文因而地理底图的设计也是一个需要考虑的问题。然而，当前网络地图设计存在如下问题:(a)网络地图难以个性化定制。(b)网络地图设计语言受限。地图上符号的设计以及地图的整体风格受限于矢量图形表现能力，没有充分应用当前图形图像技术来增强地图表现力。因此，有必要探索新的图形表现形式来扩充已有的地图设计语言。
(1.5)交互式Web地图环境
大规模运动轨迹、时空流数据的可视化存在数据规模大，信息过载严重等问题，这对可视化之前的数据处理提出了很高要求，本课题主要从两个方面来减缓可视分析的计算压力:(1)基于S0A架构建立松散耦合的交互式的可视分析环境通过“概览-交互-细节呈现”可视化原则来支持用户从大规模数据中挖掘特征信息;(2)通过并行化和分布式的服务器架构来调度计算与数据库资源，提高交互式可视分析环境的总体响应度与灵敏性。
(1.6)大规模图形符号绘制的冲突消减
轨迹可视化可通过点状符号地图混搭展现空间分布。与传统地图符号不同混搭地图的点状符号自身承载丰富信息，符号个体尺寸较大，且数据体量巨大本项目研究“大尺寸”点状符号的实时 Web 制图，定义“大尺寸”的内涵为“符号尺寸远大于符号间距”，并认为这是大数据环境下点状符号混搭制图的一个重要特征。有必要针对这一特征发展大规模符号大的冲突消减方法。
(1.7)大规模动态轨迹符号并行绘制
动画技术是表现轨迹的动态性的一种常用手段。然而，大规模移动轨迹存在实时动画渲染的性能瓶颈,这与地图符号到达一定量后的效率瓶颈属于同一问题前期研究我们利用空间尺度建立大规模地图符号的层次结构，可以有效约束每个地理尺度下绘制单元的数量，进而降低绘制瓶颈。另一种情形是符号的数量不能减少，这种情况通常采用并行计算框架解决，在图形领域最自然的选择是采用显卡中的图形处理单元(GPU)。因此，我们需要研究GPU图形技术下的时空轨迹并行符号绘制方法。
(1.8)时空“流”数据 Clutter Reduction 可视分析
以空间交互数据为代表的时空流反映了生物、物体、信息从一个位置到另一个位置的动态运动与传递过程，其中以行为轨迹数据、通勤数据、社交APP签到数据为代表，其已经成为地理科学、计算机科学、社会学、生物与生态学、城市规划等学科领域的研究焦点。然而，由于大规模空间交互数据通常有数千个位置节点以及数百万条连接线，在对其进行可视化时，大量交叉重叠的线会引发视觉混淆(VisualClutter)，掩盖了对其中隐含的重要空间交互模式的表达，影响信息的一览性以及为高层次空间交互的可视挖掘,迫切需要能够减少或避免该问题的可视化技术。
(2)取得的主要研究进展、重要结果、关键数据等及其科学意义或应用前景
(2.1)保持动态信息的移动轨迹综合化简
提出一种保持移动速度特征的轨迹线化简方法。速度特征是反映移动物体运动状态的重要指标,化简过程尽量保持原有轨迹线隐含的速度变化信息对于后期移动模式的分析、挖掘和预测有积极的作用。例如车辆交通事故领域，车辆轨迹线速度变化上的关键轨迹点是事故分析及理赔的重要依据。该方法采用的基本思想是基于移动速度相似性原则对原始轨迹线进行层次化剖分，然后将剖分关系作为约束条件结合化简精度要求对原始轨迹线实施分区化简，使得距离误差控制下的轨迹点取舍行为尽量发生在移动速度均一的轨迹线片段内，而速度变化上的重要轨迹点由于处于分区临界位置而被保留,从而缓解化简操作对原始轨迹线隐含速度特征的破坏。
对比了四种方法在不同压缩比率条件下产生的时间同步距离误差。可以发现不管是最大时间同步距离误差，还是平均时间同步距离误差，TD-TR方法、OW-TR方法以及本课题提出的方法表现较为接近，且明显优于DP方法。原因是前面三种方法均采用了时间同步距离作为轨迹点取舍的控制指标。其中，TD-TR方法采用全局性由上而下的比较策略,时间同步距离误差控制上好于采用局部启发式策略的 OW-TR方法。我们提出的方法虽然也是一种全局性方法，由于增加了原始轨迹线在速度变化上的层次化剖分关系作为约束条件,使得部分速度变化大但是在时间同步距离指标上不是最优的轨迹点优先保留,导致同一压缩率水平下时间同步距离误差高于 TD-TR方法，部分压缩比率区间甚至略高于 OW-TR 方法。也正是由于上述原因，使得本文方法在速度保持上优于其它几种方法。
(2.2)时空轨迹存储检索及群聚模式挖掘
课题组主要针对以下四个问题开展研究:(1)通过研究时空轨迹数据的存储形式、结构以及时空轨迹数据的查询方式从而构建一种高效的时空轨迹数据管理模式:(2)从时间和空间角度考虑设计一种灵活高效的轨迹模式挖掘系统从而简化轨迹模式挖掘的难度，提高轨迹模式挖掘的效率:(3)搭建一个可交互式轨迹可视化界面从而能够轻松改变轨迹模式挖掘相关参数并能以图像的形式实时获得轨迹显示效果。(4)探索轨迹模式挖掘系统在时空轨迹数据中的应用从而分析时空轨迹模式挖掘的意义。
首先，课题组总结现有的时空轨迹存储方式和轨迹模式挖掘算法，根据时空轨迹数据密集和空间分布异质性的特点，采用时间属性优先的轨迹存储方式和Swarm轨迹模式挖掘算法。
其次，我们在数据预处理阶段利用冗余数据删除、轨迹内插、轨迹数据空间存储以及轨迹数据多表格存储技术对出租车轨迹数据进行数据处理,将杂乱的轨迹数据转变为规律的、按时间序列存储的点集数据。对于完成冗余数据删除的轨迹数据，仍然是离散的轨迹点数据，不能保证每个移动物体在所给时刻内正好有记录的坐标点，为保证Swarm 算法正常计算，需要内插方法获取每个时刻的轨迹时空信息，然后将轨迹信息按照时间序列以点集的方式存储在数据库中。在实际操作中,首先获取到原始轨迹信息中大于给定时间点且与给定时间点时间间隔最小的轨迹点的坐标信息和小于给定时间点且与给定时间点时间间隔最小的轨迹点的坐标信息，再利用线性插值公式对两端点坐标信息进行计算，获取到给定时间点物体的近似坐标位置。
最后在 Swarm 算法设计中，我们采用三步裁剪规则，以Swarm 算法为核心开发实用的轨迹模式挖掘系统,采用长时序轨迹片段动态查询的方式对轨迹模式挖掘过程加以分析，调整算法参数，总结最后的轨迹模式挖掘结果。
早、晚高峰轨迹模式挖掘图:图(a)代表早高峰阶段满足高密度、低连续性挖掘模式的轨迹聚集图，其中箭头代表车辆行驶方向;图(b)代表晚高峰阶段满足高密度、低连续性挖掘模式的轨迹发散图，其中箭头代表车辆行驶方向实验表明,该轨迹模式挖掘系统能够从大量真实的轨迹数据中探索不同类型的轨迹模式，且挖掘结果与实际情况基本符合。
(2.3)支持移动轨迹的交互式可视分析
平台目前，本课题以出租车轨迹数据为例，通过构建在线交互可视分析原型系统，探索分析了出租车出行模式以及特征的时空分布，从中可归纳城市出行行为规律研究采用 Shneiderman的“Overview, zoom and filter,then details-on-demand”作为整体可视分析的设计哲学。具体而言，我们首先通过对轨迹采样点集数据和OD 数据分别进行可视编码(Encoding)，以热力图和地图底图结合构成对一段时空范围内运动群体的总体分布趋势(Overview);此次，设计可支持任意范围和运动方向偏好选取的交互工具,让用户可以进一步分析感兴趣的特定区域或者同时限定方向范围(Zoom and Filter);同时,通过多视图协调(Coordinated Views)直观的展示数据相关联但并未展示出的属性信息(Details-on-Demand)。在此基础上，我们梳理了适宜移动目标分析与探索的三种任务类型:(1)确定识别:(2)探索挖掘关联;(3)对比(见下图)，为用户交互式的探索分析城市内感兴趣区域出租车的时空模式和流向性,不同区域间的差异性以及节假日或其他特殊事件对人们出行行为模式的影响提供了分析工具。
通过三个案例研究:
(1)感兴趣区域流向性动态分析;
(2)事件对交通影分析(Outliers);
(3)交通需求分析(供需不对称)，我们获得以下结论。
第一，交互可是分析能够直观展现租车轨迹在宏观分布与趋势。例如，在哪个区域、哪段时间，出租车数量较多，从而推理该地需求较旺盛。
第二，可以发现租车上下客点相关的属性特征，分析城市居民的行为规律。比如辅助交通部门确认交通需求点或通勤需求较大的两个区域的时空特征，进而辅助公共交通规划。
第三，在分析人员使用系统发现一些较为直观的规律或者模式后,可以通过多视图协调交互组件进一步的定量探索数据,并根据更细粒度的结果总结规律,发现模式特征。
(2.4)基于图像技术的地图设计语言扩展
现以网络地图服务为应用环境，利用数字图形图像技术增强电子地图图形表现，实现了风格化地图设计服务网络中间件。具体而言，我们提出两种地图风格化服务模式,即预处理模式和交互式即时处理模式。研究了地图风格化设计流程并从数据预处理、图像风格化到输出存储三个阶段具体阐释。数据预处理阶段对地图数据进行定制，包括数据分层、缓冲区生成等步骤，使得地图更适宜风格化处理:图像风格化阶段研究了应用图像处理技术所实现的常见风格化效果，主要包括(1)矢量数据栅格化、(2)图层蒙版技术、(3)边缘轮廓增强、(4)无缝纹理技术;(5)边缘留白法、(6)图层混合。这些图像处理技术能够提供更加丰富的图形表现力(地图设计语言)。
(2.5)交互式Web地图环境
课题组采用的 WEB 地图制图引擎、切片服务器架构。主要包括了(1)服务器端的数据存储(文件系统、数据库系统):(2)服务器端的制图引擎;(3)切片服务器:(4)服务器端地图设计工作环境;(5)客户端地图程序。其中服务器端的数据存储以数据库系统为主,可利用数据库技术支持并发访问数据和分布式存储的能力，提高数据量上升时系统的整体伸缩性:另外，通过数据库技术来管理用户数据，私有数据，公有数据可提供极大的安全性和稳定性。服务器端制图引擎主要由高质量图形绘制引擎(Renderer)和地图样式模板库、符号库构成高质量图形引擎的设计目标是能够提供最先进的图形绘制、图像处理、符号化处理、图像混合等技术，用这些技术来实现传统的地图表示方法和制图技术，并探索新型地图表示方法与可视化技术(如大数据可视化技术)。地图样式文件是地图设计者控制终端发布地图的配色风格和符号方案的领域专用语言。切片服务器对 WEB服务器接受的制图请求进行处理,按照特定的切片方案返回指定空间坐标和比例尺下的地图切片图像。客户端地图程序将服务器返回的切片按照协议约定的编码规则进行排序和空间重组，形成一幅完整的地图展现在浏览器中。
时空数据可视化的数据流:数据文件/数据库→地图样式文件+符号库→图形引擎 → 切片服务 → 客户端/浏览器。该过程为静态过程，比较适宜展示时空轨迹和流的宏观、聚合层次的空间分布与强度分布。
……
还有更多成果内容，详见项目结题成果报告。该项目报告共计30页，关注城市数据派微信公众号，在微信公众号对话框中输入24118，即可获得报告全文PDF的下载方式。
原文始发于微信公众号（城市数据派）：【优秀项目成果推荐】大规模移动轨迹与空间网络的地学可视化方法研究丨城市数据派
