快速运动估计（共7篇）
快速运动估计 篇1
1 引言
视频编码标准H.264/AVC的压缩效率比MPEG-2、MPEG-4提高了近1倍[1],与此同时也造成了运算量的大幅增加,因此高效快速的运动估计算法成为H.264实时编码器实现的关键。由于运动是视频序列固有的根本特征,所以有效利用和适应运动特征的运动估计算法可以显著提高搜索速度和编码效率。
目前,典型的快速搜索算法有三步搜索法、四步搜索法、菱形搜索法、六边形搜索法、预测运动矢量场自适应搜索算法(PMVFAST)、具有匹配预判的自适应不规则模板搜索算法(AIPS-MP)等。此外,我国研究人员还提出了非对称十字型多层次六边形网格搜索算法(UMHexagonS)[2,3],这种算法采用整数像素运动估值,在高码率、大运动图像序列编码中能保持较好率失真性能,运算量很低,已被H.264标准采纳。
2 PAFME算法
实验发现,UMHexagonS算法的搜索策略也存在一些缺点和不足,如:对于不同的运动序列都采用固定的搜索模板和相同的搜索策略,这样虽能保证较高的搜索精度,但由于没有充分利用不同序列及不同块的特征,不能自适应地结束搜索,因此存在较多的冗余搜索点,造成搜索开销增大。笔者结合H.264标准采用的可变块尺寸运动估计技术的特点,提出了一种搜索模式自适应的快速运动估计算法(Search Pattern Adaptive Fast Motion Estimation,PAFME),并通过实验测试了算法性能。PAFME算法主要采用以下核心技术:初始搜索点预测,多搜索模式选择,利用经验阈值调整搜索模式的使用。
该算法的主要思想是在保证图像质量的前提下,减少算法中的冗余搜索点,从而加快运行速度。在该算法中使用由经验得到的整数型常数作为基值;对不同尺寸的块类型,采用对基值进行简单的移位操作,以作为不同的判断阈值。
在搜索的过程中,首先对初始预测点集中的部分预测点(中值预测点及原点)进行搜索,包括小菱形四点搜索和可能的密集搜索步骤;仍不满意,再搜索上层块类型预测点,而后按当前最佳点进行小菱形搜索或可延伸的六边形和小菱形搜索步骤。算法流程如图1所示。
3 实验结果与分析
把新算法嵌入到H.264的标准参考软件JM12.4中进行测试比较,以验证其有效性。测试条件:在基本框架下,采用SATD和RDO指标,搜索范围为所有编码模式,1/4像素精度,参考帧数为1,第一帧为I帧,其余为P帧。测试序列有:Forman(QCIF,10 f/s(帧/秒)),Paris(CIF,15 f/s),Football(SIF,30 f/s),各100帧。之所以选用纹理和运动复杂度各不相同的3种测试序列,格式、帧率均有差异,是为了充分测试算法对不同内容的视频序列在不同目标下的应用性能,并且选用4种量化参数以测试算法在不同码率下的性能。
采用亮度信号的峰值信噪比(PSNRY)、比特率、整数像素精度运动估计总时间(t)等指标对PAFME算法与JM12.4参考软件采用的快速算法(JM12.4FME)的性能进行比较,实验结果详见表1。可见,PAFME算法具有以下特点:1)PSNRY平均损失0.018 d B,最大不超过0.088 dB,所以新算法对视频重建质量的影响可忽略;2)比特率的增加未超过0.7%,所以新算法对编码效率影响很小;3)运算量有较大降低,整像素精度运动估计速度提升明显,耗时平均减少33%。
对上述测试序列,在不同量化参数下,PAFME算法与JM12.4FME相比,其整像素精度运动估计的耗时百分比(tPAFME/tJM12.4FME)见图2。由图可见,在不同量化参数下,PAFME算法性能稳定,即新算法的有效性受量化参数影响较小。对不同特征的信号序列,算法性能有所差异,对运动一致性较好的序列,整像素精度运动估计的耗时可减少35%以上,搜索速度较快。
4 小结
笔者针对现有算法的不足,提出搜索模式自适应的快速运动估计算法PAFME,结合H.264标准采用的可变块尺寸运动估计算法的特点,利用运动矢量在时空域及不同编码模式间的相关性,设计了初始搜索中心的预测方法。通过测试发现:自适应的搜索模式选择规则可以显著地加快运算速度,并保持了视频质量和码率基本不变,为高速的运动估计提供了一种新的方向。
摘要：提出了一种搜索模式自适应快速运动估计算法(PAFME),首先利用变块尺寸运动估计的特点与运动矢量的时空域相关性,预测初始搜索中心;采用多种搜索模式以适应不同运动特征,提出了搜索模式自适应的选择机制,以节省不必要的搜索点加快搜索速度;又能避免陷入局部极小。实验结果表明,与H.264/AVC的参考软件JM12.4相比,该算法使整像素精度运动估计的速度提高了30%～40%,同时保持了图像质量和码率基本不变。
关键词：运动估计,搜索模式自适应,H.264
参考文献
[1]OSTERMANN J,BORMANS J,LIST P,et al.Video coding with H.264/AVC:tools,performance,and complexity[J].IEEE Circuits and Systems Magazine,2004,4(1):7-28.
[2]CHEN Zhibo,ZHOU Peng,HE Yun.Fast motion estimation for JVT,Doc.JVT-G016[C]//Proc.7th JVT Meeting,2003.Pattaya,Thailand:JVT,2003.
[3]CHEN Zhibo,ZHOU Peng,HE Yun,et al.Fast integer pel and fractional pel motion estimation in for JVT,Doc.JVT-F017[C]//Proc.6th JVT Meeting,2002.Awaji,Island,JP:JVT,2002.
快速运动估计 篇2
H.264/AVC由ITU-T视频编码专家组 (VCEG) 与ISO/IEC MPEG组成的JVT (Joint Video Team) 联合开发, 沿用了基于块的混合编码技术, 但在技术细节上做了很大改进, 采用了多参考帧预测编码、多种可变块大小的帧间编码模式、1/4像素精度的运动补偿等先进技术。由于上述先进编码技术的引进, H.264/AVC成为近年来最为高效的一个视频压缩标准, 与MPEG-2、MPEG-4相比, H.264/AVC的压缩效率为它们的2倍[1]。但与此同时也造成了运算量的大幅增加。由于运动是视频序列所固有的根本特征, 通过充分利用与运动特征相适应的运动估计算法, 可以显著提高编码技术在搜索速度和编码效率方面的性能。
本研究提出一种搜索模式自适应快速运动估计算法 (PAFME) 。
1 典型的运动估计算法
早期的快速搜索算法有:三步搜索法 (TSS) 、新三步搜索法 (NTSS) 、二维对数搜索法 (LOGS) 、十字搜索算法 (CS) 、四步搜索法 (FSS) 、菱形搜索 (DS) 、六边形搜索等。在上述算法中, 最高效、最常用的是减少搜索点数的新三步法[2]、菱形法[3]与六边形法[4]等。此类快速算法基于如下假设:运动矢量为中心偏离分布, 且搜索点在接近全局最优点时对应的匹配误差单调下降。由于上述假设条件并不总能成立, 特别在运动较大时, 此类算法容易陷入局部极小, 会显著降低视频质量。近几年发展起来的基于运动矢量预测的快速运动估计算法, 如预测运动矢量场自适应搜索算法 (PMVFAFST) [5]、增强的预测带状搜索 (Enhanced Predictive Zonal Search, EPZS) [6]与具有匹配预判的自适应不规则模式搜索算法 (Adaptive Irregular Pattern Search with Matching Prejudgment, AIPS-MP) [7]和UMHS算法 (hybrid Unsymmetrical-cross Multi-Hexagon-grid Search) [8,9]等, 显示出了更好的编码性能和较快的搜索速度。此类算法利用运动矢量的相关性预测初始搜索中心, 基于“初始搜索中心接近全局最优点”的假设, 仅在初始搜索中心附近按特定搜索模式进行局部搜索;此外常引入匹配预判方法提前终止局部搜索, 以进一步节省计算开销。显然, 其性能依赖于初始搜索中心预测的可靠性及搜索模式的设计, 且与块的局部运动特征密切相关。
而在H.264/AVC参考软件中使用的就是UMHS算法。UMHS算法采用了基于运动矢量预测的快速运动估计技术的基本思想, 只是在初始搜索点、搜索模板及搜索中止准则的设计上, 充分利用了H.264中多块尺寸运动补偿模式与多参考帧的特点, 以解决因减少搜索点数而容易陷入局部极小的问题。UMHS算法主要步骤如下:
(1) 初始搜索点预测—空域的中值预测、上一层块尺寸类型的预测、相邻参考帧间的预测与时域预测, 搜索以上所有的初始搜索点, 判断是否满足提前中止准则;
(2) 不对称十字形搜索, 并判断是否满足提前中止准则;
(3) 多六边形栅格搜索, 包括半径为2像素的正方形模板与多个六边形 (16像素) 模板;
(4) 可延伸的基于六边形的搜索, 包括六边形模板与菱形模板。
其中, 提前中止准则基于3种RDC预测方式—中值预测、上层块尺寸类型预测与相邻参考帧的预测, 并且为量化参数的函数。此算法中每一步都是以前一步搜索所得的最佳匹配点为搜索中心。
可见, UMHS算法利用了H.264中多块尺寸运动补偿模式与多参考帧的特点;采用了块尺寸类型间运动矢量预测方法以及相邻参考帧间运动矢量预测方法, 提高了初始搜索点预测的准确性;采用了不对称十字形、多六边形栅格、六边形搜索等搜索模板, 以尽量避免陷入局部极小;设计了基于块尺寸类型间RDC预测与相邻参考帧间RDC预测的中止准则, 使得在运动矢量预测准确时能快速中止。
2 PAFME算法
经过大量实验测试和深入分析发现, UMHS算法的搜索策略仍存在一些缺点和不足, 即对于不同的运动序列都采用固定的搜索模板和相同的搜索策略, 这样虽能保证较高的搜索精度, 但由于没有充分利用不同序列及不同块的特征, 不能自适应地结束搜索, 存在较多的冗余搜索点, 产生很多不必要的搜索, 从而造成搜索开销增大。笔者结合H.264/AVC标准采用的变块尺寸运动估计的特点, 提出了一种改进算法即搜索模式自适应的快速运动估计算法 (PAFME) , 并通过仿真测试了算法的性能。PAFME算法针对UMHS算法的特点做了3个方面的改进:初始搜索点预测;多搜索模式选择;利用经验阈值调整搜索模式的使用。
2.1 初始搜索点预测
在初始搜索点预测方面, 其仅采用了空域的中值预测与上一层块尺寸类型的预测;如图1所示, 对运动矢量采用中值预测, 利用位于当前块左边、上边、右上 (或左上) 相邻块的预测值来预测当前块的运动矢量。
pred_mv=median (Mv_A, Mv_B, Mv_C) (1)
预测运动矢量为 (pred x, predy) 。当A块位于图片或宏块边界以外时, 其运动矢量将被 (0, 0) 所替代;若C块位于图片或宏块边界以外, 则被D块的运动矢量所替代, 而当B和C都不在边界之内时, 则将被第3块的运动矢量所替代。
在H.264变尺寸块匹配运动估计中, 同一块在不同编码模式下所得运动矢量也具有相关性[10]。编码模式为m的块, 其上层块尺寸类型下运动矢量集合记为MVUP, m=1时对应空集, 其具体构成如下:
undefined
式中 MVm—编码模式m下此块的运动矢量。
2.2 多搜索模式选择
搜索模板的大小和形状不但影响运动估计速度, 而且直接关系到算法的性能。为了获得更好的搜索速度和性能, 确定搜索模板的类型, 必须分析运动矢量分布的状况。
视频图像序列的运动矢量分布一般具有如下特性:
(1) 约有81.80%的运动矢量位于以中值预测点为中心的正方形搜索窗口内;77.52%的运动矢量位于菱形区域, 特别是有45.44%的运动矢量是零矢量。这说明绝大部分的图像块是静止或准静止的, 运动矢量分布具有中心偏置特性[11]。
(2) 运动矢量的概率分布是以中值预测点为中心向四周递减的;
(3) 运动矢量分布在水平和垂直方向的概率要比分布在相同半径下的其他方向大。
根据上述运动矢量的分布特性, 在PAFME算法中先后采用了局部3×3正方形搜索模式 (如图2所示) 、小菱形搜索模式 (如图3所示) 以实现小运动矢量的快速搜索;对于运动较大的块, 采用六边形搜索模式 (如图4所示) 可以实现搜索范围和搜索速度的折衷;另外对于运动剧烈或运动矢量分布不规则的区域, 为了在搜索中避免陷入局部极小, 采用“十”字形模式 (如图5所示) 和多层六边形模式进行大范围的稀疏搜索。在算法的执行过程中通过使用一些经验阈值自适应地调整搜索模式。
2.3 利用经验阈值调整搜索模式的使用
根据RDC选择搜索模式, RDC阈值采用简单的经验阈值 (Jth, 由经验得到的整数型常数作为基值, 其经验阈值的计算方法参见文献[12]) , 通过J
(1) 收敛条件:若满足收敛条件 (J
(2) 密集搜索条件:若满足密集搜索条件, 则进行密集搜索以避免搜索到的是局部最优。
3 测试结果与分析
为验证新算法的有效性, 把新算法嵌入到H.264的标准参考软件中进行测试比较。测试过程中选用的H.264视频编码器版本为JM12.4。测试条件如下:基本框架 (baseline profile) 下, 采用RDO、SATD, 搜索范围为16像素, 1/4像素精度, 针对所有编码模式, 参考帧数设为1, 第1帧为I帧, 其余各帧都为P帧。测试序列为:Silent (QCIF) , 帧率15 fps, 150帧;Forman (QCIF) , 帧率10 fps, 100帧;Paris (CIF) , 帧率15 fps, 100帧;Mobile (CIF) 与Football (SIF) , 帧率30 fps, 100帧。这些测试序列的纹理和运动复杂度各不相同, 格式从QCIF到CIF, 帧率也有差异, 以充分测试算法对不同内容视频序列在不同目标应用下的性能。为在较大码率变化范围下测试算法的性能, 量化参数QP设置为8、18、28与38。QP=28时PAFME算法与JM12.4参考软件中的UMHS算法在亮度信号的峰值信噪比 (PSNRY) 变化情况、比特率 (Bit-rate) 变化情况、整数像素精度运动估计总时间 (Time) 变化情况等方面的比较结果如表1所示。Foreman序列和Football序列的率失真曲线如图6、图7所示。
从表1中可以看出, 对所有测试序列采用PAFME算法的情况与采用JM12.4FME算法时相比, 具有以下特点:
(1) 亮度信号的PSNR损失平均为0.018 dB, 最大不超过0.088 dB, 对视频重建质量的影响可以忽略;
(2) 比特率的增加很小, 最大不超过0.7%, 编码效率基本不变;
(3) 整像素精度运动估计的耗时平均降低了33%左右。
以上仿真结果同时表明, 搜索模式选择规则的有效性受量化参数影响较小, 主要依赖于序列的运动特征。与JM12.4FME算法相比, 所提出的搜索模式自适应的快速运动估计算法显著降低了计算量, 同时保持了编码效率基本不变。
4 结束语
在分析现有算法的优势和不足之处的基础上, 本研究提出了一种搜索模式自适应的快速运动估计算法。针对H.264采用的变块尺寸运动估计技术的特点, 笔者利用运动矢量在时域、空域及不同编码模式间的相关性, 设计了初始搜索中心预测方法, 并引入了搜索模式自适应调整的方法。通过测试发现:自适应的搜索模式选择规则可以显著地加快运算速度, 并保持视频质量和码率基本不变。
参考文献
[1]OSTERMANN J, BORMANS J, LIST P, et al.Video cod-ing with H.264/AVC:tools, performance, and complexity[J].IEEE Circuits and Systems Magazine, 2004, 4 (1) :7-28.
[2]LI R X, ZENG B, LIOU M L.A new three-step search al-gorithm for block motion estimation[J].IEEE Transac-tions on Circuits and Systems for Video Technology, 1994, 4 (4) :438-442.
[3] ZHU S, MA K K. A new diamond search algorithm for fast block-matching motion estimation[J]. IEEE Transactions on Image Processing, 2000, 9 (2) :287-290.
[4] ZHU C, LIN X, CHAU L P. Hexagon-based search pattern for fast block motion estimation[J]. IEEE Transactions on Circuits and Systems for Video Technology, 2002, 12 (5) :349-355.
[5]TOURAPIS A M, AU O C, LIOU M L.Predictive MotionVector Field Adaptive Search Technique (PMVFAST) -En-hancing Block based Motion Estimation[C].Proceedings ofVisual Communications and Image Processing 2001 (VCIP-2001) .San Jose:[s.n.], 2001.
[6]TOURAPIS AM, AUO C, LIOUML.Highly efficient pre-dictive zonal algorithms for fast block-matching motion esti-mation[J].IEEE Transactions on Circuits and Systemsfor Video Technology, 2002, 12 (10) :934-947.
[7]NIE Y, MA K K.Adaptive irregular pattern search withmatching prejudgment for fast block-matching motion estima-tion[J].IEEE Transactions on Circuits and Systems forVideo Technology, 2005, 15 (6) :789-794.
[8] CHEN Z, ZHOU P, HE Y. Fast Motion Estimation for JVT, Doc. JVT-G016[C]. 7th JVT meeting 2003. Pattaya:[s.n.], 2003.
[9] CHEN Z B, ZHOU P, HE Y. Fast Integer Pel and Fractional Pel Motion Estimation in for JVT, Doc. JVT-F017[C]. 6th JVT Meeting 2002. Awaji: [s.n.], 2002.
[10]CHEN Z, ZHOU P, HE Y.Fast Motion Estimation forJVT, Doc.JVT-G016[C].7th JVT meeting 2003.Pat-taya:[s.n.], 2003.
[11]CHEUNG C H, PO I M.A novel cross-diamond search al-gorithm for fast block motion estimation[J].IEEETransactions on Circuits and Systerns for Video Tech-nology, 2002, 12 (12) :1168-1177.
快速运动估计 篇3
本文提出了一种新的分像素运动估计快速算法, 简单有效, 只是通过单纯的比较运算找到最匹配分像素点, 将搜索点数降为平均三个左右。在第2部分, 简单回顾一些已有的分像素快速算法, 第3部分描述新算法, 第4部分探讨提出的AVS分像素的运动估计算法, 并列举出多种算法的仿真结果, 以便比较, 第5部分得出结论。
1 已有快速算法
基于抛物面预测的分像素运动估计快速算法 (PPHPS) 中, 亚像素点周围的SAD曲面假定为抛物面模型, PPHPS需要计算3个搜索点, 和额外的SAD曲面模型的计算。基于二次方程模型的快速搜索 (JCHPS) , 在实际运动矢量周围的SAD函数假定是分离的二次方程, X和Y方向分别使用一维的线性方程来预测出最佳运动矢量。
既然最优亚像素点周围的实际SAD函数和预测的SAD函数并不完全一致, 就必然导致最佳运动矢量与实际选取的运动矢量之间产生误差, 从而引起比特率的增加和PSNR值的下降。另外, 以上两个模型的建立与预测过程中需要进行乘法和除法操作, 运算相对复杂。考虑到这两点, 下面提出新的分像素运动估计快速算法。
2 基于预测矢量的分像素运动估计快速算法
A V S中引入了1/4像素精度的运动矢量来降低补偿误差, 提高压缩率。一般采用逐级搜索:先在搜索区域内找到最优整像素点, 接着在这个整像素点的周围8个半像素点中找到最优半像素点, 然后在这个最优半像素点的周围8个1/4像素点中找到最佳的1/4像素点。如图1所示。
本文提出的算法, 利用预测矢量的值与整像素最优块的位置, 将1/2分像素的运动估计与1/4像素的运动估计合并.得到一种新的快速的分像素运动估计算法。算法大致思想如下:预测矢量可能是个整像素, 也可能是个1/2像素, 1/4像素。在分像素的搜索过程中, 我们仅仅根据预测矢量的值
3 分像素运动估计快速算法
3.1 算法描述
由图1可以看出, 按照标准的分像素搜索算法, 分像素运动估计将搜索16个分像素点, 这是相当耗时的。
整像素运动估计后, 得到一个最优的整像素位置。根据最优整像素位置与预测矢量的值确定分像素搜索的侯选点集合S。
(1) 预测矢量也为整像素:S={最优整像素周围四个最近的四个1/4分像素点}, 一共包含4个点。
(2) 预测矢量为1/2像素点:S={最优整像素加1/2像素, 最优整像素减1/2像素, 前面亮点连线上的搜索区域内的1/4像素点}, 由图1可以看出, 满足条件的点, 一共六个点。
(3) 预测矢量为1/4像素点:首先将预测矢量模4, 得到一个分像素偏移A, S={最优整像素加A/4像素, 最优整像素减 (4-A) /4像素}, 一共包含两个点。
在得到候选点集合后, 在候选点集合中根据运动估计率失真准则, 选取最优运动估计匹配点。
3.2 仿真性能比较
比较软件采用AVS参考软件Rm52jR1版本, 25帧每秒, 编码200帧, GOP为100, 无B帧, 分像素搜素中SATD计算使用Hadamard变换, RDO打开, 熵编码采用CAVLC。码率采用, CIF序列:400k, 460k, 520k;D1序列:1.5 M, 1.8 M, 2.2 M。
测试图像, 采用标准的测试图像, CIF: (352*288) foreman, football,
D1 (720*576) :mobile calendar, flower garden。
如表1, 表2所示。
4 结语
论文提出的基于预测矢量的快速分像素搜索算法, 应用到AVS的分像素运动估计中。使用该方法将分像素的搜索点数平均降低到3个左右, 比起分像素的全搜索点数15, 点数大大降低。大大加速了运动估计的处理, 而PSNR只是稍稍有点降低, 有的序列甚至还升高了, 这是由于, 前面的整像素运动估计采用非对称十六边形方法已经比较准确的定位了运动估计的最终位置。
该算法, 与FSPS算法相比, 算法平均搜索点数减少了2个, 与PPSPS相比, PSNR值降低较多, 但PPSPS的运算较复杂, 需要用到乘法与除法的操作。该算法在AVS的实现中, 尤其是编码器的应用中, 将大大提高分像素运动估计的速度。
参考文献
[1]信息技术.先进音视频编码.第二部分:视频, GB/T20090.2-2006.
[2]方健, 郑伟, 李炳博, 等.针对H.264的基于平坦区域预测的分像素运动估计[J].中国图象图形学报, 2008 (12) .
[3]李波, 张荩尹, 李炜.一种快速亚像素运动估计方法[P].专利号:200410073837.
快速运动估计 篇4
1 UMHexagon S算法分析
非对称十字型多层次六边形格点搜索算法(UMHexagon S算法)由Chen Zhibo等人[4]提出,由于该算法的运算量相对于快速全搜索算法可节约90%以上,同时能保持较好的率失真性能,因此,UMHexagon S算法已经被H.264的参考软件JM正式采纳,成为H.264标准专利库中的一部分。
UMHexagon S算法的基本步骤[5]如下:
(1)起始搜索点预测。使用多帧参考、中值预测、上层预测、相应块预测和邻近参考帧预测五种方法来进行预测。在起始搜索矢量的集合中,以拥有最小代价预测的运动矢量作为起始搜索点,然后用EARLY_TERMINA-TION判断是否提前截止,如果绝对误差和SAD较大则跳到步骤5,SAD很小则跳到步骤6。
(2)非对称十字搜索,如图1中步骤2。EARLY_TER-MINATION判断是否提前截止,SAD较大则跳到步骤5,SAD很小则跳到步骤6。
(3)螺旋搜索5×5区域如图1中步骤3-1。以目前最佳点为中心,搜索(-2,2)方形区域内的25个点。
(4)多层次大六边形格点搜索如图1中步骤3-2。在1/4 search_range的范围内,用不断扩大一倍直径的大六边形模板进行搜索。
(5)小六边形模板反复搜索如图1中步骤4-1。以小六边形为模板,在search_range范围内搜索,直到最优点出现在模板中心才停止搜索。
(6)菱形模板反复搜索如图1中步骤4-2。以菱形为模板,在search_range范围内搜索,直到最优点出现在模板中心才停止搜索,得到最终的运动矢量。
2 UMHexagon S算法的改进
2.1 对称十字搜索模板
在UMHexagon S算法的步骤3中使用的是螺旋搜索5×5区域。螺旋搜索是一种全搜索的搜索策略,需要计算整个搜索范围内所有点的SAD值,也就是要搜索25点。这样不仅复杂度高、运算量大而且费时。
自然的视频序列的运动矢量场通常是柔和平滑的,变化也比较缓慢。参考文献[6]中对典型的平缓和运动复杂的自然视频序列的运动矢量的统计研究发现,超过80%的运动矢量预测值位于中心5×5的网格区域内,但不是均匀分布。从图2中可以看出,总的5×5网格区域内的运动矢量是81.79%,而以原点为中心的半径为2的对称十字型区域(也就是A+B+C区域)运动矢量为74.74%。对称十字模板和螺旋搜索模板如图3所示。从5×5网格区域到半径为2的对称十字型区域,虽然运动矢量减少了7.05%,但是搜索点数减少达到64%,如图3(b)所示搜索点数从25点减少到9点。所以本文用对称十字型模板的9点搜索来取代螺旋搜索5×5区域的25点搜索。
2.2 自适应搜索长度
搜索长度search_range在UMHexagon S算法中用来控制搜索候选搜索点的范围。主要体现在以下几个步骤:步骤(4)(多层次大六边形格点搜索)中,以1/4 search_range做为搜索长度。步骤(5)(小六边形模板反复搜索)中,以search_range作为搜索长度;步骤(6)(菱形模板反复搜索中,以search_range作为搜索长度。可见,在UMHexagon S算法中搜索长度是固定不变的,合理地设定搜索长度能有效地减少UMHexagon S算法的复杂度。
场景中一般都是以某一对象为单位的运动,因此该对象内部的代价(mcost)应该具有很高的相关性[7]。据此,本文利用前两个搜索步骤的min_mcost之比,提出自适应搜索长度的方法。
设利用变量pre_min_mcost1、pre_min_mcost2、pre_min_mcost3、pre_min_mcost4来分别保存步骤(2)、(3)、(4)、(5的min_mcost,其定义公式如下:
式(1)中,ki表示前两个搜索步骤的min_mcost之比,式(2)中search_range是搜索长度。根据ki来相应地缩短改进后的搜索长度,本文的改进方法分别用在步骤(4)、(5)、(6)。
3 实验结果与分析
3.1 实验环境
本文在H.264的参考软件JM10.1上实现改进后的UMHexagon S算法,选取3个具有代表性的标准QCIF测试序列进行测试。
实验平台:Windows XP SP3系统,Intel Core 2 Duo CPU(T6400)2.00 GHz,内存2 GB。
实验测试序列:akyio_qcif.yuv、foreman_qcif.yuv、mobile_qcif.yuv,其场景运动快慢鲜明,运动剧烈程度由左到右依次加强。
实验参数设置:Frames To Be Encoded=20,Frame Rate=30.0,Search Range=16,Number Reference Frames=5,其他参数设置为默认值。
3.2 实验数据与分析
本文主要采用Y、U、V各分量的峰值信噪比(PSNR)、运动估计时间(MET)和比特率作为算法性能评判的标准。Y、U、V各分量的PSNR表明压缩后图像的质量,“+”为改善;MET表明运动搜索的时间,“-”为改善;比特率表明压缩率,“-”为改善。改进率=(改进后算法-原算法)/原算法×100%。实验结果比较如表1所示。
从表1中可以看出,改进后算法对Y、U、V各分量的峰值信噪比和比特率影响不大,但运动估计时间减少很显著(从7.4%~20.5%),平均减少了15%。实验中,改进算法对于不同视频序列的运动估计时间的减少幅度不同,主要由视频场景运动的激烈程度不同所造成。视频序列akiyo运动场景相对平缓,起始点预测的精度较高,在早期判断EARLY_TERMINATION时,因为SAD很小,直接跳到步骤(6),也就是说,没有执行对称十字模板步骤(3)和通过自适应搜索长度来降低运算量的步骤(4)和步骤(5)所以运动估计时间减少的效果不是很明显。而对于场景运动一般和场景运动激烈的foreman和mobile序列,由于SAD指标不符合早期判断EARLY_TER-MINATION条件,执行了对称十字模板步骤(3)和自适应搜索长度搜索步骤(4)、(5)、(6),因此运动估计时间减少显著。
本文在结合JM10.1模型的基础上分析了H.264中运动估计算法(UMHexagon S算法),针对该算法的不足之处提出了两处改进。首先,利用对称十字模板9点搜索替换原来的5×5螺旋搜索,减少了64%的搜索点数;其次,利用对象内部代价的相关性提出自适应搜索长度方法。在保证视频序列各分量的信噪比和比特率的情况下,使运动估计时间平均降低了15%,增强了编码的实时性,有利于视频图像实时编码传输的实现。
参考文献
[1]Yang Enhui,Xu Xiang.Rate distortion optimization for H.264 interframe coding:a general framework and algorithms[J].IEEE Transactions on Image Processing,2007,16(7):1774-1784.
[2]毕厚杰.新一代视频压缩编码标准-H.264/AVC[M].北京:人民邮电出版社,2005:33-45.
[3]WIEGAND T,SULLIVAN G J.Overview of the H.264/AVC video coding standard[J].IEEE Transactions on Ciruitsand Systems for Video Technology,2003,13(7):560-576.
[4]CHEN Z,ZHOU P,HE Y.Fast motion estimation for JVT[S].JVT-G016,7th Meeting[C].Thailand,Pattaya II:JVTof ISO/IEC MPEG&ITU-T VCEG,7-14 March,2003.
[5]CHEN Z,ZHOU P,HE Y.Fast integer pixel and fractionalpixel motion estimation for JVT[S].JVT-F017,2002,6thMeeting[C].Awajilsland,Japan:JVT of ISO/IEC MPEG&ITU-T VCEG,2002,5-13.
[6]LAM C H,PO L M,CHEUNG C H.A novel kite-cross-diamond search algorithm for fast block motion estimation[C].Proceedings of 2004 IEEE International Symposium onCircuits and Systems.Canada:IEEE,2004:729-732.
快速运动估计 篇5
市场需求和技术进步共同推动着3G移动视频业务的快速发展, 并使其成为移动运营商、设备制造商和内容提供商等竞相追逐的“杀手锏”业务。目前消费市场对移动视频业务的认可度和期望值都很高, 预计在未来几年内移动视频业务将是推动3G网络发展的源动力。
H. 264 / AVC是由ISO / IEC与ITU-T制定的最新视频编码标准, 具有较高的图像质量、较强的抗误码性和良好的网络亲和性[1]。H. 264 目前已在移动通信、卫星广播、远程监控、电视会议、远程教育医疗、IPTV等领域获得广泛应用[2]。
移动终端设备的处理能力相对PC机来说有很大的差距, 这使得其对视频编解码器的运算量提出了极高的要求。况且H. 264 兼顾从低码率视频通信到高清电视等高码率的广泛应用环境, 在考虑具体应用时, 需根据应用的场景和对象的特点, 对编解码模块进行优化。
运动估计ME ( Motion Estimation) 是视频编码中的一项核心技术。研究表明, H. 264 中运动估计模块的运算量占整个编码器运算量的60% - 90%[3], 并且伴随参考帧数的增加该比重也逐渐增大。因此, 要想降低H. 264 编码器的计算复杂度, 提高其编码速度和图像质量等性能指标, 应首先考虑优化运动估计算法模块, 这也一直是视频编码领域的研究热点之一。
1 快速运动估计算法分析
H. 264 标准最新采用的非对称十字型多层次六边形格点搜索算法UMHexagon S[4 - 6]是目前综合性能最好的快速运动估计算法之一。该算法具有起点预测准确、多样化的搜索模板和搜索方式、采用率失真优化准则等优点, 在很大程度上提高了预测的有效性和鲁棒性。但是UMHexagon S算法没有考虑最佳运动矢量的分布特性, 且它兼顾从低码率视频通信到高清电视等高码率的应用环境, 导致运算复杂度依然较高, 不适合移动终端等特定应用。
资料显示[7，8], 适合硬件 ( 如DSP、ASIC、FPGA等) 实现的快速运动估计算法仍然是比较传统的新三步法 ( NTSS) 、四步法 ( FSS) 、菱形搜索法 ( DS) 以及基于块的梯度下降法 ( BBGDS) 等经典算法。综合比较而言, NTSS搜索速度最慢, 但是对具有大量运动和丰富细节的视频序列效果较好。FSS算法对于缓慢运动的视频序列性能较好。DS算法搜索速度快, 但性能不佳。BBGDS算法的搜索速度最快, 但很容易陷入局部最优, 适用于只含有少量运动的视频序列, 对于含有大运动的序列, 搜索质量明显下降。
针对移动视频通信系统的特点, 近些年许多学者开展了一系列研究。比如张永辉等根据运动矢量的空间相关性提出了一种快速算法[8，9], 适合小中运动的视频序列。毛小明等提出了搜索范围自适应的快速算法[10], 能根据相邻块运动矢量的大小来自适应地调整搜索范围, 以节省不必要的搜索点。Sarwer和张新安等改进了基于提前终止策略的快速算法[11，12], 引入提前终止技术, 虽然速度有很大提高, 但也势必会降低搜索准确度。从测试结果看, 这些算法对细节较少且运动缓慢的视频序列效果较好。纵观国内外最新的研究成果, 这些快速运动估计算法在编码复杂度和率失真性能之间取得了较好的平衡, 但是针对不同运动级别和不同纹理细节的视频序列, 各算法的鲁棒性和普适性都还需做进一步的研究。
2 本文运动估计策略设计
2. 1 块匹配代价准则
块匹配代价准则用于衡量图像块之间的相似程度, 但是据资料显示各种块匹配函数的性能差别并不显著。考虑到移动终端设备的硬件性能, 为了降低计算复杂度, 本文采用运算量最小的绝对差之和SAD ( Sum of Absolute Difference) 作为搜索算法的匹配准则, 其计算公式如下:
其中, mv表示当前块的运动矢量, pmv表示预测的运动矢量, f和g分别表示当前块和参考块的像素值, λ 表示拉格朗日系数, SAD为当前块与参考块之间的绝对误差和。
2. 2 自适应的提前终止阈值
本文提出一种自适应的提前终止阈值ETT ( early termination threshold) , 使其能对不同运动类型的视频自适应地修改阈值, 从而在准确度与速度间达到一个很好的平衡。提前中终策略的基本思想是“找到足够好的匹配块就停止, 而并非要找到最好的匹配块”。在运动估计过程中, 当块匹配代价小于提前终止阈值时, 即认为已经找到了足够好的匹配块, 并终止搜索, 从而提高运动估计的速度。
由于H. 264 中4 × 4 块是物理尺寸最小的宏块划分模式, 且运动矢量也都是以4 × 4 块为单位进行保存和编码。所以本文取相邻4 × 4 块最佳匹配代价Jrefmin的均值作为提前终止阈值ETT , 其定义公式如下:
其中, Jt ( a) 、Jt ( b) 、Jt ( c) 和Jt ( d) 分别表示当前编码块的左边、上边、右上边和左上边等相邻4 × 4 块的Jrefmin。本文提出的自适应提前终止阈值算法的核心思想是将预测矢量的Jmin与该阈值ETT比较来决定是否需要进一步搜索。
本文对每个4 × 4 块的Jmin与提前终止阈值ETT之间的离差分布情况进行了实验统计, 离差分布结果如图1 所示。实验中, 平均每帧的离差数组分布计算公式为:
其中, Jmin表示当前块的最佳匹配代价, ETT表示由式 ( 2) 计算得到的提前终止阈值, N表示编码帧数。
图1 中, “均值”表示相邻块Jrefmin的均值与当前块Jmin的离差曲线, “左块”表示左边相邻块与当前块Jmin的离差分布曲线。从图2 可以看出, 相邻块的匹配代价具有很强的相关性, 相邻块Jrefmin的均值最适合作为提前终止阈值ETT , 且它能根据周围块的匹配情况自适应地调整阈值大小。
2. 3 搜索模板和起始点预测
利用相邻块之间的运动相关性选择一个反映当前块运动趋势的预测点作为搜索起始点, 从预测点开始搜索可以有效提高搜索速度和搜索精度。本文采用中值法来预测搜索起始点, 其基本思想是: 选取左边、上边、右上边运动矢量的中值来预测搜索起始点。实验统计表明, 当前块与帧内左边、上边、右上边的相邻块的相关性最强, 而与其他位置的相关性则较弱。当前编码块运动矢量Vp的预测公式如下:
其中, Vp为当前块的预测矢量, 即预测的运动估计搜索起始点, V1、V2、V3分别为相邻参考块的运动矢量。由于宏块内依照ZigZag顺序先后编码的原因, 未必每个相邻块都已经完成编码, 也就没有相应的运动矢量可作为参考。因此, 如果右上边块不可得, 则用左上边块代替; 其他相邻块不可得, 则放弃选作参考。
2. 4 混合搜索策略
根据表1 的运动矢量相关性统计数据, 周边相邻块的运动矢量场表现出明显的中心偏置特性。在进行运动估计时, 本文根据局部运动矢量的一致性程度, 判断运动趋势的可预测性, 进而采取不同的混合搜索策略。运动趋势分类定义如式 ( 5) 所示, 其中Vpx和Vpy分别代表水平和垂直方向的预测运动矢量。
在初步判定运动趋势后, 便可以根据运动情况选择更合适、更具针对性的运动搜索策略。如果该局部对象的运动矢量场具有连续平滑的特征, 则用小模板配合提前终止策略直接进行精确定位搜索; 如果该局部的运动矢量场表现出一定的分散性, 则采用先快速跟踪搜索后精确定位搜索的混合搜索策略。由表1的运动矢量相关性统计数据可知, 当相邻块的运动矢量相同时, 最佳匹配点就在预测的搜索起始点附近, 本文算法对这种情况直接采用小模板搜索。
表1 的实验数据均采用JM85 全搜索算法编码测试100 帧得到, 表中“相邻相等”指3 个相邻块的运动矢量都相等的概率; “原点”指在相邻块运动矢量相等的基础上, 当前块最终运动矢量就是预测点的条件概率; “1 × 1”指最终运动矢量分布在预测点周边1 个像素范围内的条件概率。
3 本文运动估计算法的混合搜索流程
本文运动估计算法搜索流程如下:
( 1) 首先检测预测的起始搜索中心, 如果其匹配代价小于提前终止阈值ETT , 终止搜索; 否则进行步骤 ( 2) 。
( 2) 平滑区和小幅运动区, 小模板精确定位搜索。若满足max ( | Vpx | , | Vpy | ) < T, 即预测的运动幅度小于预先设定的阈值T, 则表明当前块极有可能是小幅运动。或者满足V1= V2= V3, 即3 个相邻参考块的运动矢量相等, 则表明当前块所在区域的纹理非常均匀, 当前块只需在预测的搜索起始点周围做小范围搜索就非常有可能找到全局最佳匹配块。
因此对这两种情况, 都进行步长为1 的小模板搜索。直至当前匹配代价最小的点为搜索中心, 或此轮搜索得到的匹配代价Jmin小于阈值ETT , 终止搜索。
( 3) 对于大运动, 先进行大模版快速跟踪搜索。继续比较| Vpx | 与| Vpy | 的大小, 判断运动方向。若| Vpx | > | Vpy | , 则表明水平方向的运动幅度要比垂直方向的大, 对当前块进行步长为2 的水平大模板搜索, 直至当前匹配代价最小的点为此轮搜索中心。如果其匹配代价Jmin小于提前终止阈值ETT , 终止搜索, 否则转入步骤 ( 4) 。
( 4) 后进行精确定位搜索。以步骤 ( 3) 搜索得到的最佳匹配点为中心, 进行一次步长为1 的小模板搜索, 所得匹配代价最小的点即为最终的搜索结果。
( 5) 对于| Vpy | > | Vpx | 的情况, 采用垂直大模板进行快速跟踪搜索, 具体搜索方法与水平大模板类同。
4 实验结果与分析
为了测试算法对各类型视频序列的鲁棒性、有效性, 本文选用了小运动、中运动、大运动等不同运动幅度的视频序列进行实验测试。又鉴于移动终端屏幕分辨率较低等原因, 本文都选用QCIF标准大小的测试序列进行实验测试。为了分析比较各算法的技术性能, 本文着重从以下几个指标进行实验比较: 即平均搜索点数ANPS ( Average Number of Points Searched) , 平均运动估计耗时AME ( Average Motion Estimation Time) , 编码比特率 ( Rate) , 平均峰值信噪比 ( PSNR) 等指标。
这些比较实验都是在H. 264 测试模型JM85 的baseline上进行的。JM平台本身是为算法研究提供的统一测试平台, 对于本文研究的运动估计模块, JM也提供了专门的时间统计数据。具体实验参数设置为: IPPP, FrameRate = 24, QP = 30, 5 个参考帧, SearchRange = 8, Use Hadamard = 1, 采用7 种块模式及CAVLC熵编码, Frames To Be Encoded = 70。PC机操作系统为Windows XP, CPU为Pentium Ⅳ 双核3GHz, 2GB内存, 编译软件为Visual C ++ 6. 0。
UMHexagon S指JM采用的非对称十字型多层次六边形格点搜索算法, BBGDS指基于块的梯度下降算法, Proposed指本文算法。运动估计性能提高百分比 Δ 的定义如下:
可以看出, Δ 为正表示该项指标性能有提高, Δ 为负表示该项性能有下降。其中, AMEref指UMHexagon S和BBGDS等参考算法的每帧平均运动估计时间, AMEproposed指本文算法的每帧平均运动估计时间。Δ ( U/P) 是指UMHexagon S算法和本文所提算法的性能比较, Δ ( B/P) 是指BBGDS算法和本文算法的性能比较。
表2、表3 和表4 都是各算法对不同运动类型的视频序列前70 帧的测试结果。Mother&daughter序列背景简单, 人物运动幅度不大, 属于小运动序列。News运动变化中等, 运动形式丰富, 画面有多个运动物体, 空间细节比较丰富。Foreman序列运动较快, 既有镜头的运动, 也有物体的运动, 且背景较为复杂。
表2、表3 和表4 的实验测试结果可知, 对于不同运动幅度和画面细节的视频, 本文算法在不同量化系数下都能保持优异的编码性能。按搜索点数 ( ANPS) 计算, 本文算法比其他快速搜索算法节省46. 2% ~ 75. 0% ; 按平均运动估计耗时 ( AME) 计算, 本文算法比其他快速搜索算法减少耗时33. 0% ~ 55. 0% 。与此同时, 本文算法的率失真性能几乎没有下降; 对Foreman序列, 本文的率失真性能甚至比UMHexagon S和BBGDS算法还要好。可见本文算法在各种情况下都能保持与UMHexagon S算法持平的编码性能, 而搜索点数和运动估计耗时大幅下降。
在本文算法中, 运动幅度区分阈值T的选取也是一个很重要的问题。使用阈值T的优点在于, 对不同运动幅度的视频序列可以通过设置阈值T来改进算法性能, 将会有助于加快搜索速度。根据大量实验测试结果证实, 当T = 3 时, 运动估计算法综合性能最佳。
图3 是各算法每一帧编码的PSNR比较, 可见本文算法编码图像的客观质量非常稳定、可靠, 平均PSNR与UMHexagon S算法相当。图4 是在不同量化步长下, 各算法的整数像素运动估计耗时比较。从图4 可见, 本文算法在不同量化系数下都能大幅降低运动估计耗时, 即大幅提高了编码速度。
图 3 各算法对 Foreman 序列编码，每帧的 PSNR 比较
图 4 不同量化步长下，各算法运动估计耗时比较，Foreman 序列
表2、表3 和表4 以及图3 和图4 的这些测试数据都充分说明, 本文算法对于大、中、小各种运动类型的视频有很强的自适应性, 率失真性能保持或者略优于其他算法, 但是运动估计的计算量得到极大降低。与UMHexagon S算法相比, 本文算法最多可以降低75% 的搜索点数, 最多可节省55% 的运动估计耗时, 平均节省52. 9% 的运动估计时间。
5 结语
本文分析总结了快速运动估计算法的典型研究成果, 剖析了可视电话等典型视频业务的特性, 针对移动终端硬件设备的性能特点, 提出了一种高性能、低复杂度的快速运动估计算法。该算法根据局部运动矢量的分布特性来判断运动类型的可预测性, 进而自动选择不同的混合搜索策略; 再结合自适应的提前终止阈值, 在保证精度的同时, 大幅度提高了搜索速度。实验结果表明, 本文算法获得了良好的率失真性能、有效降低了计算复杂度, 是一种具有高性能、低复杂度、高鲁棒性的快速运动估计算法。
摘要：针对移动终端硬件计算能力不足的问题, 提出一种高性能、低复杂度的运动估计算法。算法根据相邻块运动矢量的分布特性, 判断运动趋势的可预测性, 进而自动选择不同的混合搜索策略;再结合自适应的提前终止阈值, 在保证搜索准确性的同时, 大大减少了搜索点数。通过对各种类型的视频进行测试, 结果表明, 该算法对于不同运动类型、不同运动程度的视频序列都具有较强的自适应性, 分别比UMHexagonS (Unsymmetrical-Cross Multi-Hexagon Search) 和BBGDS算法节省55%和35.6%的运动估计时间, 同时率失真性能保持不变。
关键词：移动终端,运动估计,提前终止,混合搜索,自适应
参考文献
[1]Peng Q, Zhang L, Yang T W, et al.Key-frame Reference Selection for Non-Feedback Video Communication[J].The Journal of China Universities of Posts and Telecommunications, 2009, 16 (5) :92-102.
[2]ITU-T Rec.H.264/ISO/IEC 11496-10.Advanced Video Coding Final Committee Draft, Document JVT F100d2[S].Awaji island, Dec.2002.
[3]Zhu S P, Tian J.An Iimproved Fast Fractional Pel Motion Estimation Algorithm Based On H.264[C]//2010 IEEE International Conference on Industrial Technology.Washington, DC:IEEE Press, 2010:179-182.
[4]刘鹏宇, 贾克斌.基于UMHexagonS的快速运动估计编码算法研究[J].电路与系统学报, 2012, 17 (5) :139-146.
[5]刘易, 李太君.H.264中快速运动估计UMHexagonS算法的改进[J].电子技术应用, 2011, 37 (8) :128-130.
[6]黄平, 王绍源.基于子区域最佳运动矢量搜索的UMHexagonS改进算法[J].计算机应用研究, 2011, 20 (10) :59-62.
[7]阴法明, 赵晓铃.用于运动估计的基于梯度下降搜索扩展算法[J].计算机工程与应用, 2010, 46 (33) :139-141.
[8]张永辉, 李临生.一种适用于可视电话的快速运动估计算法[J].微计算机信息, 2010, 26 (3) :217-219.
[9]李强, 孙瑞杰, 于游, 等.一种用于移动可视电话编码的运动估计快速搜索算法[J].重庆邮电大学学报:自然科学版, 2011, 23 (5) :593-596.
[10]毛小明, 鲍可进.一种基于H.264/AVC的高性能快速运动估计算法[J].计算机应用研究, 2012, 29 (4) :1598-1600.
[11]Sarwer M G, Wu Q M J.Adaptive Variable Block-Size Early Motion Estimation Termination Algorithm for H.264/AVC Video Coding Standard[J].IEEE Trans on Circuits and Systems for Video Technology, 2009, 19 (8) :1196-1201.
快速运动估计 篇6
H.264具有低码率、高画质、高压缩比等特点, 但是其高效的压缩比是以增加编码算法复杂度为代价的, 经对编码器各模块在整个编码过程中的耗时比例分析可知, 运动估计部分占用了近70%的编码时间[1], 因此要对整个编码器进行优化, 必须对运动估计模块优化。
监控视频一般具有背景相对固定不变, 前景变化内容较少, 场景相对稳定的特点。采用一般的运动估计算法时, 按照正常的搜索步骤和计算时就会浪费大量的搜索时间和计算时间。本文针对经典运动估计算法在实际应用中的存在的问题, 并结合监控视频的特点, 提出了一种适合视频监控图像的快速运动估计算法。
1 编码方案
H.264编码端采用多参考帧对编码效率只有有限提高, 但却大大增加了编码的复杂度。内容自适应二进制编码算法 (CABAC) 能够节省一定的比特率, 但是需要比统一可变长编码 (UVLC) 更多的计算量和存储容量 (最多40%) ;采用双向预测技术不但增加计算量和存储容量, 还增加了时延[2]。在实际应用中要更多地考虑降低编解码的复杂度, 因此, 本文中不采用多参考帧、B帧和CABAC。
H.264仅仅对编码后的码流结构及解码器做了标准化, 对编码器各部分的具体实现方法未作规定, 目前业内比较流行的开源编码器有三种:JM, X 264及T264。本文选取测试代码JM模型。Profile选取BaselineProfile, 使用快速运动估计算法, 测试序列的图像格式是QCIF, 均采用IPPP帧结构。量化步长在30左右选取 (太小压缩比太小, 码率过大;太大图像质量会受到影响) , 搜索范围设置为16。
2 基于监控视频的快速运动估计算法
采用全零块预判算法和提前终止算法相结合的方法, 在运动搜索之前将编码块分为全零块、运动剧烈块、运动中等块和运动缓慢块。对于全零块直接跳过, 对于运动剧烈块, 运动中等块和运动缓慢块分别采用不同复杂度的搜索算法。算法的流程图如图1所示。
本算法采用空间域和时间域两种方式来进行运动矢量预测, 时间域方式采用前帧对应块运动矢量预测方法, 空间域方式采用运动矢量中值预测和空间域的上层块模式运动矢量预测方法。在三个预测矢量中找出最小cost所对应的预测矢量, 作为下一步搜索的起始位置。
使用绝对差和 (SAD) 标准作为匹配准则[3], 如下所示:
其中 (i, j) 为参考帧中的匹配块相对于待匹配块的位置, fk (m, n) 和fk-1 (m+i, n+j) 分别表示当前帧及参考帧的象素灰度值, Qstep为量化步长, SAD 16表示每个4×4块计算的绝对差和, max (SAD 4) 表示一个4×4块最大的SAD值。
根据式 (1) 计算SAD的值。如果一个宏块满足式 (2) 、式 (3) , 根据SAD判断出全零块[4], 直接跳过不进行搜索及离散余弦变换 (DCT) 变换、量化等操作。
设置两个阈值TH 1、TH 2, 分别取TH 1=7 280、TH 2=1 250。根据设置的阈值对剩余的块进行判断并提前结束运动搜索, 并将剩余块分为运动剧烈块、运动中等块和运动缓慢块。对于运动剧烈块采用非对称十字型多层次六边形格点搜索 (UMHexagonS) 算法[5]进行计算, 以达到最佳的效果;对于运动中等块采用菱形搜索[6], 对运动缓慢块采用正方形搜索[7]。在不影响视频效果的前提下可以节省搜索时间。
3 算法的性能分析
3.1 视频质量分析
本文选取了标准测试视频序列中的Akiyo (纹理复杂度一般, 只有画面人物运动) , Claire (背景纹理简单, 只有画面人物运动) , Carphone (运动剧烈, 背景人物都发生运动) 三个典型的QCIF格式的标准序列进行测试, 量化步长QP=25, 28, 36。下面为每个序列第四个P帧在不同QP时的解码帧的对比图。
从解码帧可以看出, 在QP=25时, 各个序列的解码帧基本与原始帧的质量相同;在QP=28时, Akiyo和Claire的解码图像良好, Carphone的解码图像有一定的影响;Carphone的解码图像已经明显有干扰;当QP=36时, Akiyo和Claire的解码图像也明显有干扰, 但Carphone的解码图像已经被严重干扰, 无法让人接受。
从上面三个序列的比较可以得出结论:采用此快速运动估计算法的编码器编码, 适合背景相对稳定、前景变化不很剧烈的视频监控系统, 在背景和前景变化都剧烈的视频图像中也可以得到应用, 只是相应的量化步长不能取值过大。
3.2 算法的性能分析
取标准测试视频序列中的Akiyo、Claire和Carphone三个典型的QCIF格式的标准序列, 在编码器中采用UMHexagonS算法和本文算法分别进行测试。帧数为150帧, 帧结构为IPPPP, 表1-3中的数据是不同测试序列在不同QP条件下所得到的图像的峰值信噪比 (PSNR) 、图像的编码时间和运动估计 (ME) 时间。
从表1、表2、表3的数据比较得出, 对于不同测试序列和不同的量化参数, 采用本文算法处理图像的PSNR值只比采用UMHexagonS算法的略有下降, 编码后的比特率基本没有变化, 运动估计时间提高50%以上, 编码速度提高在35%以上。由此可以得出此算法是可行的。
从实验数据也可以看出, 对于前两个运动不剧烈的测试序列, 该算法具有很好的效果, 对于运动剧烈的图像, 该算法在相同量化步长时达不到很好的效果。由此可以得出该算法适合运动变化相对较少的监控视频, 可以在监控视频的编码器设计中得到应用。
4 结论
本文结合监控视频的特点, 提出了一种适合监控视频的运动估计算法。算法采用全零块预判算法和提前终止算法结合, 将编码块按运动情况分成不同的块, 并对不同运动块采用不同的搜索算法。从不同测试序列的解码帧图像对比, 可以得出此算法是一种适合背景变化缓慢, 前景物体较少的监控视频的快速运动估计算法, 在运动剧烈的视频中也能得到较好的结果。通过对比此算法与UMHexagonS算法处理相同序列的峰值信噪比、图像的编码时间和运动估计时间等指标, 可以看出本文算法在PSNR值少量下降码率基本不变的情况下, 运动估计时间明显减少, 编码速度明显提高。从视频质量和算法的性能两方面综合可以得出此算法是一种适合在监控视频中应用的快速运动估计算法。
摘要：针对H.264视频编码过程中运动估计所占时间大的问题, 采用全零块预判算法和提前终止算法相结合的方法, 提出了一种适合视频监控图像的快速运动估计算法。此算法可以在保证图像质量的前提下降低动估计占用的时间, 提高编码速度。
关键词：H.264,运动估计,监控视频
参考文献
[1]李静.H.264运动估计算法在会议电视中的应用研究.广州:广东工业大学, 2008
[2]关凌涛.基于DSP的快速运动估计算法应用研究.大庆:大庆石油学院, 2009
[3]古勇军, 吴乐华, 穆巍炜.基于DM642的运动估计算法的研究与实现.微计算机信息, 2008, 24 (3-2) :204—204
[4]张芙蓉.DM642监控视频H.264编码器的实现和优化.杭州:浙江大学, 2006
[5]吴晓军, 白世军.卢文涛.基于H.264视频编码的运动估计算法优化.电子学报, 2009;37 (11) :2541—2545
[6]廖泰敏, 郭宗明.十字菱形六角形优化搜索算法.中国图象图形学报, 2009;14 (8) :1530—1533
一种相干目标角度快速估计算法 篇7
传统的DOA估计算法有很多,如最大似然法、子空间拟合法、MUSIC法,ESPRIT法,其中MUSIC法和ESPRIT法已经成为DOA估计中经典的方法。ESPRIT算法的计算复杂度远小于MUSIC算法,因此ESPRIT更实用。但是,常规的ESPRIT算法需要得到信号子空间,必须进行矩阵的分解,在有相干信源时,还需要额外的算法,才能估计波达方向。
多级维纳滤波器[2]是Goldstein等人提出的一种有效的降维技术。与主分量法(PC)[3]和互谱法(CS)[4]等降维技术相比,多级维纳滤波器具有很多优点,如允许MSWF的级数远远小于信源数,可以应用在小样本支撑的信号环境中,收敛速度快,能够对时变信号进行快速跟踪,不用对协方差矩阵作特征值分解,使得其运算量大大降低,因而引起了学者浓厚的研究兴趣并得到广泛应用[5,6,7,8]。
在进行信号阵列处理时,必须要解决相干信号角度的估计问题。最初的办法是通过空间平滑来达到解相干的目的,但是此类算法降低了系统自由度且计算量较大。目前针对相干信号源的非降维类处理算法有很多[9,10]。文献[9]、[10]通过构建Toeplitz矩阵,实现了DOA估计,提高了估计性能,不损失阵列孔径。但这类算法计算量仍较大,主要是因为特征值分解。
本文为了实时估计相干信源的波达方向,提出了一种新算法,将多级维纳滤波器引入ESPRIT算法的预处理,通过构造Toeplitz矩阵,得到信号子空间,并结合ESPRIT算法得到波达方向。该算法计算复杂度低,能快速估计信号的DOA,具有一般性。
1 信号模型
如图1所示,假设有个窄带信号(P<L),为远场点目标,入射角度为θi(i=1,2,L P),波长为λ。均匀线阵阵元间距为d,阵元个数为L。则阵列接收矢量可以表示为
x(t)、S(t)、n(t)、A分别为阵列输出矢量、入射信号矢量、阵列噪声矢量和阵列流型矢量,假设n(t)服从零均值,方差为σ2的复高斯白噪声。且有
2 DOA估计算法
2.1 预处理结构
首先要构造维纳滤波器的预处理结构,本文构造的Toeplitz矩阵,与一般的估计协方差矩阵所用的计算量相同,没有增加多余的运算量,并且构造的Toeplitz矩阵的秩等于信号源个数,不存在秩亏损情况,能够起到解相干的目的,再把构造的Toeplitz矩阵作为多级维纳滤波器的预处理部分。
文献[10]证明,利用接收数据构造的Toeplitz矩阵的秩等于信号源个数,不再受信号相干性的影响,仅和入射信号的个数有关。构造的Toeplitz矩阵如下:
2.2 求信号子空间
1)子空间的估计算法。
多级维纳滤波求解信号子空间的主要原理是:对观测数据进行正交空间投影,一个子空间是通过参考信号di(k)与观测信号Xi(k)的互相关向量得到的称为信号相关空间,另一子空间正交于这个子空间。然后把观测数据投影到信号相关空间得到新的参考信号,投影到另一子空间得到新的观测数据,然后按照上述方法继续投影。互相关向量只能提取di(k)和Xi(k)相关的信号分量,由于信号是相关的,而噪声则是无关的,因此互相关向量只提取了信号分量rX0d0,噪声分量对互相关向量是没有贡献的。因此,通过不断的投影,信号分量将被全部提取,di(k)和Xi(k)只包含噪声,达到把信号和噪声分离的目的。
多级维纳滤波器,只需要各级数据Xi(k)和di(k)参考信号估计互相关向量rX0d0,并且只有标量求逆(倒数)运算,因此多级维纳滤波器的计算量较小,特别是对大型阵、协方差矩阵求逆计算量较大时,多级维纳滤波器可有效降低计算量。另外,MSWF很容易应用降秩处理,将多级维纳滤波器在r级分解处截断,得到降秩MSWF。
具体步骤如下:
2)信号子空间的估计。
1:确定信号子空间估计所需的滤波器级数。
根据信噪比的高低调节多级维纳滤波器的级数,通过如下语句可以判断:
2.3 DOA估计
2.4 算法步骤
步骤1:根据式(13)构造Toeplitz矩阵;
步骤2:将2.2节初始化中公式的矩阵代替为步骤1中构造的Toeplitz矩阵,再通过余下过程得到信号子空间;
步骤3:根据2.3DOA估计方法,通过ESPRIT算法得到信源的波达方向。
2.5 算法的计算量分析
下面对本文算法(方法1)、文献[10](方法2)进行分析和比较。
方法1的计算量:①通过数据估计协方差矩阵的计算量为NL2②从3.2节的求解过程中可以看出多级维纳滤波器一次前向递推所需的计算量为2L2+2L,共有P次前向递推,因此,所需的计算量为NL2+(2L2+2L)P。
方法2的计算量:①通过数据估计协方差矩阵的计算量为NL2;②对得到的协方差矩阵作对称QR迭代计算得到三对角阵[11],其计算量为8L3/3;③对三对角阵做Givens旋转得到对角阵,计算量为3L3+L3-4L;④将对称QR迭代所得到的变换矩阵和旋转矩阵相乘,以得到特征向量矩阵,其计算量为L3。由此可知,基于协方差矩阵特征分解估计噪声子空间所需的计算量为NL2+20L3/3+L2-4L。
3 实验仿真
从图2、图3、图4中可以看出,不论对于不相干,全相干还是部分相干信号,本文算法都能估计出正确的角度,证明了本文算法的有效性。本文算法通过构造Toeplitz矩阵达到解相干的目的,不需要额外操作,且直接利用MSWF得到子空间,避免计算量较大的矩阵分解过程,在保证算法性能的前提下,极大的降低了算法计算量。
实验2本文算法、文献[10]算法及空间平滑算法估计结果及性能比较
三个波长为λ的信号的全相干信号,入射角度为-45°,-30°,60°,阵列个数L=8,信噪比从0d B变化到25d B,M=100,比较三种算法的RMSE,仿真结果如图5。
由图5可以看出,本文算法与文献[10]算法的RMSE相当,低于空间平滑算法。说明本文算法在运算量较低时能达到与文献[10]相同的性能。本文算法与文献[10]算法的性能都高于空间平滑算法,这是因为空间平滑算法在解相干时,会造成孔径亏损,而本文算法与文献[10]算法通过构造Toeplitz矩阵达到解相干的目的,没有造成孔径损失,算法的性能较好。
实验3两种算法的计算量的比较
设快拍数为N=256,阵元数L在8至25之间改变,P=3,仿真结果如图6。
从图6可以看出,随着阵元数的增大,本文算法的运算量会远远小于文献[10]算法的运算量,因为本文算法不需要矩阵分解,计算量较低,特别是适用于高纬度矩阵,因此适合于大阵列天线。
4 总结
本文针对均匀线阵估计相干信源实时性问题,提出了一种基于多级维纳滤波器的相干信源估计算法。首先,通过构造Toeplitz矩阵作为去相干结构,达到了解相干的目的。将多级维纳滤波器引入ESPRIT算法的预处理中,多级维纳滤波器是一种有效的降维算法,可以得到信号子空间,避免了协方差矩阵的分解。本文提出的算法,不通过特征值分解,能够实时估计相干信源,且本文算法,适合于基于子空间方法的一大类DOA估计。
参考文献
[1]Puska H,Saarn Isaarih Inattij.Serial Search Code Acquisition Using an Art Antennas with Single Correlator or Matched Filter[J].IEEE Transations on Communication(S0090-6778),2008,56(2):299-307.
[2]Schmidt R O.Multiple emitter location and single parameter estimation[J].IEEE Trans AP,1986,34(3):276-280.
[3]Goldstein J S,Reed I S,Scharf L L.A multistage representation of the wiener filter based on orthogonal projections[J].IEEE Transactions on Information Theory,1998,44(7):2943-2959.
[4]Hotelling H.Analysis of a complex of statistical variables into principal components[J].J.Educ.Psychol.,1933,24:417-441,498-520.
[5]Goldstein J S,Reed I S.Reduced rank adaptive filtering[J].IEEE Trans.Signal Processing,1997,45:492-496.
[6]包志强.快速稳健的参数估计及波束形成技术研究[D].西安电子科技大学,2006.
[7]于红旗,黄知涛,周一宇,等.一种不需要特征值分解的MUSIC方法[J].国防科技大学学报,2007,29(4),91-94.
[8]黄磊.快速子空间估计方法研究及其在阵列信号处理中的应用[D].西安:西安电子科技大学,2005.
[9]梁浩,李小波,王磊.采用单次快拍数实现信源DOA估计[J].数据采集与处理,2013,28(1),58-63.
[10]唐玲,宋宏,陈明举,等.基于Teoplitz矩阵重构的相干信源DOA估计算法[J].航天电子对抗,2010,26(4):15-17.