CN103426176A - 基于改进直方图和聚类算法的视频镜头检测方法 - Google Patents

Abstract

本发明公开一种基于改进直方图和聚类算法的视频镜头检测方法，涉及图像处理技术。本发明采用改进直方图以及聚类算法计算相邻两帧图像直方图的交集，计算相邻两帧图像直方图的交集，并根据直方图相似度以判断是否发生镜头变化；如发生镜头变化，进一步对镜头边界利用帧间灰度/颜色差值对相邻两帧直方图的交集进行镜头边界的二次检测，采用非均匀分块加权处理，分别对每个分块计算像素差值，并将像素差值与预设的分块帧差阈值进行比较获得标记变量，对每个分块的标记变量加权求和，将加权求和的值与设定的分块加权阈值进行比较进行镜头检测。提高了镜头检测的准确率，解决了导致镜头误检、帧序号不连续等方面问题。

Description

基于改进直方图和聚类算法的视频镜头检测方法

技术领域

本发明涉及图像处理技术，具体是一种视频镜头检测技术。

背景技术

时域上连续的一组图像帧组成了视频流，但是由于视频帧速率一般较大，一段很短的视频就拥有大量的图像帧，而且相邻图像帧在视觉特征上具有一定的相关性，因此在视频检索领域并不能直接应用基于内容的图像检索的方法。只有对视频进行结构化并为视频建立索引和摘要，在形成关于视频内容的线性结构的情况下，才能有效实现视频数据的快速浏览和检索。视频的结构化包括镜头分割等，镜头分割又称镜头变换检测，是视频结构层次化的基础，要求避免外界因素对于镜头检测分割的影响，将视频序列分割为多个由拥有相同内容的一组不间断帧组成的镜头，正确检测出各种复杂编辑的镜头边界。

镜头分割要求准确地将视频从镜头边界处分割开，形成一个个独立镜头，以确保关键帧提取的准确性。Yeung等学者和Nagasaka等学者分别提出直方图交集算法和χ²直方图算法，对直方图差异度的计算方式进行改进；

为了减少镜头内的局部运动可能引发的干扰，Nagasaka等学者提出对各帧进行分块处理的方法；为了更好地检测持续的渐变过程，Zhang等学者提出了双阈值的算法；针对运动特征，Shahraray等学者提出了一种块匹配算法，对各块进行运动补偿后，提高了对于镜头内局部运动的容忍度，而Akutsu等学者通过计算运动向量的相关系数来定义帧间相似性，从而检测镜头转换；镜头转换时，镜头内对象边缘也随之发生变化，因此R.Zabhi等学者提出了基于边缘特征的场景分割方法；Chi-ChunLo等学者提出采用模糊C均值(FuzzyC-means:FCM)聚类算法进行镜头分割，最终将所有视频帧归入镜头变化（ShotChange:SC）和无镜头变化（NoShotChange:NSC）两类；金红等学者提出采用非监督式聚类算法对MPEG压缩视频进行检测，并根据视频数据的特征进行相应的后处理；Cernekova^[11]等学者提出在相邻两帧间，结合互信息量以及联合熵的镜头检测算法等。现阶段很多镜头检测方法对于镜头切变的检测效果已趋近完美，而镜头渐变由于其镜头转换模式的多样性，且易受到噪声干扰，现有方法的检测效果仍不理想。此外，一般采用不同方法分别进行镜头切变和镜头渐变的检测，而单纯识别镜头切变的实际意义不大，因此，能够同时识别镜头切变和渐变的方法一直是学者们的研究目标。

镜头分割是视频结构层次化的基础，得到了研究人员和学者的广泛重视，并有着丰富的研究成果。然而迄今为止，仍然没有一种在各种情况下、针对各种内容类型的视频都能表现出良好性能，“放之四海而皆准”的镜头分割检测算法。

镜头转换检测用于将电影或视频分为基本的时域单元——镜头，根据镜头边界的连接编辑方式，可将镜头转换方式分为以下两类：镜头突变（切变）和镜头渐变。镜头突变（切变）是从一个镜头突然转换至下一镜头的过程，对应的是直接连接两个镜头的镜头编辑方式；而镜头渐变是下一镜头逐渐代替当前镜头的过程，又称软转换，对应的是利用空间/着色效果连接两个镜头的镜头编辑方式。镜头渐变是包括多种镜头转换方式，其特点是整个切换过程是渐进持续的。比较常见的渐变主要有淡入淡出、划入划出、溶化、扫换和叠化等。

发生镜头转换之时，通常视频内容（高层语义）也发生了变化。视频镜头检测分割的理想过程是直接对视频内容（高层语义）进行分析，但是由于“语义鸿沟”以及涉及人类情感因素的高层语义的模糊性，多数镜头检测算法仍根据镜头边界处视频低层特征（如颜色、边缘、纹理等视觉特征及运动特征）的变化来检测镜头边界。通常情况下，镜头转换会引起视频底层特征的明显变化，如图像帧颜色分布的突然变化，视频对象边缘轮廓的移入移出等。但在镜头渐变的转换过程中，视频底层特征变化较为缓慢且不明显。

此外，即使是在同一镜头中，视频内容的快速变化和噪声也可能会导致视频底层特征发生较大变化。鉴于以上诸多影响因素，虽然在某些特定情况下，利用现有算法进行视频镜头分割可达到较好的效果，但是当视频中存在对象/摄像机的快速运动，外界光照的剧烈变化等极端情况以及在视频的渐变过程中，很多现有算法进行镜头分割的效果仍远不能令人满意。

现有技术中，视频镜头检测分割的常用方法是，计算视频中连续帧之间低层视觉特征或运动特征的帧间差异值Diff，并将其与预设或自适应的阈值T进行比较，若Diff＞T，则该处为镜头边界，反之，则认为这组连续帧属于同一镜头。由常用方法可知，帧间差异值的度量方式、阈值的设定，以及两者的最优组合将成为视频镜头检测分割的关键所在。而在同一镜头之内，视频特征发生变化主要有以下两个原因：对象/摄像机的运动和光线的变化。对象/摄像机的运动导致镜头内不断出现新对象，同时旧对象也在不断消失，若处理不当，则很容易和镜头渐变混淆，导致镜头误检(false detection)。镜头内也经常出现光线变化，若镜头内某帧突然变亮，则基于亮度特征度量的帧差值就会发生跳变，若处理不当，就会将其检测为镜头切变，也会导致镜头误检。因此，在设计算法时，需要充分考虑这两个因素。要正确检测出镜头边界以进行镜头分割，理想情况下的帧间内容差异度量应具备这样的特征：镜头内帧差值较小且相对平衡，而在镜头边界处会发生跳变很大。考虑到同一镜头内导致镜头内容变化的两个主要因素，帧差值应对镜头内的对象/摄影机运动以及光线变化尽量不敏感，而在镜头边界处敏锐地捕捉到视频内容的显著变化，跳变取得局部最大值。在视频镜头检测分割的研究领域中，经过数十年的研究和探讨，许多学者和研究人员都提出了各自的算法，根据镜头转换处的特点，基于不同的图像帧视觉特征和镜头运动特征进行镜头边界的检测分割，并取得了一定的效果。总的来说，视频镜头检测分割算法主要包括以下几类：基于像素的算法、基于直方图的算法、基于运动特征的算法、基于边缘特征的算法等。

直方图直观地反映了一幅图像灰度（灰度直方图）或颜色（颜色直方图）的总体分布，由于其出色的全局特性，广泛应用于图像处理中，并有多种度量方式：基本方法是计算相邻视频帧间的直方图差异值，但是直方图帧差值的结果因采用的直方图种类而异。还可通过引入加权系数计算两幅图像之间的直方图加权距离来对基本方法进行扩展，此外还有计算两幅图像之间的直方图交集或采用其他距离度量方法。

基于直方图的算法是应用最为广泛的视频镜头检测分割方法，处理简单方便，计算复杂度较低，对于大多数视频来说，只要阈值设置得当，一般均能达到比较好的效果。基于直方图的算法的主要优点就在于其全局特性。

基于直方图的算法与基于像素算法的基本思想一致，都是计算帧间差异值，不同的是所采用的度量标准不同，前者是在后者的基础上扩展得到的。基于像素的算法对相邻两帧相应像素的灰度或亮度差值的绝对值进行求和，以衡量帧间差异度。它是计算帧间差异值的最简单和基本的算法，算法过程如下：

对应像素的帧间灰度或亮度差值如式(1)所示：

fd＝|f_n(i,j)-f_n+1(i,j)|   (1)

其中，f_n(i,j)，f_n+1(i,j)分别表示第n帧和第n+1帧像素(i,j)的灰度或亮度值(因直方图类型而异)，则第n帧和第n+1帧间的总帧差为：

$\mathrm{Fd}=\frac{1}{\mathrm{MN}}\underset{i=1}{\overset{M}{\mathrm{\Σ}}}\underset{j=1}{\overset{N}{\mathrm{\Σ}}}\mathrm{fd}(i,j)---\left(2\right)$

然后，将总帧差与预设阈值比较，若超出阈值，则该处发生镜头转换。

虽然基于像素的方法算法简单明了且容易实现，但对于镜头内对象/摄像机的运动十分敏感，镜头内对象/摄影机的运动将会导致图像帧中很多像素的灰度或亮度发生变化，从而导致镜头边界的误检测。因此，有学者提出了基于直方图的镜头检测分割方法。

（1）直方图距离

直方图统计图像中各灰度级、亮度级或颜色等级上各像素点的分布规律。Tonomura和Abe^[14]提出将灰度直方图作为帧差度量标准，计算相邻两帧灰度直方图的差值度量图像帧间差异：

$\underset{v=0}{\overset{V}{\mathrm{\Σ}}}|H(I_t,v)-H(I_{t-1},v)|>T---\left(3\right)$

若相邻两帧帧差值符合式(3)则该处发生镜头转换。先后有学者提出基于直方图的改进方法，例如：对于颜色直方图，根据人眼的视觉特性和减少计算量的需要，计算量化的直方图差异；对于三维颜色空间(典型的如RGB、HSV等)，对三颜色通道分别计算帧间直方图差值并进行加权求和等，其中代表性的扩展有：Gargi和kasturi^[15]提出针对三维颜色空间的量化帧间直方图差异度量：

$\underset{k=1}{\overset{3}{\mathrm{\Σ}}}\underset{v=0}{\overset{V}{\mathrm{\Σ}}}|H(I_t,C_k,v)-H(I_{t-1},C_k,v)|>T---\left(4\right)$

其中C_k代表颜色空间如RGB或HSV等，若帧差值满足式(4)，则此处发生镜头变化。

（2）直方图加权

在三维颜色空间中，由于与其他颜色分量相比，某些颜色分量能够在较大程度上影响图像的颜色显示，或者人类视觉对其较为敏感(如HSV颜色空间中的Hue分量)，因此，需要根据具体情况进行具体分析，为对颜色显示影响程度大或较能满足人类视觉敏感性的颜色分量设置大权重，而对影响程度较小或难以直观感受的颜色分量设置较小的权重，加权求和得到加权帧间直方图差值，能够更好地反映出视频帧之间的内容距离或在人类视觉上的差异^[16]。若

$\underset{k=1}{\overset{3}{\mathrm{\Σ}}}\underset{v=0}{\overset{V}{\mathrm{\Σ}}}\frac{L(I_t,C_k)}{L_{\mathrm{mean}}\left(I_t\right)}|H(I_t,C_k,v)-H(I_{t-1},C_k,v)|>T---\left(5\right)$

则认为此处发生镜头转换。其中L(I_t,C_k)表示第t帧k颜色分量值，L_mean(I_t)表示第t帧中由各颜色分量得到的平均颜色值。Zhao^[17]等学者提出一种新的学习方法，通过最小最大优化过程学习获得更优的相似性度量，为各颜色分量设定不同的权重，从而得到加权直方图距离。若

$\underset{k=1}{\overset{3}{\mathrm{\Σ}}}\underset{v=0}{\overset{V}{\mathrm{\Σ}}}w(k,v)|H(I_t,C_k,v)-H(I_{t-1},C_k,v)|>T---\left(6\right)$

则认为发生镜头变化。其中，w(k,v)表示第t帧k颜色分量的加权系数。

（3）直方图交集

在镜头检测领域中，作为直方图相似度的另外一种度量方式，直方图交集^[2]也应用较多，计算方式也有多种。例如：根据最小函数法得到第t-1帧和第t帧的直方图交集，若

$(1-\frac{1}{\mathrm{xy}}\underset{v=0}{\overset{V}{\mathrm{\Σ}}}\min (H(I_t,v),H(I_{t-1},v)))>T---\left(7\right)$

则认为此处发生镜头变化，其中xy表示图像帧中的像素总数，这样计算出的直方图交集在[0,1]之间。

另一种计算直方图交集的方法^[18]如式(8)所示，若

$(1-\frac{1}{\mathrm{xy}}\underset{v=0}{\overset{V}{\mathrm{\Σ}}}\frac{\min (H(I_t,v),H(I_{t-1},v))}{\max (H(I_t,v),H(I_{t-1},v))})>T---\left(8\right)$

则认为此处发生镜头变化。

直方图交集方法统计了相邻两帧间具有相同灰度、亮度或颜色值的像素数目。其本质与直接计算直方图距离是相同的。

（4）χ²直方图

χ²直方图法^[3]作为对于传统直方图方法的一种有效的扩展，因其能放大帧间直方图差异，且算法较稳定，能够更好地反映出相邻两帧图像间的差别，而得到了广泛应用，χ²定义为：

并将χ²与预设阈值T进行比较，若大于T，则认为此处发生镜头变化。与Yakimovsy的似然率检测和Kolmogorov-Smimov检测相比，该方法性能更优^[19]。

（5）双阈值比较法

视频镜头的转换类型可分为切变与渐变两种，一般情况下，镜头渐变过程中的相邻帧间差异值幅度较镜头切变小，但是在镜头渐变的持续过程中，累积的帧间差异值幅度则较为明显。因此采用单一阈值进行判断显然无法适应镜头切变和渐变的多种情况。为此，Zhang等学者在计算直方图距离的基础上提出了双阈值比较法(twin comparison)^[5]。首先设定两个阈值T_h和T_l，分别用于检测镜头切变和镜头渐变。依次计算相邻两帧的帧间差异值，若某处帧间差异值超过T_h，则认为此处发生镜头切变；若帧间差异值小于T_h而大于T_l，则认为此处开始发生镜头渐变。继续计算其后各帧的帧差异值，若仍大于T_l，则进行累加，反之则认为未发生镜头转换，废除起始帧，并将累加的帧间差异值清零，从下一帧起重新开始判断。直到累计帧差值超过T_h，则认为此处镜头渐变结束；如果直至视频末帧或帧差异值小于T_l时，累计帧差值仍未达到T_h，则认为之前大于T_l的帧间差异值是由其他原因引起的。

现有技术采用的基于直方图的算法与基于像素算法存在下述问题：

（1）直方图反映的是图像灰度或颜色的总体分布，而无法体现图像的位置信息和视觉内容，内容毫无关联的两幅图像也可能拥有同样的灰度/颜色总体分布。此外，具有相同颜色总体分布的两幅图像可能拥有相同的对象和背景，但是对象的位置不同，典型的如法国和荷兰、爱尔兰和科特迪瓦的三色国旗等。

（2）直方图直观地反映了一幅图像灰度（灰度直方图）或颜色（颜色直方图）的总体分布，对于镜头内对象/摄像机的缓慢运动拥有较强的鲁棒性，但对于对象/摄像机的快速运动和镜头渐变情况的检测效果仍不理想，容易导致镜头误检或镜头漏检(missed detection)。

（3）基于直方图的不同度量方法根据视频帧间的灰度或颜色的总体变化情况进行镜头边界检测，并未考虑到镜头内视频对象/摄像机的运动对于检测的干扰。检测过程中，如果镜头内视频对象/摄像机运动导致镜头内部帧灰度或颜色的总体分布发生显著变化，就很可能将该内部帧识别为镜头边界，引起镜头误检测。可通过对视频帧进行分块来解决这一问题，将视频各帧等分为n×n个图像块，计算得到相邻帧对应块的帧间灰度或颜色直方图差值，排除差值最大的块，以一定的方式统计其余各块的帧间直方图差异。与传统的基于直方图的方法相比，此改进方法对于镜头内摄影机的运动有着较好的检测效果，但是对于某些镜头渐变的特殊效果，如淡入淡出等，检测效果仍不理想。此外剧烈光照变化的情况(如闪光等)，也会很大程度上干扰基于直方图的镜头检测效果。

（4）双阈值比较方法充分考虑到了镜头切变和镜头渐变的特征差异，并针对它们的特点分别进行检测，能够满足一般的镜头分割要求。并且规定在帧差异值不小于T_l的前提下，累加帧差异值达到T_h时，才认为发生镜头渐变，因此对于突发噪声有着一定的抗干扰能力。但是对于某些帧间变化不明显的渐变持续过程，很可能在其累积帧间差异值累加到T_h前，镜头渐变过程就已经结束了，很可能导致漏检。此外如果一个渐变持续过程中的某两个相邻帧之间差异很小(小于T_l)，将会直接导致累加过程结束，也很可能导致漏检。

聚类算法在信息科学领域得到了广泛应用，其基本思想是从初始化聚类开始，根据某种视频特征，利用某种相似度度量方式，将样本集X＝(X₁,X₂,...,X_n)中的每个元素分配给与其相似度最高的聚类，最终达到系统或用户要求。

B Gunsel，M R Naphade等学者先后提出用K-means聚类算法^[22]，根据相邻两帧的灰度/颜色直方图差值，将场景分为有明显变化和没有明显变化两类进行镜头检测分割。将单独出现的场景变化处判断为镜头切变，而将连续出现的场景变化处判断为镜头渐变。K-means聚类算法进行视频镜头检测分割的最大优点在于其不需要设定阈值，而且可同时利用多个视频特征，通过计算特征向量的欧氏距离以改善镜头检测效果。聚类算法的实质是根据均方误差和最小的准则，将帧间差异值分为两类，其检测结果相当于分别对每段视频设置合理的全局阈值。该算法能够对各段视频序列进行自适应，但对外界噪声的影响较为敏感，如果镜头渐变过程不是很明显，很容易将渐变过程分入无明显场景变化类。

考虑到实际场景的这两类之间是模糊的，因而Chi-Chun Lo^[9]等人提出用模糊C均值(Fuzzy C-means,FCM)聚类算法进行镜头检测分割，将所有帧间差异值分为三类：镜头转换（Shot Change,SC）、可能镜头转换（Suspected Shot Change,SSC）和无镜头转换（No Shot Change,NSC），并对镜头转换类中相邻两个元素SC(i)和SC(i+1)之间的n个可能镜头转换元素SSC(j)，SSC(j+1)…SSC(j+n-1)进行分析，通过式(14)判断可能镜头转换类中的各图像帧隶属于镜头转换类还是无镜头转换类：

H_SSC(k)≥param×[0.5×(H_SC(i)+H_SC(i+1))]   (14)

其中H_SC(i)和H_SC(i+1)分别表示SC类相邻元素SC(i)和SC(i+1)的帧间直方图差值，H_SSC(k)表示SC类相邻元素SC(i)和SC(i+1)之间SSC类元素SSC(k)中的帧间直方图差值。该算法无需设定阈值并且引入了可能镜头转换类以进行进一步分析，从而可将某些边缘帧差值更为合理地归类。

为了减少模糊聚类算法的计算复杂度，Xinbo Gao等学者还采用了粒度由粗到细的分步聚类方法。首先对视频中每相隔l(l≥2)帧的帧间进行粗聚类，得到镜头突变在时域上的大致位置，然后在可能发生镜头突变处进行逐帧细聚类，即可检测出镜头突变的精确位置。

Xinbo Gao等学者^[23]提出的模糊聚类算法还可用于镜头渐变的检测。该算法采用直方图帧差标准(Histogram difference metric,HDM)和空间帧差标准(Spatial difference metric,SDM)对相邻帧进行相似性度量，而且将所有视频帧定义为由HDM值和SDM值生成的特征空间F_D中的一个点集，

F_D＝{F_D(t)＝(D_S(t),D_H(t)),t＝1,2,...,T}   (15)

这样，就可将镜头检测问题转化为将特征空间划分为明显变化(SignificantChange,SC)和非明显变化(No Significant Change,NSC)两个子空间的问题。

采用上述算法对视频进行处理的过程中，首先分别计算出当前视频帧对于SC和NSC两类子特征空间的隶属度。若当前帧对于明显变化场景类的隶属度较高，则将该帧归入明显变化场景类，并用布尔变量1表示，否则用布尔变量0表示，直至将视频所有图像帧聚类完毕，从而将视频序列转化为一个二进制序列，例如1101001011110100101010……。视频序列中镜头突变和渐变各自具有一定的变化模式，因此，通过对转化后的视频二进制序列进行模式判断，即可分别检测出视频镜头突变和镜头渐变。根据Xinbo Gao等人的分析，二进制序列010表示镜头突变，而二进制序列011和110则表示镜头渐变。

此外，还可对各视频帧的特征值直接进行分类，由于镜头内各图像帧低层特征具有一定的相似性，可选取特征相似性最大的镜头作为帧所属的镜头。而镜头转换处由于镜头内容的变化导致各帧视觉特征或运动特征的变化，镜头转换处的当前帧就会被归入下一镜头。

非监督式聚类算法中，循环过程的应用最为广泛，其基本思想是，从某个初始聚类(一定方式选择或人为指定)出发，将样本集合中的元素分别以一定的相似性度量标准划分入某已知聚类直至满足系统或用户的预定需求。

由于没有专家先验知识的监督，非监督式聚类算法是一种自组织的迭代动态分析过程，在未满足聚类结束的条件下，根据一定的相似度计算方式不断收敛以最终满足用户或系统对于聚类数目或聚类密度的要求。在利用非监督式聚类算法对视频帧进行聚类时，可以采用之前所述的相似性度量标准，包括颜色直方图、边缘变化比例、运动矢量等。

非监督式的聚类算法通过阈值δ来控制聚类密度^[10]，以第一帧f₁作为初始聚类，计算其后各帧f_i,i∈[1,N]与之前所有已知的聚类中心(镜头类内中心)δ_k,k∈[1,M]之间的相似度S(f_i,C_k)，并保存最大值S_max及下标k，通过与相似度阈值δ进行比较以判断是否应归入之前某类，并以此进行动态的特征聚类比较，若被分进同一类的相邻帧即为同一镜头。设第k个聚类中原有N_k帧，

$\left\{\begin{array}{cc}{C}_k=\frac{f_i+\underset{j=1}{\overset{N_k}{\mathrm{\&Sigma;}}}{f^{|}}_j}{N_k+1},& S_{\max }\&GreaterEqual;\mathrm{\&delta;}\\ C_{k+1}=f_i,& S_{\max }<\mathrm{\&delta;}\end{array}\right.---(16)$

其中，C_k和C_k+1分别为第k和第k+1个聚类的中心。

K-means和ISODATA(Iterative Self-Organizing Data Analysis Technique,重复自组织数据分析技术)是两种常用的非监督式聚类的循环算法。K-means算法随机选择k个初始聚类中心，并为每个样本寻找特征距离最近的聚类中心进行动态聚类；ISODATA通过对样本数据进行自组织的重复动态分析，在相关参量的变动允许范围之内，最终得到的聚类数目是不定的。

非监督式的聚类算法在一定程度上减小了计算复杂度，且避免了阈值的设定，但是如果镜头内内容变化较大时，镜头内部帧可能会被分入不同的聚类(镜头)，从而导致镜头误检，而且其分类结果与初始质心(起始帧)密切相关。此外由于在实际应用非监督式聚类算法时，没有充分考虑到视频的时序特性，可能导致镜头出现帧序号不连续的问题。

发明内容

本发明针对现有算法进行视频检测，可能导致镜头误检、帧序号不连续等问题，针对镜头检测部分，提出了基于改进直方图和改进的聚类算法的图像检测方法。

本发明解决上述技术问题的技术方案是：一种基于改进直方图和帧差法的镜头检测方法，包括步骤：计算相邻两帧图像直方图的交集，并根据直方图相似度以判断是否发生镜头变化；如发生镜头变化，进一步对镜头边界利用帧间灰度/颜色差值对相邻两帧直方图的交集进行镜头边界的二次检测，采用非均匀分块加权处理，分别对每个分块计算像素差值，并将像素差值与预设的分块帧差阈值进行比较获得标记变量，对每个分块的标记变量加权求和，将加权求和的值与设定的分块加权阈值进行比较；将帧数小于20的镜头重新划归到上一个镜头中。

其中，根据公式： $S(t,t-1)=\frac{m_h\&times;S_h(t,t-1)+m_s\&times;S_s(t,t-1)m_v\&times;S_v(t,t-1)}{3}$ 计算相邻的第t和t-1帧的直方图相似度，其中，S_h(t,t-1)、S_s(t,t-1)和S_v(t,t-1)分别为H、S、V分量的直方图相似度，根据公式

确定相邻两帧H分量的相似度，其中，h_t(i),h_t-1(i)分别代表第t和t-1帧H分量的直方图，N表示图像灰度或颜色量化级别。可将H、S、V三个分量的加权系数m_h、m_s、m_v设定为0.9:0.3:0.1。

本发明还提出一种基于聚类检测算法的视频镜头检测方法，将视频序列第一帧f₁作为第一个镜头，以及首镜头的类内中心，并令该镜头布尔访问变量Shot.access≡1；提取视频序列的下一帧f₂，并分别计算视频序列与当前镜头类内中心在H、S、V三分量上的直方图相似度，根据公式： $S(f,\mathrm{Shot})=\frac{m_h\&times;S_H(f,\mathrm{Shot})+m_S\&times;S_S(f,\mathrm{Shot})m_V\&times;S_V(f,\mathrm{Shot})}{3}$ 加权计算总的直方图相似度；若S(f,shot)＞T，认为视频序列帧f属于镜头类内中心Shot，将f放入Shot内,并根据公式：

Shot.len=Shot.len+1重新计算镜头的类内中心；若S(f,shot)＜T，建立新镜头，将视频序列帧f放入新镜头中，作为该新镜头的类内中心，并在将前一镜头的布尔访问变量access置0的同时，令新镜头布尔访问变量Shot.access≡1，其中f_i表示镜头内部原有帧。

计算视频序列与当前镜头类内中心在H、S、V三分量上的直方图相似度具体为：将视频序列V＝{f₁,f₂,...,f_n}投影到HSV颜色空间上，对H,S和V分量进行非均匀量化，确定量化级数，根据直方图的H、S、V分量H(i),S(j),V(k)，调用公式：

$\left\{\begin{array}{c}{S}_H(f,\mathrm{Shot})=\underset{i=1}{\overset{8}{\mathrm{\&Sigma;}}}\frac{\min (H\left(i\right),\mathrm{Shot}\_H\left(i\right))}{\max (H\left(i\right),\mathrm{Shot}\_H\left(i\right))}\\ S_S(f,\mathrm{Shot})=\underset{j=1}{\overset{3}{\mathrm{\&Sigma;}}}\frac{\min (S\left(j\right),\mathrm{Shot}\_S\left(j\right))}{\max (S\left(j\right),\mathrm{Shot}\_S\left(j\right))}\\ S_V(f,\mathrm{Shot})=\underset{k=1}{\overset{3}{\mathrm{\&Sigma;}}}\frac{\min (V\left(k\right),\mathrm{Shot}\_V\left(k\right))}{\max (V\left(k\right),\mathrm{Shot}\_V\left(k\right))}\end{array}\right.$ 分别计算当前待检视频序列帧与当前镜头类内中心在三分量上的直方图相似度。

本发明提出的两种方法计算复杂度低，在没有显著增加计算和时间复杂度的同时，提高了镜头检测的准确率，解决了导致镜头误检、帧序号不连续等方面问题。

附图说明

图1本发明直方图法处理流程；

图2本发明帧差法处理流程；

图3本发明聚类算法流程。

具体实施方式

直方图有很多种应用方式，本发明采用了改进的方式——直方图交集。

由于直方图无法体现图像的位置信息和视觉内容，内容毫无关联的两幅图像也可能拥有同样的灰度/颜色总体分布，因此，本发明通过非均匀分块及加权预处理过程来改进直方图，以突出中心部分对于帧间差值的贡献，同时大大降低了镜头内小范围运动对于镜头检测的影响，与传统的全局直方图方法相比，所得结果更接近于人类的视觉认知。此外，对于视频内容而言，有效地抑制了视频顶部或底部的广告或字幕对于镜头检测的干扰。

具体为：

利用直方图方法检测出镜头。根据图像相邻两帧直方图的交集，确定镜头是否发生变化。

（1）获取相邻两帧直方图的交集，计算相邻两帧直方图相似度，相似度与阈值进行比较初步判断是否发生镜头变化，如相似度大于阈值初步判断镜头变化。根据实验一般设定直方图相似度阈值的取值范围为0.75-0.95，当阈值设为0.9时，综合效果最优。

相邻两帧H分量的相似度由如下公式确定：

$S_h(t,t-1)=\underset{i=1}{\overset{N}{\mathrm{\&Sigma;}}}\frac{\min (h_t\left(i\right),h_{t-1}\left(i\right))}{\max (h_t\left(i\right),h_{t-1}\left(i\right))}---(21)$

其中，h_t(i),h_t-1(i)分别代表第t和t-1帧H分量的直方图，N表示图像灰度或颜色量化级别。同理，S、V分量的直方图相似度分别为：

$S_s(t,t-1)=\underset{i=1}{\overset{N}{\mathrm{\&Sigma;}}}\frac{\min (S_t\left(i\right),S_{t-1}\left(i\right))}{\max (S_t\left(i\right),S_{t-1}\left(i\right))}$ 和 $S_v(t,t-1)=\underset{i=1}{\overset{N}{\mathrm{\&Sigma;}}}\frac{\min (v_t\left(i\right),v_{t-1}\left(i\right))}{\max (v_t\left(i\right),v_{t-1}\left(i\right))}.$

同样，s_t(i),s_t-1(i),和v_t(i),v_t-1(i)分别代表第t和t-1帧S和V分量的直方图。

HSV空间下，根据公式：

$S(t,t-1)=\frac{m_h\&times;S_h(t,t-1)+m_s\&times;S_s(t,t-1)m_v\&times;S_v(t,t-1)}{3}---\left(22\right)$

确定第t和t-1帧的直方图相似度。

设定直方图相似度阈值的取值范围一般为0.75-0.95，并由大量对比实验得知当阈值设为0.9时，该方法综合效果最优；HSV空间下，第t和t-1帧的直方图相似度为 $S(t,t-1)=\frac{m_h\&times;S_h(t,t-1)+m_s\&times;S_s(t,t-1)m_v\&times;S_v(t,t-1)}{3},$ 采集多帧图像作为实验对象，得到较好效果的直方图相似度阈值的取值范围一般为0.75-0.95，在这个范围内再对图像进行检测，最终得到最佳的直方图相似度阈值取0.9。

（2）如小于于阈值，进一步利用帧间灰度/颜色差值对相邻两帧直方图的交集进行镜头边界的二次检测，进行非均匀分块加权处理（如可分为9块，中心部分所占比例最大，权值和为1），分别对每个分块计算像素差值，并与预设的分块帧差阈值(取值范围为10-30)进行比较以进行标记，而后对每块的标记变量加权求和，并与设定的分块加权阈值(取值范围为0.0-0.4)进行比较以判断是否发生镜头变化。

分块帧差阈值获取方法可采用：相邻两帧之间的对应块的像素差值为：

其中，M×N为某块的大小，f_n(i,j),f_n+1(i,j)分别为n和n+1帧在点(i,j)的色度值。当分块帧差阈值取值范围为10-30时，综合效果最好。

非均匀分块加权的方法具体为，主要是为了克服直方图法不考虑位置信息和帧差法对镜头内对象/摄像机的运动十分敏感的缺点，从而提高镜头检测的检出率和准确率。通过大量实验发现，当分块加权阈值取值范围为0.0-0.4，实验效果最佳。

从视频中提取相邻两帧，在HSV空间中，计算其直方图交集，获得相邻两帧直方图相似度，并与设定阈值进行比较，当小于设定阈值时，初步判断镜头发生变化。为了更准确地判断镜头是否发生变化，再做进一步的判断。利用帧间灰度/颜色差值进行镜头边界的二次检测，从视频中提取相邻两帧，并进行非均匀分块，再计算对应块的像素差值。判断该块的像素差值是否大于分块帧差阈值，如果是，该块标记为1，否则标记为0。然后对标记变量进行加权求和。判断其是否大于分块加权阈值，如果是，则镜头发生变化，否则，镜头未发生变化。

由于在HSV颜色空间中，人眼对H分量最为敏感的视觉特性，根据H、S、V分量的加权比例，在得到H、S、V的量化值后，可得到H、S、V分量的系数比为Q_H:Q_S:Q_V，其中，Q_H,Q_S,Q_V分别为H、S、V分量的量化级别，在本发明中，系数比最优可设定为9:3:1。

S_h(t,t-1)、S_s(t,t-1)和S_v(t,t-1)分别为H、S、V分量的直方图相似度，图像在H、S、V分量的直方图相似度中灰度或颜色量化级别N的比值即为Q_H:Q_S:Q_V。N为了更多地体现H、S、V分量对直方图相似度的贡献，按照一定比例设置H分量、S分量、V分量的权值，如可将三个分量的加权系数m_h、m_s、m_v设定为0.9:0.3:0.1。

基于人类视觉感知的考虑，分别对H、S、V颜色分量进行非均匀量化，并据此在进行相似度匹配之时，为各颜色分量赋以不同的权值，这样计算出的两帧间的直方图差异度能够更好地反映出人类视觉感知的差异程度，具有一定的感知均匀性。

（3）考虑到强烈光照变化的情况，尤其是闪光，将帧数小于20的镜头重新划归到上一个镜头中。

为了进一步提高镜头检测的检出率和准确率，上述方法在利用改进直方图方法检测出镜头后，进一步利用帧差法对检测出的镜头进行过滤，从而构成了用于镜头检测的结合直方图法和帧差法的综合法，可有效减少可能由基于直方图的方法所带来的漏检及误检情况。此外，针对剧烈光照变化的情况，尤其是闪光，由于其持续帧数较少，且由于人类对于视觉媒体，如动漫、电影等存在的视觉暂留作用(其精确值为24fbps)，因此本发明将帧数小于20的镜头重新划归到上一个镜头中，使之适合于人类视觉特性。

对于测试视频，选择在HSV颜色空间下，采用改进的直方图交集方法对其进行处理，基于人类视觉感知的考虑，分别对H、S、V颜色分量进行非均匀量化，并据此在进行相似度匹配之时，为各颜色分量赋以不同的权值，这样计算出的两帧间的直方图差异度能够更好地反映出人类视觉感知的差异程度，具有一定的感知均匀性。处理完毕之后，进入改进像素帧差法的后处理过程，通过非均匀分块匹配并进行加权，这样可有效地抑制视频顶部或底部的广告或字幕对于镜头检测的干扰，并充分考虑到了图像帧各像素的位置信息，对于改进的直方图方法起到了很好的补充作用。

本发明可采用改进的聚类检测算法对视频镜头进行检测，根据相似度判断待检视频是否在当前镜头内。

如图3所示为改进聚类算法流程图。

传统的非监督式聚类算法在用于视频镜头检测时，由于未充分考虑到视频数据流的特点，仍将每个待检数据对象(图像帧)与所有已知的聚类中心(镜头类内中心)进行相似度比较，以将其分配给与其最相似的聚类(镜头)。这样很可能导致镜头误检及镜头内帧序号不连续的现象，并且时间及计算复杂度也较大。对此，考虑到视频流的时序特征，视频的每一帧仅与当前未完成聚类的镜头进行聚类比较，而已经分割完毕的镜头（只有先判断镜头是否发生变化，即是否是新的镜头，才能准确地将视频从镜头边界处分割开，形成一个个独立镜头，以确保关键帧提取的准确性，即镜头分割。）则不再参与后续的聚类。为此，引入了布尔访问变量access，当某镜头的access≡0时，表示该镜头已分割完毕，反之，则意味着该镜头为当前正在进行聚类比较的镜头。此外，因为在聚类算法中也采用了HSV空间的直方图，所以在计算待检帧与当前镜头相似度时，也需要考虑到HSV颜色空间中直方图加权的问题。将视频序列V＝{f₁,f₂,...,f_n}投影到HSV颜色空间上，对H,S和V分量进行非均匀量化，并分别计算得到直方图的H、S、V分量H(i),S(j),V(k)，这里，如可取，i∈[1,8];j∈[1,3];k∈[1,3]分别代表H、S、V分量的量化级数。

而后，利用直方图交集算法，分别计算出当前待检视频序列帧与当前镜头类内中心在三分量上的直方图相似度：

$\left\{\begin{array}{c}{S}_H(f,\mathrm{Shot})=\underset{i=1}{\overset{8}{\mathrm{\&Sigma;}}}\frac{\min (H\left(i\right),\mathrm{Shot}\_H\left(i\right))}{\max (H\left(i\right),\mathrm{Shot}\_H\left(i\right))}\\ S_S(f,\mathrm{Shot})=\underset{j=1}{\overset{3}{\mathrm{\&Sigma;}}}\frac{\min (S\left(j\right),\mathrm{Shot}\_S\left(j\right))}{\max (S\left(j\right),\mathrm{Shot}\_S\left(j\right))}\\ S_V(f,\mathrm{Shot})=\underset{k=1}{\overset{3}{\mathrm{\&Sigma;}}}\frac{\min (V\left(k\right),\mathrm{Shot}\_V\left(k\right))}{\max (V\left(k\right),\mathrm{Shot}\_V\left(k\right))}\end{array}\right.---\left(23\right)$

具体可采用以下方法：

（1）将视频序列第一帧f₁视作第一个镜头，f₁也为首镜头的类中心，并令该镜头布尔访问变量Shot.access≡1。

（2）提取视频序列的下一帧f₂，并在分别计算出当前视频序列与镜头类内中心的在H、S、V三分量上的直方图相似度后，根据公式(24)：

$S(f_i,\mathrm{Shot})=\frac{m_h\&times;S_H(f_i,\mathrm{Shot})+m_S\&times;S_S(f_i,\mathrm{Shot})m_V\&times;S_V(f_i,\mathrm{Shot})}{3}---\left(24\right)$

进行加权计算总的直方图相似度，

其中，m_h、m_s、m_v设定分别为H，S和V分量的加权系数。

一般而言，由于视觉对于H分量最为敏感，故m_h≥m_s，m_h≥m_V。与HSV颜色空间中的量化加权比保持一致，并为能体现S和V分量对于相似度的贡献，加权系数分别可被赋值为0.9、0.3、0.1，正在聚类的镜头须满足Shot.access≡1。

（3）若S(f,shot)＞T，此时认为视频序列帧f属于镜头Shot。将f放入Shot内,并重新计算Shot的类内中心为：

$\mathrm{Shot}=\frac{f+\underset{i=1}{\overset{\mathrm{Shot}.\mathrm{len}}{\mathrm{\&Sigma;}}}{f}_i}{\mathrm{Shot}.\mathrm{len}+1};$ Shot.len＝Shot.len+1      (25)

其中f_i表示镜头内部原有帧。

否则，若S(f,shot)＜T，则认为f不属于Shot。建立新镜头，将f放入新镜头中，也作为该镜头的类内中心，同时聚类个数加1，并在将前一镜头的access置0的同时，令新镜头Shot.access≡1。

其中，Shot为镜头类内中心，f为当前帧，f_i表示镜头内部原有帧，T为镜头相似度阈值，Shot.len为聚类个数。

（4）若视频仍未处理完毕，转向(2)，否则算法结束。

本发明在检测样本的选择上，考虑到视频选材的普遍性和广泛性，选择了5种类型的视频，包括动画(Beelzebub ED)、广告(innisfree cm)、新闻(Cctv_news)、节目预告(Anime 10th anniversary)及音乐视频(Taiyou noUta_clip)，并利用检出率(Recall)和准确率(Precision)来衡量视频镜头检测算法的检测效果。

检出率 $R=\frac{N_c}{(N_c+N_m)}\&times;100\%---\left(26\right)$

准确率 $P=\frac{N_c}{(N_c+N_f)}\&times;100\%---\left(27\right)$

其中，N_c,N_m,N_f分别为镜头的正确检出数、漏检数和误检数。

通过最小函数法计算两帧直方图的交集以衡量其相似度，并与设定阈值T进行比较，从而判断是否存在场景切换。相邻两帧直方图的相似度定义为：

$\mathrm{Sim}=\frac{1}{\mathrm{xy}}\underset{v=0}{\overset{V}{\mathrm{\&Sigma;}}}\frac{\min (H(I_t,v),H(I_{t-1},v))}{\max (H(I_t,v),H(I_{t-1},v))}---\left(28\right)$

考虑到传统的帧差法对于视频中物体/相机的运动十分敏感，从而容易导致误检测的缺点，本发明所述的帧差法结合了非均匀分块加权的思想，分别对每块逐点计算像素差值并与预设的分块帧差阈值进行比较以进行标记，而后对每块的标记变量进行加权求和，并与设定的分块加权阈值进行比较以判断是否存在镜头切变。相邻两帧之间的对应块的帧差定义为：

$\mathrm{Fd}=\frac{1}{\mathrm{MN}}\underset{i=1}{\overset{M}{\mathrm{\&Sigma;}}}\underset{j=1}{\overset{N}{\mathrm{\&Sigma;}}}|f_n(i,j)-f_{n+1}(i,j)|---\left(29\right)$

为了定量评估本发明的镜头分割算法与直方图法及帧差法的比较，分别对本发明提出的算法进行测试，其实验结果如表1所示。

表1视频镜头检测结果

由表1可以看出，由综合法得出的镜头检测准确率比两种传统方法要高，不过镜头的检出率却受制于分别由这两种方法得到的结果。以表中最后一段MV视频“Taiyou no Uta_clip”为例，由于其中存在大量的快速切变、渐变、镜头内主体运动以及一定的镜头内光照变化(假定渐变前后的帧与渐变过程中的帧属于不同的镜头)，故应用各方法进行检测都存在一定的漏检现象。

本发明提出的两种算法计算复杂度较低，在没有显著增加计算和时间复杂度的同时，提高了镜头检测的准确率。

Claims (6)

1.一种基于改进直方图和帧差法的镜头检测方法，其特征在于：计算相邻两帧图像直方图的交集，获得直方图相似度，根据直方图相似度初步判断镜头是否发生变化；利用帧间灰度/颜色差值进行镜头边界的二次检测，从视频中提取相邻两帧，并进行非均匀分块，再计算对应块的像素差值，并将像素差值与预设的分块帧差阈值进行比较获得标记变量，对每个分块的标记变量加权求和，将加权求和的值与设定的分块加权阈值进行比较，如果大于分块加权阈值，则镜头发生变化；将帧数小于20的镜头重新划归到上一个镜头中。

2.根据权利要求1所述的方法，其特征在于，所述获得直方图相似度具体包括，根据公式： $S(t,t-1)=\frac{m_h\&times;S_h(t,t-1)+m_s\&times;S_s(t,t-1)m_v\&times;S_v(t,t-1)}{3}$ 计算相邻的第t和t-1帧的直方图相似度，相邻两帧直方图相似度与阈值进行比较判断是否发生镜头变化，其中，S_h(t,t-1)、S_s(t,t-1)和S_v(t,t-1)分别为H、S、V分量的直方图相似度，根据公式

$S_h(t,t-1)=\underset{i=1}{\overset{N}{\mathrm{\&Sigma;}}}\frac{\min (h_t\left(i\right),h_{t-1}\left(i\right))}{\max (h_t\left(i\right),h_{t-1}\left(i\right))},$ $S_s(t,t-1)=\underset{i=1}{\overset{N}{\mathrm{\&Sigma;}}}\frac{\min (S_t\left(i\right),S_{t-1}\left(i\right))}{\max (S_t\left(i\right),S_{t-1}\left(i\right))},$ $S_v(t,t-1)=\underset{i=1}{\overset{N}{\mathrm{\&Sigma;}}}\frac{\min (v_t\left(i\right),v_{t-1}\left(i\right))}{\max (v_t\left(i\right),v_{t-1}\left(i\right))}$ 确定相邻两帧H、S、V分量的相似度，其中，h_t(i),h_t-1(i)分别代表第t和t-1帧H分量的直方图，N表示图像灰度或颜色量化级别。

3.根据权利要求1所述的方法，其特征在于，所述获得直方图相似度具体包括，计算视频序列与当前镜头类内中心在H、S、V三分量上的直方图相似度具体为：将视频序列V＝{f₁,f₂,...,f_n}投影到HSV颜色空间上，对H,S和V分量进行非均匀量化，确定量化级数，根据直方图的H、S、V分量H(i),S(j),V(k)，调用公式：

$\left\{\begin{array}{c}{S}_H(f,\mathrm{Shot})=\underset{i=1}{\overset{8}{\mathrm{\&Sigma;}}}\frac{\min (H\left(i\right),\mathrm{Shot}\_H\left(i\right))}{\max (H\left(i\right),\mathrm{Shot}\_H\left(i\right))}\\ S_S(f,\mathrm{Shot})=\underset{j=1}{\overset{3}{\mathrm{\&Sigma;}}}\frac{\min (S\left(j\right),\mathrm{Shot}\_S\left(j\right))}{\max (S\left(j\right),\mathrm{Shot}\_S\left(j\right))}\\ S_V(f,\mathrm{Shot})=\underset{k=1}{\overset{3}{\mathrm{\&Sigma;}}}\frac{\min (V\left(k\right),\mathrm{Shot}\_V\left(k\right))}{\max (V\left(k\right),\mathrm{Shot}\_V\left(k\right))}\end{array}\right.$ 分别计算频序列帧与当前镜头类内中心在三分量上的直方图相似度，其中，Shot为镜头类内中心。

4.根据权利要求2所述的方法，其特征在于，根据直方图相似度判断是否发生镜头变化进一步包括，直方图相似度与设定阈值比较，当小于设定阈值时，初步判断镜头发生变化。

5.根据权利要求3所述的方法，其特征在于，根据直方图相似度判断是否发生镜头变化进一步包括，将视频序列第一帧f₁作为第一个镜头，以及首镜头的类内中心，并令该镜头布尔访问变量Shot.access≡1根据公式：

$S(f_i,\mathrm{Shot})=\frac{m_h\&times;S_H(f_i,\mathrm{Shot})+m_S\&times;S_S(f_i,\mathrm{Shot})m_V\&times;S_V(f_i,\mathrm{Shot})}{3}$ 加权计算总的直方图相似度；若S(f_i,shot)＞T，认为视频序列帧f_i属于镜头类内中心Shot，将f_i放入Shot内,并根据公式：

Shot.len＝Shot.len+1重新计算镜头的类内中心；若S(f_i,shot)＜T，镜头发生变化，建立新镜头，将视频序列帧f_i放入新镜头中，作为该新镜头的类内中心，并在将前一镜头的布尔访问变量置0的同时，令新镜头布尔访问变量Shot.access≡1。

6.根据权利要求2，5其中之一所述的方法，其特征在于，将H、S、V三个分量的加权系数m_h、m_s、m_v设定为0.9:0.3:0.1。

Images