一种基于谱分割理论的镜头聚类方法

摘要

一种基于谱分割理论的镜头聚类方法，将谱图理论用于镜头聚类，对每个待分类的镜头提取其特征向量，根据提取出的特征向量，计算每两类间的相似度，然后将镜头集构造为一有权的无向图，根据每两镜头类之间的相似度，将使用谱分割每个镜头类二分为两个镜头类，再用贝叶斯信息准则判定此分割是否有效，有效分割的镜头子类迭代分割操作，无效分割的镜头类为终止节点，最后直到分割停止后对分类结果进行融合，得到最优镜头分类数和分类的结果。本发明解决了聚类算法中难以估计最优化的分类个数的难题，利用精确二分类的谱分割，提高了聚类结果的查全率和查准率；提出的全局融合操作，具有对分类错误的纠错功能，有效避免了局部最优解问题。

权利要求

1.一种基于谱分割理论的镜头聚类方法，其特征在于包括以下步骤：

(1)对每个待分类的镜头提取其特征向量；

(2)根据提取的特征向量，计算每两类间的相似度；

(3)将镜头集构造为一有权的无向图，根据每两镜头类之间的相似度，使用谱分割将每个镜头类二分为两个镜头类；

(4)用贝叶斯信息准则判定此分割是否有效；有效分割的镜头子类迭代分割操作，无效分割的镜头类为终止节点；

(5)对谱分割最终输出的结果，使用贝叶斯信息准则判断两分类是否连通，根据连通性进行融合，最终得到最优聚类数和聚类结果。

2.根据权利要求1所述的基于谱分割理论的镜头聚类方法，其特征在于：所述步骤(1)中的特征向量的提取采用HSV颜色直方图，并计算整个镜头所有帧的平均颜色直方图作为该镜头的特征向量。

3.根据权利要求1所述的基于谱分割理论的镜头聚类方法，其特征在于：所述步骤(2)中计算每两镜头类之间的相似度计算公式为：其中eij表示两类镜头i、j之间的相似度，Hi，Hj分别为镜头si，sj颜色直方图，σ为常数。

4.根据权利要求1所述的基于谱分割理论的镜头聚类方法，其特征在于：所述步骤(3)中的方法为：谱分割的结果{A，B}满足下式在全局范围内取得最小值：其中： 将镜头集S表示为一有权的无向图G＝

(V，E)，vi点代表镜头si，eij表示镜头i、j之间的相似度。

5.根据权利要求1所述的基于谱分割理论的镜头聚类方法，其特征在于：所述步骤(3)中的谱分割过程通过计算特征向量来获得的实现步骤如下：首先计算N×N对称矩阵E，各元素为eij，eij表示镜头i、j之间的相似度，根据E得到对角矩阵D(E)，dii＝∑jeij，构建矩-1/2 -1/2阵L(E)，L(E)＝(D(E)) E(D(E)) ，选择L(E)中最大特征向量，根据特征向量每维的符号位确定分割的结果。

6.根据权利要求1所述的基于谱分割理论的镜头聚类方法，其特征在于：所述步骤(4)的贝叶斯信息准则采用高斯球状模型，能够最优化拟合给定的样本数据集；BIC计算可选模型后验概率，并以此为作为衡量模型适合性的标准，比以计算两种模型分布之间的距离作为衡量标准的一般信息准则判断更加有效。

7.根据权利要求1所述的基于谱分割理论的镜头聚类方法，其特征在于：所述步骤(5)中使用贝叶斯信息准则对产生的分类进行融合，即对任意两类进行BIC模型判定其是否属于两类，如果属于一类更佳，则定义这两类是连通的，最后对所有连通的分类进行融合，得到最后的最佳聚类数和聚类的结果。

说明书

一种基于谱分割理论的镜头聚类方法

技术领域

[0001] 本发明属于视频内容分析与检索领域，具体涉及一种对镜头进行聚类的方法。

背景技术

[0002] 视频镜头是指语义上不间断的一段视频内容，是视频信息检索的基本结构和语义单元，对这些代表视频语义的单元进行聚类是视频语义分析的基础。当前的聚类算法可以大致分为有监督和无监督两种。有监督聚类通过给定的样本集对分类器进行训练，分类准确，但需要人工标注样本集。无监督聚类算法具有自学习功能，无需训练样本，但面临着最优化分类个数很难确定，分类结果对初始划分较敏感等难题。

[0003] 近年来，关于镜头聚类方法的研究有很多。目前在视频镜头聚类算法中常用的估计最优化分类个数的方法有以下几种：(1)基于探索模式的评判准则，该方法基于一种合适的信息准则评判标准，遍历所有可能出现的分类个数情况，得到最优化的分类个数；(2)基于融合的估计方法，首先选取一个远大于最优分类个数的分类数进行聚类，聚类的结果根据信息熵最小损失原则相互融合以得到最优的分类个数；(3)基于k-means的迭代聚类，对每个聚类的结果迭代执行k-means算法，采用合适的信息准则判断是否终止，当所有迭代终止时得到最优的分类个数。

[0004] 第一种方法是最简单的，得到的结果也是最客观的，但是这种方法计算复杂度较高，且在没有先验知识的情况下的搜索范围必须足够大。第二种方法分类过程每次融合后需重新计算融合的信息熵损失，收敛速度慢，计算复杂度高，并且无法对初始分类纠错。第三种方法以X-means为代表，具有收敛速度快，计算复杂度小等优点，但k-means算法只考虑了类间关系，可能会出现将一个类割裂的错误，并且没有针对这种错误的纠错功能。

发明内容

[0005] 本发明要解决的技术问题：克服现有技术的不足，提供一种基于谱分割理论的镜头聚类方法，该方法可以在低复杂度情况下聚类算法中难以估计最优化的分类个数，利用精确二分类的谱分割，提高了聚类结果的查全率和查准率；提出的全局融合操作，具有对分类错误的纠错功能，避免了局部最优解问题。

[0006] 本发明的目的是这样实现的：一种基于谱分割理论的镜头聚类方法，包括以下步骤：

[0007] (1)对每个待分类的镜头提取其特征向量；

[0008] (2)根据提取的特征向量，计算每两类间的相似度；

[0009] (3)将镜头集构造为一有权的无向图，根据每两镜头类之间的相似度，使用谱分割将每个镜头类二分为两个镜头类；

[0010] (4)用贝叶斯信息准则判定此分割是否有效；有效分割的镜头子类迭代分割操作，无效分割的镜头类为终止节点；

[0011] (5)对谱分割最终输出的结果，使用贝叶斯信息准则判断两分类是否连通，根据连通性进行融合，最终得到最优聚类数和聚类结果。

[0012] 所述步骤(1)中的特征向量的提取采用HSV颜色直方图，并计算整个镜头所有帧的平均颜色直方图作为该镜头的特征向量。

[0013] 所述步骤(2)中计算每两镜头类之间的相似度计算公式为：

[0014]

[0015] 其中eij表示两类镜头i、j之间的相似度，Hi，Hj分别为镜头si，sj颜色直方图，σ为常数。

[0016] 所述步骤(3)中的方法为：谱分割的结果{A，B}满足下式在全局范围内取得最小值：

[0017]

[0018] 其中： 将镜头集S表示为一有权的无向图G＝(V，E)，vi点代表镜头si，eij表示镜头i、j之间的相似度。

[0019] 所述步骤(3)中的谱分割过程通过计算特征向量来获得的实现步骤如下：首先计算N×N对称矩阵E，各元素为eij，eij表示镜头i、j之间的相似度，根据E得到对角矩阵-1/2 -1/2D(E)，dii＝∑jeij，构建矩阵L(E)，L(E)＝(D(E)) E(D(E)) ，选择L(E)中最大特征向量，根据特征向量每维的符号位确定分割的结果。

[0020] 所述步骤(4)的贝叶斯信息准则采用高斯球状模型，能够最优化拟合给定的样本数据集；BIC计算可选模型后验概率，并以此为作为衡量模型适合性的标准，比以计算两种模型分布之间的距离作为衡量标准的一般信息准则判断更加有效。

[0021] 所述步骤(5)中使用贝叶斯信息准则对产生的分类进行融合，即对任意两类进行BIC模型判定其是否属于两类，如果属于一类更佳，则定义这两类是连通的，最后对所有连通的分类进行融合，得到最后的最佳聚类数和聚类的结果。

[0022] 本发明现有技术相比的优点在于：

[0023] (1)现有的聚类方法多采用的类别距离作为分类的标准，效果依赖于提供的经验参数，很难提供一种通用、普遍的解决方法，但镜头聚类是一种不确定类别个数的聚类，在聚类前很难准确的估计出类别个数及各类别中心。本发明将谱图理论及贝叶斯信息准则用于镜头聚类，对每个待分类的镜头提取其特征向量，根据提取出的特征向量，计算每两类间的相似度，然后将镜头集构造为一有权的无向图，根据每两镜头类之间的相似度，将使用谱分割每个镜头类二分为两个镜头类，再用贝叶斯信息准则判定此分割是否有效，有效分割的镜头子类迭代分割操作，无效分割的镜头类为终止节点。本发明利用精确二分类的谱分割，同时采用基于后验概率的贝叶斯信息准则作为分类停止的准则更加准确，提高了聚类结果的查全率和查准率。

[0024] (2)本发明与传统的镜头聚类方法相比，本发明在分割操作结束时，对谱分割最终输出的结果，使用贝叶斯信息准则判断两分类是否连通，根据连通性进行融合，最终得到最优聚类数和聚类结果，解决了在低复杂度情况下聚类算法中难以估计最优化的分类个数的难题；提出的全局融合操作，具有对分类错误的纠错功能，避免了局部最优解问题。

附图说明

[0025] 图1为本发明基于谱分割理论聚类的流程示意图。

具体实施方式

[0026] 如图1所示，本发明具体包括以下步骤：

[0027] 1.镜头类特征向量提取

[0028] 提取全部镜头的特征向量，计算特征向量的平均值作为镜头类的特征向量。本发明中采用HSV颜色直方图来描述图像的特征，即计算其全部帧的平均颜色直方图作为该镜头的颜色特征。

[0029] 颜色特征是最能体现图像视觉特征的一种底层物理特征，颜色特征与图像中所包含的物体或场景具有较高的相关性，并且同其他视觉特征相比，颜色特征对图像本身的尺寸、方向、视角的依赖性较小，具有较高的鲁棒性。颜色直方图是在图像检索系统中被广泛采用的颜色特征，它描述了不同色彩在整幅图像中的概率分布。虽然无法描述图像中的对象和物体的空间位置，但仍为一种高效的描述方法。

[0030] HSV(Hue Saturation Value)颜色空间最符合人们对颜色相似性的主观判断，本文采用HSV颜色直方图来描述图像的特征。对于每个镜头，计算其全部帧的平均颜色直方图作为该镜头的颜色特征。

[0031] 在本发明中，采用12(H)×4(S)×4(V)共192级HSV颜色直方图。定义Hi，Hj分别为镜头si，sj颜色直方图，则我们定义图G中的边eij如下：

[0032]

[0033] 其中σ为镜头si，sj之间时间间隔t的函数，由于本实验中测试的视频其镜头间的关系与时间没有关系，σ取常数0.15。

[0034] 2.使用谱分割二分镜头类

[0035] 将镜头集S表示为一有权的无向图G＝(V，E)，νj点代表镜头si，eij表示镜头i、j之间的相似度。谱分割的结果{A，B}满足下式：

[0036]

[0037] 在全局范围内取得最小值。

[0038] 其中：

[0039] 谱分割算法简单描述如下：首先计算N×N对称矩阵E，各元素为eij，根据E得到对角矩阵D(E)，dii＝∑jeij，构建矩阵L(E)，L(E)＝(D(E))-1/2E(D(E))-1/2。选择L(E)中最大特征向量，根据特征向量每维的符号位确定分割的结果。

[0040] 谱分割算法定义的分类标准综合类间、类内距离进行评价，使得分割的结果更加准确。算法将求最小值问题转换为求矩阵最大特征向量，并可采取相应近似计算的方法，减少了复杂度。

[0041] 3.计算BIC(k＝1)的值：

[0042] 设待聚类的视频镜头为集合S，用于临时存放镜头类的队列，记作Q，用于记录最后分类结果的队列，记作RQ。应用谱分割将集合S划分为两个镜头类S1，S2(假设最佳分类数k≥2)。

[0043] 将S1，S2插入队列Q尾部，取队列Q首镜头类Si，假设镜头类中的样本围绕类中心呈高斯球状分布(Spherical Gaussians)。则对于在镜头类Si中的样本集X＝{xi：i＝1，...，R}的M维的高斯分布如下：

[0044]

[0045] 计算BIC(k＝1)的值：

[0046]

[0047] 其中 分别是样本数据集X在M维高斯分布中均值和方差的极大似然估计。M代表该模型中参数的个数。L是样本数据集X的极大似然函数，L(·)＝∏f(·)。R为镜头类Si中的样本个数。

[0048] 4.计算BIC(k＝2)的值：(1) (2) (1) (2)

[0049] 再次应用谱分割将其划分为两类，记作：Si ，Si 。则相应X(xi ，xi )的高斯分布如下：(1) (1) (1) (2) (2) (2)

[0050] xi ～(μi ，Vi )，xi ～(μi ，Vi )

[0051] 计算BIC(k＝2)的值：

[0052]

[0053] 此时模型的参数个数为2M。

[0054] 5.判断分类是否有效：

[0055] 如果BIC(k＝2)＞BIC(k＝1)，则认为该类被分为两类更佳，分类有效，将Si(1)，(2)Si 插入队列Q。如果BIC(k＝2)≤BIC(k＝1)，即认为该类不需要再分，分类无效，将Si插入队列RQ。

[0056] 6.聚类结果融合调整

[0057] 继续步骤5。设在队列RQ中的镜头类为S′＝(S′1，S′2，...，S′k)，对于任意的i，j(i，j＝1，...，k，i≠j)，计算S′i∪S′j的BIC(k＝2)和BIC(k＝1)，如果BIC(k＝2)＞BIC(k＝1)，则定义S′i，S′j为连通，否则为不连通。将所有连通集融合，输出最优分类数和分类结果。