使用信息论故事版选择大规模时变体数据集中的关键时间步 (Key Time Steps Selection for Large-Scale Time-Varying Volume Datasets Using an Information-Theoretic Storyboard)

在科学可视化中,随着数据规模的不断增大,时变数据往往包含了大量的时间步。由于内存和I/O带宽的限制,对所有这些时间步进行可视化经常比较困难。实际上,这些数据在连续的时间步的变化很可能非常小,其包含的信息也并不重要。解决这一问题的一个可能的方法是从中选取具有最显著特征的几个关键时间步进行可视化。但是,数据中重要特征的随时间的变化可能包含复杂的模式,并且会以未知的频率发生。如何选择关键时间步也成为了一个挑战。因此,今年EuroVis的一篇文章[1]提出了一种新颖的方法,可以使用动态规划来提取出数据中的关键的时间步。

方法的基本思想是:给定两个选定的时间步,如果中间被跳过的时间步可以使用线性插值从这两个时间步中以较小的信息差异进行重建,那么这两个选定的时间步就可以代表那些被跳过的时间步。重建的数据和其原始数据之间的信息差异可以使用信息论的方法来衡量。依据这种思路,文章设计了一种动态规划的方法,可以在最小化信息差的情况下提取出关键时间步。而后,为了能够获得最优的I/O并加速计算过程,作者将该方法拓展到了一种核外近似计算算法。

首先来看信息差是如何计算的。信息差的计算用到了信息熵的概念。两个时间步之间所包含信息的差异可以通过它们之间的条件熵计算得到。通俗来讲,也即是分别只在其中一个时间步出现的信息量之和,如图1所示。因此,给定两个选定的时间步i和j,对于i和j之间每一个跳过的时间步r,我们可以通过线性插值得到一个时间步,然后计算插值得到的时间步和其原始时间步r之间所包含信息的差异。最终我们可以将这些跳过时间步所产生的信息的差异相加,并将其定义为时间步对(i, j)的信息差(Information Difference, InfoD)。

图1 两个时间步信息之间的差异

接下来,根据初始算得的信息差,作者使用了一种动态规划的方法,如下图2所示公式,可以从[1, i]时间步范围内选择k个关键时间步。该动态规划的思想是,为了选择k个时间步,其会尝试1和i之间的每个时间步p,使得p和i是所选时间步之间最后的两个时间步,并找到具有最小信息差的那个时间步。(注意:为了保证能够进行线性插值,第1个时间步和最后一个时间步i必须要选定。)图3展示了选择表图和总信息差曲线,用以指导用户的探索。两个图的纵轴都表示所选时间步的个数,并且相互对齐。选择表图中的横轴表示所选的时间步。从该图中,我们可以清楚地看到总信息差是如何随着选择不同时间步而改变的。

图2 动态规划计算公式

图3 飓风Isabel的选择表图和总信息差曲线

在上述方法中,如果两个时间步i和j相距太远,那么计算(i, j)对之间的信息差c(i, j)将会变的困难。其中一个理由是有限的内存很可能容纳不下i和j之间所有的时间步。另一方面,针对相距太远的时间步的计算实际上在关键时间步的选择上很少用到,因为跳过其中所有的时间步并不太可能。因此,文章提出了一种核外(out-of-core)近似计算的算法,通过一个多重的动态规划来实现。

假设内存可以容纳t个时间步,我们先定义一个工作集S和一个滑动窗口W。在第一重计算中,工作集S包含所有时间步。我们在S上滑动W,首先读取S中前t个时间步。之后,对每一个j (j ≤ t)计算信息差c(1, j),对其他的j将c(1, j)设置为正无穷大。然后,我们向后滑动W一个位置,并在内存中保持第2个到第t+1个时间步,之后同样地,对每一个j (j ≤ t+1)计算信息差c(2, j),对其他的j将c(2, j)设置为正无穷大。该过程一直持续,直到滑动窗口W滑动到最后一个时间步。此时根据当前计算的信息差c(i, j),可以运行动态规划算法并提取出最佳的T/2个时间步。

图4 被跳过的时间步信息差异的近似计算

图5 性能结果

在第二重计算中,我们将前一步所选的T/2个时间步作为该重的工作集S。第二重的计算过程与第一重的类似,都是在工作集S上滑动窗口W。在该过程中,c(i, j)仅仅只有在其值是正无穷大时才会更新。第二重结束后,会选取最佳的T/4个时间步,并将其作为下一重的工作集。需要注意的是,从第二重开始,由于跳过的时间步可能不在内存中,因此我们不可能精确地计算其信息差。因此,这里使用了一种近似方法,即将跳过的时间步使用当前存在于内存中的时间步代替,用于快速计算。如图4所示,第二行被紫色下划线标注的5个时间步均被时间步r所替代计算,也即是我们假装它们都将r作为其原始数据。这样这5个时间步对c(i, j)的贡献即为5倍的时间步r处的信息差异。在第二重计算之后,剩下的多重计算会持续将工作集S减半。当S的数量小于t时,迭代过程结束,我们可以运行动态规划算法得到k个关键时间步。

图6 Vortex数据结果图

图7 在两个数据集中选择关键时间步的渲染结果

图5展示了使用两个数据的结果,包括核内精确计算(内存可以容纳所有时间步)和核外近似计算(内存较小仅能容纳部分时间步)。可以看到,计算信息差的时间占据了总运行时间的主导地位。另外,该近似方法的误差也在可接受范围之内。图1和图6进一步展示了关键时间步选择的结果图。对于飓风Isabel数据,当选择很少一部分时间步时信息差下降很快,但随着k的增加其下降速度变缓。这是因为在连续时间步上有非常多的冗余信息,因此只选择少量时间步就能够很好地表示数据全集。对于Vortex数据,其包含的信息在所有时间步上的分布更加均匀,因此可以看到每行的选择都很可能具有间隔相等的蓝色块。图7展示了所选时间步的体绘制结果。用户可以根据选择表图和总信息差曲线来选择不同的关键时间步来对数据进行探索。

Reference

[1] Bo Zhou and Yi-Jen Chiang. Key Time Steps Selection for Large-Scale Time-Varying Volume Datasets Using an Information-Theoretic Storyboard. Computer Graphics Forum, 37(3):37-49, 2018.

评论关闭。