（信息与通信工程专业论文）面向深度提取和形状识别的图像匹配.pdf

国防科学技术大学研究生院博士学位论文 摘要 图像匹配是计算机视觉和图像理解领域的研究热点之一，己广泛应用于多源图像数据融 合、环境监测、目标识别、三维重建等诸多领域。虽然图像匹配问题有一个统一的处理框架 和思路，但每一类具体的图像匹配问题也都有其特殊的处理方法。论文主要研究了面向目标 深度信息获取的立体匹配和面向形状的目标模型识别方法与技术。 在面向目标深度信息获取的立体匹配研究方面，论文在评述了立体匹配的基础理论、存 在难点、遮挡检测、评价标准、主要方法等以后，具体研究了局部立体匹配和全局立体匹配 问题。 在局部立体匹配方法研究中，针对应用最为广泛的基于区域的局部匹配方法的不足，提 出了两个算法。一是仅仅利用灰度信息即可确定匹配窗口的改进方法，由于不需要同时测算 局部灰度和视差变化，因此可以方便地利用整数图像来提高效率，而且计算量与窗口大小无 关。二是扩展仅仅基于灰度取得匹配窗口的方法，提出了基于视差点的大遮挡检测立体匹配 算法，通过在视差点的结构中用参数来分别描述直线的斜率和左右遮挡量，该方法能够处理 斜平面和遮挡问题。 在全局立体匹配研究中，针对基于分割的全局立体匹配易受颜色分割错误影响的缺点， 提出了两个新算法。是基于像元集的树加权置信扩展立体匹配方法，利用初始视差控制点 的直方图分布来对颜色分割后的区域进行二次分割，有效的缓解了视差在颜色相似区域内发 生跳跃所带来的匹配错误。二是将唯一性约束扩展到分割域中，提出了基于复杂分割的对称 遮挡检测算法，能够在分割域检测遮挡，该算法在以国际标准图像所进行测试的2 4 个算法 中综合指标名列第三。 在面向形状的目标模型识别方法研究方面，提出了两个模型匹配的应用算法。一是基于 交比不变量的利用局部不变特征识别复杂平面多边形的算法，该算法能够适用目标局部缺损 和丢失少数顶点的情况，计算量小，识别效率高。二是基于梯度模板的复杂成像条件下的数 字识别算法，该算法可以消除钢铁厂生产环境中光照、灰尘、油漆脱落、机器震动、成像对 象移动、数字质量不统一和遮挡等因素对识别处理的影响，在工厂试验生产线上达到8 0 以 上的识别率。 主题词：立体匹配，模板匹配，遮挡检测，自适应窗口，动态规划，图像分割，置信扩展， 交比不变量，数字识别 第i 页 国防科学技术大学研究生院博士学位论文 a b s t r a c t i m a g em a t c h i n gi sa na t t r a c t e da r e ai nt h ef i e l do fc o m p u t e rv i s i o na n di m a g eu n d e r s t a n d i n g ， w h i c hh a sb e e nw i d e l yu s e di nm u l t i s e n s o ri m a g ef u s i o n , e n v i r o n m e n t a lm o n i t o r i n g ，t a r g e t r e c o g n i t i o n , a n d3 dr e c o n s t r u c t i o n a l t h o u g hi m a g em a t c h i n go b 乃, sau n i v e r s a lf r f l l x l e w o r k ，e a c h c l a s so fp r o b l e mi sd e s i g n e db ) ，i t ss p e c i f i ca p p l i c a t i o n t h i sp a p e rf o c u s e so nt h et e c h n i q u eo f s t e r e om a t c h i n gf o rd e p t hr e c o v e r ya n dm o d e l b a s e dm a t c h i n gf o rs h a p er e c o g n i t i o n i ns t e r e om a t c h i n gf o rd e p t hr e c o v e r y ，b o t hl o c a la n dg l o b a ls t e r e om a t c h i n ga l g o r i t h m sa r e m a i n l ys t u d i e da f t e rr e v i e w i n gt h e i s s u e so fb a s i ct h e o r y ，d i f f i c u l t i e s ，o c c l u s i o nd e t e c t i o n , e v a l u a t i o na n dm e t h o d sf o rs t e r e om a t c h i n g i nt h er e s e a r c ho fl o c a ls t e r e om a t c h i n g ，t w on e wm e t h o d sa r ep r o p o s e df o rr i d i n go u tt h e d e m e r i to fa r e a - b a s e dm e t h o d su s e dw i d e l y f i r s t l y ，a ni m p r o v e da p p r o a c ht h a to n l yu g a sg r a y i n f o r m a t i o nt od e c i d et h ew i n d o ws i z ei sp r o p o s e d s i n c et h es e l e c t i o no f w i n d o ws i z ed o e s n tn e e d b o t hl o c a lg r a ya n dd i s p a r i t yv a r i a t i o n , i tc a l le a s i l ym a k eu s eo fi n t e g r a li m a g et e c h n i q u et os p e e d u pc o m p u t a t i o na n dt h ec a l c u l a t i o ni si n d e p e n d e n to fw i n d o ws i z e ，s e c o n d l y ，a na l g o r i t h mb a s e d o nd i s p a r i t yp o 抽tf o rd e a l i n gw i t hl a r g eo c c l u s i o ni sd e v e l o p e d ，w h i c he x t e n d st h ef i r s tm e t h o d i t c a nr e s o l v et h ep r o b l e mo fs l a n t e d s u r f a c ea n do c c l u s i o n , s i n c es o m ep a r a m e t e r sa r eu s e dt o d e s c r i b et h es l o p eo f h n ea n do c c l u s i o n sd i s t i n c t l yi nt h ep a r a m e t c r i z a t i o ne r ad i s p a r i t yp o i n t i nt h er e s e a r c ho fg l o b a ls t e r e om a t c h i n g ，t w on o v e la p p r o a c h e sa r ep r o p o s e di no r d e rt os o l v e t h e p r o b l e mt h a ts e g m e n t - b a s e dm e t h o d i sr e a d i l ya f f e c t e db yt h ee r r o r so fi n i t i a lc o l o r s e g m e n t a t i o n f i r s t l y ，t h ep i x e l s e tb a s e ds t e r e om a t c h i n ga l g o r i t h m sb yu s i n gt r e er e w e i g h t e d b e l i e fp r o p a g a t i o ni so f f e r e d t h ei n i t i a lc o l o rs e g m e n t si ss e g m e n t e da g a i na c c o r d i n gt ot h e h i s t o g r a mo fi n i t i a lg r o u n dc o n t r o ld i s p a r i t yp o i n t s t h e r e f o r ei tc a l ls u f f e rl e s sf r o mt h ee r r o rt h a t d i s p a r i t y b o u n d a r i e sa p p e a ri n s i d et h er e g i o n sw i t hs i m i l a rc o l o r s e c o n d l y ，t h es y m m e t r i c s e g m e n t b a s e da l g o r i t h mi sp r e s e n t e d ，w h i c hd e t e c t so c c l u s i o ni ns e g m e n tl e v e lb ye x t e n d i n g u n i q u e n e s sc o n s t r a i n tf r o mp i x e ld o m a i nt os e g m e n td o m a i n t h ee x p e r i m e n tr e s u l t so nt h e s t a n d a r dd a t as e t ss h o wt h a to u ro v e r a l lp e r f o m m e et a n k st h et l l i r do u to fa b o u t2 4a l g o r i t h m s i nt h er e s e a r c ho f m o d e l - b a s e dm a t c h i n gf o rs h a p er e c o g n i t i o n , t w oa l g o r i t h m sf o ra p p l i c a t i o n a r ep r o p o s e d f i r s t l y ，t h ea p p r o a c ht or e c o g n i z ep l a n a rp o l y g o nb yl o c a li n v a r i a n tf e a t u r e sb a s e do n c r o s s - r a t i oi sp r o p o s e d i th a sl i r l ec o m p u t a t i o n a lc o m p l e x i t ya n ds t a b l ep e r f o r m a n c e ，e s p e c i a l l y f o rt h el o c a li n c o m p l e t ep l a n a rp o l y g o n , e v e nl o s i n gaf e wv e r t i c e s s e c o n d l y ，t h em e t h o db a s e d0 1 3 g r a d i e n tt e m p l a t ei m a g et or e c o g r l i z en u m b e ri m a g i n gi nc o m p l i c a t e dc i r c u m s t a n c ei so f f e r e d i t c a l lr e m o v et h ee f f e c t sb yt h ei l l u m i n a t i o nc h a n g e ，d u s t ，o i lp a i n tb r e a k i n go f f , m a c h i n es h a k i n g ， o b j e c t sm o t i o n , l o wq u a l i t yn u m b e ra n do c c l u s i o ni nt h ep r o d u c tl i n ee n v i r o n m e n to fas t e e lm i l l t h ef i n a lr e c o g n i t i o nr a t eo f a b o v e8 0 i sa c h i e v e di na ne x p e r i m e n t a lp r o d u c tl i n e k e yw o r d s ：s t e r e om a t c h i n g ，t e m p l a t em a t c h i n g ，o c c l u s i o nd e t e c t i o n ， a d a p t i v ew i n d o w ，d y n a m i cp r o g r a m m i n g ，i m a g es e g m e n t a t i o n ，b e l i e fp r o p a g a t i o n ， c r o s s r a t i oi n v a r i a n t ，n u m e r i cr e c o g n i t i o n 。 第i i 页 国防科学技术大学研究生院博士学位论文 图1 1 图2 1 图2 2 图2 3 图2 4 图2 5 图2 6 图2 7 图2 8 图2 9 图2 1 0 图2 1 l 图2 1 2 图2 1 3 图2 1 4 图2 1 5 图2 1 6 图2 1 7 图2 1 8 图3 1 图3 2 图3 3 图3 4 图3 5 图3 6 图3 7 图3 8 图3 9 图3 1 0 图3 1 l 图3 1 2 图3 1 3 图目录 从双目图像获得深度数据的系统框图2 立体中的对极几何 标准结构的双目立体几何1 2 小孔相机模型1 3 视差空间示意图1 5 t s u k u b a 视差空间图像。1 5 局部非参数变换1 9 b i r c h f i e l d 测度计算示意图。2 0 t s u k u b a 、m a p 、s a w t o o t h 、v e n u s 测试像对及其标准视差图像2 2 t e d d y 和c o n e s 的测试像对及其标准视差图像2 3 三类典型区域2 4 自遮挡示意图2 5 单遮挡示意图2 5 大视差小遮挡示意图2 5 多遮挡示意图2 6 块匹配示意图2 8 特征关系图3 0 特征图的建立和匹配3 0 扫描线关系的两种构造方式3 l 紧致窗口示意图3 4 左图像的匹配窗口和右图像的目标窗口示意图3 6 窗口非线性扩展示意图3 7 窗口代价、窗口和视差的关系3 9 整数图像技术示意图4 0 利用最d , - - 乘估计视差的流程图4 2 t s u k u b a 图像匹配的结果4 3 本文所得结果和标准视差图4 3 检测遮挡示意图4 5 检测遮挡示意图。4 6 视差曲线示意图4 9 视差点结构5 0 本文算法在不同实验图像上的结果5 5 第v 页 国防科学技术大学研究生院博士学位论文 图3 1 4 算法的遮挡检测结果5 5 图3 1 5 不同算法在t s u k u b a 图像上的运行结果5 6 图4 1 图4 2 图4 3 图4 4 图4 5 图4 6 图4 7 图4 8 图4 9 图4 1 0 图4 “ 图4 1 2 图4 1 3 图4 1 4 图4 1 5 图4 1 6 图4 。1 7 图4 1 8 图4 1 9 图4 2 0 图4 2 l 图4 2 2 图4 2 3 图4 2 4 图5 1 图5 2 图5 3 图5 4 图5 5 图5 6 图5 7 图5 8 图像标号示意图。5 9 扫描线一视差的g r a p h 示意图6 l m a r k o v 随机场分布图6 3 b p 算法中的信息6 4 b p 计算过程示意图6 4 有环和无环的图结构6 5 利用图割和置信扩展优化得到的m 却立体图对的不同匹配结果6 5 基于分割的匹配算法的一般流程。6 6 s a w t o o t h 图像的分割结果6 7 视差平面参数求解的中间过程图像6 8 基于像元集的立体匹配流程图6 9 图像分割结果7 0 不同参数下厂( x ) 的形状7 1 局部图像的g c p 视差直方图分布及二次分割后的结果7 3 匹配过程图像和结果图像7 6 m a p 图像实验结果7 6 图像视差分割示意图7 9 视差分割过程的中间图像7 9 图像复杂分割过程示意图8 0 区域之间的对应性8 2 对称检测遮挡算法流程8 3 t e d d y 图像匹配过程的中间图像8 4 三个图像序列的结果图像8 5 遮挡检测结果8 6 共点共面的四条直线9 0 有三个顶点共线的凹多边形9 l 确定最佳匹配点的位置9 2 模型及其摄影图像9 4 典型工业机器视觉系统结构。9 6 机器视觉应用系统中涉及到的图像信号处理9 7 新余炼钢流程。9 9 堆放区在不同时刻的图像1 0 0 第v i 页 国防科学技术大学研究生院博士学位论文 图5 9转炉在不同阶段的图像1 0 0 图5 1 0 无法识别出数字的图像1 0 1 图5 1 l 数字识别流程1 0 2 图5 1 2 转炉处图像的中问处理结果1 0 3 图5 1 3 与m e s 系统接口程序流程1 0 4 图5 1 4 图像与模板示意图1 0 5 图5 1 5s o b e l 梯度算予1 0 6 图5 1 6 典型测试图像l 。1 0 9 图5 1 7 典型测试图像2 。l l o 图5 1 8 典型测试图像3 1 1 1 第v i i 页 国防科学技术大学研究生院博士学位论文 表目录 表1 1 表2 1 表3 2 表3 1 表3 3 表3 4 表4 1 表4 2 表4 3 表4 4 表4 5 表4 6 表4 7 表4 8 表5 1 表5 2 表5 - 3 表5 4 立体匹配方法分类5 遮挡检测方法分类2 7 本文算法的运行时间4 3 本文方法与各种方法的定量指标4 4 算法在不同阶段得到的视差点数量5 5 不同立体匹配算法对四幅标准图像的测试结果5 6 图割和置信扩展优化在得到的能量函数值和运行时间上的不同6 5 四幅标准图像过分割和欠分割后的像元集数目7 4 各种方法的定量指标7 7 m a p 图像匹配结果指标7 7 分割的各个阶段的基元数目8 0 算法实现过程中所用到的参数值8 3 算法在各步骤中花费的时间( 表中的时间单位为s ) 8 5 不同算法在新的测量标准下的量化指标和综合排名。8 6 识别顶点没有丢失的目标 识别顶点不全的目标9 5 任务说明9 9 各个任务的运行指标。1 0 8 第1 v 页 独创性声明 本人声明所呈交的学位论文是我本人在导师指导下进行的研究工作及取得的研究成果 尽我所知，赊了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表和撰写过 的研究成果，也不包含为获得国防科学技术大学或其它教育机构的学位或证书而使用过的材 料与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢 意 学位论文题目：重囱丞廑搀塑盘型丛迟剑盟国逸堕鸯 学位论文作者签名：盟丝 日期：2 0 0 6 年l o 月1 6 日 学位论文版权使用授权书 本人完金了解国防科学技术大学有关保留使用学位论文的规定本人授权国防科学技 术大学可以保留并向国家有关部门或机构送交论文的复印件和电子文档，允许论文被查阅和 借阅；可以将学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或 扫描等复制手段保存汇编学位论文 ( 保密学位论文在解密后适用本授权书) 学位论文题日：重自翌廑握塑垒蒸挂迟型鲤冒焦堕酲 学位论文作者签名：i 坌叁望 日期：2 0 0 6 年1 0 月1 6 日 懒删擀：妄糌 国防科学技术大学研究生院博士学位论文 第一章绪论 1 1 课题的背景与研究意义 人类每时每刻都要接触图像，图像是人类认识世界的重要信息来源。在国民经济和国防 建设中发挥着非常重要的作用。实际应用中仅仅依靠单幅图像的信息不足以用来对目标或场 景进行正确的检测、分析和理解，而利用多幄图像的信息，并使不同形式的信息相互补充， 是可能获得目标或者场景的更为客观本质认识的重要途径之一。然而在进行多图像分析时首 先要考虑图像之间的对应关系。对同一场景采用不同时间、不同视点的同类型传感器或者不 同传感器成像，所获得的多幅图像之间会存在因成像条件不同引起的畸变，分析多图像间的 对应关系就是为了消除或减少这些畸变，为其后的识别、定位和差异分析提供准确信息，这 就是图像匹配闯题i i j 。 图像匹配是所有需要综合不同的数据源来获得最终信息的图像分析任务中最关键的中 间处理过程，已广泛应用于遥感数据处理、医学图像处理、模式识别与计算机视觉等诸多领 域。图像匹配问题有一套统一的处理框架和思路，但每一类具体的图像匹配问题又都有其特 殊的处理方法【2 1 。本文主要研究了面向深度提取的立体匹配技术和面向形状识别的模型匹配 技术。 目标三维信息特别是深度信息的获取是计算机视觉系统必须要解决的重要问题之一。目 标在二维成像过程中丢失了深度和其他一些信息，但目标在不同视点下的多成像中包含了它 的三维信息。通常可以通过分析双视点的立体图像之问的对应关系，利用立体匹配技术得到 目标的三维信息。 形状识别属于图像理解的高层分析，一般是基于目标或者景物模型来进行的。目标模型 可以分为基于图像特征、基于空间几何参数和基于知识的三大类，不同的内部模型对应的方 法和效果亦有较大的区别，但不论何种模型，都需通过模型匹配实现图像与内部模型的匹配、 比较，从而达到识别和分类的目的。 1 1 1 面向深度提取的立体匹配 人们生活和工作在三维几何空间中，对外界的感性认识首先是各种三维目标的形体，三 维深度信息的获取是人类活动中最重要也是最基本的信息处理内容。根据光源的不同，可将 深度图像数据生成分为主动和被动两种方式p 】。主动方式需要特别的光源提供的结构信息， 如雷达成像、结构光成像、全息干涉成像、核磁共振成像等，具有精度高、抗干扰性能好和 实时性强等特点，但系统价格非常昂贵，不适宜推广 4 1 被动方式的深度获取是在自然光照 条件下完成的，具有隐蔽性好、测量快速等优点。双目立体视觉技术是被动测距方式之一， 该技术模仿生物视觉机能，利用两幅图像建立目标的空间形状和位置，目前已广泛应用于机 第1 页 国防科学技术大学研究生院博士学位论文 器人导航、测绘、医学成像、军事和工业检测等领域，在机器人、虚拟现实( v r ，v i r t u a lr e a l i t y ) 、 摄影测量等技术当中都具有不可替代的作用。图1 1 给出了由立体视觉系统获得的双目图像 求深度数据的系统框图，从中可以看出，立体匹配是其中最关键也是最主要的步骤。 图i 1从双耳国像获得深度数据的系统框图 立体匹配是计算机立体视觉中最重要也是最困难的问题，当空间三维场景被投影为二维 图像时，同一场景在不同视点下的成像会有很大不同，而且场景中的诸多因素( 如光照背景、 几何形状、环境特征、噪声干扰等) 最终都以像素灰度值的形式反映出来。因此，要准确的 对包含了如此之多不利因素的图像进行无歧义匹配，难度是非常大的。在处理过程中，既涉 及到图像校正、图像增强、噪声抑制等预处理，又涉及到图像特征提取、特征描述等中层处 理过程，还要涉及到高层匹配、优化处理等方法，所以对立体匹配的研究具有非常重要的理 论意义，同时也具有非常重要的实践意义。 1 1 2 面向形状识别的模型匹配 在计算机视觉领域，形状识别有着重要的理论意义和广泛的应用价值。许多目标和符号 都可以用二维图形来表示，如染色体，文字、地图、各种商标牌照以及遥感图像中的形状等； 也有很多三维目标，如某些空间飞行器、工业零件、生产工具、生活用品等，它们的3 d 外 表面可由一个二维平面集合或其二维形状参数集合来近似表述。 模型匹配是最重要的形状识别方法之一，由于其实现的简单性而广泛的应用于数字识别 【5 】、汉字识别【6 】、人脸识别【7 小1 、指纹识别“2 。1 4 1 、机器视觉等领域当中。模型匹配需先建立待 识别的目标特性模型，然后考虑所以可能的变化，将待识别图像与己知模型相比较，从而得 出二者之阃的相似性度量，以此来对目标进行识别和分类。不同的目标模型表达方式的匹配 算法也各不相同：对简单的模板数据的匹配采用模板匹配法，它的特点是输入图像与目标模 型均是二维数组，适合成像视角变化较小的规则形状的识别，如阿拉伯数字、指纹、车牌等 的识别：当输入仍为二维图像。但模型采用几何参数或数学公式时，则需从图像中找出合适 的特征点使之与模型的参数或数学公式所表达的几何特性一致，该方法适合成像视角变化较 大的不规则形状的识别，如复杂平面多边形，复杂工件等的识别。在实际应用中，由于受噪 声、目标运动及成像设备的限制，使得模型和需要匹配的图像之间存在一定的灰度失真和几 第2 页 国防科学技术大学研究生院博士学位论文 何形变，所以针对不同的成像条件和应用需求，研究具有良好抗噪及抗几何形变能力、计算 量较少、便于处理的模型匹配算法具有重要的理论和应用价值。 1 2 1 立体匹配研究现状 1 2 国内外研究现状 1 2 1 1 发展历史 立体匹配的研究始于二十世纪七十年代中期，以m a r r 和p o g g i o t l 习等人为代表的一些研 究者提出了一整套视觉计算的理论来描述视觉过程，其核心是从图像恢复目标的三维形状 【1 6 1 。b a m a r d 和f i s c h l c r t l 刀总结了1 9 8 1 年以前的立体匹配研究，主要集中在立体重建的基本 原理，评估标准和当时比较流行的方法。 整个8 0 年代，立体匹配成为计算机视觉的研究焦点之一。d h o n d 和a g g a r w a l 【1 8 1 总结了 8 0 年代立体匹配的进步，包括大量的新匹配方法，层次处理观念的引进，以及利用三目约束 来降低立体匹配的模糊性。到了九十年代早期，立体匹配在各方面都逐步成熟起来，尽管通 用的立体匹配算法的研究仍在继续，但很多研究者在这时把目光转向立体匹配在特定问题中 的应用，如摄影测量，三维重建，基于图像的绘制技术( i b r ，i m a g e - b a s e dr e n d i n g ) ，虚 拟现实( v r ，v i r t u a lr e a l i t y ) 等。 k o s c h a n 1 9 】总结了1 9 8 9 到1 9 9 3 年立体匹配技术的发展，包括对遮挡的早期研究，主动 和动态立体匹配，以及实现的实时性问题。这些方面的研究在过去十年中都取得了很多成果， 现在立体匹配又有了新的发展势头，取得了重大发展，包括基于区域和基于特征匹配的新方 法，处理遮挡问题的方法，多相机立体匹配以及实时实现等。 m y r o n z b r o w n 等【2 0 】总结了1 9 9 3 到2 0 0 3 年期间立体匹配技术的进展，着重于遮挡处理 和实时系统。2 0 0 2 年，s c h a r s t e i n 和s z e l i s k i l 2 1 】将立体匹配过程分为四个模块一相似性测度 计算、支撑选择、视差计算( 最优化) 及视差校正，而把当前的各种匹配算法归结为模块相 对变动的结果，这样就可以在充分了解变动因素的前提下，通过对各种算法之问的性能比较， 得出变动因素对算法性能产生的具体影响。 1 2 1 2 国内外研究机构和实时系统 国内外有很多政府机构、公司、大学、研究所正致力于立体匹配技术的研究，国外主要 有卡耐基梅隆大学的机器人技术研究所的视觉和自动化研究中心，英国哥伦比亚大学的智能 计算实验室成立的p o i n tg r e yr e s e a r c h ，由v a c l a vh l a v a c 领导的捷克技术大学的机器感知中 心研究小组，德国波恩大学的计算机视觉研究组，日本大阪大学自适应机械系统研究院、法 国国家信息与自动化研究所( i n a ) ；国内主要有浙江大学机械系统，东南大学电子工程 系，中国科技大学的自动化系、微软亚洲研究中心、清华大学的计算机科学系、国家8 6 3 计 划等。 第3 页 国防科学技术大学研究生院博士学位论文 近几年来，立体匹配的研究越来越受到重视，在几个著名的国际会议中都有立体匹配的 最新成果报道和专题交流，如国际计算机视觉会议( i c c v ，i n t e r n a t i o n a lc o n f e r e n c eo f c o m p u t e rv i s i o n ) 、国际模式识别会议( i c p r 。i n t e r n a t i o n a lc o n f e r e n c eo f p a t t e r nr e c o g n i t i o n ) 、 i e e e 协会举办的计算机视觉和模式识别会议( c v p r ，c o m p u t e rv i s i o n a n dp a t t e m r e c o g n i t i o n ) 等 近十年来，实时稠密立体匹配已经成为现实。但是在二十世纪九十年代期间，真正能够 实现实时处理的系统都需要像数字信号处理器( d s p ，d i g i t a ls i g n a lp r o c e s s o r s ) 或者可编程 门阵列( f p g a 。f i e l dp r o g r a m m a b l eg a t ea r r a y s ) 这样的专用硬件支持。从1 9 9 3 年到2 0 0 6 年期间，先后有f a u g e r a s 等1 ，n i s h i h a r a 2 3 1 ，m a t t h i e s 等，w o o d f i l l 和v o n h e r z e n 2 m ，k i m u r a 等1 2 6 l 。w a n g 等1 1 2 】，k a n a d e 等阻2 2 1 报道了基于专用硬件支持的立体视觉系统。 在本世纪初，随着计算机系统性能的不断提高，一些仅依赖于软件的实时系统开始出现， 如m u l l i g a n 等【2 9 1 在2 0 0 2 年提出的三目算法在单处理器的p c 机上可以达到每秒处理3 - 4 帧的 速度：h i r s c h m u l l e r 等 3 0 l 提出的变窗口立体匹配方法在p e n t i u mu4 5 0 m h z 上可以达到每秒计 算1 2 m 视差估计值的速度；p o i n tg r e yr e s e a r c h l 3 i j 的算法在2 8 g 的处理器上每秒可计算$ 0 m 的视差估计值。g o n g 和y a n g 3 2 j 于2 0 0 5 年提出的利用图结构硬件加速技术，d p 算法可以达 到每秒钟计算2 0 m 视差估计值的速度。 就目前的研究进展来看，立体实时系统的发展趋势有三个：一是处理速度越来越快，由 早期的每秒3 6 帧到后来的每秒3 0 帧，这为实际应用系统提供了更好的基础：二是中心处理 器从早期的专用处理器( 如d s p ，f p g a ) 向通用的c p u 芯片发展，这使得实时系统可以在 普通电脑上实现，扩大了应用范围；三是匹配方法由简单的互相关或绝对差等方法向复杂的 全局方法( 如d p ) 过渡，因此在保证效率的前提下得到的视差图质量在不断提高，以期满 足实际需求。 1 2 1 3 方法分类 立体匹配方法的有效性依赖于三个问题的解决：选择正确的匹配基元、寻找特征之间的 本质属性及建立能正确匹配所选特征的稳定算法。围绕这三个问题，目前研究者已提出了大 量各具特色的匹配算法。从实现立体匹配的技术上考虑，这些算法可以分为局部算法和全局 算法两大类【2 0 1 ，表1 1 对对目前出现的主要方法及其代表文献进行了归纳 2 0 l 。 局部算法中，根据匹配基元的不同可分为基于区域的匹配 3 3 - 4 0 1 ( a r e a - b a s e dm a t c h i n g ) 、 基于梯度的优化方法( g r a d i e n t b a s e do p t i m i z a t i o n ) 【4 1 ，4 2 1 和特征匹配f l s 4 3 4 9 1 ( f e a t u r e m a t c h i n g ) 。其中基于区域的窗口匹配( 为方便起见，以后简称区域匹配) 和特征匹配是最 常见的两类方法。 区域匹配 区域匹配算法在局部小区域内寻找最佳视差使匹配误差最小，通常使用归一化互相关、 平方差和、归一化平方差和、绝对差和等测度作为匹配的相似性测量准则。区域匹配方法一 第4 页 国防科学技术大学研究生院博士学位论文 表1 1 立体匹配方法分类 主要参 方法名称方法描述 考文献 在一定区域搜索令窗口匹配值达到最大或匹配错 3 6 2 2 【3 7 局 块匹配 误达到最小的窗口位置 3 5 】 4 0 3 3 部 梯度优化 最小化某个函数，该函数表达了一定区域内图像梯 4 1 4 2 方 度与对应点灰度差之间的关系 法 5 0 4 4 1 8 特征匹配 匹配相互关联的特征而不是图像强度值本身 4 7 4 6 4 3 通过确定两列有序基元之间的最佳路径来确定扫 5 1 5 2 5 3 动态规划 描线上的视差分布。 5 铂 5 5 全 图割 通过确定图的最大流中的最小割来确定视差分布 2 1 5 6 5 7 局置信扩展 通过g r f 网络中的信息传递来确定视差分布 5 8 5 9 6 0 方 6 1 6 2 法 本质曲线 将扫描线转换到本征曲线空间后再作为最近邻域 6 3 6 4 搜索问题来解决 非线性扩散通过局部扩展来聚集支持区域 6 5 6 6 6 7 无对应方法根据目标函数来改变场景模型 6 8 6 9 7 0 般是根据图像的灰度信息和窗口的区域相似度进行匹配的，因此它对于图像的旋转、光强和 对比度的变化、仿射畸变和辐射畸变等变形非常敏感。区域匹配方法中窗口大小的选择也很 重要，窗口过大会导致在视差不连续处出现误匹配，窗口过小会使得区域内的灰度分布特性 得不到充分的体现。许多学者对此进行了研究，并提出了许多方法 3 3 3 5 3 1 , 1 0 7 1 - 7 2 “，其中比较 经典的是k a n a d e 和o k u t o m i 瞰】于1 9 9 4 年提出的通过测算局部灰度和视差变化来选取适当窗 口的方法。 特征匹配 利用图像中较为明显的特征进行匹配，特征匹配基元包含了令人满意的统计特性以及算 法编程上的灵活性。算法的许多约束条件均能清楚的应用于数据结构。目前常用的匹配基元 主要有点特征、线状特征和区域特征等。点特征是最基本、最简单的特征基元；区域基元具 有最好的全局属性；线状基元( 包括直线和曲线) 介于二者之间。一般来讲，点特征具有定 位准确、检测和描述容易以及重建精度高的优点，但它所含图像信息较少，在图像中的数目 较多，因而在匹配时需要较强的约束准则和匹配策略，以克服歧义匹配和提高运算效率。线 状基元和区域基元则含有更丰富的图像信息，在图像中的数目较少，易于实现快速匹配。但 它们在特征提取和描述时比较困难，需要进行复杂的顸处理，而且定位精度较差。但自1 9 9 9 年t a o 等1 7 4 利用线性方程来建模分割后所得区域内的视差与图像坐标之间的关系后，使得以 分割后的区域为基元的方法逐渐得以流行，如在2 0 0 2 到2 0 0 6 年之间，z h a n g 和k a m b h a m e t m 1 7 5 1 、h o n g 和c h e n l 4 9 1 、m e y e r 和g e l a u t z 邮r7 7 ) 、w e i 和q u a r t 5 0 1 、l e i 等u s 、k l a u s 等1 6 2 1 的算 第5 页 国防科学技术大学研究生院博士学位论文 法都以分割后的区域为基元进行匹配并取得了非常好的结果。 全局算法使用全局约