基于可变块运动矢量的边信息生成算法

程德强，姜海龙，郑 珍，郭 政

(中国矿业大学 信息与电气工程学院，江苏 徐州 221008)

基于可变块运动矢量的边信息生成算法

程德强，姜海龙，郑 珍，郭 政

(中国矿业大学 信息与电气工程学院，江苏 徐州 221008)

在分布式视频编码系统中，针对图像中细节丰富的区域易造成严重的块效应，提出了一种基于可变块运动矢量的边信息生成算法。根据前后相邻关键帧对应块的相关性，将像素块分为保留块和运动块。对保留块直接作保留处理，对运动块中的像素块继续进行分割并计算子块的初始运动矢量。再将全部块的运动矢量通过加权自适应运动补偿得到边信息。实验结果表明，对于运动较剧烈复杂的视频序列，该算法能够提高边信息生成质量， 并且使得改进后的边信息PSNR值提高了0.98～1.33 dB。

视频编码；运动估计；块分类；边信息

近年来，随着信息技术和无线网络的飞快发展，多媒体数据视频应用变得越来越普及。但是这些视频应用受到设备的带宽、电池耗电量、以及计算能力大小的问题，所以要求编码端的复杂度很小但解码端的复杂度可以很高，而以往的视频编码技术显然已经不能达到这些要求，必须寻找到新的视频压缩技术。为克服这些缺陷，大家开始关注分布式视频编码框架，它具有很多优势，分布式无损编码理论[1]以及解码端边信息的有损编码理论[2]是DVC理论的依据所在。该分布式视频编码通过在解码端充分利用信号的相关性，将复杂度从编码端转移到解码端，其中边信息生成的质量对于编码性能发挥着十分关键的作用。因为生成的边信息质量，直接影响到视频压缩的效率和图像的效果。

对于如何得到更加准确的运动矢量仍是生成高质量边信息非常重要的因素。Aaron等人提出了基于运动补偿时域内插[3]，首先对已解码的关键帧进行运动估计，然后计算帧间的运动轨迹，再依据在很短时间内物体做匀速直线运动假设的原理来估计边信息。为了获得更加准确的运动估计矢量，L.Natario 和J.Ascenso 等人提出对前后已解码的关键帧进行前向和双向运动估计[4-5]，并利用空间矢量平滑技术来平滑运动矢量场，进一步优化运动矢量。纪涛等人提出了一种基于混合模型的边信息预测算法[6]，该方法通过对块匹配效果较差的区域采用光流法重新估计其运动矢量从而获得效果较好的边信息。S.Ye等人结合传统运动估计，对已解码的WZ帧重新进行运动估计[7]，得到更加精准的运动矢量。后来研究者们对于高质量边信息的生成都是基于怎样才能进行精确的运动估计，使得到的运动矢量更加接近真实的运动矢量。

以上这些方法都必须假设每个划分的像素块在很短的时间内进行匀速直线运动，但现实生活中的视频序列帧几乎没有这样假设的视频，所以对于运动画面较为剧烈的区域，就会造成生成的边信息中宏块与宏块之间不连续和重叠的问题。针对上述问题，本文提出了一种可变块运动矢量的边信息生成算法，通过把宏块划分为尺寸更小的匹配块进行搜索，以获取更多运动矢量的细节，实验结果表明，本文提出的改进算法能够使生成的图像质量有所提高。

1 分布式视频编码系统

1.1 基于像素域的分布式视频编码系统

像素域的分布式视频编码系统基于信源有损编码理论，Aaron 等人提出了利用帧内编码和帧间解码的DVC结构[8]，如图1所示。系统按照奇偶数将视频序列分为关键帧(K帧)和Wyner-Ziv帧(WZ帧)两种类型。在编码端，K帧采用帧内编码方式；WZ帧进行编码时，应将对应位置的DCT转换系数经过量化器进行量化，产生量化符号流，然后将量化符号流通过LDPC 编码器生成校验比特，缓冲器会暂时存储系统的校验码。在解码端，K帧只需要普通的帧内解码即可，然后通过已解码的K帧得到边信息。然后，解码器再利用收到的校验比特和边信息进行重构。在达到良好的解码效果时所需的校验比特就越少，系统的压缩性能就越好。

图1 Wyner-Ziv视频编/解码系统

1.2 传统边信息生成算法

边信息是指对原始WZ帧的估计，生成方法中比较典型的有运动补偿内插法和运动补偿外推法，通过研究发现，内插法充分利用前后相邻帧之间的相关运动信息，产生的边信息较外推法效果更理想[9]。

1.2.1 前向运动估计法

生成前向运动估计的方法如图2所示，Y2k表示需要生成的边信息帧，X2k-1表示前关键帧，X2k+1表示后关键帧。为了预测插值帧Y2k中的块B2k的运动矢量，首先在后一关键帧中找到与块X2k+1相同位置的块B2k，用B2k+1在前一关键帧X2k-1进行匹配计算，找到最佳匹配块，通过B2k+1与B2k-1之间的位移矢量得出前后关键帧间前向运动矢量MV2k，由于宏块的运动连续且视频帧的时间间隔相同，因而B2k的前向运动矢量MVf2k为MV2k的一半，即满足表达式(1)

MVf2k=MV2k/2

(1)

边信息帧Y2k可由式(2)得到

Y2k(p)=X2k-1(p+MVf2k)

(2)

式中：p是边信息中像素的坐标。

图2 前向运动估计

1.2.2 双向运动估计法

由于前向运动估计获得的图像容易发生相邻块区域的不连续和重叠现象，从而使获得的运动矢量误差较大，针对这一现象，J.Ascenso等人以前向运动估计为基础，提出了双向运动估计方法[10]，如图3所示。

图3 双向运动佑计

双向运动估计假设插值帧到前一关键帧的运动矢量和到后一关键帧的运动矢量是对称的，即满足式(3)和式(4)

(x1，y1)=(xk,yk)+MV(Bk)

(3)

(x2，y2)=(xk,yk)+MV(Bk)

(4)

式中：(x1,y1)和(x2,y2)分别表示X2k-1帧和X2k-1帧中相应宏块的坐标；(xk,yk)生成的边信息相应宏块的坐标；MV(Bk)表示在前向运动估计中得到的运动矢量的一半。由于插值帧Y2k到前后两个关键帧的时间间隔是相等的，从而可以得到估计的预测帧，如式(5)所示

(5)

1.2.3 自适应加权运动场滤波

通过双向运动估计得到的运动矢量容易使某一块的运动矢量的方向和周围块的运动方向不一致，从而使获得的内插帧出现严重的块效应问题，如图4所示，获得的运动矢量比较混乱，当前宏块B0的运动矢量方向与其相邻八个方向的宏块的运动矢量截然相反，所以可以判断B0宏块的运动矢量很可能是一个局部最优值，不能反映运动场的实际情况，会严重影响边信息重建质量。为了改善这一缺陷，可以通过采用空域平滑算法来修正错误的运动矢量，因此卿粼波等人提出了一种自适应加权运动场滤波算法[11]，该算法通过有效利用块匹配度和相邻运动矢量的局部相关性，进而达到优化孤立异常运动矢量的目的。

图4 方向不一致的相邻块运动矢量

如图4中为MVi(i=0,1,…,8)为B0块及其相邻8个块的运动矢量，则B0块进行自适应加权运动场滤波后输出的运动矢量MV满足式(6)

(6)

式中：权重wi由式(8)决定，将每个MVi(i=0,1,…,8)作为当前块的运动矢量，由式(7)计算双向运动矢量残差D(MVi)

(7)

式中：(MVix,MViy)是候选块的运动矢量。

wi=D(MV0)/D(MVi)

(8)

显然，当D(MVi)越大，则权重wi越小，MVi输出的可能性也就越小，反之亦然。

2 基于可变块运动矢量的边信息生成算法

运动估计的基本思想是将每一帧图像分成多个互不重叠的宏块，然后对每个宏块进行运动搜索，找出与当前块的相似度最高的宏块，该块即为匹配块。然而对于区域运动丰富且变化多的视频帧图像，多个不同方向的运动矢量就可能存在于同一个宏块里，导致宏块的实际运动轨迹并非一个运动矢量就能表示。为了使得到的运动矢量场更加接近真实运动矢量场，可以考虑把这个宏块划分为尺寸更小的匹配块进行搜索，以获取更多运动矢量的细节[12]。所以本文提出了一种基于可变块的运动矢量优化算法。

2.1 对块进行分类

本文采用的块大小是16×16，将视频序列的前关键帧X2k-1进行分块，并将对应的像素块标记为B2k-1,j，对后关键帧X2k+1进行分块，并将对应的像素块标记为B2k+1,j，同时将边信息帧对应像素块标记为B2k,j。

将前后关键帧X2k-1、X2k+1的对应像素块B2k-1,j，B2k+1,j按照式(9)分别进行求和绝对误差SAD计算，当SAD值越小时表明其相关性越强

(9)

由于视频序列的运动复杂度不一样，所以对于前后运动一致性较好的区域(如静止的背景)采用较大的块；而对于前后运动变化较大的区域(如运动的物体)采用较小的块，并重新对这些小块进行运动估计。通过以上分析，首先设定阈值T1，然后对求和绝对误差值SAD和T1进行比较，将像素块分为运动块和保留块两类，如图5所示。具体计算步骤如下：

1)计算各对应块的SAD并与T1进行比较。若SAD大于T1，则认为像素块对B2k-1,j和B2k+1,j的运动剧烈程度较大，将其像素块对判定为运动块，否则将其判定为保留块。

2)对于运动块，将该16×16的块继续划分为8×8的子块，并对这些块做运动估计，重新计算SAD′的值，重新设定新的阈值T2，比较SAD′和T2的大小，若SAD′大于T2，则转到第3步，并判定该子块也是运动块，否则是保留块。

3)将8×8的运动子块再划分为4×4的子块，并对这些块做运动估计，算法结束。

图5 可变块的划分

2.2 计算子块初始运动矢量

由于运动矢量在空域上是高度相关的，因此可以根据式(7)，分别计算当前子块B0的8个相邻子块的双向运动矢量残差D(MVi)，并认为该子块的初始运动矢就是D(MVi)值最小的那个块的运动矢量。但是如图4所示，由于这8个子块里面有的子块可能来源于同一个父块，会发生重复现象，但是以当前子块为中心的两条对角线上对应的4个子块可以替代所有的8个相邻块，所以只要选取两条对角线上的4个子块即可[13]。具体计算步骤如下：

1)将内插帧16×16的图像运动块划分为8×8的子块，并把16×16块的运动矢量设定为其对应的4个8×8子块运动矢量，记为MV0。

4)经过步骤1)～3)，内插帧运动矢量场已由16×16的块表示成8×8的块，保证了运动矢量的精度，提高了图像的主观质量，重复步骤1)～3)，可以获得更加平滑、精确的4×4级运动矢量场。

2.3 多候选运动补偿

因为视频运动具有不确定性、复杂性以及图像噪声等原因，通过以上步骤计算获得的运动矢量会存在一定的误差，会使生成的边信息帧中出现严重的块效应。为了克服上述缺陷，重叠块运动补偿方法可以减少块效应和改善图像质量，但是容易产生模糊和过平滑现象。因此，本文采用一种基于多候选运动矢量的加权自适应运动补偿算法来得到质量更高的边信息。

由于都是根据多假设运动补偿的方法，因此本文提出的补偿算法与重叠块运动补偿原理一样。多假设运动补偿是基于去噪的思想，选择多个质量差不多的运动补偿预测信号作为原始信号的候选信号，然后将多个预测信号加权线性组合处理，就达到去噪的目的，从而获得了更加精确的预测值[14]。

如图6所示，由当前块及其相邻块的运动矢量一起当着当前块的候选运动矢量集，每个候选矢量都可以生成一个预测信号Yi，如式(10)所示

X2i+1(m-MVkx,n-MVky)]

(10)

式中：(m,n)表示当前块；i∈[0,N]是候选块的系数索引；(MVkx,MVky)是候选块的运动矢量。当进行线性组合时，各个预测信号的质量决定预测信号的权值wk，通常情况，双向预测误差越小，表示前向和后向运动补偿块的匹配度越高，生成当前块的预测质量效果就越佳，因此wk由式(11)表示为

wk= (X2k-1(m+MVkx,n+MVky)-

X2k+1(m-MVkx,n-MVky))-1

(11)

加权自适应的运动补偿插值结果Y2k(m,n)如式(12)所示

(12)

3 实验结果及分析

本文分别选择对Foreman序列和Coastguard序列的前100帧进行编码测试，其中Foreman序列背景时有镜头摇晃的场景，前景运动强度中等，Coastguard纹理丰富细节变化多，运动强度中等。实验条件及假设：序列格式均为QCIF(176×144)，设置系统GOP为2，且认为K帧能完好地传到解码端。为更好地说明算法的优越性，在进行测试过程中只考虑WZ帧亮度分量部分。实验结果如图6和图7所示。图6a和图7a分别表示Foreman序列和Coastguard序列的第25帧(前关键帧)，图6b和图7b分别表示Foreman序列和Coastguard序列的第27帧(后关键帧)，图6c和图7c分别表示Foreman序列和Coastguard序列的第26帧(WZ帧)，图6d和图7d分别表示Foreman序列和Coastguard序列用本文算法生成的边信息。从图中可以看出本文算法生成的边信息帧基本上与原始帧没有差别。

图6 本文算法生成的Foreman边信息

图7 本文算法生成的Coastguard边信息

计算边信息的PSNR值采用如下方式：1)单向运动估计；2)双向运动估计；3)AWMFF；4)可变宏块大小法。测试结果如表1所示。

表1 不同算法生成边信息的PSNR值比较dB

图像PSNR单向双向AWMFF可变宏块Foreman3421345034723548Coastguard3372339134213505

如图8和图9所示，Foreman序列和Coastguard序列对应3种不同方法下的PSNR分布曲线。

图8 Foreman序列相应生成边信息帧的PSNR分布图

图9 Coastguard序列相应生成边信息帧的PSNR分布图

从图表可以看出，相比单向运动估计，采用双向运动估计方法可以使块效应减少，更加接近真实的图像效果。由于AWMFF方法剔除了运动估计环节产生的部分错误运动矢量，使运动矢量更接近真实的运动轨迹，从而提高了图像的PSNR值。另外，通过图表可以发现，本文提出的改进算法生成的边信息质量，在整个视频序列上几乎都要优于其他方法。在码率相同的情况下，对于Foreman序列，改进的算法相比单向运动估计和双向运动估计，分别提高了1.27 dB和 0.98 dB。 而对于Coastguard序列，改进的算法相比单向运动估计和双向运动估计，分别提高了1.33 dB和1.14 dB。如图10和 图11 所示，还可以通过边信息的运动矢量图来分析物体的运动情况，结合图6和图7，可以发现运动矢量图与Foreman序列和Coastguard序列的运动情况基本保持一致。由此可见，本文算法通过在解码端进行更为精确可靠的运动估计，使产生的边信息图像与原始帧误差最小，即效果最好。

图10 Foreman序列第26帧的边信息运动矢量图

图11 Coastguard序列第26帧的边信息运动矢量图

4 结束语

如何生成更加准确的边信息是DVC系统中一个非常关键的技术。本文提出的基于可变块运动矢量的边信息生成算法，通过把宏块划分为尺寸更小的匹配块进行搜索，以获取更多运动矢量的细节。实验结果表明，本文采用的算法对运动较为剧烈复杂的视频序列效果更为理想，从而提高了系统的性能。对于今后的研究方向，研究者们可以针对不同运动剧烈程度的视频序列，研究怎样才能有效对块的大小进行分类，从而使系统的编码性能缩小与H.264 Inter编码方式的差距。

[1] SLEPIAN J D，WOLF J K. Noiseless coding of correlated information sources[J].IEEE Trans. Information Theory，1973(19)：471-480.

[2] WYNER A D，ZIV J. The rate-distortion function for source coding with side information at the decoder[J]. IEEE Trans. Information Theory，1975，22(1)：1-10.

[3] WORK C K，OSCAR C A. Fast motion compensated temporal interpolation for video[C]//Proc. Process of SPIE.Taipei，China：SPIE Press，1995：1108-1118.

[4] NATARIO L，BRITES C，ASCENSO J，et al. Extrapolating side information for low-delay pixel domain distributed video coding[C]//Proc. Int. Workshop on Very Low Bitrate Video Coding.[S.l.]：IEEE Press，2005：2-17.

[5] ASCENSO J，BRITES C，PEREIRA F. Improving frame interpolation with spatial motion smoothing for pixel domain distributed video coding[C]//Proc. 5th EURASIP Conf. on Speech and Image Processing，Multimedia Communications and Servers. Smolenice，Slovak Republic：[s.n.]，2005：65-69.

[6] 纪涛.分布式视频编码中基于混合模型的边信息生成算法[J].微电子学与计算机，2010，38(9)：16-19.

[7] YE S，OUARET M，DUFAUX F. Improved side information generation with iterative decoding and frame interpolation for distributed video coding[C]//Proc. 15th International Conference on Image Processing. San Deigo，USA：IEEE Press，2008：2228-2231.

[8] AARON A，ZHANG R，GIROD B.Wyner-Ziv coding of motion video[C]//Proc. Conference Record of the Asilomar Conference on Signals，Systems and Computers.[S.l.]：IEEE Press，2002：240-244.

[9] 尹明，蔡述庭，谢云.基于高斯混合模型的Wyner-Ziv视频编码[J].计算机学报.2012，34(1)：173-182.

[10] ASCENSO J，BRITES C，PERELRA F. Motion compensated refinement for low complexity pixel based distributed video coding[C]//Proc. IEEE International Conference on Advanced Video and Signal Based Surveillance. Como，Italy：IEEE Press，2005：1-5.

[11] 卿粼波，何小海，吕瑞，等.分布式视频编码中边信息的多策略优化[J].四川大学学报，2008，39(12)：7-12.

[12] 全子一.图像信源压缩编码及信道传输理论与新技术[M].北京：北京工业大学出版社，2006.

[13] 刘东，杜明辉.基于块的分布式视频编码边信息生成技术[J].华南理工大学学报：自然科学版，2011(39)：32-38.

[14] 马力，苏卓涵，杨春玲.基于多假设运动补偿预测的边信息改进方法[J].计算机工程,2011，28(2)：71-72.

责任编辑：时 雯

Side Information Generation Algorithm Based on Variable Block Motion Vector

CHENG Deqiang，JIANG Hailong，ZHENG Zhen，GUO Zheng

(DepartmentofInformationandElectricalEngineering，ChinaUniversityofMiningandTechnology，JiangsuXuzhou221008，China)

Aiming at the problem that areas which have rich details can result in serious blocking effects in a distributed video coding system，a side information generation algorithm based on variable block motion vector is proposed.The pixel blocks are divided into preservation blocks and motion blocks according to the correlation between the blocks in adjacent key frames.The preservation blocks are directly retained， and the pixel blocks existed in the motion blocks are continued to divide and its initial motion vectors of the sub-blocks are calculated.At last，in order to get improved side information，it uses the method of weighted adaptive motion compensation to process all the motion vectors of corresponding blocks.The experimental results show that， for the video sequence is severely complex， this algorithm can improve the quality of the side information generation and the PSNR of the improved method proposed in this paper can increase by 0.98～1.33 dB.

video coding； motion estimation； block-classified； side information

国家自然科学基金项目(51204175)

TN919.8

A

10.16280/j.videoe.2015.19.001

程德强(1979— )，教授，博士生导师，主要研究方向为图像处理与视频信号编码、多媒体信息传输；

姜海龙(1988— )硕士生，主要研究方向为视频信号编码与图像处理技术；

郑 珍(1989— )，女，硕士生，主要研究方向为多媒体图像传输、宽带网络技术；

郭 政(1990— )硕士生，主要研究方向为矿井图像处理及应用。

2015-03-14

【本文献信息】程德强，姜海龙，郑珍，等.基于可变块运动矢量的边信息生成算法[J].电视技术,2015，39(19).