ABSTRACT

In the traditional distributed video compressed sensing system, low sampling rate in the encoding side often leads to the problem that the reconstruction in the decoding side is unsatisfactory. In order to solve this shortcoming, a distributed video compressed sensing reconstruction algorithm combining the optimal linear estimation with the multiple hypotheses prediction is proposed, which takes into account the spatial-temporal correlation between video frames and the different block features of different image blocks in the video frame. The block-based compressed sensing method is used to measure the video frames at the encoding side. At the decoding side, three kinds of mechanisms are added, such as similarity discrimination, measurement value supplement and smooth discrimination, which can be used to classify the blocks of non-critical frame. Then according to the classification results, the different blocks of non-critical frame use different measurement supplement strategies and can be reconstructed by different reconstruction strategies with an aim to improve the reconstruction quality. Experimental results on the public commonly used video test sequences demonstrate that the proposed algorithm outperforms the traditional multiple hypotheses predictive reconstruction algorithm by 2~3 dB (PSNR), by 4~5 dB in the case of the sampling rate below 0.2 especially.

Keywords:Distributed Video Compressed Sensing, Correlation, Multiple Hypotheses, Optimal Linear Estimation, Recovery

一种最佳线性估计与多假设结合的 分布式视频压缩感知重构算法

才争野^1,2，吕巨建^1,2，赵慧民^1,2，徐小平¹，宋智华¹

¹广东技术师范学院电子与信息学院，广东 广州

²广州数字内容处理及其安全性技术重点实验室，广东 广州

收稿日期：2018年4月13日；录用日期：2018年4月26日；发布日期：2018年5月3日

摘 要

针对分布式视频压缩感知系统存在编码端的低采样率易导致解码端重构效果不理想的问题，综合考虑视频帧间的时空相关性以及帧内不同图像块所具有的不同块特征，提出了一种最佳线性估计与多假设预测相结合的分布式视频压缩感知重构算法。算法在编码端采用分块压缩感知进行随机测量，在解码端增加了相似判别、测量值补充以及平滑判别三种机制。通过此三种机制对非关键帧块进行细化分类，并根据分类结果对不同的图像块采用不同的测量值补充及重构策略，进而提高重构质量。在标准视频序列集上的仿真实验结果表明，本文提出的算法重构视频信号的峰值信噪比(PSNR)比传统的多假设预测重构算法平均高出2~3 dB，尤其在编码端测量率低于0.2的情况下，PSNR高出4~5 dB。

关键词 :分布式视频压缩感知，相关性，多假设预测，最佳线性估计，重构

Copyright © 2018 by authors and Hans Publishers Inc.

This work is licensed under the Creative Commons Attribution International License (CC BY).

http://creativecommons.org/licenses/by/4.0/

1. 引言

通信技术的不断进步推动了多媒体技术的迅速发展，无线视频监控系统、移动可视电话和无线多媒体传感器网络等视频应用得到了广泛的应用。这些应用都具有共同的特点，即编码端计算和存储能力有限，但解码端计算资源丰富，而传统的视频编解码标准下的编码端对计算复杂度的要求较高，这使得传统的视频编码标准已经不再适合此类应用。2009年T.T. DO等人首次把分布式视频编码(Distributed Video Coding, DVC)理论 [1] [2] [3] [4] 与压缩感知理论[4]相结合提出了分布式视频压缩感知(Distributed video Compressed Sensing, DISCOS)框架 [5] 。由于DISCOS在编码端引入了压缩感知技术，因此只需少量的测量值就可在解码端高概率重构出原信号，其将编码端的大量计算转移到了解码端，使得视频编解码系统具备了较低复杂度的编码特性，很好的适应了这些新兴的视频应用。目前，分布式视频压缩感知的研究主要集中在两方面：一是如何权衡编码端的计算复杂度与编码效率；二是如何有效利用帧间的相关信息提高重构算法效率和重构质量。重构算法的设计一直是分布式视频压缩感知研究的一个重点，算法的好坏决定着重构质量的高低。传统的单帧图像重构算法如OMP、GPSR、StOMP、SpaRSA等 [6] [7] [8] 在视频重构中没有考虑视频帧间的时空相关性以及视频帧所包含的不同局部特征，如何在重构算法中有效的利用这些特性成为了分布式视频压缩感知的一个研究热点 [9] [10] 。文献 [5] 将传统的多假设预测(Multiple Hypotheses, MH)运动估计思想引入到了重构算法中，在解码端，其首先对当前帧进行基于块的多假设预测生成边信息，然后利用边信息的测量值与CS帧的测量值进行全局的残差重构。E.W. Tramel等人基于Tikhonov正则化提出了分块压缩感知(Block Compressed Sensing, BCS)平滑投影Landweber (MH-BCS-SPL)算法 [11] ，在该算法中，由于加入了Tikhonov正则化项，因此多假设预测的权值分配更加的准确，图像的重构质量也有了提高。文献 [12] 提出了一种基于MH的分布式视频压缩感知方案，在该方案中，关键帧与非关键帧的边信息均由多假设预测生成，不同的是关键帧采用的是帧内多假设预测，而非关键帧采用的是帧间多假设预测。上述方案在重构中均运用了多假设预测思想，但都忽略了视频帧内各块所具有的不同块特征(平滑、纹理等)。文献 [13] 根据视频帧内不同图像块具有的不同块特征，提出了一种对图像进行快速重构的最佳线性估计(Optional Linear Estimation, OLE)算法。该算法在编码端针对不同特征的图像块采用了自适应的CS随机测量，并在解码端对各块采用对应的线性估计器进行快速线性恢复。对于没有过多纹理细节的图像该算法有着较好的重构质量。OLE在重构过程中只利用了图像的局部特征，并没有利用到帧间的时空相关性，所以影响了解码端的重构质量。本文综合考虑视频帧间的时空相关性以及帧内不同图像块所具有的不同块特征，提出了一种最佳线性估计与多假设预测相结合的OLE-MH (Optional Linear Estimation-Multiple Hypotheses)重构算法。算法在编码端采用分块压缩感知 [14] 进行测量，在解码端增加了相似判别、测量值补充以及平滑判别三种不同的机制对图像块进行分类处理，根据分类结果对不同的图像块采用不同的重构策略。这里，相似判别合理的利用了视频帧间的时间相关性，测量值补充进一步提高了图像块的重构质量，而平滑判别的加入充分的利用了帧内的不同局部特征。仿真实验结果表明，本文提出的算法相较于传统的MH-BCS-SPL算法以及OLE算法在编码端测量率较低的情况下就能以较高的质量进行重构。

2. 相关知识

2.1. 多假设预测方法

多假设预测重构很好的利用了视频帧间的时空相关性，其基本原理如图1所示。MH预测的基本思想是利用参考帧中搜索空间内的所有假设块的最佳线性组合来近似当前块。文献 [9] 提出了一种基于Tikhonov正则化的多假设预测求解模型，描述如下：

${\widehat{w}}_i=\arg \underset{w_i}{\min }{\Vert y_i^{cs}-\Phi H_i{w}_i\Vert }_2+\lambda {\Vert \Gamma w_i\Vert }_2$ (1)

其中， $H_i$ 是参考帧中对应于当前块 $$ 位置搜索空间内维假设块矩阵， $H_i$ 矩阵中的各列为假设块的列向量形式，B为块尺寸大小，K为搜索空间中总共的假设块数量； ${\widehat{w}}_i$ 为 $K\times 1$ 维列向量的最佳线性组

图1. 空域多假设预测示意图

合系数；λ为拉格朗日参数； $\Gamma$ 为Tikhonov对角矩阵，形式如下：

$\Gamma =\left[\begin{array}{ccc}{\Vert y_i^{cs}-\Phi h_1\Vert }_2& & 0\\ & \ddots & \\ 0& & {\Vert y_i^{cs}-\Phi h_k\Vert }_2\end{array}\right]$ (2)

其中， $h_1,h_2,\cdots ,h_k$ 为 $H_i$ 矩阵中的各列，代表各个假设块。式(1)可以直接由下面的闭式解求得：

${\widehat{w}}_i={\left[{\left(\Phi H_i\right)}^{\text{T}}\left(\Phi H_i\right)+\lambda {\Gamma }^{\text{T}}\Gamma \right]}^{-1}{\left(\Phi H_i\right)}^{\text{T}}{y}_i^{cs}$ (3)

为了提高预测精度，本文对 $H_i$ 矩阵做了优化处理，即为了避免那些与当前块不相似的假设块对 ${\widehat{w}}_i$ 权重的干扰，在 $H_i$ 矩阵中只选择与当前块相似的C列重组合成新的假设矩阵 $H_i^{opt}$ ，将 $H_i^{opt}$ 代入式(3)后形式如下：

${\widehat{w}}_i^{opt}={\left[{\left(\Phi H_i^{opt}\right)}^{\text{T}}\left(\Phi H_i^{opt}\right)+\lambda {\Gamma }^{\text{T}}\Gamma \right]}^{-1}{\left(\Phi H_i^{opt}\right)}^{\text{T}}{y}_i^{cs}$ (4)

2.2. 最佳线性估计方法

最佳线性估计方法能够以线性方式对图像进行快速恢复，其基本原理是先利用图像块像素间存在的相关性构造出线性算子，再利用线性算子通过观测值 $y$ 对原始帧进行线性估计。其相较于传统分布式视频压缩感知重建过程中的非线性最优化迭代过程具有较低的计算复杂度，文献 [11] 给出了最佳线性估计方法的求解模型：

$L=R_{xx}{\Phi }_B^{\mathrm{T}}{\left({\Phi }_B{R}_{xx}{\Phi }_B^{\mathrm{T}}\right)}^{-1}$ (5)

$\widehat{x}=Ly$ (6)

其中， $L$ 为最佳线性估计器， $R_{xx}$ 为自相关函数矩阵，其形式如下：

$R_{xx}=E\left[x{x}^{\mathrm{T}}\right]=\left[\begin{array}{cccc}E\left(x_1{x}_1\right)& E\left(x_1{x}_2\right)& \cdots & E\left(x_1{x}_{B^2}\right)\\ E\left(x_2{x}_1\right)& E\left(x_2{x}_2\right)& \cdots & E\left(x_2{x}_{B^2}\right)\\ ⋮& ⋮& \ddots & ⋮\\ E\left(x_{B^2}{x}_1\right)& E\left(x_{B^2}{x}_2\right)& \cdots & E\left(x_{B^2}{x}_{B^2}\right)\end{array}\right]$ (7)

$R_{xx}$ 矩阵的元素可根据文献 [15] 由下式进行估计：

$R_{xx}\left(p,q\right)=E\left[x_p{x}_q\right]={\rho }^{\mu }$ (8)

其中，

$\mu =\sqrt{{\left(n_1-n_2\right)}^2+{\left(m_1-m_2\right)}^2}$ (9)

这里， $\left(n_1,m_1\right)$ 为像素 $x_p$ 的空间位置坐标， $\left(n_2,m_2\right)$ 为像素 $x_q$ 的空间位置坐标；μ为 $x_p$ 与 $x_q$ 的欧几里德距离；ρ为相关系数，本文中 $\rho =0.999$ ；3.1节仿真实验中的结果表明，对于平滑图像的重构，最佳线性估计方法相较于另外四种非线性重构算法有着较好的重构表现，实验结果如表1所示。

3. 最佳线性估计与多假设预测相结合的OLE-MH重构算法

本文提出的基于最佳线性估计与多假设预测相结合的分布式视频压缩感知系统框架如图2所示。图2(a)

表1. 几种算法对平滑块重构的PSNR值及时间(单位：dB/s)

图2. 提出的OLE-MH重构算法系统框架

为编码端，如图所示视频信号被分为关键帧与非关键帧，每帧均进行互不重叠的 $B\times B$ 分块处理。对关键帧块采用较高测量率的测量矩阵 ${\Phi }_B^{Key}$ 进行测量，对非关键帧块则用较低测量率的 ${\Phi }_B^{CS}$ 进行测量，即 $y_{j,t-1}^{Key}={\Phi }_B^{Key}{x}_{j,t-1}^{Key}$ 与 $y_{i,t}^{CS}={\Phi }_B^{CS}{x}_{i,t}^{CS}$ ，其中， $x_{j,t-1}^{Key}$ 表示t-1时刻关键帧中第j个宏块的列向量形式， $x_{i,t}^{CS}$ 表示t时刻非关键帧中第i个宏块的列向量形式。解码端如图2(b)所示，首先对相邻的关键帧采用BCS-SPL-DDWT算法进行重构，然后在相邻关键帧中对应于非关键帧当前块 $x_i$ 位置的搜索窗内以同样 $B\times B$ 的块大小采用全搜索方式生成假设块矩阵 $H_i$ ， $H_i$ 中的每列均为假设块的列向量形式。生成 $H_i$ 后利用测量矩阵 ${\Phi }_B^{Key}$ 对其进行测量，得到测量值矩阵 $Q_i^{Key}$ ，计算公式如下：

$Q_i^{Key}={\Phi }_B^{Key}\times H_i$ (10)

在本文中，测量矩阵 ${\Phi }_B^{Key}$ 的前K (K为 ${\Phi }_B^{CS}$ 的行数)行设置成与 ${\Phi }_B^{CS}$ 相同，这样做有助于后面的相似判别与测量值补充。得到 $Q_i^{Key}$ 后将其前K行进行截取，得到的矩阵记为 $Q_i^{CS}$ ，计算当前块测量值 $y_i^{CS}$ 与矩阵 $Q_i^{CS}$ 中每列的欧氏距离，得到距离向量 $D_i$ 。设置一个阈值 $T_1$ (一般设置在1~3之间)来衡量当前块与假设块是否相似。当距离向量 $D_i$ 中的最小值 $d_{D_i}>T_1$ ，表示此搜索窗中没有与当前块相似的块，对该种情况，采用多假设预测方法对当前块进行重构。当距离向量 $D_i$ 中的最小值 $d_{D_i}\le T_1$ ，则表示此最小值所对应的假设块与当前块最为相似。找到相似块后，判断此相似块在关键帧中是否与当前块处于同样的位置，如果在同样的位置，则直接利用关键帧中此块的测量值 $y_i^{Key}$ 对 $y_i^{Key}$ 进行测量值补充，如果不在同样的位置，则利用此相似块的测量值对 $y_i^{CS}$ 进行测量值补充，进行测量值补充可以获得更好的重构效果，其示意图如图3所示，从图中可以看出，测量值补充是把关键帧中相似块的一部分测量值补充到非关键帧当前块的测量值中。测量值补充后，利用当前块与相似块具有相似的块特征的特性，通过计算相似假设块的均方差σ来判定当前块是否平滑，计算公式如下：

$\sigma =\frac{{\Vert \left(h_i^{\text{current}}-{\overline{h}}_i^{\text{current}}\right)\Vert }_2}{\sqrt{N}}$ (11)

其中， $N=B^2$ ； $h_i^{\text{current}}$ 为 $H_i$ 中与当前块最相似的假设块的列向量形式； ${\overline{h}}_i^{\text{current}}$ 为其平均值。如果 $\sigma \le T_2$ (阈值 $T_2$ 一般设置在30~35之间)那么判定当前块为平滑块，针对平滑块采用最佳线性估计方法进行重构。如果 $\sigma >T_2$ 则判定当前块为非平滑块，对其采用MH进行重构。所有图像块均重构完成后，对它们进行重组，形成对当前非关键帧的重构帧 ${\tilde{x}}_i^{CS}$ 。

4. 实验结果与分析

4.1. 最佳线性估计方法仿真结果

为验证最佳线性估计方法对平滑图像重构的质量，本文针对Cameraman图像分别提取其左上角以及右上角大小均为 $128\times 128$ 的平滑区域作为实验图像，并采用最佳线性估计方法进行重构测试，与其进行

图3. 测量值补充示意图

对比的重构算法有BCS-SPL-DDWT [16] [17] [18] 、BCS-SPL-DCT [17]、BCS-TV [18]，块尺寸大小为 $32\times 32$ ，测试结果均为独立运行十次取平均值，具体结果如表1所示。本文所有的测试均在Intel酷睿i7双核3.6 GHz、64位Windows7操作系统以及Matlab2015b平台上运行。从表1可以看出最佳线性估计对平滑块的重构不论是从重构效果还是从重构时间上都整体优于其他算法，而且最佳线性估计在低测量率的情况下对平滑块仍然有着较好的重构效果。

4.2. 本文提出算法仿真结果

为了验证提出的方法，本文选取了三个标准CIF视频序列Akiyo、Mother-daughter以及News (http://trace.eas.asu.edu/yuv/)进行仿真实现，并与传统的MH-BCS-SPL算法 [9] 以及最佳线性估计方法 [11] 进行对比，这里三个算法的关键帧均采用BCS-SPL-DDWT算法进行重构，实验数据均为对视频序列取前50帧进行测试的结果。实验参数设置如下：视频格式为 $352\times 288$ 大小的视频序列，图像组GOP设为2，关键帧采样率为0.7，块尺寸为32，搜索窗口大小w为10。表2显示了三种重构算法在三个不同的视频序列上以不同的采样率进行重构的PSNR值对比，从表中可以看到，由于在重构过程中利用了相似性及平滑判别，本文提出的OLE-MH算法在重构质量上相较于另外两种方法均有很大的提高，尤其是在低测量率的情况下由于测量值补充的原因，OLE-MH有着明显的优势。图4显示了三种重构算法在不同测量率下平均重构的PSNR曲线图，通过观察曲线图可以明显的看出，本文提出的OLE-MH算法在重构效果上整体优于其他两种算法，而且还可看出测量率的大小对本文提出的算法影响不大，尤其是当非关键帧测量率越小时，本文提出的算法对图像重建质量的改善越大，因此非常适合那些在编码端测量率较低的视频编解码设备。

图5显示了三个不同的视频序列在三种重构算法上的重建效果对比，仿真实验均选取视频序列的第22帧(非关键帧)作为对比，关键帧测量率为0.7，非关键帧测量率为0.1。对比三种重构方法的重构图像可以看出，本文提出的OLE-MH算法能够较好地改善图像的重构质量。

表2. 几种算法对平滑块重构的PSNR值及时间(单位：dB/s)

5. 结束语

本文结合最佳线性估计与多假设预测方法，提出了一种分布式视频压缩感知重构算法。算法通过整

图4. 在不同测量率下平均重构PSNR曲线图

图5. 三种视频序列在不同重构算法上的重建效果对比

合相似判别、测量值补充和平滑判别三种机制，实现了非关键帧图像块的差别化处理和优化重构，充分的利用了视频帧间的时空相关性以及帧内图像块间的不同块特征特性。实验结果表明，相较于传统的MH-BCS-SPL算法以及OLE算法，本文提出的算法在重构视频图像的PSNR上有了明显的提升，尤其是当编码端测量率较低或视频图像平滑区域较多时，算法的优越性更为明显。

文章引用

才争野,吕巨建,赵慧民,徐小平,宋智华. 一种最佳线性估计与多假设结合的分布式视频压缩感知重构算法
Distributed Video Compressed Sensing Reconstruction Algorithm Combining Optimal Linear Estimation with Multiple Hypotheses[J]. 计算机科学与应用, 2018, 08(05): 601-610. https://doi.org/10.12677/CSA.2018.85068

参考文献