几种经典快速块匹配运动估计算法的比较研究

格式：pdf
大小：965.25 KB
文档页数：3

下载文档原格式

一种综合搜索策略的快速运动估计算法

ｐｔｒｎｌｃ—ａｅａｉｔｄｓｅｔｅｒｈ（ＢＤ）ａｏｔｍｎｏｏａｄｅｒｅｉａｏｔｔｙｉｔｅｍｔｄａｅａｄｂｏｋｂｓｄｇｄｎｅｃｎｓａｃＢＧＳｌｒｈ．Ｉｃｒｒｅａｌｔｍｎｔｎｓａｇｅｏｔｎｒｅｇｉｐｔｙｒｉｒｅｎｈｈ
ＷＡＮＧＣｕ，Ｓｈｎ－ｕ，ＪＡＫｅｂｎｈｎＵＮＺｏｇｈａＩ — ｉ
（ｏｅｅｏｌｔｎｃｎｏｍｔｎ＆ＣｎｒｌｎｉｅｒｇｅｎｎｖｒｙｏｅｎｌｇＢ￣ｎ０１４ｈｎ）ＣｌｇｅｒｉＩｒａｉｌｆＥｃｏｆｏｏｔｇｎｅｎ，ＢｉｇＵｉｓｃｏｏｙ，ｅｉｇ１０２，ＣｉａｏＥｉｆｅ￣ｆＴｈｉ
ｓｖｒｌｉｓｕｔｅｐｅｉｇｕｅｓａｃ．Ｅｐｒｎａｅｕｔｓｏｔａｅｐｏｏｅｇｒｈｃｎｉｒｖｅｒｈｓｅｄｅｅａｍｅ，ｆｒｒｓｅｄｎｐｔｅｈｔｈｈｒｘｅｍｅｔｌｓｌｈｗｔｈｒｐｓｄａｏｔｍａｍｐｏｅｓａｃｐｅｉｒｓｈｔｌｉ
ｖｎｅｎｅｎｔｎｌｓｎａｄａｃｄｉｔｒａｉａｔｄｒ．Ｅｓｅｉｌｏｅｕｎｅｔａｇｔｎｃｎｅｔｈｐｅｕｏｌｃｉｖ０一４％．ｏａｐｃａｌｆｒｓｑｅｃｓｗｉｌｒｅｍｏｉｏｔｎ，ｔｅｓｅｄｐｃｕｄａｈｅｅ２％ｙｈｏ８Ｋｅｒｓｙｗｏｄ：ｂｏｋｍａｃｉｇｍｏｉｎｅｔｔｎ；ｓａｃｔｔｇ；ｓａｉｌｃｒｌｔｎ；ｐｅｉｔｎｌｃｔｈｎｔｓｍａｉｏｉｏｅｒｈｓｒｅａｙｐｔｏｒａｉａｅｏｒｄｃｉｏ

一个健壮的用于低比特率视频编码的快速运动估计算法

维普资讯
第２３卷第９期２００２年９月文章编号：００１２（０２０ — ０８０１０ — ２０２０）９１８ —４
小型微型计算机系统
ＭＩＩ— Ｎ —ＭＩＣＲＯＳＹＳＴＥＭ
Ｖｏ１．２３ＮＯ．９Ｓｅｐ．２００２
一
个健壮的用于低比特率视频编码的快速运动估计算法
郭红星余胜生周敬利
（中科技大学计算机科学与工程系．北武汉４０７）华湖３０４
摘要：提出一个用于低比特率视频编码的快速块匹配运动估计算法．算法能够自适应调整搜索起点使其接近全局该最优位置，采用有效的搜索模式来防止搜索过程陷入局部最小，时用灵活的中止准则来控制运动估计精度与计算并同
其中
为当前帧中正进行运动估计预测的块，为参考帧Ｆ
中搜索区域内的候选块．Ｓ使ＡＤ最小的候选块被选为最佳匹配块，应的在水平和垂直方向的位移（。）是运动矢相 “７就２
缩性能变差．
▲
本文提出一个新的快速块匹配算法．为最小棱形搜索称（ｅｓＤａｎｅｒｈＬ）法．其它快速算法相比，ＬａｔｉｍｏｄＳａｃ — ＤＳ算与其在减少搜索次数的同时．有效地防止搜索过程陷入局部能最小．高估计精度．提

一种基于无回溯搜索方法的块匹配运动估计算法

ｐｏｌｏｔｎｅｔｔｎＢａｅｎｔｅｉｅｆｔｅＫＭＰａｇｒｈｏｈｒｃｅｔｉｇｆｒｆｓａｔｒｒｂｅｍｆｍｏｉｓｉｉ．ｏｍａｏｓｄｏｈｄａｏｈｌｏｉｍｆｃａａｔｒｓｒｏａｔｐｔｎｔｎｅ
２．ｐｆＣｍｐｔｒＳｉｎｅａｄＴｅｈｏｏｙ。Ｈｕｉｕｌｇ。Ｈｕｉｕ。Ｈｕａ４８０ＤｅｔｏｕｅｅｃｎｃｎｌｇｏｃａｈａＣｌｅｏｅａｈａｎｎ１０８。Ｃｈｎ）ｉａ
Ａｂｓｒｃ：ｎｏ — ａｋｒｃｎｅｒｈｎｌｏｉｈｆｒｂｏｋｍａｃｉｇｉｉｅｓｐｏｏｅｏａｄｅｓｔｅｔａｔＡｎｂｃｔａｋｉｇｓａｃｉｇａｇｒｔｍｏｌｃｔｈｎｎｖｄｏｗａｒｐｓｄｔｄｒｓｈ
ｍａｃｉｇ，ｏｌｏｉｈｍｏｎｅｔｈｅｂｏｋｍａｃｉｇｉｔｅｖｄｏｉｇｎｔｈａｔｒｔｈｉｇｏｈｒｃｅｔｈｎｕｒａｇｒｔｃｖｒｓｔｌｃｔｈｎｎｈｉｅｍａｅｉｏｔｅｐｔｅｎｍａｃｎｆａｃａａｔｒｓｒｎｇ．Ｔｈｘｔｆｃｉｎｖｌｅｏａｈｐｉｌｉｈｕｂｂｌｃａｅｅｓｌｂｔｉｄｂａｎｇａｖｎａｅｏｈｔｉｅｎｅｕｎｔｏａｕｆｅｃｘｅｎｔｅｓ — ｏｋｃｎｂａｉｙｏａｎｅｙｔｋｉｄａｔｇｆｔｅｓｌ．ｔｈｎｒｉｆｔｅｂｌｃｅｆｍａｃｉｇｔａｔｏｈｏｋ．Ａｎｈｔｘｌｆｏｔｅｔａｒｙｏｈｅｂｌｃａｌｏｂｏｎｔｔｅｐｄｔｅｒｈｐｉｅｒｍｈｅｎｘｒａｆｔｏｋｃｎａｓｅｆｕｄｏｕｏｋｅ

一种改进的快速全局运动估计算法

第３６卷第２Ｏ期
１．３６
・
计
算
机
工
程
２１００年１０月
Ｏｃ
ＣｏｐｅｍｕｔｒＥｎｇｎｅｒｎｇｉｅｉ
博士论文・
一
文章编号：１ｏ４８００ｏｌ８ｏ文献码：０ —３２（１） —Ｉ２— ４０２２Ｉ）标识Ａ
ｈｇｅｉｈｒＧＭＥｒｃｓｏ．ｐｅｉｉｎ
［ｙｗｒｓＫｅｏｄ］ＧｌｂｌｔｎＥｔｔｎＧＭＥ；ａｉｎｓｅｔｏａＭｏｉｓｍａｉ（ｏｉｏ）Ｇｒｄｅｔｃｎ（ＤｅＧＤ）ｌｏｉｍ；ｌｃｔｈｎｇｒｈＢａｇｒｈＢｏｋＭａｃｉｇｏｉｍ（ＭＡ）ＩｒｔｅｅｓＳｕｒ（ＳｔＡｌｔ；ｔａｉａｔｑａｅＩ）ｅｖＬＬ
［ｓｒｃ］ＴｉｐｐｒｒｓｎｓｎｉｒｖｄｆｓＧｏａＭｏｉｎＥｔｔｎＧ）ｌｏｉｍｙｃｍｂｎｎｉ —ｔｔｏｎａｉｏａＡｂｔａｔｈｓａｅｅｅｔａｐｍｐｏｅｔｌｂｌｔｓｍａｉ（ＭＥａｇｒｈｂｏｉｉｇｗｔｔｓｐｍｅｈｄａｄｔｄｔｎｌａｏｉｏｔｈｗｏｅｒｉ
ｍｅｈｄｉｕｅｎｔｅｆａｕｅｐｘｌｉｈａｅｓｌｃｅｒｍｈｅｉｕｌｓｍｐｅｌｃｓｔｔｈｖｅｎｅｃｕｅｔｉｒｔＬＳｔｏｓｓｄｏｈｅｔｒｉｅｓｗｈｃｒｅｅｔｄｆｏｔｅｒｓｄａａｌｄｂｏｋｈａａｅｂｅｘｌｄｄｏｕｌｓｗｉＩＥｘｅｉｎａｅｈｐｒｍｅｔｌｒｓｌｓｖｌｔｈｔｔｅｅｔｔｎｓｅｄｏｍｐｏｅｌｏｉｍｅｃｅ４／，ｉｉｉｓｆｓｅｈａＦＲＧＭＥａｇｒｔｍ，ａｄｉｇｔｅｕｔａｉｅｔａｈｓｉｉｐｅｆｉｒｖｄａｇｒｔｄａｍａｏｈｒａｈｓ１２ｍｓｆｔｓ１３ｔ１ｍｅａｔｒｔｎＦＴｌｏｉｈｎｔｅｓ

运动估计与运动补偿

运动估计与运动补偿运动补偿是通过先前的局部图像来预测、补偿当前的局部图像，它是减少帧序列冗余信息的有效方法。

运动估计是从视频序列中抽取运动信息的一整套技术。

运动估计与运动补偿技术MPEG-4采用I-VOP、P-VOP、B-VOP三种帧格式来表征不同的运动补偿类型。

它采用了H.263中的半像素搜索(half pixel searching)技术和重叠运动补偿(overlapped motion compensation)技术，同时又引入重复填充(repetitive padding)技术和修改的块(多边形)匹配(modified block(polygon)matching)技术以支持任意形状的VOP区域。

此外，为提高运动估计算法精度，MPEG-4采用了MVFAST(Motion Vector Field Adaptive Search Technique)和改进的PMVFAST(Predictive MVFAST)方法用于运动估计。

对于全局运动估计，则采用了基于特征的快速顽健的FFRGMET(Feature-based Fast and Robust Global Motion Estimation Technique)方法。

编解码器用来减少视频序列中的空域冗余。

它也可以用来进行去交织(deinterlacing)的操作。

定义运动补偿是通过先前的局部图像来预测、补偿当前的局部图像，它是减少帧序列冗余信息的有效方法。

分类包括全局运动补偿和分块运动补偿两类。

运动补偿是一种描述相邻帧(相邻在这里表示在编码关系上相邻，在播放顺序上两帧未必相邻)差别的方法，具体来说是描述前面一帧(相邻在这里表示在编码关系上的前面，在播放顺序上未必在当前帧前面)的每个小块怎样移动到当前帧中的某个位置去。

这种方法经常被视频压缩/视频编解码器用来减少视频序列中的空域冗余。

它也可以用来进行去交织(deinterlacing)的操作。

用于快速块运动估计的多方向钻石搜索算法

高压缩率。帧间编码利用前面的帧（或参考帧）预测当前帧，降低连续帧间的时间冗余度。运动估计
是帧间编码的核心技术。相比于其他运动估计算法，匹配技术因为其简单性与易于实现性，被广块而泛应用于许多视频编码标准中，ＭＰＧ、２ｘ如Ｅ２Ｈ．６。在块匹配技术中，帧都被划分成块，每每块都对应一
ｆｒｂｏｋｍｏｉｎｅｔｔｎＴｅａｇｒｈｔｋｓｉｔｃｏｎｌｄｒｃｉｎｆｂｏｋｄｓｒｏｒｄｅｔｅｃｎ．ｏｎｙｏｌｃｔｓｍａｉ．ｈｏｔｍａｅｎｏａｃｕｔａｉｔｓｏｌｃｉｏｔｎｇａｉｎｓｅｔｎｔｏｌｏｉｏｌｉｌｅｏｔｉｄ
ｓｏｔａｈｒｐｓｄａｇｒｈｐｏｉｅｏｐｔｉｅｐｒｒｎｅｉｅｃｐｅｎｕｉ．ｈｗｔｔｅｐｏｏｅｏｔｍｒｖｄｓｃｍｉｖｅｆｍａｃｓａｈｓｅｄａｄｑａｔｈｌｉｅｔｏｎｒｌｙ
ＹＮｍｉｇＩＦａｎ
（ａｊｇＣｌｇｎｏｍａｉｅｈｏｇＮｎｉｇ２０１，ｈｎ）ＮｎｉｏｌｅｏｆｒｔｎＴｃｎｌｙ，ａｊ１０３ＣｉｎｅｆＩｏｏｎａ
ＡｓａｔＯｅｂｓｆｈｉｏｄＳａｃ（ＳａｇｒｈｔｓｐｐｒｒｏｅｕｉｉｃｏＳａｏｔＭＤ）ｂｔｃ：ｎｔａｉｏｅＤａｎｅｒＤ）ｌｉｍ，ｉａｅｏｓｍｌ— ｒｔｎＤｇｒｈｒｈｓｔｍｈｏｔｈｐｐｓｔｄｅｉｌｉｍ（ＤＳ

H.264帧间块模式选择与快速运动估计算法

ｐｏｏｅａｇｒｈｒｐｓｄｌｏｉｍｃｎｒｍａｉａｌｅｕｅｍｏｎｏｏｕａｉｎｎｈｇｌｓｅｄｏｉｇｆｃｅｃｗｉｋｅｉｇｔａｄａｔｌｒｄｃａｕｔｆｃｍｐｔｔａｄｉｈｙｐｅｃｄｎｅｉｉｎｙｈｌｅｐｎｃｙｏｅ
维普资讯
Ｈ．４帧间块模式选择与快速运动估计算法２６
郭再荣。喻占武。游韵
。武汉大学测绘遥感信息工程国家重点实验室，汉４０７）（武３０９
ห้องสมุดไป่ตู้（汉大学电子信息学院，汉４０７）武武３０９
文章编号１０ — ３１（０６０ — ０００文献标识码Ａ０２８３一２０）６０３ — ３中图分类号Ｔ９９８：Ｐｌ．；Ｐ９Ｎ１．１Ｔ３１２Ｔ３３１
ＦａｔＩｔｒＭｏｅＤｅｉｉｎａｄＭｏｉｎＥｓｉａｉｎＡｌｏｉｍ０２４ｓｎｅｄｃｓｏｎｔｏｔｍｔｇｒｔｏｈｆｒＨ．６
团
ｌ引言
Ｈ２４￣ＩＵＴ和ＭＰＧ联合制定的最新的视频编码标．６ｔＴ — Ｉ是Ｅ准，主要面向ＩＰ和无线网络的视频传输。由于它采取了增强的
ＡｂｔａｔＴｉａｅｐｏｏｅａｅｆｓｎｅｍｏｅｅｉｉｎｎｍｏｉｎｓｉｔｎｌｏｉｍｓｉｂｅｏＨ．６ｓｒｃ：ｈｓｐｐｒｒｐｓｓｎｗａｔｔｒｉｄｄｃｓｏａｄｔｅｔｏｍａｉａｇｒｈｏｔｕｔｌｆｒａ２４

基于多模板搜索的快速运动估计算法

Ｋｅｗｏｄ：ｍｏｉｎｅｔｔｏ，ｌｃ — ａｅｔｈｎｌｏｔｍ，Ｐ，ＳｉｎｒｓａｃＭＰｙｒｓｔｓｉｉｎｂｏｋｂｓｄｍａｃｉｇａｇｒｈＨＳＶＰ，ｎｅｅｒｈ，ＭＶＦＴｏｍａｉＡＳ
ＡｂｔａｔＩｔｉａｅ，ｅｒｐｓａｏｅｍｏｉｎｓｉｔｎｌｏｉｍ，ｈＭｕｉａｔｍ — ａｅＭｏｉｎｅｔｒｉｌｓｒｃ：ｎｈｓｐｐｒｗｐｏｏｅｎｖｌｔｅｔｏｍａｉａｇｒｈｔｅｏｔｈｐｔｅｂｓｄｔＶｃｏＦｅｄｏ
ＡｖｌＭ ቤተ መጻሕፍቲ ባይዱ ｔａｔｒ．ｓｄＭｏｉｎＥｓｉａｉｎＡｌｏｉｈＮｏｅｌｉｔｅｎ．ｐＢａｅｔｏｔｍｔｇｒｔｍｏ
ＺａｇＰｎＧｕｏｏｇｈｎｅｇｏＢａｌｎ
（ｃｏｌｏｌｃｒｍｃａｉａＥｇｎｅｉｇＸｉｉｎｖｒｉ，ｉｎ７０７）ＳｈｏｆＥｅｔｅｈｎｃｌｎｉｅｒ，ｄａＵｉｓｙＸ１０１ｏｎｎｅｔａ
ＡｄｐｉｅＳａｃｃｎｑｅＭＰａｔｅｒｈＴｅｈｉｕ（ＭＶＦＴ）ｔｉｏｏｅｆｔｅｐｅｉｔｎｏｎｔｌｅｒｈｏｎｓａａｔｅｓａｃｍｏｅｖＡＳ。ｓｃｍｐｓｄｏｈｒｄｃｉｆｉｉａｓａｃｐｉｔ，ｄｐｉｅｒｈＩｏｉｖｄｓ
运动类型进行判断，于静止块则直接跳ｆ匹配，于其它运对｝｛对

一种改进的H.264运动估计算法

Ｋｅｗｏｄ：．６；ｉｅｎｏｅ；ｔｏｓｉｔｏｙｒｓＨ２４ｖｄｏｅｃｄｒｍｏｉｎｅｔｍａｉｎ
ＥＥＡＯｃ：１０６２Ｄ
一
种改进的Ｈ．６２４运动估计算法
马骏，丁晶，赵力，邹采荣
ＭＡＪｎ，ＮＯＪｎＺＨＡＯＬｉＺｕＤＩｉｇ，，ＯＵＣｉｏｇａ— ｎｒ
（ｅａｔｅｏ如ＥｇｎｅｉＳｕｅｓＵｉｓｙ，ａｊｇ２０９，￣ｎ）Ｄｐ，，ｆＲ＇￣ｍｎｉｒｇ，ｏｔａｔｎ￣ｒｉＮｎｉ１０６Ｃｉｅｎｈｔｎａ
ａｇｒｈｂｓｄｏｈｈｒｃｅｉｉｆｔｎｅｔｔｎｉｐｏｏｅＴｅｐｓｉｌｄｓｒｄｅｙｌｏｉｍａｅｎｔｅｃａａｔｒｓｃｏｉｓｉｉｒｐｓ＆ｈｏｓｅｍｏｅｅｕｇｄｂｔｔｓｍｏｏｍａｏｓｂａｊ
ＡｂｔａｔＩｒｅＯｒｄｃｈｏｕａｉｎｏｔｎｅｔｍａｉｎｉ２４ｅｃｄｒａｔｍｏｅｄｃｓｏｓｒｃ：ｎｏｄｒｔｅｕｅｔｅｃｍｐｔｔｆｍｏｉｓｉｔｏｎＨ．６ｎｅ，ａｆｓｄｅｉｉｎｏｏｏ
１Ｈ２４编解码过程概述．６
Ｈ．６采用了经典混合编码算法的基本结构，２４本文第１部分简要介绍了Ｈ．６２４的编解码过其编解码框图如图１图２，所示。
收稿日期：０５０－３２０－６０－
作者简介：骏（９１，硕士研究生・马１８一男，）主要研究数字视频信号处理及其软件实现，视频压缩编码等，ａｎｅ．ｄ．ｎｍｊ＠ｓｅｕｃ！ｕｕ

一种新的基于H.264／AVC的快速块运动估计算法

摘要：为了解决目前快速块运动估计搜索算法容易使系统陷入局部最优陷阱这一问题，本文提出了一种新的基于Ｈ．４ＡＣ的快速块运动估计算法。简要介绍了运动估计算法和部分失真消除算法，给出了基于空间相关性的搜索范围修２／Ｖ６正方法，并提出了基于ＰＤＥ算法的最大局部匹配误差算法。通过实验数据测试表明，该算法在缩小搜索点数，提高编码效
ｔｈｎＧａｂｎ，ｎｉｏｅｏｉｇＹａｇＬｂ
（ｃｏｌｆｌｔｎｃｎｆｒｔｎＥｇｅｒｇＣａｇｈｎＵｉｒｉｆＳｈｏｏｅｒｉａｄＩｏｍａｉｎｉｅｉ，ｈｎｃｕｎｅｓｙｏＥｃｏｓｎｏｎｎｖｔＳｉｃｎｅｈｏｏｙＣｈｎｃｕ１０２，ｈｎ）ｃｅｅａｄＴｃｎｌｇ。ａｇｈｎ０２Ｃｉｎ３ａ
率上具有较大的优势。
关键词：最大局部匹配误差；空间相关性；部分失真消除；运动估计
中图分类号：Ｔ３１Ｐ０．６
文献标识码：Ａ
文章编号：１０－５９（０１６０３－２０７９９２１）０－０４０
ＡｗｓｏｋＭｏｉｎＥｓｉｔｎＡｌｏｉｍｓｄＨ．６／ＮｅＦａｔＢｌｃｔｏｔｍａｉｇｒｔｏｈＢａｅ２４ＡＶＣ
计算机光盘软件与应用
工程技术
ＣｍＢｅＤＳｆｗｒｎｐｌｃｔｏｓｏｐｔｒＣｏｔａｅａｄＡｐａｉｎｉ

基于X264的运动估计算法研究

襄呈弘渊一峨
基于 X2 6 4的运动估计算法研究
钱瑛 ( 南京工程学院计算机工程学院江苏南京21 11 57 )
C摘要】} L 264是目前最新的视频编解码标准．研究运动估计基本原理和研究状况的基础上，对X264编码器的三种运动估计算法进行分析和比较，实验结果表明可以在保证图像质量的情况下，提高编码速度。有效压缩视频．
=、X2H中运动估计算洼
l ‘l
8
1
2
3
o 初始搜索点．由于编码过程中宏块按扫描顺序编码。同一帧图像中与当前
_Ti T=r r —l l l 1
b
I 5
c
块相邻的已编码块共有上、左、左上、右上4个块。在参考帧中，以这
ru习r 1—LJ1i 1u——tL．J ] 『u可门 r ·1广1 L三j L■ U
以大写英文字母标注整像素位置，以小写英文字母标注 1／ 2像素位置，以阿
拉伯数字标注1 ／4像素位置。首先，在整像素运动估计中，假设点E为最佳匹
配点，则编码器在其周围的八个1／2像素位置( a- h ) 行搜索，设b 为这一阶段
的最佳匹配点，则在b周围的8个1 ／4像素位置( 1 ～8) 中进行搜索．直至找出
表1三种运动估计算法比较
测试序列 f or eEa a． qc i f c ar phone ．qc i f c l a i re ．qc i f
搜索范围码率( kb／s ) 质量( P s 际) 速度 ( f ps ) 码率( kb／s ) 质量( P S胍) 速度 ( f ps ) 码率( kb／s ) 质量( P SNR) 速度 ( f ps )

block matching算法原理

block matching算法原理Block matching算法是一种用于运动估计的方法，常用于视频压缩和图像处理领域。

其原理是通过比较不同帧间的像素块来寻找最佳匹配，从而推断出图像或视频中的运动信息。

在block matching算法中，首先将两个帧的像素块进行比较。

每个像素块由一定数量的像素组成，通常是一个正方形的区域。

然后，通过计算两个像素块之间的差异来评估它们的相似度。

常用的差异度量方法包括均方误差（MSE）、平均绝对误差（MAE）、均方根误差（RMSE）等。

接下来，需要在参考帧中搜索最佳匹配块。

对于每个目标像素块，在参考帧中搜索一定范围的像素块，并计算其与目标像素块之间的差异度量值。

搜索范围可以是一个固定大小的区域，也可以是根据预估的运动范围进行调整。

最后，选择差异度量值最小的参考像素块作为最佳匹配块，并记录其在参考帧中的位置偏移。

这个位置偏移就是目标像素块在不同帧间的运动向量，用来表示目标像素块的运动信息。

Block matching算法的优点是简单而且易于实现。

它可以在实时应用中快速计算出运动信息，并用于视频压缩和运动补偿等领域。

然而，由于图像中存在复杂的运动情况，单纯的block matching算法会存在一些问题。

例如，对于非刚体运动、快速运动和背景复杂的情况，block matching算法很容易产生错误的运动估计结果。

为了解决这些问题，研究者们还提出了一系列的改进算法。

例如，改进的block matching算法可以通过使用多尺度和多步长搜索来提高运动估计的精确度。

此外，也可以使用一些补偿技术来进一步提高运动估计的效果，如运动矢量预测和运动补偿。

总之，block matching算法是一种常用的运动估计方法，在视频压缩和图像处理领域具有广泛的应用。

虽然存在一些问题，但通过改进算法可以提高它的准确性和鲁棒性。

一种新的快速运动估计算法

一
步的搜索都是以上一步的最佳匹配点进行下一步搜索，而不考虑其它的已搜索点，因此ＴＳ算法容易陷入Ｓ
局部最优。ＮＴＳ和ＦＳ算法虽有所改进，由于没有考虑运动矢量的分布特点，索的效率不高。１９ＳＳ但搜９７年出现的ＤＳ算法及其以后的改进型Ｌ，有良好的搜索效果和较少的搜索次数，现在的视频压缩算法最常用６具］是
文章编号：ｌＯ一３２２０）０１３ — ４Ｏｌ４２（０７１ — ６５０
一
种新的快速运动估计算法
刘昌松，严高师，蔡建荣
（４
摘
要：数字化战场的发展使得红外图像信息的传输量迅速增加，因此必须对图像信息进行压缩处理，
１块匹配准则
块匹配算法对图像中物体的运动作了一定的假设和限制，化了运动分割，基本原理是将图像划分为简其Ｎ×Ｎ固定大小的方块，后对每块分别处理。将当前场的某一块在前一场的一个特定区域中搜索，据某一然依个匹配准则得到最佳匹配块，以这一最佳匹配块作为当前方块的预测块，同时将得到的位置矢量作为当前块的运动矢量。由该算法的描述可以看出，匹配算法是在块内运动场一致性的假设下实现的，块即假设方块内所有像素均具有相同的运动参数，这种运动被看成是刚体平移。块匹配算法的优点是分割及编码简单，现开销实小；点是对比较复杂的场景和快速运动的场景无法得到良好的预测效果。在块匹配运动估计过程中，缺匹配

一种新的基于H.264的快速运动估计算法

ＣｍｕｅｎｉｅｉｇａｄＡｐｉａｏｓｏｐｔｒＥｇｎｒｎｐｌｔｎ计算机工程与应用ｅｎｃｉ
一
种新的基于Ｈ．４的快速运动估计算法２６
李丽，宋刚
ＬＩｉＳＬ．ＯＮＧＧａｇｎ
山东大学信息科学与工程学院，济南２００５１０
ｐｔｒａａｔｅｙＴｉｎｂｅＵｔａｄｈｎｍｂｒｆｅｒｈｏｎｓａｔｎｅｄｐｉｌ．ｈｓｖｅａｌｓＳｏｄｔｅｕｅｏｓａｃｐｉｔｍｏｅｆｃｅｔａｄｈｓｍｐｏｅｔｅｅｒｈｐｅ．ｒｅｆｉｎｌｎｔｕｉｒｖｓｈｓａｃｓｅｄｉｙＭｅｎｉ，ｈｅｌｏｔｍｌｏａｏｔｈｄａｃｄｓｐｃｔｒｎｉｅｒｓａｃｅｈｏｏｙＳｍｕａｉｎｒｓｌｈｗｔａｈａｗｈｌｔｅｎｗａｇｒｈａｓｄｐｓｔｅａｖｎｅ－ｔｒｅａａｄｌａｅｒｈｔｃｎｌｇ．ｉｌｔｅｕｔｓｏｈｔｔｅｅｉｏｉｉｎｏｓｎｗａｇｒｈｃｎｒｄｃｈｅｒｈｔｂｖ０ｃｍｐｒｄｗｉｈｅｌｏｔｍａｅｕｅｔｅｓａｃｉｉｍｅａｏｅ２％ｏａｅｔｔｅＵＭＨｅａｏｓａｇｒｈａｏｔｄｂ２４ｓａｄｒ．ｈｘｇｎｌｏｔｍｄｐｅｙＨ．６ｔｎａｄｉＫｅｒｓｙｗｏｄ：ｍｏｉｎｅｔｔｎＵＭＨｅａｏｓａｇｒｈ；ｄｐｉｅｕｓ－ｔｓｉｉ；ｏｍａｏｘｇｎｌｏｔｍａａｔｎｙｍｍｅｒａｒｓｅｒｈａｔｒｉｖｔｉｌｃｏｓｓａｃｐｔｎｃｅ

基于运动矢量时-空特性的快速运动估计算法研究

１引言
基于块匹配的运动估计是视频压缩编码中的
的特点设计合理匹配点阵形状，从而减少搜索收敛前的搜索点数；初始搜索点的预测是使得搜索范围尽可能接近最终收敛点从而减少运算量；自适应技术主要是根据视频信息进行一定分析并对运动估计进行分类，根据不同类别采用不同的搜索模式，这样能够起到一定的优化运算，从而提高了运算速度。目前，主流的运动估计算法是上述３种方法的综合实现。典型的搜索模式算法包括三步法【１】（ＴＳＳ）、四步法【２（ＦＳＳ）￣ｎ钻石法（ＤＳ）等，其中，钻石法最为
２．ＳｃｈｏｏｌｏｆＥｌｅｃｔｒｏｎｉｃｎｄａＩｎｆｏｒｍａｔｉｏｎＥｎｇｉｎｅｅｉｒｎｇ，Ｘｉ ’ ａｎＪｉａｏＴｏｎｇＵｎｉｖｅｒｓｉｔｙ，Ｘｉ ’ ａｌｌ７１００４９，Ｃｈｉｎａ；
（１ｌＳｃｈｏｏｌｏｆＡｕｔｏｍａｔｉｏｎａｎｄＩｎｆｏｒｍａｔｉｏｎＥｎｇｉｎｅｅｉｒｎｇ，Ｘｉ ’ ａｎＵｎｉｖｅｒｓｉｔｙｏｆＴｅｃｈｎｏｌｏｇｙ，Ｘｉ ’ ａｎ７１００４８，Ｃｈｉｎａ；
第３４卷第１期
２０１３ห้องสมุดไป่ตู้ １月

快速运动估计中一种改进的块匹配免疫算法

重建图像的质量，ＰＮ即ＳＲ接近全搜索（ｕｌｅｒｈＦ）ＦｌＳａｃ，Ｓ算法，
的抗体被确定性地选择参与进化。
第３步细胞克隆，使被选择的抗体依据其亲和度高低
繁殖克隆细胞，同时其中部分克隆可作为记忆细胞更新记忆
池，即记忆细胞的演化；忆细胞的获取是从记忆池中选择一记
ｃｍｐｔｔｎｌａｎｒａｅｃｎｉｅａｌ．Ｉｈｅｌｏｔｍ，ｔｏｅｂｏｋｆｂｉｇｕａｌｏｍａｃｌｂｉｋｄｏｔａｄｏｕａｉｏｄｉｃｅｓｏｓｄｒｂｙｎｔｅｎｗａｇｒｈｏｉｈｓｌｃｓｏｅｎｎｂｅｔｔｈｗｉｅｐｃｅｕｎｌ
ＺＮａ，ＧＯＸｕｊａ，ＺＮｉ－ｉＥＧＨｏＡｉ－ｎＥＧＸａｐｇｕｏｎ
（ｏｅｅｏｏｕｉｔｎＥｇｎｅｎ，Ｃｏｇｉｎｖｓｙｈｎｑｇ４０３，ＣｉａＣｌｇＣｍｍｎｃｉｎｉｒｇｈｎｑｎＵｉｒｉ，Ｃｏｇｉ０００ｈｎ）ｌｆａｏｅｉｇｅｔｎ
Ｋｅｒｓｙｗｏｄ：ｍｏｉｎｅｔｔｎｍｍｕｅａｇｒｔｍ；ｂｏｋｍａｃｔｓｍａｉ；ｉｏｉｏｎｌｏｈｉｌｃｔｈ
０引言
文献［］１首先把免疫算法应用到图像的运动估计中，相对于传统三步法（ｒｅＳｅｓＳａｃ，Ｓ、形搜索ｈＴｅｔｅｈＴＳ）菱ｐｒ（ｉｏｄＳａｃ，Ｓ算法等传统快速运动估计算法，高了ＤａｎｅｈＤ）ｍｒ提

一种新的块匹配运动估计算法

中图分类号：１ＴＰ３２文献标志码：Ａ
ＮｅＢｃｔｈｎｏｉｎＥｓｉａｉｎＡｌｏｉｍｗｌｋＭａｃｉｇＭｔｏｔｍｔｏｇｒｔｏｈ
ＹＵＢｏ
（ｌｔｎｃＥｇｎｅｉｇＤｐｒｎ，ｎｇａｉｅｉｆｅｈｏｇ，ｏｇｕｎ５３０ＣｉａＥｅｒｉｎｉｅｒｅａｔｔＤｇｕｎＵｎｖｒｔｏｃｎｌｙＤｎｇａ２８８，ｈｎ）ｃｏｎｍｅｅｓｙＴｏ
ｍａｃｉｇｍｏｉｎｓｉｔｏａｇｒｔｍｗａｄｖｌｐｄ．ＴｈｅｅｉｅｔｌｅｕｔｈｗｓｈａｔｅｐｒｔｏｔｈｎｔｏｅｔｍａｉｎｌｏｉｈｓｅｅｏｅｅｘｐｒｍｎａｒｓｌｓｏｔｔｈｏｅａｉｎａｏｎｆｔｉｅｍｅｈｄｉｅｓｔｎＥＢＭＡｅｈｄａｓｈｇｅｒｃｓｏｈｎｔｒｅｓｅｓａｃｎｇｍｕｔｏｈｓｎｗｔｏｓｌｓｈａｍｔｏｎｄｈａｉｈｒｐｅｉｉｎｔａｈｅ —ｔｐｅｒｈｉｍｅｈｔｏｄ．
Ａｂｔａｃ：Ｎｏｉｉｇｔｅｃｒｅａｉｎｏｈｉｈｂｒｆａｓｉｉｅｅｕｎｃｓ，ａｄｂｓｄｏｈｎｌｓｓｏｈｓｒｔｔｃｎｈｏｒｌｔｏｆｔｅｎｅｇｏｒｍｅｎｖｄｏｓｑｅｅｎａｅｎｔｅａａｙｉｆｔｅｈｉｈｐｅｉｉｎｏｏｋｍａｃｉｇｍｅｈｄａｄｔｉｈｓｅｄｏｐｒｔｏｆｔｒｅｓｅｅｒｈ，ａｍｏｉｉｄｂｏｋｇｒｃｓｏｆｂｌｃｔｈｎｔｏｎｈｅｈｇｐｅｆｏｅａｉｎｏｈｅ —ｔ算法及其改进算法。我们把图像域分割成

1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

ComputerKnowledgeandTechnology电脑知识

与技术

计算机工程应用技术本栏目责任编辑：梁书

第6卷第32期(2010年11月)几种经典快速块匹配运动估计算法的比较研究肖敏连（湖南人文科技学院计算机科学技术系，湖南娄底417000）摘要：块匹配运动估计算法被许多视频编码标准采用以消除视频序列帧间的时间冗余信息，而运动估计往往是视频编码器中的最耗时的部分，为了加快视频编码速度，许多快速运动估计被相继提出，该文首先对三种经典的快速运动估计算法进行详细的分析，然后把这三种经典快速运动估计算法嵌入到国际视频编码标准H.264/AVC中，在相同的条件下分别对这三种算法进行性能测试，最后通过比较测试结果对三种经典快速运动估计算法的各自的特点进行了总结。

关键词：块匹配；运动估计；算法中图分类号：TP312文献标识码：A文章编号：1009-3044(2010)32-9152-03ComparativeResearchonSeveralClassicalRapidAlgorithmsofBlock-matchingMotionEstimationXIAOMin-lian(DepartmentofComputerScienceandTechnologyofHunanInstituteofHumanities,ScienceandTechnology,Loudi417000,China)Abstract:Block-matchingmotionestimationwasadoptedbymanyvideostandardstoeliminatethetemporalredundancyinformationbe-tweensuccessiveframes,andusuallythemotionestimationisthemosttimeconsumingpartofthewholeencodingprocess.Manyrapidmotionestimationalgorithmsaredevelopedinthepasttwentyyearssuccessively.Thispaperfirstlyanalyzedthethreeclassicalrapidblock-matchingmotionestimationalgorithms.ThenthesealgorithmswereinsertedintotheH.264/AVCreferencesoftware.Thethreeclassicrapidblock-matchingmotionestimationalgorithms'performancesweretestedunderthesamecondition.Finally,thecharacteristicsofthethreeclassicalrapidalgorithmsweresummarizedaccordingtotheexperimentalresults.

Keywords:block-matching;motionestimation;algorithm对于视频图像序列，如果帧与帧之间不是场景变换，运动幅度不是很大，则两帧之间就会存在很大的时间相关性即时间冗余，可以通过运动估计来消除时间冗余，从而达到视频压缩的目的。块匹配运动估计算法是目前应用最广泛的一种运动估计算法，它已被许多视频编码标准所采纳，如MPEG-1/2/4、H.261、H.263及H.264/AVC等等[1-2]。最基本的块匹配算法是全搜索（FS，FullSearch）

算法，虽然它能通过对搜索范围内所有的点进行搜索而找到最佳匹配点，但其计算量非常巨大，因此寻求快速的块匹配运动估计算法成了视频编码中热点问题。1几种快速经典运动估计算法的搜索策略

运动搜索的目的就是要寻找最优匹配点。在搜索过程中可以采用上述不同的起点预测方法和块匹配准则来加快搜索速度或提高精度。搜索策略选择适当与否对运动估计的准确性、运动估计的速度都有很大的影响。最简单、最可靠、搜索精度最高的是全搜索法，但由于它计算复杂度高，不易于实时应用，为此人们提出了各种改进的快速算法，下面介绍几种经典的快速运动估计算法。1.1三步搜索算法

三步搜索算法[3](ThreeStepSearch，TSS)于1981年由T.KOGA等人提出，作为

一种简单有效的运动估计技术，被广泛使用在低比特率视频压缩场合中，当最大搜索距离为7，搜索精度取1个像素，则步长为4、2、1，共需三步即可满足要求，因此而得名三步法。TSS采用一种由粗到细的搜索模式，从搜索窗中心点开始，按一定步长取周围

8个点构成每次搜索的点群，然后进行匹配计算，跟踪到最小块误差MBD点。

TSS算法具体执行步骤：①它先确定一个中心点，确定最大搜索长度，然后以

最大搜索长度的1/2作为步长，在中心点周围取离中心点距离为一个步长的8个点，将这9个点按照匹配原则进行计算，得到最佳匹配点；②然后以上一步得到的最匹配的块为中心，搜索与此相距为最大搜索长度1/4搜索窗口距离的8个点进行比较，再通过比较找出最匹配的块；③最后比到步长为1时，找出此时的最佳匹配点就是最终的结果。图1为TSS的一个搜索图示。该算法简单、健壮、性能良好。但第一步的搜索步

收稿日期：2010-09-07基金项目：湖南人文科技学院教改课题（RKJGY0928，RKJGZ0706）资助作者简介：肖敏连（1969-），女，湖南娄底人，实验师，本科，主要研究方向为多媒体技术。

图1TSS搜索图示

ISSN1009-3044ComputerKnowledgeandTechnology电脑知识

与技术

Vol.6,No.32,November2010,pp.9152-9154

E-mail:kfyj@cccc.net.cnhttp://www.dnzs.net.cnTel:+86-551-56909635690964

9152ComputerKnowledgeandTechnology电脑知识

与技术

计算机工程应用技术本栏目责任编辑：梁书

第6卷第32期(2010年11月)长过大而引起误导，从而对小运动幅度的视频图像的估计效果就不怎么理想。所以，后来又相继出现了许多改进的新三步法等，以改进它对小运动的估计性能。1.2新三步搜索法

新三步搜索算法[4](NovelThreeStepSearch，NTSS)是1999年由R.li,B.Zeng和M.L.Liou提出的，它是在三步法的基础上所做出的

改进算法，NTSS利用运动矢量的中心偏置分布，采用具有中心倾向的搜索点模式，并应用中止判别技术，以减少搜索次数。NTSS算法具体执行步骤：①除了对原三步法第一步的9个点进行搜索计算匹配

之外，还对搜索窗口中心的周围8个点进行比较。如果匹配的块在中心位置，则结束搜索，若是在周围的8个点上，则转②，如果在最外的8个点上，则转③；②以上一步得到的最匹配的块为中心继续搜索其周围8个点，其中有部分重复了，所以实际需要搜索的点为3到5个点，搜索得到的匹配块即为所求的最佳匹配块；③对最外面的8个点则按原三步法进行搜索。图2为NTSS的一个搜索过程图示。运动矢量通常总是高度集中分布在搜索窗的中心位置附近，NTSS采用中心倾向的搜索点模式不仅提高了匹配速度，而且减少了陷入局部极小的可能性；而采用中止判别技术则大大降低了搜索复杂度，提高了搜索效率。1.3菱形搜索法

菱形搜索算法(DiamondSearch，DS)[5]最早由S.Zhu和K.KMa提出，经过多次改进，成为目前快速块匹配算法中性能较为优异的一种算法。1999年10月被MPEG-4国际标准采纳并收入验证模型(VM)。搜索模板的形状和大小不但影响整个算法的运行速度，而且也影响它的性能。统计数据表明，视频图像中进行运动估计时，最优点通常在零矢量周围以搜索窗口中心点为圆心，两像素为半径的圆内，如图3所示。DS使用了两种搜索模式，分别为有9个点的大菱形搜索模式(LargeDiamondSearchPat-tern，LDSP)和有5个点的小菱形搜索模式(SmallDiamondSearchPatten，SDSP)。图4给出了DS的两种搜索模式，搜索过程先使用LDSP，对9个点进行比较，得到最佳匹配点，如果该点不在中心位置，则以最佳匹配点作为新的中心点，用LDSP继续进行比较，直到最佳匹配点位于中心位置，将LDSP换为SDSP，再进行匹配计算，这时SDSP中5个点中的MBD即为最优匹配点。然后以该点为中心应用SDSP进行比较，得到的最佳匹配点就是最后结果。DS搜索具体步骤：①在搜索区域中心及周围8个点按LDSP分别进行块匹配计算，如果计算得到的MBD在中心点则转到③，否则转到②；②以上一次找到的MBD点为中心，用LDSP计算，若MBD点位于中则转到③，否则重复该步骤；③以上次最佳点为中

心，搜索SDSP下的5个点，找到最佳点即是运动矢量对应的点。图5给出了DS的一个搜索过程，黑点表示该步搜索到的最佳点。该算法分析了视频图像中运动矢量的基本规律，选用了大小两种形式的模板LDSP和SDSP进行搜索，既可以进行粗定位，使搜索过程不会陷入局部最小，也使搜索不至于有大的起伏，所以其性能优于其他算法。另外，DS搜索时各步骤之间有很强的相关性，模板移动时只需要在几个新的检测点处进行匹配计算，所以也提高了搜索速度。但其性能上仍然存在缺陷：其一，对于运动大的序列，菱形法同等地对待搜索区域的各部门，这就造成较大的冗余，影响了算法的搜索速度；其二，对小运动序列来说DS算法还有待改进。在菱形搜索算法的基础上，后来又推出了六边形搜索算法、十字菱形搜索算法等，这些算法基本沿用了菱形搜索策略，提高了平均搜索速度，并且保持了相当的搜索精度。2实验结果

为了便于比较四种算法对运动估计的加速效果，在H.264参考平台JM17.2[6]的基础上，对不同的测试序列进行了一系列的测试，这里选取其中4个具有不同运动水平的视频序列，其中Akiyo（QCIF）和Foreman（QCIF）序列的运动较为简单，而Mobile&Calendar(QCIF)和Coastguard(QCIF)序列的运动则较为复杂；量化参数

（QuantumParameter，QP）选取28，32，36，40；运动搜索范围为33×33矩形窗（即在初始搜索中心点周围±16个整像素范围内），参考帧数为1，采用率失真优化算法及CABAC编码。为了突出各算法与全搜索算法的比较效果，在所有的测试序列中，只

有第一帧被编码为I帧，其它的帧都被编码为P帧，总共编码21帧。

图2NTSS搜索图示图3最优点分布规律图4大菱形模板LDSP及小菱形模板SDSP