基于新型十字_菱形搜索的块匹配算法

毕业论文（设计） 2013届通信工程专业 0913071 班级题目菱形搜索运动估计算法研究及实现姓名学号指导教师职称二零一三年五月二十四日内容提要运动估计是视频压缩编码中的核心技术之一。

采用运动估计和运动补偿技术可以消除视频信号的时间冗余，从而提高编码效率；运动估计搜索算法是帧间编码的基础，常用的运动估计搜索算法采用在搜索区域内搜索最佳绝对误差和（SAD，Sum of Absolute Differences）匹配点来进行宏块匹配，获得宏块的运动矢量。

不同的搜索方法在搜索最佳SAD点上采用不同的搜索策略。

常见的快速搜索算法有三步法、新三步法、四步法、块梯度下降法以及菱形搜索算法等，本文主要研究菱形搜索运动估计算法并实现，首先阐述了课题的背景与意义和运动估计的研究现状，其次详细介绍了运动估计的原理以及典型块运动估计算法，分析它们的技术特点，然后重点介绍了菱形搜索算法，并在Visual C++ 6.0环境下编写程序代码将之实现，最后进行仿真得出实验结果。

关键词视频压缩;运动估计;块匹配;菱形搜索The Realization Of Diamond Searching MotionEstimation AlgorithmAuthor: Tutor:AbstractMotion estimation is the video compression coding technology of the core. Using motion estimation and motion compensation techniques can eliminate temporal redundancy of the video signal, thereby improving the encoding efficiency; motion estimation search algorithm based on inter-coded, the common motion estimation search algorithm of the search area to search the best absolute error and SAD (Sum of Absolute Differences) matching points to the macro block matching motion vector of the macro block obtained. Different search method searches for the best SAD point different search strategies. Common fast search algorithm has three steps, the new three-step method, four-step, block gradient descent and diamond search algorithm, etc. This paper studies the diamond search motion estimation algorithm and implementation, first describes the background and significance of the subject and motion estimation research status, followed by details of the motion estimation principle and the typical block motion estimation algorithm to analyze their technical characteristics, and then focuses on the diamond search algorithm, and the Visual C + + 6.0 environment to prepare the program code of the implementation, and finally the simulation The experimental results obtained.KeywordsVideo Compression Motion Estimation Block Matching Diamond Search目录内容提要................................. 错误!未定义书签。

基于起点预测的十字-六边形-菱形运动估计算法
王艳营
【期刊名称】《电子测量技术》
【年(卷),期】2009()5
【摘要】为了解决运动估计算法精度不高和运算量大的问题,有必要寻找一种有效的运动估计算法。

本文在讨论块运动类型的判定和起始搜索点预测的基础上,分析
了针对整像素的六边形-菱形(HDSP)的搜索过程和针对半像素的十字形(CSP)的搜
索条件,从而提出了基于起点预测的十字-六边形-菱形的运动估计算法(IPP-CHDS)。

文中详细研究了该算法的搜索过程和流程,并利用三个序列进行测试,测试结果表明,IPP-CHDS算法的搜索精度与FS算法接近,但它的运算量却大大的减少。

【总页数】5页(P54-57)
【关键词】运动类型;整像素;半像素;起点预测
【作者】王艳营
【作者单位】黑龙江科技学院计算机与信息工程学院
【正文语种】中文
【中图分类】TP391
【相关文献】
1.基于起点预测的自适应交叉-准菱形运动估计算法 [J], 梁燕;刘文耀
2.一种起点预测的十字形快速运动估计算法 [J], 谢帅铃;蔡志勇;柳丹青
3.基于改进的十字-菱形搜索算法的运动估计 [J], 刘海华;雷奕;谢长生
4.自适应简单菱形六边形运动估计搜索算法 [J], 韩波;秦水介
5.基于起点预测的单位十字快速运动估计算法 [J], 林兆花;谢存禧;邹焱飚
因版权原因，仅展示原文概要，查看原文内容请购买。

基于方向自适应十字搜索的快速块匹配运动估计算法
杨恒;王庆
【期刊名称】《计算机应用研究》
【年(卷),期】2007(24)5
【摘要】提出了一种方向自适应十字搜索算法,通过自适应地使用小十字模板、大十字模板和四种方向的T形模板,有效地减少了搜索点数,提高了搜索速度.实验结果表明,该算法在保持与菱形搜索(DS)、正方形-菱形搜索(SDS)、十字-菱形搜索(CDS)和小十字-菱形搜索(SCDS)四种算法相同搜索精度的同时,速度上比DS、SDS、CDS和SCDS算法分别提高了74.65%、39.78%、42.44%和7.84%.【总页数】3页(P44-45,65)
【作者】杨恒;王庆
【作者单位】西北工业大学,计算机学院,陕西,西安710072;西北工业大学,计算机学院,陕西,西安710072
【正文语种】中文
【中图分类】TP301.6
【相关文献】
1.基于边缘局部偏差搜索的快速块匹配运动估计算法 [J], 卢紫微;钟修皓;张燕;敬博
2.用于快速块匹配运动估计的自适应十字模式搜索 [J], 王晓燕;郑建宏
3.基于预测搜索距的快速块匹配运动估计算法 [J], 余颖;胡继承
4.一种基于块匹配的自适应快速运动估计算法 [J], 舒振宇;高智勇;陈心浩;刘海华
5.基于方向自适应采样搜索的快速运动估计算法 [J], 王强;李月娥
因版权原因，仅展示原文概要，查看原文内容请购买。

视频压缩感知中基于菱形快速搜索的双匹配区域预测杨春玲;戴超【摘要】多假设预测是视频压缩感知多假设预测残差重构算法的关键技术之一,但目前的多假设预测算法对运动剧烈的视频序列依然存在计算复杂度高且质量不佳的缺陷,而且由于观测值与真实信号是一对多的关系,只采用观测值的绝对误差和准则选择假设块容易引入噪声,从而限制了重构质量.针对这些问题,文中结合视频前/后景的运动特征,提出了基于菱形快速搜索的双匹配区域多假设预测算法(MH-DS),即利用菱形快速搜索方式确定当前解码块的前景/后景的运动矢量,获得两个最佳搜索窗,从中搜索多假设匹配块组;在匹配过程中,采用融合最小均方误差和最大匹配像素统计的块匹配准则,以得到更相关的假设块.仿真结果表明,基于菱形快速搜索的双匹配区域多假设算法能够有效地降低重构端多假设预测过程的计算复杂度,与现有最优视频压缩感知预测-重构算法相比,提升了预测精度和重构质量.【期刊名称】《华南理工大学学报（自然科学版）》【年(卷),期】2018(046)003【总页数】9页(P49-57)【关键词】视频压缩感知;多假设预测;菱形搜索;块匹配准则【作者】杨春玲;戴超【作者单位】华南理工大学电子与信息学院,广东广州510640;华南理工大学电子与信息学院,广东广州510640【正文语种】中文【中图分类】TN919.82006年Donoho[1]、Candès等[2]提出并论证了压缩感知(CS)理论，即只需要按照特定的条件将可压缩信号的高维信号投影到一个低维空间上，就可以通过重构算法利用少量观测值重建出原始信号，该理论突破了传统的奈奎斯特信号采集理论.之后压缩感知理论在图像/视频压缩与重建领域受到广泛的关注[3- 16].最初是对图像/视频帧直接观测，但实际应用中图像/视频帧的信息量较大，导致压缩感知中测量矩阵规模较大，计算复杂度较高.为此，文献[3]提出了分块压缩感知及其重构算法(BCS)，即先对图像进行分块观测，再利用投影Landweber迭代算法重构，并在迭代过程中引入维纳滤波以消除重构图像的块效应.BCS算法提高了图像压缩感知的重构质量，大大降低了重构计算复杂度，被认为是图像压缩感知的经典重构算法，在图像和视频压缩感知研究中备受重视.文献[4]在BCS基础上，提出了在离散余弦变换(DCT)、离散小波变换(DWT)、离散双树小波变换(DDWT)域进行阈值处理的BCS算法(BCS-SPL)，进一步提高了重构质量;将该算法应用到视频压缩感知中，实现了视频压缩感知重构，但由于没有充分利用视频的帧间相关性，重构性能不太理想.基于视频信号的帧间相关性，文献[5]提出了一种观测域多假设预测视频压缩感知重构算法，即将相邻帧作为参考帧，从参考帧中选取一组假设块的加权线性组合作为当前块的预测，然后对得到的更加稀疏的残差信号做稀疏重构，取得了很好的重构性能.基于多假设预测的视频压缩感知重构的相关研究的不断深入，使视频压缩感知的研究得到了突破性进展.在观测域多假设预测研究中，文献[5]提出的添加Tikhonov正则化项求解最优权值方法，具有计算简单和重构效果好的优点;文献[6]联合Iasso模型中的l1范数正则化及岭回归模型中的l2正则化求解最优权值;文献[7]提出了在l2范数正则化项中加入权重调整函数，并优化了假设集合.文献[6- 7]对权值分配求解过程作出了改善，重构质量得到了一定的提升，但计算复杂度大大增加，实用性不高.观测域多假设预测算法由于预测块的不重叠分块处理，使其预测结果和重构结果依然存在着块效应.因此，文献[8- 9]基于Tikhonov正则化多假设预测模型[5]提出了两阶段多假设预测模式，分为观测域多假设预测和像素域多假设预测，利用像素域灵活分块的特性，在像素域进行重叠块多假设预测，有效地削弱了重构图像的块效应，相比于文献[6- 7]的算法，重构质量更高且计算复杂度更低.但多假设预测方案[5- 9]依然存在如下不足:①对于运动剧烈的视频序列，如果需要匹配到较好的假设块，则需要扩大搜索范围，全搜索模式将导致计算复杂度呈指数级增长，不符合实际应用，如果限制搜索范围，则导致预测精度不高;②在观测域使用欧式距离作为相似块匹配准则不太合理，有可能引入新的噪声而降低重构质量．基于上述分析，文中在两阶段多假设预测重构[8- 9]的框架基础上，提出了一种基于菱形快速搜索的双匹配区域多假设预测算法(MH-DS)，针对视频压缩感知多假设预测中方形全搜索模式预测精度与计算复杂度不能兼顾的问题，基于视频中前景和后景通常运动方向相反的事实，先以菱形快速搜索方式确定前景/后景的运动矢量，然后分别以两个运动矢量末端点为中心确定假设块双匹配域，以保证在计算复杂度增加幅度不大的前提下提高预测精度;针对观测域匹配准则的不合理性，文中提出了基于最小均方误差(MMSE)和最大匹配像素统计(MPC)的融合匹配准则来优化假设块集合．1 多假设预测算法视频压缩感知采用分块观测模式[10- 13]，其主要原理为:将每个视频帧分成若干个不重叠的B×B大小的图像子块，对每个图像子块采用高斯随机观测矩阵Φ进行观测，即yi=Φxi(1)式中，xi为第i个图像块，Φ为M×B2维的高斯随机矩阵，yi为第i个图像块的观测值，采样率为M/B2．在视频压缩感知重构中，通常将整个视频序列分成若干个图像组(GOP).每个图像组的首帧为关键帧，其余帧为非关键帧.对于关键帧，利用CS重构算法进行帧内独立重构;对于非关键帧，由于视频帧间相关性非常大，故在当前帧的相邻几帧内大概率存在当前帧图像块的相似块，可以将相邻几帧作为参考帧[14]进行多假设预测．多假设预测的核心思想是选取一定数量的相似块作为假设块组，然后对假设块组加权线性组合以获得更接近于原始图像的预测帧，对于当前t帧中第i个B×B解码块，多假设预测的目的是尽可能使得预测信号与原始信号间的残差信号e的能量W(e2)最小，即W(e2)=min(2)式中:xt，i为列向量化的当前块;Ht，i为假设块组，维数为B2×K，每一列由列向量化的假设块组成，K为假设块的个数，w为权重列矢量.对式(2)中Ht，i的线性组合进行优化，则式(2)转化为(3)式中，wt，i为最优权值向量，利用最小二乘优化算法求解.由于在视频压缩感知中，解码端只有当前块的观测值矢量yt，i，yt，i=Φxt，i(4)因此，文中对式(3)采用观测域的优化方法求解wt，i:(5)由于各图像子块的观测点数通常小于假设块数量K，即方程个数小于未知数的个数，因此式(5)为不适定问题，文献[5]采用Tikhonov正则项来求解此问题，以的l2范数作为惩罚函数添加到目标函数式(6)中，即2(6)式中，为尺度参数，Γ为惩罚权重，则可以求得闭式解:(7)当前块的预测值为目前视频压缩感知重构最常用的是预测-残差重构框架[15- 16]，即在多假设预测之后利用CS重构算法恢复出原始观测值与预测观测值之间的残差帧，再将恢复后的残差帧与预测帧相加得到最后的重构视频帧，其框图如图1所示．图1 预测-残差重构流程图Fig.1 Flowchart of prediction-residual reconstruction2 基于四步菱形搜索的双匹配区域多假设预测算法文献[5- 9]采取在参考帧中以当前待重构块的空间位置为中心的全搜索模式搜寻假设块，但在运动剧烈的视频序列中，由于图像块的运动速度较快，在参考帧中，与当前待重构块最相似的图像块可能已经远离它的空间位置，那么只能扩大搜索窗，但在全搜索模式中，搜索窗的扩大将导致计算复杂度呈指数级增长.另外，视频序列中的前景和后景通常运动方向相反，如果沿一个方向搜索确定一个运动矢量，很有可能只是当前图像块的前景或者后景信息所在的匹配区域，因此会丢掉前景或后景的有效信息.结合传统块匹配搜索方案并根据视频前/后景的运动特征，文中提出了基于菱形快速搜索的最优双匹配区域预测算法(MH-DS)，其框图如图2所示，全搜索模式如图3所示．图2 中算法框架图Fig.2 Framework of the proposed algorithm2.1 基于菱形快速搜索的最优双匹配区域选择在搜索最优匹配区域的过程中，选用不同大小的搜索模版[17]，如图4所示，黑点为中心点，红点与黑点组成小菱形搜索模版(SDSP)，灰点与黑点组成大菱形搜索模版(LDSP)．双匹配区域的菱形快速搜索步骤如下:(1)确定前景/后景初步运动位移点.以当前待重构块位置为中心在参考帧中构造LDSP，分别比较9个搜索点，找出其中最相似的两个点(搜索点所代表的图像块与当前块的均方误差(MSE)越小则越相似)，这两个点的运动矢量表示前景和后景的运动方向，因此将这两个点称为前景、后景初步运动位移点．(2)搜索菱形模版.分别以前景与后景初步运动位移点为中心构建新的菱形搜索模版，若位移点(图5中蓝点)位于菱形搜索模版的中心，则以此位移点为中心点构建SDSP，并计算其中未被匹配计算过的点(图5(b)中红点)，分别比较这5个搜索点，找出其中最相似的点作为更新相似点;若位移点位于原模板的其他位置，则以此位移点为中心点构建LDSP，并计算其中未被匹配计算过的点(图5(c)、5(d)中红点)，分别比较这9个搜索点，找出其中最相似的点，将前景运动位移点或者后景运动位移点更新为最相似点．(3)若得到的前景运动位移点或者后景运动位移点位于菱形模版中心且在上一步搜索中菱形模版为SDSP，则停止搜索并将此点作为最终位移点;否则返回步骤(2)，当且仅当步骤(2)重复执行3次后停止搜索并输出最终位移点．(4)生成双匹配区域.分别以上述菱形快速搜索算法得到的位移点a和b为中心构造匹配域，即得到双匹配区域，如图6所示．2.2 基于MMSE和MPC的最优假设块组的选择文献[5]假设块组为搜索窗内所有的图像块，这种假设块组的选取方式不但增加了计算复杂度，而且由于搜索窗内的假设块并不全是有效匹配块，反而会影响重构质量，因此只保留和当前块测量值的绝对误差和SAD最小的前若干块作为最优匹配块组[14]，在降低计算复杂度的同时，也避免了低匹配度的噪声影响，在一定程度上提升了重构质量.但测量值的SAD大小并不能很好地反映假设块的好坏，考虑到在观测域多假设预测后，待重构图像已经包含图像块像素信息，文中提出了一种结合图像块像素信息、MMSE匹配准则和MPC的融合匹配准则来保证假设块集合最优.MPC可在像素域中计算，也可在观测域中计算(文中选择在像素域中计算)，MPC阈值处理过程如下:(8)图3 以待重构块在参考帧的对应空间位置为中心的全搜索模式示意图Fig.3 Schematic diagram of the full search pattern with spatial location of the current block to reference frame as the center图4 菱形快速搜索模版Fig.4 Fast diamond search template图5 菱形搜索示意图Fig.5 Schematic diagram of diamond search图6 最优双匹配区域示意图Fig.6 Schematic diagram of the best double match regions式中，t为估算阈值，I(p)为当前块位于p点的像素值/观测值，R(p)为假设块位于p点的像素值/观测值.由式(9)可计算块中像素点的匹配个数[18](9)式中，I为当前块，R为假设块.若块中像素点的匹配个数越多即MPC 越大，则表示当前块与假设块越相近．文中提出的融合匹配机制选择假设块的具体步骤如下:(1)粗选假设块.若要为当前块选出最优的K个假设块，则利用像素域的MMSE和MPC以及测量域的MMSE匹配准则在搜索窗中分别选出3K个最优匹配块，共选出9K个匹配块(有重叠)．(2)精选假设块.若3种匹配准则所选取的匹配块集合分别表示为O、M、N，则最终选取的匹配块集合为P=O∩M∩N．(3)控制误差.若匹配块集合P中的元素超过K个，则取前K个元素;若不足K个，则再从观测域MSE准则选取的匹配块集合C中选取MSE较小的元素补充至匹配块集合P，直至有K个元素为止．2.3 基于像素域信息的多假设块预测在假设块线性加权步骤中，式(6)中的Tikhonov正则项Γ为[5](10)文献[12]提出联合欧式距离与相关系数加权的Tikhonov正则项来改善文献[5]中的正则化失真，即(11)(12)(13)式中，E(·)和D(·)分别计算期望和方差，M维的y和yi,h分别为当前块和第i个假设块的观测值．为进一步改善预测性能，文中基于文献[12]，结合第一阶段的像素域重构信息,将ci修改为(14)式中，M维的x和xi,h分别为当前块和第i个假设块的像素值．3 实验结果及分析为验证文中所提算法的有效性，将文中算法(MH-DS)与近年来视频压缩感知重构算法的最新算法进行性能对比.由于部分文献算法程序无法复制，为了保证对比的公平性，文中在与对比文献基本条件一致的情况下对比重构算法的性能．3.1 仿真实验结果及性能对比分析实验1 仿真条件与文献[6，8]中相同，GOP长度为16，采用6个qcif@15 Hz的标准视频序列(Foreman、Coastguard、Hall、Football、Soccer、Suize，每个序列取前96帧共6组GOP)进行测试，分块大小为16×16，观测矩阵为随机高斯矩阵，每个GOP的关键帧采样率均为0.7，采用BCS-SPL-DDWT算法[4]进行独立帧内重构;非关键帧采样率依次取0.1～0.5，采用预测-残差重构模型进行帧间重构，残差重构选用BCS-SPL-DDWT算法.各算法在不同采样率下的平均PSNR见表1，Soccer序列第2帧的重构视觉效果见图7．表1 不同非关键帧采样率下4种算法的平均PSNR对比Table 1 Comparison of average PSNR among four algorithms with different sampling rates for non-key frames视频序列重构算法PSNR/dBM/B2=0.1M/B2=0.2M/B2=0.3M/B2=0.4M/B2=0.5均值CoastguardwElasticNet[6]28.2430.3532.1933.8135.5432.02Fw_2sMHR[8]28. 9130.8232.4433.9435.4832.32Gw_2sMHR[8]28.8931.0132.8434.3636.0732.6 3MH-DS29.1131.2733.3434.7336.3732.97FootballwElasticNet25.9428.0129.7531. 0532.5129.45Fw_2sMHR26.4628.7330.4431.9133.4130.19Gw_2sMHR26.352 8.7230.5332.0333.5630.24MH-DS26.6728.9631.0632.5034.1130.66ForemanwElasticNet32.0234.9337.1439. 3141.4236.96Fw_2sMHR33.2536.1738.3840.1541.9237.97Gw_2sMHR32.973 5.9238.1540.1241.9937.83MH-DS33.5536.4339.1840.7142.4638.46HallwElasticNet32.1833.8435.0836.1237. 2834.90Fw_2sMHR32.8834.7636.2137.2638.0435.83Gw_2sMHR32.3134.283 5.6936.8437.6135.34MH-DS32.9634.9136.4737.5338.0735.98SoccerwElasticNet28.8931.8834.1836.49 38.5433.99Fw_2sMHR29.3232.4234.8136.5138.4234.29Gw_2sMHR29.0832.3 934.9136.9338.9734.45MH-DS30.0533.1235.8037.5939.5535.22SuizewElasticNet36.3338.4440.0841.544 3.0139.88Fw_2sMHR37.8240.0641.6343.0744.4241.40Gw_2sMHR37.5239.83 41.4843.0644.4841.27MH-DS37.9140.1141.9343.2544.7641.59图7 3种算法的重构视觉效果对比Fig.7 Comparison of reconstructed vision effect among three algorithms由表1可见，文中MH-DS算法对于各序列的PSNR均明显高于wElasticNet、Fw_2sMHR和Gw_2sMHR算法，在非关键帧采样率为0.1～0.5时，MH-DS算法对于6个序列的平均PSNR比wElasticNet算法的最大PSNR提高了1.71 dB，比Fw_2sMHR算法的最大PSNR提高了0.93 dB，比Gw_2sMHR算法的最大PSNR提高了0.77 dB.由图7可见:在wElasticNet算法的重构效果图中，3个运动员的小腿区域出现明显的模糊块，背景也极其模糊;在Fw_2sMHR算法的重构效果图中，模糊块虽然得到一定的改善，但依然在视觉上存在一定的模糊;在MH-DS算法的重构效果图中，小腿附近的模糊块基本消除，并且球员的球衣号码15大大增强了辨识度.这是因为在基于菱形快速搜索双匹配区域的多假设预测中，充分利用了观测信号的先验信息和视频的帧间相关性，并且在选取假设块的过程利用融合匹配准则，避免了虚假噪声块的干扰，从而提高了重构质量．实验2 实验条件完全按照文献[7,15]中给出的设置,采用3组CIF@30 Hz的标准视频序列(Foreman,Hall,Coastguard)的前88帧(GOP为8,关键帧采样率为0.7)进行实验，不同非关键帧采样率下文中算法与视频压缩感知算法HD-BDCVS[15]、Up-Se-AWEN-HHP算法[7]的平均PSNR如表2所示.从表中可知，在不同采样率下，MH-DS算法对Foreman、Coastguard、Hall序列的平均重构PSNR比Up-Se-AWEN-HHP算法分别高出1.71、0.71、2.23 dB，比HD-BDCVS算法分别高出2.83、1.00、1.38 dB.可见，在不同的采样率下，文中算法的重构性能都有一定的提升.这是因为在多假设预测中充分利用了先验信息，采用双匹配区域寻找的匹配块更加合理，更加符合视频运动特征.在观测域假设块匹配阶段，先利用像素域MMSE、观测域MMSE和MPC三种匹配准则，大范围剔除了不相关的匹配块，然后进一步选择同时符合3种匹配准则的假设块，避免引入噪声块而导致重构质量变差的情况出现.在权值分配上，文中算法更加注重匹配块与当前块的相关性，使得权重调整更为合理，因此重构质量得到提升．实验3 仿真条件完全参照文献[16]设置,即采用5个cif@30 Hz的标准视频序列的前16帧(GOP为8,关键帧采样率为0.7,非关键帧采样率为0.2),分块大小为32×32,各视频序列在不同算法下的平均PSNR如表3所示.由表中可见，对比文献[16]中算法，MH-DS算法的PSNR值提升明显，对Paris、Foreman、Silent、Mother-daughter、Akiyo视频序列分别提升了0.73、0.41、0.86、1.04和0.22 dB，这是因为MH-DS算法充分利用了有效信息，并且文中的块匹配准则精准性优于文献[16]的匹配准则，权值调整更为合理，因此得到了较高的重构质量．表2 不同非关键帧采样率下MH-DS算法与文献[7，15]算法的平均PSNR对比Table 2 Comparison of average PSNR among MH-DS and algorithms in references [7，15] with different sampling rates for non-key frames视频序列重构算法PSNR/dBM/B2=0.1M/B2=0.2M/B2=0.3M/B2=0.4M/B2=0.5均值ForemanHD-BDCVS[15]33.6236.2337.8839.5240.8837.62Up-Se-AWEN-HHP[7]36.1738.1539.6540.8642.0839.38MH-DS37.6339.3140.7041.8542.7840.45HallHD-BDCVS35.7537.3238.2439.2540.3238.17Up-Se-AWEN-HHP35.1536.5037.5138.3739.1137.33MH-DS37.2338.7639.8340.6141.3339.55CoastguardHD-BDCVS30.1532.4134.2336.4538.1034.26Up-Se-AWEN-HHP30.8632.9434.6736.2937.9934.55MH-DS31.8933.7235.3136.9338.4535.26表3 MH-DS算法与文献[16]算法的平均PSNR对比Table 3 Comparison of average PSNR between MH-DS and algorithm in reference [16]算法PSNR/dBParisForemanSilentMother-daughterAkiyo文献[16]32.5439.0137.844.6545.75MH-DS33.2739.4238.6645.6945.973.2 算法复杂度分析通过实验仿真对比了基于菱形块匹配搜索的多阶段多假设算法与基于全搜索的多假设预测算法的重构质量和时间复杂度，FS(32，32)表示全搜索窗大小为32，DS(16，16，4，2)表示本文的四步菱形搜索法，其中16为最终搜索窗半径，4为LDSP搜索步长，2为SDSP搜索步长;GOP为8，关键帧采样率为0.7，非关键帧采样率为0.1，都使用MH-BCS-SPL算法进行预测.文中的仿真实验环境为Inter Core i5 3.30 GHz处理器，内存4 GB，操作系统Wndows 7.所有仿真实验均在Mtalab R2014a上进行.表4给出了两个运动比较剧烈的序列(Soccer和Football)的前88帧的实验结果，其中时间复杂度以解码端平均每帧的多假设预测实际时间作为度量标准，PSNR为预测结果.由表4可知，菱形快速搜索匹配区域在保证重构性能的情况下，大大降低了匹配时间，这是因为菱形搜索算法满足视频序列运动矢量中心偏置分布特性，并且步长由大到小地逐步寻找最优匹配块的区域保证了匹配的精准性，避免了将大量计算成本用在与当前块并不相关的区域，有效地降低了寻找匹配块的搜索复杂度．表4 两种搜索算法的时间复杂度与重构质量对比Table 4 Comparison of time complexity and reconstruction quality between two searching algorithms视频序列FS(32,32)时间/sPSNR/dBDS(16,16,4,2)时间/sPSNR/dBSoccer19.3129.418.1629.28Football19.4526.328.3426.254 结论文中提出了基于菱形快速搜索的双匹配区域多假设算法(MH-DS)，基于视频前/后景的运动特征，利用菱形搜索方式确定前/后景的运动矢量，然后分别以两个运动矢量的末端为中心建立两个匹配区域，在这两个匹配区域内搜寻假设块并进行多假设预测;采用融合最小均方误差(MMSE)和最大匹配像素统计(MPC)的块匹配准则，在假设块选择过程中利用两种匹配准则对假设块集合进行筛选，剔除其不相关的假设块，避免噪声块的干扰.文中所提出的菱形快速搜索算法中双匹配区域的设定很好地契合了视频前/后景的运动性质，与现有多假设预测算法相比，提高了预测精度;而双重匹配准则中由粗到细的选择假设块机制，进一步优化了假设块集合.仿真实验结果表明:相比于现有视频压缩感知重构算法，MH-DS算法的性能有了明显的提升，MH-DS算法的PSNR比HD-BDCVS算法的最大PSNR提高了2.8 dB左右;与全搜索方式相比，MH-DS算法的计算复杂度减少了一半以上;对于运动剧烈的视频序列，文中快速搜索算法在降低计算复杂度的同时还能保证视频重构质量，尤其在低采样率时，由于文中算法充分利用了有限的先验知识，故其重构效果提升更为明显．参考文献：[1] DONOHO D pressed sensing [J].IEEE Transactions on Information Theory，2006，52(4):1289- 1306．[2] CANDS E J，TAO T，ROMBERG J，et al.Exact signal reconstruction from highly incomplete frequency information [J].IEEE Transactions on Information Theory，2006，52(2):489- 509．[3] LU G.Block compressed sensing of natural images [C]∥Proceedings of the 15th International Conference on Digi-tal Signal Processing.Cardiff：IEEE，2007：403- 406．[4] MUN S，FOWLER J E.Block compressed sensing of images using directional transforms [C]∥Proceedings of IEEE International Conference on Image Processing.Cairo：IEEE，2009：3021- 3024．[5] CHEN C，TRAMEL E W，FOWLER J pressed-sensing recovery of images and video using multihypothesis predictions [C]∥ Proceedings of the 45th Asilomar Conference on Singals，Systems，andComputers.Pacific Grove：IEEE，2011:1193- 1198．[6] JIAN 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．[7] 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．[8] OU Wei-Feng，YANG Chun-Ling，LI Wen-Hao，et al.A two-stage multi-hypothesis reconstruction scheme in compressed video sensing [C]∥Proceedings of IEEE International Conference on Image Processing.Phoenix：IEEE，2016：2494- 2498．[9] 杨春玲，欧伟枫，戴超.一种视频压缩感知中两级多假设重构及实现方法 [J].电子与信息学报，2017，39(7):1688- 1696．YANG Chunling，OU Weifeng，DAI Chao.A two-stage multi-hypothesis reconstruction and two implementation schemes for compressed video sensing [J].Journal of Electronics & Information Technology，2017，39(7):1688- 1696．[10] 王蓉芳，焦李成，刘芳，等.利用纹理信息的图像分块自适应压缩感知 [J].电子学报，2013，41(8):1506- 1514．WANG Rong-fang，JIAO Li-cheng，LIU Fang，et al.Block-based adaptive compressed sensing of image using texture information [J].Acta Electronica Sinica，2013，41(8):1506- 1514．[11] 练秋生，田天，陈书贞，等.基于变采样率的多假设预测分块视频压缩感知 [J].电子与信息学报，2013，35(1):203- 208．LIAN Qiu-sheng，TIAN Tian，CHEN Shu-zhen，et al.Block compressedsensing of video based on variable sampling rates and multihypothesis predictions [J].Journal of Electronics & Information Technology，2013，35(1):203- 208．[12] 常侃，覃团发，唐振华.基于联合总变分最小化的视频压缩感知重建算法 [J].电子学报，2014，42(12):2415- 2421．CHANG Kan，QIN Tuan-fa，TANG Zhen-hua.Reconstru-ction algorithm for compressed sensing of video based on joint total vasriation minimzation [J].Acta Electronica Sinica，2014，42(12):2415- 2421．[13] 李然，干宗良，崔子冠，等.联合时空特征的视频分块压缩感知重构 [J].电子与信息学报，2014，36(2):285- 292．LI Ran，GAN Zong-liang，CUI Zi-guan,et al.Block compressed sensing reconstruction of video combined with temporal-spatial characteristics [J].Journal of Electro-nics & Information Technology，2014，36(2):285- 292．[14] 杨春玲，欧伟枫.CVS中基于多参考帧的最优多假设预测算法 [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．[15] CHEN Jian，WANG Ning，XUE Fei，et al.Distributed compressed video sensing based on the optimization of hypothesis set update technique [J].Multimedia Tools and Applications，2017，76(14):15735- 15754．[16] ZHAO C，MA S W，LIU J，et al.Video compressive sen-sing reconstruction via reweighted residual sparsity [J].IEEE Transactions on Circuits & Systems for Video Technology，2017，27(6):1185- 1195．[17] ZHU S，MA K K.A new diamond search algorithm for fast block matching motion estimation [J].IEEE Tran-sactions on Image Processsing，2000，9(2):287- 290．[18] CHEN M J，CHEN L G，CHIUEH T D，et al.A new block-matching criterion for motion estimation and its implementation [J].IEEE Transactions on Circuits and Systems for Video Technology，1995，5(3):627- 635．。