李 然 干宗良 崔子冠 武明虎 朱秀昌



联合时空特征的视频分块压缩感知重构

李 然 干宗良 崔子冠 武明虎 朱秀昌*

(南京邮电大学江苏省图像处理与图像通信重点实验室 南京 210003)

为了提高视频压缩感知(CS)重构算法的率失真性能，该文提出利用视频的时空特征进行联合重构。为了不引入过多的复杂度，采集端以固定采样率对帧内各块进行测量；重构端则在最小全变差(TV)重构模型的基础上，分别加入利用时空自回归(AR)模型和多假设(MH)模型所形成的正则化项，以提高预测-残差重构的性能。另外，考虑到视频源的统计特性在时空域中是动态变化的，讨论了5种不同的帧间预测模式对重构精度和重构计算复杂度的影响。仿真实验表明，所提出的重构算法能够以一定的计算复杂度为代价有效地改善视频重构质量，且在关键帧采样率高于非关键帧的情形下，帧间预测模式的改善也可一定程度上提高视频重构质量。

压缩感知；视频重构；最小全变差；时空自回归；多假设；预测-残差重构

1 引言

压缩感知(Compressed Sensing, CS)旨在以欠奈奎斯特(Sub-Nyquist)速率采样信号，以降维方式实现在采样信号的同时压缩信号[1]。该理论表明，具有一定结构性的信号(例如，变换系数是稀疏或可压缩的)可从少量随机测量值中以极大概率无失真恢复原始信号[2,3]。将CS理论应用到图像和视频信号采集上可大大减少传感器的数量，从而实现低成本、低能耗和低计算复杂度的数据采集。

考虑到计算复杂度，视频压缩感知采集端应尽量简单。本文方法仍以固定采样率测量帧内各块，仅在接受端加入适当的正则化项来提高预测精度，从而改善预测-残差重构的率失真性能。根据视频信号的时空特征，分别将基于像素的时空AR模型和基于块的MH模型与全变差(Total Variation, TV)模型相结合，形成两种不同的联合时空特征的预测-残差重构模型，这两种模型均能有效利用视频信号的时间和空间相关性，提高视频重构质量。另外，由于帧间统计相关特性随时间变化，本文也讨论了5种帧间预测模式对视频重构质量和计算复杂度的影响。仿真实验表明，本文提出的两种算法均能以一定的计算复杂度为代价换取率失真性能的提高，而帧间预测模式的改善进一步提高了视频重构的质量。

2 图像分块压缩感知的全局重构模型

文献[7]提出的BCS首先将I×I个像素的图像分成个尺寸为×的块，第个块的列向量形式记为，然后使用相同的高斯随机测量矩阵对进行测量，得到相应长度为M的观测值向量，上述过程可记为

由式(1)可看出，观测值向量并不是对整幅图像作CS测量得到的，而是由各图像块相应的观测值向量按列组合而成，因此接收端无法一次重构整幅图像，而是独立地重构各图像块。这种局部重构方式割裂了图像的空间特征，导致了块效应等问题。为了克服该缺陷，文献[18]通过引入排序算子得到式(1)的等价形式如式(2)：

其中(,)是图像的像素坐标，1为垂直方向差分1=(,)–(–1,),2为水平方向差分2=(,) –(,–1)。因此，利用图像梯度域的稀疏性，图像CS重构问题可采用最小TV模型求解。

3 联合时空特征的视频重构

在重构视频信号时，除了考虑帧内的空间相关性外，帧间的时间相关性也应被充分利用。时空AR模型能够很好地描述时空域像素之间的相关性，在帧率提升算法(Frame Rate Up-Conversion, FRUC)和边信息(Side Information, SI)估计算法中经常使用[19,20]；MH模型充分利用了帧间块与块的结构相似性，应用到传统视频编码的运动补偿(Motion Compensation, MC)中获得了很好的效果[21]。本文将上述两种描述时间相关特征的模型分别与描述空间相关特征的TV模型相结合，提出了两种联合时空特征的预测-残差重构模型。

3.1 时空AR模型与TV模型联合重构

将时空AR模型与TV模型结合，可构造出式(5)所示的当前帧预测模型：

步骤1 初始化：令(0)=SI；设定初始迭代= 1和最大迭代次数maxiter。

步骤2 固定(k)，求解：

该式具有闭式解如式(7)：

其中为在邻近帧相对应位置处的半径为1的搜索窗，为搜索窗中的候选匹配块，为权衡因子。由于中包含有图像的全部信息，所以在式(8)中第1项较为重要，本文中值取为0.3。

该式的等价形式为

其中

可使用TVAL3工具箱[23]求解式(10)，需要注意的是，在该工具箱中需要设定的参数反比于正则化参数。

其中为当前帧的残差帧。

3.2 MH模型与TV模型联合重构

如图2所示，在MH模型中，当前帧的每一个块B,m可由邻近帧相对应位置处的半径为2的搜索窗内所有候选块线性加权估计。与时空AR模型类似，MH模型也可分为P帧情形(图2(a))和B帧情形(图2(b))。

将MH模型与TV模型结合，可构造出如式(13)所示的当前帧预测模型：

图2 MH模型

步骤1 初始化：令(0)=SI；设定初始迭代= 1和最大迭代次数maxiter。

该式具有闭式解如式(16)：

与时空AR模型相似，式(17)仍可等价为与式(10)相同的形式并采用TVAL3工具箱求解，不再赘述。

考虑计算复杂度，最大迭代次数maxiter设为3。与时空AR模型相同，重构残差使用BCS-SPL- DDWT算法。

3.3 帧间预测模式

在预测-残差重构模型中，视频信号首先会被划分为若干个长度为的图片组(Group Of Pictures, GOP)，接着对它们分别采样和重构，最后合并成整个视频信号。每组GOP均由关键帧和非关键帧组成：关键帧以较高的采样率进行测量，而非关键帧则以较低的采样率测量。由于关键帧采样率较高，因此可采用静止图像CS算法进行重构，也称之为I帧。然而，低采样率的非关键帧必须通过参考相邻帧才可达到与关键帧可比的重构质量：若仅参考前一重构帧，则称之P帧；若参考前后两重构帧，则称之B帧。由于视频源的统计特性在时空域中是动态变化的，所以不同帧间预测模式会对视频重构质量造成一定影响。文献[14]提出了两种单向帧间预测模型(如图3(a), 3(b)所示)，虽然能够满足实时的视频采集和重构，但并未引入B帧。适当地插入B帧，虽然会使视频系统丧失实时性，但也能够提升一定的重构精度。文献[24]讨论的多视点视频的预测模式提出3种加入B帧的帧间预测模式(以= 4为例)，如图3(c), 3(d), 3(e)所示。

图3 5种帧间预测模式(方框右上角数字为预测顺序)

双向预测模式在连续两个I帧中全部插入B帧，该模式充分利用了前后帧的相关特性，能够提升一定的重构精度，但是B帧的重构计算复杂度过高，为了适当地减少计算复杂度，将其中两个B帧替换成P帧，形成混合预测模式。在混合预测模式1中，考虑到采样率较高的I帧，其重构质量较好，所以B帧参考前后I帧进行重构。然而，考虑到B帧与I帧间隔较远，时间相关性减弱，所以混合预测模式2中的B帧使用前后P帧进行重构。5种帧间预测模式的优劣，将在第4.2节结合实验数据进行分析。

4 实验结果与分析

采用3组格式为CIF的标准视频序列Foreman, Mobile和Football的前21帧(GOP的长度= 4，共5组GOP)分别测试本文提出的算法和帧间预测模式的性能。每个GOP的关键帧(I帧)采用文献[10]提出的BCS框架下基于MH预测的SPL(MH-BCS- SPL)算法进行独立帧内重构；对于非关键帧，采用3种对比算法与本文算法进行比较，它们分别是文献[13]提出的分布式压缩视频感知(DIStributed Compressed Video Sensing, DISCVS)框架下的重构算法，文献[14]提出的BCS框架下基于MC的SPL (MC-BCS-SPL)算法和文献[15]提出的多假设预测-残差重构(Multi-Hypothesis Prediction-Residual Reconstruction, MHPR)算法。所有算法的分块尺寸=16，关键帧和非关键帧的采样率分别用K和NK表示，所提出的两种算法的参数设置如下：

(1)时空AR模型与TV模型联合重构(AR+ TV)：邻域半径= 1;,i的尺寸=/2；搜索窗半径1=；正则化因子和分别取0.2和0.1；TVAL3的设定参数取为28。

(2)MH模型与TV模型联合重构(MH+TV)：Bm的尺寸=；搜索窗半径2=；正则化因子和分别取0.1和0.01; TVAL3的设定参数取为28。

评价性能的指标分别为可反映客观质量的峰值信噪比(Peak Signal-Noise Ratio, PSNR)，可反映主观视觉质量的结构相似性指数[25](Structural SIMilarity, SSIM)和可反映计算复杂度的重构时间。实验的硬件平台为主频3.20 GHz的酷睿i5 CPU计算机，软件平台为Windows 7 64位操作系统和Matlab 7.6仿真实验软件。

4.1 本文算法的性能分析

4.2 帧间预测模式的性能分析

表2列出了各帧间预测模式下所有算法重构出不同视频序列的平均PSNR值，SSIM值和重构时间。表2表明当K与NK均取0.3时，各种预测模式重构视频质量相差无几，性能最好的双向预测模式的PSNR值仅比最差的单向预测模式1高了0.5 dB，这说明在关键帧与非关键帧采样率相同的情形下，通过改变帧间预测模式并不能有效地改善重构视频的质量，原因在于关键帧的重构质量较差，导致非关键帧无法依靠关键帧提高重构质量。当K= 0.7,NK= 0.3时，可看到重构视频序列的平均PSNR值和SSIM值均得到了大幅提高，且性能最好的双向预测模式的PSNR值比最差的单向预测模式1高出0.7~1.7 dB，这说明在关键帧采样率高于非关键帧的情形下，帧间预测模式的改善可提高视频重构质量。在所有预测模式中，可看出单向预测模式1的重构质量最差，但其计算复杂度低，所需的重构时间短；单向预测模式2的重构质量略优于单向预测模式1，但由于重构GOP组的中心帧时需要重构2次取平均，导致其重构时间最长；双向预测模式中的非关键帧均为B帧，因此其重构精度最高，但B帧过多使得其计算复杂度较高；与双向预测模式相比，混合预测模式1和混合预测模式2均缩短了一定的重构时间，但重构视频质量有所下降；比较混合预测模式1与混合预测模式2，对于运动较慢的视频序列Foreman和Mobile，其重构视频的质量基本相同，然而，对于包含快速运动的视频序列Football，混合预测模式2重构视频质量高于混合预测模式1，其PSNR增益为0.3 dB，这说明对于快速运动的视频序列，时间相关性更为重要。

图4 SK = 0.7, SNK = 0.3时，Foreman视频第2帧的重构结果(局部放大)

表1帧间预测模式为混合预测模式1时，不同采样率下各种视频重构算法的性能比较：PSNR(dB)/SSIM/重构时间(s)

重构算法SNK(SK = SNK) 0.10.30.5平均 Foreman DISCOS27.7/0.769/14.333.3/0.881/15.037.0/0.936/13.832.7/0.862/14.4 MC-BCS-SPL28.2/0.817/47.533.9/0.915/37.437.6/0.959/28.733.2/0.897/37.9 MHPR28.3/0.826/13.334.1/0.928/14.137.5/0.957/12.733.3/0.904/13.4 AR+TV28.6/0.831/49.034.8/0.934/54.738.3/0.965/57.033.9/0.910/53.6 MH+TV28.9/0.843/45.235.0/0.939/46.038.6/0.968/44.834.2/0.917/45.3 Mobile DISCOS16.5/0.303/10.221.5/0.639/13.126.4/0.819/13.821.5/0.587/12.4 MC-BCS-SPL17.4/0.395/40.022.8/0.735/28.427.3/0.866/25.822.5/0.665/31.4 MHPR17.2/0.389/8.722.9/0.736/12.227.3/0.874/11.422.5/0.666/10.8 AR+TV17.8/0.420/47.423.2/0.745/55.827.9/0.887/61.423.0/0.684/54.9 MH+TV17.9/0.427/41.323.3/0.752/45.528.1/0.892/45.123.1/0.690/44.0 Football DISCOS21.3/0.485/12.026.7/0.737/13.630.7/0.859/13.426.2/0.694/13.0 MC-BCS-SPL22.1/0.568/54.128.1/0.815/42.932.6/0.918/31.027.6/0.767/42.7 MHPR22.3/0.593/9.728.2/0.818/11.631.5/0.903/11.027.3/0.771/10.8 AR+TV22.6/0.604/48.428.8/0.843/56.232.6/0.919/59.828.0/0.789/54.8 MH+TV22.8/0.616/42.929.1/0.852/45.533.1/0.926/44.928.3/0.798/44.4 重构算法SNK(SK =0.7) 0.10.30.5平均 Foreman DISCOS34.7/0.906/10.236.6/0.927/10.038.4/0.948/10.636.6/0.927/10.3 MC-BCS-SPL34.2/0.914/40.737.2/0.932/31.739.2/0.957/25.236.9/0.934/32.5 MHPR35.9/0.919/8.938.3/0.951/9.339.6/0.968/9.137.9/0.946/9.1 AR+TV36.2/0.939/44.538.9/0.964/49.440.5/0.974/53.938.5/0.959/49.3 MH+TV36.4/0.943/40.839.2/0.967/41.440.9/0.976/44.838.8/0.962/42.3 Mobile DISCOS25.0/0.796/14.827.5/0.853/14.929.3/0.887/15.427.3/0.845/18.4 MC-BCS-SPL24.5/0.796/47.728.2/0.896/33.830.4/0.921/29.027.7/0.871/36.8 MHPR25.3/0.822/12.828.4/0.903/12.930.5/0.933/13.028.1/0.886/12.9 AR+TV25.9/0.842/52.429.0/0.910/57.030.9/0.935/63.328.6/0.896/57.6 MH+TV26.0/0.848/46.829.2/0.916/48.431.1/0.940/47.628.8/0.901/47.6 Football DISCOS27.3/0.741/13.429.9/0.823/13.532.3/0.888/13.929.8/0.817/13.6 MC-BCS-SPL27.1/0.770/58.631.5/0.892/43.834.2/0.942/32.130.9/0.868/44.8 MHPR28.4/0.814/11.131.8/0.897/11.333.5/0.934/11.431.2/0.882/11.3 AR+TV28.8/0.824/47.332.2/0.911/53.934.3/0.942/59.431.8/0.892/53.5 MH+TV29.0/0.831/44.532.5/0.918/46.234.9/0.949/45.232.1/0.899/45.3

预测模式SK = SNK = 0.3 ForemanMobileFootball 单向预测模式134.1/0.917/27.222.7/0.717/25.028.1/0.806/27.7 单向预测模式234.3/0.921/78.022.8/0.722/74.828.5/0.821/83.9 双向预测模式34.6/0.925/44.223.3/0.746/41.028.6/0.823/46.1 混合预测模式134.2/0.919/33.422.7/0.721/31.028.2/0.813/34.0 混合预测模式234.3/0.920/32.522.7/0.721/30.428.4/0.820/33.4 预测模式SK =0.7, SNK = 0.3 ForemanMobileFootball 单向预测模式137.4/0.940/22.127.3/0.864/27.131.3/0.874/27.4 单向预测模式238.0/0.946/72.128.1/0.888/78.531.9/0.893/84.7 双向预测模式38.5/0.952/39.229.0/0.907/44.332.0/0.895/46.1 混合预测模式138.0/0.948/28.428.5/0.896/33.431.6/0.888/33.7 混合预测模式238.0/0.947/27.828.3/0.890/32.631.9/0.893/33.7

5 结束语

本文分别将基于像素的时空AR模型和基于块的MH模型与TV模型相结合，提出了两种联合时空特征的预测-残差视频压缩感知重构算法。为了避免不必要的计算复杂度，采集端以固定采样率测量帧内各块；重构端则在最小TV重构模型的基础上，通过分别加入利用时空AR模型与MH模型所形成的正则化项来提高视频的预测精度。另外，考虑到视频源的统计特性在时空域中动态变化的特点，讨论了5种不同的帧间预测模式对重构精度和重构计算复杂度的影响。仿真实验表明，本文提出的联合时空特征的重构算法能够以一定的计算复杂度为代价有效地改善视频重构质量，且在关键帧采样率高于非关键帧的情形下，帧间预测模式的改善也可一定程度上提高视频重构质量。

[1] Eldar Y C and Kutyniok G. Compressed Sensing: Theory and Applications[M]. Cambridge: Cambridge University Press, 2012: 1-5.

[2] Candes E J, Romberg J, and Tao T. Stable signal recovery from incomplete and inaccurate measurements[J]., 2006, 59(8): 1207-1223.

[3] Baraniuk R C, Cevher V, Duarte M F,.. Model-based compressive sensing[J]., 2010, 56(4): 1982-2001.

[4] Oechard G, Zhang J, Suo Y,.. Real time compressive sensing video reconstruction in hardware[J]., 2012, 2(3): 604-614.

[5] Holloway J, Sankaranarayanan A C, Veeraraghavan, A,.. Flutter shutter video camera for compressive of videos[C]. IEEE International Conference on Computational Photography, Seattle, WA, 2012: 1-9.

[6] Sankaranarayanan A C, Studer C, and Baraniuk R G. CS-MUVI: video compressive sensing for spatial-multiplexing cameras[C]. IEEE International Conference on Computational Photography, Seattle, WA, 2012: 1-10.

[7] Gan L. Block compressed sensing of natural images[C]. International Conference on Digital Signal Processing, Cardiff, UK, 2007: 403-406.

[8] Tramel E W. Distance-weighted regularization for compressed sensing video recovery and supervised hyperspectral classification[D]. [Ph.D. dissertation], Mississippi State University, 2012.

[9] Mun S and Fowler J E. Block compressed sensing of images using directional transforms[C]. International Conference on Image Processing, Cario, Egypt, 2009: 3021-3024.

[10] Chen C, Tramel E W, and Fowler J E. Compressed sensing recovery of images and video using multihypothesis predictions[C]. Conference Record of the 46th Asilomar Conference, Pracific Grove, CA, 2011: 1193-1198.

[11] Chartrand R. Nonconvex splitting for regularized low-rank + sparse decomposition[J]., 2012, 60(11): 5810-5819.

[12] Shu X and Ahuja N. Imaging via three-dimensional compressive sampling (3DCS)[C]. IEEE International Conference on Computer Vision, Barcelona, 2011: 439-446.

[13] Do T T, Chen Y, Nguyen D T,.. Distributed compressed video sensing[C]. IEEE International Conference on Image Processing, Cario, Egypt, 2009: 1393-1396.

[14] Mun S and Fowler J E. Residual reconstruction for block- based compressed sensing of video[C]. Data Compression Conference, Snowbird, UT, 2011: 183-192.

[15] Tramel E W and Fowler J E. Video compressed sensing with multihypothesis[C]. Data Compression Conference, Snowbird, UT, 2011: 193-202.

[16] 李星秀, 韦志辉. 基于局部自回归模型的压缩感知视频图像递归重建算法[J]. 电子学报, 2012, 40(9): 1795-1800.

Li Xing-xiu and Wei Zhi-hui. Compressed sensing video images recursive reconstruction algorithm based on local autoregressive model[J]., 2012, 40(9): 1795-1800.

[17] 练秋生, 田天, 陈书贞, 等. 基于变采样率的多假设预测分块视频压缩感知[J]. 电子与信息学报, 2013, 35(1): 203-208.

Lian Qiu-sheng, Tian Tian, Chen Shu-zhen,.. Block compressed sensing of video based on variable sampling rates and multihypothesis predictions[J].&, 2013, 35(1): 203-208.

[18] 李然, 干宗良, 朱秀昌. 基于分块压缩感知的图像全局重构模型[J]. 信号处理, 2012, 28(10): 1416-1422.

Li Ran, Gan Zong-liang, and Zhu Xiu-chang. A global reconstruction model of images using block compressed sensing[J]., 2012, 28(10): 1416-1422.

[19] Zhang Y, Zhao D, Ma S,.. A motion-aligned auto- regressive model for frame rate up conversion[J]., 2010, 19(5): 1248-1258.

[20] Zhang Y, Zhao D, Liu H,.. Side information generation with auto regressive model for low-delay distributed video coding[J].&, 2012, 23(1): 229-236.

[21] Sullivan G J. Multi-hypothesis motion compensation for low bit-rate video coding[C]. International Conference on Acoustics, Speech and Signal Processing, Minneapolis MN, 1993: 437-440.

[22] Elad M and Aharon M. Image denoising via sparse and redundant representations over learned dictionaries[J]., 2006, 15(12): 3736-3745.

[23] Li Cheng-bo, Yin W, and Zhang Yin. TV minimization by augmented Lagrangian and alternating direction algorithms [OL]. www.caam.rice.edu/~optimization/L1/ TVAL3/, 2010, 12.

[24] Merkle P, Smolic A, Muller K,.. Efficient prediction structures for multiview video coding[J]., 2007, 17(11): 1461-1473.

[25] Wang Z, Bovik A C, Sheikh H R,.. Image quality assessment: from error visibility to structural similarity[J]., 2004, 13(4): 600-611.

李 然： 男，1988年生，博士生，研究方向为图像处理与多媒体通信.

干宗良： 男，1979年生，讲师，研究方向为分布式视频编码、图像(视频)信号处理.

崔子冠： 男，1982年生，讲师，研究方向为视频编码.

武明虎： 男，1975年生，博士生，研究方向为分布式视频编码、多媒体通信、信息安全.

朱秀昌： 男，1947年生，教授，博士生导师，长期从事图像通信方面的科研和教学工作.

Block Compressed Sensing Reconstruction of Video Combined with Temporal-spatial Characteristics

Li Ran Gan Zong-liang Cui Zi-guan Wu Ming-hu Zhu Xiu-chang

(&,,210003,)

To improve the rate-distortion performance of video Compressed Sensing (CS) reconstruction, the temporal-spatial characteristics of video are used to jointly recover the video signal in this paper. At the collection terminal, each block in a single-frame is measured at the fixed sampling rates to advoid excessive complexity. At the reconstruction terminal, two regularization terms are respectively added to the minimum Total Variation (TV) reconstruction model to advance the performance of prediction-residual reconstruction, and the terms are constructed in terms of temporal-spatial Auto-Regressive (AR) model and Multiple Hypothesis (MH) model. In addition, considering that the statistics of video source are dynamically varying in spatial and temporal domain, it is discussed how the five different inter-prediction modes impact on precision and computational complexity of reconstruction. Simulation results show that the proposed algorithms effectively improve the quality of reconstructed video at the cost of the computational complexity , and the improvement of inter-prediction mode enhances reconstruction quality in some extent.

Compressed Sensing (CS); Video reconstruction; Minimum Total Variation (TV); Temporal-spatial Auto Regressive (AR); Multiple Hypothesis (MH); Prediction-residual reconstruction

TN911.73

A

1009-5896(2014)02-0285-08

10.3724/SP.J.1146.2013.00396

朱秀昌 zhuxc@njupt.edu.cn

2013-03-28收到，2013-07-18改回

国家自然科学基金(61071091, 61271240)，江苏省研究生创新计划(CXZZ12_0466, CXZZ11_0390)，江苏省高校自然科学研究项目(12KJB510019)，南京邮电大学校科研基金(NY212015)和湖北省教育厅科研重点项目(D20121408)资助课题