本发明涉及一种视频场景聚类及浏览方法，包括以下步骤：镜头边界检测与分割；镜头关键帧提取；镜头间相似度计算；镜头聚类；场景聚类；场景图表示。本发明使用场景聚类，从而得到视频场景层次的内容图结构，获得了基于场景的视频的高层语义信息；并使用二维图结构表述视频结构，为用户提供了一种有引导的非线性视频浏览方式，提高了浏览效率。
读取视频，检测视频中的切变和渐变镜头边界，根据所得镜头边界，将视频分割为多个独立的镜头；
对于独立的镜头，使用光流法检测视频内容变化，当视频帧内对象运动的距离达到一定阈值时，提取关键帧，得到代表镜头的关键帧集合，所述阈值为视频帧长宽的百分比Tflow；
对于镜头中提取的关键帧进行SIFT特征点提取，在所有镜头的关键帧集合之间进行关键帧的SIFT特征点匹配，根据匹配特征点数量定义镜头之间相似度，相似度定义如下：其中Sa,b是镜头a、b之间的相似度，Na、Nb分别表示镜头a、b的关键帧集合中关键帧图像的数量， 是镜头a中第k个关键帧图像， 是镜头b的第h个关键帧图像，是两幅图像之间SIFT特征点匹配的数量，若 小于特定阈值Tnum，则设置为0；
根据上一步获得的镜头之间的相似度，使用信息传递聚类算法对镜头进行聚类，得到若干聚类中心，根据每个镜头所属的聚类中心不同，将所有镜头分为若干个镜头集合，每个集合属于一个镜头类别；在信息传递聚类中镜头自身相似度定义为：Ns表示全部已有相似度的数量，即将镜头自身相似度Sa,a设置为全部非自身相似度的均值；
根据镜头聚类结果，将在一定窗口Twin即连续Twin个镜头内连续出现切换的镜头类别合并为一类，定义不同镜头类别之间的相似关系如下：S(i，k)＝-1/f(i，k)
S(i,k)是镜头类别i,k之间的相似度，f(i,k)是镜头类别i,k之间的切换次数，令镜头类别自身相似度值为S1，使用信息传递聚类算法对镜头类别进行聚类，得到初步的场景聚类结果；令镜头类别自身相似度值为S2，以初步的场景聚类结果为输入，重复本步骤上述操作，得到最终的场景聚类结果，其中S1和S2为用户设置的整数。
2.根据权利要求1所述的一种视频场景聚类方法，其特征在于，步骤一中的镜头边界检测方法为：定义一种衡量视频帧之间的；内容变化剧烈程度的相似度值，对于帧fi和帧fi+1，其相似度通过计算对应位置像素灰度值差的加权和得到，即：其中，W和H表示关键帧的宽与高，km,n表示赋予(m,n)位置的权值，用于标定视频帧中各个位置的重要性；G(fi)m,n表示帧fi中(m,n)位置的灰度值；考虑到人类的视觉关注点集中在视频的中间部分，而边缘处在一定程度上则被忽略，本方法以3:5:3的黄金分割比率非均匀地对视频帧划分区域，最上方三个区域以及最下方三个区域的权值设定为1/14，中间两侧的权值设为1/7，中央区域的权值设置为2/7；对于一段视频，计算相似度后得到一个相似度序列：Ω＝{d0，d1，d2，d3...dn-2}
对于切变镜头边界，根据滤波后的相似度序列，检测镜头切变：
hc(Ω′)表示平滑序列Ω′中的切变边界点组成的集合，T0、T1和T表示设定阈值，即当某处的变化量远大于前后两帧的变化量时，便将其标记为切变镜头边界；
对于镜头渐变边界，将相似度序列做差，其相似度的差值序列中超过某个阀值TdiffⅹDiffavg的点即为渐变镜头边界的待选位置，Diffavg定义为上一个镜头渐变边界到当前位置所有差值的均值，对于在帧窗口M内存在N个待选位置的视频片段，选取位于中间位置的待选帧作为镜头渐变边界；根据所得镜头边界，将视频分割为多个独立的镜头。
3.根据权利要求2所述的一种视频场景聚类方法，其特征在于，在镜头边界检测方法中，取σ＝27，T0＝2，T1＝2，T＝5，Tdiff＝4，M＝20，N＝8。
4.根据权利要求1所述的一种视频场景聚类方法，其特征在于，步骤二中的阈值Tflow＝0.3。
5.根据权利要求1所述的一种视频场景聚类方法，其特征在于，步骤三中的阈值Tnum＝
6.根据权利要求1所述的一种视频场景聚类方法，其特征在于，步骤五中所述Twin＝4，S1＝-4，S2＝-6。
7.一种视频场景聚类及浏览方法，根据权利要求1的场景聚类结果进行视频浏览，其特征在于，包括以下步骤：步骤一、镜头边界检测与分割；
读取视频，检测视频中的切变和渐变镜头边界，根据所得镜头边界，将视频分割为多个独立的镜头；
对于独立的镜头，使用光流法检测视频内容变化，当视频帧内对象运动的距离达到一定阈值时，提取关键帧，得到代表镜头的关键帧集合，所述阈值为视频帧长宽的百分比Tflow；
对于镜头中提取的关键帧进行SIFT特征点提取，在所有镜头的关键帧集合之间进行关键帧的SIFT特征点匹配，根据匹配特征点数量定义镜头之间相似度，相似度定义如下：其中Sa,b是镜头a、b之间的相似度，Na、Nb分别表示镜头a、b的关键帧集合中关键帧图像的数量， 是镜头a中第k个关键帧图像， 是镜头b的第h个关键帧图像，是两幅图像之间SIFT特征点匹配的数量，若 小于特定阈值Tnum，则设置为0；
根据上一步获得的镜头之间的相似度，使用信息传递聚类算法对镜头进行聚类，得到若干聚类中心，根据每个镜头所属的聚类中心不同，将所有镜头分为若干个镜头集合，每个集合属于一个镜头类别；在信息传递聚类中镜头自身相似度定义为：Ns表示全部已有相似度的数量，即将镜头自身相似度Sa,a设置为全部非自身相似度的均值；
根据镜头聚类结果，将在一定窗口Twin即连续Twin个镜头内连续出现切换的镜头类别合并为一类，定义不同镜头类别之间的相似关系如下：S(i，k)＝-1/f(i，k)
S(i,k)是镜头类别i,k之间的相似度，f(i,k)是镜头类别i,k之间的切换次数，令镜头类别自身相似度值为S1，使用信息传递聚类算法对镜头类别进行聚类，得到初步的场景聚类结果；令镜头类别自身相似度值为S2，以初步的场景聚类结果为输入，重复本步骤上述操作，得到最终的场景聚类结果，其中S1和S2为用户设置的整数；
根据场景聚类结果，以场景为节点，以切换关系为边，以切换次数为边权重，使用弹簧模型绘制无向有权的场景图，并将各个场景的时间信息和场景图信息存储在一个XML文件中，以便于用户接口访问；当用户进行视频浏览时，根据XML文件中存储的场景图信息和场景时间信息建立场景图，选择特定的场景进行非线性浏览。
8.根据权利要求7所述的一种视频场景聚类及浏览方法，其特征在于，步骤一中的镜头边界检测方法为：定义一种衡量视频帧之间的内容变化剧烈程度的相似度值，对于帧fi和帧fi+1，其相似度通过计算对应位置像素灰度值差的加权和得到，即：其中，W和H表示关键帧的宽与高，km,n表示赋予(m,n)位置的权值，用于标定视频帧中各个位置的重要性；G(fi)m,n表示帧fi中(m,n)位置的灰度值；考虑到人类的视觉关注点集中在视频的中间部分，而边缘处在一定程度上则被忽略，本方法以3:5:3的黄金分割比率非均匀地对视频帧划分区域，最上方三个区域以及最下方三个区域的权值设定为1/14，中间两侧的权值设为1/7，中央区域的权值设置为2/7；对于一段视频，计算相似度后得到一个相似度序列：Ω＝{d0，d1，d2，d3...dn-2}
对于切变镜头边界，根据滤波后的相似度序列，检测镜头切变：
hc(Ω′)表示平滑序列Ω′中的切变边界点组成的集合，T0、T1和T表示设定阈值，即当某处的变化量远大于前后两帧的变化量时，便将其标记为切变镜头边界；
对于镜头渐变边界，将相似度序列做差，其相似度的差值序列中超过某个阀值TdiffⅹDiffavg的点即为渐变镜头边界的待选位置，Tdiff为阀值的一个常值系数，Diffavg定义为上一个镜头渐变边界到当前位置所有差值的均值，对于在帧窗口M内存在N个待选位置的视频片段，选取位于中间位置的待选帧作为镜头渐变边界；根据所得镜头边界，将视频分割为多个独立的镜头。
9.根据权利要求8所述的一种视频场景聚类及浏览方法，其特征在于，在镜头边界检测方法中，取σ＝27，T0＝2，T1＝2，T＝5，Tdiff＝4，M＝20，N＝8。
10.根据权利要求7所述的一种视频场景聚类及浏览方法，其特征在于，步骤二中的阈值Tflow＝0.3；步骤三中的阈值Tnum＝10；步骤五中Twin＝4，S1＝-4，S2＝-6。
一种视频场景聚类及浏览方法
技术领域：
[0001] 本发明涉及一种视频场景聚类方式，具体涉及一种基于二维图结构的视频场景聚类和非线性浏览方法，属于视频处理领域。背景技术：
[0002] 为了清晰地表述视频内容，为用户提供高效的视频浏览，一般将视频分成层次化的四层：帧、镜头、场景和视频。一个视频帧是视频数据中保存的一幅图像；镜头是一台摄像机连续拍摄的若干连续帧的集合；一个或者多个表述相同语义的连续镜头构成一个场景。
[0003] 由于视频表述是一项基础性问题，这方面的工作已有许多，其中视频摘要的方式更适合视频内容的浏览。常见的视频摘要方法包括静态概要和动态略读两种。例如静态概要中层次化场景拼图(C.Barnes,D.B.Goldman,E.Shechtman,and A.Finkelstein.Video tapestries with continuous temporal zoom.ACM Transactions on Graphics,29(4):89:1–89:9,2010)等方法可以表述视频中不同层次的视频细节，但是无法提供视频浏览时的场景内容回顾；动态略读中基于视频、音频、文本流混合分析的方法（J.G.Kim,H.S.Chang,K.Kang,M.Kim,J.Kim,and H.M.Kim.Summarization of news video and its description for content-based access.International Journal of Imaging Systems and Technology,13(5):267–274,2003.）在浏览视频时可以很好地提供略读效果，但是其缺少场景类别鉴别的能力，只能表现相邻场景之间的切换关系，而无法表现非相邻场景之间的语义关系（即无法将相同语义信息的场景归为一类）。
[0004] 由于图的抽象灵活性和构建便捷性，图成为目前比较流行的数据呈现形式。基于图模型的镜头分类（S.Lu,I.K.King,and M.R.Lyu.Video summarization by video structure analysis and graph optimization.In Proc.ICME,pages1959–1962,2004.）使用图对视频进行镜头层级上的建模，以搜索最优的视频内容建立动态略读。但是其图结构的视频表述还是局限在镜头层级上的底层视频分析，无法表现场景之间的关系。发明内容：
[0005] 为了使用户清晰地了解视频场景语义结构和切换过程，高效地浏览视频内容，本发明提出了一种视频场景聚类及浏览方法，根据对镜头的聚类结果，得到视频场景类别和场景之间的切换关系。
[0006] 本发明的具体实现步骤如下：
[0007] 一种视频场景聚类及浏览方法，该方法包括以下步骤：
[0008] 步骤一、镜头边界检测与分割；
[0009] 读取视频，检测视频中的切变和渐变镜头边界，根据所得镜头边界，将视频分割为多个独立的镜头；
[0010] 步骤二、镜头关键帧提取
[0011] 对于独立的镜头，使用光流法检测视频内容变化，当视频帧内对象运动的距离达到一定阈值时，提取关键帧，得到代表镜头的关键帧集合；
[0012] 步骤三、镜头间相似度计算
[0013] 对于镜头中提取的关键帧进行SIFT特征点提取，在所有镜头的关键帧集合之间进行关键帧的SIFT特征点匹配，根据匹配特征点数量定义镜头之间相似度，相似度定义如下：
[0014]
[0015] 其中Sa,b是镜头a、b之间的相似度，Na、Nb分别表示镜头a、b的关键帧集合中关键帧图像的数量， 是镜头a中第k个关键帧图像， 是镜头b的第h个关键帧图像，是两幅图像之间SIFT特征点匹配的数量，若 小于特定阈值Tnum，则设置为0；
[0016] 步骤四、镜头聚类
[0017] 根据上一步获得的镜头之间的相似度，使用信息传递聚类算法对镜头进行聚类，得到若干聚类中心，根据每个镜头所属的聚类中心不同，将所有镜头分为若干个镜头集合，每个集合属于一个镜头类别；在信息传递聚类中镜头自身相似度定义为：
[0018]
[0019] Ns表示全部已有相似度的数量，即将镜头自身相似度Sa,a设置为全部非自身相似度的均值；
[0020] 步骤五、场景聚类
[0021] 根据镜头聚类结果，将在一定窗口Twin即连续Twin个镜头内连续出现切换的镜头类别合并为一类，定义不同镜头类别之间的相似关系如下：
[0022] S(i，k)＝-1/f(i，k)
[0023] S(i,k)是镜头类别i,k之间的相似度，f(i,k)是镜头类别i,k之间的切换次数，令镜头类别自身相似度值为S1，使用信息传递聚类算法对镜头类别进行聚类，得到初步的场景聚类结果；令镜头类别自身相似度值为S2，以初步的场景聚类结果为输入，重复本步骤上述操作，得到最终的场景聚类结果，其中S1和S2为用户设置的整数。
[0024] 通过以上步骤，提出了一种视频场景聚类方法，得到视频场景类别和场景之间的切换关系。基于以上聚类方法，本发明还提出了一种基于二维图结构的非线性视频浏览方法，使用节点表示场景，使用边表示场景之间的切换关系，将视频场景结构以二维图的形式表示出来，并提供基于二维图的浏览接口，使用户可以根据图表现出的视频场景结构，选择感兴趣的视频场景浏览。视频浏览方法除了包括场景聚类方法的五个步骤之外，还包括：
[0025] 步骤六、场景图表示
[0026] 根据场景聚类结果，以场景为节点，以切换关系为边，以切换次数为边权重，使用弹簧模型绘制无向有权的场景图，并将各个场景的时间信息和场景图信息存储在一个XML文件中，以便于用户接口访问；当用户进行视频浏览时，根据XML文件中存储的场景图信息和场景时间信息建立场景图，选择特定的场景进行非线性浏览。
[0027] 有益效果：
[0028] （1）传统方法中的视频聚类方法一般只能得到镜头层次的信息，而无法提供视频更高级语义信息，本方法使用场景聚类，从而得到视频场景层次的内容图结构，获得了基于场景的视频的高层语义信息。
[0029] （2）传统方法中静态概要只能提供图像形式的视频信息，对于用户感兴趣的视频片段无法进一步详细浏览，而本方法可以使用户在提供视频场景结构信息的前提下，详细浏览感兴趣的视频片段。
[0030] （3）传统方法中动态略读一般只能以线性结构来表述视频结构，对视频进行非线性浏览时只能无目的地拖动进度条实现，而本发明使用二维图结构表述视频结构，为用户提供了一种有引导的非线性视频浏览方式。
[0031] （4）本方法还可以为用户提供场景层次上的切换信息，使用户在开始浏览视频时，可以选择切换次数较多（即语义信息较重要）的视频场景开始浏览，除去了用户浏览非主要语义内容片段的时间，提高了浏览效率。附图说明：
[0032] 图1是本发明一种视频场景聚类及浏览方法的流程图；
[0033] 图2是计算视频帧间相似度时的帧图像分片示例；
[0034] 图3是非线性场景表示示意图；
具体实施方式
[0035] 下面结合附图对本发明方法的实施方式做详细说明。
[0036] 本实施方式具体实现了一种视频场景聚类及浏览方法，首先进行视频的镜头分割，然后根据对镜头的聚类结果，得到视频场景类别和场景之间的切换关系，进而使用节点表示场景，使用边表示切换关系，使用切换次数作为边权重，将视频场景结构以二维图的形式表示出来，并提供基于二维图的浏览接口，使用户可以根据二维图表现出的视频场景结构，选择感兴趣的视频场景进行浏览。
[0037] 本实施方式的具体实现步骤如下：
[0038] 步骤一、镜头边界检测与分割；
[0039] 读取视频，分别检测视频中的切变镜头边界和渐变镜头边界。
[0040] 本实施方式中采取的镜头边界检测方法为：
[0041] 定义一种衡量视频帧之间的内容变化剧烈程度的相似度值，对于帧fi和帧fi+1，其相似度通过计算对应位置像素灰度值差的加权和得到，即：
[0042]
[0043] 其中，W和H表示关键帧的宽与高，km,n表示赋予(m,n)位置的权值，用于标定视频帧中各个位置的重要性。G(fi)m,n表示帧fi中(m,n)位置的灰度值；考虑到人类的视觉关注点集中在视频的中间部分，而边缘处在一定程度上则被忽略，本方法以3:5:3的黄金分割比率非均匀地对视频帧划分区域，如图2所示，最上方三个区域以及最下方三个区域的权值设定为1/14，中间两侧的权值设为1/7，中央区域的权值设置为2/7；对于一段视频，计算相似度后得到一个相似度序列：
[0044] n＝＝{d0，d1，d2，d3...dn-2}
[0045] 对相似度序列进行高斯滤波得到：
[0046]
[0047] 对于切变镜头边界，根据滤波后的相似度序列，检测镜头切变：
[0048]
[0049] hc(Ω′)表示平滑序列Ω′中的切变边界点组成的集合，T0、T1和T表示设定阈值，即当某处的变化量远大于前后两帧的变化量时，便将其标记为切变镜头边界；
[0050] 对于镜头渐变边界，将相似度序列做差，其相似度的差值序列中超过某个阀值TdiffⅹDiffavg的点即为渐变镜头边界的待选位置，Diffavg定义为上一个镜头渐变边界到当前位置所有差值的均值，对于在帧窗口M内存在N个待选位置的视频片段，选取位于中间位置的待选帧作为镜头渐变边界；
[0051] 较佳地取σ=27，T0= 2，T1=2，T=5，Tdiff=4，M=20，N=8。
[0052] 根据所得镜头边界，将视频分割为多个独立的镜头。
[0053] 步骤二、镜头关键帧提取
[0054] 对于独立的镜头，使用光流法检测视频内容变化，当视频帧内对象运动的距离达到一定阈值（视频帧长宽的百分比Tflow）时，提取关键帧，得到代表镜头的关键帧集合。较佳地选取阈值Tflow=0.3。
[0055] 步骤三、镜头间相似度计算
[0056] 对于镜头中提取的关键帧进行SIFT特征点提取，在所有镜头的关键帧集合之间进行关键帧的SIFT特征点匹配，根据匹配特征点数量定义镜头之间相似度，相似度定义如下：
[0057]
[0058] 其中Sa,b是镜头a、b之间的相似度，Na、Nb分别表示镜头a、b的关键帧集合中图像的数量， 是镜头a中第k个关键帧图像， 是镜头b的第h个关键帧图像，是两幅图像之间SIFT特征点匹配的数量。若 小于特定阈值Tnum，则设置为0。较佳地选取Tnum=10。
[0059] 步骤四、镜头聚类
[0060] 根据上一步获得的镜头之间的相似度，使用信息传递聚类算法对镜头进行聚类，得到若干聚类中心，根据每个镜头所属的聚类中心不同，将所有镜头分为若干个镜头集合，每个集合属于一个镜头类别。信息传递聚类算法的核心是根据不同应用设置Sa,a和Sa,b，定义好这两个量后，就可以输入到信息传递聚类方法进行聚类。在使用信息传递聚类算法中，镜头自身相似度定义为：
[0061]
[0062] Ns表示全部相似度的数量，即将镜头自身相似度Sa,a设置为全部非自身相似度的均值。
[0063] 步骤五、场景聚类
[0064] 根据镜头聚类结果，将在一定窗口Twin（连续Twin个镜头）内连续出现切换的镜头类别合并为一类。定义不同镜头类别之间的相似关系如下：
[0065] S(i,k)＝-1/f(i，k)
[0066] S(i,k)是镜头类别i,k之间的相似度，f(i,k)是镜头类别i,k之间的切换次数。令镜头类别自身相似度值为S1，使用信息传递聚类算法对镜头类别进行聚类，得到初步的场景聚类结果。令镜头类别自身相似度值为S2，以初步的场景聚类结果为输入，重复本步骤上述操作，得到最终的场景聚类结果。较佳地选取Twin=4，S1=-4，S2=-6。
[0067] 步骤六、场景图表示
[0068] 根据场景聚类结果，以场景为节点，以切换关系为边，以切换次数为边权重，使用弹簧模型绘制无向有权的场景图，并将各个场景的时间信息和场景图信息存储在一个XML文件中，以便于用户接口访问。当用户进行视频浏览时，即可根据XML文件中存储的场景图信息和场景时间信息建立场景图，选择特定的场景进行非线性浏览。
