（应用数学专业论文）面向三维可视通讯的立体匹配方法.pdf

摘要 摘要 立体视觉是计算机视觉的核心研究领域。经过几十年努力，视图几何关系 的研究取得突破，理论逐步完善，方法逐渐成熟，立体匹配的研究也取得很大 进展。人们将视差场描述为马尔科夫随机场。将立体匹配表述为像素标号问 题，采用图割算法和置信传播算法估计视差场，取得很好的实验结果。近年 来，出现了三维可视通讯、基于图像的绘制等新兴应用领域，这些领域对立体 匹配提出新的要求。本文针对这些新兴应用领域，围绕质量和效率两个要素， 以马尔科夫随机场为描述工具，以图割算法为求解工具，对立体匹配问题开展 研究。主要贡献包括： 1 提出像素标号的二分法。首先将整个标号集赋给每个像素，然后将标号集 一分为二成为两个子标号集并舍弃其中一个子集，如此循环直至标号集 仅含一个标号为止。通过这种方式将多值标号问题转换为一系列二值标 号问题，从而提供了n p 难问题的一种近似解法。进一步解释上述标号过 程，并据此构造优化目标函数，证明所构造目标函数可以利用图割算法进 行优化。在此基础上，设计像素标号的置位算法，算法复杂度为l o g a 咒( 仃 是标号数目) ，而目前同类算法中效率最高的扩张算法( q e x p a n s i o n a l g o r i t h m ) 复杂度为几 k ( k 1 ) 。应用置位算法求解立体匹配问题并与扩 张算法进行比较，结果表明：在匹配质量相当的基础上，二分法具有很强 的效率优势。像素标号的二分法对立体图像没有特殊要求。方法具有很强 通用性，而且还可以应用于图像恢复、运动估计等领域。 2 提出双层立体匹配方法。回顾和分析现有分层立体匹配方法，针对前景和 背景彼此分离并各自连续的场景，提出首先确定前景层视差场和背景层视 差场，然后组合成为整体视差场的匹配方法，从而将整个匹配分解为一系 列二值标号问题，避免模型拟合与迭代改善。在此框架下进一步给出融 合颜色、对照度和形状等信息划分前景区域和背景区域的目标函数。实验 结果表明：双层立体匹配方法大大改善了匹配质量。与分层动态规划方法 比较的结果表明：双层立体匹配方法在质量和效率方面都具有一定优势。 3 基于上述两个方法，给出三维可视通讯系统中凝视校证和前景背景分离两 个关键技术问题的解决方案和实现技术。特别地，提出基于双层表达的视 图合成算法，提出基于像素标号：- i f f z h 的前景背景分离算法。进一步给出 一i 一 摘耍 实验结果，表明方法的有效性。 关键词：立体匹配，三维可视通讯，视图合成，前景背景分离，马尔科夫随机 场，图割算法。像素标号问题 一一 a b s t r a c t s t e r e ov i s i o ni saf u n d a m e n t a lt o p i ci nc o m p u t e rv i s i o n t h e r eh a v er e c e i v e d ab r e a k t h r o u g ho nm u l t i p l ev i e wg e o m e t r yi nt h ep a s td e d c s a tt h es a m el i m e , p e o p l ed e s c r i b e dd i s p a r i t yf i e l da sm a r k o vr a n d o mf i e l d , f o r m u l a t e ds t a r o om a t c h i n g a s p i x e l l a b e l l i n g p m b l e m ，a p p l i e d g r a p h c o t a l g o r i t h m s o r b e l i e f p r o p a g a t i o n a l g o r i t h m t oe s f i m a t et h ed i s p a r i t yf i e l d , a n dg o tv e r yg o o de x p e r i m e o t a lr e s u l t s i nr e c a n ty e a r s ， t h r e ed i m e n s i o n a lv i s u a lc o m m u n i c a t i o na n di m a g eb a s e dr e n d e r i n ge t e a r eb e c o m i n g n e wa p p l i c a t i o n so fs t e r e ov i s i o na n dr e q u i r eb o t hh i g hq u a l i t ya n dh i g he f f i c i e n c yo f t h em a t c h i n g i nt h i st h e s i s w ed e v e l o ps o m en o v e la p p r o a c h e sf o rs t e 豫：om a t c h i n gt o m e e tt h e s er e q u i r e m e n t s t h em a i nc o n t r i b u t i o n sc o n s i s t0 f ： 1 w ep r o p o s eb i s e c t i o na p p r o a c hf o rp i x e ll a b e l l i n g i ta s s i g n st h ew h o l el a b e ls e t t oe a c hp i x e la tf i r s t ，s p l i t st h el a b e ls e ti n t ot w os u b s e t sa n dd i s c a r d st h eo n ew i t h h i g h e r c o s t o f a s s i g n i n g i t t o t h e p i x e l i t e r a t i v e l y , u n t i l e a c hs u b s e t c o n t a i n s o n l y o n el 曲d w ep r e s e n tap r o b a b i l i s t i ei n t e r p r e t a t i o no ft h ep r o c e s s c o n s t r u c ta n e n e r g yf u n c t i o nt oo p t i m i z ei t ，a n dp r o v e t h a tt h ec o n s t r u c t e de n e r g yc a nb em i n i - m i z e dv i ag r a p hc u te x a c t l y b a s e do nb i s e c t i o na p p r o a c h ，w ep r o p o s eb i ts e t t i n g a l g o r i t h m 。i ts e t so n e b i to f e a c hp i x e l sl a b e la te a c hs t e p b i ts e t t i n ga l g o r i t h m h a sc o m p l e x i t yo f ( 1 0 9 s 扎) ，i sm o s te f f i c i e n ta m o n gs t a t eo ft h ea r tt e c h n i q u e s w ea p p l yb i ts e t t i n ga l g o r i t h mt os o l v es t e r e oc o r r e s p o n d e n c ep r o b l e m e x p e r - i m a n t a lr e s u l t sd e m o n s t r a t et h a tb o t hg o o dp e r f o r m a n c ea n dh i g he f f i c i e n c ya r e a c h i e v e d 2 w ep r o p o s eb i l a y c rs t e r e om a t c h i n gf o rs c e n e sc o n s i s to ff o r e g r o u n da n db a c k - g r o u n d i tf i r s td e t e r m i n e sd i s p a r i t yf i e l d sf o rf o r e g r o u n dl a y e ra n db a c k g r o u n d l a y e ri n d e p e n d e n t l y , t h e nc o m b i n e st h e mt o g e t h e r t og e tt h ef i n a ld i s p a r i t yf e l d u n l i k ep r e v i o u sl a y e r e da p p r o a c hf o rs t e l om a t c h i n g ，i td o e sn o tn e e dm o d e l f i t t i n ga n di t e r a t i v ea d j u s t m e n t w ea l s om a k eu s eo fc o l o ri n f o r m a t i o na n dc o n - t r a s ti n f o r m a t i o ni no n ei m a g et od e t e r m i n eab e t t e rs e g m e n t a t i o no ff o r e g r o u n d a n db a c k g r o u n d e x p e r i m e n t a lr e s u l t sd e m o n s t r a t et h a tb i l a y e rs t e r e om a t c h i n g i m p r o v e sp r e c i s i o ng r e a t l y , h a sa d v a n t a g e so nb o t hq u a l i t ya n de f f i c i e n c yo v e r l a y e r e dd y l 埔如i cp r o 掣锄n m i n g 一一 3 b a s e do i la b o v ea p p r o a c h e s ，w ep r e s e n ts o m es o l u t i o n sf o rg a z ec o r r e c t i o na n d f o r e g r o u n d b a c k g r o u n ds e g m 口t a t i o n , w h i c hi sn e c e s s a r yf o rt h r e ed i m e n s i o n a l v i s u a lc o m m u n i c a t i o n w ep r o p o s e dav i e ws y n t h e s i sa l g o f i t h mb a s e do nb i l a y e r e dd e s c r i p t i o no fs c 朗e p r o p o s eaf o r e g r o u n d b a c k g r o u n d 转g i n 蛐t a 吐a l g o - r i t h mb a s e do i lb i s e c t i o na p p r o a c hf o rp i = l e ll a b e l l i n g m o r ee x p e m n e n t a lr e s u l t s d e m o n s m t t et h a tt h et e c h n i q u e sp r o p o s e di nt h i st h e s i sa r ee f f e c t i v e k e yw o r d s ： s t e r e om a s h i n g 3 dv i s u a lc o m m u n i c a t i o n , v i e ws y n t h e s i s , f o r e - g r o u n d b a c k g r o u n ds e g m e n t a t i o n ，m a r k o vr a n d o mf i e l d s ，g r a p hc u t , p i x e ll a b e l l i n g 一一 插图 插图 1 1 立体视觉示意图 3 1 2 基于图像绘制技术分类两；意图1 1 1 3 桌匿可视通讯系统示意图1 2 1 4 论文结构示意圈1 5 2 1 成像过程1 7 2 2 三角测量1 8 2 3 极线几何1 9 2 4 立体校讵2 0 2 5 视差与深度的关系2 2 2 6 格网状图模型2 5 2 7 马尔科夫随机场估计2 8 3 1 二值标号3 4 3 2 多值标号3 5 3 3 交换算法和扩张算法3 6 3 4 二叉决策树3 8 3 5 距离关系1 4 5 3 6 距离关系2 4 5 3 7 置位算法4 7 3 ，8 置位算法的执行过程，5 2 3 9m a p 图像实验结果5 3 3 1 0s a w t o o t h 图像实验结果5 4 3 1 1t s u k u b a 图像实验结果5 5 3 1 2v e n u s 图像实验结果5 6 4 1 前景与背景5 9 4 2 两种不同的近似估计策略6 0 4 3 前景层与背景层组合6 2 一一 插图 4 4 前景区域与背景区域之间的相互影响6 4 4 5 双层立体匹配算法6 9 4 6 双层立体匹配的执行过程。7 4 4 7 前景层匹配7 5 4 8 背景层匹配7 6 4 9m a p 图像实验结果7 7 4 1 0 双层立体匹配与分层动态规划比较7 8 4 1 l 多线索信息的作用。7 9 4 1 2 利用不同信息求解结果比较， 5 1 三维可视桌面通讯系统相机配甓示意图8 2 5 2 凝视问题实例8 2 5 。3 基于双层表达的虚拟视图合成算法8 6 5 4 前景背景分离算法9 0 5 5 基于双层表达的视图合成过程9 l 5 6 不同视点的虚拟视图9 2 5 7 不同姿态的虚拟视图9 3 5 8 双层立体匹配与分层动态规划比较9 4 5 9i u 图像序列分离结果9 5 5 1 0j m 图像序列分离结果9 6 一x 一 表格 表格 3 1 置位算法的实验结果质量评估表4 9 3 2 扩张算法的实验结果质量评估表4 9 3 3 置位算法和扩张算法的效率比较表5 0 4 1 m a p 图像实验结果质量评估表7 l 一一 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成果。据 我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的 研究成果，也不包含为获得浙婆盘茔或其他教育机构的学位或证书而使用过的材料。与 我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢意。 靴敝储婵：即钿瓤峰朋尹日 学位论文版权使用授权书 本学位论文作者完全了解逝婆盘生，有关保留、使用学位论文的规定，有权保留并向 国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。本人授权逝婆盘 生可以将学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫 描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名：彳茁小于 导师签名： d 1扩谤7 鼍 7 签字日期：脚阴；9 日 签字日期：加年，月，7 日 第一章绪论 第一章绪论 自古以来，人类都在思考和探索视觉的奥秘：视觉是怎样形成的? 我们是 怎样观察到周围这个三维世界的? 人类对视觉的最初认识与对光的认识紧密联 系在一起。在古希腊时期，欧几晕德( e u c l i d ) 提出观点，认为光从人们眼睛 晕发射出去，当光到达某个物体的时。这个物体就被看见了。在罗马时代，卢 克莱修( l u c r e t i u s ) 提出观点，认为光从光源直接到达眼睛。在公元1 0 0 0 年左 右，哈桑( h a y t h a m ) 提出观点，认为光从物体反射到达眼睛，他还给出著名 的小孔成像实验证明这个观点的币确性。在1 6 0 4 年，开普勒( k e p l e r ) 从理论 上解释了眼睛的光学原理。在1 6 2 5 年，谢纳( s c h e i n e r ) 在实验中观察到形成于 眼球底部的图像。理论和实验都支持视觉是眼睛被动接受外界光刺激而形成的 观点。迄今为止，人们对包括立体视觉在内的视觉机理知之仍甚少，有待继续 探索其中的奥秘。 进入工业社会后，人类认识和改造自然的能力大大提高，发明了各种先进 机器，与此同时，人类认识和改造自然的需求也不断增长，渴望高效获取周围 世界的三维信息。人们试图让机器模拟眼睛以观察周围世界，获取三维信息。 主动方式借鉴欧几罩德关于视觉的观点，使用仪器发射测距信号到达物体以感 知物体并测量物体与仪器之间的距离，测距信号包括声纳、雷达以及激光等 等。利用这种方式可以准确获取深度( 距离) 数据，而且很容易转换为所需的 三维信息。但是，这种方式的应用往往受限于测距信号的可达范围，而且测距 信号发射和采集设备的造价通常比较昂贵。被动方式则借鉴目前视觉被动形成 的观点，利用相机拍摄待测物体或场景的图像，然后根据立体视觉原理获取深 度信息。这种方式更加接近人眼观察物体的过程，不受测距信号影响和制约， 而且图像获取设备的造价比较低廉。由于人眼立体视觉的机制尚未完全清楚， 这种方式的研究和应用仍具有很大挑战性，然而，正是这个需求激励着人们对 立体视觉开展全面深入研究。 近年来，图像获取硬件飞速发展，带动了相关技术的发展。人们利用相机 拍摄图像、采用基于图像的建模与绘制技术合成虚拟图像，就像利用相机在不 同视点拍摄的真实图像。在通讯时，人们利用摄像机拍摄自己并传送给对方， 达到可视交流的效果。这些技术依赖于立体视觉方法，又提出新的要求，给立 体视觉发展注入新的生机。 第一章绪论 1 1 立体视觉的研究历史 立体视觉是人类观察世界的基本功能，揭开立体视觉的神秘面纱可以开拓 立体视觉的应用领域。具有重要科学意义和产业价值。因此，立体视觉吸引了 众多领域的学者，研究内容丰富，研究历史悠久。在本节中，我们将从立体视 觉的机制、立体视觉的模拟以及立体视觉的应用等三个方面介绍相关领域的研 究历史。 1 1 1 立体视觉机制 1 8 3 8 年，立体镜的发明使人看到了深度景观并发现了双眼视差，开拓了立 体视觉研究领域。2 0 世纪6 0 年代，双眼驱动细胞的发现以及计算机产生的随机 点立体图的发明标志者立体视觉研究进入新阶段。4 0 多年来，心理物理学、神 经生理学以及医学等领域的学者力图发现和阐述立体视觉的心理和生理机制， 研究取得令人瞩目的进展。 在心理物理学方面。研究认为视觉的形成过程主要包括两个阶段：第一阶 段是抽取双眼物像中的某种基元，然后进行基元匹配并检测出视差信息，第二 个阶段是从所获得的视差信息中感知深度，即形成立体视觉。 在神经生理学方面，研究认为来自双眼的视觉信息在很早的阶段就发生汇 合，视差是产生立体视的充分条件。深度感知的神经机制一定发生在对形状感 知之前。研究的主要目标是确定与视觉刺激传入相应的中枢区域。 黄欣等对近年来立体视觉机制的研究进展作了比较全面的回顾【3 】。 1 。1 2 立体视觉模拟 利用计算机来模拟人眼的立体视觉功能是计算机视觉等学科的重要研究课 题【2 ，6 】，这羁介绍计算机视觉领域的相关内容。 2 0 世纪7 0 年代末，马尔( m a r t ) 系统概括了心理物理学、神经生理学及脏 床神经病理学等方面取得的重要成果，提出立体视觉的计算理论 6 9 。他将立 体视觉过程分为5 个步骤。并给出唯一性( u n i q u e n e s s ) 和连续性( c o n t i n u i t y ) 约束，为后续研究奠定了基础。 c 0 4 1 n $ o l l 在计算机上实现了m a r t 的理论并使用随机点立体图及真实图像 测试了理论模型的有效性【4 4 】，随后又增加轮廓线连续的约束并改进了实现 一2 一 第一章绪论 版本 4 5 】。在立体视觉计算理论的基础上，很多学者增加或改进一些机制、约 束，提出不同方法，d h o n d 矛1 a g g a r w a l 对2 0 t 甘纪8 0 年代的工作作了比较全面的 回顾【3 2 】。 图1 1立体视觉示意图 2 0 世纪8 0 年代初。b a r n a r d 等归纳和剖析已有立体视觉方法，认为立体 视觉方法通常执行图像获取( i m a g e a c q u i s i t i o n ) 、相机建模( c a m e r a m o d e l - t a g ) 、特征提取( f e a t u r e a c q u i s i t i o n ) 、图像匹配( i m a g e m a t c h i n g ) 、深度确 定( d e p t hd e u m 嘶n a t i o n ) 和内插( i n t e r p o l a t i o n ) 等六个步骤【9 】对后续研究产 生很大影响。 如图1 1 所示，左右相机获取场景的图像。相机建模步骤即建立相机几何模 型，通常就是确定相机的定标参数，因此又称相机定标，相机模型实际上确定 山视点o f 发射到像素鼽的射线o l 面的空间方位。特征提取则从图像中检测出显著 特征，如研和肼，显著特征包含丰富的纹理信息，为特征点的可靠匹配奠定基 础。图像匹配步骤建立左图像中特征点和右图像中特征点之问的对应关系，如 场景点p 在左右图像中投影点研和肼的对应关系。深度确定步骤根据建立起来的 对应特征点研和n 以及相机模型确定射线d l 磊和研瓦的空间方位，交会确定场景 点p 及其深度。内插步骤则根据重建的稀疏场景点内插生成更加稠密或精确的 场景点。 一3 一 第一章绪论 相机建模涉及三维景物空问中的点与二维视图平面上的点之间的几何关 系，深度确定涉及不同视点下拍摄的多个视图之间的几何关系，这两个问题g l 起计算机视觉领域的极大关注和兴趣。在2 0 世纪8 0 9 0 年代，人们对视图几何 关系问题开展了全面、深入的研究。取得了突破性进展，h a t t l e y 和z i s s e r m a u 等对视图几何关系的研究工作作了全面回顾并构建了完备理论体系【4 8 】， 求解算法逐渐趋于成熟。特征提取、图像匹配等内容则仍然是目前的研究热 点 6 9 ，7 0 ，7 8 】。 1 ，1 ，3 立体视觉应用 立体视觉的传统应用领域包括摄影测量( p h o t o g r a m m e t r y ) 、自主导航 ( a u t o n o m o u s n a v i g a t i o n ) 及工业自动化( i n d u s t r i a l a u t o m a t i o n ) 等。摄影测量 是立体视觉最古老和最成功的应用领域，在此，我们介绍摄影测量领域的相关 内容。 早在2 0 世纪初，维也纳军事地理所就按奥雷尔( o r e l ) 的思想制成了立体 自动测图仪，成功模拟立体视觉的几何过程。通过在不同视点拍摄待测物体的 像片，利用立体测图仪实现摄影过程的几何反演，测量地形或非地形的三维位 置。如今，摄影测量经历了模拟阶段和解析阶段，进入了数字阶段。数字 摄影测量利用立体匹配技术自动建立不同图像中特征之间的对应关系，测量目 标物的三维位置【5 】。在摄影测量理论趋于完善的同时，摄影测量系统也逐步 实用化，例如数字摄影测量系统v i r t u o z o 可以自动生成数字高程模型( d i g i t a l e l e v a t i o nm o d e l ) 等。 实际上，立体视觉的机制、模拟和应用等三个方面的研究是相辅相成的。 立体视觉机制的研究为模拟和应用研究提供依据和基础，模拟研究可以反馈机 制研究的成果，带动应用研究，应用研究则具有对机制研究和模拟研究的刺激 作用，譬如，m a n 的计算理论和模型建立在视觉机制研究成果的基础上，对机 制研究具有反馈作用。这种分类的界限并不是非常明确，立体视觉的模拟和应 用研究经常交织在一起。 1 2 立体匹配的研究现状 在图像获取、相机建模、特征提取、图像匹配、深度确定和内插等六个步 骤中，图像获取的研究相对较少，相机建模和深度确定属于视图几何关系润 题，目前已有比较完备的理论体系和比较成熟的方法解决这类问题，特征提取 一4 一 第一章绪论 在一定程度上服务于图像匹配，内插则属于后处理，图像匹配是关键所在。由 于所匹配图像为立体图像，故称为立体匹配。在此，我们围绕立体匹配介绍相 关方面的研究现状。 1 2 1 视图几何关系 早期立体视觉系统的工作流程都是按照上述六个步骤顺序执行，首先建立 相机模型，然后进行立体匹配，在此基础上再确定深度，人们普遍认为，只有 在相机定标基础上，才能进行立体匹配和三维重建。在2 0 世纪8 0 - 9 0 年代，人们 以射影几何与向量代数为工具1 8 5 ，8 0 】，对投影、重建以及多视图之间几何关系 等问题进行研究，将三维重建划分为射影重建、仿射重建与度量重建三个不同 层次，提出三维重建的层次方法。层次方法能利用非定标相机拍摄的图像，借 助场景的先验几何信息实现射影重建、仿射重建直至度量重建，是三维重建的 非定标法 4 8 】。 特别地，人们对两个视图的几何关系进行了深入研究。给定左右两个视点 的视图及左视图中的一个像点p ，由左视点和像点p 确定的空间直线在右视图中 的投影直线r 称为p 的极线则p 在右视图中的对应点矿必位于极线1 7 上。任意视 图中任意像点在另一个视图中都有一条极线与之对应，这种关系称为极线几 何，是两个视图之间的重要几何关系。 极线几何将对应点的位置限定在一维极线上，是很强的几何约束，对立体 匹配产生重要影响。一方面，人们利用极线约束剔除匹配过程中的错误对应 点【1 0 7 ，9 5 1 ，结合鲁棒估计方法1 3 5 ，7 5 对错误对应点的抵抗能力，构造方法自 动建立非定标图像之间的特征对应并恢复极线几何关系。另一方面，人们利用 极线几何约束校j 下立体图像，使得使得极线与扫描行吻合。简化对应点搜索。 提高匹配可靠性 2 3 1 。 1 2 2 特征提取 一直以来，特征提取是计算机视觉领域的重要研究课题【4 7 8 3 ，2 4 ，3 1 ，1 0 5 ， 9 3 1 。最近，人们基于局部不变( l o c a li n v a x i a n t ) 量构造方法检测和描述图像特 征，提取图像特征的支持区域并计算图像特征的局部不变描述。这种方法具有 良好的区分性，能抵抗遮挡等因素的影响，不随图像变换而变化，如具有缩放 不变、仿射不变等性质1 6 2 , 9 8 ，6 8 。m i k o h a j e z y k 和s c l u n i d 对这类方法作了比较 全面的比较和评估【6 9 ，7 0 1 。 一5 一 第一章绪论 1 2 3 特征匹配 在提取图像显著特征的基础上，特征匹配旨在建立这些稀疏特征之间的对 应关系。 一方面，得益于特征提取方法的进展，即使图像特征在不同图像存在比例 缩放或仿射变换等现象时，目前方法也能实现两幅图像的可靠匹配。 另一方面，利用极线几何对错误对应点的初步识别能力和鲁棒估计方法对 镭误对应点韵抵抗能力，在图像纹理丰富以及遮挡等现象不严重时。目前方法 能够自动建立立体图像的特征对应关系。 1 2 4 稠密匹配 与特征匹配不同稠密匹配确定参考图像中每个像素在匹配图像中的对应 像素，建立稠密分布的像素对应关系。一方面，像素以规则格网形式分布，像 索之间的邻接关系明确，易于描述。另一方面，匹配产生稠密分布的视差场或 深度图，提供了丰富的三维信息，为后续应用( 如视图合成) 提供可靠支持。 人们针对这类方法开展广泛研究，取得很大进展。本小节将从研究内容、匹配 方法的剖析和评估等几个方面介绍稠密匹配的研究现状。 研究内容 图像匹配的核心是比较对应点之间的相似性。由于视点的不同和视线方向 的差异，同一场景点在不同图像中的成像点可能具有不同亮度。对应点相似程 度的刻划非常困难。通常假设景物是理想漫反射体，简化光照现象，而且进一 步假设参考图像中待匹配点在匹配图像中存在对应点。忽略遮挡现象。在此假 设下，像点的亮度或颜色与其对应空间点的本身属性相关，而与相机位置无 关，可以根据亮度或颜色判断两个像素是否对应，简化图像匹配。在现实中， 这种假设条件往往无法满足。 遮挡是立体视觉中的重要现象。由于景物深度不同，距离相机较远的景 物就可能被距离相机较近的景物遮挡，从而不能形成图像。而且。由于视点 的变化，景物的遮挡区域可能发生变化。某一视点下可见的场景区域在另一 个视点下可能成为遮挡区域，这种现象称为半遮挡现象。计算机视觉中研究 的遮挡现象几乎都属于半遮挡现象。b e l h u m 锄r 等指出半遮挡现象是立体视 觉的重要线索，必须将其引入立体匹配过程中。他们在贝叶斯( b a y e s i a n ) 一6 一 第一章绪论 框架下导出匹配优化目标函数，使用动态规划方法极小化目标函数，改善了 匹配结果f 1 3 。1 2 。c , e i g e r 等观察到一幅图像中的遮挡区域往往与另幅图像 中的深度跳跃区域对应，据此构造约束条件并将其引入匹配过程中【3 9 】。在 此基础上。i s h i k a w a 与o e e r 进- - 步考虑相邻极线之问的连续性，构造了统一 模型，将其转换为网络最大流( m a x i m u m - f l o w ) 问题，然后采用图割算法求 解 5 3 】。b o b i c k 等认为高度可靠的对应点在匹配过程中可以起到控制作用，引 入地面控制点( g r o u n dc o n t r o lp o i n t ) 概念，并检测图像中的边缘点作为控制 点协助匹配。设计视差空间图像( d i s p a r i t ys p a c e i m a g e ) 数据结构，采用动态 规划法确定最佳对应点【1 8 】。s u n 等推广唯一性和连续性约束，使用可见性约 束( v i s i b i l i 哆c o n s t r a i n t ) 条件描述遮挡现象，构造优化目标函数并采用置信传 播( b e u e f p r o p a g a t i o n ) 算法优化目标函数 8 6 1 。k a n g 等针对多幅图像的情况， 选择不同图像和窗口，使得所选窗口尽可能避免遮挡现象，从而改善匹配质 量 5 5 】。 ， 透明、半透明以及镜面反射等是现实世界中普遍存在的光照现 象。s z e l i s k i 等首先对透明现象开展研究工作【9 0 】。他们提出同时恢复深度、 颜色和透明度等三种信息，给出三维视差空间数据结构，并在该空间中进 行迭代代价积聚和迭代能量优化，以求取每个像素的颜色、透明度及深 度。s z e l i s k i 等进一步针对反射现象开展研究，认为图像幽不同层叠加而形成， 将反射被反射物体、透射物体等不同景物的图像分别表达为一层图像，并给出 约束线性最小二乘方法以及迭代改善最大最小分量方法( r a i n m a x a l t e r n a t i o n ) 分离、确定不同层1 8 9 1 。t s i n 等进一步给出平面扫描( p l a n es w e e p ) 方法分离不 同层，并设计对应点相似度度量和目标函数，采用图割算法优化目标函数，不 断改善深度和颜色估计值1 9 7 。 方法剖析 随着研究不断深入，人们对各种立体匹配方法认识不断提高，s c h a r s t e i n 和s z e l i s k i 对各种方法作了回顾和分析【7 7 7 8 】，他们认为稠密立体匹配方法通 常都执行匹配代价计算( m a t c h i n g c o s tc o m p u t a t i o n ) 、代价( 支持) 积聚( c o s t ( s u p p o r t ) a g g r e g a t i o n ) 、视差计算和优化( d i s p a r i t yc o m p u t a t i o n o p t i m i z a t i o n ) 和视差精化( d i s p a r i t yr e f i n e m e n t ) 等四个步骤，将匹配方法剖分为相对独立的 四个模块。分别对应于上述四个步骤。 1 匹配代价计算：根据图像中对应像素的颜色计算它们的匹配代价。常见的 一1 一 第一章绪论 匹配代价有灰度差的平方，灰度差的绝对值等等，b i r c h f i e l d 和t o m a s i 利用 相邻像素的颜色确定一个线性函数，并据此比较像素的颜色相似度，设计 了一种对图像采样不敏感的匹配代价【1 5 】，得至广泛应用。 2 代价积聚；将周围像素的匹配代价积聚到中心像素的匹配代价上。实际 上。这一步假设支持区域内像素具有相同视差，然后在支持区域内对匹配 代价进行平均处理以减少噪声等因素的影响，以此反映相邻像素的相互作 用。一种方式取长方形或正方形窗口的支持区域，并直接以支持区域内 匹配代价的平均值作为积聚结果。如果支持区域跨越物体边缘，覆盏不 同物体，平均处理将导致不正确结果。为此。人们设计移动窗口f 1 8 】以及 自适应尺寸窗口 5 4 1 的支持区域。另一种方式通过迭代扩散方式确定支持 区域1 7 7 】，每次迭代将所有像素的匹配代价叠加到其邻近像素的匹配代价 上，逐步迭代即可确定支持区域并实现加权平均。 3 视差计算和优化：根据匹配代价计算每个像素的视差，确定视差场。局部 方法侧重匹配代价计算和代价积聚，这一阶段仅仅取对应于最小匹配代价 的视差作为计算结果。全局方法则往往跳过代价积聚，采用图像视差场的 整体约束表达相邻像素的相互作用，根据约束范围分为一维和二维优化方 法。一维优化方法针对每条扫描行施加约束，构造优化目标函数，所构造 目标函数可以使用动态规划方法进行优化。这类方法针对不同扫描行独 立进行优化，忽略相邻扫描行之间的相互作用，相邻扫描行的视差计算 结果存在明显的不一致现象1 7 1 ，1 3 ，1 2 ，1 8 】。二维优化则针对整幅图像的 视差场施加整体约束，构造优化目标函数，模拟不同方向上相邻像素的 相互作用，弥补一维优化方法的缺陷，但所构造目标函数的优化比较困 难1 7 6 ，5 3 ，2 l 】。 4 视差精化：对上述视差计算结果作精确调整。一方面，利用上一阶段计算 得到的视差场，采用内插、拟合等方法重新估计每个像素的视差值，以达 到子像素级别的精度1 6 3 ，5 4 1 。另一方面，作后处理，包括遮挡像素的检测 及其视差的恢复等 3 8 1 。一般来说，调整之后的视差场能够更加准确地反 映真实视差场一 方法评佶 观察到运动估计领域中方法比较和评估工作对该领域的研究工作起到了很 - 8 第一章绪论 大推动作用f 1 0 ，1 1 】，s z e l i s k i 等开展了类似工作，使用两种方法对立体匹配方法 进行比较和评估1 8 8 ，9 1 ，第一种方法以真实视差场为参照，对计算得到的视差 场进行评估，统计视差场的准确度，以此反映匹配方法的性能。第二种方法利 用原始图像根据计算得到的视差场合成不同视点下的新视图并以该视点下的 实拍图像为参照，与合成视图进行比较，以此反映匹配方法的性能。 在对各种方法剖析和分类的基础上，s e h a r s t e i n 和s z e l i s k i 采用以上两种方 法对匹配四个阶段的各种不同方法进行了全面比较【7 8 】，给出评估和分析。此 外，他们还开设立体匹配方法评估网站，提供各种标准测试数据，接受各种方 法的结果并对其进行评估。目前，这个平台已经成为立体匹配方法评估的标准 平台。 近年来，人们将图像视差场描述为马尔科夫随机场，将立体匹配问题转化 为能量极小化问题，利用图割算法和置信传播算法求解。评估结果表明，这类 方法取得很好实验结果，优于其它方法。这是立体匹配研究的一个重大进展。 立体匹配方法的剖析、归类和评估对立体匹配方法的研究产生很大影响， 不但有助于人们深入理解方法，而且有助于人们设计和构造更加优秀的方法。 1 2 5 马尔科夫随机场 g e m a n 等将图像描述为马尔科夫随机场( m a r k o v r a n d o mf i e l d ) ，并引入 线过程( 1 i n e p r o c e s s ) 表达其中的不连续现象，将图像恢复表述为马尔科夫随 机场后验估计【4 0 】。此后，马尔科夫随机场就在计算机视觉领域得到广泛应 用，人们利用它描述图像恢复中的灰度场、立体匹配中的视差场以及运动估计 中的运动场等等。在马尔科夫随机场表述框架下，利用随机变量表示每个站点 ( 像素) 的取值，以随机变量的相互依赖关系刻划相邻像素之间的相互作用， 捕捉数据场的局部特性，进而反映连续性等先验假设。马尔科夫随机场有效地 刻划数据场内部的相互作用，是描述和分析问题的重要工具。 在马尔科夫随机场表述框架下，问题归结为最大后验估计，进一步转 换为能量极小化。因此，马尔科夫随机场的应用潜力取决于能量极小化方 法，高效求解方法能够促进马尔科夫随机场的广泛应用，反之，则限制其 应用。g e m a n 等采用模拟退火( s i m u l a t e da n n e a l i n g ) 方法优化能量函数，理论 上，它可以求得最优解，但实际上，求解结果并不理想【4 3 】，特别地，模拟退 火法的时间复杂度为指数级别，求解效率非常低。人们还尝试迭代条件模式 ( i t e r a t e dc o n d i t i o n a lm o d e s ) 等其它优化方法 2 1 1 ，效果也不理想。 - 9 - 第一章绪论 近年来。入们构造图割算法( g r a p hc u t ) 和置信传播算法( b e u e f p r o p a g a - t i o n ) ，以此作为能量函数优化的近似方法。这两类方法不但能够求取很好的 近似解，而且执行效率较高，促进了马尔科夫随机场的应用和相关问题的研 究【9 4 ，9 2 1 。 图割方法根据能量函数中每个因子的取值巧妙构造赋权图，建立起赋权图 上的割与马尔科夫随机场的配罱之间的对应关系，并使得最小割极小化目标能 量函数，将能量极小化问题转换为赋权图的最小割问题 2 0 1 ，进而采用最大流 算法求解。当随机变量的耿值空间含有多个变量时。镯题转化为多路最小图割 ( m u l t i w a ym i n i m u mc u t ) 问题。多路图割是n p 难问题，没有好的求解算法，为 此，b o y k o v 等设计了交换( m 伊s w a p ) 算法和扩张( e x p a n s i o n ) 算法，两个 算法能够比较高效的求取良好近似解。已经得到广泛应用1 2 1 1 。 置信传播算法采用消息传递机制实现能量极小化 1 0 4 ，根据能量函数中 每个因子的取值设定相应消息( m e s s a g e ) 和置信度( b e l i e f ) ，每个站点( 像 素) 于每个变量值都有一个置信度。消息反映邻近站点变量取值对该站点变量 取值的