基于信息熵的流场特征提取及可视化研究

牛 婵，梁 猛,高瑞波,聂俊岚,*

(1.燕山大学 信息科学与工程学院，河北 秦皇岛066004；2.燕山大学 河北省计算机虚拟技术与系统集成重点实验室，河北 秦皇岛066004)

0 引言

流场可视化中的特征可视化是矢量场数据研究领域中的热门方向，通过提取数据特征，忽略冗余数据，在保证信息准确性的同时大大减少了不必要的可视化数据量，能够很好地应用于复杂而庞大的海量数据研究。

特征提取的流场可视化方法是指提取并绘制用户感兴趣的特征信息，当前主要方法是分析流场拓扑结构，1991年由Helman等首先提出，通过计算矢量场中的一阶奇点来定位简单特征点并对其进行分类，可提取出流场中的基本结构信息[1]。2000年，Sadarjeo等在此基础上实现了矢量场中精细特征信息的自动提取，为实现基于交互的特征可选可视化方式奠定了基础[2]。1998年，Tang等为提高标量场拓扑结构信息提取的精度，在标量场中引入矢量化操作[3]，解决了标量场特征提取技术难以实现特征选择的问题。同年，Slilver等首次提出时变矢量场可视化的理论基础及处理方法，提出了一种清晰的时变矢量数据可视化的框架[4]。2014年Chaudhuri等通过分析空间流线实现了对矢量场特征信息的探索[5]。2015年Li等通过监测流线的线段分割对流场进行特征提取[6]。2016年，巴振宇等基于特征信息进行种子点选取实现了流线的多层次可视化[7]。2017年，鲁大营等提出了流场可视化中最优视点的选择方法[8]。此外，为了实现流场不同层次上的细节特征信息的可视化，近年来提出的多种流场拓扑结构简化绘制的理论与方法，成为了领域研究的热点。

信息熵量化了矢量场中方向信息变化的程度，可以帮助研究学者有效地确定变化剧烈的流场区域。2010年，Xu等人基于信息熵概念，首次提出了一种基于矢量信息内容引导的流场可视化框架[9]，先计算出矢量场各子区域的信息熵值，迭代测量信息内容并迭代布局种子点，直至达到满意的效果。2011年，Chen等人在此基础上对流线进行了相似性分组，在保持精度的同时有效解决了遮挡问题[10]。2013年，Tao等人在此基础上引入了视点概念，根据全局矢量数据创建不同的视点作为视点集，实现了不同视点下的相应流场信息可视化[11]。2014年，Jun等人为解决3D流场的特征信息可视化问题，设计了一种内部特征信息的自动计算方法[12]，有效解决了特征定位、流线布局、选取视点等问题。2015年，Liu等基于信息熵概念，提出了一种基于Clifford代数的流场特征信息自动检测方法[13]，根据预设的特征模板，通过Clifford卷积方法进行自动特征匹配操作，便于用户寻找感谢兴趣的特征区域。同年，张沙等基于条件熵的概念提出了一种种子点迭代布局更新的算法[14]，反复迭代直到条件熵收敛，该方法有效刻画了原始矢量场但计算繁琐。2016年，刘晓帆提出了基于信息熵与Clifford代数的流场特征检测[15]，流场信息熵的引入避免了大量无效的模版匹配，提高了特征检测效率。2018年黄冬梅等提出了基于贪婪策略的种子点选取方法[16]，得益于流场信息熵的计算，该方法对流场中的关键特征具有高度敏感性。

特征信息提取和交互式可视化探索是大规模矢量场数据可视化的两大研究重点。本文从信息熵应用于矢量场的角度出发，提出局部最大熵值和变化规律的概念，对矢量场的特征信息进行精确提取并基于此设计合理的种子点布局策略，同时对流场基于多分辨率的交互式可视化进行了探索。

1 特征提取

特征点定位是分析流场拓扑结构的基础。现有方法能够确定特征点的大概存在区域，但缺乏足够的精确度，只能选取熵值较大的区域进行特征提取，因此很容易遗漏掉一些特征信息。为弥补现有方法的不足，本文对信息熵及特征点之间的关系进行了深入探索。流场中存在很多重要的特征信息，例如旋涡、源点、汇点、鞍点、湍流等。图1展示了不同矢量场中的矢量信息分布情况。二维矢量场中的矢量角度量化范围为θ∈[0,360),将其划分成60个区间段，每个区间段的长度为6。图1(a)和图1(b)分别为马鞍型矢量场和中心型矢量场及其相对应的矢量信息分布情况，图1(c)和图1(d)为无特征矢量场及其相对应的矢量信息分布情况，很显然特征区域的矢量信息比非特征区域的信息分布要均匀，即信息的变化量大。图1(a)、1(b)、1(c)、1(d)中矢量场所对应的信息熵值依次为5.79、5.82、4.36、2.42。信息变化越大的矢量场，其信息熵值越大，就越有可能存在特征点，这为矢量场的特征信息提取提供了可靠有效的依据。

图1 不同矢量场中的矢量信息分布
Fig.1 The vector information distribution in different vector fields

由特征点的定义可知特征点周围区域的矢量方向变化最为剧烈，因此特征区域范围内的矢量数据必定是特征点所对应的熵值最大，即特征点处熵值必为局部最大值。但局部最大熵值不一定为特征点，因此需要进一步进行分析判断，为此提出一种基于局部最大熵值并结合线性插值原理的特征点定位算法。

1.1 特征点定位

假设矢量场中的某点P在各个分量上的速度均为零，即满足(up,vp,wp)=0则称P点为特征点。设一个特征点候选网格区域，(xi,yi)表示顶点Vi的坐标位置，(ui,vi)表示顶点Vi的矢量值。对特征点候选单元网格的4个顶点数据的某个方向分量进行正负标记，首先分析x方向，正值标记为1，负值标记为0。每个候选特征单元有4个顶点，每个顶点均可能有0、1两种标记情况，因此理论上总共可以有16种标记情况。

以情况0001为例进行分析，若4个顶点的u方向(u0,u1,u2,u3)标记为状态(0,0,0,1)的话，由于实际矢量场的变化可看成是连续线性变的，因此候选特征网格中的边V2V3必定存在分量u为0的P点，边V0V3之间必定存在分量u为0的Q点。根据线性插值原理便可求出P、Q两点的坐标。P点坐标的计算公式为

(1)

采用相同的方法可求Q出点的坐标，则线段PQ表示该候选特征网格中u=0的集合，即u=0的等值线段。同理可求出v=0的等值线段MN。计算线段PQ和线段MN的交点记为O，判断O点是否在当前的候选特征网格内，若在网格单元中则判定该交点为特征点。

拓扑结构信息的基础构成包括特征点和描述特征点的积分曲线，其中积分曲线一般使用几何可视化中的流线。根据特征点周围区域方向变化规律，即特征点周围区域的方向变化最剧烈，距离特征点越远，区域的方向变化剧烈程度则随之降低。将该规律对应于熵场，对于简单矢量场其表现形式为特征点处的熵值最大，向外延伸熵值依次降低，直到熵值变化趋于零。对于复杂矢量场，即特征区域相互作用，其表现形式为特征点处熵值最大，向外延伸依次降低，直到熵值逐渐增大，其临界值的位置即为特征区域的边界。

1.2 特征点类型检测

特征点按类型分类主要分为中心点(center)、聚点(focus)、鞍点(saddle)、交点(node)等四大类型，其中focus类型和node类型又分别可被分为排斥(repelling)类型和吸引(attracting)类型这两种情况，因此一共细分为6类。特征点类型的判断，可以通过列出特征点位置的雅克比矩阵J，求其特征值，然后对特征值实部和虚部进行正负判断，特征值实部和虚部的正负状态代表着不同类型的特征点，特征点处的Jacobian矩阵形式为

(2)

根据矩阵J的特征值λ1和λ2，用Re(λi)、Im(λi)分别表示λi的实部和虚部，特征点类型的判断依据如下：

1) 源点：0

2) 排斥鞍点：Re(λ1)<0

3) 吸引鞍点：Re(λ1)≤Re(λ2)<0

4) 汇点：Re(λ1)≤Re(λ2)≤Re(λ3)<0。

1.3 特征区域界定

结合特征区域的信息熵值变化规律对特征区域进行界定，逐层对特征区域内的熵值进行比较，采用内层与外层熵值的差值进行判定，计算方式为

Variation=Entropy1-Entropy2，

(3)

其中，Entropy1表示内层熵值，Entropy2表示外层熵值，Variation表示内层熵值与外层熵值的差值，若差值大于零，则表示仍在该特征区域的影响范围内，若该差值趋于零或等于零则表示到达该特征值的影响区域边界。在进行熵值比较时，对于大规模流场数据来说，若对特征区域各层数据内的熵值都进行差值比较运算，则计算规模必然庞大。不同特征所对应的影响区域均呈现一个圆形，因此只需对特征区域4个方向上的值进行熵值数据比较运算即可。运用差值比较方法对特征区域进行界定计算，针对特征区域的4个方向上的信息熵值进行差值比较，即减少计算量，又保持精确度。图2给出了熵值变化规律计算的模板。

图2 熵值变化规律计算模板
Fig.2 A template for calculating the law of entropy change

2 基于特征信息的流场交互可视化

基于流线的矢量场可视化方法具有较好的视觉表达效果，但流线刻画流场信息的质量严重依赖于种子点分布策略的选取。本文采用基于特征点的种子点布局方案，并设计一种基于多分辨率的可视化方法，完成矢量场信息的高精度绘制。在判定特征点的位置和类型后，为了更加精确地描述特征点周围的矢量流动模式，可以在特征点影响范围区域内，根据其特征类型来选取相应的流线种子点播撒模式。

种子点布局方案的主要思想为根据特征点的位置确定种子点模板的播撒位置；根据特征点的特征类型选取合适的种子点模板类型；根据特征点的影响区域的界定来确定种子点模板的放置规模。实现了严格依据矢量场特征点的三大特征信息对流场进行种子点布局。

对于矢量场的拓扑结构信息可视化展示，结合矢量场特征点的位置、类型、影响区域范围进行针对性的种子点播撒并进行流线积分绘制。对于流场的全局信息可视化展示，在基于拓扑结构种子点播撒方案的基础上对非特征区域采取均匀的种子点播撒模式。如图3所示，其中图3(a)展示的是原始矢量场数据，图3(b)是流场特征点的位置判断及特征影响区域的界定结果，图3(c)是流场拓扑结构信息可视化的种子点布局方案，图3(d)是流场全局信息可视化的种子点布局方案。

图3 种子点布局策略
Fig.3 The change regulation of entropy in entropy field

本文采用GPU生成积分流线。GPU的优势主要是其中含多个几何着色器(Geometry Shader，GS)，能够实现多个图元同时进行计算，很大程度上降低了计算时间，GS是存在于GPU中的顶点着色器和片段着色器之间的一种着色器，它的计算单位为图元。相较于顶点着色器其优势是可以在同一时间段处理某一图元中的所有顶点信息，并且能对这些顶点进行修改、删除等操作，能够实现对输入的几何形态进行修改并输出另外一种全新的几何形态。利用这一原理，将积分生成流线所用到的种子点信息转换成图元表示形式，将矢量场数据转换成纹理表示形式，并将其传输进入图形管线中，流线的积分生成过程全部在GS中执行，如图4所示。以这种方式采用PK4积分器计算生成流线，很好地弥补了其复杂的计算过程要求实现了实时性。

图4 基于GPU的RK4积分生成流线方法
Fig.4 Based on GPU RK4 integral to generate streamline method

3 实验及分析

实验在64位Win7操作系统下完成，中央处理器为Intel i7-4770k 3.5GHz，内存为32G，显卡为NVIDIA GTX770。本文实验所使用的数据是由NOAA公开的二维全球流场数据，数据规模为1 440×720，数据格式为规则网格结构。

本文利用信息熵提取流场中方向变化剧烈的区域，首先基于局部最大熵值提取出特征点，然后严格根据特征信息来可视化矢量场。

如图5所示，图5(a)为比例信息熵的计算方法，主要思想是选取信息熵值较大的区域，在其中心位置布局菱形种子点模板并积分生成流线，但没有针对性地计算特征点位置及类型。而图5(b)为本文算法。使用本文算法所可视化出的矢量场特征信息明显要多，因为算法是严格根据特征信息布局种子点并生成流线，而不是只针对采样点进行流线积分生成操作。譬如用红色方框画出的是矢量场中重要的漩涡特征，而该特征信息在图5(a)中并没有可视化出来，这说明图5(a)的方法不能绘制出矢量场中的所有特征信息，如果此基础上利用条件熵对流线进行删减、添加操作，但是会使得计算量变大，尤其不适于大规模矢量场。

图5(c)为基于区域信息熵的计算效果，图5(d)为本文算法绘制效果，其中方框画出的特征信息，同样在图5(c)中被丢失。图5(c)采用的方法主要思想是对矢量场数据进行粒度的网格划分并分别计算出网格区域的信息熵值，对信息熵值较大的网格区域进行特征点检测，并计算特征点类型然后根据矢量场的特征点位置和类型布局种子点。该方法虽然实现了基于特征点的位置和类型的计算，但其最大的不足在于只选取信息熵值较大的部分流场网格区域进行特征信息检测，显然很可能会遗漏掉某些存在特征信息的网格区域。而本文方法则是根据特征点区域熵值,首先找出可能是特征点的所有矢量点集合，再通过零点定理对其进行筛选，以确定特征检测的完整性和准确性。绘制效果图验证了本文算法的有效性。

图5 本文算法与现有算法效果对比图
Fig.5 The comparison between existing algorithm and this paper′s algorithm

在特征分布较为稀疏的矢量场区域，必然会将非特征区域划入其中，导致特征种子点模板的播撒规模变大，因而不能精确地提取出流场的拓扑特征。在性能方面，常用的维诺图划分方法主要有分治算法、增量算法、扫描线算法和基于Delaunay三角剖分的算法，其中基于Delaunay三角剖分的算法速度相对较快，但其时间复杂度也达到了o(n2)，而本文提出的基于熵值变化规律的特征区域界定算法只需对特征点4个对角方向的熵值进行变化率计算，其时间复杂度为o(n)，因此本文算法在提高了绘制效果的同时也提高了计算性能。

在绘制性能方面，选取了三种单一分辨率与本文所提出的多分辨率方法在不同的视点与矢量场距离下进行了绘制帧率的性能比较，如表1所示，其中帧率(5)、帧率(10)、帧率(15)分别表示种子点密度为每经度5个、10个、15个的种子点集合所构成的流场种子点布局，其中视点距离单位为百万米。

表1 种子密度与帧率的对比Tab.1 Comparison of seed density and frame rate

分析表中数据可得出随着距离改变积分绘制性能呈下降趋势。表中最后一列多分辨率为采用本文算法的实验结果，在视点距离较近时，绘制帧率较每个经度15个种子点集合的效果有所提高，而在视点距离较远时，运算速度大幅度提升，说明多分辨率方法在保障数据特征提取的前提下，绘制性能有很大提高。

4 结论

特征信息提取和交互式可视化探索是当前大规模矢量场数据可视化的两大研究重点。针对传统方法对特征区域界定不准确问题，提出了一种基于局部最大熵值的特征点检测方法，将信息熵应用于矢量场的特征提取，实现了特征精确提取及种子点合理布局策略；为更好地展示数据的规律，设计实现了基于多分辨率的交互式可视化方法，通过实验验证了该方法在大规模矢量场中的有效性。在未来，本文的算法可以应用于三维矢量场数据，在更加复杂的矢量数据中进行探索，实现用户对特征信息的高精度刻画。