UMHexagonS算法的优化研究

ISSN 1009-3044E- mail: edufccc.net.cnComputer Knowedge and Technology电脑知识技术htp://ww .dnzs.net.cnVal.6,No.10,April 2010, p.24444 2445.2448Tel:+86- -551- -5690963 5690964UMHexagonS算法的优化研究宫婷婷,王民(西安建筑科技大学信控学院,陕西西安710055) :摘要:视频编码标准H.264已经正式采纳了UMHexagonS算法作为整像素的快速运动估计算法。文章对UMHexagonS算法进行了介绍,对其特点进行详尽分析后,提出了一种改进方法,即在预测起点处增加一个内容自适应的中止搜索阈值判斯,以判断是否可立即结束搜索。模拟实验表明,相比原算法,在基本保持了原算法的的编码效果,还明显减少了搜索点减少了运动量,从而节省了编码时间。关键词:H.264;运动估计;UMHexagonS算法;提前终止中图分类号:TP311文献标识码:A文章 编号:1009- 3044(2010)10 2444224Research and Optimization of UMHexagonS AlgorithmGONG Ting- ting,WANG Min(Architecture and Technology University, Xi'an 710055,China)Abstract: The video coding standards H.264 have adopted Unsymmetrial cross Muli Hexagon grid Search (UMHexagonS) algorithm forinteger pels motion estimation. However, further investigation on fast motion esimation method is still necessary. In this paper, based on thestudy of the principles of the UMHexagonS algorithm, an improved method is proposed, in which the idea of a new adapive facor is intro-duced in initial search point prediction step for early termination. Simulation Results show that the improved UMHexagonS algorithm canreduce search points with minimal loss in bit -tate and reconsructed quality compared with those of the original UMHexagonS algnthm.Key words: H.264; motion estimation; UMHexagonS algorithm; ealy terminaionUMHexagonS算法-2是H.264标准所采纳的运动估计算法之一,全名为“非对称十字型多层次六边形格点搜索"。相比于全搜索算法,该算法在保持较好的率失真性能的同时,可以节约90%以上的运算鼂吗。本文对UMHexagonS快速搜索算法做了系统的分析,提出了引进调节因子Bsw,并在原算法的预测起点部分增加一个自适应的终止搜索判断,在保i证原算法良好的半失真特性前提下,降低了运箅量.从而提高了H.264 的编码效率。1 UMHexagonS算法1.1 UMHexagonS算法简介UMHexagonS算法包括4步不同种类的搜索过程.其基本步骤如下:第一步:多种预测模式进行初始搜索点预测.包括:1)中值预测;2)原点预测;3)上层块预测;4)前帧同位置块预测;5)相邻(多)参考帧预测。对以上运动矢量所指向的点进行搜索.获得当前最优预测起点。第二步:进行混合搜索.包括:1)非对称十字搜索;2) 5x5余搜索;3)扩展的多层次六边形格点搜索。第三步:满意区的快搜索.以当前最优点为中心,用六边型模板进行搜索.直至最优点在六边型的中点为止。第四步:很满意区的块搜索.以当前最优点为中心.用小菱形模板进行搜索.直至最优点在:小菱形的中点为止。UMHexagonS算法依靠每个搜索步骤后的SAD(绝对误差和)指标或者mincost参数门限来判断搜索精度.跳转到相应的搜索算法进行循环,或者提前终止。1.2 UMHexagonS算法特点1)多尺寸运动估计:H.264采用了7种块尺寸的块匹配".通过逐渐减小的过程来实现由粗到细的运动估计,从而获得可靠性高.一致性好的运动矢量场。但是以相应的提高了计算复杂度。2)基于内容的自适应搜索模板和搜索)i式:UMHexagonS算法每步的搜索都与图像内容有关。其搜索模板和搜索方式分为三类:大范围的混合模板、细搜索的六角形模板精细搜索的十字模板,对于内容程度不同的块选拌不同的搜索模板。3)起点预测:由于综合了H.264)的宏块划分技术所带来的不同尺寸的运动矢鼠相关性,以及帧内帧间的运动矢量相关性,故可以选出最能反映当前运动趋势的点作为搜索起点。4)匹配准则:H.264采用率失真最优化(Rate Distorion Opimization)准则则，在保证目标数据率的条件下传输的视频信号失真最小。率失真控制机制为:中国煤化工YHCNMHG收稿日期:2010-01-27作者简介:宫婷婷(1984-),女,陕西西安人,西安建筑科技大学硕士研究生,研究方向为数字娱乐与多媒体通信;王民,副教授,研究.方向为控制理论与控制工程,信号与信息处理。2444..人工智能及识别技术....本栏目责任编辑:唐一东.第6卷第10期(2010 年4月)Computer Knowledge and Tchnoloy电腈知识与技术jewex(m,REF | )men )=SAD(s,c(REF.m)+ xa"(R(m-p)+R(REF),(1I式中: M=M,My)"为运动矢量,REF参考帧图像,P=(PxPy)为预测的运动矢量,入mmn为拉格朗日乘数因子, R(m-p)为运动矢量差值比特数,SAD为绝对误差之和。2基于UMHexagonS的改进方法UMHexagonS算法中SAD具有很强的相关性，因此将运动矢量MVpred,即p .MVpred. up .MVpred. _ref 所指向点的率失真值分别称为Pred. space. mincost .Pred. uplayer. mincost .Pred. _ref mincost, 作为当前mincost是否足够准确的标尺,使用阈值判断公式判断此处属于不甚满意还是满意或很满意区,并跳到相应的二步或第三步或第四步。故在UMHexagonS算法中第步与第四步上,都是以“最佳点在模板中心”为准则来判断是否最优.是否可结束搜索。也就是说,即使所得点已经是最佳点，却仍要按模板搜索-到两轮才能结束搜索,而这些点数都是浪费的。尤其对高准确率的起点预测而盲,开始就找到最佳点的概率较大,则浪费在该结束而术结束搜索上的点数也就不可小视。例如:30帧的carphone 序列.根据统计其有76.1%的点在第一步预测后就直接进人第三步或第四步,而这其中的96.1% .95.8%的点已经找到最佳点，但仍需要在搜索4或10个点才能结束搜索。在第一步预测部分再增加一个与内容相关的自适应阈值,以判断是否叮立即结束搜索。在UMHexagonS算法中,基本判断方法为":设当前最佳值为mincost(含义见式():.min cost>(1+Px)' pred - mincost判为不满意(1+ rmra) pred - mincost < mincostr(l+ Psm). pred - min cost判为较满意mincost<(1+βn _)xpred_ mincost判为满意其中调节因子为:Bsitel[locknpe]-ase [blocknpx]Bnms=Bsrblockpepred_ mmcosrpred_ mmcost'数组Bsize为当前块尺寸; "Sec ."Third为常数组,其值的选取诸见文献[7]。判断找到的点是否满意的方法有两种:这里称作A类判断与B类判断。在A类判断中，与mincost作比较的pred. minct=ped. uplayer_ mincost,仅用在第一步中的由MVpred. _up所指向的点求出比特率mincost后进行;其余地方的判断都使用B类判断。B类判断的pred. _mincost 则视情况而定:1) 若参考帧的ref不为O,pred. _incst=pred. -ref mincost2)若ref为0:(目) blocktype为16x16,则pred. _mincost =pred-space- -mincost(b) blocktype不为16x16, 则pred_ umincost =pred-uplayer-mincost笔者将各类标准序列在第一步中进行判断 而进入第二步、第三步,第V四步的点按blocktype的不同归类.并进行了大量的数据分析。提出改进方法如下:在第一步的使用A类判断的地方,冉增加一个类似B类判断的.内容自适应的新阈值来判断是否叮停止搜索(考虑到判断本身的耗时，只在预测准确率敢商处增加该停止判断): mincost<(1 +Bs )xpred_ mincot, 则判为可停止搜索，其中pred_ mincost 取B类判断中的pred. .mincostoPsm =Bse[bocktype]age[blocktype]pred min cost2根据实验数据,按其概率分布规律,本文将"Stoplblocktype]取值选为:(sJ)-=.303;s[)-0-33:;5@q313033a:3,4)a0.27;,[5]=.1;as,[6J=0.13 ;a1[7]--0.44将上述改进引入UMHexagonS算法之后结果表明.在对比特率、图像质放均影响不大的前提下,可比原UMHexagonS算法减少10%到30%的搜索点数。3实验结果与分析表1两种算法搜索点数的比较利试序列重算法改迎算去搜素卤数为验证改进算法的有效性,将该算法在H.264标准代码JM12.2Mobole sT220505657”” ””194 860435的测试模型下进行。实验参数匹:按照PPP序列类型编码;5个参n OCF”灌少29.44.04851061.10 28111考帧;7种搜索模式:搜索范围为16像素;量化系数为28.32.36 ,40 ;Trevos. QCF40662 731减少16.28。16456472帧率为30Hz;使用率失真优化和ME哈达码变换。执行平台:CPUAltyo. QCF2645647218668 167减少14.89。25799 6441"863 372减少11.63-。Intel (R) Celeron (R) 2.00 CHz ;内存(RAM) 768 MB。由表1可见改进算法较有效地降低了搜索点数,特别对于大表2两种算法平均比特率(kbits)的比较运动序列效果更为明显,减少点数可达30%之多。利速字列改理后放变室为改善)由表2可看出改进后的算法编码产生的比特数变化较小,故Mobile. soF1602.40’”160191.00560%126.03126-4+0.5*19。对运动估计的准确性影响较小。中国煤化工.0.0C10.0表3说明了改进算法和UMHexagonS算法的率失真性能网几乎-0.0-0.427%是一样的,即改进算法没有减少准确率对图像质量影响很小。。MYHCNMHG-4结束语本文对H.264所采用的UMHexagonS算法进行了一定的分析.并在原算法基础上,提出了改进的优化(下转第2448页)本栏目责任编辑;唐-东.....人工智能及识别技术. 2445Computer Knowledge and Technoloy电腾知识与技术第6卷第10期(2010年4月)所示:表3备选方案量化指标利用训练过程得到的SVM模型,将待评估的方案指标作为输人,输出层得到的方高序号4| 44人输出数据作为方案评估的结果。得出以下评估结果:0707口o表4作战方案 评估结果脚05 0050.3将选方高4 4| 4|016707结果0.7089 I 0900 0.014 0.6909 」B安全性十T十070↑门结果表明在考虑装备、人员等客观条件的情况下，作战方案A更符合实际情兄。因此在最后的决策中选择方案A1。.B狐动性07 0705↑007004结论传统的方案评估主要是由专家参与评定,其结果含有主观因素。基于SVM的作理战方案评估方法.弥补了专家评定法的不足,通过训练样本的学习获得专家的经验岛的既重配力07 0507 0和知识.并利用所获的经验和知识解决相应问题.从而降低评估过程中人为因素,具I 107C7T 1有客观性。品动雄o030707参考文献:雄HB可性个070507[1]王静岩,郑建军,吴裕树.一种基于神经网络的作战方案评估方法[J].军事运筹与系品安姓十703 07统T程学205,19():57-61.品吸性叶T7o[2]谭东风.指挥信息系统导论[M],湖南:国防科学技术大学,2007:65 -70.[3]范昕炜.支持向最机算法的研究及其应用[D1.杭州:浙江大学,2004.马业对口概驶5050s03[4]边肇棋,张学工.模式识别[M].北京:清华大学出版社200:.2030- 210.[5]白鹏,张喜斌.支持向量机理论及工程应用实例[M].西安:西安电子科技大学出版洁B人员制情备的慢控能力T 070707 0↑杜,2008:13-20.0T070[6] Tax D,Duin R. Support vector domain decripionpJ].Pat tem Recogniton Ltters1999(20):1191-1199.T050305 05[7] Tax D,Duin R. Support veetors data deseription[J.Machine Leanmin.20045):45-66.07070 0[8]王文胜,刘奎,王治德.作战方案评估专家系统的设计与研究J.沈阳航空工业学院学报,2004,21(3).B力调重理07070707(上接第2445页)表3平均峰值信噪比运动估计算法。改进算法在对运动估计准确性和图像质量的影响测试中到PSIRdBT .三工本文夏去吕克革 ”为改善，-0 029*。不大的前提下,大大减少了原算法中不必要的搜索点数,从而降低(SIF)了编码器端的运动估计耗时,提高了编码器的编码效率。-0.0289.36.18Formo-0.02.4211019号[1] JVT2F017, Fast Integer Pel and Fractional PelMotion Estimation520-0.069Thevo3896forJVT[S].(QCIF)[2] JVT2P021, Imp roved and Simp lified FastMotion Estimation forMotber-0219.JM [S].(QCF)-013*.[3]李红叶刘明军.H.264运动估计算法研究[J].济南大学学报:自然-0.029.科学版,2009,23(1):72- -76.Aliyo3985-0028[4]毕厚杰新- .代视频编码压缩标准- H.264/AVCM]北京:人民邮-0029元电出版社2005.[5] Cote G, Eml B, GallantM, et al. H. 263 + : video coding at low bit rate [JIEEE Trans on Cireuit and Syslems for Video Technology,1998,8(7):849 -866.[6] Hye- Yeon Cheong Tourapis, Alexis Michael Tourapis, Pankaj Topiwala. Fast Motion Estimation wihin the JVT codec [C]In: JVT-E023, 5th Meeting: Geneva, Switzerland, 2002- 10[7] Zhibo Chen, Peng Zhou, Yun He.Fast Motion Estimation for JVTC].In:JVT中国煤化工[8]马兰,沈笑云,万棣.精逋Visual C++视频/音频编解码技术[M]北京:人民MHCNMH G[9]佟雨兵,张其善,祁云平.基于PSNR与SSIM联合的图像质量评价模型J中国图家图龙子报，2006,11(12):1758- 1759.2448 ..人工餐能及识别技术...本栏目责任编辑:唐一东