黄永锋，熊泽东，王绍宇

（东华大学 计算机科学与技术学院，上海 201620）

基于DCE算法的压缩域视频镜头分割方法

黄永锋，熊泽东，王绍宇

（东华大学 计算机科学与技术学院，上海 201620）

镜头分割是视频检索的结构化基础，为此提出一种高效的视频镜头分割方法.首先，在压缩域中提取视频流中I帧携带的特征信息，并生成帧间特征分布曲线；然后，利用离散曲线演化（DCE）算法对预处理过的曲线进行分析与演进；最后，分割出视频镜头并提取关键帧.试验结果表明：该方法充分考虑了视频编码的时序特点，具有较好的分割效果，鲁棒性强.

压缩域；镜头分割；关键帧；DCE算法

随着多媒体技术的飞速发展，视频数据量呈现爆炸式增长，而视频信息又具有海量性和无序性的特点.如何对这种非结构化数据进行有效的组织、管理、索引与查询是一个关键问题，视频检索技术为解决这一问题提供了可行途径，并已成为近年来的研究热点，而镜头分割更是研究的焦点.在视频索引与检索系统中，把具有相同语义的镜头自动分类并有效组织，为用户检索提供合理的反馈信息［1］.

镜头是视频的基本结构单元和内容表示单元，根据视频的变换方式镜头可以分为切变（cut）和渐变（gradual transition）两种.压缩域的视频镜头分割根据其使用的信息不同主要分为两类：一类比较帧的 DCT（discrete cosine transform）系数［2－4］；另一类则比较帧宏块的运动补偿信息［5－7］.前者主要使用视频流中I帧的信息，根据国际视频编码标准MPEG（moving pictures experts group）规定大约每13帧中有一I帧，因此，该类方法资源消耗少，时间效率高；而相比之下，后者需比较所有帧的宏块信息，时间效率低，计算量大.本文考虑到处理效率问题，选用前者进行数据处理.

镜头的检测方法也大致分为两类：一是基于阈值的方法［8－9］，这种方法比较简单，程序上容易实现；二是基于机器学习的方法［10－11］，在这种方法中，一般是通过训练得到视频变换的特有统计模型去实现视频变换检测，该方法能有效检测出渐变，但是复杂度较大.与上述两类方法不同，本文不直接对视频数据进行处理，而是应用文献［12］提出的DCE（discrete curve evolution）算法，通过轮廓消解的方法对视频特征分布曲线进行处理来实现视频镜头分割与关键帧提取.

1 压缩域视频特征描述

在视频压缩编码中，MPEG标准以GOP（group of pictures）为编码单元，其结构如图1所示.GOP主要由3种帧组成，分别为I帧、B帧和P帧，其中B帧和P帧采用运动补偿机制的帧间编码方式，而I帧采用帧内编码.因此，可以直接在视频流中通过熵解码、反量化的方法获得I帧的DCT系数，方便快捷地提取所携带的视频信息，而其他两种帧则不能直接提取DCT系数.

图1 GOP结构图Fig.1 The GOP structure

对于MPEG压缩域的视频特征提取，最自然的解决方法是利用与基色调相关的DC（direct current）系数和与纹理相关的 AC（alternating current）系数，即用MEPG数据流中的离散余弦变换的直流分量来提取视频帧的基色调，用交流分量来提取帧的纹理信息.定义式（1）和（2）分别用来量化I帧的特征信息及其差值.

其中：Cn和Sim （Cn，Cn＋1）分别为第n帧的特征量及其差值；DCn（i，j）和ACn（i，j）分别为第n帧的第（i，j）个子块的基色调和纹理信息；α和β分别为基色调和纹理信息对帧特征的影响因子，且满足α＋β＝1（α＞β，α，β∈［0，1］），本文中α和β分别取值为0.75和0.25.由于一个子块有63个AC系数，考虑到计算量及纹理信息分布特点，此处只选取Zigzag扫描顺序的前9个最大值.

2 镜头分割方法

通过上述提取的视频特征差值并不能直接应用于下文的镜头分割，因为同一镜头内帧的特征量具有很大的相似性，数据波动性很小，这些数据对镜头分割意义不大，可以看成是噪声，需要对其进行预处理来简化后续操作.然后，对预处理后的数据曲线应用DCE算法实现镜头分割及关键帧提取.

2.1 数据预处理

首先通过高斯滤波除去数据中的噪声，然后求取曲线局部的谷值与峰值，并通过连接谷值与峰值点的方法重绘曲线.为了求取曲线局部的谷值与峰值，采用类似数学理论中求解曲线局部极值的方法，计算相邻两点的微增量dxi，若dxi×dxi＋1＜0，则说明第i帧处存在谷点或峰点.

2.2 DCE算法

DCE算法［12］是以类比发散方程为导向，除去那些对曲线整体特征没有影响或者影响较小的曲线段，并保留曲线整体特征的曲线演进算法.首先，把曲线分成m 段，即Dm＝s0，s1，…，sm－1；然后，计算相邻两段曲线的权值K（si，si＋1）来确定该段曲线对曲线整体轮廓的影响大小；最后，根据关键点数N来控制程序的循环次数，程序每循环一次都会合并掉K（si，si＋1）最小的曲线段.DCE算法流程如图2所示.

图2 DCE算法流程图Fig.2 Flowchart of the DCE algorithm

为了同时考虑特征差值和帧间距对曲线的总体波动性的影响，确定权值K（si，si＋1）的计算式如式（3）所示.

其中：Smax为相邻两曲线段中最大特征差值；Lmax为曲线段的起始点与结束点间的帧间距.

2.3 镜头分割及关键帧提取方法描述

对一段MPEG视频流的输入，镜头和关键帧的输出按下述步骤进行：

Step 1 在视频流中提取I帧的DCT系数，并依据式（1）和（2）分别计算由基色调和纹理信息表征的帧特征量和特征差值；

Step 2 对Step 1提取的视频帧特征差值进行高斯滤波去除数据中的噪声，然后对滤波处理后的数据曲线求谷值与峰值点；

Step 3 根据谷值与峰值点生成新的数据曲线图，并对其应用DCE算法进行处理，然后得到满足关键点数的曲线图；

Step 4 依据Step 3生成的目的曲线图实现镜头分割和关键帧提取，曲线图中的峰值点说明镜头内容发生了极大变化，而谷值点说明帧间内容变化较小，相对稳定，相似性极强，可作为代表镜头内容的关键帧.

以New Indians（Segment 004）视频段为例，该视频段共有2 572帧.首先，在压缩域提取视频中I帧的特征值及特征差值，其分布如图3和4所示，图4中存在大量噪声；然后，预处理特征数据，生成图5，噪声被滤除，谷值、峰值点明显；最后，对预处理数据应用DCE算法，得到目的特征数据分布如图6所示，关键点数N设为40.图6中峰值点对应镜头变化处，谷值点为关键帧；椭圆标记点的峰值相对较小，但帧间距较大，说明发生镜头渐变.

3 试验结果与分析

试验选用北卡罗莱纳大学信息与图书馆学院的开放式数字视频库 （http：//www.open－video.org）作为视频测试集，并通过 Matlab R2008（b）编程实现.试验环境为Windows XP SP3，硬件配置为Pentium（R）Dual－Core CPU，主频2.10GHz，2GB内存.为了评价本算法性能，采用查全率（Recall）和查准率（Precision）作为评价指标［13］，定义如式（4）和（5）所示.

其中：Nc，Nm和Nf分别表示正确检测镜头数、漏检镜头数和误检镜头数.

采用式（6）自适应地确定曲线的关键点数N.

其中：θ为加权因子，取值范围一般为［1.0，1.5］；Si的取值如式（7）所示.

对所选用视频库中的视频数据进行试验，并将本文算法与文献［4］中的镜头检测算法进行了比较，结果如表1所示.

表1 镜头分割结果数据统计表Table 1 The results of shot segmentation

由表1可知，本文结合DCE算法对压缩域视频镜头进行检测与分割，取得了令人满意的效果，查全率和查准率较文献［4］都有很大的提高，其中，切变镜头的查全率和查准率的平均值都达到了90%以上，渐变镜头的查全率和查准率的平均值也在80%以上.本文算法对视频库中的视频有普遍适用性，鲁棒性较强.

4 结 语

本文算法在压缩域对视频流中I帧所携带的特征信息进行量化、比较与分析，并结合DCE算法的应用来实现镜头直观快速的分割，且可以方便地提取视频镜头关键帧.该算法充分地考虑了视频编码的时序特点，能够准确有效地检测镜头的切变和渐变，适用范围广、鲁棒性强，并且资源消耗少.

［1］王鹏，杨士强，刘志强.信息论联合聚类算法及其在视频镜头聚类中的应用［J］.计算机学报，2005，28（10）：1693－1699.

［2］YEO B L，LIU B.On the extraction of DC sequences from MPEG compressed video ［C］//Proceedings of the 1995 International Conference on Image Processing.Washington：IEEE Computer Society，1995：260－263.

［3］智敏，蔡安妮.基于基色调的镜头边界检测方法［J］.自动化学报，2007，33（6）：654－657.

［4］WANG J Y，LUO W.A self－adapting dual－threshold method for video shot transition detection［C］//IEEE International Conference on Networking，Sensing and Control.Sanya，2008：704－707.

［5］NANG J H，HONG S W，IHM Y G.An efficient video segmentation scheme for MPEG video stream using macro block information ［C］//Proceeding of the seventh ACM International Conference on Multimedia.New York，1999：23－26.

［6］CHAU W S，AU O C，CHAN T W，et al.Optimal key frame selection using visual content metric［C］//2005International Conference on Communications circuits. New York：Association for Computing Machinery，2005：551－555.

［7］CALIC J，IZQUIERDO E.Efficient key－frame extraction and video analysis ［C ］//Proceedings of the International Conference on Information Technology：Coding and Computing.Washington：IEEE Computer Society，2002：28－33.

［8］ZHAO N，LV N，LIU H Y.Content－based cut shot detecting algorithm of news video ［J］.Journal of Jilin University：Information Science Edition，2009，27（1）：50－55.

［9］WANG Y，WEN X M，LIN X Q，et al.A novel video shot segmentation based on textural features［C］// 2009Fifth International Conference on Information Assurance and Security.Xi'an：IEEE Computer Society，2009：119－122.

［10］LI L，ZENG X L，LI X，et al.Video shot segmentation using graph－based dominant－set clustering［C］//Proceedings of the First（ACM）International Conference on Internet Multimedia Computing and Service.New York，2009：166－169.

［11］CAO J R，CAI A N.Algorithm for shot boundary detection based on support vector machine in compressed domain ［J］.Acta Electronic Sinica，2008，36（1）：203－208.

［12］LATECKI L J，LAKIMPER R.Convexity rule for shape decomposition based on discrete contour evolution ［J］.Computer Vision and Image Understanding，1999，73（3）：441－454.

［13］GARGI U，STRAYER S.Performance characterization of video－shot－change detection methods ［J］.IEEE Trans on Circuits and Systems for Video Technology，2000，10（1）：1－13.

A Method of Compressed Domain Video Shot Segmentation Based on DCE Algorithm

HUANG Yong－feng，XIONG Ze－dong，WANG Shao－yu
（School of Computer Science and Technology，Donghua University，Shanghai 201620，China）

Shot segmentation is structural base for video retrieval.An efficient video shot segmentation method is proposed.Firstly，the features are extracted from I frame of video stream in the compressed domain，and the curve of feature information is drawn.Then，the discrete curve evolution （DCE）algorithm is used to evolved the curve.Finally，video shots are segmented and key frames are extracted by the key points of the curve.The experimental results show that the method is efficient and robust，because it takes fully into account the timing features of video encoding.

compressed domain；shot segmentation；key frames；DCE algorithm

TP 391

A

2011－06－09

中央高校基本科研业务费专项资金科研计划资助项目（2011D11206）

黄永锋（1971—），男，山东泰安人，副教授，博士，研究方向为图像处理与模式识别.E－mail：yfhuang＠dhu.edu.cn

1671－0444（2012）03－0308－04