（测试计量技术及仪器专业论文）基于图像分割的立体匹配算法研究.pdf

r e s e a r c ho nas t e r e om a t c h i n ga l g o r i t h m b a s e do ni m a g es e g m e n t a t i o n a t h e s i si n i n s t r u m e n ts c i e n c ea n dt e c h n o l o g y p r o f e s s o rw a n gj i n g d o n g s u b m i t t e di np a r t i a lf u l f i l l m e n t o ft h er e q u i r e m e n t s f o r t h ed e g r e eo f m a s t e ro fe n g i n e e r i n g j a n u a r y , 2 0 1 0 l i i i in i l 0 19 u i y m 湖 毋训 们蒜 承诺书 本人声明所呈交的硕士学位论文是本人在导师指导下进 行的研究工作及取得的研究成果。除了文中特别加以标注和致 谢的地方外，论文中不包含其他人已经发表或撰写过的研究成 果，也不包含为获得南京航空航天大学或其他教育机构的学位 或证书而使用过的材料。 本人授权南京航空航天大学可以将学位论文的全部或部 分内容编入有关数据库进行检索，可以采用影印、缩印或扫描 等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本承诺书) 作者签名：匦整 日期：兰g ! ：! 皇 ，： 本文提出了一种基于t a o 框架的改进立体匹配算法，主要针对初始匹配点的计算、模板参数的 计算以及全局评价函数的选取进行了改进。算法通过彩色图像分割、初始匹配点的获取、区域 分类、模板参数计算和模板参数优化等步骤实现。其中图像分割采用了目前广泛应用而且比较 优秀的均值漂移算法；在t a o 的算法中，初始匹配点的计算采用基于偏差绝对值和的固定较小 窗口算法，在低纹理区域造成较多的误匹配，给后继的模板参数计算带来不利的影响，本文采 用基于变窗口技术来获取较多的初始匹配点，并在计算过程中采用一致性校验和相似点滤除等 措施去除误匹配点，以保证初始匹配点的可靠性；由于分割后存在一些初始匹配点较少的区域， 这些区域计算出米的模板参数并不准确，本文先只计算匹配点数较多区域的模板参数，然后利 用其相同或相近的模板参数近视初始匹配点较少的区域，通过模板参数优化求得不可靠区域的 最终模板参数：模板参数优化阶段，本文采用了含有数据项、平滑项和遮挡项的评价函数，增 加了遮挡约束。 本文还使用v c 6 0 开发工具在p c 机上搭建了软件系统平台，对相关算法进行了实验。实 验结果证实本文算法具有较高的匹配精度，边界清晰且定位较准确，低纹理区域的视差也得到 了较好恢复。 关键词：立体匹配，均值漂移，变窗口技术，模板计算，贪婪算法 基于图像分割的立体匹配算法研究 a b s t r a c t s t e r e om a t c h i n gi sac o r r e s p o n d e n c eb e t w e e nt h er e l a t i o n sb yl o o k i n gf o rt h es a m es p a c ea t d i f f e r e n tp o i n to fv i e wo ft h ep i x e lu n d e rt h ep r o j e c t i o ni m a g ea n de v e n t u a l l yg e tt h ed i s p a r i t ym a po f t h es c e n e s t e r e om a t c h i n gi st h ec o r ei s s u ei ns t e r e ov i s i o n h o w e v e r , d u et od e f o r m a t i o n ，o c c l u s i o n ， t e x t u r e l e s sr e g i o n st h ei m p a c to ff a l s em a t c h e s ，e t c ，s t e r e om a t c h i n gi sd i f f i c u l tt oo b t a i nh i 【g h p r e c i s i o nd i s p a r i t ym a p t h e r e f o r e ，s t e r e om a t c h i n gi st h em o s td i f f i c u l tp a r to fs t e r e ov i s i o n i nt h i sp a p e r , s t e r e ov i s i o nt e c h n o l o g yh a sb e e ns t u d i e d ，f o c u s e do ns t e r e om a t c h i n ga l g o r i t h m f r o mt h ep e r s p e c t i v eo fi m p r o v i n gp r e c i s i o no fd i s p a r i t ym a p ，a ni m p r o v e ds t e r e om a t c h i n ga l g o r i t h m b a s e do n af r a m e w o r ko ft a oh a sb e e np r o p o s e d a i m e da ti n i t i a ld i s p a r i t ya c q u i r e m e n t , t h e c a l c u l a t i o no ft h ep l a n ep a r a m e t e r sa n ds e l e c t i o no ft h eg l o b a le v a l u a t i o nf u n c t i o nh a v eb e e n i m p r o v e d a n dt h ew h o l ea l g o r i t h mi n c l u d e ss e v e r a ls t e p s ，s u c ha sc o l o ri m a g es e g m e n t a t i o n ，i n i t i a l d i s p a r i t ya c q u i r e m e n t ，s e g m e n t sc a t e g o r i e s ，t h ec a l c u l a t i o no ft h ep l a n ep a r a m e t e r s ，t h ep l a n e p a r a m e t e r so p t i m i z a t i o na n ds oo n f o ri m a g es e g m e n t a t i o n ，aw i d e l yu s e da n dr e l a t i v e l yg o o d m e a n s h i f ta l g o r i t h mh a sb e e na d o p t e d i nt h ei n i t i a ld i s p a r i t y a c q u i r e m e n to ft a oa l g o r i t h m ， d e v i a t i o ns m a l l e rw i n d o ws a da l g o r i t h mh a sb e e na d o p t e d ，r e s u l t i n gi nt e x t u r e l e s sr e g i o n sm o r e f a l s em a t c h e sa n das u b s e q u e n tn e g a t i v ei m p a c to fp l a n ep a r a m e t e r s t h i sp a p e rb a s e do nv a r i a b l e ，w i n d o wt e c h n i q u et oo b t a i nm o r ei n i t i a lm a t c hp o i n t s ，a n dt h ep r o c e s su s e di nt h ec a l c u l a t i o no f c o n s i s t e n c yc h e c k i n ga n dt h es i m i l a r i t ym e a s u r e sf i l t e r i n gt or e m o v ef a l s em a t c h i n gp o i n t si no r d e rt o e n s u r et h er e l i a b i l i t yo ft h ei n i t i a lm a t c h i n gp o i n t s b e c a u s et h e r ea r es o m er e g i o n sw i t hl e s sm a t c h i n g p o i n t sa f t e rt h es e g m e n t a t i o n ，t h e s er e g i o n so ft h ep l a n ep a r a m e t e ra r en o tc a l c u l a t e da c c u r a t e l y , t h e p a p e rc a l c u l a t ep l a n ep a r a m e t e r so fr e g i o n sw i t hm o r em a t c h i n gp o i n t s ，t h e nu s et h es a m eo rs i m i l a r p l a n ep a r a m e t e r si n s t e a do ft h el e s si n i t i a lm a t c h i n gp o i n t sr e g i o n s ，a n do b t a i n e db yt h ep l a n e p a r a m e t e ro p t i m i z a t i o n t h ef i n a l t e m p l a t ep a r a m e t e ro fu n r e l i a b l er e g i o n s i np l a n ep a r a m e t e r s o p t i m i z a t i o ns t a g e ，c o n t a i n i n gd a t ai t e m s ，s m o o t hi t e m sa n do c c l u s i o ni t e m so ft h ee v a l u a t i o nf u n c t i o n h a sb e e na d o p t e d ，w i t ho c c l u s i o nc o n s t r a i n t s t h i sp a p e ra l s ou s e sv c 6 0d e v e l o p m e n tt o o l st ob u i l do nt h ep c ，t h es o f t w a r es y s t e mp l a t f o r m f o rt h eu n d e r l y i n ga l g o r i t h mi nt h ee x p e r i m e n t t h ee x p e r i m e n t sr e s u l t ss h o wo u ra l g o r i t h mh a sa h i g h e rm a t c h i n ga c c u r a c y , t h eb o u n d a r yc l e a ra n dm o r ea c c u r a t ep o s i t i o n i n ga n dd i s p a r i t ym a po f t e x t u r e l e s sr e g i o n sh a sa l s ob e e nw e l lr e s t o r e d k e y w o r d s ：s t e r e om a t c h i n g ，m e a n s h i f t ，v a r i a b l ew i n d o wt e c h n o l o g y , p l a n ec a l c u l a t i n g ，g r e e d y a l g o r i t h m 南京航空航天大学硕士学位论文 目录 第一章绪论1 1 1 研究背景和意义一1 1 2 立体匹配技术研究进展和存在的问题3 1 2 1 立体匹配技术研究进展3 1 2 2 立体匹配存在的问题4 基于图像分割的立体匹配算法研究 3 3 3 实验结果和分析3 0 第四章基于变窗口技术的初始匹配算法3 3 4 1 引言3 3 4 2 变窗口初始匹配算法3 5 4 2 1 相似性测度函数的选取3 5 4 2 2 有效性检验4l 4 2 3 匹配窗口的选择4 2 4 2 4 自适应支撑权值的变窗口算法一4 2 4 3 实验结果和分析4 3 第五章基于能量最小化的模板优化。4 8 5 1 引言4 8 5 2 模板参数计算4 8 5 2 1 区域分类4 8 5 2 2 平面模板参数计算4 9 5 3 基于贪婪算法的模板优化5l 5 4 实验结果和分析5 2 第六章总结和展望5 6 6 1 全文总结5 6 6 2 展望5 6 参考文献一5 8 至定谢6 2 在学期间的研究成果及发表的论文6 3 一2 8 。9 1 0 1 l 图2 5 三角测量原理图1 2 图2 6 立体匹配对应关系的多义性1 3 图2 7 视差空间( d s i ) 示意图1 5 图2 8t s u k u b a 图的原始匹配代价d s ! 1 5 图2 9t s u k u b a 图叠加后的d s i 1 6 图2 1 0m i d d l e b u r y 标准图像对及标准视差图1 7 图2 1 lt s u k u b a 典型区域的图像1 8 图2 1 2 遮挡现象产生的原因1 9 图2 13 本文立体匹配算法流程图2 2 图3 1 图像坟x ，y ) 的直方图2 4 图3 2 区域生长法简例2 5 图3 3 分裂示意图。2 6 图3 4 分水岭算法示意图2 7 图3 5 分割结果图和分割区域边界图3 2 图4 1 区域匹配示意图一3 3 图4 2 基于变窗口技术的匹配算法流程图一3 4 图4 3b t 法求匹配代价3 6 图4 4 格式塔理论的两个图形组织原则3 7 图4 5 当视差为d 时自适应支撑权值算法设计示意图3 7 图4 6t s u k u b a 和v e n u s 左图以及在不同测度函数下产生的视差图4 0 图4 7 左右一致性校验示意图4 1 图4 8 相似点搜索示意图：“4 1 图4 9 相似点滤除示意图4 2 图4 1 0 初始匹配点分布图一4 5 图4 1 l 错误匹配点分布状况( 灰度级0 为错误匹配点) 4 7 图5 1 去除干扰点示意图4 9 基于图像分割的立体匹配算法研究 图5 2 采用m i d d l e b u r y 标准图的实验结果5 3 图5 3 室内左右视图、分割图及其最终视差图5 5 图5 4 三维视差曲面图5 5 1 8 2 0 4 0 4 4 5 2 5 4 基于图像分割的立体匹配算法研究 注释表 略写英文全称中文名称 s a ds u mo f a b s o l u t ed i f r e f e n c e s 偏差绝对值和 s s ds u mo fs q u a r e dd i f f e r e n c e s 偏差平方和 n c cn o r m a l i z e dc r o s sc o r r e l a t i o n归一化互相关 n pn o n d e t e r m i n i s t i cp o l y n o m i a l 非确定性多项式 g c g r a p hc u t s 图害0 b pb e l i e fp r o p a g a t i o n置信度扩展 d p d y n a m i cp r o g r a m m i n g 动态规划 d s l d i s p a r i t ys p a c ei m a g e 视差空间图 能力。人类视觉的最终目的，就是要对场景做出对观察者有意义的描述和解释。计算机视觉是 指用计算机来模拟人类眼睛的视觉功能，利用图像或图像序列来认知三维世界，实现对三维场 景的感知、识别和理解。目前广泛采用的方法有以下两种：一类是工程的方法，从分析人类视 觉功能的过程入手，并不刻意模仿人类视觉系统内部的结构，而是仅仅考虑输出和输入，并采 用任何现有的可行性手段实现系统的功能；另一类是仿生学的方法，参照人类视觉系统的结构 原理，建立相应的处理模块完成类似的功能和工作【2 】。 双目立体视觉是计算机视觉中的一个重要分支，也是计算机视觉研究的重点和热点问题之 一，其研究的核心问题是从左右图像或序列图像中计算出物体三维几何描述，并定量的确定图 像中景物的深度信息。双目立体视觉经过几十年的研究，性能不断提高，理论正处在不断发展 与完善之中。立体视觉涉及的内容很多，包括图像获取、摄像机建模( 或摄像机标定) 、双目立 体匹配( 以下简称为立体匹配) 以及三维重建等四个步骤。如图1 1 所示，左右摄像机获取场 景的图像，摄像机建模就是建立摄像机的几何模型，确定摄像机的内外参数，因此又称为摄像 机标定，摄像机模型实际是确定由视点p 发射到像素p ，和旷的射线的空间方位。立体匹配步 骤就是建立左图像中像素点与右图像中像素点之间的对应关系，如场景点p 在左右图像中投影 点p ，和矽之间的对应关系。三维重建步骤是在立体匹配之后，一旦精确的对应点建立起来， 如p z 和妒之间的对应关系，在得到空间任一点在两个图像中的对应坐标和摄像机参数的条件 下，就可以利用三角测量原理计算空间点的深度信息，进而可以计算出空间点的三维坐标，实 现三维重建。在这四个步骤中，立体匹配是整个立体视觉系统中的核心部分，立体匹配结果的 好坏将直接影响后续三维重建的结果。但是，到目前为止，立体匹配技术仍然是立体视觉中的 瓶颈问题。 基于图像分割的立体匹配算法研究 图1 1 立体视觉示意图 立体匹配是双目立体视觉中最关键也是最困难的步骤。立体匹配是通过寻找同一空间场景 在左右视点下投影图像的像素间的一一对应关系，最终得到该景物的视差图。在图像传感器经 过标定后，立体匹配的任务就在于如何准确、可靠的在左右图像中寻找匹配特征，只要立体图 像对满足一定的几何约束条件就可以实现物体的三维重建。当空间三维场景被投影为二维图像 时，同一景物在左右视点下的图像会有很大差异，而且场景中的诸多因素，如光照条件、景物 几何形状、物理特性、噪声干扰、畸变以及摄像机特性等，都被映射为图像中的灰度值。因此， 要对包含了如此多成像畸变的图像进行准确的匹配，得到精确的视差值，显然是十分困难的。 军事需求和航天应用是推动立体匹配研究的巨大动力。现代战争早已步入信息化的发展阶 段，信息成为决定战争胜负的关键。某些军事技术发达的国家，都致力于利用各种侦查手段所 获资料来重构三维虚拟战场与地形数据库的研究，为作战的决策和指挥提供强有力的信息保障， 同时也为精确制导武器的发展提供技术支持。随着空间科学技术的发展，人类的视野已经不再 局限于太阳系之内。但到现在为止，人类还不能够登上除了月球以外的其它星球，只能通过卫 星或探测机器人对这些星球进行间接考察，运用立体匹配技术重建所考察星球的三维表面成为 了当前研究的热点。我们国家正在实施的嫦娥工程，其中一个重要环节就是登月，这里面月球 探测车的导航也需要用到立体匹配技术。 此外，立体匹配技术在无人导航汽车、虚拟现实、场景漫游、目标的识别与跟踪、数字化 医学、现代工业设计、商业、娱乐、教育以及传媒等领域都有广泛的应用前景。立体匹配技术 的研究还可以促进传感器技术、计算机技术、图像处理技术、机器人技术、人工智能和模式识 别等相关学科领域的发展，同时也可以为人类逐步认识自身的视觉机制，逐步解开人类视觉的 奥秘打下坚实的基础。 本文主要研究左右图像的立体匹配问题，即双目立体匹配。在平行光轴布局的立体视觉系 统( 也称为标准立体相机布局) 中，对应像素点横坐标之差称为视差，通过三角测量原理就可 以计算每个像素对应场景信息的深度距离。因此，如果已经建立了两幅图像像素点问的对应关 系，并且两部相机已经校准过，那么利用标准立体相机布局提取深度信息是非常直观的。 2 南京航空航天大学硕士学位论文 1 2 立体匹配技术研究进展和存在的问题 1 2 1 立体匹配技术研究进展 立体视觉的研究始于上世纪6 0 年代，美国麻省理工学院的r o b e r t 完成的三维景物分析工 作，把过去的二维图像分析推广到了三维景物，这标志着立体视觉技术的诞生。立体视觉的开 创性工作是从7 0 年代中期开始的，以m a r r 3 和p o g g i 0 1 4 等人为代表的一些研究人员首次从信息 处理的角度综合了图像处理、心理物理学、神经生物学及临床神经病学的研究成果，提出第一 个较为完善的视觉系统框架，其核心是从图像恢复目标的三维形状。 从8 0 年代开始，立体匹配成为计算机视觉的研究重点之一，到了九十年代，立体匹配在各 方面都逐步成熟起来。随着计算机科学的发展，许多新理论被引入立体匹配领域，新的匹配算 法不断涌现。1 9 9 9 年康奈尔大学的v e k s l e r l 5 】在其博士论文中首次将基于图论的能量最小化理论 引入到立体匹配领域。2 0 0 1 年，康奈尔大学的b o y k o v 、v e k s l e r 和z a b i h 6 1 首先将图割( g r a p h c u t ， g c ) 优化算法引入到立体匹配中，将稠密视差匹配转化为基于图割的目标函数最小化问题，基 于图割的立体匹配方法取得了不错的效果。2 0 0 2 年，s c h a r s t e i n 和s z e l i s k i l 7 l 将立体匹配过程分 为原始匹配代价计算、原始匹配代价叠加、视差计算、视差细化等四个模块，按照四个模块的 不同，对现有算法进行了总结，并且通过对各种算法之间的性能比较，分析了不同因素对算法 性能产生的具体影响。2 0 0 3 年，微软死洲研究院的s u n 等人1 8 】首先将置信度扩展 ( b e l i e f - p r o p a g a t i o n ，b p ) 引入到立体匹配中，该方法通过消息传递机制实现能量最小化，计算 精度在s c h a r s t e i n 和s z e l i s k i 对各种算法的排名中名列前列。2 0 0 4 年，f o r s t m a n n s t 9 】提出了一种 基于动态规划( d y n a m i c - p r o g r a m m i n g ，d p ) 的立体匹配算法，能达到实时性，但匹配精度比较 低。2 0 0 6 年，清华大学的邓毅1 1 0 】提出了一种视觉导航的立体匹配算法，该算法在灰度图像上在 保证一定精度的前提下可以实现很高的处理速度，2 0 0 8 年，中国科学技术大学的郑志刚】等提 出了一种基于区域间协同优化的立体匹配算法，该算法获取了稠密的视差图，计算精度在 s c h a r s t e i n 和s z e l i s k i 对各种算法的排名中名列第二。2 0 0 1 年，t a o 等人i l2 1 提出了一种基于图像 分割的立体匹配算法框架，该算法框架基于平滑表面假设，即在单一的色彩区域中视差变化是 平滑的，视差不连续处只与分割区域边缘一致，这样就可以通过一个平面模板来描述该区域， 基于这个假设，就可以把传统的基于全局算法中对每个像素点分配最优视差的问题转化为对每 个区域分配最优模板的问题，从而可以取得较好的效果。从此，基于图像分割的立体匹配算法 越来越引起研究者的兴趣【4 0 m 】； 当前立体匹配技术的研究依然非常活跃。在几个著名的国际会议中每年都有立体匹配的最 新成果报道和专题交流，比如国际计算机视觉会议( i c c v ) ，计算机视觉，国际模式识别会议 ( i c p r ) ，计算机视觉与模式识别会议( c v p r ) ，图形与图像处理会议( c v g i p ) ，欧洲计算机视觉 3 基于图像分割的立体匹配算法研究 会议( e c c v ) 和亚洲计算机视觉会议( a c c v ) 。有关立体匹配的国际刊物也有很多，有国际机器 视觉杂志( i j c v ) ，模式分析与机器智能( i e e et r a n so np a m i ) ，模式识别( p r p a t t e r nr e c o g n i t i o n ) ， s p i e 的论文集和期刊( p r o c e e d i n g sa n dj o u r n a lo f s p i e ) 等，在这些会议和刊物上每年发表的文章 有百余篇。 国内外很多研究机构也致力于立体匹配技术的研究，国外主要有卡耐基梅隆大学的机器人 技术研究所的视觉和自动化研究中心，加拿大哥伦比亚大学的智能计算实验室成立的p o i n t g r e yr e s e a r c h 公司，德国波恩大学的计算机视觉研究组，日本大阪大学自适应机械系统研究院 等；国内主要有微软亚洲研究院的视觉计算小组，清华大学的计算机科学系，浙江大学的机械 系，中国科学技术大学的自动化系，哈尔滨工业大学的机器人研究所，中国科学院长春光学精 密机械与物理研究所等。 1 2 2 立体匹配存在的问题 虽然当前立体匹配的研究非常活跃，但由于其涉及的问题太多，至今仍未得到很好的解决。 如何提高算法的抗干扰能力，如何减少算法的误匹配，如何降低计算的运算量，仍需要进行更 深入的探索和研究。对导致立体匹配问题难度较大的原因总结如下： ( 1 ) 成像过程是通过二维的图像信息来描述三维的景物，不可避免的存在大量信息的缺失， 因而，要从二维图像计算场景的三维信息本身存在难度； ( 2 ) 成像时外部条件的变化：成像过程中不可避免的存在光线变化、传感器噪声和一些非 线性因素的影响，以及外界不可预知噪声的影响，因此左、右视图中对应点的灰度值可能出现 相差较大的情况； ( 3 ) 遮挡：所谓遮挡是指由于相机角度的原因，某些景物只在一幅图像中看得见的情况， 一般来说，左、右图像的相机位置相隔越远，存在遮挡的可能性越大，遮挡的情况比较复杂； ( 4 ) 低纹理区域：真实场景中，一般总存在一些低纹理区域，使得匹配难以进行。灰度相 似性约束在纹理不明显区域是无用的； ( 5 ) 深度不连续性：在物体边界处，平滑性约束一般是不满足的，也就是说，信息扩展在 视差不连续的地方停止。 因此，一个良好的立体匹配算法应该具备以i 力) ( 2 1 0 ) v ( j ，y ) 该指标反映了计算所得视差值的误差大于某一闽值的点数在整幅图中占有的比例，一般取 磊= l 。均方根误差r 用下式来计算： 、! 尺2 土。v 。z ，y ，l a c ( x ，y ) 一面( x ，y ) 1 2 j 2 ( 2 1 1 ) 该指标反映了估计视差图以( x ，y ) 与真实视差图露( x ，y ) 之间视差值的统计误差。式2 1 0 和 2 1 1 中d x x , y ) 为坐标 的估计视差，d t ( x , y ) 为真实视差，为图像像素个数。 为了更好的衡量算法在不同区域的效果，还要从图像中提取出两类典型区域进行测试：遮 挡区域( o c c l u s i o nr e g i o n ) 禾l l 视差不连续区域( d e p t hd i s c o n t i n u i t yr e g i o n ) 。图2 1 1 给出t n 试图 像t s u k u b a 典型区域的图像。图( a ) 中深度不连续区域用白色表示，遮挡和边界区域用黑色表示， 其他区域用灰色表示。图( b ) 中遮挡和边界区域用黑色表示，非遮挡和边界区域用白色表示。 ( a ) 深度不连续区域( b ) 遮挡和边界区域 图2 1 lt s u k u b a 典型区域的图像 ( 1 ) 深度不连续区域为视差图中像素的深度( 视差) 发生阶跃突变的区域，即该像素与邻域像 素视差差异超过一定阈值的相邻像素组成的区域，用d 表示，深度不连续区域匹配错误百分比 用表示。这个区域的判定以真实视差图为标准。若i 办 ，y ) 一砟( x ，j ，+ 1 ) | 乃，则像素( r 和( x 扩1 ) 属于深度不连续区域，若i 砟( x ，y ) 一砟( x + 1 ，y ) i 乃，则像素0 ) 和0 + 1 ) 属于深度 1 8 南京航空航天大学硕士学位论文 不连续区域，其中乃为阈值。 ( 2 ) 遮挡区域是指被遮挡的区域。它们只在一幅视图中出现，而另一幅视图中没有对应像 素，用o 表示，除此以外为非遮挡区域，用d 表示，非遮挡区域匹配错误百分比。因为遮 挡区域没有对应的匹配像素，冈此对遮挡区域内的像素匹配进行评价是没有意义的，因此岛是 衡量匹配结果好坏的主要指标。 图2 1 2 反映了立体匹配中遮挡现象产生的原因。 ab de 图2 1 2 遮挡现象产生的原因 图2 1 2 ( a ) 中区域b 只能被左侧摄像机看到，而右侧摄像机无法看到，对左视图而言，区域 b 被称为遮挡区域。从图2 1 2 ( b ) 中可以看出，遮挡区域一般均发生在视差由较小值突变到较大 值的区域。 为与其他研究者的方法结果做定性和定量比较，我们后续章节中提出的立体匹配算法主要 以m i d d l e b u r y 网站的标准图像对为测试图像进行了测试，并依据非遮挡区域匹配错误百分比 岛，所有区域匹配错误百分比和视差不连续区域匹配错误百分比三个指标对算法进行 了比较，每个指标都是在一= l 的情况下得到的。因为我们采用的图片都是经过校正以后的， 所以本文中的匹配算法都没有考虑图像校正这一步骤。 对于没有标准视差图的情况，一般采用转换比较法评价算法的优劣。转换比较法是根据计 算所得的视差图对参考图或匹配图中的像素点进行坐标转换，从而得到一幅新图，再将这幅新 图与匹配图或参考图进行比对，最终得出误差值。根据像素点坐标转换作用在不同的图上，可 以分为两种： ( a ) 止向转换( f o r w a r dw a r p i n g ) ：将参考图进行坐标转换得到新图，将新图与匹配图进行比 对，得出误差值。误差值越小，表示算法精度越高。 ( b ) 反向转换( i n v e r s ew a 巾i n g ) ：将匹配图进行坐标转换得到新图，将新图与参考图进行比 对，得出误差值。误差值越小，表示算法精度越高。 转换比较法更适用于没有标准视差图的情况，但是标准视差图比较法应用的更为广泛。 本文算法测试平台是p c1 7 g h za m da t h l o n ( t m ) 6 4 * 2 d u a l c o r e 处理器1 gr a m ，操作系 1 9 基于图像分割的立体匹配算法研究 统为w i n d o w s x p ，编程工具为v c 6 0 。 2 3 本文立体匹配算法框架 迄今为止国内外提出了许多立体匹配算法，根据约束方式的不同，文献把立体匹配分为 局部匹配算法和全局匹配算法两种。见表2 2 ，表中同时也列出了常见的一些算法特性。 ( 1 ) 局部匹配算法 局部匹配方法是对像素周围小区域进行约束。其优点是计算量小，速度快，易于硬件实现 和加速，许多立体视觉系统都采用了局部匹配方法【1 9 。2 1 1 。但是这类方法受局部不明确的图像区 域( 例如遮挡区域) 影响较大，和全局匹配方法相比其视差图的误匹配率较高。 在局部算法中，根据匹配基元的不同，分为区域( 窗口) 匹配算法【2 2 , 2 3 1 和基于特征的匹配 算法1 2 她6 1 。其中，基于区域的匹配算法最为常见。区域匹配算法是解决基元对应问题的一个最 直观最简单的方法。其思想就是考察匹配点各自邻域窗口内像素集合的相似性。区域匹配算法 需要进行逐点匹配，对噪声很敏感，可以得到整幅图像的稠密视差图，但视差图误匹配率较高。 区域匹配方法是按照逐点的策略进行匹配，但许多实际应用中感兴趣的只是某些具有鉴别信息 的特征，如边缘、轮廓等，这些特征信息量少，处理方便，而且能表征物体的主要信息。但基 于特征的立体视觉匹配算法，其结果是稀疏的视差图，如果需要，可以通过内插等方法来得到 完整的深度图【2 7 l 。这一类算法因各自采用的匹配基元不同而相异。概括而言，该类匹配算法都 是建立在特征匹配基元之间的相似性度量基础上的，是以匹配基元的各项参数信息为依据的局 部特征相似程度的度量。基于特征的匹配算法特别适用于具有显著特征信息的环境( 如室内环 境) ，具有速度快、精度高的特点，但在缺少显著主导特征自然环境下，该方法也遇到很大困 难。 ( 2 ) 全局匹配算法 全局匹配算法是对扫描线甚至整个图像进行约束。一般可以被归纳在一个能量最小化的框 架下进行，得到能量函数后，再利用各种优化算法米最小化能量函数，从而得到视差的最优解。 目前解决此类问题比较流行的优化算法包括动态规划【2 8 2 9 1 、图割m 3 1 1 和置信度扩展【1 1 , 3 2 , 3 3 1 等。 因为全局匹配算法提供了额外的优化，因此匹配准确性较高，但是这类方法计算复杂度较高， 速度相对较慢。 2 0 表2 2 匹配算法分类 匹配算法算法描述参考文献 窗口匹配在一定范围内搜索最大相似性 3 7 ，3 8 】 局部匹配算法 特征匹配对可靠的特征( 如角点、边缘等) 进行匹配 3 4 - 3 6 】 动态规划为扫描线的视差确定一条最优路径 【2 8 ，2 9 】 全局匹配算法 图割算法把视差确定为图中最大流的最小割问题 3 0 ，3 1 南京航空航天大学硕士学位论文 局部方法的特点是速度较快，但是这类方法受局部不明确的图像区域( 例如，遮挡区域、纹 理重复区域) 影响较火。全局匹配算法是对扫描线甚至整个图像进行约束，一般可以被归纳在一 个能量最小化的框架下得到视差的最优解。如图害i j ( g r a p h c u t ，g c ) 3 0 , 3 1 1 和置信度扩展( b e l i e s p r o p a g a t i o n ，b p ) 【l l ，3 2 ，3 3 】等全局优化算法的成功应用，这类算法不受局部不明确图像区域的影响， 因为全局约束提供了额外的优化，但是这类方法计算复杂度较高。近年来出现了一些将局部和 全局优化相结合进行匹配的算法1 4 叫2 1 ，这些算法考虑到两种方法各自的优势，有效地将二者结 合起来。本文研究的立体匹配算法就是有效地结合了局部算法和全局算法，即利用局部算法获 取的初始匹配点作为模板参数计算使用，然后利用贪婪全局优化算法对模板进行优化求得每个 区域的模板参数，以期得到更佳的匹配效果。 t a o 等人于2 0 0 1 年提出了一种基于图像分割的立体匹配算法框架，该算法首先把参考图像进 行分割，不同于以往基于像素匹配对每个像素分配视差，而是把每个区域当成整体，以一个视 差模型来估计整体视差。这其实隐含一个假设，在单一的色彩区域中视差变化是平滑的，视差 不连续处只与分割区域边缘一致，这通常在真实自然场景中是成立的。基于分割区域的算法利 用图像分割信息带来的好处，使得它们在传统上被认为是有困难的区域得到了成功应用。这些 优势f 4 4 】在于： ( 1 ) 最明显的好处在于基于区域的立体匹配技术限制了在同一区域内的视差必须符合同一 模型，换言之，区域内的平滑是被强制执行的。这对缺少纹理的区域匹配非常有好处； ( 2 ) 把参考图像分割获得具有同一颜色的区域所获得的视差边界在很多时候比单纯由视差 估计的边界更为准确。很多立体匹配算法在重建时含蓄或明确的简化了对象的形状。因此，当 存在较多复杂形状时它们的匹配效果下降较大。而分割可以对此问题进行补救； ( 3 ) 通常分割区域数会明显小于图像像素数，这使基于区域的立体匹配算法的效率更高。 我们借鉴了文献1 1 2 l 算法框架的基本思想，主要针对初始匹配点的计算、模板参数的计算以 及全局评价函数的选取进行了改进。在t a o 的算法中，初始匹配点的计算采用偏差绝对值和算 法，由于匹配窗口的选取较小，在低纹理区域造成较多的误匹配，进而每个分割区域里的初始 匹配点较少，给后继的模板参数计算带来不利的影响。为了使区域模板参数计算的更准确，本 文采用自适应支撑权值的变窗口算法来计算初始匹配点，并在计算过程中采用一致性校验和相 似点滤除等措施去除误匹配点，以保证初始匹配点的可靠性。在t a o 的算法中，模板参数为直 接对分割后对所有区域进行计算所得，由于分割，f ；彳存在一些可靠点较少的区域( 不可靠区域) ， 使得这些区域计算出来的模板参数并不准确。本文算法先只对匹配点数较多的区域( 可靠区域) 计算其模板参数，由于在利用变窗口技术获取的初始匹配点时不可避免的会带来一定的误差， 而模板参数的计算恰恰很容易受误差点的影响，所以我们在计算模板参数之前排除数据中的干 扰点，从而增强了模板参数的鲁棒性，然后利用相同或相近的可靠区域模板作为不可靠区域的 2 l 基于图像分割的立体匹配算法研究 初始模板，通过模板参数优化求得不可靠区域的最终模板参数。另外，针对遮挡像素处理的问 题，本文在模板参数优化阶段，采用了含有数据项、平滑项和遮挡项的评价函数，增加了遮挡 约束，进一步提高了算法的匹配精度。低纹理区域和边界区域往往是误匹配率较高的区域。在 本文算法中，区域中这些点的视差是通过区域的模板参数间接计算所得的，模板参数则是由区 域内的初始匹配点计算出来的，而初始匹配点通过了一致性校验和相似点滤除等措施，可靠性 得到了保证，可信度较高。 改进后的算法流程如图2 1 3 所示： 图像分割 士 初始匹配点获取 士 区域分类 ， 模板参数计算 模板参数优化 最终视差图计算 图2 1 3 本文立体匹配算法流程图 算法由六个主要步骤构成：首先采用均值漂移算法进行彩色图像分割；然后采用自适应