第6卷第6期 智能系统学报 Vol.6 No.6 2011年12月 CAAI Transactions on Intelligent Systems Dec.2011 doi:10.3969/i.issn.16734785.2011.06.010 分布式视频编码的关键帧提取算法 宋晓丽，刘冀伟，张晓星 (北京科技大学信息工程学院，北京100083） 摘要：分布式视频编码方案中，目前常用固定周期的方法选取关键帧.该方法忽略了视频序列的帧间相关性、运动 变化情况.针对这些缺陷，研究了基于聚类的自适应关键帧提取算法，在此基础上，提出基于互信息量的改进算法. 最后，针对以上2种算法中的时延问题给出了解决方案.实验证明，对于不同的测试序列，基于互信息量改进算法相 比固定选取关键帧算法，边信息PSNR均值有0.67~1.4dB的提高.此外，解决时延的算法比改进算法在效率上有很 大提高 关键词：分布式视频编码：关键帧：互信息 中图分类号：TP18:TN919.81文献标识码：A文章编号：16734785(2011)06053905 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) Abstract: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 ac- tivity 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. Keywords:distributed video coding;key frame;seection algorithm;mutual information 传统视频编码方案在编码端隐含一个解码器，的实现算法逐渐引起关注，成为视频编码领域关注 使编码端的运算复杂度是解码端的5~10倍以 较多的前沿课题之一. 上口.这种编码方案适用于编码端复杂的领域.而 Wyner--Ziv视频编码(Wyner-Ziv video coding, 近年来，一些新的移动视频设备如：移动视频相机、 WZVC)是DVC编码的一种主流框架.在WZVC中， 移动视频电话、无线P℃机等需要低复杂度编码.此 待编码的帧分为K帧和Wyner-Ziv(WZ)帧，K帧是 时，传统的视频编码方案难以胜任，迫切需要一种编 通过传统的视频编码方案进行帧内编解码，而WZ 码端复杂度低的编码方案.在此背景下，一种新的视 帧则是通过信道编码，仅传输校验位给解码端.大多 频编码框架一分布式视频编码(distributed video 数WZVC方案采用周期性选择关键帧的方法，该方 coding,DVC)应运而生.该编码方案是基于20世纪 法有许多弊端4]：如果视频序列运动缓慢，选择过 70年代Slepian和Wolf2]的分布式无损编码理论以 多的关键帧会造成冗余，不利于压缩比的提高；如果 及Wyner和Zivs)的使用解码端边信息(side infor- 视频序列运动剧烈，选择较少的关键帧则难以生成 mation)的有损编码理论而建立.从2002年起DVC 高质量的边信息.为了解决这些问题，需要一种有效 收稿日期：201107-11. 的选择关键帧的方法，使得关键帧会随着视频序列 基金项目：国家自然科学基金资助项目(60903067). 的运动情况而灵活变化. 通信作者：宋晓丽.E-mail:ysx02@163.com, 文献[5]提出一种基于聚类算法的自适应关键
·540 智能系统学报 第6卷 帧提取算法；文献[4]利用感兴趣点来描述图像的 比特流和DCT变换后的边信息重建WZ帧， 信息，提出一种基于感兴趣点匹配的关键帧选择算 法；文献[6]利用SURF算法得到的特征点信息作为 2自适应选取关键帧 对帧间相关性的近似估计，提出一种自适应选取关 2.1基于聚类的自适应关键帧提取 键帧的方法.上述几种方法从不同角度进行了关键 文中利用以下4个低水平特征指标来评估视频 帧提取算法的研究，系统性能比周期性选取关键帧 序列的运动剧烈程度5]：1)直方图差DH;2)差的直 提取算法均有所提高。 方图HD:3)块的直方图差BHD;4)块的方差的差 本文研究了文献[5]中的算法，并且从另一角 BVD: 度，利用互信息量来描述相邻2帧的相关性，提出基 它们的定义如下： 于互信息量的自适应关键帧提取改进算法，从系统 DH(i,j) =1h,()-h,(k)1, D: (1) 性能和计算复杂度上对文献[5]中的算法进行了改 进，然后对算法中的时延问题给出了解决方案， HD(i,j)= ()+ 1 l/2-a =0 h-(k), =/2+ 1 Wyner-Ziv视频编码框架 (2) 本文采用变换域分布式视频编码系统「)，编码 D/DB L BHD(i)= ∑∑Ih,(b,k)-h(b,k)I, 框架如图1所示，首先将视频序列分为K帧和WZ 帧（每个GOP里的首帧为K帧，其余帧为WZ帧）. D/D8 L BVD(i,j)= K帧采用传统帧内编解码方法.WZ帧经过基于8× AA1i(6,)-i(6,l 8的块DCT变换后，进行量化，然后提取位平面，从 式中：i代表帧的索引，h代表L区间的直方图，D 高位到低位依次送入LDP℃编码器编码，编码后根 和DB分别代表帧和块的大小，σ代表方差，对于指 据解码端的反馈信息，将要求的校验位送到解码端。 标D,α代表与原值接近的阈值.前2个指标在帧 水平上，检测全部运动的变化，HD指标是非常有效 Slepian-Wolf Codec 的.BHD和BVD指标对于局部运用更为敏感， 基于上述4个指标的聚类关键帧提取算法描述 如下： 1)计算所有帧中相邻帧间的4个指标，建立四 维矢量，并进行归一化； 2)累积相邻2帧帧间运动矢量，找到相邻2帧 帧间运动矢量规范化式最小值对应的下标值； 视颍 3)将该下标值对应的帧与后一帧或后一类进 码流 关键顿 提取 行聚类； 运动内捅 4)重复步骤2)、3)，直到相邻2帧间运动积累 传统顿 传统制 大于设定的阈值”时，停止聚类， 内编码 内解码 P控制聚类的类数，同时也控制了关键帧帧数 图1 Wyner--iv视频编码框架 (每类里的首帧为关键帧). Fig.1 Architecture Wyner-Ziv video coding 2.2基于互信息量的关键帧提取 在Wyner-Ziv视频编码系统框架中，解码是最 2.2.1互信息量 复杂的部分，对于K帧，只需要进行传统的帧内解 互信息量源于信息论，不仅是2个随机变量相 码就可以得到相应的解码帧；而对于每个WZ帧，解 似性的量度，同时也决定了每一个独立的随机变量 码器都会利用相邻的已经解码的K帧，使用时间域 在交迭处各自表示的信息量的大小，利用互信息量 上的插值或者外推的方法形成作为估计WZ帧的辅 作为图像的相似性测度是Collignon]于1995年提 助信息，对辅助信息做DCT变换，和编码端一样提 出的，它在应用上取得了很大成功 取位平面，送入LDPC解码器；LDPC解码器，如果不 2幅图像的互信息量定义如下： 能可靠地解码出符号流，会通过反馈信息从编码器 I(X,=∑Pm(x,）logPx(x,y）/P.(x)P(y）. 的缓冲区中申请附加的奇偶校验码；利用解码后的 (3)
第6期 宋晓丽，等：分布式视频编码的关键帧提取算法 。541· 式中：Px(x)和P,(y)分别表示前一帧X和当前帧Y 接获得91，WZ帧PSNR值估计o1如式(6)： 的概率密度函数，由图像的直方图除以图像总的像 Lmi,disU; (4 由图像X、Y的联合直方图除以图像总的像素个数 dis,UB<ds<L 得到.由定义可知，互信息量并不信赖于灰度值本 Lg=(Ce-1/2)×qs1, 身，而是信赖于这些灰度值出现的概率，当互信息量 Um=(C+1/2)×q, 为0时，说明视频序列相邻帧发生剧烈运动，该相邻 N-1 帧相互独立；当互信息量值较大时，意味着相邻帧间 MSEe=∑(da-aae)2/N (5) 司 的相似性程度较高，所以互信息量能很好地反映视 式中：d为重建WZ帧的DCT系数，ds为边信息的 频序列中相邻2帧间的相似性程度， DCT系数，L、U分别表示原始WZ帧量化的上、下 2.2.2关键帧提取的改进算法 限，C为原始WZ帧的量化系数，q,为DCT系数第 互信息量从全局运动来反映视频相邻2帧间的 j个系数带的量化步长， 变化，2.1节中的DH和HD这2个指标也是从全局 解决时延的关键帧提取算法的具体过程如下： 角度出发来衡量2帧间的相似性，但互信息量表示 1)以当前帧为起始帧，在编码端分别计算G0P 的是2幅图像相互包含对方的信息量，即帧X包含 为2、3、4时的率失真性能； 帧Y的信息量或帧Y包含帧X的信息量，相比于 2)选择最优性能的G0P作为特定窗口内的第 DH和HD,互信息量更加直接，全面描述了2帧的 一个G0P,窗口的初始大小为1，当且仅当当前获得 相似程度.因此在改进算法中用互信息量替换DH 的GOP与先前的GOP一样时，窗口尺寸才会增加 和HD作为衡量视频序列全局变化的指标，同时保 (W=2×Wold,W<20),否则W=1; 留原有的局部指标：BHD和BVD. 3)Wold =W; 改进的关键帧提取算法步骤如下： 4)W为1时，使用选择好的G0P进行编码，从 1)计算所有视频序列的相邻2帧间的I、BHD 下一帧算起，回到1)； 和BVD,建立三维矢量，并进行归一化； 5)当W不为1时，连续进行W个GOP(从当前 2)、3)、4)同2.1节中基于聚类的关键帧提取 GOP的前一个GOP作为初始值算起)编码，未完成 算法中步骤2)、3)、4) 时重复进行4)，否则重新开始测试G0P,回到1). 由式(1)、(2)和(3)得知，改进算法的计算复 根据上述分析及算法步骤可知，该算法选择性 杂度明显减小.首先，互信息量的计算量小于DH和 能最优GOP作为编码GOP,能保证系统的性能，且 HD的计算量和；其次，相比于原算法中的基于四维 在满足一定条件时，允许连续编码，可以用当前的 矢量聚类，改进算法中基于三维矢量进行聚类较为 GOP作为后续窗口内的GOP,明显减少测试GOP所 简单 用的时间，因此该算法在保证系统性能的前提下，能 3解决时延的关键帧提取算法 有效减少时延， 4 基于聚类的自适应关键帧提取算法和基于互信 实验结果 息量的关键帧提取算法，在编码端的聚类过程引进 本部分首先给出传统周期性关键帧提取算法 了时延，这不满足实际应用的实时性.因而有必要对 (periodical key frame selection,PKFS)、基于聚类的 上述2种方法的时延问题进行研究，本文给出了合 自适应关键帧提取算法（clustering adaptive key 理的解决方案， frame selection,CAKFS)和基于互信息量关键帧提 假设视频序列比较平稳，根据系统已经选择好 取改进算法(mutual information key frame selection 的GOP可以预测后续视频序列的GOP,减少编码端 improving algorithm,MKFS)3种方案的性能对比， 等待时间，同时选择几个不同G0P中率失真性能最 结果如表1所示.实验中，以Foreman、Coastguard序 优（用每个GOP中WZ帧的率失真性能代替整个 列作为测试序列，以边信息和原始WZ帧的平均 GOP的率失真性能)的GOP作为编码组，进而保证 PSNR作为评判标准，通过调整阈值使3种方案中 了选择的关键帧的有效性.其中速率的估计可以直 的关键帧数(key frame number.,KFN)相同
·542 智能系统学报 第6卷 表1PKFS、CAKFS与MIKFS的性能比较 Table 1 Comparison results of the performance of PKFS,CAKFS and MIKFS dB KFN为25 KFN为33 KFN为50 算法 Foreman Coastguard Foreman Coastguard Foreman Coastguard PKFS 30.7 29.9 31.6 29.4 34.3 31.9 CAKFS 30.1 28.5 31.8 31.1 35.1 34.5 MIKFS 30.7 29.2 32.0 31.4 35.9 34.9 分析表1的数据可知，在测试序列为Foreman、 分析表2的数据可知，在测试序列为100帧 Coastguard时，相比于PKFS方案，CAKFS方案中边 Foreman时，相比于PKFS方案，DEKFS方案中边信 信息质量分别平均提高了0.13dB、0.97dB.本文给 息质量平均提高了0.1dB 出的MIKFS改进方案中边信息质量相比于CAKFS 另外给出了CAKFS算法、MIKFS算法与解决时 方案提高了0.53dB0.47dB;相比于PKFS方案提 延的关键帧选取算法(delay efficient key frame selec- 高了0.67dB、1.4dB.可见说明了本文MIKFS方案 tion,DEKFS)整体性能比较结果.分别统计CAKFS 的优越性。 算法、MKFS算法和解决时延的关键帧选取算法中 关于解决时延的关键帧提取算法的实验，用 总WZ帧的率失真性能，测试结果如图3， Foreman序列的前l00帧来测试，测试架构是本文 39 第2部分给出的DVC框架，1)量化部分采用PEG 38 标准里量化矩阵，量化因子为QF=(0.5,2,4),取 37 不同的量化因子，可以获得不同的输出码率和不同 质量的重建帧.量化因子为0.5时，DEKFS算法获 36 得的GOP情况如图2；2)调节CAKFS和MIKFS中 35 的阈值，使3类算法的关键帧数相等；3)边信息使 34 --MIKFS 用传统的运动补偿内插方案来插出.首先给出以 CAKFS 33 PSNR值作为评判准则，DEKFS算法与PKFS算法相 DEKFS 37 比较的结果如表2所示. 100 150 200 250300 350 4.0 3.8 图3 Wyner-.Ziv系统性能对比 3.6 Fig.3 Performance comparison of Wyner-Ziv system 3.4 3.2 3类算法的时间统计结果如图4. 30 3.0 2.8 25 6 20 2.4 2.2 10 2.0 10 15 20 253035 GOP数吊 w CAKFS算法MIKFS算法DEKFS算法 图2 DEKFS算法的GOP情况 图43种算法的时间对比 Fig.2 GOP results of DEKFS algorithm Fig.4 Time comparison of three algorithms 表2PKFS与DEKFS的性能比较 由图3可知，解决时延的关键帧算法与基于聚 Table 2 Comparison results of the performance of PKFS 类的自适应关键帧算法和改进算法相比，率失真性 and DEKFS dB 能有略微降低.主要是因为本文的算法是在假设视 KFN为33 序列方法 频序列比较平稳的前提下进行的，这样可以预测后 PKFS DEKFS 续视频序列的GOP,另外，DEKFS算法限制了每个 Foreman 31.6 31.7 GOP里能取的帧数的范围
第6期 宋晓丽，等：分布式视频编码的关键帧提取算法 ·543· 虽然DEKS算法相比于CAKFS和MKFS,率 [6]张晓星，刘冀伟，张波.分布视频编码中基于顿间相关性 失真性能略微降低，但从图4可得，DEKS算法相 的自适应关键帧选取算法[J].光电子·激光，2010,21 比于PKFS在时间对比度上有明显的优越性. (10):1536-1541 CAKFS和MIKFS算法必须把所有的帧先聚类，才能 ZHANG Xiaoxing,LIU Jiwei,ZHANG Bo.Adaptive key frame selection algorithm based on interframe correlation in 编码，这样编码端聚类没有完成时，编码器闲置起 distributed video coding[J]Journal of Optoelectronics La- 来，造成时间的浪费.而CAKFS算法在获得一组 96r,2010,21(10):1536-1541 GOP后，编码器即可开始编码，编码和后续GOP的 [7]AARON A,RANE S,SETTON E,et al.Transforms-domi- 获得可以同时进行，允许系统持续编码，对于平稳的 an Wyner-Ziv codec for video C]//Visual Comm-unica- 视频序列，可以通过前面的GOP获得即将编码的 tions and Image Processing.San Jose,USA,2004:520- GOP尺寸，减少计算量，且更有效地减少了时间.因 528. 此，从实际角度出发，能够解决时延的算法更有效、 [8]MAES F,COLLIGNON A,VANDERMEULEN D.Multi-m- odality image registration by maximization of mutual informa- 5 结束语 tion[C]//Mathematical Methods in Biomedical Image Anal- DVC中固定选取关键帧的方法对系统性能的 ysis.San Francisco,USA,1996:14-22. 提高有一定的局限性.基于此，本文在研究基于聚类 [9]YAACOUB C,FARAH J,PESQUET-POPESCU B.Opti- mal 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- 序列的帧间相关性的全局指标，优化了率失真性能， 同时提高了计算效率.但以上2种算法都有一定的 [10]AHMAD I,AHMAD Z,ABOU-FAYCAL I.Delay-effic- 延迟效应，解决时延的算法在率失真性能上略微降 ient GOP size control algorithm in Wyner-Ziv video coding 低，却有效地减少了编码器的等待时间，更具有实际 [C]//Signal Processing and Information Technology.Aj- 应用价值.后续的工作将考虑如何更精确地度量帧 man,United Arab Emirates,2009:403-408. 间相关性，优化DVC的率失真性能，以及在DVC的 作者简介： 宋晓丽，女，1986年生，硕士研究 率失真性能和关键帧选取算法的复杂度之间找到平 生，主要研究方向为图像处理、视频压 衡点。 缩等】 参考文献： [1]NILSSON M.The advanced video coding standard[C]//IT to HD:Visions of Broadcasting in the 21st Century.Lon- don,UK,2004:85-100. 刘冀伟，男，1962年生，副教授，中 [2]SLEPIAN D,WOLF J.Noiseless coding of correlated infor- 国人工智能学会、人工心理与情感计算 mation sources[J].IEEE Transactions on Information Theo- 专业委员会理事，主要研究方向为图像 y,1973,19(4):471480. 处理、视频压缩、人工智能系统等，近年 [3]WYNER A,ZIV J.The rate-distortion function for source 来在国内外著名期刊与会议上发表学 coding with side information at the decoder[J].IEEE 术论文40余篇，出版著作多部 Transactions on Information Theory,1976,22(1):1-10. [4]YANG Feng,DING Guiguang,DAI Qionghai.Adaptive key 张晓星，男，1984年生，博士研究 frame selection Wyner-Ziv video coding[C]//IEEE Multi- 生，主要研究方向为图像处理、图像、视 media 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.Atlan- ta,USA,2006:605609