基于遗传块匹配算法的高效运动估计技术研究

开篇：润墨网以专业的文秘视角，为您筛选了一篇基于遗传块匹配算法的高效运动估计技术研究范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！

摘 要：在MPEG4视频压缩中,运动估计是帧间视频编码中的关键技术,块匹配方法BMA（Block Matching Algorithm）是目前广泛使用的运动估计方法,但在现有的快速搜索算法中大都是次优算法,容易陷入局部最优。针对此问题,将遗传算法GA(Genetic Algorithm)应用于块匹配运动估计。实验证明,该算法不仅有效解决了局部极小问题,且计算量相对较少。

关键词：视频压缩；运动估计；块匹配；遗传算法

中图分类号：TN919.81文献标识码：A

文章编号：1004-373X(2008)08-121-03

Technology Research Based on Genetic Algorithm Efficient Block Matching Motion Estimation

CHEN Hong,QI Hua,ZHANG Jian

(School of Electronic Information Engineering,Xi′an Technological University,Xi′an,710032,China)

Abstract：Motion estimation is essential for many interframe video coding techniques in MPEG4 video compression.The Block Matching Algorithm(BMA) is currently widely used in motion estimation,However the existing quick search algorithm are mostly suboptimal algorithm and get a suboptimal solution.Aiming at this problem,this paper applies the genetic algorithm to block matching motion estimation.The result shows that the algorithm not only solve the problem of being trapped to local optima but also have a relatively small amount of computation.

Keywords：video compression;motion estimation;block matching;genetic algorithm

1 引 言

MPEG4是现在最重要最有影响的多媒体数据压缩编码国际标准之一。基于对象的编码思想使其具有高压缩比、可扩展性、可交互性等许多优点。MPEG4 视频压缩算法主要是对某一时刻某帧画面VO（Video Object）的形状、运动、纹理等信息进行编码。而实现上述编码的关键是运动估计,运动估计的结果不仅会影响视频图像压缩编码的质量,也会影响压缩编码的效率,因此提高运动估计的效率是整个编码的重点。现有的快速搜索算法中大都是次优算法,且易陷于局部极小点。遗传算法是借助于计算机编程将待求问题表示成串(或染色体),即为二进制码或数码串,从而构成一群串,并置于问题的求解环境中,根据一定适应度的原则选择出适应环境的串进行复制,且通过交叉和变异两种基因操作产生新的更适应环境的一代种群,经这样一代代不断变化,最后收敛到一个最适应环境的串上,而求得问题的最优解。本文提出了一种将遗传算法应用于块运动估计中的遗传搜索块匹配运动估计算法。该方法把块运动向量作为遗传染色体,经过交叉、变异等操作,以便得到全局意义上的最优解 。

2 遗传算法的基本原理

遗传算法是模仿自然界生物进化机制发展起来的随机全局搜索和优化方法,他借鉴了达尔文的进化论和孟德尔的遗传学说。其本质是一种高效、并行、全局搜索的方法,他能在搜索过程中自动获取和积累有关搜索空间的知识、并自适应地控制搜索过程以求得最优解。遗传算法操作使用适者生存的原则,在潜在的解决方案种群中逐次产生一个近似最优的方案。他利用某种编码技术,作用于称为染色体的数字串,模拟由这些串组成的群体的进化过程。遗传算法通过有组织的、随机的信息交换重新组合那些适应性好的串,生成新的串的群体。如今他以其固有的计算并行性,已广泛应用于问题优化、模型识别、并行处理等领域。

遗传算法解决问题的基本步骤为：将实际问题参数进行编码；确定作为优胜标准的适应值度量；选取初始种群；运用选择、交叉、变异等遗传算子对种群进行选择进化；运用停止运行原则得到优胜个体,最终得到问题的解。

3 基于GA的块匹配运动估值方法

运动估计是消除图像帧间冗余的有效方法。 块匹配算法（BMA）是目前应用最广的一种运动估计算法。各种快速搜索算法都是基于一种假设前提:在沿搜索路径到最佳匹配点的搜索过程中,匹配误差是单调递减的,也即假设在整个搜索窗中,匹配误差只有一个最小值,但实际上这种假设在绝大多数应用中得不到满足,通常情况下的匹配误差在整个搜索窗内呈现多极值状态,因此,这些快速搜索算法往往陷于局部最优解,而得不到全局最优解,从而导致编码质量的显著下降。为了解决局部最优化问题,本文采用基于遗传算法的块匹配运动估计。

已出现的几种基于遗传算法(GA)的块匹配算法中,文献［1］提出的一种GSA算法,由于具有很高的迭代次数,故其计算耗时非常大,接近FSA,所以很难应用于图象视频编码；文献［2］中提出的LGSA算法,虽然计算时间大大减少,但由于他未采用交叉操作,仅利用生存竞争策略控制下的高变异率去寻找全局最优,因此也会使算法质量变得不稳定。本文提出的基于遗传算法的块匹配算法,不仅能有效地解决局部极小问题,而且大大减少计算量。

3.1 编码方案的确定

码需要建立一种从搜索空间中的各个候选点到确定长度的各个染色体串的双向映射并确定染色体串的长度L和字母表规模k,块匹配问题的待解参数为运动矢量MV(x,y)。本文采用二进制串表示法( k= 2)将运动矢量映射到染色体(x1,x2,…,xn,y1,y2,…,yn),其中L=2n;n = ［log2W］ + 1;W = max{sx ,sy };sx ,sy 分别为搜索窗的水平半径和垂直半径。 由于偏移量具有方向性,故专用x1,y1来表示运动偏移量的正负(例如:x1=1表示水平运动矢量为负,x1=0П硎舅平运动矢量为正)。在MPEG4标准中,图像块大小为16×16,搜索窗大小为(2W+1)2,故n=5,L=10。И

3.2 定义适应度函数

遗传算法最优值为适应度大的点,而BMA中最优点是使MAD值最小的点,为使两者统一,适应性函数定为:F(i)=1/MAD,MAD越小的点,其适应度越高。

ИMAD=1/I×J∑|i|≤1[]2∑|j|≤1[]2|f(i,j)

-g(i-[WTHX]d[WTBX]x,j-[WTHX]d[WTBX]y)|И

其中I=J=16,坐标(0,0)表示块的左上角像素。[WTHX]d[WTBX]x,[WTHX]d[WTBX]yХ直鹗遣慰己昕榈脑硕矢量的水平矢量和垂直矢量。

3.3 设定种群规模和初始种群

在常规遗传算法中,初始个体通常是随机产生的,其个数和位置决定着能否快速找到最优解。个数过少、分布过于集中,迭代可能过早收敛；个数过大,运算量较大；分布过稀,迭代次数较多。在BMA具体问题中,应根据运动序列的具体情况指定初始点。首先,运动矢量具有中心偏移特性,即认为运动偏移大多限制在围绕搜索窗中心的一个很小区域内。其次,相邻宏块运动相似,可以用已编码相邻宏块的运动矢量来预测当前宏块的运动矢量,如图1所示。

根据以上2个特性,初始染色体个数为9个,位置指定方法如下:

对于图像边缘的宏块,没有参考宏块,初始点为搜索窗口中心的9个点,如图2（a）所示。

对于内部宏块,根据周围匹配过的宏块预先设定运动矢量,初始点为该运动矢量周围的9个点,如图2（b）所示。

图1 运动矢量预测

图2 初始点分布示意图

[BT3-*3]3.4 确定进化机制

采用交叉、变异和选择3种算子作用于进化过程,具体过程如下：

(1) 交叉：用转轮法选择N个用来繁殖后代的个体,并放入杂交池中。从杂交池中任选2个个体作为父、母代个体,根据预先设置的交叉率Pc进行或者复制,重复该过程,最后得到N个子代个体。交叉过程是遗传算法中很重要的部分,交叉率的选择将直接关系到算法的性能,Pc过高,群体中个体的更新越快,则高性能个体的破坏也越快,Pc过低,相对来说,搜索范围就会变小,易造成算法停滞不前,交叉率Pc需要根据经验值来选取,经过实验令Pc=0.8效果较好。И

(2) 变异:变异操作,用以模拟生物在自然界的遗传环境中由于各种偶然因素引起的基因突变。其方法是根据生物遗传中基因变异的原理,以变异率Pm对某些个体的某些位执行变异。即对执行变异的对应位求反,把1变为0,把0变为1。单靠变异不能在求解中得到好处,但是他能保证算法过程中不会产生无法进化的单一群体。因为在所有的个体一样时,交叉是无法产生新的个体的,这时只能靠变异产生新的个体。也就是说,变异增加了全局优化的特性。具体做法是：根据突变概率Pm,对杂交池中的个体进行变异操作,最后得到后代的群体。在有交叉环节的情况下令Pm=0.05。

(3) 选择:将得到的N个后代个体与N个父代个体共2N个个体,按其适应值从大到小依次排列,取前N个个体形成下一代群体。

3.5 停止运行的准则

迭代终止的条件为达到种群进化的最大代数IА

ИI=log2 WИ

W是最大运动偏移量,他的值由搜索窗决定,搜索窗越大代数越多。在MPEG4标准中,图像块大小为16×16,故本文中取W=16,则种群进化的最大代数I=4。若达到此最大代数则迭代终止,得到最优匹配点,如果不满足条件,则执行交叉,变异,选择。 И

3.6 算法流程

算法流程如图3所示。

图3 算法流程图

4 实验结果及分析

在表1和表2中,列举采用本文算法和FS,DS搜索法后得到的PSNR值,以及采用他们所需要的搜索点数。在实验中,采用两个典型的标准测试序列foreman.yuv和coastguard.yuv来验证该算法的性能指标,这两个序列均为CIF格式,速率为30 f/s,他们还有一个特点就是图像运动剧烈,摄像机镜头移动幅度比较大。本文对这两个测试序列中的30帧图像进行运动估计,计算出他们的PSNR值与运动估计搜索点数,并将他们的值和FS,DS搜索法的值相比较。在做运动估计时,图像块大小为16×16像素,染色体长度L=10,交叉率Pc=0.8,变异率Pm=0.05,搜索窗大小为33×33,最大迭代次数I=4。

表1 采用3种算法得到的foreman的Y,U,V三分量的PSNR

表2 采用3种算法得到的 coastguard的Y,U,V三分量的PSNR

通过比较可以看到,采用本文算法,可以使用最少的搜索点搜索到最优点,PSNR值较FS略有降低,但略高于DS算法。这是由于本文采用了选择、交叉、变异等遗传算子,且在产生初始种群时考虑了运动矢量具有中心偏移特性以及相邻宏块运动相似,既防止早熟现象,又保证了种群的进化收敛,避免陷入局部最优,从而得到全局最优解。

5 结 语

将遗传算法应用于视频压缩的运动估计部分,引入全局优化思想,同时考虑运动矢量具有中心偏移特性以及相邻宏块运动相似,避免了局部最优,极大地提高了算法性能。实验结果表明,本文算法得到的PSNR值略低于FS,略高于DS算法,而搜索点数较上两种算法大大减少,减少了计算量,提高了速度,可以很好地应用于MPEG4视频压缩编码中。

参 考 文 献

［1］Chow K H K,Liou M L.Genetic Motion Search Algorithm for Video Compression\[J\].IEEE Trans.,Circuits Syst.Video Technol.,1993,3:440 445.

［2］Lin Chunhung,Wu Jaling.A Lightweight Genetic Block Matching Algorithm for VideoCoding\[J\].IEEE.Trans.Circuits Syst.Video Technol.,1998,8:386 392.

［3］Zhu Shan,Ma K K.New Diamond Search Algorithm for Fast Block Matching Motion Estimation\[C\].Int′L.Conf.on Information,Commun And Signal Proc.(ICICS′97),Singapore,1997.

［4］Holland J H.Adaptation in Natural and Artificial Systems\[M\].2nd Edition.CambridgeMA:MIT Press,1992.

［5］雷英杰,张善文,李续武.Matlab遗传算法工具箱及应用 ［M］.西安:西安电子科技大学出版社,2005.

［6］龚涛,丁润涛,一种基于改进的遗传算法的块匹配运动估计方法［J］.信号处理,2003,19(3):207210.

［7］李|,徐维朴,郑南宁,等.一种新的基于遗传算法的快速运动估计方法［J］.电子学报,2000(6):115118.

［8］刘伟峰,庄奕琪,屈文博,等.基于TMS320DSC21的视频编码系统设计\[J\].现代电子技术,2005,28(12):7679.

作者简介 陈 红 女，1980年出生,西安工业大学电子信息工程学院助教,硕士研究生。主要研究方向为图像处理、通信技术、信息论与编码。

齐 华 女，1963年出生,西安工业大学教务处副处长、高教研究室主任。主要研究方向为信息论与编码、图像处理。

张 健 男，1980年出生,西安工业大学电子信息工程学院硕士研究生。主要研究方向为图像处理、通信技术。

注：本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文