视频压缩感知中基于快速搜索的迭代多假设算法*

杨春玲 熊光银 戴超

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

视频压缩感知中基于快速搜索的迭代多假设算法*

杨春玲 熊光银 戴超

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

针对观测域和像素域两阶段多假设预测重构方案在低采样率时重构效果不理想，且对于运动剧烈的序列预测精度不够、时间复杂度较高等问题，在两阶段多假设预测的基础上，提出了基于快速搜索的迭代多假设预测重构算法.该算法利用像素域分块的灵活性，基于重叠块在像素域迭代预测重构；针对运动较快的序列，采用十字形联合区域搜索方法以减小大范围搜索的算法复杂度；同时利用图像空间相关性进行帧间/帧内自适应假设块的模式选择与已有算法相比，文中重构算法进一步削弱了块效应，降低了大范围搜索的运算复杂度，提高了重构性能.

视频压缩感知；多假设预测；假设块；像素域；迭代预测；预测精度；时间复杂度

在传统的视频压缩信号采集模式中，若想无失真的恢复视频信号，采样率必须满足奈奎斯特采样定理.Donoho、Candès等[1- 3]提出的压缩感知(CS)理论打破了传统采样率限制，其基本思想是：对于可压缩信号，在编码端通过一个不相关的观测矩阵采样得到少量的观测值，在解码端利用信号在变换域稀疏表示的先验信息，通过压缩感知重构算法可以高概率地恢复原信号.

压缩感知理论提出之后，许多学者不断深入研究其在视频采集和压缩领域的应用.文献[4]提出将视频帧分割为关键帧和非关键帧，其中关键帧采样率较高，并在解码端独立重构以获得重构质量较高的图像帧.非关键帧将与其比较相关的帧以及相邻两端的关键帧作为参考帧进行联合重构.因此对于非关键帧重构，如何充分利用帧间相关性提升重构质量是研究视频压缩感知的关键点，而多假设预测方法由于其充分挖掘帧间相关性信息的特性，逐渐成为视频压缩感知中主流方法之一.在多假设预测中，关键点是假设块的选择和权值计算问题.文献[5- 6]提出对当前帧中的每一个非重叠图像块，以欧氏距离为基准在多参考帧中搜寻多个较好的假设块，理论分析将多个假设块通过相应的权值结合，得到近似预测值，并提出了Tikhonov正则项来优化求解假设块的权值计算.在上述研究基础上，文献[7- 8]分别将I1范数、I2范数和权值向量稀疏性融入到假设块权值求解问题中，不但保证了稀疏性，而且提高了预测准确性.此外，为了避免相关性较弱的假设块影响重构质量，文献[9- 10]均提出需要对假设块集合进行筛选，即只保留与当前重构块最相关的若干匹配块，从而避免相关程度较低的匹配块的干扰，进一步提高对当前帧的预测精度.但是文献[5- 8]中假设块的选取形式过于单一，相关性信息利用不充分，于是文献[9]作者提出了多参考帧多假设预测算法(MRMH)，文献[10]中也提出了扩充更新多假设块集合的算法，使得假设块的选取有了更多的选择.

上述算法中都是在观测域匹配选取假设块，假设块大小需与采集端分块大小一致.因此，不可避免地会引起块效应.针对此问题，文献[11]作者提出了两阶段多假设重构算法(2SMHR)，即在观测域预测残差重构的基础上再进行一次像素域预测及残差重构，由于在像素域的预测分块更加灵活，可以有效地消除观测域非重叠块预测引起的块效应，有效地提高了重构质量.但两阶段多假设重构算法依然存在以下两方面的问题：在低采样率时依然存在明显块效应；对快速运动序列，由于运动估计时搜索范围的限制，预测精度不高，导致重构性能不高.针对这两个问题，本研究提出了基于快速搜索的迭代多假设预测优化算法(IMH)，并通过实验与现有算法进行了对比.

1 视频压缩感知中多假设预测

1.1 观测域多假设预测

视频压缩感知中多采用分块观测[10,12]模式，其基本思想是：将每个视频帧分成相同B×B大小的子图像块，对每一个子块用高斯随机观测矩阵Φ进行观测：

yi=Φxi

(1)

式中，x的第i列xi为第i个图像块的列向量化，Φ为M×B2维的高斯随机矩阵，y的第i列yi为第i个图像块的观测值，采样率为M/B2.

(2)

由于MEMC/运动估计是在解码端进行，摆脱了码率的限制，文献[8]提出选取多个假设块，用这一组假设块的线性组合作为当前块的预测，即

(3)

(4)

式中：H为全搜索得到的假设块列矢量集合组成的矩阵，w为相应假设块权值集合组成的向量.由于当前块观测值y的维度M较小，因此一般情况下，假设块个数满足k≫M，故，为不定解问题(式(4))添加Tikonov正则约束项进行权值求解，如式(5)所示.

(5)

其中，

Γ=diag(‖yi-ΦH1‖2,…,‖yi-ΦHi‖2,…,

‖yi-ΦHk‖2)

(6)

其中,Hi为第i个假设块的列向量化，λ为常数，并可得权值向量的闭式解：

w=((ΦH)T(ΦH)+λΓTΓ)-1(ΦH)Tyi

(7)

多假设预测与单假设预测对比，视频帧重构质量得到提升.上述算法是在观测域选取假设块，预测帧分块被局限为非重叠分块，这将导致预测帧块效应明显.针对此问题，文献[11]提出在观测域预测的基础上，在像素域进行多假设预测过程，以弥补观测域预测的不足.

1.2 像素域多假设预测

(8)

由于在像素域预测分块可以重叠，充分利用这一点，基于重叠块在像素域预测，可以进一步降低预测帧的块效应，得到的残差信号更加稀疏，继而提高视频重构质量.

2 基于快速搜索的迭代多假设预测优化算法——IMH

在文献[11]提出的两阶段预测重构算法(2SMHR)的基础上，本研究提出了基于快速搜索的迭代多假设预测算法(IMH)，其算法结构如图1所示.

相对于2SMHR 算法，本研究算法提出3点改进方案：①提出了像素域的多次迭代预测方法及迭代终止条件，以提高低采样率时的预测重构性能；②提出了一种用于假设块匹配的快速搜索算法，对于运动剧烈的序列，在保证重构质量的前提下，大大减少了算法的复杂度；③在假设块匹配过程中增加了帧内假设块选择，提出了自适应假设块选择模式，以提高在前后参考帧中得不到较好假设块时的预测性能.

图1 基于快速搜索的迭代多假设预测算法框架

2.1 像素域迭代预测

在2SMHR算法中，其在观测域预测重构后增加了像素域预测重构步骤，对视频重构质量提升较高.但对于低采样率情况，重构质量还相对较差，文中通过深入研究，在2SMHR基础上提出了像素域多次迭代预测重构算法，进一步提升了视频序列的重构性能.具体步骤如下：

步骤1 像素域多假设预测.第k次迭代利用上一次的重构结果(若是首次迭代则利用观测域多假设预测重构结果)，对每个重叠图像块在多个参考帧中选取n个最优假设块集合，记为Hk，通过式(9)求解权值向量wk：

(9)

2.2 区域快速搜索方案

在视频压缩感知多假设预测算法中，假设块的获取至关重要，尤其对于剧烈运动的序列，较大的搜索范围可以匹配到较好的假设块，但同时也带来了巨大的计算负担.因此本研究基于传统视频编码中非对称十字形搜索方案[14]，针对剧烈运动序列提出了快速搜索方案，以降低快速运动序列匹配块搜索的计算复杂度，其步骤如下.

初步搜索：以当前图像块为中心的非对称十字区域内间隔s像素点搜索当前图像块的最佳匹配块.

联合搜索：分别以当前图像块位置和步骤1搜索到的最佳匹配块位置为中心，在较小范围内逐点匹配搜索，得到多假设匹配块组.

图2中十字形阴影区域为初步搜索范围，区域1为以当前图像块为中心的搜索区域，区域2为以最佳匹配块为中心的搜索区域，R表示为十字搜索区域半径，r为区域1和区域2的搜索区域半径.

图2 搜索区域示意图

2.3 自适应假设块模式选择

由于视频序列中场景变化的不确定性，在当前帧中可能会出现新的图像块信息[12].对这些新信息，无法在参考帧中找到与其较匹配的假设块.此时若仍利用参考帧中得到的次优匹配块，则可能无法达到像素域增强预测的目的.对于这些图像块，文中提出利用图像空间相关性在当前帧中搜索并筛选最优假设块，称之为帧内模式.基于此，文中提出了自适应假设块模式选择思路，即利用阈值TSSIM自适应选择图像块的多假设预测模式(帧间预测(Inter-mode)/帧内预测模式(Intra-mode)).利用结构相似度SSIM(i,j)作为当前图像块xi与第j个假设块的匹配准则，若满足式(10)则选择帧间预测模式，反之，选择帧内预测模式.

max {SSIM(i,j),(j∈[1,n])}>TSSIM

(10)

3 实验结果与分析

3.1 迭代多假设预测算法仿真实验及性能分析

采用5组QCIF格式的标准视频序列foreman、hall、coastguard、football和soccer的前129帧(GOP=8)进行实验分析，实验结果示于表1和图3.在实验中，像素域重叠块分块大小b=8；像素域多假设预测块个数n=8；关键帧采样率0.7，非关键帧采样率f为0.1；自适应帧间帧内多假设模式选择阈值TSSIM=0.7；搜索窗Winter=16，Wintra=8.

表1 不同采样率下各算法的PSNR对比

Table 1 Comparison of PSNR of different algorithm with diffe-rent sampling rates

实验序列重构算法PSNR/dBf=0.05f=0.1f=0.15foremanMRMH31.0632.9034.322SMHR31.6233.6535.19IMH32.8035.0736.56hallMRMH30.5532.0933.342SMHR31.1332.7534.01IMH33.0234.3635.05coastguardMRMH27.3828.5629.392SMHR27.7929.0429.93IMH28.5229.8730.73footballMRMH27.0728.8729.932SMHR27.4629.2430.28IMH28.0129.5830.54soccerMRMH28.6631.2432.862SMHR29.1331.8733.51IMH30.1132.6434.07

由表1可见，不同序列在非关键帧的采样率较低(0.05～0.15)的情况下，文中提出的迭代多假设算法(IMH)相比MRMH与2SMHR算法重构质量普遍提升了0.5～1.5 dB；但是，对比运动比较缓慢的序列(hall序列)与运动比较剧烈的视频序列(football，soccer)发现，运动比较缓慢的序列重构质量提升更加明显，这是因为对于运动缓慢的序列，多假设的运动估计和运动补偿会更加精准.由图3显示的foreman局部放大图中可以看出对于运动程度较大的嘴唇周围部分可见2SMHR的块效应明显，而IMH算法在对foreman视频帧在像素域进行迭代预测后，能够有效消除块效应，提高重构质量.

图3 “foreman”第59帧重构效果(局部)

Fig.3 Reconstruction effect of the 59th frame of foreman sequence(partial)

3.2 IMH算法性能实验

利用实验仿真，对比了基于快速搜索的迭代多假设预测算法与全搜索的多假设预测算法的性能，FS表示全搜索(FS(32,32)表示搜索窗W=32)，“IS”表示文中的优化搜索，IS(R,r,s)表示初步搜索非对称十字形估计区域，如图2所示，其中R表示初步搜索窗水平方向半径，r表示十字重叠区域半径，s表示匹配假设块的稀疏搜索距离.

表2给出了soccer和football两个运动比较剧烈的序列的前129帧的实验结果，其中，时间表示重构时平均每帧所用时间，包括预测和重构过程.由表2可知，文中所提快速算法在保持重构性能的条件下，soccer和football序列重构时间明显下降，这是因为快速搜索方案由大范围稀疏搜索到小范围全搜索的模式，即通过大范围稀疏搜索摒弃与当前块并不相关的区域，然后通过小范围全搜索进行精确匹配，有效地降低了预测过程中匹配块搜索算法复杂度.这对于视频解码来说减少了许多不必要的负担.

表2 不同匹配块搜索方案重构时间复杂度及性能对比

3.3 与现有最优视频压缩感知算法性能对比分析

将本算法性能与现有最优的预测残差重构视频压缩感知算法(MH-BCS-SPL[11]，MS-wEnet[7]， Up-Se-AWEN-HHP[15])做对比实验，仿真结果如表3所示.实验中使用和对比文献中完全相同的条件，标准30Hz CIF格式序列前89帧的亮度分量进行实验.在采样端，用正交高斯随机观测矩阵分块采样，非重叠块分块大小B=16，序列分组GOP=8，关键帧采样率0.7，非关键帧采样率0.1～0.5.在重构端，关键帧使用MH-BCS-SPL算法独立重构，非关键帧假设块搜索窗W=15，非关键的预测残差信号使用BCS-SPL-DDWT[13]算法重构.

在本算法中，像素域重叠块分块大小b=8；像素域预测多假设块个数n=8；自适应帧间帧内多假设模式选择阈值TSSIM=0.7，搜索窗.Winter=16,Wintra=8.

表3 不同序列前89帧各算法重构平均PSNR

从表3中可以看出，IMH与MH-BCS-SPL、MS-wEnet、Up-Se-AWEN-HHP算法相比，其重构质量均有明显提升，foreman、hall、coastguard、mother-daughter在非关键帧为0.1的低采样率情况下提高了1～3.5 dB，尤其是对于背景运动较简单的hall序列，由于其纹理信息较多的图像特征，IMH算法与Up-Se-AWEN-HHP算法相比，提升更为明显，从表3中发现，随着非关键帧采样率的提升，IMH与Up-Se-AWEN-HHP的重构性能差距越来越小.这是因为在高采样率时，视频帧已经被高质量重构，无很明显的块效应，此时在像素域进行迭代多假设预测性能的提升就不太明显了.

4 结论

在基于多参考帧的多假设预测残差重构算法的基础上提出了基于快速搜索的迭代多假设预测重构算法(IMH)，即在观测域多假设残差重构的基础上，在像素域基于重叠分块进行增强的多假设预测残差重构循环迭代，逐步消除块效应，提升视频重构质量，并且提出了相关的自适应假设块模式选择.通过对比仿真实验可知，IMH算法相对于其他视频压缩感知重构算法性能都有所提升，在较低采样率时性能提升更为明显；与现有最优视频压缩感知算法Up-Se-AWEN-HHP相比，IMH算法最大提升PSNR可达2.1dB；另外，对于快速运动序列，需要大范围搜索才能得到更好的假设块，在这种情况下，IMH算法有效地降低了搜索算法的复杂度.这些实验结果表明了文中提出的IMH算法具有更加优越的视频压缩重构性能.

[1] DONOHO D L. Compressed sensing [J].IEEE Transactions on Information Theory,2006,52(4):1289- 1306.

[4] KANG L W,et al.Distributed compressive video sensing [C]∥IEEE International Conference on Acoustics,Speech & Signal Processing.Taipei:IEEE Computer Socie-ty,2009:1169- 1172.

[5] CHEN C,TRAMEL E W,Fowler J E.Compressed-sensing recovery of images and video using multihypothesis predictions [C]∥Signals,Systems and Computers.Pacific Grove:IEEE,2011:1193- 1198.

[6] ZHU J,CAO N,Meng Y.Adaptive multihypothesis prediction algorithm for distributed compressive video sensing [J].International Journal of Distributed Sensor Networks,2013,2013(7):718- 720.

[7] JIAM C,CHEN Y,DONG Q,et al.An elastic net-based hybrid hypothesis method for compressed video sensing [J].Multimedia Tools & Applications,2013,74(6):1- 24.

[8] AZGHANI M,KARIMI M,MARVASTI F.Multi-hypothesis compressed video sensing technique [J].IEEE Transactions on Circuits & Systems for Video Technology,2015,26(4):627- 635.

[9] 杨春玲，欧伟枫.视频压缩感知中基于多参考帧的最优多假设预测算法研究 [J].华南理工大学学报(自然科学版)，2016,44(1):1- 8.

YANG Chun-ling,OU Wei-feng.Multi-reference frames-based optimal multi-hypothesis prediction algorithm for compressed video sensing [J].Journal of South China University of Technology (Natural Science Edition),2016,44(1):1- 8.

[10] GAN L.Block compressed sensing of natural images [C]∥International Conference on Digital Signal Processing. Wales：IEEE,2007:403- 406.

[11] OU W F,YANG C L,Li W H,et al.A two-stage multi-hypothesis reconstruction scheme in compressed video sensing [C]∥IEEE International Conference on Image Processing.Phoenix：IEEE,2016:2494- 2498.

[12] FOWLER J E,MUN S,TRAMEL E W.Block-based compressed sensing of images and video [J].Foundations & Trends & in Signal Processing,2012,4:297- 416.

[13] MUN S,FOWLER J E.Block compressed sensing of ima-ges using directional transforms [C]∥Proceedings of the 16th IEEE International Conference On Image Processing.Cairo：IEEE，2009:2985- 2988.

[14] PAN Z,KWONG S,XU L,et al.Predictive and distribution-oriented fast motion estimation for H.264/AVC [J].Journal of Real-Time Image Processing,2012,9(4):597- 607.

[15] KUO Y,WU K,CHEN J.A scheme for distributed compressed video sensing based on hypothesis set optimization techniques [J].Multidimensional Systems & Signal Processing,2017:28(1):129- 148.

FastSearching-BasedIterativeMulti-HypothesisAlgorithmAppliedtoCompressedVideoSensing

YANGChun-lingXIONGGuang-yinDAIChao

(School of Electronic and Information Engineering, South China University of Technology, Guangzhou 510640, Guangdong, China)

As the two-stage multi-hypothesis reconstruction (2sMHR) for the prediction in both measurement and pixel domains is of low reconstruction quality at low subrate as well as low prediction accuracy and high computational complexity for fast movement sequences, on the basis of 2sMHR scheme, a novel iterative multi-hypothesis (IMH) prediction reconstruction algorithm utilizing fast searching technology is proposed. This algorithm utilizes the flexibility of block partition in pixel domain to conduct overlapping block-based iterative multi-hypothesis prediction, and adopts the scheme of jointing cross-shaped and regional searching to lessen matching complexity in large-range searching for fast sequences. In addition, by utilizing the space correlation in images, an adaptive interframe/intraframe hypothesis-block selecting scheme is presented. In comparison with the existing algorithms, the proposed IMH prediction reconstruction algorithm suppresses the prediction block effect, reduces the computational complexity for large-range searching and improves the video reconstruction quality.

compressed video sensing; multi-hypothesis prediction; hypothesis block; pixel domain; iteration prediction; prediction accuracy; time complexity

2016- 07- 22

国家自然科学基金资助项目(61471173);广东省自然科学基金资助项目(2016A030313455)

*Foundationitems: Supported by the National Natural Science Foundation of China(61471173) and the Natural Science Foundation of Guangdong Province(2016A030313455)

杨春玲(1970-)，女，博士，教授，主要从事图像/视频压缩研究.E-mail:eeclyang@scut.edu.cn

1000- 565X(2017)07- 0107- 06

TP 919.8

10.3969/j.issn.1000-565X.2017.07.015