（电子科学与技术专业论文）基于特征点的立体匹配算法研究.pdf

摘要立体匹配就是对多幅图像中的对应点进行匹配，它是获得图像的深度信息最关键的步骤。立体匹配是计算机视觉领域中的一个重要研究方向，同时也是立体视觉中的一个瓶颈问题。研究一种鲁棒性好、精确度高、性能稳定和适用性强的立体匹配方法具有重要的理论意义和实用价值。本文作者对立体匹配中特征点的提取算法和特征描述子的生成方法做了较深入的理论研究和大量的实践工作。本文对h a r r i s 特征点提取算法进行改进，提出了一种精确度和实时性更优越的特征点提取算法，此算法首先对图像所有像素点进行一次简单的初始选择，排除一部分普通像素点，得到数量相对较少的候选角点集，后续的h a r r i s角点提取范围从整幅图像缩小为该候选角点集，从而降低了算法的时间复杂度。利用圆的旋转不变性，本文还对s i f t 特征描述子的生成方法进行了改进，该方法首先构造以特征点为中心的五个同心圆环，通过同一圆环内的所有像素点的八个方向梯度累加值排序生成的特征向量来表征特征点信息，这样生成的描述子本身就具备旋转不变性，特征向量维数的降低为后续的匹配节省了时间。最后将改进的算法分别引入到立体匹配中的特征提取和特征描述过程中，提出了一种基于h a r r i s 角点和s i f t 特征描述子的立体匹配算法。该算法首先采用改进的h a r r i s 角点提取算法对预处理后的图像对进行角点提取，然后用改进的方法生成特征描述子，再利用描述子间的相似性度量进行匹配并依据约束准则删除误匹配，得到匹配结果。实验结果证明该算法在实时性和准确性方面的性能都有较大提高。关键词立体匹配，特征点提取，s i f t 特征描述子，h a r r i s 角点 a bs t r a c ts t e r e om a t c h i n gi st om a t c ht h ec o r r e s p o n d i n gp o i n t si np i e c e so fd i f f e r e n ti m a g e s ，a n di t st h em o s tc r i t i c a ls t e po fo b t a i n i n gt h ed e p t hi n f o r m a t i o no ft h ei m a g e s i t sa ni m p o r t a n tr e s e a r c hd i r e c t i o ni nc o m p u t e rv i s i o nf i e l d a tt h es a m et i m e ，i t sb o t t l e n e c kp r o b l e mi nt h er e s e a r c ho fs t e r e ov i s i o n i t sag r e a tc h a l l e n g et oi n v e s t i g a t ear o b u s t ，p r e c i s e ，s t a b l ea n da p p l i c a b l es t e r e om a t c h i n ga l g o r i t h m ，w h i c hi sb o t ht h e o r e t i c a l l ya n dp r a c t i c a l l yv a l u a b l e t h i sp a p e rf i n i s h e dd e e pt h e o r e t i cr e s e a r c ha n ds u f f i c i e n tp r a c t i c a lw o r ko nf e a t u r ep o i n te x t r a c t i o na l g o r i t h ma n dt h em e t h o dh o wt os t r u c t u r ef e a t u r ed e s c r i p t o rf o rs t e r e om a t c h i n g t h i sp a p e ri m p r o v e dt h eh a r r i sf e a t u r ep o i n te x t r a c t i o na l g o r i t h m ，w h i c hp r e s e n t e dan e wf e a t u r ep o i n te x t r a c t i o na l g o r i t h m i no r d e rt oo b t a i nar e l a t i v e l ys m a l la m o u n to fc o m e rp o i n t s ，t h i sa l g o r i t h mm a k e sa ni n i t i a ls e l e c t i o nf o ra l lp i x e l so ft h ei m a g e s ，a n dr e m o v e sap a r to fo r d i n a r yp i x e lf i r s t l y i nt h i sw a y , t h er a n g eo fe x t r a c t i o no fh a r r i sc o r np o i n t si sr e d u c e d ，s ot h et i m ec o m p l e x i t yo ft h ea l g o r i t h mi sr e d u c e d w h i c hi m p r o v e sa c c u r a c ya n dr e a lt i m eo ft h ea l g o r i t h m b yu s i n gt h er o t a t i o n a li n v a r i a n c eo ft h ec i r c l e ，g e n e r a t i o nm e t h o do ft h es i f tf e a t u r ed e s c r i p t o ri si m p r o v e d f i r s t l y , t h i sm e t h o ds t r u c t u r e sf i v ec i r c l ea r e a s ，a n de a c hc e n t e ri sf e a t u r ep o i n t t h e n ，c h a r a c t e r i z a t i o no ff e a t u r ep o i n t si n f o r m a t i o nw i t he i g e n v e c t o r si sg e n e r a t e db ya c c u m u l a t et h eg r a d i e n t so fe i g h td i r e c t i o n sf o ra l lp i x e l si nt h es a m ec i r c l e 1 1 1 ed e s c r i p t o rg e n e r a t e db yt h i sw a yh a sr o t a t i o n a li n v a r i a n c ei n t r i n s i c a l l y i na d d i t i o n i ti su s e f u lf o rt h ec o n s e c u t i v em a t c h i n gt or e d u c et h ed i m e n s i o no ft h ee i g e n v e c t o r s t h el a s t as t e r e om a t c h i n ga l g o r i t h mt h a ti se m b e d d e di ni m p r o v e da l g o r i t h mi sb a s eo nh a r r i sc o m e ra n ds i f tf e a t u r ed e s c r i p t o rf i r s t l y , t h ea l g o r i t h me x t r a c t st h ec o m e rp o i n t sw i t hi m p r o v e dh a r r i sc o m e rd e t e c t i o no p e r a t o r , t h e ni tg e n e r a t e st h ef e a t u r ed e s c r i p t o r s ，a tl a s t ，i tm a t c h e st of e a t u r ep o i n t sb yu s i n gt h es i m i l a r i t i e so fd e s c r i p t o r s ，a n df a l s em a t c h e sa r er e m o v e da c c o r d i n gt ot h ec o n s t r a i n tc r i t e r i a t h ee x p e r i m e n t a lr e s u l t sa r ep r o v e dt h a tt h ea l g o r i t h mp r e s e n t e di nt h i sp a p e rc a ni m p r o v et h ea c c u r a c ya n d r e a lt i m e k e y w o r d s s t e r e om a t c h i n g ，f e a t u r ep o i n te x t r a c t i o n ，s i f tf e a t u r e d e s c r i p t o r , h a r r i sc o m e r i i i 目录摘要ia b s t r a c t i i第一章绪论11 。1 课题背景及研究意义11 2 立体匹配算法的研究现状21 3 论文的主要研究内容及结构5第二章立体匹配基本理论，72 1 引言72 2 立体匹配的原理与流程72 2 1 立体匹配的原理72 2 2 立体匹配的流程92 3 立体匹配的研究内容92 3 1 立体匹配的基本约束1 02 。3 2 特征空间1 12 3 - 3 搜索空间1 22 3 4 搜索策略1 22 3 5 相似性度量132 4 本章小结1 4第三章特征点提取算法研究及改进1 53 1 引言l53 2 基于灰度的特征点提取算法1 53 2 1m o r a v a c e 算子1 63 2 2f o r s t n e r 算子173 2 3h a r r i s 算子183 2 4s u s a n 算子1 93 2 5 几种算子的性能评价2 13 3 改进的特征点提取算法2 53 4 本章小结2 8第四章局部特征描述子研究及改进2 94 1 引言2 94 2 常见的局部特征描述子2 9i v 4 2 1s i f t 特征描述子3 0 4 2 2p c a s i f t 特征描述子3 2 4 2 3g l o h 特征描述子3 3 4 2 4 几种特征描述子的性能评价3 3 4 3 改进的s i f t 特征描述子3 4 4 4 本章小结3 5 第五章立体匹配算法研究及改进3 6 5 1 经典的特征匹配算法3 6 5 1 1 经典的基于h a r r i s 角点的特征匹配算法3 6 5 1 2s i f t 特征匹配算法3 6 5 2 基于h a r r i s 角点和s i f t 特征描述子的立体匹配算法4 0 5 2 1 基于h a r r i s 角点和s i f t 特征描述子的立体匹配算法原理4 0 5 2 2 基于h a r r i s 角点和s i f t 特征描述子的立体匹配算法实现4 1 5 3 实验结果与分析4 3 5 3 1 标准图像对的实验结果与分析4 3 5 3 2 采集图像对的实验结果与分析4 6 5 4 本章小结4 7 第六章总结与展望4 9 6 1 本文总结4 9 6 2 展望5 0 参考文献51 附录：部分算法源代码5 5 致谢6 1 攻读学位期间主要研究成果6 2 v 硕士学位论文第一章绪论1 1 课题背景及研究意义第一章绪论人类观察世界和认知世界的重要手段之一便是视觉，而人类对视觉的认识从感受上升到感知经历了一个漫长的过程。人类视觉系统通过感受光信号本身，或者在视觉信息的获取、传输、处理、存储以及理解的过程中有效获取信息【1 】，其中从外界获取的信息量占人类信息获取总量的8 0 ，这说明人类通过视觉获取的信息量是非常大的，同时也说明了这些视觉信息被人类充分的利用到了实践活动中。人类利用视觉的最终目标是要使观察者能对一定场景得出有特定意义的诠释和描述，广义的说，是要在这些诠释和描述的基础上，结合实际的客观场景和观察者的主观意愿来规划行为【2 j 。让计算机模拟生物视觉观察和理解世界的功能，使其具有自主适应环境的能力是人类多年的夙愿，计算机视觉技术正是在这种需求下于二十世纪六十年代中期由“积木世界”的研究而开启 3 1 ，随后对计算机视觉的研究不断深入和拓展，研究成果也是发生了质的飞跃，对图像的分析从二维平面发展到三维空间，在这种背景下，立体匹配技术逐渐形成并迅速发展成为一门新学科。到了七十年代，m a r t 等人从信息处理的角度创造性的提出了第一个比较完善的视觉系统框架，m a r r 的理论框架主要由视觉建立、保持并予以解释的三级表象结构组成，它们分别是基元图、2 5 维图、三维模型，如图1 1 所示。第一阶段第二阶段第三阶段图1 - 1m a r r 理论框架三个阶段在m a r r 理论框架下，视觉信息被分为低、中、高层视觉三个阶段【4 】，低层视觉主要负责表达原始图像中包含重要信息的区域及其几何分布和组织结构；中层视觉的任务则是结合低层视觉得到的简图和输入图像得到2 5 维简图；而高层视觉则是结合低、中层视觉得到简图以及输入图像使物体得到三维表示。m a r t视觉理论的提出将立体匹配技术带上了历史舞台，在此后的几十年里，对立体匹配技术的研究越来越深入，其应用也是越来越广泛。立体匹配已经在军事、航天、医学、现代工业等领域得到广泛应用并具有非常好的发展前景【5 j 。随着摄像机的 硕士学位论文 第一章绪论 普及，在普通摄像机成像条件下实现现场勘测等领域的应用逐渐成为研究热点。 立体匹配作为三维重建中最重要的部分在三维空间研究领域也发挥着不可或缺 的作用【6 j 。 立体匹配发展至今已经有了一系列成果，但当前立体匹配研究仍有一些有待 解决的问题。比如说场景的遮挡问题、视差不连续问题、由于光照等客观因素引 起的匹配问题【7 1 。另外立体匹配算法的精度和实时性是一对难以解决的问题，精 度较高的算法处理时间往往比较长，硬件实现比较难；而实时性较高的算法往往 精度就较低，容易产生误匹配，影响匹配的效果。所以如何合理的权衡两者的矛 盾，得到能满足实际需要而又更加优化的匹配算法，也是对立体匹配算法进一步 研究的方面。 1 2 立体匹配算法的研究现状 立体视觉就是模拟人类视觉处理景物的方式，通过对所选特征进行计算，建 立特征之间的对应关系，将空间中景物的具体物理点在不同的图像中的映像点一 一对应起来，恢复景物的三维信息【8 】。而在立体视觉中要获得图像的深度信息最 关键的步骤当属对多幅图像中的对应点进行匹配，也就是立体视觉匹配的问题， 简称立体匹配。立体匹配算法是立体视觉系统的关键，它主要是完成在不同观察 角度下的同一空间物理点在投影图像中的对应关系这一过程。立体匹配是三维重 建等后续操作的基础，匹配的结果直接关系到三维重建的效果，所以对立体匹配 技术的研究是非常重要的。 立体匹配的实质就是利用匹配基元之间的相似性，运用相应的匹配准则进行 最佳搜索的问题。那么数学中的许多最优化技术也就能在立体匹配中得到应用。 由于对人类视觉的工作机理缺乏研究，现阶段的立体匹配还缺乏统一的认识和完 整的体系框架【9 】，很多研究人员为了完善这个不足做了大量的工作。立体匹配算 法采取怎样的匹配策略在很大程度上依赖于匹配基元的选取。目前，立体匹配算 法包括区域匹配算法、特征匹配算法和相位匹配算法u0 1 。划分这三类匹配算法 的主要依据是匹配基元的不同，匹配基元的稳定性、致密性以及奇异性程度直接 决定了各类算法的基本性能，匹配基元的不同决定了判断对应点是否匹配的理论 依据也有所不同。 ( 1 ) 区域匹配算法。基于区域的匹配算法的中心思想是：以匹配图像对中原 匹配图像中的某一给定待匹配点为中心创建一个大小合适的窗口，该像素点的信 息利用邻域相关的思想用窗口内其邻域其他像素点的灰度值分布来表征，然后在 硕士学位论文 第一章绪论 待匹配图像中依据约束准则顺次搜索这样一个像素点，按照同样的方法创建窗口 以及表征其信息，接下来选择一个合适的相似性测度函数，并确定对应匹配点之 间相似性所需满足的阈值条件，以此来度量两个窗口内像素点的灰度值分布相似 性。算法的性能很大程度上取决于算法所选用的相似性度量和搜索策略。相似性 度量用得比较多的是频域相关算法、归一化相关算法以及基于主成份分析的方 法，常用的搜索策略有贯序相似性检测算法、多子域相关匹配算法等。 z h a n g t i a n x u 等提出了直接以原匹配图像与待匹配图像窗口之间的灰度相似性作 为两者相关性的衡量【l ，该算法虽然简单，但对图像灰度的变化敏感，而且阈值 的选取比较困难。归一化积相关算法也是用得比较多的相似性度量，它将模板和 待匹配图像在各个区域的相关系数最大的点作为最佳匹配点，该算法虽然抗白噪 声干扰能力强，还不受比例因子影响，但其计算复杂度相当大，实际硬件实现比 较难。b a m e a 等提出了一种在利用排除法剔除不匹配点的同时寻找最佳匹配的算 法【l2 | ，该算法先迅速剔除不匹配点，从而减少了在不匹配点上不必要的计算量， 其匹配速度因此提高很多。 基于区域的匹配算法能得到较高的定位精度和致密的视差图。但此类算法对 图像间的细微差别很敏感，也就是对图像灰度的统计特征过于依赖，对仿射畸变 以及辐射畸变较敏感以至于可能因为光照反射、景物结构等因素引起的一个微小 的变化导致匹配失败【l3 1 ，所以此类算法只适用于对具有相同外界条件的两幅图 像进行精细匹配，而在空间景物表面缺乏足够纹理细节、成像失真比较大的匹配 时存在一定的困难；另外算法的性能很大程度上依赖于合适大小窗口的选取，而 选取窗口大小没有具体标准，这样就无法准确估计出算法的计算量，此外，此类 算法对与除有限窗口外的其他匹配算法是不适用的；因为此类算法的计算复杂度 比较大，很难满足实时性要求比较高的应用场合。 ( 2 ) 特征匹配算法。基于特征的匹配算法的中心思想是：通过特征提取算法 对两幅或者多幅图像进行特征提取，接下来对提取到的特征进行参数描述，然后 选用恰当的搜索策略，采用合适的相似性度量将描述的参数与预设的阈值相比较 完成匹配。z z h a n g 等提出了一种利用极线约束对采用互相关获得的初始匹配进 行改进的算法【l4 1 ，但算法的互相关函数容易受噪声和像素点定位偏差的影响。 z h e n g 在提取特征点阶段引入了g a b o r 小波模型【l 引，先利用少量稳定特征点对平 移等参数进行估计，然后采用分层的方法获得精确的外参数。v m c e n tt 提出的 算法引入了h a r r i s 角点、方差归一化相关以及极线约束【l6 。，提高了匹配精度。 实际研究的特征一般有点、线以及面特征等。基于特征的匹配一般分为特征 提取和定位、特征描述、特征匹配三个阶段。特征点的提取和定位过程相当重要， 它直接影响匹配结果的精确度。由于特征匹配不直接依赖与灰度，特征对图像的 硕士学位论文第一章绪论几何形变也不太敏感，而且图像的特征相对来说是比较稀少的，所以匹配算法一般具有较强的抗干扰性，而且算法复杂度小，便于快速实现，特别是在处理视差不连续区域的匹配问题时，特征匹配有着不可替代的作用。但是由于特征点的相对稀少，使得特征匹配只能得到稀疏的视差图，要想得到致密的视差图，就必须进行非常复杂的插值过程h 。( 3 ) 相位匹配算法。相位匹配相对( 1 ) ( 2 ) 两种匹配方法来说，出现的比较晚。从生理学的角度出发，r o b s o n 证明了人类视觉系统中的简单视觉细胞在相位关系上是以正交的形式成对出现的【l8 1 ，其可以用两个实部与虚部互相正交的复数滤波器来模拟。j u l e s z 等人也指出相位信息也许是立体匹配中最理想的一种匹配基元形式【l 纠。相位信息作为匹配基元的重要性被慢慢发掘，研究人员发现v 2 g 零交叉、卷积峰匹配基元等都与特定的相位值相对应【20 | ，相位信息比幅度信息包含更多的图像信息，并且图像的结构信息取决于频率相位信息。基于g a b o r 滤波相位的双面视觉系统就是基于这些信息而提出来的。f l e e t 等人详细研究了基于相位的立体匹配算法 2 1 , 2 2 】，他对j s p s o r t h i 对于检测相位奇点给与了有效的办法，还利用邻域的视差在奇点处进行填补；w e n g 对采用短时f o u r i e r 变换相位的图像匹配【2 3 】；m a i m o n e 提出的隐含投票策略的相似性测度函数能实现对滤波器的自适应选择【2 4 1 。基于相位的立体匹配技术在国内也有一定发展。中科院的杜利民等人对g a b o r 滤波器组的波长采用低冗余度的质数序列瞄j ，很大程度上提高了计算速度。清华大学的柳建等利用h a r d y 小波基函数将图像对表示成正交带通分量，其具有良好的频域定位性，其相位信息作为匹配基元实现了视差估计的问题向小波相位差估计问题的转化【2 6 】。立体匹配算法在国外起步比较早，d a n i e ls c h a r s t e i n 和r i c h a r ds z e l i s k i 于2 0 0 1 年系统的分析了常见匹配算法的种类，对立体匹配算法的评价方法和理论框架进行了总结，这些工作能有效的知道后来的研究1 2 列；剑桥大学的v l a d i m i rk o l m o g o r o v 在图割的匹配算法的基础上从匹配的精度和速度出发提出了一种最小割算法，这种算法运行效率比较高；美国的m i d d l e b u r y 学院建立了立体匹配研究平台，提供经极线校正后的图片库，提供各种立体匹配算法的评价对比；在美国k e n u c k y 的大学l i a n gw a n g 等人从图割匹配算法的实时性出发提出了一种具有更高实时性的匹配算法，这种算法的实时性体现在融合了硬件的加速、自适应的代价叠加以及采用了动态规划法【2 引。国内研究立体匹配的人员也提出了一些比较好的匹配算法。上海交通大学的徐奕等人提出了一种能有效处理奇点和遮挡检测问题的相位匹配算法【2 9 1 ，该算法是基于动态规划的：安徽大学的鲍文霞等提出了一种基于图割理论和极几何约束的匹配算法【3 0 】；中国科技大学的郁理等人基于分级置信度的思想对立体匹配 硕士学位论文第一章绪论算法进行了改进【3 。立体匹配算法依据匹配策略的不同又可以分为全局匹配算法和局部匹配算法，全局匹配算法是对扫描线或者整幅图像进行约束来寻求最优化匹配结果的算法，局部匹配算法则是只对像素点周围的局部区域进行约束来寻求最优化匹配结果的算法。可以将局部匹配看成是全局匹配将约束范围从全局缩小到某个局部的特例。全局匹配算法能很好的解决稀疏纹理和遮挡等问题，而且能得到精度比较高的匹配结果，但其算法的执行时间复杂度非常高；局部匹配算法与全局匹配算法相比则正好相反，它具有较低的算法执行时间复杂度，但其匹配结果的精度却达不到很高的要求。因此，寻找一种既有较高的匹配精度又能够快速实现的匹配算法是研究人员进一步研究所要努力的方向。1 3 论文的主要研究内容及结构立体匹配的首要的问题就是特征点提取和特征描述子的生成，本文主要围绕这两个问题展开研究。首先在研究传统特征点提取算法和特征描述子的基础上，提出了改进的特征点提取算法和特征描述子的生成算法，根据双目立体视觉系统拍摄到的图像对之间只存在很小的尺度变化和较小的旋转变化的特点，结合改进的特征点提取算法和特征描述子，并利用双向匹配的策略，对图像对进行匹配。最后从标准图像对和采集图像对两个方面对经典的匹配算法和本文算法进行比较分析，并给出合理的评价。本文的章节具体安排如下：第一章绪论。首先介绍了本文所研究的课题的背景和研究意义；接着介绍了目前立体匹配算法的研究现状，着重介绍了立体匹配算法中的区域、特征以及相位匹配算法的研究现状，为本文的研究奠定了理论基础。第二章立体匹配基本理论。立体匹配基本理论首先从立体匹配模型出发引出立体匹配的原理，按照立体匹配的原理得到其一般流程，针对立体匹配过程中涉及到的一些问题，重点介绍了基本约束、特征空间、搜索空间、搜索策略以及相似性度量，为立体匹配算法的后续研究打下了坚实的理论基础。第三章特征点提取算法研究及改进。本章首先概括的介绍了基于灰度的、基于模板的和基于边缘的特征点提取算法，重点介绍了基于灰度的特征点提取算法，并通过比较分析实验结果，对几种经典的特征点提取算法的性能进行了评价和总结。针对h a r r i s 特征点提取算法复杂度高、角点定位不精准的问题，引入非角点剔除函数，提出了一种改进的基于h a r r i s 的特征点提取算法，这种算法在进行h a r r i s 角点提取之前，先对整幅图像的像素点进行一次初始选择，剔除一部分 硕士学位论文第一章绪论非角点，因此，在进行h a r r i s 角点提取的时候就不用对整幅图像的所有像素点进行角点响应函数的计算，能有效的减小算法复杂度；算法在进行角点初始选择时，对选取的角点进行了条件限定，避免了邻近像素点的影响，提高了角点的定位精度。最后通过对比实验结果验证了算法的有效性。第四章局部特征描述子研究及改进。首先概括性的介绍了基于分布的、基于空频转换技术的和基于差分的特征描述子以及其他类型的特征描述子，重点介绍了基于分布的特征描述子，并通过实验数据，对几种经典的特征描述子的性能给出了合理的评价和总结。在此基础上，利用圆的旋转不变性，对s i f t 特征描述子的生成算法进行了改进，降低了特征向量的维数，有效的降低了后续的匹配的计算时间，最后对改进的特征描述子的性能给出了合理的评价。第五章立体匹配算法研究及改进。首先介绍了经典的基于h a r r i s 角点的特征匹配算法和s i f t 特征匹配算法；针对立体双目视觉系统拍摄到的图像对的实际特点提出一种基于h a r r i s 角点和s i f t 特征描述子的立体匹配算法，该匹配算法有效结合了改进的h a r r i s 角点提取算法和s i f t 特征描述子能有效降低匹配算法处理时间方面的优点，使得匹配算法在保持一定精度的情况下，提高了实时性；最后对经典的基于h a r r i s 角点的特征匹配算法、s i f t 特征匹配算法以及本文算法在v c 平台上进行了仿真，根据实验结果对其进行了分析和性能评价。第六章总结与展望。对本文内容和所做的工作进行了总结，对本文算法的优缺点进行了分析，为今后的研究工作指明了方向。 硕士学位论文第二章立体匹配基本理论 2 1 引言 第二章立体匹配基本理论 立体视觉主要研究如何借助多图像成像技术从多幅图像中获取场景中物体 的深度信息，早在2 0 世纪6 0 年代中期，r o b e r t s 就进行了开创性的工作。立体 视觉的基本方法是从两个或者多个视点去观察同一场景，获得在不同视角下的一 组图像，然后通过三角测量原理获得不同图像中对应像素间的视差，即同一个 3 d 点投影到两幅2 d 图像上时，两个对应点在图像上的差，从中获得深度信息， 并进而计算场景中目标的形状和它们之间的空间位置等【3 2 1 。立体视觉的工作过 程与人类视觉系统的感知过程有许多相似之处，事实上，人类视觉系统就是一个 天然的立体视觉系统。 作为计算机视觉领域中的一个基础性课题，立体匹配得到了广泛的应用。立 体匹配可定义为在同一摄像机在不同角度或者不同角度的多台摄像机对同一个 景物采集的多幅投影图像中各像素点之间建立对应关系。由于拍摄角度的不同， 投影图像之间也有比较大的差异，噪声干扰以及光照变化等因素更是加大了立体 匹配的实现准确性的难度【3 引。目前，立体匹配的研究正朝着以下三个方向努力： ( 1 ) 建立一种通用的人类视觉计算模型。但至今仍未出现一种视觉模型完全 类似于人类的视觉，因此这方面的工作还有待进一步的去研究和完善。 ( 2 ) 建立一种实用的立体视觉系统。这种系统具有很强的实用性，它可以根 据不同的实际需要而适用于不同的领域。 ( 3 ) 解决立体视觉中存在的诸多问题。比如说对于复杂的场景，如何提高匹 配准确率和提高匹配算法的稳定性，以及如何权衡匹配准确性和实时性的要求， 使它们达到平衡等问题都亟待深入的探索。 2 2 立体匹配的原理与流程 2 2 1 立体匹配的原理 双目立体视觉进行三维信息的恢复和重建是基于两幅图像的视差值，根据投 影几何三角法原理来进行的，即由两个摄像机的图像平面和被测物体之间构成的 一个_ 角n t 3 4 1 。所采用的图像是由摄像机对同一场景从两个或多个角度获取的 7 硕士学位论文第二章立体匹配基本理论两幅图像或多幅图像，通过透视投影关系可以确定多个成像之间的点的几何约束关系，然后根据像素点之间的相似性来计算求解像素点的视差值，最后通过透视模型进行逆映射变换，得到场景中每一个空间点的三维空间信息。立体匹配的最终目的就是要通过图像处理方法和最优化理论的知识，得到像素点的视差值。图2 1 为简单的平行双目立体成像原理图。图2 - 1 平行双目立体成像原理图两摄像机的投影中心连线的距离，即基线距离为b ，两摄像机在同一时刻观察空间物体的同一特征点e ( x 。，y 。，z 。) ，分别在左图像和右图像上获取了点p 的图像，它们的图像坐标分别为异( x ，髟) ，p r ( x ，e ) 。假定两摄像机的图像在同一水平面上，则特征点尸的图像坐标的】，坐标相同，即z = r = y ，则由三角几何关系得到x l ：fx c x ，：厂鲣望( 2 1 )z c】，：f y c z 。视差为d = x ，一x ，。由此可以计算出特征点尸在摄像机坐标系下的三维坐标为：b x 。x = 一dy 。：掣( 2 - 2 )y c2 百b f。d因此，左摄像机像面上的任意一点只要能在右摄像机像面上找到对应的匹配 硕士学位论文第二章立体匹配基本理论 点，就可以确定出该点的三维坐标。这种方法是点对点的运算，图像上所有像素 点只要存在对应的匹配点就可以参与式( 2 1 ) 、( 2 1 ) 运算，从而获取对应的三维 坐标。 2 2 2 立体匹配的流程 立体匹配技术的发展经历了几十年，至今已经形成了多种各式各样的匹配算 法【3 5 。3 7 】。对于任何一种匹配算法，首先都必须选择正确的匹配特征，寻找特征之 间的本质属性，然后构建能够对所选特征建立起正确匹配的稳定算法。立体匹配 算法的系统流程如图2 2 所示。 蓄藿酬熟吲特征提取酬优化酬特征描述 选择 匹配基元 搜索 策略 立体匹配 算法 臀吲黑吲特征提取吲龇酬特征描述 匹配 结果 图2 - 2 立体匹配系统流程 立体匹配的一般流程为： ( 1 ) 对摄像机采集得到的图像对进行图像预处理，包括图像灰度化、滤波、 锐化等，这样可以将图像从2 4 位真彩转化为8 位的灰度图，便于后续处理，同 时预处理能够使噪声得到抑制； ( 2 ) 根据实际情况选择合适的匹配基元，根据选取的匹配基元确定恰当的算 法对图像的特征进行提取； ( 3 ) 对提取到的初始特征集合进行优化，可以剔除一部分特征不明显的点； ( 4 ) 对特征进行描述，生成能表征特征信息的特征描述子； ( 5 ) 选择合适的搜索策略寻求匹配结果的最优化，以相似性测度函数作为特 征间相似性的度量，通过设置阈值来判断匹配是否成功，利用立体视觉约束准则 对得到的匹配结果进行约束，剔除一部分误匹配，得到最终的匹配结果。 2 3 立体匹配的研究内容 虽然立体匹配算法的种类和数量都很多，但总结分析过去的这些算法可知， 硕士学位论文第二章立体匹配基本理论 无论什么算法，都需要考虑以下几个问题：约束准则【3 8 】；确定用来进行匹配所 用特征的特征空剐3 9 】；限制搜索范围，确定使搜索过程有可能有解的搜索空间； 对搜索空间进行扫描的搜索策略【4 0 】；用来确定匹配是否成立的相似测度函数。 2 3 1 立体匹配的基本约束 由于噪声、光照变化、遮挡和透视畸变等因素的影响，空间同一点投影到两 个摄像机的图像平面上形成的对应点的特征可能不同，对在一幅图像中的一个特 征点或者一小块子图像，在另一幅图像中可能存在好几个相似的候选匹配，因此， 需要另外的信息或者约束作为辅助判据，以便能得到唯一准确的匹配。我们可以 一般采用的约束有： 1 极线约束 图2 - 3 立体匹配中的极线约束 如图2 3 所示，和，分别为由左右摄像机获取的图像平面，异和p 分别为 空间同一点尸在，和，平面上的投影点，m ，和m ，分别为空间中的同一点m 在 ，和，平面上的投影点，尸与左摄像机光心q 的连线与右摄像机光心d ，构成平 面s ，s 与，相交于直线er 1 ，即只在，上的外极线。反之亦然，e 为只在，上 的外极线。同样m 与左摄像机光心q 的连线与右摄像机光心o r 构成平面q ，q 与，相交于直线e ，：，即m ，在，上的外极线，e ，则为m ，在，上的外极线。s 和 q 为极平面簇中的两个平面。外极线限定了立体图像对应点的位置，即与点p 在 ，上的投影点只所对应的，上的投影点一定在外极线e 。上，反之亦然。对于点m 也是如此。这样一来，就可以将待匹配点的搜索范围从二维降低到了一维，不但 提高了匹配的速度，也降低了误匹配率。 2 唯一性约束 在任何时刻，图像中的一个给定的三维空间点只占据空间中唯一的位置。因 此待匹配图像中的某个匹配基元只能与基准图像中的一个匹配基元相对应，反之 硕士学位论文第二章立体匹配基本理论 亦然。图像中的每个匹配基元就只会有一个视差值。 3 相容性约束 灰度相同或相似的图像点不一定就是相互对应的点，由于受到客观因素的影 响，图像中的对应点的亮度是相似而不是完全相同的。所以相容性是用来测度对 应点的一致性的。 4 视差连续性约束 物体的表面一般来说是光滑的，因此除遮挡或者间断区域外，空间中的物体 在某一成像平面的匹配点附近的视差变化在整幅图像中的点是连续或者平滑的。 5 顺序一致性约束 在视角变化不是很大的情况下，图像对中的对应点对在位置顺序上保持一致 性。 2 3 2 特征空间 特征空间的选择是立体匹配的首要问题，也就是选取哪一种特征来作为匹配 基元。图像的原始像素灰度值以及闭合曲线、轮廓、边缘点、角点、曲率局部极 大点等都是一些经常用到的特征。表2 1 列出一些常用的特征和相应的一些性质。 表2 - i 常用特征空间及其性质 图像原始灰度值最常用的图像信息 边缘特征 统计特征 高级特征 模型匹配 突出特征 图像内部结构且对噪声不敏感 ( 边缘、轮廓、表面) 利用图像所有信息，对刚体变换非常有用 ( 不变矩、质心主轴) 利用关系和其他高级信息，尤其适用于不精确的 局部匹配( 结构化特征、句法特征、语言网络) 精确的内部结构 ( 解剖地图集、地理图集、对象模型) 图像内部结构且可精确定位 ( 轮廓线局部曲率最大点、局部最大差异窗口中 心、闭合区域重心、直线交点、傅立叶描述子) 考虑到以下几个原因，特征空间的选择在立体匹配过程中显得至关重要。 ( 1 ) 特征空间的选择决定了图像中具体会用到哪种匹配基元进行匹配。 ( 2 ) 特征空间的选择决定了场景和传感器的哪些性质对匹配数据的影响最 硕士学位论文第二章立体匹配基本理论 大。 ( 3 ) 特征空间的选择直接影响整个立体匹配算法的计算复杂度，特征空间选 择得好就可以大大降低相似性度量的计算代价。 选择一个好的特征空间可以极大的改善和提高立体匹配算法的性能。特征空 间的选择原则可归结为：被选作匹配基元的特征是图像中那些可以精确表示场景 物理本质特征的像素点，这些特征点是不受关照变化等外界因素的影响的。 边缘、轮廓以及边界代表了图像中的绝大部分内部结构信息，所以它们经常 被用作特征空间。边缘作为匹配特征主要有两个好处：一是计算复杂度低，能实 现快速匹配；二是边缘对图像畸变具有很好的不变性。但对点匹配来说，边缘特 征对并不是很好的选择，因为边缘点的独特性和唯一性较差。 总而言之，特征空间的选择问题就是选取图像中的哪种匹配基元进行匹配的 问题。它决定了参与匹配的匹配基元种类，而怎样进行匹配就取决于相似性度量。 结合两者就可以在除去很多图像中可能会引起歧义匹配的异常的同时，优化图像 中重要特征的匹配。两者既有联系又有区别，在匹配开始之前特征空间就已经提 前计算好，而相似性度量要利用两幅图像的特征空间在匹配的过程中计算出来。 2 3 3 搜索空间 搜索空间取决于两幅图像之间相对位置的变化。如果从第一副图像只要通过 平移就可以变换到第二幅图像，那二维的搜索空间就已经足够了；而如果这种变 化是一般的仿射变换，那就必须增加搜索空间的维数。图像之间的几何变换包括 刚体变换、投影变换、仿射变换、非线性变换等，它们的确定就是搜索空间的确 定。刚体变换是指经过变换后第一幅图像中的两点之间的距离和第二幅图像中这 两点之间的距离相同，它可以分解为平移、反转和旋转；仿射变换和投影变换的 共同之处在于第一幅图像上的直线变换到第二幅图像后仍为直线，不同的是经过 仿射变换后的直线保持着平行关系，而经过仿射变换后的直线基本不保持平行关 系，另外，投影变换可以用高维空间上的线性变换来表示；非线性变换则可以将 直线变换成曲线。 2 3 4 搜索策略 搜索策略可以使图像之间经过变换后的相似性最大，它通过合适的搜索方法 在搜索空间中找出平移、旋转等变换参数的最优估计。选择合适的搜索策略引入 到立体匹配中可以限制解空间的大小，最大限度的减少匹配结果的歧义性，同时 可以极大的提高搜索速度，降低算法的时间复杂度。常用到的搜索策略有分层搜 硕士学位论文第二章立体匹配基本理论 索、松弛技术、模拟退火算法、遗传算法、动态规划法和神经网络等。表2 2 列 出了一些常用的搜索策略及其特点。 表2 - 2 常用搜索策略以其特点 搜索策略优点 决策序列 松弛算法 动态规划 线性规划 分层技术 树和图文匹配 广义h o u g h 变换 改善了刚体变换的相似性优化的计算计算效率 利用了特征的空域相关性，当存在局部畸变时，是寻找一个 全局变换的可行方法 当存在匹配的内部顺序时，对于寻找局部变换关系非常有效 对于存在多边形误差边界的点匹配，是一种非常有效的寻找 刚体变化的策略 通过将搜索过程渐进的变成分辨率由粗到精的过程，可以有 效的改善和加速搜索过程 通过树图的特性将搜索最小化，适用于高层次结构的粗糙匹 配 通过将边缘空间匹配到双重参数空间，非常适用于强制替换 轮廓的形状匹配 松弛技术是一种能适应不同的匹配基元的搜索策略，因此在立体匹配中应用 得比较多。松弛技术基于分级的思想，先采用相对比较简单的相似性度量获得初 始匹配，接下来对对应匹配基元利用立体视觉的约束准则，然后再采用松弛迭代 技术对初始匹配的结果进行优化，有效的降低了匹配结果的误匹配率。 分层匹配技术在立体匹配中也是一种有效的搜索策略，与松弛技术不同的是 它运用了分层的思想，模拟人