（模式识别与智能系统专业论文）基于对象的视频图像运动估计与补偿方法研究.pdf

华中科技大学硕士学位论文 一= = = ；= = = = = = = = 目= ；目日_ ；2 = ；= ；= = = ； 摘要 运动补偿技术是数字视频图象压缩的关键技术之一，传统的基于块的运动补偿技 术已经发展的非常成熟，但是基于块的运动补偿的本质缺陷使得进一步增加压缩率变 得很困难，为了解决诸如低码率下的视频传送、交互视频操作、基于内容的视频检索 ，1 一 等视频应用，人们不断研究各种更先进的视频压缩方法。其中 基于对象的运动补偿是 一个热门的研究领域，这也是m p e g 一4 标准所提出来的概念之一。 在本文中我们完成了一个基于对象的视频图象运动估计与补偿算法。它通过自动 提取和跟踪连续帧间的运动对象，进而估计对象的仿射运动参数来达到运动补偿的目 的。 、 在提取运动对象之前磊翻采用了全局运动补偿来克服背景运动对真正运动对象 检测的影响。在全局运动补偿中我们使用了仿射变换模型，并且运用了分级的运动估 算来减少计算量。搜索算法采用了遗传算法以获得全局搜索能力。 在对象模板获得过程中，我们使用了变化检测来得到变化区域，并在此基础上提 出了两种方法来保证得到正确和完整的运动对象。f 首先，我们收集多帧的背景信息的 方法去除变化区域中的显露背景和噪声区域；其次，结合空间的静止分割获得完整的 运动对象模板。 后续帧中的对象运动参数估计采用了仿射变换下的配准以得到对象的运动参数， 配准准则使用最大互信息法以保证精度。为了防止运动对象的变形对后续运动参数造 成的影响，我们对对象进行了跟踪并用跟踪后的对象更新对象模板，跟踪使用了区域 相似度度量，判别准则为最大后验概率法。 本文提出的方法能够比较好的在背景具有运动且运动对象没有发生遮挡的情况 下完成运动对象的检测和运动参数的估计，可以用于低码率视频压缩、视频交互等应 用中。 、 ，一 关键词：运动补偿视频对象视频分割背景定位分水岭 华中科技大学硕士学位论文 a b s t r a c t m o t i o n c o m p e n s a t i o n i so n eo fk e yt e c h n o l o g i e si n d i g i t a l v i d e o c o m p r e s s i o n t r a d i t i o n a lc o m p e n s a t i o na l g o r i t h m sb a s e do nb l o c k m a t c h i n gh a v eb e e nw e l l d e v e l o p e d ， b u tt h ee s s e n t i a ld r a w b a c k so fb l o c k m a t c h i n ga l g o r i t h mc u m b e rt h ef a r t h e rg a i n i n c o m p r e s s i o nr a t i o i n o r d e rt om e e tt h ed e m a n do fl o wb i t r a t i ov i d e o st r a n s f e r r i n g ， i n t e r a c t i v ev i d e oo p e r a t i o na n dc o n t e n t - b a s e di m a g ei n d e x i n g ，p e o p l eh a v eb e i n gd e v e l o p e d v a r i o u sa d v a n c e dv i d e oc o m p r e s s i n gt e c h n o l o g i e s t h em o t i o nc o m p e n s a t i o na l g o r i t h m b a s e do nv i d e oo b j e c t si sah o tr e s e a r c hf i e l d ，f i r s tp r e s e n t e db ym p e g - 4 i nt h i sp a p e rw e c o m p l e t eam o t i o ne s t i m a t i o na n dc o m p e n s a t i o na l g o r i t h mb a s e do n v i d e oo b j e c t t h i sa l g o r i t h mc a nc o m p e n s a t et h eo b j e c t sm o t i o nb ye x t r a c t i n ga n dt r a c k i n g o b j e c t sb e t w e e n c o n s e c u t i v ef r a m e s b e f o r ew ec a ng e tr e a lo b j e c t sw e e x p l o i tt h eg l o b a lm o t i o nc o m p e n s a t i o n t oe l i m i n a t e t h ei n f l u e n c e so fb a c k g r o u n d sm o t i o n w eu s ea f f i n et r a n s f o r m a t i o na sm o d e lo fg l o b a l m o t i o n ，a n d u s eh i e r a r c h i c a lm o t i o ne s t i m a t i o nt od e c r e a s e c o m p u t a t i o nc o m p l e x i t y m e a n w h i l ew e a d o p t t h eg e n e t i ca l g o r i t h mt og a i ng l o b a ls e a r c h i n ga b i l i t y i np r o c e s so fo b j e c te x t r a c t i o n ，w eu s ec h a n g ed e t e c t i o nt og e tc h a n g e dr e g i o n s ，a n d p r e s e n tt w om e t h o d st oa s s u r et h ea c c u r a c yo f e x t r a c t e do b j e c t s f i r s t ，w ea c c u m u l a t et h e b a c k g r o u n di n f o r m a t i o no fs e v e r a l f r a m e ss oa st ow ec a n g e t r i do ft h eu n c o v e r e d b a c k g r o u n di nc h a n g e dr e g i o n s t h e ni n c o m b i n a t i o nw i t hs p a t i a l s e g m e n t a t i o nw eg e t w h o l e o b j e c t s i ns t a g eo fm o t i o n e s t i m a t i o n ，w eu s ei m a g er e g i s t r a t i o nb a s e do na f f i n et r a n s f o r m a t i o n t og e tm o t i o np a r a m e t e r s i no r d e rt oa s s u r e p r e c i s ew ea d o p tm a x i m u m m u t u a li n f o r m a t i o n o , sr e g i s t r a t i o nc r i t e r i o n w et r a c kt h eo b j e c t s t d e f o r m a t i o na n du s et r a c k e d o b j e c tt or e p l a c e o l do b j e c tt e m p l a t e ，t h r o u g hw h i c hw ec a na v o i dt h ei n f l u e n c eo f o b j e c t sd e f o r m a t i o no n s e q u e n t i a lm o t i o n e s t i m a t i o n f h em e t h o d p r e s e n t e di nt h i sp a p e rc a ne f f e c t i v e l ye x t r a c tm o v i n go b j e c t sa n de s t i m a t e t h e i rm o t i o np a r a m e t e ri nc o n d i t i o no fm o v i n gb a c k g r o u n d i tc a nb eu s e di nv a r i o u s a p p l i c a t i o n ss u c h a sl o wb i t r a t i ov i d e oc o m p r e s s i o na n di n t e r a c t i v ev i d e o o p e r a t i o n e t c i i 华中科技大学硕士学位论文 k e y w o r d s ：m o t i o nc o m p e n s a t i o n ，v i d e o0 b j e e t ，v i d e os e g m e n t a t i o n ， b a c k g r o u n dr e g i s t r a t i o n ，w a t e r s h e d i i i 牮中科技大学硕士学位论文 iv-, = = = = = ；= = = ；= ；= 目= _ = = = = = 目 1 绪论 当人们尽情享受着日新月异的多媒体应用如高清晰电视，可视电话，多媒体移动 手机等时，没人注意到背后突飞猛进的数字视频技术的强大支撑。想象一下一部 6 4 0 x 4 8 0 、真彩色、帧率3 0 帧秒，片长3 分钟的未经压缩的影片会占据你多达3 g 的 硬盘空间，你就会意识到数字视频压缩技术的巨大作用。实际上，正是数字视频技术 的不断发展推动着多媒体视听应用产品的更新换代。 1 1 课题简介 在视频编码系统中，运动补偿技术是一种非常通用有效的数据压缩技术视频 图像上的运动部分在帧与帧之间必然有连续性，即帧与帧之间存在冗余。运动估值与 补偿就是根据这一特性，将当前图像中画面的运动看作是前面某时刻图像中画面的 位移，位移的幅度和方向在图像中的各处可有不同。利用这些位移信息和前面某时刻 的图像可以重构当前图像。目前使用最广泛的运动估计与补偿技术是基于块匹配的运 动估计与补偿，这种方法算法简单，运算量少，便于硬件实现，但是它是基于运动只 存在平移的假设之上，因此对于复杂的运动情况下，它的预测效果并不好，导致压缩 码率的下降。为了克服这个缺点，各种先进的运动估计与补偿技术在不断的研究中， 力图能更准确的预测物体的运动。 本课题来自于航天科技创新基金资助。目的是研究一种基于仿射变换的任意形状 对象提取和匹配搜索算法，能够跟踪运动物体的复杂运动，包括平移、旋转、缩放等。 克服常用的块匹配算法只能跟踪物体平移运动的缺点。应用于视频图象压缩中，由于 可以更全面的描述物体的运动，因此能够达到比采用常规块匹配压缩算法更高的压缩 率。应用于物体跟踪及监控领域可以更精确稳定的跟踪物体。 i 华中科技大学硕士学位论文 1 2 视频压缩技术和标准简介 视频序列包含有大量的数据，但是这些数据是有冗余的，因此对其压缩才成为可 能。视频图象的压缩是通过去除空间和时间方向上的冗余进行的，空间的冗余以一帧 图象中的象素点和其邻域存在相关来表示，而时间上的冗余则以图象序列中连续的两 帧间存在相关来表示。另外，人类的视觉系统具有一个特别的生理特点即人眼对于图 象中高频部分的变化不如对于图象低频部分的变化敏感，也就是说人眼能够容许图象 高频部分出现较大的误差。这一点使得人们可以对图象高频部分进行较粗的量化以达 到压缩的目的。 目前存在着多种压缩标准应用于c d r o m ，数字电视广播，远程多媒体教学和娱乐， 视频会议，多媒体数据库等诸多领域。不过最广泛使用的还是国际电信联盟( i t u ) 和m p e ( ；组织制定的视频压缩标准。 i t u 开发了h 2 6 1 、h 2 6 3 标准以用于诸如视频会议之类的视频服务领域。h 2 6 1 用于码率在6 4 k b s 以上的应用中，而h 2 6 3 主要用于低于6 4 k b s 的低码率应用场合。 国际标准化组织( i s o ) 于1 9 8 8 年建立了运动图象专家组( m p e g ) 以开发有关视 频方面的标准。在1 9 9 2 年和1 9 9 4 年m p e g 分别制定出了m p e g 一1 和m p e g 一2 视频压缩 标准。m p e g - 1 主要用于最高至1 5 m b s 的c d r o m 和多媒体应用中的音视频压缩。 m p e g 一2 设计为向下兼容m p e g l ，它提供了高达4 3 0 0 m b s 的高画质图象以满足h d t v ， 高清晰数字广播，d v d 等应用的需要。 m p i ! g 于1 9 9 8 年完成了m p e g 一4 标准的制定。不同于上面的面向帧编码的压缩标准， m p e g 一4 面向对象编码。它的设计目的是为各种不同码率应用提供有效的编码方法，以 及为视频应用提供人机交互。m p e g 一4 的应用场合包括网络多媒体、视频会议、视频电 话、无线多媒体、媒体库等。 上面除m p e g 一4 以外的其他视频压缩标准都属于传统的面向帧编码的方法，其基 本工作原理大致相同，流程如下： 华中科技大学硕士学位论文 这里编码方式分为两种，帧内编码和帧阳j 编码。帧内编码是为了去除数据的空间 冗余，主要过程是变换编码一 量化一 行程编码一 熵编码。帧间编码是为了去除数 据的时间冗余，主要过程是基于块的运动估计与补偿一 d p c m 一 d c t 变换一 量化一 行程编码一 熵编码。 变换编码可以将一组相关的数据变换为一组相互独立的互不相关的因子，一般变 换都是线性和正交的。通常我们选择的变换都将能量集中在少数一些因子上，这个特 性是信号压缩所需要的，通过量化这些因子我们可以达到压缩的目的，并且对能量较 少的因子进行粗量化或者舍弃能进一步进行压缩。最常用的变换编码是离散余弦变换 ( d e t ) ，实际图象压缩中是将图象分成n x n 的矩形块，分别对这些矩形块进行变换。 为了描述预测编码先介绍脉码调制( p c m ) ，它对模拟信号进行采样，然后对每个 采样值用预先设定好的一组数值进行量化。预测编码里普遍使用的是差分脉码调制 ( d p c m ) 。其基本原理是用前面已编码的数据来预测当前的数据，然后对预测误差( 当 前数据与预测数据的差值) 进行编码。 视频压缩中预测编码使用的预测方法是运动估计与补偿。它利用了连续帧间的时 间冗余性。运动估计与补偿是视频压缩中最复杂和最耗计算量的部分。大部分常用的 视频压缩方法采用基于块的运动估计与补偿。他们假设场景中运动是平移的并且平行 于摄像机平面从而忽略了旋转和缩放运动。另外，还需假定在运动过程中光照条件是 不变的，这样才能在不同帧问认定具有相同象素值的象素是匹配的。基于块的运动估 华中科技大学硕士学位论文 计框图如下： 图1 一l ：基于块匹配的运动估计过程 当前帧被划分为块，每个块用其左上角的坐标( x ，y ) 表示。为了预测这个块， 我们在参考帧以初始位置( x ，y ) 为中心标出一个搜索区域，然后在此区域内搜索出 一个最佳的匹配块，位于( x + i ，y + j ) ，它们之间的偏移( i ，j ) 叫做运动矢量。也 就是说对当前帧的每一个块都能够用参考帧中的一个块加上运动矢量来预测。 块的搜索方法最简单的是全搜索法，也就是对每一个搜索位置都进行计算，勿庸 置疑，这种方法是计算量很大的。为了减少计算量，人们发展了很多快速搜索算法如： 三步法，菱形搜索法，金字塔分级法等。但是这些快速搜索算法通常只能达到局部最 优，而不能确保达到全局最优。 1 3 先进的运动补偿技术 基于平移的块模型的运动估算是简单的，但它处理逐帧的块旋转和变形以及运动 场中的不连续值时效果却不好。平移模型的失效导致错误的匹配结果，使得重建图象 容易出现马赛克等所谓的块效应。 由于这个效应，o r c h a r d 1 提出了后处理法来重建基于图蒙分割的高分辨率的运 动场。在这个方法中，如通常一样，首先，每一个块估算一个单一的运动矢量，接着， 图象块被分成k 个区域，每一个区域用一个单一的运动矢量表示。为避免附加矢量的 4 华中科技大学硕士学位论文 然后，从k 个待用的运动矢量集合中选择运动矢量，求块的每一个象素d f d 的最小值。 此法改善了常规块运动估计的效果，并且计算量增加不多。 另外，变形的块匹配 2 是另一种有效的补偿技术。它使用了基于仿射变换透视 变换的块匹配。当前帧被分成三角形，长方形或任意的四边形小块，接着在给定的空 间变换中，我们在搜索帧中找到最佳匹配三角形或四边形。分割块形状的选择和空间 变换是互关联的。例如，三角形分割块提供了猪狗的仿射变换的自由度，这个仿射变 换仅仅有六个独立参数。透视变换和双线性变换有八个自由参数，因此它们很适合用 于长方形和四边形分割块。与平移模型相比，仿射和透视空间变换很明显提供了更优 越的运动跟踪和重现技术，特别是在旋转和缩放的情况下。然而，运动估计的复杂度 也大大增加了。 除了块匹配估计，基于视频对象技术的运动补偿是另一个研究热点。这也是 m p e g 一4 标准所使用的技术。它将场景中的运动对象作为单独的个体提取出来，并且进 行单独的编码。这种方法同基于块的方法不同，它能够精确跟踪对象的轮廓，因此能 够完美的匹配运动对象。基于对象的运动补偿技术的难点在于运动对象的精确提取， 初始对象的不正确会影响后续帧中跟踪结果的不确定。 韩军”1 提出并实现了一种用于分割及跟踪视频运动对象的时空联合方法该方法 首先采用连续帧间差的4 次统计量假设检验，确定运动对象的位置，自动地分离出 运动区域与背景区域；在运动区域内，采用数学形态学的分水岭算法来精确地提取运 动对象的轮廓：最后，将提取到的运动对象作为模板，对后续的视频序列，用 h a u s d o r f f 距离度量，来跟踪并提取后续帧中运动对象。该方法能有效地分割和跟踪 视频运动对象，且能有效减少计算复杂度，其调整参数也较少。 y uz h o n g “1 等提出了一种基于可变形模板的跟踪技术，模板随时间不断变化。首 先通过勾勒轮廓或者自动检测等方法获得对象的先验知识，用对象的边界来表示，称 为对象的原型。然后在这个原型上运用参数化的变形变换以得到变形模板。对象的变 形由对变形参数施加一个概率分布得到。变形模板通过从静止图象特征中计算的概率 场和输入图象相互作用，匹配结果用一个综合考虑形状偏差和变形模板对输入图象真 实度的目标函数来评估。 华中科技大学硕士学位论文 另一种广泛使用的对象跟踪方法类似于可变形模板技术，也是着眼于对象的轮 廓，以不断适应每帧间对象轮廓的变化来跟踪对象，这就是活动轮廓技术 5 6 7 8 9 。相对上面的技术，它少了模板的匹配过程，每一帧的轮廓变化结 果就认为是对象在此帧中的实际轮廓。 1 4 本文的研究内容 本文试图提出一种基于仿射变换的运动补偿技术，通过提取出序列图象中的运动 物体，并计算出运动物体帧间仿射运动参数来达到补偿目的。本文的研究内容主要在 如下四个方面： 1 ) 消除背景运动对于运动对象检测的影响，也就是研究全局运动补偿算法。 2 ) 变化区域中真正运动对象的识别，也就是研究如何在变化区域中去除显露的 背景和噪声。 3 ) 研究一种精确分割出对象边缘的分割算法以帮助获得精确到边缘的运动对象。 4 ) 运动对象的仿射运动参数估计算法。 本文使用的方法的基本思路如下：首先使用了基于遗传算法的全局运动补偿以抵 消背景运动的影响，再利用多帧的背景标记技术分离出可信的无变化的背景，从而得 到位于变化区域中的部分运动对象，然后在利用空间静止分割划分出每帧中对象的轮 廓，结合背景定位阶段获得的部分运动对象提取出实际的运动对象模板。最后使用仿 射变换配准获得运动对象的运动参数，并且利用基于最大后验概率准则进行后续帧中 运动对象模板的跟踪和更新。流程图如下： 6 华中科技大学硕士学位论文 图1 2 算法流程图 本文后续内容安排如下： 第二章：全局运动估计与补偿 本誊研究了全局运动补偿算法以抵消镜头的平移、旋转以及缩放等。建立了获得 最优全局运动参数的仿射变换模型，判决标准使用最小均方误差，搜索算法采用了简 单遗传算法以确保以更大的概率命中全局最优值。 第三章：基于多帧的背景定位 为了获得真正的运动对象和去除噪声的干扰，我们采用基于多帧的背景定位法来 判别运动区域中那些属于显露的背景，那些属于运动对象。在多帧图象中长时间保持 不变的点被划分为背景，其余的被认为是运动对象的一部分。最后使用了连通算子来 清除由于噪声引起的小块的变化区域。 第四章：基于分水岭变换的静止分割 本章我们研究如何使用基于分水岭变换的静止分割来获得图象中颜色一致的区 块，以此得到精确划分对象边缘的分割图。我们提出了平坦区域算子来获得表征图象 区块均匀性的均匀性图，对均匀性图进行二值化得到分水岭变换使用的标记，最后进 行分割。结合上一章得到的部分运动对象，所有包含这些部分运动对象的分割块被挑 选出来，经过合并得到真正的运动对象。 第五章：对象提取与仿射参数估计 上一章获得的运动对象在这里作为初始的运动对象模板使用，在当前帧进行基于 仿射变换模型的配准以得到运动对象的运动参数。为了在后续帧中跟踪对象的变化并 且更新对象模板，我们使用了基于最大后验概率的判决准则。当前帧同样经过分水岭 华中科技大学硕士学位论文 变换来得到一个分割图，配准后的运动对象模板作为先验知识，然后对每一个区块进 行二类( 场景中仅有一个运动对象，也就是图中仅含有两类：对象和背景) 判决或者 是多类判决( 场景中有多个运动对象) ，最后获得更新后的对象模板 第六章：总结 8 华中科技大学硕士学位论文 ：= = = = # = = ；= = = = = = = = i ；= ；= = = = = = # ；= = 2 全局运动估计与补偿 在摄像机固定也就是背景固定的场合中，所有的图象变化都是由前景对象的运 动造成的( 假设不计噪声的影响) ，因此对变化区域的检测就基本等同于对运动对象 的检测。而在实际大多数的视频图象r 1 ，摄像机往往并不是固定不动的，会存在各种 运动，造成图象中不仅存在运动对象的变化，还有背景图象的变化。在背景纹理复杂 的情况下，有可能使得背景留下的变化区域远大于真正对象运动造成的变化区域，从 而造成完全不能识别出运动对象的情况。想要正确的识别出真正的运动物体，就必须 去除摄像机运动的影响，也就是补偿j 彳景的运动，这称之为全局运动补偿。 2 1 全局运动估计原理和方法 假设u ( x ) 和v ( x ) 是在背景存在运动情况下获取的两幅连续图象，要补偿它们之问 的全局运动就是要定义一个相似性测度，并寻找一个运动模型( 空问变换关系) ，使 得经过该空间变换后，两幅图象间的0 1 h 以性达到最大。 2 1 1 基于仿射变换的全局运动估计 摄像机的运动是一个刚体运动，包括平移、旋转、缩放等。这个刚体运动可以用 仿射变换模型【1 1 】来描述。假设用五a o ，表示t 时刻的图像，x , y 表示象素点坐标，x ，y 表示另一时刻象素点新的坐标。采用、参数模型来表示两个时刻图像之间像素的对应 关系： f xr ：a x + b y + c 1 。 (21)d 【y = x + e y + f 7 在该模型下定义参数矢量p ：c 4 p 力，其中分量c , f 与平移运动有关，分量 q 6 ，c d 与放缩、旋转运动有关。这样，在穴参数模型下就可以由参数矢量p 用五“ 预测厶“，+ 似彤，其中似圳和以。，+ 卜、，中的位置对应关系满足六参数模型，即 ：， 矿：，+ 奶j ： ( 2 _ 2 ) 、y h - = 叔t + e y t + f 。 9 华中科技大学硕士学位论文 = 一一= = = ；= ；= ；j ；目； 全局运动估计问题就成为求解最优的运动模型参数p 的问题，使得模型参数在 p 时预测图像以。，+ 似彤和实际，+ a t 时刻图像。以最相似。相似性度量可以用一 个目标函数来表示。相似性准则采用最小均方误差法l s e ： 户= a r g m i n 0 ( p ) = a r g m i n d 1 t + & + ( x ，y ，p ) 一，。m ( x ，y ) i d ( 2 4 ) 即寻找一个p 使得目标函数o ( p ) 最小，这是一个典型的最优化问题。 2 i 2 仿射变换下目标函数的计算 图象处理中使用的数字图象是真实世界图象的离散化，一般可用矩阵来表示。我 们用矩阵a 表示参考图象，矩阵b 表示当前图象，i g z , 目标函数口( p ) 就可以写 为： o f p ) ：宝卦。i i f lj = i ( 2 5 ) 口。表示a 中位于第i 行第j 列的元素，b + 。表示b 经过仿射变换后位于第i 行第 j 列的元素。这个公式并不能直接使用，因为对于b 中的任一点进行仿射变换后， 其坐标可能不再位于整数点上，需要进行插值处理。而且，a 矩阵中的坐标范围是( 1 ， 1 ) ( m ，n ) ，变换后的坐标可能越出了这个界限。这部分越界的象素应该是忽略不 计的。对于插值处理，由于b + 矩阵中的坐标非整，而且相邻元素坐标的相对关系未 知将b + 的元素插值到对应于a 整数坐标上的计算就比较复杂，我们这罩采用相反 的做法，对a 矩阵进行插值取得对应于b + 元素坐标的值。最简单的插值法莫过于近 邻插值，对于插值区间的任一点都以常数代替。例如，已知f ( 口) 和f i b ) 要对区间( a ， b ) 进行插值： 肋m ( 口) 或掣m 印，6 ) ( 2 6 ) 近邻插值虽然计算简单，但是不能反映同一插值区间内不同位置点的函数值，这样当 b 中有多个象素都映射到一个插值区间时，对插值都只有一个结果，这样就造成了 计算误差。由于插值区间为一个象素大小，换句话说，常数插值不具有亚象素精度。 为了保证亚象素精度，我们采用双线性插值法，用线性关系去估计待插值区域的函数 关系。考虑由( i ，j ) 、( i + 1 ，j ) ( i ，j + 1 ) 和( i + 1 ，j + 1 ) 围成的区域，落在此区 1 0 华中科技大学硕士学位论文 域的任一点的值d “( ( f ，i + 1 ) ，( ，j + 1 ) ) 可由线性插值公式得到： a k t2 ( i + l - k ) ( j + 1 一f ) 。p + ( k - i ) ( ，+ 卜f ) 。+ l ，7 ( 2 7 ) + ( i + 1 一七) ( ，一j ) a u + l + ( k f ) ( ，一j ) a h j + i 另外一个需要解决的问题是由于仿射变换后有部分越界元素被丢弃了，那么每次 搜索位置计算的有效象素数是不同的，这会导致o ( e ) 的不准确，即有这种可能：不匹 配的位置由于计算象素少而使o ( p ) 值比那些实际更匹配的位置的值小，从而导致错误 的判断。这样对不同位置计算出来的o ( p ) 值进行标准化是有必要的。我们用每次计算 的有效象素数作为标准化分母，完整的流程如下： ( i ) 取b 中一个未计算的元素b 。 ( 2 ) 计算在变换参数p 下b 。仿射变换后的新坐标( i ，j ) ( ：3 ) 判断( i ，j ) 是否在合法的坐标范围内( 1 ，1 ) ( m ，n ) ，若坐标合法， 对矩阵a 插值取得对应此坐标的值珥。若不合法，则此点被抛弃。 ( 4 ) 计算目标函数8 ( p ) 和有效象素数m 臼( ，) = 口( p ) + 怫厂6 口l ，m = m + l ( 5 ) 是否还有未计算的元素，有则转到( 1 ) ，否则继续下一步 ( 6 ) 进行标准化处理 州耻民 2 1 3 分级全局运动估计 全局运动估计是一个非常耗时的计算过程，以3 2 0 x 2 4 0 大小的图象序列为例， 每计算一个p 值对应的目标函数所需要的计算次数是7 6 8 0 0 次，而每次计算都包括坐 标的仿射变换、线性插值、均方差的计算。因此，为了提高计算速度，必须采取一些 优化计算方法。我们使用了分级运动估计来减少计算量。 分级运动估计利用了图象的分层表示。其基本思想是从最低分辨率开始，在每层 依次进行运动估计。较低分辨率级用于确定全局运动参数的粗略估计，由于此时分辨 率较低，进行计算的点数大大减少，可以很快的获得一个低分辨率估计，接着把低级 分辨率级的参数的估计值传递到下一个高分辨率级，用来作初始值，以获得进一步精 华中科技大学硕士学位论文 ：j = = = = = _ = = = = = 4 = = _ = _ = l l _ _ l = _ = = 确的参数值。由于已经有了一个粗略的估计值，在高分辨率级进行参数估计时就可以 缩小搜索范围，只在粗略值附近的空间进行搜索。 图象的分层表示是通过对原始图象进行低通滤波和二次采样得到。为了减少计算 量，我们可以通过用局域平均值代替每一个象素的方框型滤波器来实现低通滤波。每 次采样的问隔设为2 。 2 2 参数估计中的搜索算法 2 2 1 基于梯度的搜索算法 我们处理的是离散的数字图象，在目标函数臼和参数矢量j p 之间并无解析表达 式，因此只能用数值算法计算最优解。最简单也最重要的一类数值解法是最速下降法 1 1 】。假设取p 的初始值为p o ，将e ( p ) 在p o 处展开为泰勒级数： o ( e ) z 目( 最) = o ( e o ) + 0 ( 最) ( 只一r ) ( 2 - - 8 ) 要使鲥p ) 最小也就是近似的使口( 只) 最小，假设最小值为m ，则有 口( e o ) + p 。( p 0 ) ( 最一i o ) = m j 最一e o 错 c z 咖， j 只e o 筹 这里只就是下一步迭代的参数矢量，照此不断进行下去赢到臼( 最) 小于一个预设的阀 值。从( 2 - - 8 ) 式可以看出，这里是用了一个线性表达式去逼近8 ( p ) ，也就是用线性 函数关系去预测p 和参数矢量尸之间的变化关系。就( 2 - - 9 ) 式本身而言，它是将只 点的梯度负方向作为变化方向，口是步长因子，决定着收敛的快慢与否。 最速下降法是否收敛与初始点r 的选择有关，并且只会收敛到离异点最近的一 个极小值区域，也就是说它并不能保证取得全局极小值。而且对于一般的函数在极小 值附近都接近于二次函数，最速下降法在收敛到极值附近后收敛速度就会很慢。为了 克服这个缺点可以采用n e w t o n 法 1 2 】。n e w t o n 法原理基本和最速下降法一样，不同 的是它采用泰勒二次展开式来逼近o ( p 1 ， 华中科技大学硕士学位论文 p ( j p ) 。曰( b ) ：o ( p o ) + 0 ( e o ) c e k p o ) + 旦：生垦2 掣 ( 2 1 0 ) 要求毋( 只) 的最小值也就是求( 茸) = 0 的点，对于( 2 - - 1 0 ) 式左右两边同时取导数有 0 。( 只) = 0 ( r ) + 0 ”( p o ) 只 钾( 驴。j b 一器 ( 2 叫1 ) n e w t o n 法不仅利用了只点的导数信息，而且利用了p o 点的二阶导数信息。从物理意 义上说，也就是说它不仅利用了速度信息，而且利用了加速度信息，能够更准确的预 测0 随尸点的变化情况，对于二次函数，一次迭代即可达到最优点。 2 2 2 基于遗传算法的搜索算法 遗传算法【1 3 】是一类借鉴生物界自然选择和自然遗传机制的随机化搜索算法，由 美国j h o l l a n d 教授提出，其主要特点是群体搜索策略和群体中个体之间底信息交换， 其搜索不依赖于梯度信息，它尤其适用于处理传统搜索方法难于解决的复杂和非线性 问题。 遗传算法的内涵乃是启迪于自然界生物从低级、简单，到高级、复杂，乃至人类 这样一个漫长而绝妙的进化进程，借鉴于达尔文的物竞天演、优胜劣汰、适者生存的 自然选择和自然遗传的机理，其本质是- 3 + 求解问题的高校并行的全局搜索方法。它 能在搜索过程中自动获取和积累有关搜索空间的知识，并自适应的控制搜索过程以求 得最优解。 遗传算法的两大特点是群体搜索策略和群体中个体之间的信息相互交换，它实际 上是模拟由个体组成的群体的整体学习过程，其中每个个体表示给定问题搜索空间中 的一个解点。遗传算法从任一初始化的群体出发，通过随即选择( 使群体中优秀的个 体有更多的机会传给下一代) 、交叉( 体现了自然界中群体内给体之间的信息交换) 和变异( 在群体中引入新的变种确保群体中信息的多样化) 等遗传操作，使群体一代 一代地进化到搜索空间中越来越好地区域，直至抵达最优解点。 遗传算法和其他的搜索方法相比，其优越性主要表现在以下几个方面：首先，遗 传算法在搜索过程中不易于陷入局部最优，即使在所定义的适应度函数非连续。不规 则和伴有噪声的情况下也能以极大的概率找到全局最优解；其次，由于遗传算法周有 华中科技大学硕士学位论文 的并行性，使得它非常适合于大规模并行处理； 1 遗传算法的介绍【1 4 】 遗传算法是具有生成+ 检测的迭代过程的搜索算法，它的基本处理流程如图2 1 所示。 由图2 1 可见，遗传算法是一种群体型操作，该操作以群体中的所有个体 圈2 1 遗传算法流程图 作为对象。选择、交叉和变异是遗传算法的三个主要的操作算子，它们构成了所谓的 遗传操作，使得遗传算法具有了其他传统方法所没有的特性。遗传算法中包含7 z l 下 5 个基本要素： 1 ) 参数编码 2 ) 初始群体的设定 3 ) 适应度函数的设计 4 ) 遗传操作设计 5 ) 控制参数设定( 主要是指群体的大小和遗传操作的概率等) 这5 个要素构成了遗传算法的核心内容。这里我们以一个简单的函数极值求解为例， 来说明遗传算法的基本概念和处理过程。 假定用遗传算法求函数f ( x ，y ) = x 2 + y 2 的最大值，x 0 , 3 1 ，y 0 ，3 1 】。 a 参数编码 由于遗传算法不能直接处理解空间的解数据，因此我们必须通过编码将它们表示 成遗传空间的基因型串结构数据。最常用的是将参数表示成二进制无符号整数表示形 式，如参数x = 5 可以表示成0 1 0 1 。这里有两个参数x ，y ，由于x 和y 均小于3 2 ， 我们可以用一个5 位的二进制整数串来表示每一个参数变量，这个5 位的二进制整数 串叫做基因子串，将这两个子串连接起来就组成了一条完整的染色体。假设解空间有 4 华中科技大学硕士学位论文 一个点( x = 1 2 ，y = 2 0 ) ，在遗传算法中这也叫一个个体，它的x 对应的基因子串为 0 1 1 0 0 ，y 对应的基因子串为1 0 1 0 0 ，它的完整的染色体就是两者相连0 1 1 0 0 - - 1 0 1 0 0 。 b 初始群体的生成 由于遗传算法的群体型操作的需要，所以我们必须为遗传操作准备一个由若干初 始解组成的初始群体。初始群体的大小与进化结果的优劣紧密相关，群体越大，则群 体中个体的多样性就越高，算法陷入局部解的危险性就越小。初始群体的每个个体都 是通过随机的方法产生。如果对最优解的分布范围具有先验知识，我们可以采用高斯 分布来产生个体；如果对最优解一无所知，我们可以采用在解空间的均匀分布来产生 个体。初始群体也称为进化的初始化，即第一代。 c 适应度函数的设定 遗传算法在搜索进化过程中一般不需要其他的外部信息，仅用评估函数值来评估 个体或解的优劣，并作为以后遗传操作的依据。评估函数值又称为适应度，它表示了 个体对环境的适应程度。这里我们直接用f ( x ，y ) = x 2 + y 2 作为适应度函数来评估个体 的优劣，这是显而易见的，因为求的是f ( x ，y ) 的最大值，使f ( x ，y ) 值大的点( x ，y ) 当然属于优良个体，具有较高的适应度。 d 选择操作 选择或复制操作的目的是为了从当前群体中选出优良的个体，使它们有机会作为 父代为下一代繁殖子孙。判断个体优良与否的标准就是各自的适应度函数。显然这一 操作借用了达尔文适者生存的进化原则，即个体适应度越高，其被选择的机会就越多。 最常用的选择方法是比例选择法，即个体被选择的概率与其适应度值成比例。具体的 说，就是先计算群体中所有个体适应度的总和，再计算每个个体的适应度所占的比例， 并以此作为被选择的概率。 e 交叉操作 交叉操作模拟生物进化中的遗传基因重组，它将两个父代个体基因的部分结构加 以替换重组以生成新的个体。简单的交叉( 即一点交叉) 可分两步进行：首先对配对 库中的个体进行随机配对；其次，再配对个体中随机设定交叉处，配对个体彼此交换 部分信息。 华中科技大学硕士学位论文 表2 1 交叉操作示意表 父代个体 = 2 ，y = 5 )0 = 1 5 ，y = 2 0 ) 染色体0 0 0 1 1 0 一0 0 1 1 0 10 1 1 1 1 l 1 0 1 1 0 0 交叉后的染色体 0 0 0 1 1 一0 0 1 0 00 1 1 1 0 1 们0 1 生成的子代个体o = 3 ，y = 4 )“= 1 4 ，y = 2 1 ) 由表21 可见，配对库中的个体2 和个体l 配对，交叉处为3 ，通过交叉得到了两个 新的个体。 通过将配对库中的个体进行如上的交叉得到的新个体形成了新的群体，即新一 代。需要指出的是，交叉操作是遗传算法中最主要的遗传操作。由于交叉操作我们得 到了新一代个体。一般来说，通过交叉操作会产生兼具不同父代优良基因的的新个体， 也就是新个体具有不同父代的优势特性。 变异操作 变异操作是按位( b i t ) 进行的，即把某一位的内容进行变异。对于二进制编码的 个体来说，若某位为0 ，则通过变异操作就变成了1 ，反之亦然。变异操作同样是随 机进行的。一般而言，变异概率p 。通常都取得很小。如果染色体的长度是2 0 位，变 异概率p m = 0 0 1 ，那么群体中共有2 0 x o 0 1 = 0 2 位可以变异，这意味着群体中没有一 位可以变异。变异操作是十分微妙的操作，它需要和交叉操作妥善配合使用，目的是 挖掘群体中个体的多样性，克服有可能陷于局部解的弊病。 2 3 基于遗传算法的全局运动估计 使用遗传算法计算全局运动的仿射变换参数就是在参数空间搜索最优化的个体 使得其个体的适应度最高。流程图如下： 1 6 华中科技大学硕士学位论文 搜索空间 空间均匀分布的 初始群体的生成 遗传代数 已到? 赢面翮苎 商斯分布的初始 群体的生成 遗传代数 已到? 变异 否 变异 否 交叉l _ 一选择 群体的适应度计算 低分辨率图象 交义l _ j 选择 群体的适应度计算 是工继续传给f 一级 i 高分辨率图象 图2 2 基于遗传算法的全局运动估计流程 2 3 1 适应厦函数的确定 我们前面已经讨论过，目标函数表征了两帧连续图象在仿射变换下的相似性，不 过，我们使用的是l s e 准则，也就是要计算的是目标函数的最小值，因此不能直接将 目标函数作为个体的适应度函数，而需要作一个变换。显然，适应度最高的个体应该 是使得目标函数取最小值的参数，简单的我们可以用目标函数的倒数作为适应度函 数，不过这时目标函数与适应度函数之间就不存在线性关系，这会影响到个体的选择 操作。我们希望目标函数和适应度函数之间存在线性关系，下面我们定义适应度函数 如下： f l t n e s s ( p ) = m 一日( p )( 2 - - 1 2 ) 其中m 是一个常数，并且大于o ( p ) 的最大值。 2 3 2 初始群体的产生 前面我们说过，遗传算法中初始群体的产生都是通过随机的方法，对于在参数空 间求解最优值的问题，一般要求参数能够分布的尽可能广泛，这样可以大概率获得具 有最多群体多样性的个体，避免陷入局部最优值中。当然，通过扩大群体的规模也可 1 7 华中科技大学硕士学位论文 以达到这个效果，不过这样就使计算量有所上升。基于这个要求，在最低分辨率级时 我们采用了在参数空间的均匀分布来获得初始群体，形象的说就是在参数空间内均匀 地撒种，将这些种子作为第一代群体。在高分辨率级时我们采用均值为低分辨率级粗 略估计值的高斯分布来产生初始群体，并且此时的搜索空间可以取得小一些。 2 3 3 交叉概率和变异概率的选择 交叉算子和突变算子的性质体现了遗传算法的搜索原理和搜索策略。交叉算子的 机理相当于生物学意义上的基因遗传，其特点是产生出具有与父代相似基因组合的个 体，在数学上表现为收敛操作。根据文献 2 - - 2 】，在没有变异操作的条件下，初始种群 经过n 次交叉遗传操作，n 充分大时，种群最终会收敛到局部最优。这里所谓的局部最 优，是由于交叉算子的收敛特性，概率意义上不能产生与父代基因差异很大的个