像素域分布式视频编码双向运动补偿重建算法*

杨春玲 苏卓涵

(华南理工大学电子与信息学院，广东广州510640)

近年来，分布式视频编码(DVC)成为视频压缩领域的研究热点.与传统视频编码技术编码复杂、解码简单的特点不同，分布式视频编码在编码端不考虑视频各帧之间的相关性，而在解码端利用视频的帧间相关性进行解码，将编码端的复杂运算移至解码端，大大降低了编码的复杂度.因此，分布式视频编码在计算能力、内存和耗电量均受限的无线视频终端领域有广阔的应用前景.分布式视频编码的理论基础是20世纪70年代由Slepian等［1］建立的分布式无损编码理论以及由Wyner等［2］建立的使用解码端边信息的有损编码理论.这两个理论指出:利用独立编码、联合解码的分布式编解码方法对两个统计相关信号进行压缩，可以达到与传统的联合编解码方法相同的编码效率.近几年，一些实用的分布式视频编码系统相继被提出.其中，Aaron等［3］建立的像素域Wyner-Ziv视频编码系统结构简单，性能良好，引起了广泛关注.

在像素域分布式视频编码中，重建模块直接影响着解码视频的质量.最早的重建算法是文献［3］提出的简单重建算法.在该算法中，如果边信息落入译码符号对应的量化区间内，就直接用边信息进行重建，否则利用量化区间边界进行重建.简单重建算法复杂度低，但性能较差，因此不少学者提出了改进算法.文献［4-5］利用像素的空间相关性来辅助重建，但并未考虑视频前后帧的相关性.文献［6-7］利用前后向关键帧的信息来改进重建，但这两个算法对整帧以简单的块的形式进行运动补偿，得到的补偿值未必都比原来的精确，特别是在选取关键帧编码质量与译码的Wyner-Ziv帧质量相近的情况下，运动补偿得到的补偿帧质量可能反而会更差.在重建改进算法中，Kubasov等［8］提出的最小均方误差(MMSE)重建算法是均方误差准则下的理论最优算法，被广泛应用于分布式视频编码中.该算法利用边信息与原始像素之间的虚拟相关模型计算出像素的期望值作为重建值，以使重建帧的均方误差最小.这样的处理方法在整体统计上是最优的，但仍然存在以下两方面问题:一是对于边信息落在正确量化区间的像素，MMSE重建算法在边信息基础上进行修正，破坏了边信息帧在平坦区域的原有的连续性，造成了明显的边界;二是对于边信息落在正确区间外的像素仅仅考虑了边信息与原信息的统计关系，未考虑周围像素和前后帧的像素的影响，得到的重建值有时并不精确.

根据以上分析，结合分布式视频压缩算法的特点，文中提出了双向运动补偿重建(Bi-Directional Motion Compensated Reconstruction，BMCR)算法.该算法中，重建被看成是边信息生成的延续，进一步利用前后关键帧的信息来构造Wyner-Ziv帧:当边信息值落在译码符号所对应的量化区间内时，这个边信息值可以认为是原像素的良好估计，为保留边信息帧平坦区域整体上的连续性，直接利用边信息值进行重建;当边信息值在译码符号所对应的量化区间外时，综合考虑周围像素以及前后帧相应像素的影响，通过以该点为中心的块进行结合量化区间的双向运动补偿产生重建值.因为解码器已通过Turbo码的译码符号获得原始Wyner-Ziv帧的像素所处的量化区间，所以在运动估计和补偿时能更好地利用关键帧的信息来辅助重建，得到更好的重建效果.

1 像素域分布式视频编码

图1给出了文中所使用的像素域分布式视频编码的框架，该框架主要以Aaron等［3］建立的像素域Wyner-Ziv视频编码系统为基础.在编码端，视频序列被分为关键帧(奇数帧)和Wyner-Ziv帧(偶数帧).对于关键帧，采用传统视频编码的帧内编码方法进行编码;对于Wyner-Ziv帧，对帧内的像素进行2M级均匀量化及码平面分离，形成M个码平面，将每个码平面作为一个信息帧q，采用码率兼容删余Turbo码(RCPT码［9］)进行独立编码.编码后校验位保存到缓存器中，并根据解码器的反馈信息选择性地传送校验位.

图1 像素域DVC框架Fig.1 Framework of pixel-domain DVC

在解码端，对于关键帧，通过传统视频解码的帧内解码得到解码后的关键帧;对于Wyner-Ziv帧，解码器对已解码的前后关键帧进行运动补偿内插得到边信息Y［10-11］，Turbo码译码器利用边信息和接收到的部分校验位进行译码，恢复原始Wyner-Ziv帧的量化符号.如果译码不成功，则通过反馈信道向编码端请求更多的校验位，直至误码门限低于某个设定的误码门限为止.在译码过程中，边信息和原信息之间的虚拟信道采用拉普拉斯模型来描述并通过估计得到拉普拉斯参数［12］.

在此之后，重建模块利用边信息和Turbo译码器译码得到的量化符号q'进行重建.假设x为原始像素值，y为边信息值，文献［3］中的简单重建算法可表示为

式中，fx|y(x)为在已知y的条件下x的条件概率密度函数.该算法的重建值是统计上的最优值，但是对于视频中的像素，单纯从统计上得到的重建值有时并不精确，应综合考虑视频的特性(即视频帧内和帧间相关性)进行估计.因此，文中提出了双向运动补偿重建算法，利用已经得到的量化区间和运动补偿技术来辅助重建那些边信息落在正确区间外的像素点.算法的细节在下节中说明.

2 双向运动补偿重建算法

双向运动补偿重建算法的基本思想是将重建看成边信息生成的延续.在边信息生成过程中，用前后关键帧的信息通过运动补偿来估计当前Wyner-Ziv帧.但是由于边信息生成时无法获得原始Wyner-Ziv帧的信息，因此在估计过程中前后关键帧的信息并未被很好地利用.在重建过程中，原始Wyner-Ziv帧的量化符号已经获得，因此文中在重建过程通过结合量化区间的双向运动补偿技术来进一步利用前后关键帧的信息，从而更好地构造出Wyner-Ziv帧.

在双向运动补偿重建算法中，对于落在正确量化区间［zi，zi+1)内的边信息值y，可以看成是原信息的良好估计，因此y直接作为重建值;而对于其它像素，先通过结合量化区间的双向运动补偿技术找到前后向运动补偿值，再对这些补偿值进行必要的修正，最后，计算出修正后的前后向补偿值的平均值作为该像素的重建值.双向运动补偿重建算法的重建公式为

式中，xf和xb分别为修正后的前向和后向运动补偿值.

该算法的具体过程包括如下4个步骤:

(1)初始重建.在这一步中，对于边信息落在译码符号对应的量化区间［zi，zi+1)内的像素，直接用边信息值y进行重建.之所以直接用边信息进行重建而不进行修正，是为了在重建帧中尽可能保留边信息帧像素的连续性.而对于其余的像素，由于在接下来的运动估计时需要利用到各个像素的像素值，这里采用较为合理的MMSE算法对它们进行初始重建.

(2)双向运动补偿.对于每个边信息落在译码符号对应的量化区间外的像素点，为了保证该像素点能够找到最为合适的补偿点，以该点为中心选取一个5×5的块进行双向运动估计.运动估计的匹配准则是加权绝对误差和(WSAD).考虑到此时解码端已经获得的原始Wyner-Ziv帧像素的量化区间，WSAD的加权系数根据参考点的像素是否落入正确量化区间来定义.假设(x0，y0)是当前像素点坐标，WSAD 的定义如下［6］:

式中，X'2i为步骤(1)中的初始重建帧，X'k为前关键帧(k=2i－1)或后关键帧(k=2i+1)，(px，py)为X'2i中像素点的坐标，(dx，dy)为运动矢量，Q表示括号内像素的量化符号.

在运动估计中，找出当前块的前后向运动矢量作为当前像素的运动矢量，进而可以得到当前像素的前后向补偿值xfmc和xbmc:

式中，(dxf，dyf)代表前向运动矢量，(dxb，dyb)代表后向运动矢量.

(3)运动补偿值修正.在运动补偿过程中，部分像素得到的运动补偿值落在正确的量化区间内，这些补偿值被认为是足够精确的，但是仍有部分像素的补偿值落在译码符号对应的量化区间外，这样的补偿值直接重建出来的像素质量不佳.因此需要对运动补偿值进行必要的修正.假设xmc代表运动补偿值xfmc或xbmc，修正后的补偿值为

在修正之后，x'mc落在区间［zi，zi+1)内.这里得到的x'mc正是公式(3)中的xf或xb.

(4)最终重建.对于那些边信息落在正确量化区间外的像素点，计算出修正后前后向补偿值的平均值作为重建值，如式(3)中的第2种情况所示.由于xf和xb都落在［zi，zi+1)内，因此最终的重建值也必然落在［zi，zi+1)内.

3 实验结果及分析

为验证双向运动补偿重建算法的性能，将其与文献［3］、［6］和［8］的算法进行比较，并得到相应的实验结果.实验的硬件环境如下:CPU为2.81 GHz的AMD athlon(tm)Ⅱ X4 630 processor，内存大小为2 GB.软件环境如下:操作系统为 Windows XP sp3，实验平台为Microsoft Visual C++2005.实验中，选用运动强度中等的Foreman序列和运动强度剧烈的Soccer序列进行实验.两个序列均为QCIF格式，帧率为30 fps.实验中对两个序列前201帧(包含100帧Wyner-Ziv帧)的亮度分量进行编解码.对于关键帧，采用H.264帧内编解码，量化参数QP选择的准则是使得解码后的关键帧与Wyner-Ziv帧的平均质量保持在同一水平.对于Wyner-Ziv帧，边信息用文献［10］的分级运动估计算法生成.实验通过对Wyner-Ziv帧量化级数 2M(2M∈{2，4，8，16})的调整，产生不同的码率点.系统所用的Turbo编码器码率为1/2，生成矩阵为解码端误码门限Pe=10－3.

图2给出了不同重建算法下Wyner-Ziv帧的率失真(RD)曲线.由实验结果可知，对于Foreman序列和Soccer序列，文中提出的双向运动补偿重建算法比文献［3］中的简单重建算法在解码质量上均高出1dB以上.相比于文献［6］的算法，文中提出的算法由于采取了以像素点为中心的块运动估计、补偿值修正等技术，因此两个序列的质量平均提高约0.6dB.而相比于文献［8］的MMSE重建算法，文中提出的双向运动补偿重建算法的两个序列的总体平均效果有0.5dB的提高，其中Foreman序列提升了约0.2dB，Soccer序列增益达0.9 dB.两个序列增益不同的原因是:Soccer序列相比于Foreman序列运动复杂度高，边信息质量较差，因此边信息落在量化区间外的像素比例较大，由于这些像素的重建质量在双向运动补偿重建算法中得到了改进，所以总体性能上Soccer序列的增益也比Foreman大.由此也可以看出，边信息质量越差，文中的双向运动补偿重建算法对系统性能的提升越大.

图3示出了Soccer序列各帧的重建质量(已解码4个码平面，M=3).由图3可以看出，文中提出的双向运动补偿重建算法各帧的重建质量均比文献［3］和文献［6］的算法要好.对比文献［8］的 MMSE算法，对于那些本身解码质量较差的帧，文中算法的重建质量有明显的提高;而对于那些解码质量较好的帧，双向运动补偿重建算法的重建质量与文献［8］的MMSE算法相当.这是因为:那些边信息质量较好的Wyner-Ziv帧本身解码重建后的质量就比关键帧要高，如果用关键帧作为参考帧进行运动补偿，改进效果不明显;而对于那些边信息较差的Wyner-Ziv帧，关键帧质量比解码重建后的Wyner-Ziv帧好，这时双向运动补偿算法利用关键帧的信息来辅助重建Wyner-Ziv帧，提高了Wyner-Ziv帧的重建质量.双向运动补偿重建算法在提升解码后视频序列总体性能的同时，也使得视频序列中各帧的质量变化更加平稳.

图2 4种算法解码Foreman序列和Soccer序列的RD性能Fig.2 RD performance of Foreman and Soccer sequences decoded by using four algorithms

图3 4种算法重建的Soccer序列各帧质量Fig.3 Reconstruction quality of each frame for Soccer sequence by using four algorithms

图4为双向运动补偿重建算法和其它重建算法得到的Soccer序列的主观质量图(M=3，第110帧).正如前文所提到的，像素域分布式视频编码中的MMSE重建算法对于边信息落在正确量化区间内的像素的处理破坏了原有边信息帧平坦区域的连续性，产生了一些明显的边界，如图4(d)中球场所示.文中的双向运动补偿重建算法直接利用边信息值来重建那些边信息落入正确区间的像素，因此不会出现这样的失真.对于边缘区域，由图4中的脚可以看出，双向运动补偿重建算法的重建图像的边界比其它算法均要清晰.这是因为边信息落在正确区间外的像素大多出现在边缘区域，双向运动补偿重建算法能利用运动补偿技术为这些像素找到更为精确的重建值，因此在视觉上双向运动补偿重建算法重建图像中的物体轮廓更为清晰.总体上说，文中算法的视觉效果优于其它3种算法.

图4 4种算法的Soccer序列主观重建质量图Fig.4 Subjective reconstruction quality of Soccer sequence by using four algorithms

在计算复杂度上，分布式视频编码的解码计算量主要集中在运动估计补偿和Turbo码的迭代译码.由于文中提出的算法将重建看成是边信息生成的延续，在重建时引入了运动估计，因此增加了一定的计算量.表1中给出了不同序列在采用文献［8］的MMSE重建算法和采用双向运动补偿重建算法的情况下平均每帧的解码时间，由实验结果可以看出，文中算法每帧的平均解码时间有所增加，并且码平面数越大，解码时间增加的比例越大.这是由于随着量化区间变得更为精确，落在正确译码区间外的像素比例有较大的增加，使得文中算法用在运动估计上的时间更长.需要指出的是:文中算法增加的计算复杂度仅仅是解码端的复杂度，对于分布式视频编码的编码复杂度并无影响.分布式视频编码更加关注的是编码复杂度，而解码复杂度是次要考虑的因素;并且，现阶段，分布式视频编码的瓶颈依然是解码性能，特别是中高速运动序列的解码性能，而文中提出的算法恰恰是改进了中高速运动序列的性能.因此文中提出的算法在改进性能的同时增加这样的复杂度对于分布式视频编码来说是可以接受的.

表1 采用不同重建算法的解码时间Table 1 Decoding time using different reconstruction algorithms

4 结语

文中提出了一种像素域分布式视频编码的双向运动补偿重建算法.在该算法中，对于边信息值落在译码符号对应量化区间内的像素，直接利用边信息来重建;而对于边信息落在译码符号对应量化区间外的像素，则采用修正后的前后向运动补偿值的均值来进行重建.实验结果表明，与MMSE重建算法相比，文中提出的双向运动补偿重建算法对于中高速运动强度视频序列的RD性能平均提高了约0.5dB，并且解码后视频序列各帧的质量更加稳定.同时，文中的重建算法所得到的解码图像的视觉质量也得到了有效的提升.由于在重建过程中引入了运动估计，文中提出的算法在分布式视频编码译码端引入了一定的计算量，如何在保持文中算法性能的条件下，利用边信息生成过程中已有的运动矢量缩小运动补偿重建过程中的搜索范围以降低计算复杂度，是下一步研究的重点.

［1］Slepian D，Wolf J.Noiseless coding of correlated information sources［J］.IEEE Transactions on Information Theory，1973，19(4):471-480.

［2］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.

［3］Aaron A，Zhang R，Girod B.Wyner-Ziv coding of motion video［C］∥The Thirty-Sixth Asilomar Conference on Signals，Systems and Computers，2002.Pacific Grove:IEEE，2002:240-244.

［4］Shim S Y，Han J K，Bae J.Adaptive reconstruction scheme using neighbour pixels in PD Wyner-Ziv coding［J］.Electronics Letters，2010，46(9):626-628.

［5］Zhang Y，Xiong H，He Z，et al.Reconstruction for distributed video coding:a context-adaptive Markov random field approach ［J］.IEEE Transactions on Circuit and System for Video Technology，2011，21(8):1-14.

［6］Ascenso J，Brites C，Pereir F.Motion compensated refinement for low complexity pixel based distributed video coding［C］∥Proceedings of Advanced Video and Signal Based Surveillance 2005.Como:IEEE，2005:593-598.

［7］Liu Hongbin，Li Yongpeng，Liu Xianming，et al.Two-pass reconstruction in distributed video coding［C］∥The 27th Conferenceon Picture CodingSymposium.Chicago:IEEE，2009:1-4.

［8］Kubasov D，Nayak J，Guillemot C.Optimal reconstruction in Wyner-Ziv video coding with multiple side information［C］∥Multimedia Signal Processing 2007.Chania:IEEE，2007:183-186.

［9］Rowitch D，Milstein L.On the performance of hybrid FEC/ARQ systems using rate compatible punctured Turbo codes［J］.IEEE Transactions on Communications，2000，48(6):948-959.

［10］Ascenso J，Pereira F.Hierarchical motion estimation for side information creation in Wyner-Ziv video coding［C］∥Proceedings of the 2nd International Conference on Ubiquitous Information Management and Communication.New York:ACM Press，2008:347-352.

［11］刘东，杜明辉.基于块的分布式视频编码边信息生成技术［J］.华南理工大学学报:自然科学版，2011，39(2):32-38.Liu Dong，Du Ming-hui.Generation of side information of distributed video coding at block level［J］.Journal of South China University of Technology:Natural Science Edition，2011，39(2):32-38.

［12］Brites C，Pereira F.Correlation noise modeling for efficient pixel and transform domain Wyner-Ziv video coding［J］.IEEE Transactions on Circuits and Systems for Video Technology，2008，18(9):1177-1190.