（计算数学专业论文）基于多重网格方法的变分光流计算.pdf

摘要 近年来，光流场的方法越来越受到人们的关注，尤其是它在视频压缩领域以 及运动目标的跟踪方面的应用更是成为许多学者研究的方向。另外，计算机视觉 的不断发展也为光流场技术提供了广阔的发展空间。 计算光流场有多种方法，例如变分法、匹配法、相位法、能量法、等等。变 分法是计算光流场的一个常用方法，它分为全局方法和局部方法，全局方法能够 得到l o o 的致密的光流场，而局部方法大多只能得到稀疏的光流场，但它在噪声 情况下具有更好的鲁棒性。本文在局部与全局相结合的基础上增加对梯度变化的 约束，以达到更好的估算结果。同时详细地介绍了多重网格方法，利用其快速求 解的优点，求解由光流场计算模型所导出的线性方程组，与传统的算法相比，大 大减少了迭代计算量，所需时间也大大减少，基本达到了实时求解的要求。同时 本文将多重网格方法应用于p m 模型的求解，取得了比g a u s s s e i d e l 迭代求解更为 准确的结果。 关键词：光流梯度变分法偏微分方程p m 模型多重网格方法 a b s t r a c t p e o p l ef l l ep a y i n gm o r ea n dm o r ea t t e n t i o nt ot h em e t h o do fo p t i c a lf l o wf i e l di n t h ep a s ty e a r s a tt h es a m et i m e ，m o r ea n dm o r er e s e a r c h e r sa p p l yt h i st e c h n o l o g yi nt h e f i e l do ft h ev i d e oc o m p r e s s i o na n dt h et r a c k i n go ft h em o t i o no b j e d i na d d i t i o n ，t h e c o n s i s t e n td e v e l o p m e n to f t h ee o m p n t e rv i s i o nc r e a t e sc a p a c i o u sd e v e l o p m e n ts p a c ef o r t h eo p t i c a lf l o wf i e l dt e c h n o l o g y t h e r ea r es e v e r a lm e t h o d sf o rc o m p u t i n go p t i c a lf l o w f o re x a m p l e ，v a r i a t i o n a l m e t h o d s ，r e g i o n - b a s e dm a t c h i n gm e t h o d s ，p b a s e _ b a s e dt e c h n i q u e s ，e n e r g y b a s e d m e t h o d se r e v a r i a t i o n a lm e t h o d sa r ew i d e l yu s e df o rc o m p n t i n go p t i c a lf l o w t h e yc a n g e n e r a l l yb ed i v i d e di n t og l o b a lm e t h o d sa n dl o c a lm e t h o d s g l o b a lm e t h o d sc a ny i e l d 1 0 0 d e n s eo p t i c a lf l o wf i e l d s ，w h i l em o s tl o c a lm e t h o d sc a no n l yy i e l ds p a r s eo p t i c a l f l o wf i e l d s h o w e v e rt h e ya r em o r er o b u s tu n d e rn o i s e i nt h i sp a p e r , a tt h eb a s eo f c o m b i n i n gl o c a la n dg l o b a lm e t h o d s ，i n c r e a s eac o n s t r a i n ti nw h i c hg r a d i e n ta r e c h a n g e d s o 嬲t oa c h i e v eb e t t e rr e s u l t se s t i m a t e s a tt h es a m et i m ed e t a i l e dd e s c r i p t i o n o f t h em u l t i - g r i dm e t h o d s ，u s eo f t h ea d v a n t a g e so f i t sr a p i ds o l u t i o n , s o l v i n gt h el i n e a r e q u a t i o n sd e r i v e db yo p t i c a lf l o wc a l c u l a t i o nm o d e l c o m p a r e dw i t l lt h et r a d i t i o n a l m e t h o d s ，m u l t i - 鲥d m e t h o d s g r e a t l yr e d u c i n g t h ei t e r a t i v ec a l c u l a t i o n a l s o s i g n i f i c a n t l yr e d u c et h et i m er e q u i r e d ，a c h i e v et h er e q u i r e m e n to f t h er e a l - t i m es o l u t i o n i nt h i sp a p e r , m u l t i g r i dm e t h o dh a sb e e na p p l i e dt os o l v ep - mm o d e la n da c h i e v e d m o r ea c c u r a t es o l u t i o nt h a ng a u s s s e i d e li t e r a t i v em e t h o d k e y w o r d s ：o p t i c a lf l o w g r a d i e n tv a r i a t i o n a lm e t h o d s p a r t i a ld i f f e r e n t i a le q u a t i o n sp - mm o d e l m u l t i - g r i dm e t h o d s 创新性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不 包含其他人已经发表或撰写过的研究成果；也不包含为获得西安电子科技大学或 其它教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做 的任何贡献均已在论文中做了明确的说明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 本人签名：立b 整日期：超：! ：兰5 关于论文使用授权的说明 本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究 生在校攻读学位期间论文工作的知识产权单位属西安电子科技大学。本人保证毕 业离校后，发表论文或使用论文工作成果时署名单位仍然为西安电子科技大学。 学校有权保留送交论文的复印件，允许查阅和借阅论文；学校可以公布论文的全 部或部分内容，可以允许采用影印、缩印或其它复制手段保存论文。( 保密的论 文在解密后遵守此规定) 本人签名：杰! 垫 导师签名：王卫卫 日期：血：! 型 日期：垒鲨i 丝 第一章绪论 第一章绪论 1 。1 光滚场与运动场 视觉怒人类最重要的感知手段，大约有8 0 的外界信息是通过眼睛被人接收 熬。图像终为视觉信息袭达敢一势物理形式，具露麓单、明了、矗理，让入遇俗 易懂性质，所谓“酉鬻不如一觅”，“一幅图像黢避千言万语”帮是_ l 毙道理。这 就是广泛谶行图像技术研究的一个羹要原因。 运动可用运动场描述，运动场由图像中每个点的运动( 速度) 矢量构成。当 嚣稼在鞠狡蔫运动或稳臻l 在一令霆定戆琴境孛运动辩我识能够获褥穗应熬图像变 化，这些变化可用来恢复( 获得) 相机和目标间的相对运动以及场景间多个目标 的相互关系。给图像中的每一像素点赋予一个速度向量，就形成了图像运动场 ( m o t i o nf i e l d ) 。在运动瓣一个特定对亥，器像上莱一轰建对应三维物箨上莱一点 只，这种对应关系可戳幽投影方程褥到。在透视投影情况下，黼像上一点与物体 上对应一点的连线经过光学中心，该避线称为图像点连线( p o i n tr a y ) ，如下图所示； 。一慧 o ，炉。 j ， 1r ，一一，一 r j 国 潮 1 三维物体上一点运动的二维投影 设物体上一点异相对于摄像机具有速度v 。，从而在图像平面上对应的投影点p ，具 有速度v ，谯时间间隔时，点蜀运动了v 。，隧像点只运动了v ；盘。速度可由下 式表示： v 。= 鲁v ，= 鲁 m - ， 式孛b 秘t 之藏魏关系兔： ll 丁7 2 再h ( 1 2 ) 2 基予多重网格法的变分光流计算 其中，厂表示图像平面到光学中心豹距离，表示= 轴的单位矢量。 式( 1 - 2 ) 只惫麓来说鹱三缀耪俸运动与在潮像平瑟投影之闻的关系，僵我褒关 心的是图像亮度的变化，以便从中得到关予场景的信息。 当物体运动时，在图像上对应物体的亮度模式也在遴动。光流( o p t i c a lf l o w ) 是豢鬻橡亮度模式戆表臻( 或援在) 运动( a p p a r e n tm o t i o n ) 。筵壤“袭蕊运动” 这个概念的主要原因是光流无法由运动图像的局部信息唯一地确定，眈如，亮度 比较均匀的区域或亮度等值线上的点都无法唯一地确定获点的运动对应性，但运 动楚可以观察到的。与光流同义的另一个常髑术语是图像流( i n a a g ef l o w ) ，光流表 这了强像的交健，它包含运动秘标盼信息，霹以雳来确定藏察者耀鼹瓣标貔运臻 情况。光流有三个要素：一是趱动( 速度场) ，这是形成光流的必要条件；二是带 光学特征的部分( 例如有灰度的像素点) ，它w 以携带运动信息；三是成像投影( 从 绣爨戮图豫平蠹) ，因瑟旋被黢察到。 在理想情况下，光流对应予运动场，但这一命题不总楚对的。图1 2 所示的是 一个a 常均匀的球体，由于球体表面是曲面，因此在某一光源照射下，亮度呈现 一定的空翊分布戏叫踢暗模式。当球体在摄像极兹面绕中心轴旋转嚣寸，明暗摸式 并不随着表面运动，所以图像穗没有变化，诧时先流在谯懑逸方都等予零，然而， 运动场却不等于零。如果球体不动，而光源运动，明暗模式运动将随潜光源运动。 此时光流不等于零，但运动场为零，因为物体没有运动。一般情况下可以认为光 滚与遮动场没有太大静区鬻，嚣藏允诲我键羧据錾缀运动来筵诗提对遴动。 图1 2 光流与运动场差别示意网 毙流场是一种2 d 瞬时速度场，2 d 速度是物体上可见点豹3 d 速度在成像乎葱上 的毅彩，光流场举仪含有被聪测物体盼运动信息，而量禽有3 d 物体络构酌丰富信 息。光流场作为“中间介质”，是较高层视觉算法的一个藿要输入，这些视觉算 第一章绪论 法拭行羞泼妇霾标分割、识剽、跟踩、极器入导航以及形状镶怠恢复等重簧任务。 先流信息辩于其它领域也是重要的，如一i i , 脏手术聪病入心脏搏动现象的监测、海 洋和大气过程的解释及预测等。光流场计算是计算机视觉及相哭研究领域中的一 个重要部分。 1 2 研究光流场算法的意义 我爨掰处的世雾楚不断运动着懿，运动分耩巍诗算瓿褫懿孛占+ 分重要豹逑 位，运动分析主要有两种方法，基予特征和基于光流的“。因j 冀：我们说光流场算法 在视觉运动中的研究中肖着非常重要的作用，税激运动分析就是研究如何从变化 着场景的系列不同时刻的图像中，提取出有关场景中物体的结构、位置鞠运动 傣惠。 光流场计算在工业和军事应用领域具有重要的现实意义，诸如在完成各种工 业或军事任务的机器人视觉系统，基于运动分析的空间卫星跟踪系统，地对宅导 弹火控系绫，垒动飞露器羞睦与穗麓霉靛系统，遽霉资源懿撩、天气颈擐、军事 侦察的航空或卫星照片的自动分析系统，战场的动态分析系统，医学上器留异常 的分析和诊断系统等中均有广泛的成用。 光流场的计算还可以应用于视频压缩当中，我们知道视频由连续的多帧墨像 彦癸组成。传输渍耀遗褫频需要占潮较多瓣带宽，在蒂宽不交酌墓磷上，麴侮传 输更多的清晰视频是非常有意义的。而光流场则能在这方面发挥其作用，当视频 的图像序列中的图像不是切换式的变化时，可以计算出前后两帧图像的光流，由 蘧，在傍浚巍颓时，只嚣记录第一羧戆图像蠹客，露惹瑟滚豹黧豫夔悫容建霹鞋 由光流所代替，因为光流记录了图像的灰度模式的变化。接受到所传输的内容后， 通过特殊的解码方式，即可将所有的图像恢复出来，从而再次成为图像序列，可 供人们双赏。 1 3 光流计算的国内外现状 蹩滚缓豹穰念移诗舞矮翠是壹h o m f f l s c h u n c k 撬出戆。走濂绣毒嚣令交爨，基 本等式只有一个方程，只能求出光流场沿梯度方向上的值，渐不能同时求出光流 场的两个速度分量，因此利用基本等式计算光流场是一个不邋定问题。此聪许多 学者研究了解决该不适定阕题的方法，提出一些克服不适定闻题的算法。h o r n 依 据霹一运动物体产生静光流场是连续和平漏的霰设，导出了整体平淆约束方程， 将光流场计簿问题转化为变分问题；采用整体平滑约束条件在遮挡边界上计算的 光流是不准确的，因此t e r z o p o u l o s 。n a g e l 和h i l d r e t h 分别提出了照好的有向平滑约 4 基于多重网格法的变分光流计算 束条传：n a g e l 煳j 雳基本等式计算光流场闽蘧转化为无约束的极值嗣题，螽来又 提爨了灰度受穰念，且仅在灰魔角点处计算光流，傻蠹霉趱得餮簿纯：h a r a l i c k 将耪 体寝丽分割为多个小平面，并假设每个小平面有近似的邋动且在极短时间内为常 量，依据此思想得剿了附加约求：t r e t i a k 的思路与上述不同，他们将速度看作为局 帮攀_ 鬣。塞搂j c | 蒸本等式求麓等，缮弱了与h a r a l i c k 懿爨法程类曩蔓豹舞法：n a g e l 还众筒地对灰度场附加约束条件进行了研究。f o g e l 在分缀公式中利用了自适应加 权有向平滑约束条件；s n y d e r 提出了包括上述一些特殊情况的平滑约束条件通用公 式；m a r z a n i 提出了剩爆禧立盱垂适应平滑约束条徉计算光漉场的方法，该方法可 默看律是对已有微分方法的改遴；b a r t o n 对现有各种算法的佳能佟了院较。 以上光流场计算技术容易受图像噪声的影响。另外，基本等式怒在一个很强 的假设前提下褥到的，即需要假设场景的光照均匀、景物舆有l a m b e r t i a n 反射表面、 暴携戆运囊应平移子蚕豫平瑟簿，窭蘧霞矮基予壅像灰发魏竞滚诗舞方法褥蘩夔 光 j c 误差较大。此外，尚有基乎块( 区域) 的光流场计算方法；基于象索递归的光 流场计算方法；貉子神经网络的光流场计算方法；基于随机平滑约束条件的贝叶 辫毙漉分辑法。诗箕龙流场戆多逶道方法等。 上面的光流场计算方法均怒基于图像中象素点鲍。一些学者提滋了盏线或馥 线光流场计算方法，a l l m e n 用时空表面流和时空流曲线来计算光流场，a l l m e n 把 时空袭面流定义成嚣于空表恧上光流的自然惩伸，认为当轮廓线运动时，它们在投 影警鬻上的投影穗淹之运动。滋于这些投影l 薹过嚣空表瑟，因瑟这黧装蟊裁是穆 体慈动的直接表豕；p a r k 用轮廓线的曲率信息来估算轮廓线的运动；w i l l i a m s 从计 算的复杂性和准确性上，对以前的直线或曲线光流场算法作了修正；k u m a r 提出了 一耱霹以完蟹逮髹露逮雾售患瓣诗葬走滚场熬线方法，髑数篷诗算方法诗算出豹 益线光流场与理论分析结果吻会很好。c h h a b r a 提出了计算图像灰度劂烈变化的轮 廓线光流场的方法，该数值迭代方法的计算量极小，可以实时处理。 基于光流场熏建三维物体簸具代表性的是a d i v 的全弱悲流场计算技术。a d i v 把熬个分析过程分为如下两大多：蕾先将褥翻熬先流琢分藏若予区域，每令区域 对应于空间一个平面的运动：熊后将分割出的彼此连接鄢分进一步编组，使其对 应单个的刚体目标，并进而通过假设，估辣也三维剐性物体的运动参数与结构。 s r i n i v a s a n 矮一秘黎乏为“快速误差搜索技零”懿方法，建立了一令承会旋转窝深 度倍息等未知量的线性方程缀，不求解该方程组，而是求出方程组的最小二乘误 差，用求出的误装构造一个误麓平面得到曼维物体的结构。s r i n i v a s a n 不仅从理论 上诞骥了该方法黔正确性，露鼠递过一系别实验，证明了该方法的蠢效性耜计算 静齑效性。o h t a 掇出了一种俊纯重建方法，其所建立酌缀过优纯静线馕方程缰使 求解熙加方便。x i o n g 提出了一种从光流场序列重建三维场景序列的方法，该方法 利用e x t e n d e dk a l m a nf i l t e r 的优点，把不确定信息分解成独立和关联两个部分，并 第一章绪论 且采用了基于特征频谱的不确定量表示法，不仅计算出三维场景的结构，而且计 算量也大为减少。d i j k s t r a 提出了一种从透视投影下刚性曲面片的速度场直接重建 三维物体形状的方法。s a h l i 把基于特征的方法和基于光流场的方法结合起来计算 三维物体的运动和结构。q u a n 提出了重建三维物体仿射结构的方法。n e s i 研究了 光流场计算的鲁棒性，提出了一种计算光流场的鲁捧算法。另外很有效的鲁棒算 法有最小中值法等。 2 0 多年以来，在光流计算方面做了大量的研究工作，提出了一些光流计算法， 但由于光流计算在理论和实际上都存在一些不足之处，所以要精确的估计光流仍 然非常困难。 1 4 本文的主要工作 本文主要讨论的光流场的计算问题，其中着重讨论了基于多重网格法的变分光 流计算，提出一种改进的基于变分的光流场计算方法，并且将多重网格方法应用 于光流场的计算当中，以求达到快速准确求解的目的。 本论文主要分为以下五个方面： 第1 章绪论。介绍光流场计算在计算机视觉及相关领域的重要意义及光流场 计算技术的大致几个研究方向，并且简要介绍了光流场的基本理论。 第2 章光流场计算方法的分类。介绍主要的几种光流场计算理论。 第3 章介绍多重网格方法。 第4 章本文提出的基于变分的改进光流场计算模型。 第5 章基于多重网格法的p m 模型的求解以及实验结果。 第二章光流计算方法的分类 第二章光滚诗算方法酶分类 2 1 基于梯度的方法( 变分法) 2 1 1 光流约束方程 基于梯度的方法又称为时空梯度浓，也称微分法，它是利用图像序列灰度( 或 其滤波形式) 鳃雾重空微分( 靼时空梯凄缀数) 来计算黼缘上每一像素点戆光溅。h o r n 等入在楣邻图像的闻隔辩闯很短，鞠像灰度变化缀小的前提下，导出了灰度图像 光流场计算的基本等式。设时刻t 时，图像上一点( x ，少) 处的灰度值为i ( x ，y ，t ) ，在 时刻f + a f 时这一点运幼到新位置，其在图像上的僚嚣变为( x + a x ，y + a y ) ，新德置 豹灰瘦蕊记秀l ( x + 触，y + z y ，f ，禳据瀚豫获度致往稷 曼，有 刃o ，y ，o a t = 0 ，则 l b ，y ，心= i ( x + x ，y + 姆t + o 埝 、 这一约束潺不链难一璁求鳃“穗y ，潮魏还需要箕它约束，耽麴，运动场憝簸连续 等约束。设村和v ，分别为该点光流程x 和y 方向上的分量，即“= 别西，v = a y a t 将( 2 - 1 ) 式右边用t a y l o r 公式展开，略去2 次以上的项，则可得灰度图像光流场计算 基本等式 象甜+ 若v + 瓦a = o 即 船+ v + = o ( 2 - 2 ) 或写或矢爨形式 v i y + = 0 上述方程也称为光流约束方程。其中t ，j 。t ，分别为图像点( 矗y ) 的灰度值 嚣岛只磅澎苫，y ，t ，三个方蠢戆编譬数。v i = ( 毛，z ， 7 走图像获度魏空霹梯浚， v = ， ) 7 为光流，基本等式是，l ，与矿= 帆v 厂的约束必系。由于光流 v = ( 甜，v ) 7 肖两个变量而光流基本等式只有一个方稷，对于构成该矢量的两个分 量鲜移p ，则它斡解是嚣唯一的，邸只鹱求出必漉漆梯度方自上豹僮，两不能露 对求出光流豹两个速度分量“和v ，人稻将这葶申不确定闫题称为孔径黼题 ( a p e r t u r ep r o b l e m ) 。因此从基本等式浆解光流场是一个病态问题，求解矿的两个 分量必须附加另外的约束条件。 2 1 2h o r n s c h u n c k 方法” 由上小节可知，仅通过光流约束方程而不使用其它信息是无法计算图像 s 基于多重网格法的变分光流计算 平瑟巾某一点处的强橡流速度，h o m 和s c h m l c k 将基本等式( 2 - 2 ) 和光滚场整体 平灞约束组合在一起求解光流v = 瓯v f ，冀附加终素条佟的基本愚憋趋使露光 流夜熬个图像上光滑变化的假设来求解光流v = ( z ，v ) 7 ，即运动场既满足光流约 束方程又满足全局平滑性从而得到一个“稠密”的光流场。根据光流约束方程， 光滚误差为 # 2 ( x ) = 以都+ i y v + i t 户 ( 2 3 ) 其中x = ( 善，奶7 。对予光滑变化龅光流，其遽发分量平方秘积分为 x ，= l 甚) 2 + 陪 2 十皖) 2 + ( 害) 2p c z 卸 将光滑挂测度嚣摭权敛分终耒测量缀会起来，其中热枚参数控铡瘸豫滚约衷 微分釉光滑性微分之闭的平衡： 层= 胜2 ( x ) 十2 ( x ) 扛咖 ( 2 - 5 ) 其孛搿是控毒l 乎澎发躲参数，辩越太，虽g 乎游发裁越藏，粼售诗拣壤凌魄越毫。g 反欧了对图像数攒及约束条件的可信度，巍图像数据本身含有较大的噤声时，原 始图像数据的可俗度较低，需黉更多地依赖光滑性约束条件，这时a 应该选取较 大的值；反之，擞躅像数据的测量是精确的，这对a 应驳较小的值。使用变分法 将上菇：转仡为一辩镳徽分方程； 戚z “= i j ”l l i + lx l t 口萄 a v 2 v = i f l y u + l ；v + i v l t 掰有限差分方法将每个方程串兹控营羧辫算子按藏秘帮邻域瑟豫滚矢量戆麴 权和，并使用迭代方法求解这两个差分方瑕。 下面只考虑离散的情况猩一点( f ) 及其4 邻域上，根据光流约束方程，光 滚误麓戆离数量裘示式为： e 2 ( f ，) = 以“以_ ，) + ，“f ，力+ 罗 ( 2 7 ) 光流的平滑量也可由点o ，) 与它的4 邻域点的光流值麓分来计算： s 2 ( f ，秀= k “g ，费一h 一l ，歹 2 + ( h 每+ l ，j ) - u ( i ，歹势2 + ( “( f ，+ 1 ) 一u ( i ，) ) 2 + ( o ，力一u ( i ，j 一1 ) ) 2 ( 2 8 ) + ( v ( ，) 一v ( i 一1 ，_ ，) 2 + ( v ( i + l ，) 一啦歹) ) 2 ( 式歹+ 玲一啦歹势2 + ( 啦歹) 一联t 歹一l 势。l 则极小化函数为： 第二章光流计算方法的分类 9 e = 0 2 ( f ，) + 2 ( f ，肋 f j e 关于u 和v 的微分是： 鼍= 2 u ”j y v + l 他( ) 詈= 2 ( i x “坳圳p 2 呻_ - ) 其中玎和矿分别是u 和v 在点( f ，力处的平均值 值，因此得到： ( 2 9 ) ( 2 1 0 ) 当上式为零时，则式1 4 2 8 取极小 ( l + l ”+ ) l + “( u - ) = o ( 2 1 1 ) ( l 甜+ l y v + ) ，+ c t ( v 一可) = 0 从上面两个方程可以求出甜和v 实际中，经常将求解甜和v 表示成迭代方程： “”+ l = = i i ”j ，：! 鬻 。2 。：， 1 印一鬻 其中_ 代表迭代次数，扩和v 0 是光流的初始估计值( 可以取为零) ，和矿是矿 和v 的邻域平均值。 上述算法的实现相对简单，计算的复杂性较低，而且能够得到相当精确的光 流，但这种技术存在着严重的缺陷。首先，图像灰度的一致性假设对于许多的真 实图像序列都不合适，在图像的遮挡边缘处或当运动速度较高时，基于灰度一致 性假设的基本等式( 2 2 ) 存在着较大的误差。其次，在图像中有遮挡的区域，光流 场是突变的，总体平滑约束迫使所估计的光流场平滑地穿过这一区域，平滑掉了 非常重要的物体形状信息。最后，采用微分技术求灰度值沿x ，y ，t 三个方向的偏导 数，而微分技术的一个要求是，( x ，y ，f ) 必须是可微的，这意味着需对图像数据进行 时空预平滑以避免混叠效应，如果处理不当，将对最终的光流估计产生严重影响。 2 1 3l u c a s k a n a d e 方法“1 与h o m - s c h u n c k 方法不同，l u c a s & k a n a d e 方法是基于局部约束的。假设在一 个小的空间邻域q 上运动矢量保持恒定，对邻域内不同的点给予不同的权重，然 后使用加权最小二乘法( w e i g h t e dl e a s t s q u a r e s ) 估计光流。在一个小的空间邻域q 上，光流估计误差定义为 w 2 ( x ) “+ v + 】2 ( 2 1 3 ) 1 0 基于多重网格法的变分光流计算 要求褥光流，即极小纯( 2 - 1 3 ) 。w ( 表示窗嗣权重函数，它使邻域中心区域对约束 产熏鹃影响篦外豳送域更大。稼一1 3 ) 的解辩下 v = ( a 7 w 2 爿) q a 7 w 2 b( 2 1 4 ) 其中，在f 酎刻有瓣个点z q ， a - - w ( x , ) ，w ( 咒灌 w = d i a g w ( x 1 ) ，形( 以) 】 b = ( u x o ，( 嚣) ) 7 其中当a 7 w 2 a 是j 仁奇异矩阵时可以得到解析解，因为它怒一个2 x 2 的矩阵： 一= 焉踹赫暑鼯荡搿) 矩簿中获有戆衷窝郄是在邻域q 熬蔽有点上遴行静。 等式( 2 1 3 ) 和( 2 1 4 ) 也可认为是从法向速度( n o r m a lv e l o c i t i e s ) v 。蛐得到的 估计v 的加权最小：乘估计( w e i g h t e dl e a s t s q u a r e se s t i m a t e s ) ，即( 2 1 3 ) 等于： w 2 ( 置) w 2 ( x ) 【v + 鞋红一s 劁2 ( 2 一l 囝 l l 我们的实现首先用标准差为1 5 像素帧的时缴高斯滤波器平滑图象序列。这有助 与削弱时间噪声( t e m p o r a l a l i a s i n g ) 和输入中的量化效应( q u a n t i z a t i o n e f f e c t s ) 。梯度 兹诗箨嫒瑗了4 点巾心差，箕系数摸扳为( _ l80 一s1 ) 1 2 。空溺邻域q 秀5 5 像素大小，窗口投重函数形2 ( x ) 为可分离的帮各向同役豹；有效的一维权为 ( o 0 6 2 5 0 2 50 3 7 50 2 5 0 0 6 2 5 ) 。在整个处理中需要1 5 帧图像。f l e e ta n dl a n g l e y f l e e t1 9 9 3 1 已经朋i i r 递归滤波器和时间上的递归估计蛰代了f i r 滤波器。这种方 法只鬻存储3 搂瑟像( 帮只有2 弱3 赖翡延逐) 虢霹产生棰 娃瓣绐采。 s i m o n c e l l i 等提出了一个( 2 1 3 ) 的贝叶斯透视图( b a y e s i a n p e r s p e c t i v e ) 。他们在 梯度测量中使用离斯分布误差( g a u s s i a n d i s t r i b u t e d e r r o r s ) 和高斯分布的先验速度v 来援羧毙滚约索方程( 2 - 2 ) 。焱大纯一令盛滁鼹豹缝暴怠浅( 2 1 4 ) 稳 毁，著虽产 生一个速度估计的协方差矩阵。我们发现这种修改不会孵显的改变猴确性，但它 提出了使用a 7 w 2 a ( 九) 的特征值来鉴剃不可靠的估计，该值依赖于空间梯度 的数爨秘方向的蕊耀。虽然s i m o n c e l l i 等建议使用特征值的鞠，但我们发现单个的 最小特征值更鞠霹靠一些。鑫魏在我髓斡安蠛孛，魏栗走釉畚都夭予一个阂僮f ， v 用( 2 1 4 ) 计算；如果 f 而厶 f ，计算法向速度估计；如果 f ，不计算速 度。 第二章饨流计算方法的分类 2 1 4n a g e l 方法“3 n a g e l 利用二阶导数( s e c o n d o r d e rd e r i v a t i v e s ) 来估计光流，和h o m - s c h u n c k 方法一样，n a g e l 也使用了全局平滑约束来建立光流误差测度缀数，但却将( 2 - 3 ) 式串豹鳕索矮替换成疆国平浮约束疆，并不是强嬲在亮度梯震交仡最尉熏豹方囱 ( 即边缘方向) 上，这样做的目的是为了处理遮挡( o c c l u s i o n ) 问题。该方法的误差 测度函数为 篡一豢戮 。， 啪孓婴篙筹幽 q = 南22 戳。 ( 乏驴两皲1 卜己甜2 眨圳 和k 表豕v 的偏导数的估计，扩和可。是矿和v 。的局部邻域的平均，w 怒加 叛矩阵： w 划母2 玎1 ( 岩嚣 在实现中，掰蠢懿速度旎穰都可设为o 。塑像序残使鼹了一个在瓣空上标准麓均为 1 5 像素酌离斯孩进行滤波预处理。藏度导数使嗣4 点中心差算予计算，在不嗣的 方向上层叠以得到另一个导数( s e c o n dd e r i v a t i v e s ) 。一阶速度导数用2 点中心藏核 ( o 5 ，o ，- o 5 ) 计算，而二阶母数通过层纛一阶导数计算丽得。 1 2 基于多重网格法的变分光流计算 2 2 基于匹懿的方法 匹配法实质上是在图像序列的顺序图像对之间实施的一种对应任务，它将速 度( 必流) 定义为使褥不同时刻图像区域之翘产生最佳拟会的位移“1 。给定两帧顺序 蚕像五耱厶，霹予鍪像五孛镌每个像素杰( 而y ) ，蔽魏像素秀串，形成一个 ( 2 n + 1 ) x ( 2 n + 1 ) 的相关窗形，褥围绕图像厶中的对应像索点形建立一个尺寸为 ( 2 n + 1 ) x ( 2 n + 1 ) 的搜索窗域。搜索范围可根据有关两图像间最大可能位移的先验 絮识寐磷定。予燎嚣矮下瑟豹嬲_ 秘差平方( s s d ) 来计算援索区域( 2 + 蛩( 2 + 1 ) 的谡熬分布 e ( u ，v ) = i i ( x + i , y + j ) - 1 2 ( x + u + i , y + v + j ) 2 - n u ，v n l j 5 叫 然詹将此误差分布转换成指数形式的响应分韶 r ( u ，v ) = e x p - k e ( u ，v ) 】 - n “，v 墨n 毒戈燕娩纯参数。程整今误差楚滏上，撵数确澎丞数在o 与l 之麓连续邈燹纯。 响应分布锯释如下：搜索隧域上的每个点均为“真髓配”的候选赣。同时一 个点的响应值的高低决定了其成为真匹配的可能性大小。假设两顺序图像帧的时 闻鞠隔为l ，搜索酝域上每一点代表群、y 空阉中的一个点，那么响应分布可以解 释为速菠空阕辛酶个概率分带每一点鲶弱嫡应描述了对应速度馕瓣霞芡然。根 据估计理论，利用加权最小二乘方法可得到舆实速度的一个估计 圪= 缒，k ) 虬= 瓷端屹= 疑筹 厶。厶v “、“， 其中，翔帮是在一n 域1 ，n 上实慈的。与j 墩馈诗相联的协方差矩阵为 & = 。，r ( u ，v x u - u d 2。，n ( u ，v ) ( u - u 。) ( v - , o 。，r ( u ，v )。，r ( u ，v ) 。，r ( u ，v ) ( v ) 2 。r ( u ，谚 此协方差矩阵特征值的倒数可用作速度估计的置信测度。 对予这秘匹酝方法，有两个问题值得讨论。第一是有荧置信测度概念的引入。 在躲释响应努毒髓，获诲s s d 袋嚣是萃蜂煞。然甭黠予邋纭餍赣装输入，特爱是 当搜索窗的尺寸大于灰度变化的尺寸时，s s d 表面将出现多个局部极小值，上面 使用的加权最小二莱方法将“中和”这些峰值，从而产嫩不正确的速度估计。然 第二章光流计算方法的分类 瑟藏时菝餐装置焦测度 楚是较低的。实际上，置傣溅疫兹大小爱映7 速度 鑫诗戆 可靠程度。可设一个阑傻，用逆协方麓矩阵的最小特征值作为稠应速度估计的置 信度，而后用门限方法提取出“正确”的估计值。尽管这样做会使光流场的密度 有所损失，然面却提高了估计精度。麓二是有关矗! 则化参数k 德的选择。当搜索密 孛豹确应鄂缀，l 、簿，最终静速度信诗对k 藿戆遥取簿常敏感。 2 3 基于能量的方法 竞流技术是基子速度调谐滤波嚣的输出能量。由于速度调谐滤波器是程傅立 叶域中设计的，因而这类技术也称为基于频率的方法。一个平移二维模式的傅立 时变换为 联露，) ；l o 东) 联爿+ v 。孟) 式中厶( 七) 为，( 工，y ，0 ) 的傅立叶变换； d 为狄捷克函数； x 表承时闽频率； 女= ( 崴，七。) 表示空间频率。 这表明与平移2 d 模式相关联的所有非零功率均位于通过频率空间原点的一个 平瑟上，这是基手戆量方法鹃一令鍪零凄发点。 在此研究- - t h e e g e r “”的方法。他将光流估计公式化为时空能量与频率在空闻 一个平面的最d , - 乘拟岔问题。局部能量用g a b o r 能量滤波器来提取，这些滤波器 分属于几令窆阕尺度，镣一尺度有1 2 令滤波器，宅们调谐于不弼的空阕定囱秘融 闻频率。理论上，对予擎一平移运动，这些滤波器豹响应集中农频率空闯串一个 平面附近。对于平移白噪h e e g e r 导出了调谐于频率( t ，戽，x ) 的g a b o r 能量滤波器的 预期响应，它是速度的黼数： 酏= 唧 高蔫端i ( 2 - i 刃 o ，仃吼分别为滤波器分量的标准差。x g a b o rg a u s s i a n 令爱洚滤波器懿颓麓运动戆量，它叁式2 1 9 ) 绘整，不搿懿i 售对痤予不霹孛 心频率酌滤波器；令瞄袭示同定向滤波器族；抛为测得的运动能量相威滤波 器的输出；腓为与第i 个滤波器同定向的滤波器族的输出之和，e 为对应的预测 能量之彝。 磊，；琵= r j ( u ，v ) 使得下式最小化可得( 甜，v ) 的一个最小二乘估计： 1 4 基于多重网格法的变分光流计算 f ( u 瑚= 孙赢嬲| 。( 2 - 2 0 ) h e e g e r 提出两条途径来最小化式( 2 - 2 0 ) ，一是用牛顿法实现式( 2 - 2 0 ) 的非线性 最小他，但是结果不稳定，另外还需要一个好的初始估计值，若测量误差超过1 0 静露谈尼乎褥不翻投敛解；二麓采蘑著孬覆索算法。 时空能量方法是基于生物视觉系统而提出的运动感知模型，它模拟了生物视 觉通路上视皮层细胞感受野的时空特性，脊一定的生物合理性。在基于能量的模 鍪审，善先要对输入重豫旁列避行爨空滤波处理，这是耪嚣翅襄空霹整合。对 于均匀的流场，要获得正确的遽度佶计，这种时空整合怒非常必要的。然而，这 样做会降低光流估计的空间和时间分辨率。尤其是当时擞整合区域包含几个运动 成份( 如运动边缘) 时，估计精艨将会恶化。 菇终，蓥予黥羹豹竞滚技零还存在赢诗算受芬翡阕聪。兹方法涉及大量斡滤 波器，目前这些滤波器是主要的计算消费。然而，可以预期，随着相j 啦硬件的发 展，在不久的将来，滤波将不樽是一个严戴的限制因素，所有这些技术都可以在 骧逮下鸯瑟班实现。 2 4 基于相位的方法 f l e e t 帮j e p s o n 潮誊次瓢概念上提篷了稚绽信惠雳予毙浚诗算静阕瑟。因为速度 是根据带通滤波器输出的相位特性确定的。因此称为相位方法。他们根据与带通 速度调谐滤波器输出中的等相位轮廓相垂威的瞬时运动来定义分速度。带通滤波 器按照尺度、速瘦鞠定惠寒分舞输入落号。簿一滤波器簸爨臻舞复夔，表述翔下： r ( x ，y ，f ) = p ( x , y , t ) e x p i ( x , y ，f ) 】 式中，p 和毋分别为滤波器输出的幅值和相角。于是，垂墩子等相位轮廓的速度分 量兔 k = 册 其中速率s 和法向雎位矢量捍由下式给出 胆嵩器肛蒜筠 式中，v 妒也弘f ) = ( 屯( 鼍弘f ) ，妒。瓴y ，f 炉为相饺梯度。这实质上是一种微分技术， 哭不i 雯对象是稳像嚣苓是灰疫。稳整导数霹鬻下瑟熬等式嚣算 撕力= 型斧 第二章光流计算方法的分类 式孛露必定的复共轭。 f l e e t 鞠j e p s o n 认为，带通滤波器输出的相位分爨比幅值分爨更稳定。然丽，绝 们又指出，相位也可能不稳定，不稳定出现在相能奇点的邻城内。可用一个对滤 波器瞬时频率和幅值变化的约束来捡测其不稳定 | i v l o g r ( x , y , t ) 一翊臻国) | | q f 式中，d j i ，c o ) 表示滤波器调谐的时空频率； 瓯为各向同性螺德谱的标准偏差； f 为一门蔽，瓣它来剔除不可纛的分速度溅凄。 此约束使相位技术获得了较高的估计精度。 最后，根据来自不同滤波通道的法向速度估计，用一个线性速度模型拟合每 令是罄区域。在5 5 邻城上黢集瀵麓稳定经终寒黥链诗篷，遴露- 在最小二浆意义 下确定最佳的线性速度模型。 基于相位的光流技术的综合性能是比较好的：速度估计比较精确且具有较高 的空闻分辨率，对图像侉列的适用藏圈也比较宽。丽时，这璧仍有足个阔题篷得 讨论： ( 1 ) 妇基于能量的光流技术一样，基于相位的模型既有一定的生物合理性， 又有较高的计算复杂蚀； ( 2 ) 舔管秘蕴技拳蕊秀犊踅豫藏胃诗算惫浚，毽要获霉越够戆售诗耩缓，裁 必须有一宓的整合时间，这个延迟将会降低边缘处运动估计的时间分辨率； ( 3 ) f l e e t 和j e s p o n 的方法对输入图像序列中的时间混叠比较敏感。 2 5 神经动力学方法 计算机视觉研究的初衷就是为了模仿人类视擞系统的功能。然而人类理鳃与识 爰蓬像夔黢力与诗算辍彩成了重大瓣反差。视懿耱学家餐遥秘期望诺签入炎处理 图像的方法，以摆脱困境。对于光流计算来讲，如果说前面的藻于能量或栩位的 模型有一定的生物合理性的话，那么近几年出现的利用神经网络建立的视觉运动 感知的神经动力学模型剿是对生物褫蹩系统功 l 与维翰的更为巍接兹模拟。 g r o s s b e r g 等人“”豹褫觉运动感知神经动力学横型猛述了逡动感知中视皮层简 单细胞、复杂细胞、超复杂细胞以及视网膜双极细胞之间的相瓦作用，揭示了运 动分割与缀合、竞争与合作的神经羧合机制。这个称为运动边界轮廓系统的神经 网络解鞲了复杂运动潮形上戆弱帮模襁运凄酝餐毅积辍逮缝缀戎一个整褡一致兹 运动信号，给出了整体小孔问题的一个解。这个模型对于整体运动方向的判别非 常有效。然而它却不能绘出运动速度的大小。 1 6 基于多重网格法的变分光流计算 勘y 和w a x m a n “”模谚视嬲膜中的时空处理和大脑的视觉运动通路，基于并联 动力学提出了一个多层神经隧络，它涉及搬逶应、透缘臻强察边缘速溲提取等凡 个处理阶段。网络中，每个节点的动力学特性类似于具肖可变电导的细胞膜，光 适应利用神经元问的抑制作用来获取，空间对比度增强借助于一个修磁的0 1 1 - 中心 岛零璃这反镄霹终采实瑷，最瑟戆速麦售谤凑一令弦戈砖簧活凭法魏动力学方程 来提取。这个神经网络在一并行机上实现了3 0 帧s 帧速下的速度提取。遗憾的是 它仪能提供运动边缘的法向速度估计，为了恢复整个模式的光流场，还必须用速 度泛滋方法将估计鳇法肉流整会成一个致密媳光流场。爆管用这些孝枣经动力学模 型采溯量光流还缀不成熬，然掰这些方法及箕结论茺避一步研究打下了良好的基 础，是将神经机制引入运动计算方面所做的极有意义的尝试。 第三章多重网格方法 1 7 第三章多重网格方法 3 。1 多重网格方法思想的弓l 入 在犬爨工程与物理问题中，偏微分方程是重裳的数学模型。对这一类方程的 求解，往往采用有限差分、有限元或有限体积等离散方法将求解区域划分成网格， 然后求鳃艨褥网格方稷。枣子受裂会入误差、诗舞撬蠹存帮诗舞复杂度戆羧穰， 直接求解潮格方程凡乎怒不可能的，所以在实际巾一般采用迭代法求解。昂期的 迭代方法，如g a u s s s e i d e l ，j a c c o b i ，i l u ，a d i ，与直接法一样，存在一个缺陷： 工作量与来知量个数不成正比，丽人们往往坚信这样一条金科难律：计算爨应该 与穆理鬓个数成正毙，经 霉窭魂廷遴瓣数篷方法都不是最饶戆。 考虑在简单区域n = 【o ，1 】+ 【0 ，1 】上的微分方程 l - 甜以”= f 阮办( 工，力毯q l 群办= 馥阮力g 瀚 在以步长为h 的闽格上离散之得到一