用于运动估计的全新自适应一步一次搜索策略

用于运动估计的全新自适应一步一次搜索策略 用于运动估计的全新自适应一步一次搜索 策略 ComputerEngineeringandApplications计算机工程-9应用2007,43(11)219 用于运动估计的全新自适应一步一次搜索策略 王红.乔永强,王松梅 WANGHong,QIAOYong-qiang,WANGSong—mei 北京微电子技术研究所.北京100076 BeijingMicro-electronicsTechnologyInstitute,Beijing100076,China E-mail:wh_ franky@126.com WANGHong,QtAOYong-qiang,WANGSong-mei.Noveladaptiveoneatatimesearchstrategiesformotionestimation. ComputerEngineeringandApplications,2007,43(11):219—221. Abstract:Inthispaper,severalnovelsearchstrategiesusedintheproposedOTA(oneatatimealgorithm)areproposed;actual- ly,allthesesearchstrategiescanbeusedinotheralgorithms.Thesesearchstrategiesincludenewadaptiveterminationthreshold, MotionVector(MV)prediction,zeroMVpriorityandsearchtemplates.Extensivestandardtestsequenceshaveshownthatthepro- posedsearchstrategiesandalgorithmisveryeffective,robustandadaptive.Wefocusonalltheperformancesofcodingimagebutnot onlyonbit-rateorPSN1L Keywords:fastsearchalgorithm;adaptive;terminationthreshold;templateexchange;motionvetor 摘要:采用全新的搜索策略对一步一次搜索(OTA)方法进行改进,包括利用全新的 自适应搜索提前终止门限,运动矢量预测,零 运动矢量优先,以及搜索模版技术.并且这些策略完全可以运用到其他算法当中. 大量的 标准 excel标准偏差excel标准偏差函数exl标准差函数国标检验抽样标准表免费下载红头文件格式标准下载 序列测试结果表明了这种算法的有 效性,强健性和高度自适应性.该文的搜索策略和算法关注编码后的所有性能,而 不仅仅是只关注编码速度或者是峰值信噪比. 关键词:快速搜索;自适应;终止门限;模版变换;运动矢量 文章编号:1002—8331(2007)11-0219—03文献标识码:A中图分类号:TP391 1简介 运动估计是视频编码系统中用来去除帧与帧之间冗余信 息的关键技术.当前,作为运动估计的一种实现方法,块匹配运 动估计技术因为它的有效性和易于实施性而被众多国际视频 编码标准所采用(例如,H.26X系列与MPEG系列).单纯按照 编码图像峰值信噪比(PSNR)和码率(bite—rate)大小来说,全搜 索(fullsearch)在大多数情况下都能取得最好的结果;但是FS 的巨大计算复杂度使其不可能在实时视频系统中得到应用,特 别是全软件实现的系统.因而,寻找一种强健而又有效的快速 块匹配算法一直都是过去几十年里人们研究的焦点.到目前为 止,人们已经开发了许多优秀的快速搜索算法,例如,菱形算法 (DS),三步搜索算法(TSS),六边形搜索算法(HEXS).这些算 法利用不同的搜索模版和策略.以达到在搜索速度尽可能快的 同时接近全搜索性能的目的.虽然它们的模版都是根据实际序 列的运动矢量的分布而设计出来的,也很有效,但是它们都是 从零运动矢量开始搜索,并没有利用相邻块运动矢量之间的高 度相关性.这样,对于大运动序列,就很容易导致它们陷入局部 最小(例如,利用sad作为准则)而使性能下降很大.这主要是 因为大部分现实中的实际序列都不具备图1所描述的那样,在 搜索窗内只有一个全局最小值:而图2则描述了它们的真实分 布,可以看到在搜索窗中有很多局部最小点.根据以上所讨论 的事实,运动矢量预测技术被广泛应用到各种快速搜索算法当 中.这样一来就可以在大幅度降低计算复杂度的同时得到更好 的压缩性能.为了进一步地降低计算复杂度,人们又在算法当 中加入了一个终止门限,也就是搜索提前终止阈值.它的基本 原理是:如果当前所搜索到的sad值小于一个提前设定的阈值 时,就立即停止当前的搜索,而且有理由相信目前所得到的sad 值已经足够精确了.但是,如果阈值设置的不是很恰当就会导 致这样的结果:要么是起不到作用,要么是对图像的质量有很 大的影响并引入很大的额外开销.例如,如果阈值设置得太低, 那么对于大的运动序列将起不到任何作用;而阈值太高,则会 使小运动序列的压缩质量有很大的降低:另外,如果阈值计算 公式太复杂的话就会带来很大的额外开销而得不偿失.所以说 . jj.l. 图1理想sad分布 图2实际sad分布 0 2202007,43(11)ComputerEngtneeringandApplications计算机工程与应用 如何去选择一个合适的阈值变得很关键:既要很有效果,又不 能引入过多的计算量或带来性能上的巨大下降. 在本文算法当中,基于已有的一步一次搜索算法(OTA), 采用全新的自适应运动矢量预测技术,提前结束搜索阈值技术 以及根据视频序列的特点去选择搜索模式的技术.为了检测这 种新的算法的有效性,自适应性与强健性,采用了几个运动范 围不同的视频测试标准序列(football,Stefan,foreman和news), 它们的运动剧烈程度依次降低.仿真结果表明:本文算法的自 适应性特别强,在PSNR,bite—rate以及搜索次数都要优于传统 的算法,特别适合于低码率实时视频编解码系统. 2传统一步一次算法简介 一 步一次算法是一种能够简单,有效地找到最佳匹配块的 块匹配算法.它分为两个不同的搜索方向:一个是水平方向,一 个是垂直方向.如果在一个方向上找到当前最优点的话就结束 当前方向的搜索,然后以这个点为基准进入另一个方向的搜 索.下面就介绍一下它的具体搜索步骤: 步骤1首先在搜索窗的中心位置搜索水平方向上的3 相邻点. 步骤2如果步骤1中搜索到的最小sad是3个点的中心 点时,停止水平方向搜索并开始垂直方向的搜索;否则将对水 平方向上最靠近步骤1得到的最小sad点的点进行搜索,这样 一 直持续下去直到当前搜索点的sad大于上一个点的sad 为止. 步骤3重复以上的步骤,只是以水平方向上得到的最小 sad点为中心进行垂直方向上的搜索,直到找到垂直方向上的 最小sad点,这一点便是所要找的最佳匹配块. 图3示出了一种可能的搜索路径: 上 工?水平方向搜索 v水平方向最小sad点 ?垂直方向搜索 ?找到的最佳匹配点 图3oTA的一个搜索路径 3全新的自适应搜索策略 3.1全新的自适应运动矢量预测技术 初始搜索中心预测技术广泛应用于各种快速块匹配算法 当中.事实 证明 住所证明下载场所使用证明下载诊断证明下载住所证明下载爱问住所证明下载爱问 采用这种技术的算法比不采用这种技术的算法 在搜索速度上和压缩性能上都有很大的提高.它主要是利用了 同一帧的相邻块或者相邻帧对应块的运动矢量之间有很强的 相关性这一特点来提高算法的效率.如果想用前一帧图像的运 动矢量的话.就必须把它们保存起来,这对于嵌入式系统来说 很是不利.而且带来的性能提高也很有限,所以本算法只利用 同一帧的相邻块进行运动矢量预测.在图4中,肘代表当前 块的运动矢量,MV1代表当前块左边块的运动矢量,而MV2 与肘3则分别表示上一块和上右块的运动矢量.经统计发现, 肘与MMV1或Median(MVI,MV2,MV3)的相关性最高,事实 上它们也经常被用作当前运动矢量MV的预测值.这里Me— dian(.)是取中值的意思,如公式(1)所示: Median(a,b.C)=0ifa>b&&a<c(1) 图4运动矢量相关性 abs(0)=07a:一a(2) 但是,在本文算法中,并不单独使用MV1或者Median (MV1,MV2,MV3),而是同时利用它们作为当前宏块的运动矢 量预测,到底用哪个则由下面的伪代码决定: IFabs(MVl_x)+abs(MVl_y)<m Mvredict=MV1 ELSE _predict=Median(MV1,MV2,MV3) 这里abs(.)是取绝对值的意思,如公式(2)所示,m是一个 常量,根据不同的序列会自动取不同的值,其中MV1一,肘1 分别是MV1的与y方向上的分量,MV__predict则是当前宏 块运动矢量的预测值.仿真结果表明这样的预测策略要比过去 的各种预测方法的效果要好得多. 3.2全新自适应提前终止阈值 搜索提前终止技术是减少运动估计计算复杂度的一项关 键技术.它能够很大程度地减少计算量,同时对视频的压缩性 能的影响很小.当然,如果这个阈值设置得不太恰当的话,则会 大大影响压缩效率和视频压缩质量.当前,主要有两种设置阈 值的方法: (1)设置一个固定的常量作为阈值,比如经常取T=512. 这种方法的特点是非常简单但缺乏灵活性,对于内容丰富的视 频序列的作用不是很大.也就是说,如果太小,将对大的运动 序列没有任何作用;而太大的话,又会造成小运动序列压缩 性能的下降,所以无法根据序列的特点做到自适应. (2)如果当前计算的sad值小于所有相邻宏块的sad或者 它们的均值则停止搜索.这种方法也不是很恰当,要么不符合 实际情况,要么带来很大的额外计算量(为了防止预测值过大 而对压缩性能有很大的影响). 在本文算法中,提出一种全新的自适应阈值策略:利用前 一 帧sad的信息.方法是:求出前一帧所有宏块sad值的平均 值.然后把这个均值乘上一个 经验 班主任工作经验交流宣传工作经验交流材料优秀班主任经验交流小学课改经验典型材料房地产总经理管理经验 因子作为当前帧的阈值.为 了减小运算量,对sad采用亚采样(如图5中黑色方块所示)计 算.这样可以在减少运算量的同时取得同样的效果. II1Ilj_l I,7l一—z,zl—一 ?j?'?'?_l ?tj?tj?j一1I 图5所有sad值的亚采样 对于一个cIf序列来说,每一帧只引入了25次的加法运 算.可以说额外的开销是微乎其微的.但是根据这个值,可以决 定当前序列是一个什么运动强度的序列,以给出一个合理的阈 值真正做到自适应.这样既可以减少搜索的点数,又可以保持 原有的压缩性能. 3_3零运动矢量优先 对于基于运动估计的视频编解码系统,视频序列最终的编 码码流大小由两个部分决定:(1)当前块与最佳匹配块的残差 王红,乔永强,王松梅:用于运动估计的全新自适应一步一次搜索策略221 编码码流;(2)运动矢量差分编码码流.所以,在实践中,会发现 这样一种现象:当匹配更加准确时,也就是说当前块与最佳匹 配块的残差更小,最后的码流反而增大了.这是因为:虽然发在 块残差编码上的码流变小了;但是对更大的运动矢量进行编码 却会增加码流的开销,导致了总的码流的增加.于是,人们就把 零运动矢量的sad减去一个值以提高零运动矢量的优先级,特 别是小运动序列,这样处理后会大幅度减小编码的码流大小. 但是.这样处理后编码序列的PSNR会有较大程度的降低.在 本文中,为了在不提高码率的同时提高PSNR,采用了以下策 略:统计上一帧的平均sad值,以判断当前序列是不是小运动 序列:如果是的话,就把零运动矢量的sad减去一个常量,并同 时减小量化步长.仿真结果表明:在获得同样码率的同时,采用 这种策略的算法要比不采用这种策略的算法的PSNR有一个 很大的提高. 4优化的策略和搜索模式 传统的OTA算法利用图3所用的模式进行搜索,而不管 当前序列的运动特点.这样,对于大的运动序列就会很容易陷 人局部最小值:另外.它先采用水平方向搜索,再采用垂直方向 搜索,这样,对于垂直方向运动显着的序列,压缩性能会比较 差在本文算法中,会根据当前序列的特性来选择步长和搜索 策略.也就是说如果当前序列是一个小的运动序列,则选择小 步长进行搜索;否则,选择大步长进行搜索,搜索的第一步如图 6和图7所示: 图7大步长 如果运动矢量的估计值的分量比Y分量大很多,将选择 先用水平方向搜索.否则就先进行垂直方向搜索;如果分量 和Y分量差不多时,就采取图8或图9的对角线方向进行 搜索: 当采用步长为2的模版(图7)时,当找到一个方向上的最 小值点后.为了保证搜索的精度,会对最后搜索的两个点的中 间点进行搜索.以确定最终的当前最小值. 下面将给出本文算法的搜索策略实施步骤: (1)统计上一帧sad的平均值,并乘上一个经验系数作为 当前帧的阈值.并由此判断出当前序列的运动强度的大小. (2)利用本文提供的方法对运动矢量进行预测,并计算预 测点和零点的sad,如果它们之一小于步骤(1)中的阈值,搜索 过程终止;否则,根据预测得到的和Y分量的不同来选择各 种搜索模版(如图6一图9所示). (3)以步骤(2)中得到的预测点为搜索中心,如果步骤(1) 中判定当前为小运动序列,那么就减小量化步长,否则量化步 长不变;然后利用步骤(2)中选择的模式进行搜索;如果当前所 用步长为大步长,则补充搜索一点(如图10中的?所示). 以上搜索过程中,每搜索一点之后,都要检查一下当前得 到的最小sad是不是小于步骤(1)中设置的阈值,是则停止搜 索,否则继续进行,最终得到所要搜索的最佳匹配点. 图10给出了一种可能的搜索路径: ? 工一 1r L一L_.卜'一 ?第一步三点搜索 接下来的搜索点 ?水平方向补搜点 ?垂直方向搜索 ?全局最优匹配点 图1O本文算法的一种搜索路径 这个搜索路径是在水平预测运动矢量较大,而垂直方向的 预测矢量较小的情况下进行的.这时,在水平方向上采用步长 为2的模版.而垂直方向则采用步长为1的模版搜索,其中的? 点是为了提高精度而补充搜索的点. 5实验结果及结论 为了检测本文提出的各种全新的搜索策略和算法的有效 性,自适应性与强健性,采用了几个运动强度范围不同的视频 测试标准序列(football,Stefan,foreman和news),它们的运动剧 烈程度依次降低.表1同时给出了优秀的三步算法(TSS),砖石 算法(DS),六边形算法(HEXS),一次一步算法(OTA)的实验结 果.仿真时所使用的平台为H.263编解码平台的基本模式,量 化系数为10.下面的表1给出了本文算法的实验结果: 表1本文算法和一些有名的传统算法的仿真结果 黑体显示的是利用本文提出的全新搜索策略的一步 一 次(OTA)算法 从表1中的结果可以看到:利用本文提出的搜索策略对已 (下转234页) 2342007,43(II)ComputerEngineeringandApplications计算机工程与应用 人都可以利用签证机构的公钥y及参数P验证选票的合法 性,同时可以利用承诺因子k检验计票机构解密的正确性. (8)坚固性:本 方案 气瓶 现场处置方案 .pdf气瓶 现场处置方案 .doc见习基地管理方案.doc关于群访事件的化解方案建筑工地扬尘治理专项方案下载 采用了(t,,z)门限签名方案,能够容忍 部分签证中心的作弊行为.一张张合法的选票只需要经过t个 签证中心的签名就可以了.由于某个签证中心无法猜测其他签 证中心的密钥,因此当有投票人弃权时,可以有效地防止签证 中心冒名投票的现象. (9)实用性:本 协议 离婚协议模板下载合伙人协议 下载渠道分销协议免费下载敬业协议下载授课协议下载 可将投票人划分为若干个不相交的类 别,可以分别统计每个类别中投票人的观点,也可以像一般的 投票方案一样,统计所有人的观点,这只需要将最后的投票结 果汇总起来就可以了.无论划分的类别个数是多少.本协议所 需进行的投票轮数都固定不变.因而本协议满足实用性. 一 般的电子投票方案采用普通的盲签名技术,但用于存在 多类投票人的选举时,所需的密钥与投票人的类别有关.本方 案在进行多类投票人的选举时,所需的投票轮数与类别的个数 没有关系.文献[41N协议较复杂,特别是签名长度较长,至少为 (/+I)log~o+(1+t+I)log2q(ql(p-I),q,p都是大素数,Z是类别的 个数),可见,签名的长度与类别的个数Z有关.而文献『2,31在 进行多类投票人的选举时,所需的密钥为nl(n为类别的个数.f 为签证中心的个数),很显然密钥的个数也与类别的个数有关. 在本文的协议中,进行表决所需的密钥仅为,z,与投票人的类 别无关,协议高效,方便. 5结束语 本文设计了一个可将投票人分为多类,分别统计每一类投 票人观点的电子投票协议.针对文献『41中提出的新问题,参与 者采用了基于双线性配对的门限部分盲签名协议.通过在签名 中嵌人投票人所属类别标识,有效地完成了投票人所属类别的 划分,并且由于采用了(t,,z)门限秘密共享方案,系统具有更强 的健壮性.本协议的计算量与通信量小,并且满足电子投票协 议的安全标准.(收稿日期:2006年8月) 参考文献: 【1】FujiokaA,OkatomaT,OhtaK.Apracticalsecretvotingschemefor largescaleelections[C]//LNCS718:AUSCRYPT'92.Berlin:Springer- Vedag,1993:244—251. 【2]姚立,李仲麟.一个实用的电子投票协议的设计【J]|华南理工大学学 报:自然科学版,1997,25(5):96—99. [3]3赖瑾,范玉顺.一种新的安全,实用的电子投票方案[J].计算机科学, 2003,20(1):142—145. 【4]石怡,冯登国.一类新型(,t,n)一门限群签名方案的设计与分析【M] //王鄂芳,杨伟成.密码学进展:ChinaCrypto2000.北京:科学出版 社.2000:156—159. 【5]陈伟东,冯登国.一类存在特权集的门限群签名方案[J].软件, 2oo5,16(7):1289—1295. 【6]陆洪文,郑卓.基于双线性对的门限部分盲签名方案【J].计算机应 用,2005,25(9):2057—2059. 【7]BlumM.Coinflippingbytelephone[C]//ProeIEEESprintCOMP- COM,1982:122-137. (上接221页) 表2本文算法与各种快速算法的性能对比 OURS算法和各种快速算法的性能对比 序列各种算法PS NR升降/dR码率升降/%速度加快倍数/倍 有的一步一次算法进行改进后,和已有的各种优秀算法相比, 新算法在PSNR,码率和搜索的点数三个方面的性能都取得了 显着提高.本算法在实现快速搜索的同时,又获得了很好的压 缩性能,而且自适应性和强健性也是非常强的;同时它也特别 容易实现,引入的额外计算开销特别小,自适应性特别的强,是 一 个实用性很强的算法.当然,所有这些策略完全可以运用到 其他算法当中去,同样取得了很好的效果,由此也说明了这些 搜索策略的自适应性和强健性. 为了直观起见,表2给出了本文算法在峰值信噪比,码率, 速度加快倍数(以搜索点数为准)三个方面与各种算法的一个 对比,其中正值表示上升,负值表示下降. (收稿日期:2006年8月) 参考文献: [1]TsaiJang-jer,ChenHsin-chia.Predictiveblock-matchingdiscrep- ancybasedonrhombuspatternsearchforblockmotionestimation[J]. ImageProcessing,2005:I一1073-6. 【2]WeiZheng-yu.Anewfull-pixelandsub-pixelmotionvector searchalgorithmforfastblockmatchingmotionestimationinH. 2640].ImageandGraphics,2004:345-348. 【3]lainEGRichardson.Videocodecdesigndevelopingimageand videocompressionsystems[M].欧阳合,韩军,译.长沙:国防科技大 学出版社,2Oo4. 【4]lainEGRichardson.H.264andMPEG一4videocompression[M].欧 阳合,韩军,译.长沙:国防科技大学出版社,2004. 【5]栗强,崔慧娟.H.263的高效算法研究及单片DSP实现【】].电视技 术.2002. [6]刘峰.视频图像编码技术及国际标准【S].北京:北京邮电大学出版 社.2005.