讲故事是人类与生俱来的本领，就像《疯狂原始人》里主人公总是在夜里给大家讲故事一样，人们习惯并喜欢讲故事、听故事。但当故事复杂的时候，尤其是参与的人物之间关系随时间变化、故事的场景也随时间变化时，要很好地”讲“一个让人理解的故事就很有挑战性了。来自微软亚洲研究院的Liu等人在今年的VIS会议中提出的StoryFlow系统，很好地提供了一个基于故事线（Storyline）的追踪故事发展的可视化方法。如下图所示。
基于故事线的可视化，是将不同的人物利用线来表示，横轴表示时间，当两人有某种联系（同时出场、有交集等）会在一定的时间范围内相邻，这种方法最早见于手绘xkcd的项目。之后UC Davis的Tanahashi等人成功地将storyline的形式用计算机自动生成，并符合一些美学的标准，可以处理例如《李尔王》等复杂情节故事的可视化。但之前的工作具有以下的一些值得研究的问题，例如视觉美观和生成时间两者是一个矛盾权衡，如果要生成美观的图片，以前的方法都会耗时很久（对一部复杂的小说大概几十个小时），无法做到交互，但往往支持实时交互的作品却难以得到满意的视觉效果。还有就是之前的一些工作并没有考虑对象的层次性，例如地域的层次性（国家、省、市），而仅仅是扁平化的人物关系。并且当线条多了以后容易造成遮挡（Clutter），也并不可扩展。
因此StoryFlow针对以上几点问题，提出了一个实时可交互的、美观的、且展现实体层次关系的故事可视化方法，并且通过细节层次绘制（LOD）来解决了大量线条存在的干扰与性能下降问题。以下是工作流。
这个工作其实将布局分成两个阶段，首先基于一些标准生成一个初始布局，然后再基于原先已经优化的初始布局进行进一步的优化，通过将问题分解的方式，每步中可以减少计算复杂度，总体的可以支持交互。首先，我们来看看具体的要求，根据之前的一些工作以及他们整理的，要满足视觉审美，首先要减少相交的边（Line crossings），其次是线条摆动（Line wiggles），满足这两个要求后，尽量低应该减少摆动的距离（Wiggle distance）和空白部分（White space）。
那具体是如何一步步做到这样的效果的呢？首先，第一步是在每个时间步上构造一个关系树，这样需要满足实体的层次关系。获得了每个时间步的关系树之后，需要做排序（Ordering），排序的目的就是减少相交的边。具体分为两个步骤，首先将地点节点排序，然后将每个地点节点中的实体节点再继续排序。具体的排序方式使用了DAG中的sweeping算法的改进，具体请参考原论文【1】。排序之后，为了减少摇摆边的数量，于是需要对整个布局进行对齐（Alignment）。对齐的基本思想是将全局的最优化问题转化为局部的最优化问题，并且最后可以化简为最长公共子序列（LCS）算法进行求解。对齐之后，需要通过进行压缩（Compaction）来获得一个紧致且尽量对称的布局，这个问题也可以转化为线性约束的最优化问题来解决。
在这些算法之后，我们就获得了一个视觉愉悦的布局，但静态的布局并不能满足用户所有的需求，因此StoryFlow还提供了一系列实时交互，包括变捆绑操作、删除、移动以及直线化（Straightening）。变捆绑操作结合了LOD的绘制方法，可以解决可视化实体过多的问题。其他的移动、删除方式可以使得用户对结果定制到他们自己的需求。还有值得一提的是，直线化这一操作对于用户关注某个具体人物或者事件会有很大的帮助。
他们的评价和案例分析也做的十分到位，证明了他们工作的意义。例如在评估环节，量化分析证明他们的工作比先前的工作快了近1000倍，并且那些关键影响审美的要素都保持得很好。最后他们的例子不仅做了如第一幅图所示的故事可视化，StoryFlow也是具有可扩展性的，比如可以分析一些twitter数据，发现关于不同的人和话题随时间的演变。
总结一下，StoryFlow是一个基于高效的混合最优化算法，通过迭代的更新获得高效率且美观的故事线的方法。并且它可以描述一个基于层次关系的故事线布局，实时的交互也提高了它的交互能力与用户探索的功能，是一个美观和技术兼得的实践。
【1】Shixia Liu, Yingcai Wu, Enxun Wei, Mengchen Liu, Yang Liu. IEEE Transactions on Visualization and Computer Graphics, 19(12):2436-2445, Dec. 2013.
评论关闭。