基于特征分布的三维流线相似性研究

张伯雄， 谢伙生

(福州大学数学与计算机科学学院， 福建 福州 350116)

基于特征分布的三维流线相似性研究

张伯雄， 谢伙生

(福州大学数学与计算机科学学院， 福建 福州 350116)

针对利用流线的形状特征对流线进行分类和选取， 可以方便用户洞察三维流场的特征, 提出一种高效的基于特征分布的三维流线相似性比较方法. 该方法在Lu Kewei等流线相似性比较方法的基础上， 引入曲折度和速度方向熵两个全局属性. 首先将流线均匀分段， 然后计算每段的曲率直方图、 扭率直方图、 曲折度直方图、 速度方向熵直方图， 构建相应的二维直方图， 最后利用堆土机距离(EMD)及k-means聚类方法进行流线相似度计算和分类. 实验结果表明， 该方法在引入全局几何属性后能够产生更鲁棒性的查询和分类结果.

流线相似性； 特征分布； 二维直方图； 流线聚类

0 引言

流场可视化是科学计算可视化的一个重要课题, 在许多科学和工程领域， 可视化矢量场在理解潜在的流场特征和模式方面起着重要的作用. 流场可视化研究方法包括基于图标的方法[1]、 基于纹理的方法[2]、 基于几何图形的方法[3]和基于特征结构的可视化方法[4]. 其中因为流线便于计算， 可在不同分辨率下以交互的速率进行渲染， 所以流线可视化方法是最普遍使用的方法之一. 但当成千上百条流线被渲染描绘一个流场时， 由于杂乱和遮挡问题， 用户很难发觉潜在的流场特征， 而且用户往往只想查看具有特定形状特征的流线. 因此， 将流线基于形状特征进行分类， 展示和用户目标相关的流线是非常重要的.

流线相似性度量和分类工作中， 有许多是基于点和点之间的距离. Chen等[5]把流线间局部相似性度量的方法引入到流线生成中， 这种度量方法涉及流线形状和方向的统计信息， 以及每对流线的欧式距离； Yu等[6]计算流线间点对的欧式距离， 使用平均最短点距离度量流线相似性， 最后结合单链接方法进行层次聚类. 但这些相似性度量方法不具有旋转、 平移、 缩放不变性， 两条相似的流线可能因为方向不同、 距离过远、 长短不一而导致度量距离过大不能划分为同一类. 鲁大营等[7]提出了一种基于迭代最邻近点(ICP)算法与k-means聚类方法的流线生成算法， 首先利用ICP算法实现流线间轮廓特征上的配准并根据几何相似性进行排序， 然后利用k-means聚类算法对流线分组， 这种方法虽然具有旋转、 平移不变性， 但计算量过大.

近年来， 基于流线特征分布的相似性度量方法越来越受到重视. Mc Loughlin等[8]计算流线每点的各种特征值， 构建1D直方图， 并用χ2测试比较相似性， 但由于形状不相近的流线也可能具有相似的1D直方图， 文献[8]的方法将不相似的流线归为一类. Lu等[9]考虑特征的空间分布信息， 将流线分段， 构建2D直方图， 解决了文献[8]方法中由于空间信息丢失导致的流线相似性度量错误， 但他的相似度量方法只考虑流线的曲率和扭率两种局部属性， 当流线选取的比例增大时， 新增流线的整体形状可能与目标流线有较大的偏差. Li等[10]受特征包想法的启发， 选择k个具有代表性的特征矢量作为词汇， 在词汇组合中考虑两点的弧长信息从而构建空间敏感的特征包， 通过加权的曼哈顿距离进行流线间的相似性计算， 并考虑流线的曲折度和速度方向熵两个全局属性， 使得查询的流线结果与目标流线在整体上更加贴近. 但由于文献[10]中加权曼哈顿距离不一定能正确表达人对流线相似性的理解， 在流线聚类实验中， 可能使一条螺旋上升的流线被错误地划到与其形状相差甚远的流线组中. 相比之下， 文献[9]中基于2D直方图的方法仍能正确地聚类， 具有更好的鲁棒性.

因此， 采用2D直方图比较流线相似性， 保证流线相似性比较和分类的鲁棒性， 并引入文献[10]中所用的曲折度和速度方向熵两个全局属性， 使得流线相似性比较在全局属性上也能更加接近目标流线， 产生更准确的相似性度量结果.

1 三维流线特征的选择

选取合适的特征描述子是构建直方图重要的一步. 为了选取形状相类似的流线, 本研究选取能够描述流线形状的相关特征描述子. 首先选择曲率和扭率， 因为它们分别表示了曲线的弯曲程度和脱离密切面的变化程度. 曲率和扭率属于流线的局部几何属性， 为了能结合流线的全局几何属性进行比较， 接着引入曲折度和速度方向熵. 曲折度反映了曲线整体的弯曲程度； 速度方向熵反映了速度方向的均匀程度， 亦即流线的平坦程度.

1.1 曲率

曲率是正切矢量关于弧长的变化率. 曲线上某点p的曲率， 可以通过下式进行计算：

(1)

1.2 扭率

扭率的计算公式如下：

(2)

其中:det表示矩阵的行列式.

1.3 曲折度

曲折度是曲线长度和始末两点最短距离之比. 曲线的长度通过组成流线的直线段的累计长度来近似， 始末两点的最短距离采用欧几里得距离进行计算.

对于流线上点p的曲折度， 先算出起点和该点间的弧长s(p)， 然后除以两点间的欧几里得距离， 其计算公式如下所示：

(3)

其中:p0是起始点位置.

1.4 速度方向熵

对于流线上每一点， 使用该点小范围领域的N点来计算熵值. 为了计算熵值， 使用文献[11]的算法把单位球体分成50份相同面积的区域， 并判断每个矢量指向哪一块. 对于流线上点p的速度方向熵可通过下面的公式进行计算：

(4)

其中:di是领域中样本点落入i方向块的频率.

2 基于特征分布的流线相似性查询与分类

2.1 流线特征的2D直方图

流线特征分布可选1D直方图与2D直方图. 对于1D直方图， 存在两条形状不相同的流线并可能有着相似的特征分布的问题. 例如， 图1(d)曲线由图1(a)曲线经过分割后拼接生成. 显然， 它们有着相同的一维特征分布， 但是两者的形状并不相同. 两条曲线的1D曲率直方图分别如图1(b)和图1(e)所示.

本研究采用2D直方图， 对于给定的流线， 将其分成M段， 每段具有相同数目的样本点数， 接着对每一段建立一个1D直方图， 从而构建2D直方图. 由于携带了空间信息， 2D直方图可弥补由于丢失空间信息而导致的流线相似性度量错误的不足.

图1(c)和图1(f)分别为曲线1(a)和曲线1(d)的2D直方图； 在把曲线分成4等分后， 曲线各段的特征分布情况便体现在2D直方图中.

2.2 基于k-means的三维流线分类

本文中k-means新的聚类中心计算公式为：

(5)

其中:C(j， t)为第j簇新中心的第t个特征直方图；H(i， t)为流线i(或聚类中心i)的第t个特征直方图；nj为第j簇所包含的流线下标集合.

流线(或聚类中心)i，j的EMD相似性距离度量公式为：

(6)

k-means聚类的目标函数为：

(7)

计算具体步骤如下：

Step1: 选择k条流线作为初始聚类中心；

Step2: 使用公式(6)计算出流线到各簇类域间的距离， 并把流线划分到距离最短的一类中；

Step3: 使用公式(5)更新各簇类中心；

Step4: 重复Step2和Step3直到目标函数(7)小于一定的误差或者达到一定的迭代次数， 终止计算.

2.3 交互式流线相似性查询与分类方法

首先通过密集播种， 生成大量的流线； 然后根据每条流线的弧长， 均匀地插值采样相同数量的N个点； 接着计算流线上每点的特征值并建立2D直方图； 在最后的用户交互里， 根据用户选择的流线， 利用EMD计算每条流线与目标流线的直方图距离， 根据指定的数量比例显示最相似的流线组； 然后使用k-means聚类方法进行流线分类， 按用户要求显示感兴趣的聚类结果. 在交互期间用户可以调整流线段数和特征值等分数； 也可以采用不同属性组合或者赋予不同权值进行相似性比较试验.

3 实验结果与分析

本研究使用两组数据进行实验. 第一组数据由Roger Crawfis的台风模拟算法生成， 第二组数据是来自文献[12]提供的五临界点数据集. 下面对这两组数据分别进行流线相似性查询和流线聚类实验.

3.1 运行时间测试

实验采用CPU-GPU混合解决方案. 硬件配置为： Intel Core i5-3470 CPU， 频率 3.2 GHz； 16 G内存； GT630显卡. 使用CPU进行流线的生成， 采用CUDA技术对特征以及直方图进行并行计算. 表1列出了特征值估计、 直方图构建及相似性比较所用的时间.

表1 实现时间Tab.1 Implementation time

从表1中可以看出， 特征值估计和直方图构建所用时间都非常短， 用户可以调整流线划分的段数M和特征值的划分数N. 由于调整是对单个特征的直方图进行， 所以在1～2 s内便可获得调整效果反馈.

3.2 流线相似性查询实验

试验中台风数据集和五临界点数据集分别生成600条和500条流线， 每条流线采样1 000点. 流线均分成10段， 四种特征值均划分为30块. 速度方向熵中领域的取点数左右各取20点. 在选取完目标流线后， 加入各种属性进行相似性比较. 实验对比效果如图2～4所示.

实验显示结果可以明显地看出：

1) 图2(b)中, 当台风流线最相似流线增加到50%时， 新增流线虽然也是漩涡状， 但已开始向外伸展， 而图2(c)中在加入全局属性后新增流线依然贴近目标流线.

2) 图3～4中, 五临界点数据流线在考虑全局属性后整体也更向目标流线靠拢.

3) 图4(d)中, 不加入扭率， 选取的流线更为平坦.

由此可见, 不同属性体现流线的不同形状特征， 简单地将各特征直方图通过EMD计算出距离后相加可能不足以突显流线的形状特征. 不同属性间的组合， 赋予各特征直方图相似性距离以不同的权值可以更好地体现流线形状特征.

3.3 流线分类实验

实验中两组数据均用k-means聚类方法， 在相同初始聚类中心的条件下聚成3类， 不同颜色的流线组表示不同的类簇.

图5～6为聚类效果对比图. 从结果中可以看出， 图5(c)中红色簇下端流线部分更接近于图5(a)中蓝色的流线簇. 考虑了全局属性的聚类结果将红色部分归为蓝色簇， 聚类后整体在形状上更加贴合.

图6为五临界点数据流线聚类效果. 从结果可以看出， 加入全局属性后黄色簇流线都较顺直， 红色簇流线中都是两端螺旋. 从两组数据的聚类结果可以看出， 加入全局属性后簇内流线更加相似， 簇间差别更加明显.

4 结论

本研究通过特征2D直方图距离进行流线相似性比较， 克服了1D直方图空间信息丢失的缺陷， 同时引入曲折度和速度方向熵两个全局属性， 使得流线相似性查询和聚类结果都更具鲁棒性， 整体形状更加紧凑. 该方法采用CUDA技术对特征值和直方图进行并行计算， 消耗的时间都非常短， 为用户提供了实时的交互查询体验. 该方法中直方图如何量化， EMD距离如何计算， 是影响相似性比较结果的关键. 在流线特征值分布极不均匀时， 如何以较小的块数进行划分， 如何设计EMD距离， 不仅影响相似性比较的计算量， 也影响其比较效果. 这些问题将是下一步的研究方向.

[1] KLASSEN R V， HARRINGTON S J. Shadowed hedgehogs: technique for visualizing 2D slices of 3D vector fields[C]//Proceedings of the 2nd Conference on Visualization′91. [S.l.]: IEEE Computer Society Press， 1991: 148-153.

[2] SUNDQUIST A. Dynamic line integral convolution for visualizing streamline evolution[J]. IEEE Transactions on Visualization and Computer Graphics， 2003， 9(3): 273-282.

[3] MA J， WANG C， SHENE C K. Coherent view-dependent streamline selection for importance-driven flow visualization[C]//Proceedings of SPIE - The International Society for Optical Engineering. San Francisco: SPIE， 2013， 8 654(5 755): 1-15.

[4] OZEN C A ， ROCKWELL D. Flow structure on a rotating plate[J]. Experiments in fluids， 2012， 52(1): 207-223.

[5] CHEN Y， COHEN J， KROLIK J. Similarity-guided streamline placement with error evaluation[J]. IEEE Transactions on Visualization and Computer Graphics， 2007， 13(6): 1 448-1 455 .

[6] YU H F， WANG C L， SHENE C K，etal. Hierarchical streamline bundles[J]. IEEE Transactions on Visualization and Computer Graphics， 2012， 18(8): 1 353-1 367.

[7] 鲁大营， 朱登明， 王兆其. 三维流场的流线提取算法[J]. 计算机辅助设计与图形学学报， 2013(5): 666-673.

[8] MCLOUGHLIN T， JONES M W， LARAMEE R S，etal. Similarity measures for enhancing interactive streamline seeding[J]. IEEE Transactions on Visualization and Computer Graphics， 2013， 19(8): 1 342-1 353.

[9] LU K， CHAUDHURI A， LEE T Y，etal. Exploring vector fields with distribution-based streamline analysis[C]//2013 IEEE Pacific Visualization Symposium. Sydney: IEEE， 2013: 257-264.

[10] LI Y F， WANG C L， SHENE C K. Streamline similarity analysis using bag-of-features[C]//Proceedings of SPIE - The International Society for Optical Engineering. Francisco: SPIE， 2013， 9017: 628-637.

[11] LEOPARDI P. A partition of the unit sphere into regions of equal area and small diameter[J]. Electronic Transactions on Numerical Analysis， 2006， 25(12): 309-327.

[12] YE X， KAO D， PANG A. Strategy for seeding 3D streamlines[C]//16th IEEE Visualization Conference VIS 2005. Minneapolis: IEEE Computer Society， 2005: 471-478.

(责任编辑： 林晓)

3D stremlines similarity analysis based on distribution of measurements

ZHANG Boxiong， XIE Huosheng

(College of Mathematics and Computer Science， Fuzhou University， Fuzhou， Fujian 350116， China)

Considering the feature of shape， classification and selection of streamlines advance the understanding of the features in 3D flow field.In this paper， we propose an efficient 3D streamlines similarity comparison method based on distribution of features. This method is based on the streamline similarity comparison method proposed by Lu Kewei et al. and introduces two global geometric properties: tortuosity and velocity direction entropy. At first， we divide each streamline into segments evenly， then we construct curvature histogram、 torsion histogram、 tortuosity histogram and velocity direction entropy histogram for each segment， and form corresponding 2D histograms.In the end， we use the Earth Mover’s Distance(EMD) and k-means clustering method to measure the similarity between streamlines and classify these streamlines. The final experiment showed that after combining the two global features， this method can produce more robust query and clustering results.

streamline similarity; feature distribution; 2D histogram; streamline clustering

10.7631/issn.1000-2243.2016.05.0633

1000-2243(2016)05-0633-06

2014-09-24

谢伙生(1964-)， 副教授， 主要从事智能图形图像处理、 数据挖掘、 大规模数据可视化、 机器学习等方面研究， xiehs@sina.com

福建省自然科学基金资助项目(2014J01229)

TP391.41

A