本发明属于图形和可视化领域，涉及一种基于最优传输理论的边采样及边捆绑方法。
背景技术：
数据可视化主要是借助图形化手段，对数据加以解释，从而使用户能对数据进行深入的观察和分析。当今存在许多可视化方法，不同的数据类型可以使用不同的可视化方法，在可视化的众多对象中，节点连接图是一种基础的、重要的结构，它由顶点和边组成，适用于表示实体及实体之间的关系，实体用顶点表示，实体之间的关系用边表示。节点连接图的应用十分广泛，许多问题都可以通过建立节点连接图模型来解决，例如层次结构和网络结构等问题。然而随着数据规模日益增大，节点连接图的可视化方法变得混乱，出现了严重的视觉混淆，大量顶点的聚集与边的交叉降低了信息的辨识度，导致我们无法对边进行跟踪，也无法在整体上得出整个数据集表现出的信息。
为了解决大规模数据下的视觉混淆问题，提出了各种各样的方法，总体上可归结为两种思路。第一种是拓扑结构法，改变图形的布局或基于某种规则合并某些特定数据，优化空间的利用；第二种是边捆绑法，使用曲线来代替直线，将相似的边捆绑在一起，形成视觉上可被整体感知的边束。
技术实现要素：
有鉴于此，本发明的目的在于提供一种基于最优传输理论的边采样及边捆绑方法。
为达到上述目的，本发明提供如下技术方案：
一种基于最优传输理论的边采样及边捆绑方法，该方法具体包括以下步骤：
s1：输入节点连接图，利用层次聚类算法使用不同的距离函数基于方向和距离对边进行聚类；
s2：使用最优传输理论，从每一类边集中采样出一条公共边作为骨架；
s3：分别选取边的端点和重心点为控制点绘制两条三次贝塞尔曲线，并连接曲线的终点；
s4：为贝塞尔曲线部分设置低透明度，终点连线部分设置高透明度，短边直接绘制并设置极低的透明度；
s5：测量每个像素过度绘制的数量，使用opengl渲染技术进一步强调捆绑。
可选的，所述步骤s1中，输入节点连接图，利用层次聚类算法对边进行聚类，具体操作为：
选择类间最不相似的两条边之间的距离作为类之间的相似值，将边ei均匀采样为n个点，用向量表示为ei＝{x1,y1,...,xn,yn}，取n等于80，使用距离函数计算两个向量之间的距离作为边之间的距离。
可选的，所述步骤s1中，利用层次聚类算法使用皮尔逊距离基于边的方向进行第一次聚类，皮尔逊距离被定义为：
可选的，所述步骤s1中，利用层次聚类算法使用欧式距离基于边的距离进行第二次聚类，欧式距离被定义为：
可选的，所述步骤s2中，使用最优传输理论，从每一类边集中采样出一条公共边作为骨架，包括以下步骤：
s201：将初始边看成概率空间中的概率测度，使用平方2-wasserstein距离定义测度之间的距离：
s202：wasserstein重心定义为多个概率分布加权wasserstein距离的平均，如果每个测度权重相同，则重心ν被定义为：
采样边看做重心，将重心离散化为m个点
s203：最优传输包含一个等价的对偶问题：
其中，φ是kantarovich势能：φ＝(φ1,...,φm)，
s204：对于每一条初始边，fot关于φi和xi的偏导数分别为
其中，
s205：对于每一类所有边而言得到优化函数
f关于
可选的，所述步骤s205中，为求f的最大值，交替进行如下步骤得到重心，即采样边的最终分布：
固定重心点的位置，对于每条边，每个重心点在其相关的加权维诺图胞腔中包含相同的质量；
固定权重，使用类似劳埃德算法找到每个重心点关于每条边的胞腔的重心，用每条边的权重对胞腔中的点进行平均。
可选的，所述步骤s3中，分别选取边的端点和三个重心点为控制点绘制两条三次贝塞尔曲线，连接两条曲线的终点。
可选的，所述步骤s4中，使用rgba形式的颜色数据，为贝塞尔曲线部分设置较低的透明度，为终点连接的线段部分设置较高的透明度；第一次聚类出现的一类短边集合不进行第二次聚类，直接加入边捆绑后的结果图中，设置低于贝尔塞尔曲线的透明度。
可选的，所述步骤s5中，所有的边被绘制到模板缓冲区中来计算每个像素穿过的边，即过度绘制的数量，计算出所有像素穿过边的最大值和最小值，随后这个信息被线性映射到自定义的颜色梯度中。
本发明的有益效果在于：本发明使用最优传输理论中的wasserstein重心来作为采样边，使用采样边作为骨架来进行边捆绑，解决了点线图的视觉混淆、现有边捆绑算法绑定不充分以及无法在高层次体现图的骨架结构。本发明过程易于理解，既适用于有向图，也适用于无向图，在两种类型的布局上，都能获得较好的效果。
本发明的其他优点、目标和特征在某种程度上将在随后的说明书中进行阐述，并且在某种程度上，基于对下文的考察研究对本领域技术人员而言将是显而易见的，或者可以从本发明的实践中得到教导。本发明的目标和其他优点可以通过下面的说明书来实现和获得。
附图说明
为了使本发明的目的、技术方案和优点更加清楚，下面将结合附图对本发明作优选的详细描述，其中：
图1为本发明方法的流程图；
图2为本实施例输入一张节点连接图；
图3为本实施例边聚类的结果；图3(a)为基于方向聚类后的某一类在原图上的绘制；图3(b)是图3(a)基于距离聚类后的绘制；
图4为本实施例边采样的结果；
图5为本实施例边捆绑的结果；图5(a)为3(b)边捆绑的效果，图5(b)为初始边捆绑图；
图6为本实施例alpha混合的结果；图6(a)为5(b)设置透明度的效果，图6(b)为6(a)加上短边的效果；
图7为本实施例颜色渲染的结果；图7(a)为自定义颜色梯度，7(b)为结果图；
图8为本实施例增加捆绑紧密度的结果；
图9为本发明方法在有向图和无向图的使用。
具体实施方式
以下通过特定的具体实例说明本发明的实施方式，本领域技术人员可由本说明书所揭露的内容轻易地了解本发明的其他优点与功效。本发明还可以通过另外不同的具体实施方式加以实施或应用，本说明书中的各项细节也可以基于不同观点与应用，在没有背离本发明的精神下进行各种修饰或改变。需要说明的是，以下实施例中所提供的图示仅以示意方式说明本发明的基本构想，在不冲突的情况下，以下实施例及实施例中的特征可以相互组合。
其中，附图仅用于示例性说明，表示的仅是示意图，而非实物图，不能理解为对本发明的限制；为了更好地说明本发明的实施例，附图某些部件会有省略、放大或缩小，并不代表实际产品的尺寸；对本领域技术人员来说，附图中某些公知结构及其说明可能省略是可以理解的。
本发明实施例的附图中相同或相似的标号对应相同或相似的部件；在本发明的描述中，需要理解的是，若有术语“上”、“下”、“左”、“右”、“前”、“后”等指示的方位或位置关系为基于附图所示的方位或位置关系，仅是为了便于描述本发明和简化描述，而不是指示或暗示所指的装置或元件必须具有特定的方位、以特定的方位构造和操作，因此附图中描述位置关系的用语仅用于示例性说明，不能理解为对本发明的限制，对于本领域的普通技术人员而言，可以根据具体情况理解上述术语的具体含义。
本发明是一种基于最优传输理论的边采样及边捆绑方法，首先输入节点连接图，利用层次聚类算法使用不同的距离函数基于方向和距离对边进行聚类；然后使用最优传输理论，从每一类边集中采样出一条公共边作为骨架；接着分别选取边的端点和重心点为控制点绘制两条三次贝塞尔曲线，并连接曲线的终点；为贝塞尔曲线部分设置低透明度，终点连线部分设置高透明度，短边直接绘制并设置极低的透明度；最后测量每个像素过度绘制的数量，使用opengl渲染技术进一步强调捆绑。如图1所示，本发明所述边捆绑方法具体包括以下步骤：
步骤1，输入图2所示节点连接图，利用层次聚类算法对边进行聚类，具体操作为：
选择类间最不相似的两条边之间的距离作为类之间的相似值，将边ei均匀采样为n个点，用向量表示为ei＝{x1,y1,...,xn,yn}，取n等于80，使用距离函数计算两个向量之间的距离作为边之间的距离。
边端点的选择会造成聚类结果的不同，如果考虑为有向图，则直接使用原有的数据进行计算，如果考虑为无向图，为了消除端点选择的问题，对某条边而言，在使用距离函数时分别计算从起点到终点和从终点到起点的坐标取值顺序的距离值，取其中的较小值。将图2所示的节点连接图考虑为无向图。
步骤2，利用层次聚类算法使用皮尔逊距离基于边的方向进行第一次聚类，皮尔逊距离被定义为：
图3(a)是基于方向聚类后的某一类在原图上的绘制。
步骤3，利用层次聚类算法使用欧式距离基于边的距离进行第二次聚类，欧式距离被定义为：
图3(b)是图3(a)基于距离聚类后的绘制。
步骤4，使用最优传输理论，从每一类边集中采样出一条公共边作为骨架，包括以下几个步骤：
步骤401：将初始边看成概率空间中的概率测度，使用平方2-wasserstein距离定义测度之间的距离：
步骤402：wasserstein重心定义为多个概率分布加权wasserstein距离的平均，如果每个测度权重相同，则重心ν被定义为：
采样边看做重心，将重心离散化为m个点
步骤403：最优传输包含一个等价的对偶问题：
其中，φ是kantarovich势能：φ＝(φ1,...,φm)，
步骤404：对于每一条初始边，fot关于φi和xi的偏导数分别为
其中，
步骤405：对于每一类所有边而言得到优化函数
f关于
步骤5，为求f的最大值，交替进行如下步骤可得到重心(即采样边)的最终分布：
固定重心点的位置，对于每条边，每个重心点在其相关的加权维诺图胞腔中包含相同的质量。
固定权重，使用类似劳埃德算法找到每个重心点关于每条边的胞腔的重心，用每条边的权重对胞腔中的点进行平均。
参照图4，可以看出边采样的结果，每一类边对应一个重心点的分布。
步骤6，分别选取边的端点和三个重心点为控制点绘制两条三次贝塞尔曲线，连接两条曲线的终点。
图5(a)展示了3(b)边捆绑的效果，对步骤2中的每一类(除短边类)执行相同的步骤得到图5(b)所示的初始边捆绑图。
步骤7，使用rgba形式的颜色数据，为贝塞尔曲线部分设置较低的透明度，为终点连接的线段部分设置较高的透明度得到图6(a)。第一次聚类出现的一类短边集合不进行第二次聚类，直接加入边捆绑后的结果图中，设置低于贝尔塞尔曲线的透明度得到图6(b)，可视化结果表明该短边处理方法具有较好的视觉效果，低透明度的短边对捆绑的整体效果没有影响，却又能保证初始数据的完整性。
步骤8，所有的边被绘制到模板缓冲区中来计算每个像素穿过的边(称之为过度绘制)的数量，计算出所有像素穿过边的最大值和最小值(通常为1)，随后这个信息被线性映射到图7(a)所示自定义的颜色梯度中，得到7(b)所示的结果图，从颜色可以得知哪部分骨架聚集了更多边。
在本发明方法中，选择层次聚类是因为能根据不同的相似度值将数据分为不同数量的簇，将每一类边用不同颜色可视化出来，可根据实际情况对每一类进行适当的调整。减少聚类数量可以增大捆绑紧密度，增多聚类数量可以减小捆绑紧密度，本实施例中，在图7(b)的基础上，减少第二次聚类中每一类的数量得到图8所示的结果图，更多的边被捆绑在了一起。
参照图9，说明本发明方法在无向图和有向图上的使用，使用四个简单数据集进行说明，上一行表示原图，颜色表示边的方向，中间行将原图考虑为无向图，下一行将原图考虑为有向图。在两种类型的布局上，本发明方法都能获得较好的捆绑效果。
最后说明的是，以上实施例仅用以说明本发明的技术方案而非限制，尽管参照较佳实施例对本发明进行了详细说明，本领域的普通技术人员应当理解，可以对本发明的技术方案进行修改或者等同替换，而不脱离本技术方案的宗旨和范围，其均应涵盖在本发明的权利要求范围当中。
1.一种基于最优传输理论的边采样及边捆绑方法，其特征在于：该方法具体包括以下步骤：
s1：输入节点连接图，利用层次聚类算法使用不同的距离函数基于方向和距离对边进行聚类；
s2：使用最优传输理论，从每一类边集中采样出一条公共边作为骨架；
s3：分别选取边的端点和重心点为控制点绘制两条三次贝塞尔曲线，并连接曲线的终点；
s4：为贝塞尔曲线部分设置低透明度，终点连线部分设置高透明度，短边直接绘制并设置极低的透明度；
s5：测量每个像素过度绘制的数量，使用opengl渲染技术进一步强调捆绑。
2.根据权利要求书1所述的一种基于最优传输理论的边采样及边捆绑方法，其特征在于：所述步骤s1中，输入节点连接图，利用层次聚类算法对边进行聚类，具体操作为：
选择类间最不相似的两条边之间的距离作为类之间的相似值，将边ei均匀采样为n个点，用向量表示为ei＝{x1,y1,...,xn,yn}，取n等于80，使用距离函数计算两个向量之间的距离作为边之间的距离。
3.根据权利要求书2所述的一种基于最优传输理论的边采样及边捆绑方法，其特征在于：所述步骤s1中，利用层次聚类算法使用皮尔逊距离基于边的方向进行第一次聚类，皮尔逊距离被定义为：
4.根据权利要求书3所述的一种基于最优传输理论的边采样及边捆绑方法，其特征在于：所述步骤s1中，利用层次聚类算法使用欧式距离基于边的距离进行第二次聚类，欧式距离被定义为：
5.根据权利要求书4所述的一种基于最优传输理论的边采样及边捆绑方法，其特征在于：所述步骤s2中，使用最优传输理论，从每一类边集中采样出一条公共边作为骨架，包括以下步骤：
s201：将初始边看成概率空间中的概率测度，使用平方2-wasserstein距离定义测度之间的距离：
s202：wasserstein重心定义为多个概率分布加权wasserstein距离的平均，如果每个测度权重相同，则重心ν被定义为：
采样边看做重心，将重心离散化为m个点
s203：最优传输包含一个等价的对偶问题：
其中，φ是kantarovich势能：φ＝(φ1,...,φm)，
s204：对于每一条初始边，fot关于φi和xi的偏导数分别为
其中，
s205：对于每一类所有边而言得到优化函数
f关于
6.根据权利要求书5所述的一种基于最优传输理论的边采样及边捆绑方法，其特征在于：所述步骤s205中，为求f的最大值，交替进行如下步骤得到重心，即采样边的最终分布：
固定重心点的位置，对于每条边，每个重心点在其相关的加权维诺图胞腔中包含相同的质量；
固定权重，使用类似劳埃德算法找到每个重心点关于每条边的胞腔的重心，用每条边的权重对胞腔中的点进行平均。
7.根据权利要求书6所述的一种基于最优传输理论的边采样及边捆绑方法，其特征在于：所述步骤s3中，分别选取边的端点和三个重心点为控制点绘制两条三次贝塞尔曲线，连接两条曲线的终点。
8.根据权利要求书7所述的一种基于最优传输理论的边采样及边捆绑方法，其特征在于：所述步骤s4中，使用rgba形式的颜色数据，为贝塞尔曲线部分设置较低的透明度，为终点连接的线段部分设置较高的透明度；第一次聚类出现的一类短边集合不进行第二次聚类，直接加入边捆绑后的结果图中，设置低于贝尔塞尔曲线的透明度。
9.根据权利要求书8所述的一种基于最优传输理论的边采样及边捆绑方法，其特征在于：所述步骤s5中，所有的边被绘制到模板缓冲区中来计算每个像素穿过的边，即过度绘制的数量，计算出所有像素穿过边的最大值和最小值，随后这个信息被线性映射到自定义的颜色梯度中。
技术总结