图可视化中的边绑定技术研究

摘要

近年来，急剧增长的数据规模导致太多的边拥挤在有限的展示空间中，所谓的视觉混乱(visual clutter)严重阻碍了点线图的可用性。
　　边绑定将视觉上相似的边捆扎在一起形成可辨识的、所谓的边束，从而减少视觉混乱。边绑定能够在仅牺牲部分细节的条件下，揭露出数据中潜在的宏观模式，即骨架或骨干结构。这对于用户认知整体结构至关重要。学术界已经提出了若干种边绑定方法，它们基于不同的范式，例如，力导向模型，几何结构，路径规划，图片骨架提取等。然而，由于强烈的吸引效应，前人结果中表现出锋利且不必要的弯曲，在边束相交的区域形成有害的纠缠，引入误导用户的树枝状模式。
　　因此，本文提出了边绑定的3个主要目标，即揭露骨架，形成可辨别的边束和尽可能让边束可追踪。我们设计了一个参数化的、6步组成的边绑定方法，命名为LEB，即层次边绑定算法。LEB依据边的方向属性，将边分配到不同的方向层次中，并依据穿过的边的数量和方向计算出单元格的权重。之后，在层次中进行基于参数化A*算法的路径规划。方向隔离有效地阻隔了不同方向边之间的相互污染。形成了更少弯曲、可辨识、可追踪的边束。我们也提出了充分利用算法产出、简单且有效的边束识别和着色算法，这使得结果更加清晰地凸显出不同的边束和整体结构。
　　LEB算法中包含7个用户调节参数，我们讨论了各个参数影响的范围，调整方法和合理的初始值设定。我们在浏览器中实现了LEB算法，基于JavaScript。实现中，利用路径复用技术减少了大量的冗余计算，这让算法复杂度主要依赖于网格粒度，而不是数据规模。表现试验充分支持了LEB的高效性，在未利用计算优化的情况下，LEB已经都能够支持实时交互。我们在三个公开的、被广泛使用的数据集上，展示了LEB的效果。结果显示LEB不仅达成了3点目标，并且不论在固定顶点布局，还是抽象顶点布局场景上都能揭露出数据的整体结构。
　　最后，为了评估和比较，我们设计了用户对比实验。实验要求被试使用固定数量的笔画勾画出绑定结果中的骨架。通过笔画覆盖边的数量之指标，我们量化了任务表现。统计结果充分支持了LEB的优越性。不管是在哪个数据集中，LEB都具有最好的表现，且是统计上显著地区别（优于）其他边绑定结果。需要指出的是，学术界目前不存在对边绑定方法评估的有效实验。

目录

声明

摘要

第一章 绪论

1．1 研究背景及研究意义

1．2 国内外研究现状

1．3 本文研究内容和组织结构

第二章 边绑定技术相关背景

2．1 图、顶点和边与相关可视化

2．2 模型的参数空间

2．3 连线视觉隐喻

2．4 两种复杂度

2．5 评估范式

2．6 小结

第三章 分层范式下的边绑定技术

3．1 设计目标

3．2 算法总览

3．3 发现主方向

3．4 方向层次下的划分空间

3．5 路径规划

3．6 路径平滑

3．7 识别边束并作色

3．8 处理短边

3．9 小结

第四章 渲染和参数设定

4．1 渲染

4．2 参数调整目标

4．3 主方向数量

4．4 方向分布直方图的粒度

4．5 角度阈值

4．6 单元格尺寸

4．7 估计权重因子

4．8 相似性度量阈值

4．9 短边阈值

4．10 小结

第五章 案例研究

5．1 人口迁移数据集案例

5．2 航空数据集案例

5．3 引用数据集案例

5．4 小结

第六章 算法实现

6．1 框架设计

6．2 路径复用

6．3 算法表现

6．4 小结

第七章 评估与比较

7．1 实验设计

7．2 被试与设备

7．3 实施过程

7．4 结果分析

第八章 总结与展望

参考文献

发表论文和参加科研情况说明

致谢