（模式识别与智能系统专业论文）贝叶期信息传递在计算机视觉中的应用.pdf

摘要 摘要 贝叶斯信息传递( b a y e 8 i 射lb e l i e fp r o p a g a t i o n ) 是用来求解概率图模型概率 推断问题的重要算法。在无环的网络中，它是可以得到严格证明的。在有环的 网络中，很多实验表明信息传递算法也能得到非常好的结果。沦文介绍了信息 传递算法的相关理论，并研究了它在几个计算机视觉问题中的廊用。沦文的主 要工作有： 第一章的主要内容是信息传递算法相关的基本理论：图论、概率图模型、 马尔可夫网络中的信息传递算法。文章还概述了关于信息传递算法的一些 最新研究进展，阻及信息传递算法在计算机视觉中现有的麻用。 第二章研究了基于背景减除的运动检测问题。基于背景减除的运动检测的 难点不仅在于减除本身，更在于背景模型的维持。论文阿先综述并比较 了现有的背景模型，然后描述了一种新的背景模型。这一模型包括两个 模块：点过程模块和m a r k o vn e t w o r k ( m n ) 模块，这两个模块交替在象素 级和图象级处理输入的周象序列。点过程模块的输出作为观察输入m n 模 块f 背景减除) ，m n 模块的输出又作为输入来更新所有的点过程模型( 背 景维持) 。m n 的最大后验估计问题可以被信息传递算法很好的求解。沧 文还提出了一种新的象素过程模型：自适应的h m m 模型，j _ f 二讨沦了他的 学习算法。( 部分工作发表在i c v l 2 0 0 2 ) 第三章研究了动态场景的深度恢复问题，也就是说从动态场景的几个同步 图象序列中计算每一时刻的场景深度。为了同时利用图象序列空间和时间 上的相关性，论文提出了一个新的统计框架。在这个框架中，同时包括了 时间上和空间上的信息传递。最后深度恢复问题被描述为一个m n 的最大 后验估计问题。信息传递可以自然的解决这个问题。试骑中，真实图象的 计算结果证明了算法的有效性。最后，沦文介绍了一个我们实现的动态场 景的实时采集绘制系统。( 部分工作发表在i c i p 2 0 0 2 ) 第四章中，为了提高虹膜识别系统的识别效果，论文针对虹膜识别提出了 种新的基于学习的图像增强方法。该算法是改进了的t 作。该算法 通过大量的虹膜图像去学习虹膜特征图像各频带之间的先验依赖关系，这 种关系被一个马尔可夫网络所描述。然后信息传递算法被用来估计给定低 分辨率图像的最可能的高频细节。为了避免在学习过程中引八会严重破 坏识别算法的虚假高频信息，论文引入t g a b o r 滤波处理使得新算法只学 习对识别最重要的部分频段信息。在n l p r 虹膜图像数据库h 针对这种 新的算法，我们做了大量的实验，取得了非常好的结果。( 部分t 作投递 到b m v c 2 0 0 3 ) 关键词：信息传递，马尔可夫网络，贝叶斯推断，背景减除与维持，动态场 景，深度恢复，图象增强 第i 页 英文摘要 b a y e s i a nb e l i e fp r o p a g a t i o n ： a p p l i c a t i o n si nc o m p u t e rv i s i o n a u t h o r ：d o n g s h e n gw a n g s u p e r v i s o r ：s o n g d em a ，h e u n g - y e u n gs h u m a b s t r a c t b a y e s i a nb e l i e fp r o p a g a t i o n ，o rb e l i e fp r o p a g a t i o n ( b p ) ，p r o b a b i l i t yp r o p a g a t i o n 、i so n eo ft h ei m p o r t a n ta l g o r i t h m sf o rp r o b a b i l i s t i ci n f e r e n c eo fp r o b a - b i l i s t i cg r a p h i c a lm o d e l t h o u g hi tc a no n l yb ep r o v e di nu n l o o p yn e t w o r k ，s o m e e m p i r i c a lr e s u l t st e l lu si tc a ng e te x c e l l e n tr e s u l t si nl o o p yn e t w o r k t h i st h e s i s f i r s ti n t r o d u c e ss o m er e l a t e db a s i cc o n c e p t sa n dt h e o r i e s ，a n dt h e nd e s c r i b e ss o m e o fm yw o r ka b o u ti t sa p p l i c a t i o n si nc o m p u t e rv i s i o nc o n t e n t so ft h et h e s i sc a l f b es u m m a r i z e da sf o l l o w s ： c h a p t e r1f i r s ti n t r o d u c e sb a s i cc o n c e p t sa n dt h e o r i e sa b o u tg r a p h i c a lm o d e l a n db pa l g o r i t h m ，a n dt h e ns u m m a r i z e ss o n r er e c e n td e v e l o p l n e n t sa b o u t b pa l g o r i t h m a tl a s t ，i tg i v e sab r i e fr e v i e wo fr e c e n ta p p l i c a t i o n so fb p i nc o m p u t e rv i s i o n c h a p t e r2s t u d i e st h ep r o b l e m sa b o u t “b a c k g r o u n dm a i n t e n a n c ea n ds u b t r a c t i o n ” “b a c k g r o u n dm m n t e n a n c ea n ds u b t r a c t i o n ”i sa l li m p o r t a n t m o d u l a ri nm a n yc o m p u t e rv i s i o na p p l i c a t i o n s ，ef i r s tr e v i e wa u ( 1c o i n p a r ea i lt h ep r e v i o n sb a c k g r o u n dm o d e l s a n dt , h e nw e1 ) r o p o s ean o v e lo n e t h i sm o d e lh a st w oc o m p o n e n t s ：p i x e lp r o c e s sm o d u l a ra l l dm a r k o vn e t w o r k ( m n lm o d u l a r t h eb a c k g r o u n di n a i n t e n a n c ea n ds u b t r a c t i o ni sp e r f o r m e db yp r o c e s s i n gi n p u ti u l a g es e q u e n c ea l t e r n a t i v e l yu s i n gt h e s et w o m o d u l a r sa te a c hp i x e la n dw h o l ei m a g cr e s p e c t i v e l yt h eo u t p u to fp i x e l p r o e e s sm o d u l a ri si n p u to fm nm o d u l a ra so b s e r , _ ，；a t i o n f b a c l ( g r o u n ds u b t r a c t i o n la n dt h eo u t p u to fm ni sa l s ot h ei n p u to fp i x e ip r o c e s sl n o d n l a r ( b a c k g r o u n dm a i n t e n a n c e l t h em a pp r o b l e mo fm nl n o d u l a rc a nb e n a t u a l l ys o l v e db yb p f p u b l i s h e di ni c v l 2 0 0 2 1 c h a p t e r3i sm yw o r ka b o u td y n a m i cd e p t hr e c o v e r yu s i n gb p ，m e 、t ( 1r e c o v e r t h es h a p eo fd y n a m i cs c e n e sf r o l nm u l t i p l es y n c h r o n i z e di m a r es e q u e l k ：e s t oi n c o r p o r a t eb o t hs p a t i a la n dt e m p o r a li n f o r m a t i o nf o rd e p t hi e c o v c r y w e p r o p o s ean e ws t a t i s t i c a lf r a m e w o r kt h a tu s e sp i x e ip r o c e s sl n o d e it oe n e o ( t e t e m p o r a lc o h e r e n c e a i t dm nf o rs p a t i a lc o h e r e n c e i nt h i sf r a m e w o r k ，t h e d y n a m i cd e p t hr e c o v e r yp r o b l e mi sf i n a l l yf o r m u l a t e da sa l lm a pp r o b l e m o fm n a n di ss o l v e db yb e l i e fp r o p a g a t i o na l g o r i t h m e x p e r i n m n t a l l e s u l t s w i t ht h er e a ld a t ai l l u s t r a t eo u rm e t h o d sa b i l i t yo fr o b u s ts h a p er e c o v e r y ( p u b l i s h e di ni c i p 2 0 0 3 1 c h a p t e r4d e s c r i b e sal e a r n i n gb a s e di r i si m a g er e s o l u t i o ne l l l l & u c c l l t e l l tf o t r e c o g n i t i o n i ti sa ne x t e n s i o no fw o r k 卧i tf i r s tl e a in st i mp r i o ip r o b a , - b i l i s t i cr e l a t i o nb e t w e e nd i f f e r e n tf r e q u e n c yb a n di n f o r l n a t i o no li r i si n r a g e s ， 第i i i 页 英文摘要 w h i c hi sd e s c r i b e db vam n t h eb pa l g o r i t h mi su s e dt oe s t i m a t et h em o s t p r o b a b l e1 0 s th i g hf r e q u e n c yo ft h ei n p u tb l u r r e di r i si m a g e st oa v o i dt h e f a k eh 培hf r e q u e n c yi n f o r m a t i o nt h a tw i l ld a m a g et h ei r i sr e c o g n i t i o ng r e a t l y , w ei n c o r p o r a t eag a b o rp r o c e s s i n gp r o c e d u r e t h er e s u l ta l g o l i t h mo n l yt r y t or e c o v e r yt h ei n f o r m a t i o nu s e f u lt oi r i sr e c o g n i t i o n al a r g en m n b e ro fe x - p e r i m e n t sc a r r i e do u to no u ri r i sd a t a b a s ed e m o n s t r a t et h a tt h ep r o p o s e d a p p r o a c hw o r k sw e l l f s u b m i t t e dt ob m v c 2 0 0 3 ) k e yw o r d s ：b e l i e fp r o p a g a t i o n ，m a r k o vn e t w o r k ，b a y e s i a ni n f e r - e n e e ，b a c k g r o u n dm a i n t a n a n c ea n ds u b t r a c t i o n ，d y n a m i cs c e n e ， d e p t hr e c o v e r y ，s u p e r - r e s o l u t i o n 第i v 页 独创性声明 本人声明所递交的论文是我个人在导师指导下进行的研 究工作及取得的研究成果。尽我所知，除了文中特别加以标 注和致访 的地方外，论文中不包含其他人已经发表或撰写过 的研究成果。与我一同工作的同志对本研究所做的任何贡献 均已在论文中作了明确地说明并表示了谢意。 签名：垂查封日期：塑：i 奇! 璺一协 i 1 关于论文使用授权的说明 本人完全了解中国科学院自动化研究所有关保留、使用 学位论文的规定，即：中国科学院自动化研究所有权保留送 交论文的复印件，允许论文被查阅和借阅：可以公布论文的 全部或部分内容，可以采用影印、缩印或其他复制手段保存 论文。 签名 新貉蝉, j b l e 日期 导师签名：? 至日期 伽、，) 贝叶斯信息传递在计算机视觉中的应用 第一章信息传递算法的相关理论 贝叶斯信息传递( b a y e s i a nb e l i e fp r o p a g a t i o n ) 或者叫信息传递、概率传 递( p r o b a b i l i t yp r o p a g a t i o n ) 是用来求解概率图模型概率推断问题重要算法。 在这章，我们将会简要介绍一下与概率图模型( 简称图模型) ( p r o b a b i l i s t i c g r a p h i c a lm o d e lo rg r a p h i c a lm o d e l ) ，信息传递算法有关的基本知识，并简单 总结算法在汁算机视觉中现有的应用。 简单的说，每一个概率图模型实际是一个特定概率分布的图表示。每一个 节点表示一个随机变量，所有随机变量的联合分布定义为一系列函数的乘积， 每一个乘积定义在一个互相连接的节点子集上。m i c h e a li j o r d a n 盔4 1 4 中有非 常精彩的论述： g r a p h i c a lm o d e l sa r eam a r r i a g eb e t w e e np r o b a b i l i t yt , l m o r ya n dg r a p h t h e o r 矿t h e yp r o v i d ean a t u r a lt o o lf o rd e a l i n gw i t ht w op r o b l e m st h a t o c c u rt h r o u g h o u ta p p l i e dm a t h e m a t i c sa n de n g i n e e r i n g u n c e r t , a i n t ya n d c o m p l e x i t y a n di np a r t i c u l a rt h e ya r ep l a y i n ga ni n c r e a s i n g l yi m p o r t a n t r o l ei nt h ed e s i g na n da n a l y s i so fm a c h i n el e a r n i n ga l g o r i t h m s p u n d a n m n t a l t ot h ei d e ao fag r a p h i c a lm o d e li st h en o t i o no fm o d u l m i t vac o m p l e x s y s t e mi sb u i l tb yc o m b i n i n gs i m p l e rp a r t s p r o b a h i l i t yt h e o r yp r o v i d e st h e g h mw h e r e b yt h ep a r t sa r ec o m b i n e d e n s u r i n gt h a tt h es y s t e m aw h o l e i sc o n s i s t e n t ，a n dp r o v i d i n gw a y st oi n t e r f a c em o d e l st od a t at h eg a a p h t h e o r e t i cs i d eo fg r a p h i c a lm o d e l sp r o v i d e si ) o t ha ni n t u i t i v e l ya 1 ) p e a l i n g i n t e r f a c eb yw h i c hh u m a n sc a nm o d e lh i g h l y - i n t e r a c t i n gs e t so fw u i a b l e sa 8 w e l la 8ad a t as t r u c t u r et h a tl e n d si t s e l fn a t u r a l l yt ot h ed e s i g no fe f f i c i e n t g e n e t a l p u r p o s ea l g o r i t h m s m i e h e a lih n ( 1 a n 第1 页 第一章信息传递算法的相关理论 概率图模型是图论和概率论结合的产物，因此有必要首先介绍一下和概率 图模型有关的图论基本概念。 1 1 相关的图论基本概念( g r a p h s ) 图论( g r a p ht h e o r y ) 探讨由“结点”及“边”构成的结构。研究的重点 在于节点与连线的结构( 连接) 关系，而不是距离或者方向的问题。1 7 3 6 年， 大数学家欧拉( e u l e r ) 首先以数学的方法，解决了哥尼斯堡七桥( k o e n i g s b e r g b r i d g e s l 问题。欧拉关于七桥问题的论文章被公认为是图沧研究的开始。理解概 率图模型需要了解的图论概率有： 定义11 ( p n ( g r a p h ) )一个图g 定义为两个集合，g = ve ) ，v 是有限 个节点( v e r t i c e s n o d e s ) 的集合，e 是边( l i n k e d g e s a r c s ) 燃，它是所有可 能的节点对的集合的一个子集。 定义1 2f 有向图与无向图( d i r e c t e d u n d i r e c t e dg r a p h s ) )设g 为个 图，g = k _ e 1 。如果考虑的为无序节点对，即对任意x 。，玛v ， 有( k ，x ，) = ( 玛，k ) ，则边称为无向边。如果一个图的边均为无i 柚边， 则图称为无向图。如果考虑的是有序结点对，即对任意x ，x ，v ， 有( x 。，x f ) ( x ，鼍) ，则边称为有向边。如果一个图的边均为有i 劬边，则图称 为有向图，。给定一个有向边l ，= ( x 。，x ，) ，x 。称为起点，玛称为终点。 例如，如图1 - l 为图的简单的例子，其中1 1 ( a ) 为有向图，而11 ( b ) 为无向 图。在有向图ll ( a ) m ，节点集和边集分别是 v = a ，b ，c ，d ，e ，f ) e = ( a ，d ) ，( d ，口) ，( b ，g ) ，( 只d ) ，( e ，f ) ，( d ，e ) 定义1 3 ( n i * n 集( a d j a c e n c ys e t ) ) 给定一个图g = ue 和图的个节 点x 。e ，五的邻接集，就是从x ；可以直接到达的节点的集合，g p a d ；i ( x i ) = x 3 l 玎= ( 置，玛) e 。对有向图，邻接集是所有以咒为起点的边的终节点 组成的集合。对无向图，邻接集是所有与x 。相邻的节点组成的集合。 1 女i 果个罔巾同时台有有向边和无向边 则h 成为链i 矧。我们返卫并不荚心链蚓。 第2 页 贝叶斯信息传递在计算机视觉中的应用 ( a ) 有向图 图1 - 1 圈的例子 定义1 4 ( 路径( p a t 1 ) )给定一个图g = k e ) ，咒，x ，v ，节 点五到玛的路径是一个节点列j 岛，j 已k ，满足x l = 冠，五。= 玛，且对 其中任何一节点五。( 1 m ：妒( z 1 ，z 2 ) 砂( z l ，x 3 ) 妒( x 2 ，x 4 ) 1 ) ( x 3 ，z 5 ) 妒( z 2 ，z 5 ，x 6 ) 。i 1 一 = 专砂( z 1 ，z 2 ) 妒( 1 ，z 3 ) 妒( 。2 ，z 4 ) 砂( z 3 ，z 5 ) ，p ( x 2 ，z 5 ，x 6 ) 山 z 6 现在对z 。的求和作用在p ( a ：2 ，z 。，z 6 ) 上。计算的复杂度已经从r 6 将到了r 3 。一般 说来，对需要n 次求和的概率推断，每个求和的复杂度在优化后的复杂度 为，k ，则总的复杂度将会是n 一，而不是p 。这里的是所有簇的节点的个数的 巧磊马尔可关随机场地概率密度函数可以表示为1 9 ，其中胃( ：r ) 为能量晒数n 这 点早 在1 9 8 4 年就已被g e m a n 证明，这里从圈论地角度给m 了更般更统地衷可j 第1 2 页 贝叶斯信息传递在计算机视觉中的应用 最大值。对给定的图，有标准的图论算法可以找到这个值 6 。通常在计算机 视觉中使用的马尔可夫网络的k 值都非常小，带来的计算量上的改进相当的可 观。 再来计算另外一个例子，计算图1 4 ( b ) 中的p ( x 。i z 6 ) 。首先计算边际概 率p ( x l ，z 6 ) p ( z - ，z 。) = 去e e e e 币( z - ，z 。) 妒( z ，z 。) 妒( z 。，z a ) 妒( z s ，z s ) 妒( z z ，z s ，z 。) = 去妒( x l j x 2 ) 妒( x l ，x 3 ) 币( x 2 ，x 4 ) 妒( 砘z s ) 妒( = 乏1 妒( x l i x 2 ) 廿( z ，。s ) 咖( z 。，z 。) 妒( x 2 ，x 4 ) = 三1 妒扛，z 。) 西地( z z ) 妒( z - ，z s ) 曲溉( x 2 ，x 3 ) = 喜妒( z ，z z ) 毋托( 。z ) 曲弛( z ，磊) 一z 2 = 寺地( z 1 ) ( 1 - 1 0 ) 然后积掉上式中的z 1 得到 p ( z 6 ) = 去曲( z 1 ) ( 1 _ 1 1 ) 这样就可以计算条件概率p ( z t ，x 6 ) 了 p ( x , x 6 ) c x 2 ( x 1 ) 。q x 2 ( x 1 ) 可以看到，标准化因子z 消失了。但是对于条件概率的计算 必须被显式的计算出来。 1 3 马尔可夫网络与信息传递算法 ( 1 一1 2 ) z 没有被消掉，它 在计算机视觉中，很多问题例如图象增强，立体视觉，运动估计都可 以归结为在贝叶斯框架下的概率推断问题f 严格的说是统汁推断问题) 。给定 一幅或几幅图象( 或图象序列) ，要求出一个隐含的场景特征z 。f i 同的情况 下，所求的场景特征可以是深度信息，高频信息，运动信息等等。茸先j 算后验概率p ( z j ) = 印( z ，y ) ，标准化项c = 1 p ( ) 对z 为常数。在蚍叶斯框架 下，p ( z ，y ) = p ( ) p ( 引z ) ，p ( g ) 和p ( l 。) 分别解释为先验和似然。引入马尔可夫 假设：图象和场景被分成很多的图象块，每一个小块对应一个节点。每个图象 第1 3 页 第一章信息传递算法的相关理论 图1 - 5 计算机视觉中常用的马尔可夫网络模型 块节点同时只和对应的场景块节点以及与它相邻的图像块节点相连。任两个节 点，当给定( 给定是指节点被设定为某一特定值) 两者间的节点时，两者统计独 立。当给定某场景块的节点时，对应图象块节点的相应的统讨信息完全决定。 这样就可以用如图1 - 5 的马尔可夫网络来描述。这是计算机视觉中最常用的马尔 可夫网络模型之一。需要指出的是，图像块可以小到只包含一个象素。这时每 个象素就对应一个节点。 对于马尔可夫网络1 5 ，一般上层的y 节点为可观察节点或证据节 点( e v i d e n c en o d e s l ，下层的x 为待求节点。对4 i 同问题，x 节点的含义也 是不同的，比如，可以是图象块的高频分量，运动信息，或者是深度信息等。 而y 节点，对不同问题相应的也有不同的含义，一般是可以从给定的图象( 或图 象序列) 中计算得到的关于待求节点的概率分布。后面我们会根据不同的问题 来说明x 和y 的含义。在图1 - 5 中。除了观察节点和对应的隐含节点的相容性， 本文只考虑相邻两隐含节点的相容性。一般说来，观察节点和对应的隐含节点 的相容性包含了给定图象对场景z 的要求，即贝叶斯框架中的似然，而两个隐 含节点的相容性包含的是场景本身具有的统计特性，即先验。最常用的先验是 平滑先验，即相邻的两个隐含节点的取值应该尽量接近。观察节点y 和隐含节 点x 的联合概率可以表达为1 0 1 p ( x l ，y l y n ) = 皿( t i , ：z j ) 中( 玑) ( 1 - 1 3 ) ( 2 j ) k 其中，母和西为势函数，( i ，j ) 表示在位置i 和j 的两个相邻节点，是节点的个 数。通常有两种常用的评价准则用于从后验概率分布中得到最后决策，即期望 值f 对应最小的平方误差解，m m s e ) 和众数值f 对应最大后验概率解，m a p ) 。 对于某个节点五，积掉上述的联合概率中的其他变量后再求期单，或者求后验 概率的最大值就可以分别得到在m m s e 和m a p 意义下的最优估计结果毛。对 第1 4 页 贝叶斯信息传递在计算机视觉中的应用 于离散的随机变量，表达为 严”8 e = p ( z 小，z w ，y ”一 ) z ，2 。，；， 华舻一r g m q a x 。m ，a 自x p ( 蚧蜘，y 价) ) ( 1 一1 4 1 ( 1 一1 5 ) 由于维数问题，直接1 1 4 ，1 - 1 5 两式非常困难。 信息传递算法是一种迭代的近似求解概率图模型概率推断问题的方法。 对于无环( 单连通的) 马尔可夫网络，信息传递算法可以得到严格的证明，算 法得到的解是全局最优的。但是，对于有环的( 非单联通的) 马尔可夫网络， 信息传递算法的本质还没有得到透彻的理解，寻找解的含义是当前的研究热 点之一。但是，众多学者依然建议在有环的网络中使用信息传递算法。很多 研究结果表明，在实验中，信息传递算法在有环的网络中也： 作的非常好。 最有名的例子可能是纠错编码研究中有关“t u r b oc o d i n g ”的结果。“t u r b o c o d i n g ”被学者认为是“这许多年以来。编码理论最令人兴奋和也可能是最 重要的进展之一”f “t h em o s te x c i t i n ga n dp o t e n t i a l l yi m p o r t a n td e v e l o p m e n t i nc o d i n gt h e o r yi nm a n yy e a r s ”- - m c e l i e c e ，r o d e m i c ha n dc h e n g1 9 9 5 1 1 1 ) 。 “t u r b oc o d i n g ”的编码效率接近t s h a x m o n 理论的极限。“t u r b oc o d i n g ” 的实质等价于在有环的网络中1 使用和信息传递等价的算法。在视觉领域，y a i r w e n sf 1 2 1 ，w i l l i a mt f r e e m a nf 1 1 和j s u n 1 3 1 也先后在针对不同的问题在无 环和有环的网络中使用了信息传递算法，得到了非常好的结果。 下面我们从个简单的无环网络的例子导出信息传递算法，然后对如 图1 - 5 的有环马尔可夫网络中的信息传递算法作一个简述。讨论仍将仅限于马 尔可夫网络的情形。我们这里的讨论决不是严密的证明，仅仅是面l 句应用的介 绍。更加详细的内容可以在蚓f 1 1f 3 1 找到。 1 3 1 无环网络中的信息传递算法 考虑如图1 - 6 所示的马尔可夫网络。联合分布的分布式表示带来一个非常简 1 说明f 闻为我们讨沦的是马尔可夫网络中的信息传递算法，所以我们始终用有环j e 环 来界定网络是否一定适用信息传递算法。“丑z r l ：) o c o d i n g ”研究的是有向嗣络，j l 有单联逊的 有向网络中，信息传递算法可以严格i j _ e 明。我们这里为了简单没有解释选区：i j | | 。需要指出的 是，信息传递算法媛p 是由p e a r l 针对贝叶斯脚络讨论的f 8 j 第1 5 页 第一章信息传递算法的相关理论 巾h 图1 6 一个简单的无环马尔可犬网络的例子 单的算法。例如，求节点x 1 的最大后验估计e f a p 有 壬r ”= a r g m a x m a x m a x p ( x l ，阮y l ，y 2 ，y 3 ) = a r g m a x m a x m o x t 12 x 3 垂扛1 ，y i ) o ( x 2 ，2 ) 西( z 3 ，y 3 ) v ( = l ，z 2 ) ( z 2 ，x 3 ) = a r g m a x 中( z 1 ，y i ) m a x ( z 1 ，z 2 ) 中( 。2 ，y 2 ) m a x 田( z 2 ，z 3 ) 西( z 3 ，y 3 )( 1 - 1 6 ) 注意上面1 一1 6 式的每一行中的计算仅仅涉及某一个节点和它的邻节点。 对岔r a p 和士r 9 ，都可以得到类似的结果。所以只需通过局部的所谓信息传递 计算，就可有效地计算出最后的m a p 估计结果。 假设考虑的马尔可夫网络无环，则1 1 5 可以通过迭代的进行下面的步骤得 到【8 【1 2 j 1 。例如，节点j 的m a p 估计为 i 尹”= a r g m ，a x o ( x j ，y j ) 蟛 ( 1 - 1 7 ) 。 k e a d j ( x j ) 这里。圳向取值包括中与x j 相邻的所有隐含节点的下标，而m ? 是定义为由节 点k 传向节点j 的信息( m e s s a g e s ) 。所有的信息通过下式计算 蟛= m + a x 皿( x j 胁) 中( y k ) 磁( 1 - 1 8 ) 。t e a d j ( x k ) a 3 其中城为上一次迭代中的峨。初始化时，所有的蛾都被设为向 量( 1 11 ，1 ) 。a d j ( x k ) 玛表示节点甄的邻节点去掉玛。这里势函数 通中和常被称为相容函数( c o m p a t i b l ef u n c t i o n ) ，因为它们描述了相邻节 点的概率约束。也就是说，要计算k 传向邻节点x ，的信息时，要把上次 迭代时从其他节点传过来的信息综合，加上本身的观察节点的信息，然后通 过氩，x ，之间的相容矩阵传到x ，去。对一个给定的图像节点，k = y k ，则 相容函数，中( z k ，乳) ，是一个列向量，z k 节点凰为所有可能的取值。相容函 第1 6 页 贝叶斯信息传递在计算机视觉中的应用 数皿( 轨，) 是一个矩阵，行和列分别是置和玛的可能取值。 使用例子1 6 可以说明说明l 一1 7 ，l 1 8 是怎么得到式子1 1 5 的。 信息被初始化为向量( 1 ，l ，1 ) ，第一次迭代时有 孵= i i l f l , x 皿( z 2 ) 圣( 勋，y 2 ) 1 m ；= i n o , x 皿( 。2 ，z 3 ) 中( z 3 ，蝴 3 m j = n l a x 皿( z 2 ，z 1 ) 西( z 1 ，y 1 ) 1 = m 皿( z 2 ) 西( y 2 ) 第二次迭代使用上面计算得到的信息作为m ，应用1 一1 8 式得到 因为所有的 ( 1 一1 9 ) ( 1 2 ( ) ) ( 1 2 1 ) ( 1 2 2 ) 聊= m a x 皿( z l ，z 2 ) 垂( 。2 ，) 嘲( 1 2 3 ) 埘= i i l a x 皿( z 3 ) 中( z 3 ，y 3 )( 1 - 2 4 ) 蛆= i n o u x 皿( z 2 ，z 1 ) 中( z l ，1 ) ( 1 - 2 5 ) 增= m a x 皿( z 3 ，z 2 ) 西( z 2 ，驰) m ； ( 1 - 2 6 ) 使用 霹替换 磐得到 m ：= m a x 皿( z l ，z 2 ) 中( y 2 ) i n “皿( 珐z z ) 中( z 3 ，y 3 )( 1 - 2 7 ) 信息传递的情况如图1 7 所示。此后的迭代中所有的信息不会再发生变化。最后 计算m a p 的估计结果为 i ，9 = a r g m a x o ( x l ，y 1 ) 聊 ( 1 - 2 8 ) 使用1 - 2 7 替换上式中的胼，就得到了l 一1 6 。具体的关于z 2 和z 3 的m a p 估计可以 类似的得到。可以严格的证明 8 】 1 2 ，无环嘲络中上面的迭代算法会在有限步 内收敛于每个节点的最优m a p 估计。 图1 7 信息的传递 对于m m s e 估计的信息传递算法，只需将m z 。换y , j e 。就可以类似的得 到。对于无环的马尔可夫网络，信息传递是标准的贝叶斯推断。它和隐马尔 第1 7 页 i 当聊 | 第一章信息传递算法的相关理论 可夫模型( h m m ) 中经常使用韵卡尔曼滤波器( k “m a n f i l t e r i n g ) 和前向后向算 法( f o r w a x d - b a e k w a r da l g o r i t h m ) 是完全类似的。 1 3 2 有环网络中的信息传递算法 对于有环的网络，信息传递算法是无法直接导出的，因为这时信息在传递 的过程中会被重复计算而导致错误。除非是在非常小的网络中，否则在有环的 网络中求解m a p 和m m s e 的确切解在计算上是不可能的。学者们提出了很多近 似算法。在信息编码领域关于“t u r b oc o d i n g ”的结果f 1 4 j ，在汁算机视觉领 域的一些试验【1 2 】【1 lf 1 3 和理论研究【1 2 】【3 1 5 】【1 6 】( 1 7 告诉我们：即使是 有环的网络，使用1 一1 7 和1 1 8 所定义的信息传递算法，有时也会得到很好的结 果。下面是针对如图1 - 5 的马尔可夫网络叙述信息传递算法， b e l i e fp r o p a g a t i o na l g o r i t h m 1 所有的信息( m e s s a g e s ) 露，初始化为向量( 1 ，l ， ，1 ) ，其中1 jsm ，1si n ，( m ，n ) 为如图1 5 的马尔可夫网络的格点行列数。 2 迭代的计算所有的信息：f o rf = 1 ：t 蟛= 。n 攀皿) 西驺)蟛 ( 1 2 9 ) k e a d j ( x j ) x i 其中，m ? 为上一次迭代得到的节点j 以传向x ，的信息。 3 计算信息传递的结果( b e l i e f s ) ： b ( ) 一a 垂( z ，珊) 聊 自 审( 五 z ，9 = a r g m a x b ( x ) 。 o k f l 一3 0 ) f 1 3 1 1 上面l 一2 9 和1 ，3 0 中a 是为了汁算的稳定性引入的归一化系数。以比较复杂 是l 一2 9 为例，涉及的计算可以用图1 8 。计算玛传向五的信息，旨先把从其他方 向传向码的所有信息和从巧传来的观察信息对应元素相乘，然后把结果右乘矩 阵( 甄，) ，就得到了删。注意这里所有的变量都是以离散的形式表示的。下 一节会简单介绍基于吉布斯采样的连续变量信息传递算法的实现。 第1 8 页 贝叶斯信息传递在计算机视觉中的应用 一二。_ 乙 忙口卅卧 图1 - 8 信息传递算法中1 2 9 涉及的计算 对于无环网络中信息传递算法找到的解的性质以及如何改进它，很多学者 进行了一些研究( 1 2 】 3 】 1 5 】【1 6 【1 7 卜但是除了一些简单的情形外，日前还没 有很好的解释。下一节会简单的介绍一些关于信息传递算法理论研究的重要成 果。 1 4 有环网络的信息传递算法研究进展 现在很多学者开始注意关于在有环网络中使用信息传递算法的问题， 出现了众多相关的文献。2 0 0 2 年，在n i p s ( n e u r a li n f o r m a t i o np r o c e s s i n gs ”一 t e r n ) t - ，还召开了以b e l i e fp r o p a g a t i o na l g o r i t h m so ng r a p h sw i t hc y c l e s ：t h e o r ya n da p p l i c a t i o n s 为主题的国际研讨会。但是相关的研究还远远谈不上系 统、完整。从信息传递算法应用的角度出发，我们最关心两个问题： 收敛问题：什么情形下信息传递算法会在有环的网络中收敛? 它收敛到了 一个什么样的解? 实现问题：在实际应用中，如何实现信息传递算法? 也就是说如何在各种 情况下有效的表示相关变量，以及实现相关的计算? 下面介绍一下关于这两个方面的重要进展。 1 4 1 信息传递算法的收敛 信息传递算法存在的问题还很多，其中最重要的是算法的收敛性，关于这 方面的研究也最多。事实上对于有环网络，甚至无法保证算法一定会收敛。但 在实验中，大多数情况下，算法都能很快收敛( 一般只需迭代3 一l o 次) 到个比 较好的解。表格l 一1 总结t w e i s s n f r e e m a n 在【3 】中的研究结果：1 ) 对于高斯分 第1 9 页 第一章信息传递算法的相关理论 布，从均值上说，m m s e 规则的信息传递总能正确的收敛到后验。2 ) 即使时非 高斯的情形，如果m a p 规则的信息传递收敛了，则算法找到的至少是一个局部 最优的解。 b e l i e fp r o p a g a t i o n无环网络 有环网络 | m m s em m s b 解 对高斯分布，均值正确，方差不正确 m a p m a p 解 局部最优解( 即使不是高斯分布) 表1 - 1 关于信息传递算法收敛性，引自e i s s 和n e e m a n 的工作f 3 在 1 5 中，y e d i d i a 等人证明了m m s e 规则的信息传递等价于求解对应网络 近似的自由能量“f r e ee n e r g y ”的不动点。在统计物理领域，这种近似被称作 “b e t h e ”近似。而且在