分布式视频编码的关键帧提取算法

宋晓丽，刘冀伟，张晓星

(北京科技大学信息工程学院，北京 100083)

分布式视频编码的关键帧提取算法

宋晓丽，刘冀伟，张晓星

(北京科技大学信息工程学院，北京 100083)

分布式视频编码方案中，目前常用固定周期的方法选取关键帧.该方法忽略了视频序列的帧间相关性、运动变化情况.针对这些缺陷，研究了基于聚类的自适应关键帧提取算法，在此基础上，提出基于互信息量的改进算法.最后，针对以上2种算法中的时延问题给出了解决方案.实验证明，对于不同的测试序列，基于互信息量改进算法相比固定选取关键帧算法，边信息PSNR均值有0.67～1.4dB的提高.此外，解决时延的算法比改进算法在效率上有很大提高.

分布式视频编码;关键帧;互信息

传统视频编码方案在编码端隐含一个解码器，使编码端的运算复杂度是解码端的5～10倍以上［1］.这种编码方案适用于编码端复杂的领域.而近年来，一些新的移动视频设备如:移动视频相机、移动视频电话、无线PC机等需要低复杂度编码.此时，传统的视频编码方案难以胜任，迫切需要一种编码端复杂度低的编码方案.在此背景下，一种新的视频编码框架—分布式视频编码(distributed video coding，DVC)应运而生.该编码方案是基于20世纪70年代Slepian和Wolf［2］的分布式无损编码理论以及 Wyner和 Ziv［3］的使用解码端边信息(side information)的有损编码理论而建立.从2002年起DVC的实现算法逐渐引起关注，成为视频编码领域关注较多的前沿课题之一.

Wyner－Ziv 视频编码 (Wyner－Ziv video coding，WZVC)是DVC编码的一种主流框架.在WZVC中，待编码的帧分为K帧和Wyner－Ziv(WZ)帧，K帧是通过传统的视频编码方案进行帧内编解码，而WZ帧则是通过信道编码，仅传输校验位给解码端.大多数WZVC方案采用周期性选择关键帧的方法，该方法有许多弊端［4］:如果视频序列运动缓慢，选择过多的关键帧会造成冗余，不利于压缩比的提高;如果视频序列运动剧烈，选择较少的关键帧则难以生成高质量的边信息.为了解决这些问题，需要一种有效的选择关键帧的方法，使得关键帧会随着视频序列的运动情况而灵活变化.

文献［5］提出一种基于聚类算法的自适应关键帧提取算法;文献［4］利用感兴趣点来描述图像的信息，提出一种基于感兴趣点匹配的关键帧选择算法;文献［6］利用SURF算法得到的特征点信息作为对帧间相关性的近似估计，提出一种自适应选取关键帧的方法.上述几种方法从不同角度进行了关键帧提取算法的研究，系统性能比周期性选取关键帧提取算法均有所提高.

本文研究了文献［5］中的算法，并且从另一角度，利用互信息量来描述相邻2帧的相关性，提出基于互信息量的自适应关键帧提取改进算法，从系统性能和计算复杂度上对文献［5］中的算法进行了改进，然后对算法中的时延问题给出了解决方案.

1 Wyner－Ziv 视频编码框架

本文采用变换域分布式视频编码系统［7］，编码框架如图1所示，首先将视频序列分为K帧和WZ帧(每个GOP里的首帧为K帧，其余帧为WZ帧).K帧采用传统帧内编解码方法.WZ帧经过基于8×8的块DCT变换后，进行量化，然后提取位平面，从高位到低位依次送入LDPC编码器编码，编码后根据解码端的反馈信息，将要求的校验位送到解码端.

图1 Wyner－Ziv视频编码框架Fig.1 Architecture Wyner-Ziv video coding

在Wyner－Ziv视频编码系统框架中，解码是最复杂的部分，对于K帧，只需要进行传统的帧内解码就可以得到相应的解码帧;而对于每个WZ帧，解码器都会利用相邻的已经解码的K帧，使用时间域上的插值或者外推的方法形成作为估计WZ帧的辅助信息，对辅助信息做DCT变换，和编码端一样提取位平面，送入LDPC解码器;LDPC解码器，如果不能可靠地解码出符号流，会通过反馈信息从编码器的缓冲区中申请附加的奇偶校验码;利用解码后的比特流和DCT变换后的边信息重建WZ帧.

2 自适应选取关键帧

2.1 基于聚类的自适应关键帧提取

文中利用以下4个低水平特征指标来评估视频序列的运动剧烈程度［5］:1)直方图差DH;2)差的直方图HD;3)块的直方图差BHD;4)块的方差的差BVD;

它们的定义如下:

式中:i、j代表帧的索引，h代表L区间的直方图，Df和DB分别代表帧和块的大小，σ代表方差，对于指标HD，α代表与原值接近的阈值.前2个指标在帧水平上，检测全部运动的变化，HD指标是非常有效的.BHD和BVD指标对于局部运用更为敏感.

基于上述4个指标的聚类关键帧提取算法描述如下:

1)计算所有帧中相邻帧间的4个指标，建立四维矢量，并进行归一化;

2)累积相邻2帧帧间运动矢量，找到相邻2帧帧间运动矢量规范化式最小值对应的下标值;

3)将该下标值对应的帧与后一帧或后一类进行聚类;

4)重复步骤2)、3)，直到相邻2帧间运动积累大于设定的阈值φ时，停止聚类.

φ控制聚类的类数，同时也控制了关键帧帧数(每类里的首帧为关键帧).

2.2 基于互信息量的关键帧提取

2.2.1 互信息量

互信息量源于信息论，不仅是2个随机变量相似性的量度，同时也决定了每一个独立的随机变量在交迭处各自表示的信息量的大小.利用互信息量作为图像的相似性测度是Collignon［9］于1995年提出的，它在应用上取得了很大成功.

2幅图像的互信息量定义如下:式中:PX(x)和PY(y)分别表示前一帧X和当前帧Y的概率密度函数，由图像的直方图除以图像总的像素个数得到;PXY(xy)表示相邻2帧的联合概率密，由图像X、Y的联合直方图除以图像总的像素个数得到.由定义可知，互信息量并不信赖于灰度值本身，而是信赖于这些灰度值出现的概率.当互信息量为0时，说明视频序列相邻帧发生剧烈运动，该相邻帧相互独立;当互信息量值较大时，意味着相邻帧间的相似性程度较高，所以互信息量能很好地反映视频序列中相邻2帧间的相似性程度.

2.2.2 关键帧提取的改进算法

互信息量从全局运动来反映视频相邻2帧间的变化，2.1节中的DH和HD这2个指标也是从全局角度出发来衡量2帧间的相似性.但互信息量表示的是2幅图像相互包含对方的信息量，即帧X包含帧Y的信息量或帧Y包含帧X的信息量，相比于DH和HD，互信息量更加直接，全面描述了2帧的相似程度.因此在改进算法中用互信息量替换DH和HD作为衡量视频序列全局变化的指标，同时保留原有的局部指标:BHD和BVD.

改进的关键帧提取算法步骤如下:

1)计算所有视频序列的相邻2帧间的I、BHD和BVD，建立三维矢量，并进行归一化;

2)、3)、4)同2.1节中基于聚类的关键帧提取算法中步骤 2)、3)、4).

由式(1)、(2)和(3)得知，改进算法的计算复杂度明显减小.首先，互信息量的计算量小于DH和HD的计算量和;其次，相比于原算法中的基于四维矢量聚类，改进算法中基于三维矢量进行聚类较为简单.

3 解决时延的关键帧提取算法

基于聚类的自适应关键帧提取算法和基于互信息量的关键帧提取算法，在编码端的聚类过程引进了时延，这不满足实际应用的实时性.因而有必要对上述2种方法的时延问题进行研究，本文给出了合理的解决方案.

假设视频序列比较平稳，根据系统已经选择好的GOP可以预测后续视频序列的GOP，减少编码端等待时间，同时选择几个不同GOP中率失真性能最优(用每个GOP中WZ帧的率失真性能代替整个GOP的率失真性能)的GOP作为编码组，进而保证了选择的关键帧的有效性.其中速率的估计可以直接获得［9］，WZ 帧 PSNR 值估计［10］如式(6):

解决时延的关键帧提取算法的具体过程如下:

1)以当前帧为起始帧，在编码端分别计算GOP为2、3、4时的率失真性能;

2)选择最优性能的GOP作为特定窗口内的第一个GOP，窗口的初始大小为1，当且仅当当前获得的GOP与先前的GOP一样时，窗口尺寸才会增加(W=2×Wold，W＜20)，否则W=1;

3)Wold=W;

4)W为1时，使用选择好的GOP进行编码，从下一帧算起，回到1);

5)当W不为1时，连续进行W个GOP(从当前GOP的前一个GOP作为初始值算起)编码，未完成时重复进行4)，否则重新开始测试GOP，回到1).

根据上述分析及算法步骤可知，该算法选择性能最优GOP作为编码GOP，能保证系统的性能，且在满足一定条件时，允许连续编码，可以用当前的GOP作为后续窗口内的GOP，明显减少测试GOP所用的时间，因此该算法在保证系统性能的前提下，能有效减少时延.

4 实验结果

本部分首先给出传统周期性关键帧提取算法(periodical key frame selection，PKFS)、基于聚类的自适应关键帧提取算法(clustering adaptive key frame selection，CAKFS)和基于互信息量关键帧提取改进算法(mutual information key frame selection improving algorithm，MIKFS)3种方案的性能对比，结果如表1所示.实验中，以Foreman、Coastguard序列作为测试序列，以边信息和原始WZ帧的平均PSNR作为评判标准，通过调整阈值使3种方案中的关键帧数(key frame number，KFN)相同.

表1 PKFS、CAKFS与MIKFS的性能比较Table 1 Comparison results of the performance of PKFS，CAKFS and MIKFS dB

分析表1的数据可知，在测试序列为 Foreman、Coastguard时，相比于PKFS方案，CAKFS方案中边信息质量分别平均提高了0.13 dB、0.97 dB.本文给出的MIKFS改进方案中边信息质量相比于CAKFS方案提高了0.53 dB、0.47 dB;相比于PKFS方案提高了0.67 dB、1.4 dB.可见说明了本文MIKFS方案的优越性.

关于解决时延的关键帧提取算法的实验，用Foreman序列的前100帧来测试，测试架构是本文第2部分给出的DVC框架，1)量化部分采用JPEG标准里量化矩阵，量化因子为 QF=(0.5，2，4)，取不同的量化因子，可以获得不同的输出码率和不同质量的重建帧.量化因子为0.5时，DEKFS算法获得的GOP情况如图2;2)调节CAKFS和MIKFS中的阈值，使3类算法的关键帧数相等;3)边信息使用传统的运动补偿内插方案来插出.首先给出以PSNR值作为评判准则，DEKFS算法与PKFS算法相比较的结果如表2所示.

图2 DEKFS算法的GOP情况Fig.2 GOP results of DEKFS algorithm

表2 PKFS与DEKFS的性能比较Table 2 Comparison results of the performance of PKFS and DEKFS dB

分析表2的数据可知，在测试序列为 100帧Foreman时，相比于PKFS方案，DEKFS方案中边信息质量平均提高了0.1 dB.

另外给出了CAKFS算法、MIKFS算法与解决时延的关键帧选取算法(delay efficient key frame selection，DEKFS)整体性能比较结果.分别统计CAKFS算法、MIKFS算法和解决时延的关键帧选取算法中总WZ帧的率失真性能，测试结果如图3.

图3 Wyner－Ziv系统性能对比Fig.3 Performance comparison of Wyner-Ziv system

3类算法的时间统计结果如图4.

图4 3种算法的时间对比Fig.4 Time comparison of three algorithms

由图3可知，解决时延的关键帧算法与基于聚类的自适应关键帧算法和改进算法相比，率失真性能有略微降低.主要是因为本文的算法是在假设视频序列比较平稳的前提下进行的，这样可以预测后续视频序列的GOP，另外，DEKFS算法限制了每个GOP里能取的帧数的范围.

虽然DEKFS算法相比于CAKFS和MIKFS，率失真性能略微降低，但从图4可得，DEKFS算法相比于 PKFS在时间对比度上有明显的优越性.CAKFS和MIKFS算法必须把所有的帧先聚类，才能编码，这样编码端聚类没有完成时，编码器闲置起来，造成时间的浪费.而CAKFS算法在获得一组GOP后，编码器即可开始编码，编码和后续GOP的获得可以同时进行，允许系统持续编码，对于平稳的视频序列，可以通过前面的GOP获得即将编码的GOP尺寸，减少计算量，且更有效地减少了时间.因此，从实际角度出发，能够解决时延的算法更有效.

5 结束语

DVC中固定选取关键帧的方法对系统性能的提高有一定的局限性.基于此，本文在研究基于聚类的关键帧提取算法的基础上，提出了基于互信息量的改进算法，改进算法中用互信息量作为反映视频序列的帧间相关性的全局指标，优化了率失真性能，同时提高了计算效率.但以上2种算法都有一定的延迟效应，解决时延的算法在率失真性能上略微降低，却有效地减少了编码器的等待时间，更具有实际应用价值.后续的工作将考虑如何更精确地度量帧间相关性，优化DVC的率失真性能，以及在DVC的率失真性能和关键帧选取算法的复杂度之间找到平衡点.

［1］NILSSON M.The advanced video coding standard［C］//IT to HD:Visions of Broadcasting in the 21st Century.London，UK，2004:85－100.

［2］SLEPIAN D，WOLF J.Noiseless coding of correlated information sources［J］.IEEE Transactions on Information Theory，1973，19(4):471－480.

［3］WYNER A，ZIV J.The rate－distortion function for source coding with side information at the decoder［J］.IEEE Transactions on Information Theory，1976，22(1):1－10.

［4］YANG Feng，DING Guiguang，DAI Qionghai.Adaptive key frame selection Wyner－Ziv video coding［C］//IEEE Multimedia Signal Processing.Shanghai，China，2005:1－4.

［5］ASCENSO J，BRITES C，PRERIRA F.Content adaptive Wyner－Ziv video coding driven by motion activity［C］//IEEE International Conference on Image Processing.Atlanta，USA，2006:605－609.

［6］张晓星，刘冀伟，张波.分布视频编码中基于帧间相关性的自适应关键帧选取算法［J］.光电子·激光，2010，21(10):1536－1541.

ZHANG Xiaoxing，LIU Jiwei，ZHANG Bo.Adaptive key frame selection algorithm based on interframe correlation in distributed video coding［J］Journal of Optoelectronics·Laser，2010，21(10):1536－1541

［7］AARON A，RANE S，SETTON E，et al.Transforms－domian Wyner－Ziv codec for video［C］//Visual Comm－ unications and Image Processing.San Jose，USA，2004:520－528.

［8］MAES F，COLLIGNON A，VANDERMEULEN D.Multi－modality image registration by maximization of mutual information［C］//Mathematical Methods in Biomedical Image Analysis.San Francisco，USA，1996:14－22.

［9］YAACOUB C，FARAH J，PESQUET－POPESCU B.Optimal rate allocation in multi－user Wyner－Ziv video coding systems with coded key frames［C］//Personal，Indoor and Mobile Radio Communications.Cannes，France，2008:1－5.

［10］AHMAD I，AHMAD Z，ABOU－FAYCAL I.Delay－efficient GOP size control algorithm in Wyner－Ziv video coding［C］//Signal Processing and Information Technology.Ajman，United Arab Emirates，2009:403－408.

宋晓丽，女，1986年生，硕士研究生，主要研究方向为图像处理、视频压缩等.

刘冀伟，男，1962年生，副教授，中国人工智能学会、人工心理与情感计算专业委员会理事，主要研究方向为图像处理、视频压缩、人工智能系统等，近年来在国内外著名期刊与会议上发表学术论文40余篇，出版著作多部.

张晓星，男，1984年生，博士研究生，主要研究方向为图像处理、图像、视频编码等.

A key frame selection algorithm for distributed video coding

SONG Xiaoli，LIU Jiwei，ZHANG Xiaoxing
(School of Information Engineering，Beijing University of Science and Technology，Beijing 100083，China)

In most of the existing distributed video coding schemes，the fixed period method is usually applied for selecting a key frame.This strategy ignores the correlation between video frames and the changes of the motion activity along the video sequence.To avoid these flaws，this paper studied the adaptive key frame selection method based on hierarchical clustering;on this basis，an improved algorithm based on mutual information was proposed.Finally，a solution was given to overcome the delay in the above－mentioned methods.Experimental results show that for various video sequences，a 0.67－1.4dB gain in the quality of side information has been achieved.In addition to being delay－efficient，the key selection algorithm requires the lowest performance time.

distributed video coding;key frame;seection algorithm;mutual information

TP18;TN919.81

A

1673－4785(2011)06－0539－05

10.3969/j.issn.1673－4785.2011.06.010

2011－07－11.

国家自然科学基金资助项目(60903067).

宋晓丽.E－mail:xysxl02@163.com.