轨迹是多维空间中十分重要的一种数据形式,它可以看作是移动对象的位置和时间的记录序列,也可以看作数据由高维空间向时空维度的映射。
随着定位技术的发展,人们已经能够搜集大量的轨迹数据,对这些数据进行分析可以得到许多的规律和知识[1]。由于当前传感器技术的限制,轨迹数据往往有着大量的误差[2],因此在对轨迹数据进行分析和挖掘的时候,经常会使用可视分析技术对轨迹进行处理[3-8]。
在可视分析技术中,首先利用数据可视化的方法将原始数据或者自动挖掘分析的结果呈现给用户,然后用户通过人机交互接口返回对结果的评价和修改,然后在结合用户返回的内容对模型和参数进行修正。在这个过程中,轨迹数据的可视化直接影响了人机交互的过程和用户判断,因此选取合适的可视化方式在实际的应用中显得尤其重要。
在轨迹数据的可视化中,一般会通过大尺度和小尺度2种方式将信息呈现给用户[9]。在小尺度的可视化中,轨迹的细节信息被充分的展示给了用户。在大尺度的可视化中,轨迹的细节信息被弱化,而轨迹的整体信息被呈现给用户。在进行可视分析的时候,为了一次性展示完整的数据,往往会选取一个较大的尺度,但在用户进行分析的时候,往往需要一些轨迹的细节信息进行判断,因此,在对轨迹数据进行可视化的时候,如何通过多个尺度对数据进行展示是一个十分重要的问题。
传统的多尺度的可视化方式为背景+焦点(Context+focus),如图 1所示;概览+细节(Overview+detail)如图 2所示;缩放如图 3所示。更多细节可见文献[10-11]。
文献[12]提出了一种通过缩放来展示飞机轨迹细节信息的方法。文献[13]提出了一种类似于概览+细节的方式对轨迹的属性和细节进行可视化。
在概览+细节的模式中,无法对多个区域进行同时放大。在缩放模式中,无法同时展示轨迹的大尺度信息,也无法对多个区域同时进行放大。同时上述的模式中,均对人机交互操作有一定依赖性,依赖于用户发起多尺度显示的请求,使得操作流程变得复杂,使得在可视分析的过程中,这些被弱化的区域存在被用户忽略掉的风险,因此并不能保证这些区域的信息被正确地呈现给了用户。
基于以上这些原因,文中选取在背景+焦点的模式下,采用引入多个焦点的方式,对多个区域进行放大;同时为了避免由于用户疏忽导致的信息丢失以及减少对人机交互的依赖,采用主动呈现的方式对轨迹细节信息进行强化。
图 1(b)中的放大方式为鱼眼视图,鱼眼视图不仅是地理信息多尺度可视化中的一种常见手段,也是广泛的应用在可视化和可视分析的各个领域[14]。Gutwin等[15]利用鱼眼视图进行人机交互的导航;Furnas[16]利用鱼眼视图进行日历文字的布局;Sarkar等[17]利用鱼眼进行图的布局,同时也提出一种鱼眼视图的构造方式;在文中的可视化鱼眼视图作为突出重点和人机交互的手段也在大量使用。鱼眼视图不会破坏图片连续性,但会使视图中心被放大而边缘被缩小,造成一定的扭曲与失真。
轨迹的连续性是一种十分重要的属性,所以在通常情况下可视化工作会避免破坏轨迹的连续属性。另外在实际的可视分析中,往往会加入地名、道路信息等辅助信息来进行挖掘和分析,所以一些信息含量较低的区域的失真并不会对可视分析造成显著的影响,因此文中选取鱼眼视图对轨迹的重点区域进行放大。
考虑到在可视分析中,用户关注的重点往往是这些轨迹点密度较高的区域,而这部分轨迹也是在大尺度的可视化中损失信息较多的区域。因此,基于以上这些方面,文中在背景+焦点模式的基础上,提出了一种新轨迹可视化方法,利用指数函数构造多个鱼眼视图,在大尺度下通过多个鱼眼视图对轨迹密度较高区域进行放大,在大尺度下将轨迹的细节信息呈现出来。
1 鱼眼视图笔者将采取鱼眼视图的方式在大尺度下对需要重点显示的区域进行放大,使得在大尺度的可是分析中,依然能够呈现给用户一些重要区域的细节信息。
鱼眼透镜是一种焦距极短且视角极大的透镜,与普通透镜相比,这种透镜中间区域被放大而周边区域被缩小,而鱼眼视图则是仿照这种成像效果做出的可视化效果。
鱼眼视图的基本原理是将整个区域内的元素向边界方向进行延伸,延伸程度从中心到边界一次减小。在鱼眼视图中,中心区域被放大而边缘区域被压缩,从而实现了对中心区域信息的强化。
令鱼眼视图中心为坐标原点,假设鱼眼视图内一点的原始坐标为C=(x, y),在视图下的坐标为C′=(x′, y′)。
对应的映射为
$C\prime = {F_{{\rm{fisheye}}}}\left( C \right)。$ | (1) |
记C=(x, y)与+x轴的逆时针夹角为φ,C'=(x′, y′)与+x轴的逆时针夹角为φ′,则式(1) 可以写作
$\left\{ {\begin{array}{*{20}{l}} {\left\| {C\prime } \right\| = {f_{{\rm{fisheye}}}}\left( {\left\| C \right\|} \right),}\\ {\varphi \prime = {g_{{\rm{fisheye}}}}\left( \varphi \right)。} \end{array}} \right.$ | (2) |
在文中,为了简化复杂度,令鱼眼视图的形状为圆,通过在径向上的扭曲来实现鱼眼视图的效果。
可得
${g_{{\rm{fisheye}}}}\left( \varphi \right) = \varphi ,$ | (3) |
因此,映射可简化为
$\left\| {C\prime } \right\| = {f_{{\rm{fisheye}}}}\left( {\left\| C \right\|} \right),$ | (4) |
其原理如图 4所示。
为了实现文中的鱼眼视图,需要建立一个从[0, 1]到[0, 1]的单调的非线性映射作为径向上的扭曲函数。
假设放大区域的半径为rmax,区域内某点距离中心的距离为r,选取映射关系为
$r\prime = {r_{{\rm{max}}}}*(1 - {(1 - r/{r_{{\rm{max}}}})^N}),$ | (5) |
式中:N为表征放大程度的参数;r′为放大后该点距离中心的距离。
易知r/rmax的取值范围为[0, 1], 采用r′/rmax表征径向的扭曲程度,可得在径向的扭曲程度示意图如图 5所示。从图 5可以看出靠近中心的区域被放大而远离中心的区域被压缩。
对于多个放大区域,每个放大区域的轨迹点个数即为m1, …, mn, 选取每个区域的中心为鱼眼的中心,为了充分利用图像的空间,同时借鉴网络布局中的节点密度均匀准则,在文中将基于以下2条准则进行可视化布局:
准则1:在不相互交叠的情况下鱼眼区域尽可能较大;
准则2:每个区域中的轨迹密度尽可能相似。
考虑2个间隔较近的区域mi、mj的情况,可得
${r_i} + {r_j} = {d_{ij}},$ | (6) |
$\frac{{{m_i}}}{{\pi r_i^2}} = \frac{{{m_j}}}{{\pi r_j^2}},$ | (7) |
式中:dij为mi、mj中心之间的距离;ri、rj为mi、mj对应的鱼眼的半径。
可得
$\left\{ {\begin{array}{*{20}{l}} {{r_i} = \frac{{\sqrt {{m_i}} }}{{\sqrt {{m_i}} + \sqrt {{m_j}} }}{d_{ij}},}\\ {{r_j} = \frac{{\sqrt {{m_j}} }}{{\sqrt {{m_i}} + \sqrt {{m_j}} }}{d_{ij}}。} \end{array}} \right.$ | (8) |
对于多个区域,其相切次序依次记作M1, …, Mn,i, j中心距离记作Dij,可以通过由中心逐渐增加半径的迭代的方式获取最终分布。类比2个区域的情况,定义每个中心的增长速率为
${\rho _i} = \frac{{\sqrt {{M_i}} }}{{\sum\limits_{j = 1}^n {\sqrt {{M_i}} } }}。$ | (9) |
定义步长l, 每个放大区域的半径r1, …, rn,令ri=0(i=1, ..., n), 可迭代计算
$r{\prime _i} = {r_i} + {\rho _i}l,$ | (10) |
当′ri+r′j>Dij时,i, j同时停止迭代,重复直至所有放大区域停止迭代。
考虑到人的视觉系统对长度或距离等变量有着较大的误差,因此在计算时可以近似选取一些较为简单的整数比例来降低计算的复杂程度,同时又不对可视化效果造成较大的影响。
对于某个放大区域参数N的选取,假设未进行放大时轨迹区域的半径为R0, 放大后轨迹区域的半径为R′0, 由之前步骤确定的该鱼眼区域的半径为R。为了方便定量分析,定义α如下来表征每个鱼眼区域的填充程度为
$\alpha = \frac{{R{\prime _0}}}{R}。$ | (11) |
α代表进行放大后鱼眼视图中有轨迹的区域的半径与整个鱼眼视图的半径的比例。
若要使填充程度大于或等于某一定的数值,即α>α0。由式(3) 可得
$R{\prime _0} = R*\left( {1 - {{\left( {1 - \frac{{{R_0}}}{R}} \right)}^N}} \right),$ | (12) |
可得
$\alpha = \left( {1 - {{\left( {1 - \frac{{{R_0}}}{R}} \right)}^N}} \right) \ge {\alpha _0},$ |
可以通过牛顿法求解N。
3 实验结果与分析文中所使用的数据集为微软亚洲研究院发布的GeoLife数据集,该数据集为微软亚洲研究院收集的182名用户的从2007年4月至2012年8月的日常生活的GPS定位数据。文中选取可其中一名用户的所有轨迹来进行可视化。
图 6展示了直接对原始数据进行可视化和利用文中方法对数据进行可视化的结果。
图 6(a)表示的是直接对原始数据进行可视化的结果。可以看到,在图片的左上角部分和右下角部分为轨迹密度较高的2个区域,在对原始数据的直接可视化的结果中,这2个区域均被弱化,而占据可视化结果主要部分的是2个区域之间的连线。
在可视分析中,除了这2个区域之间连线之外,往往也会关注左上以及右下区域中的轨迹模式。而且在一般情况下,认为左上和右下区域的包含有比连线更加丰富的信息,但在直接可视化的结果中这2个区域因为尺度较大而被弱化。在传统的可视化方法中,如果用户不主动在小尺度下分别查看,很难对这2个区域的信息有较为全面的掌握。
图 6(b)为用文中方法对轨迹数据进行可视化的结果。可以看出,与原始可视化结果相比较,左上和右下的信息与细节较多的区域被更全面地展示给了用户。事实上,对于有一定先验知识的用户,可以从图 6(b)中很明显地看出图片的左上区域对应的实际地理位置为北京及其周边区域,同时可以看出该轨迹上传者的主要活动范围为城区以及东南郊区。
在图 6(b)的图片中,除了显示了在大尺度下被忽略的信息之外,也引入了区域之间连线畸变的问题。进行可视分析的时候,通过地名、路网或交通等信息的复制,包含信息较少的区域的畸变并不会对分析造成十分显著的影响。在本例中,这2个区域之间的连线实际代表了该轨迹上传者往返北京与上海之间的行程;通过连线区域两端的地名信息,这段畸变的连线并不会对实际的分析造成困扰。
通过文中的方法,在大尺度下就将更多细节信息呈现给了可视分析的用户,降低了细节区域被用户忽略的风险,同时也提高了可视分析的效率。
图 7对比了参数N对于鱼眼放大效果的影响。由式(9) 可知
$\alpha = \left( {1 - {{\left( {1 - \frac{{{R_0}}}{R}} \right)}^N}} \right),$ | (14) |
可得α与N的关系,如图 8所示。
从图 8可以看出:当R0/R固定时,α是关于N的上凸函数。当N较小的时候,α随着N的变化有着较大的变化;当N较大时,α随着N的变换的幅度较小。
4 总结笔者提出一种新的轨迹可视化方法;在大尺度的轨迹可视化中,利用鱼眼视图对多个区域同时进行放大,同时提出了一种基于美学准则对多个鱼眼视图进行布局方法。文中方法考虑在不破坏轨迹连续性的前提下,结合轨迹可视分析的可以容忍一定失真特点,采用了鱼眼视图队轨迹信息进行强化。通过文中方法能够解决一些在可视分析中,因为尺度较大而带来的信息被弱化或者被用户忽略的问题。
[1] | Demšar U, Kirsi Virrantaus. Space-time density of trajectories:exploring spatio-temporal patterns in movement data[J]. International Journal of Geographical Information Science, 2010, 24(10): 1527–1542. DOI:10.1080/13658816.2010.511223 |
[2] | Cohenour C, Graas F V. GPS orbit and clock error distributions[J]. Navigation, 2011, 58(1): 17–28. DOI:10.1002/navi.2011.58.issue-1 |
[3] | Andrienko N, Andrienko G. Visual analytics of movement:an overview of methods, tools and procedures[J]. Information Visualization, 2013, 12(1): 3–24. DOI:10.1177/1473871612457601 |
[4] |
王祖超, 袁晓如.
轨迹数据可视分析研究[J]. 计算机辅助设计与图形学学报, 2015(1): 9–25.
WANG Zuchao, YUAN Xiaoru. Visual analysis of trajectory data[J]. Journal of Computer-Aided Design & Computer Graphics, 2015(1): 9–25. (in Chinese) |
[5] |
蒲剑苏, 屈华民, 倪明选.
移动轨迹数据的可视化[J]. 计算机辅助设计与图形学学报, 2012, 24(10): 1273–1282.
PU Jiansu, QU Huamin, NI Mingxuan. Survey on visualization of trajectory data[J]. Journal of Computer-Aided Design & Computer Graphics, 2012, 24(10): 1273–1282. DOI:10.3969/j.issn.1003-9775.2012.10.004 (in Chinese) |
[6] | Wang Z, Lu M, Yuan X, et al. Visual traffic jam analysis based on trajectory data[J]. IEEE Transactions on Visualization & Computer Graphics, 2013, 19(12): 2159–2168. |
[7] | Andrienko G, Andrienko N, Bak P, et al. Visual analytics of movement[M]. New York: Springer, 2013. |
[8] | Goncalves T, Afonso A P, Martins B. Visual analysis of mobility data[C]//IEEE International Conference on Mobile Data Management. IEEE, 2013:7-10. |
[9] | Jakobsen M R, Kasper H. Interactive visualizations on large and small displays:the interrelation of display size, information space, and scale[J]. IEEE Transactions on Visualization & Computer Graphics, 2013, 19(12): 2336–45. |
[10] | Cockburn A, Karlson A, Bederson B B. A review of overview+detail, zooming, and focus+context interfaces[J]. Acm Computing Surveys, 2009, 41(1): 1–31. |
[11] | Mikkel R J, Kasper H. Sizing up visualizations:effects of display size in focus+context, overview+detail, and zooming interfaces[C]//Proceedings of the SIGCHI Conference on Human Factors in Computing Systems. Vancouver, BC, Canada, 2011:1451-1460. |
[12] | Klein T, Matthew V D Z, Telea A. Dynamic multiscale visualization of flight data[C]//International Conference on Computer Vision Theory and Applications. IEEE, 2014:104-114. |
[13] | Liang S, Xu Q, Guo Y, et al. Multiscale visualization of trajectory data[C]//International Conference on Information Visualisation. IEEE Computer Society, 2015:206-210. |
[14] | Jakobsen M R, Hornbæk K. Fisheye interfaces-research problems and practical challenges[J]. Lecture Notes in Computer Science, 2011, 6431(16): 76–91. |
[15] | Gutwin C, Skopik A. Fisheye views are good for large steering tasks[J]. Proc Chi, 2002, 5: 201–208. |
[16] | Furnas G W. Generalized fisheye views[J]. Acm Sigchi Bulletin, 1986, 17(4): 16–23. DOI:10.1145/22339 |
[17] | Sarkar M, Brown M H. Graphical fisheye views of graphs[C]//Proceedings of the SIGCHI Conference on Human Factors in Computing Systems. ACM, 1992:83-91. |