（计算机应用技术专业论文）一种基于图像分割的快速立体匹配算法.pdf

一 嬲煳必 学位论文的主要创新点 一、指明了立体视觉图像中能够用于区域匹配的四类特征信息。 二、根据上面的四类特征信息，制定了匹配区域的寻找规则，提 高了匹配区域的定位速度和精度。 摘要 立体匹配算法的有效性主要取决于三个方面，分别为匹配特性的正确性，特 征间的本质属性可靠性以及算法对所选特征点进行正确匹配的稳定性。根据匹配 策略的不同，现有的立体匹配算法可以分为局部立体匹配算法和全局立体匹配算 法两大类。局部立体匹配算法只利用匹配像素本身及邻域像素的特征对图像对中 的像素进行匹配，虽然能够取得较快的匹配速度，但是在遮挡，纹理单一等病态 区域的匹配效果很不理想。全局立体匹配算法在局部立体匹配算法的基础上增加 了全局一致性匹配因素，在一定程度上提高了匹配方法在病态区域的匹配性能， 但同时也增加了匹配的计算量，导致这种方法匹配速度慢，实时性差等缺点。 随着立体视觉技术在生产生活中的广泛应用，立体视觉对立体匹配的速度和 精度都提出了更高的要求。特别是在复杂场景中，如何降低实现的复杂程度和计 算量，以及提高算法的去歧义匹配和抗干扰能力，都需要进行更深入的研究。 基于图像分割的立体匹配方法首先将二维数字图像在灰度和空间两方面都 进行简化处理，然后对分割后的区域进行匹配。这种算法不仅能够大大减小了整 个图像的信息量，而且对于计算机视觉领域中缺失纹理区域的匹配这个的经典难 题的处理上能够取得较好结果。但是由于该算法使用的是全局的优化算法，在匹 配速度上达不到实时性要求。本文对立体视觉图像进行了深入研究，指出了能够 用于区域匹配的四类特征信息。在此基础上对图像分割后的区域信息在多个维度 上进行了重新组织，并制定了匹配区域的寻找规则，从而提高了匹配区域的查找 速度和精度。总体来看，本文提出的视差计算算法，执行速度快，计算精度较高， 可用于匹配精度和实时性要求较高的场合。 关键词：计算机视觉，立体匹配，视差图，图像分割 a b s t r a c t t h ec a p a c i t yo fs t e r e om a t c h i n ga l g o r i t h mm a i n l yd e p e n d so nt h ec o r r e c t n e s so f m a t c h i n gf e a t u r e s ，t h er e l i a b i l i t yo ff e a t u r e c h a r a c t e r i s t i c sa n dt h e s t a b i l i t yo f a l g o r i t h m t o c o r r e c t l y m a t c ht h es e l e c t e d f e a t u r e a c c o r d i n g t ot h es t e r e o c o r r e s p o n d e n c es t r a t e g y , s t e r e oc o r r e s p o n d e n c em e t h o d sc a nb ed i v i d e di n t ot w o c a t e g o r i e s ：t h e l o c a ls t e r e o c o r r e s p o n d e n c e m e t h o da n dt h e g l o b a l s t e r e o c o r r e s p o n d e n c em e t h o d l o c a ls t e r e oc o r r e s p o n d e n c em e t h o d ，r e f e rt ot h em e t h o do f o n l yu s i n gc o n s t r a i n t so nas m a l ln u m b e ro fp i x e l ss u r r o u n d i n gap i x e lo fi n t e r e s tt o m a k ec o r r e s p o n d e n c e ，a l t h o u g ha c h i e v ef a s t e rm a t c h i n gs p e e d ，b u tw o r kp o o r l yi n o c c l u d e da n dt e x t u r el e s sa r e a s g l o b a ls t e r e oc o r r e s p o n d e n c em e t h o dr e a c h e sab e t t e r c o r r e s p o n d e n c ep e r f o r m a n c eb ye x t e n d i n gt h el o c a ls t e r e oc o r r e s p o n d e n c em e t h o dt o s o m eg l o b a lc o n s t r a i n t sw i t i las u b s t a n t i a lc a l c u l a t i o ni n c r e a s i n g a st h es t e r e ov i s i o nt e c h n o l o g yi su s e di no u rn o r m a ll i f em o r ea n dm o r ew i d e l y h i g h e rr e q u i r e m e n t sh a v eb e e np u tf o r w a r do ns t e r e oc o r r e s p o n d e n c em e t h o d e s p e c i a l l yi nc o m p l e xs c e n e s ，h o wt or e a c hab e t t e rr e s u l t 嘶ml e s st i m ea n d i m p l e m e n t a t i o nc o m p l e x i t ys t i l ln e e dal o to fw o r k s t e r e o c o r r e s p o n d e n c e m e t h o db a s e do n i m a g es e g m e n t a t i o n f i r s tr e d u c e s i n f o r m a t i o no fi m a g ei nc o l o ra n ds p a c e ，a n dt h e nc o m p u t ed i s p a r i t yb yt h er e g i o n t h i sa l g o r i t h mc a na c h i e v eb e t t e rr e s u l t sa to c c l u d e da n dt e x t u r el e s sr e g i o n s h o w e v e r , a so t h e rg l o b a ls t e r e oc o r r e s p o n d e n c em e t h o d ，t h e s em e t h o d sc o u l dn o t m e e tr e a l - t i m er e q u i r e m e n t s t h i sp a p e ra n a l y s i st h es t e r e ov i s i o ni m a g ed e e p l y , a n d p o i n to u tf o u rk i n d so ff e a t u r et h a tc a nb eu s e di nf m d i n gm a t c h e dr e g i o n o nt h i s b a s i s ，o r g a n i z a t i o n sw e r ep m c e s s e do nt h er e s u l to ft h ei m a g es e g m e n t a t i o n ，a n dr u l e s t of i n dm a t c h e dr e g i o n sw e r ea l s om a d e a sr e s u l ts h o w s ，o u ra l g o r i t h ma c h i e v e da f a s t e ri m p l e m e n t a t i o ns p e e da n dh i g h e ra c c u r a c y k e y w o r d s ：c o m p u t a t i o n a ls t e r e o ，s t e r e oc o r r e s p o n d e n c e ，d i s p a r i t ys p a c ei m a g e ， i m a g es e g m e n t 目录 第一章绪论1 1 - l 课题的历史背景1 1 2 立体匹配技术国内外发展概况一2 1 2 1 国外立体匹配技术的发展。2 1 2 2 国内立体匹配技术的发展3 1 3 课题的研究内容及组织结构4 1 3 1 立体匹配算法的发展趋势和存在问题4 1 3 2 本文的组织结构4 第二章立体视觉基本理论7 2 1 立体视觉的理论基础7 2 2 立体视觉的不确定性。9 2 3 极线几何l o 2 3 1 极线几何基本原理1 0 2 3 2 基础矩阵求解1 l 2 3 3 极线校正1 2 2 4 立体视觉图像研究1 4 2 4 1 图像中的极线约束1 4 2 4 2 图像中水平扫描线方向长度的变化1 5 第三章图像分割算法研究17 3 1 图像分割模型1 7 3 2 常用的图像分割方法对比1 8 3 2 1 阈值法1 8 3 2 2 区域分割方法1 8 3 2 3 微分算子法1 9 3 2 4 边界曲线拟合的方法2 l 3 2 5 基于模糊集理论的方法2 l 3 3 分水岭图像分割算法2 2 3 3 1 分水岭算法定义2 2 3 3 2 分水岭算法实现2 3 3 4 实验结果2 5 第四章立体匹配算法2 7 4 1 立体匹配算法研究2 7 4 1 1 立体匹配算法的分类2 7 4 1 2 局部立体匹配算法2 7 4 1 3 全局立体匹配算法3 2 4 2 基于图像分割的快速立体匹配算法3 8 4 2 1 区域信息的组织方法3 8 4 2 2 区信息结构的生成方法3 9 4 2 3 本文算法的匹配过程4 0 4 2 4 区域视差的计算方法4 2 4 3 实验结果与性能分析4 4 第五章总结与展望4 7 5 1 主要完成的工作一4 7 5 2 主要创新点4 7 5 3 工作展望4 8 参考文献4 9 发表论文和参加科研情况说明5 3 霉i 【谢。5 5 i i 第一章绪论 第一章绪论 视觉是我们观察世界、认知世界的重要手段。人类从外界获取的信息约有 7 5 来之于视觉系统。视觉的最终目的是要对场景做出对观察者有意义的解释和 描述，然后基于这些解释和描述并根据周围环境和观察者的意愿制定出行为规 划。计算机立体视觉是计算机科学和人工智能的一个重要分支。它的研究目的和 内容有两个方面，一是用计算机实现人类视觉的部分功能；二是由此帮助理解人 类视觉的机理。计算机立体视觉研究始于2 0 世纪5 0 年代，当时计算机立体视觉 和图像处理、模式识别一起通称为计算机图像处理，泛指一切研究如何用计算机 处理图像信息的技术。随着研究不断地深入，三类学科各自分别自成体系向纵深 发展。 我们生活的客观世界在空间上是3 维的，但现有的大多数图像采集装置所获 取的是含有3 维信息的2 维图像。计算机立体视觉主要研究如何借助成像技术从 图像里获取场景中物体的距离信息。计算机立体视觉的基本原理是从两个或多个 视点去观察同一场景，获得在不同视角下的一组图像，然后通过三角测量原理获 得不同图像中对应像素间的视差，并进而推断场景中目标的空间位置等。计算机 立体视觉的主要目标是构建计算机的“视觉系统 ，实现计算机对三维场景的感 知、识别和理解。计算机立体视觉系统通常可以分为摄像机标定、立体匹配和三 维空间重建三部分。计算机立体视觉技术感知三维信息的能力依赖于同一空间场 景在不同视点图像中成像的差异，立体匹配的任务就是在两幅或多幅图像中寻找 空间物理元素成像点之间的对应关系【1 1 。 1 1 课题的历史背景 计算机立体视觉的研究工作可以追述到上世纪六十年代中期，美国麻省理工 学院的r o b e r t 对图像分析进行的研究工作。二十世纪八十年代初，麻省理工学 院人工智能实验室的m a r r 首次从信息处理的角度综合了图像处理、神经生理学、 临床精神病学及心理物理学的研究成果，提出了较为完善的视觉系统框架【2 1 。该 框架从信息处理系统的角度出发，将计算机视觉的研究应分为三个层次，即计算 理论层次、表达与算法层次、硬件实现层次。该框架奠定了双目计算机立体视觉 发展的理论基础，至今仍然被广大计算机立体视觉工作者使用，并已发展成了从 图像获取到最终的景物可视表面重建的比较完整的体系。 天津工业大学硕士学位论文 今天计算机立体视觉依然是科学研究的一个热点，但是其研究重点已转向了 一些具体的和细节性的问题，如立体匹配算法、遮挡检测、实时处理等等。同时 计算机立体视觉无论在应用还是在理论方面都取得了许多进展，从最初的双目计 算机立体视觉发展到多视几何【3 j ，从被动计算机立体视觉扩展到主动计算机立体 视觉，从基于灰度图像的计算机立体视觉发展到基于彩色图像的计算机立体视 觉，从需要标定的计算机立体视觉向着不标定或少标定的方向发展等等。 目前，对立体匹配的研究大致分为两个方向：一个方向是从实际应用和要求 出发，通过强调场景和任务的约束等手段来降低视觉处理问题的难度，致力于建 立适用于专门领域的实用计算机立体视觉系统。另一个方向是从理解生命体视觉 的立体融合机制出发，试图建立一种通用的双目视觉计算模型。尽管该方向也取 得一些研究成果，但是就目前的研究而言，还不能要构造出与人类视觉一样灵活 的机器视觉系统。 1 2 立体匹配技术国内外发展概况 1 2 1 国外立体匹配技术的发展 国外的计算机立体视觉技术发展的比较早；立体匹配技术作为计算机立体视 觉领域一个非常重要的环节，也取得了很多的研究成果。计算机视觉研究起初都 是采用模式识别的方法对图像中的二维信息进行研究。二十世纪六十年代，美国 m i t 的r o b e r t 和h u f f m a n 、c l o w s 以及w a l t z 等人先后成功地对三维积木世界进 行了研究。积木世界的研究工作对计算机立体视觉的发展起了很重要的促进作 用，反映了视觉早期研究中从简化的世界出发进行研究的特点【4 】。 窗匹配是一种比较常用的匹配算法，而匹配窗的大小很难选择。美国卡内 基梅隆大学的t k a n a d e 提出了基于变化窗进行匹配的方法1 5 1 。t k a n a d e 采用 的变化窗口的大小和形状均可以变化。基于变换窗口的匹配方法在纹理稀梳的区 域也能获得很好的匹配效果，但是该法中变化的窗e l 计算需要很大的计算量，从 而降低了算法的匹配速度。 意大利信息与通信技术电子系统研究中心和意大利波洛尼亚大学合作， l u i g id is t e f a n o ，m a s s i m i l i a o n o 等人利用极线约束，提出了一种单向匹配算法【们。 此种算法只需经过从左图像到右图像( 右图像到左图像) 一次匹配就可以得到所 需要的匹配点对，大大节省了匹配的时间的同时，也提高了匹配精度。 微软公司与华盛顿大学合作基于宽基线计算机立体视觉系统为火星卫星“探 测者”号研发了一套精确的导航定位系统。该系统通过“探测者”上的同一台摄 像机在的不同位置对某一物体进行拍摄来获取匹配的图像对【刀，拍摄间距越大， 2 第一章绪论 基线越宽，能观测到越远的地貌。系统首先采用非线性优化得到两次拍摄图像时 相对准确的摄像机位置，并利用鲁棒性强的最大似然概率法与高效的立体搜索相 结合的方法进行图像匹配得到亚像素精度的视差，然后根据此视差计算图像对 中各点的三维坐标。 1 2 2 国内立体匹配技术的发展 国内的立体匹配技术虽然起步较晚，正处于初始阶段，但也有了一定的发展。 尤其是近十几年来，计算机立体视觉技术方面的研究在国内引起了广泛关注。同 国外的研究相比，国内计算机视觉的研究主要关注于如何将该技术转化成生产 力，应用到现实生活中，因此发展很快，尤其是在工业、农业和军事领域都显示 出了强劲的发展势头，也有了一定的理论和实际研究成果。 哈尔滨工业大学通过异构双目活动视觉系统实现了全自主足球机器人导航。 此导航系统通过一个可以水平旋转的摄像机和两台固定的摄像机对现实场景进 行拍摄，使机器人在处理速度、测定精度以及视野范围方面达到最佳匹配。双目 协调技术能够使机器人同时捕捉多个有效目标。当观测目标发生相遇时也可以通 过数据融合提高测量精度。在实际比赛中部分传感器失灵的情况下，仅仅依靠双 目协调仍然可以实现全自主足球机器人导航【8 】。 中科院自动化研究所机器人视觉研究组的雷成博士基于计算机立体视觉开 发出了c v s u i t e 软件【9 j ，该软件主要完成了相机的自标定、特征点的提取、特征 点的匹配、模型的三维显示的功能。该软件使用方便，能够有效地去除错误的匹 配点，大大提高了匹配的精度。但是，该软件的匹配过程耗费了很多的时间，速 度很慢。 浙江大学的机械系利用透视成像原理，通过双目体视方法实现了对多自由度 机械装置的动态、精确位姿检测。该方法仅需从两幅图像对中抽取必要的特征点 进行匹配【l o i ，便可以得到三维坐标信息；因此信息量少，处理速度快，尤其适于 动态情况。与手眼系统相比，该方法不受被测物的运动的影响，且不需知道被测 物的运动先验知识和限制条件，提高了检测精度和稳定性。 武汉汽车工业大学的王天珍教授，在现有视觉模型的基础上，将生物视觉模 型与计算机立体视觉模型相结合，提出了一种并行匹配模型【1 1 】。香港大学的 m a x m il h u i l l i e r 博士和龙泉教授，在图像匹配中引入了区域分割的区域增长算法 思想，对人脸以及景物图像等进行处理，已经取得了一定的成绩，能够得到数目 较多的匹配点对和稠密的视差刚1 2 j 。 3 天津工业大学硕士学位论文 1 3 课题的研究内容及组织结构 1 3 1 立体匹配算法的发展趋势和存在问题 目前立体匹配的研究工作大多是针对校正后的匹配图像对进行稠密立体匹 配研究。立体匹配算法的有效性主要取决于三个方面，分别为匹配特性的正确性， 特征间的本质属性可靠性以及算法对所选特征点进行正确匹配的稳定性。立体匹 配的研究主要是围绕着这三方面的工作进行的，现已提出了大量的匹配方法，但 是由于该问题涉及的内容太多，至今立体匹配问题仍未得到很好的解决。特别是 在复杂场景中，如何降低实现的复杂程度和计算量，以及提高算法的去歧义匹配 和抗干扰能力，都还需要进行更深入的研究。 基于图像分割的立体匹配算法对于计算机视觉领域中缺失纹理区域的匹配 这个的经典难题的处理上能够取得较好结果。但是由于基于图像分割的立体匹配 算法使用的是全局的优化算法，在匹配速度上达不到实时性要求。 本文对现有的基于图像分割的立体匹配算法进行了深入研究，发现这些立体 匹配算法对图像分割后得到的区域信息的使用方法没有充分利用立体视觉图像 的特点。本文对立体视觉图像进行了深入研究，指出了匹配图像中能够用于区域 匹配的四类特征信息。根据四类特征信息本文对图像分割后得到的区域从不同的 维度进行了组织，并制定了匹配区域的寻找规则，从而提高了匹配区域的查找速 度和精度。总体来看，本文提出的视差计算算法，执行速度快，计算精度较高， 可用于匹配精度和实时性要求较高的场合。 1 3 2 本文的组织结构 本文的组织结构如下： 第一章主要介绍了立体匹配的历史背景知识和国内外的发展现状。 第二章对立体视觉的基本理论进行了介绍。第一部分介绍了立体视觉技术理 论基础。第二部主要立体视觉中的不确定性。第三部分介绍了极线几何的有关知 识。第四部分对立体视觉图像进行了研究，指出了立体视觉图像中能够用于区域 匹配的四类特征信息。 第三章对图像分割进行了详细介绍。首先介绍了图像分割的基本模型，然后 介绍了图像分割的主要算法以及每种算法的优劣，最后介绍并实现了本文使用的 快速分水岭图像分割算法。 第四章首先对当前的匹配算法按照策略的不同作了详细的介绍，然后对已有 的基于图像分割的立体匹配算法在图像分割算法和分割后区域信息的组织方法 4 5 天津工业大学硕士学位论文 6 第二章立体视觉基本理论 第二章立体视觉基本理论 2 1 立体视觉的理论基础 计算机立体视觉研究的主要内容为如何从不同视角拍摄的两幅或多幅图像 提取现实场景的三维信息。计算机立体视觉的基本原理是三维空间中的每一点在 两个或多个不同投影面上的投影对是唯一的。因此，如果可以确定空间点不同图 像中的像的对应位置，就可以确定点在三维空间的位置。 计算机立体视觉系统可以分为多目计算机立体视觉系统和双目计算机立体 视觉系统两类。由于多目计算机立体视觉系统可以由双目计算机立体视觉系统组 合而成，而且本文研究的立体匹配算法主要针对于双目立体视觉领域，因此下面 以两幅图像为例对立体视觉的理论基础进行说明。 图2 1 双目立体视觉系统 图2 1 为双目立体视觉系统示意图，图中分别以下标，和，标注左、右摄像 机的相应参数。世界空间中一点a ( x ，y ，z ) 在左右摄像机的成像面c ，和c ，上的像 点分别为a t ( u ，坼) 和a ，( 甜，) 。这两个像点是世界空间中同一个对象点a 的像， 称为搿共轭点一知道了这两个共轭像点分别作它们与各自相机的光心q 和o ， 的连线，即投影线口，d ，和a ，d ，它们的交点即为世界空间中的对象点a ( x ，y ，z ) 。 简化后的双目计算机立体视觉系统如图2 2 所示。 7 天津工业大学硕士学位论文 图2 - 2 双目计算机立体视觉系统 x k 图2 - 2 中以和吼分别为双目立体视觉中左右两台摄像机的光心，乙，和乙， 分别为两台摄像机的光轴，其中z 。，和乙互相平行，两台摄像机的水平坐标轴x 。， 和x d 相互重合，且两摄像机的内部参数相同。这样右摄像机可以认为是由左摄 像机在x d 方向平移距离b 得到的。q ，和吼之间的连线称为基线，图中其长度 用b 表示。世界坐标系原点仇置于基线中间，并且l 与髟轴重合。对于世界 坐标系中的一点p ，其在左右摄像机成像平面上的像坐标分别记作( x ，) ，) 和 o ，y ，) ： 盼- 小z 。ll y d j = 舒朔 州2 m x r = z f 。7l y x c 仃r j 7 = x ”；? 7 2 公式c 2 2 ， 本文中，如果不做特别说明，均定义视差d 为： d ：而一x ，：笪 z _ 公式( 2 3 ) 反之，如果知道点p 的视差d ，则可计算其深度坐标： 气：等：j l 公式( 2 - 4 ) 气2 亏。焘 蜮q 。4 8 tlfi上 爻、 ， ， ， ， ， ， ， 第二章立体视觉基本理论 2 2 立体视觉的不确定性 m a r t 提出的另一个重要理论是立体视觉的不确定性【1 3 l 。该理论认为早期视 觉的一个恰当定义是成像过程的逆过程。具体表现为计算机图形学或经典光学中 遇到的是确定3 维物体的影像，而在计算机视觉中面对的问题是由影像恢复3 维 物体的表面信息。由于在从3 维世界向2 维影像投影的过程中丧失了大量的信息， 视觉系统必须依赖于客观的约束条件才能获得确定的解 1 3 , 1 4 , 1 5 】。为避免假匹配， m a r r 首先采取了两个约束条件旧： ( 1 ) 任何一个给定点，在任何时候都只有一个固定的位置。这是唯一性的约 束条件。 ( 2 ) 物体是凝聚的，它们不可能在没有变化的迹象的前提下，发生突然折断 或是弯曲。这是连续性的约束条件。 一般的计算理论是采用3 个匹配规则【1 4 1 ： ( 1 ) 如果正在考虑的是白底上黑点子所组成的面，那么一个眼睛所见到面上 的黑点子也正是另一眼所见到的黑点子，黑点子只能和黑点子匹配，这是匹配的 相容性； ( 2 ) 一个黑点子只可以和另一眼的一个黑点子真正匹配。这是匹配的唯一性； ( 3 ) 视差的变化是很缓慢的，这是视差的连续性。 m a r r 的这种思想被p o g g i o 进一步发展为早期视觉不适定性问题【1 6 1 ，他认为 早期视觉依赖于约束条件的这种共有特征可以表述为h a d a m a r d 意义下的不适定 性问题。h a d a m a r d 将不适定性问题的概念引入到了偏微分方程的求解过程中。 p o g g i o 说明了许多早期视觉问题，如立体视觉中的匹配、光流计算、边缘提取等 问题，都可以看作h a d a m a r d 意义下的不适定问题，。不适定性问题求解的基本 思想是通过引入先验知识来限定解的空间范围，使不适定性问题转化为适定性问 题。先验知识可以是变分规则或统计特征。通过先验知识的引入来表征解空间的 特征的方法称作正则化理论。在立体匹配领域，一般是利用匹配连续性约束将匹 配视差限制在平滑解空间里。 设g ，( x ，y ) ，g ，( z ，y ) 分别表示左右图像的灰度值或某种变换，d ( x ，力为匹 配视差，则根据正则化理论可将立体视觉问题转化为求解以下变分式的最小化问 题。如公式( 2 5 ) 所示， f 阿g ，g ，j ，) 一g ，g + d g ，y x 夕汗+ a 【d g ，j ，) 】2 净呻= m i n 公式( 2 5 ) 公式( 2 5 ) 中第1 项表示匹配特征间的相似性；第2 项反映了视差连续性 9 天津工业大学硕士学位论文 约束。在正则化方法中，如何有效地保护视差的不连续信息是将视差约束在平 滑解空间里存在一个需要解决的问题。通常的做法是通过引入一个可控制平滑度 的权函数来构造含有不连续信息的通用正则化模型，来保护解的不连续信息。 当前的影像匹配中还有很多约束。通常用到的约束条件如下 i l l s ： ( 1 ) 核线约束，同名像点在同名核线上； ( 2 ) 唯一性约束； ( 3 ) 光度匹配约束，同名像点灰度应匹配； ( 4 ) 几何相似约束，同名特征的几何特性应相似； ( 5 ) 顺序约束，同一表面上物体在左右影像点的投影顺序应一致； ( 6 ) 形状连续性约束，沿边缘方向上的视差变化应是连续的； ( 7 ) 相容性约束，同名特征应相容； ( 8 ) 视差有限； ( 9 ) 视差变化梯度有限。 2 3 极线几何 2 3 1 极线几何基本原理 c l 图2 - 3 极线几何关系 假设有空间场景的两幅图像以和j 2 ，x 为图像以中的一点，则在三维空间 中所有映射到而的空间点构成一条过第一个摄像机c l 摄影中心的直线。从第二 个摄像机c ：，来看，这条直线映射为图像以中的一条直线z ：，z ：g 黼- t x , 的极线。在图像以中与而匹配的点必定位于极线，2 上。图像j 2 中所有极线交于 一点p ：称为极点。 1 0 第二章立体视觉基本理论 事实上，极点p ：是第一个摄像机q 的摄影中心在图像以上的投影点交换 两幅图像的角色，有同样定义的几何关系存在。如图2 3 所示 计算机立体视觉中的这种极线几何关系可以用有公式( 2 - 6 ) 来表示。 而聃= 0 公式( 2 呦 其中x 。和x 2 ( 齐次坐标) 为空间中同一点p 在图像以和j 2 上的匹配像点对。 f 是秩为2 的3 x 3 矩阵，称为基础矩阵。点毛在图像以上对应的极线，2 = f x i ， 点x 2 在图像上对应的极线i i = f x 2 。 2 3 2 基础矩阵求解 对于每一对匹配点x = ( 甜， ，) r 和r = ( ”，v ，) 丁由式( 2 - 5 ) 可以确定关于待求 参数f 的线性方程，如有公式( 2 7 ) 所示： ”= ，；i + 材，以l + u f , l + ，l | z 2 + ，以2 + 历2 + 材z 3 + ，+ 厶3 = 0 公式( 2 7 ) 如果存在多对匹配点，就可以构成一个有公式( 2 - 8 ) 所示线性方程组。 a f = 0 公式( 2 - 8 ) 其中，彳是系数矩阵，厂是由基础矩阵元素构成的一个9 维向量。根据基础 矩阵的特点，实际中只需确定厂的8 个尺度因子，因此为了简化求解，通常认为 8 州= l ，4 州表示厂的模，即2 范数当矩阵彳的秩为8 时，解是唯一的。这种 计算基础矩阵的方法称为8 点算法。但当使用的匹配点对多于8 个时，由于点的 坐标噪声带来的误差，矩阵a 的秩很可能大于8 。此时彳最小奇异值的特征向量， 即么的奇异值分解( s v d ) c p 矩阵v 的最后一列向量为的最小二乘解。 如果只有7 对匹配点，并且矩阵a 的秩为7 ，则方程( 2 - 6 ) 的解是一个形 如a f , + ( 1 一口) e 的2 维空间，其中口是纯量变数，矩阵e 和r 是对应于a 的奇 异值分解a = u d v r 中矩阵v 的最后两列向量 和疋的矩阵。此时可以通过 d e t ( f ) = 0 ，即州媚+ ( 卜口) r ) = 0 ，得到口的一个或三个实解，从而得到基 础矩阵的一个或三个解。这种求解基础矩阵的方法称为7 点法。 为了降低矩阵a r a 的条件数，以提高线性问题求解的稳定性，在求解基础 矩阵前，需要对输入数据匹配点的坐标做归一化处理。通常的做法是找一个能够 对图像坐标进行平移和比例缩放的变换矩阵t ，使变换后匹配点集的形心为原 点，点集到原点的均方根距离为2 ，如式( 2 9 ) 和( 2 1 0 ) 所示。 舅= t x 公式( 2 - 9 ) 天津工业大学硕士学位论文 t = 公式( 2 1 0 ) 的个戮攮k 靠嘉劳蕊篮配点 舅晟= 0 公式( 2 1 1 ) 其中户= 丁”r f t 一，在求解户后，可以通过有公式( 2 1 2 ) 计算基础矩阵。 f = t r 励 公式( 2 1 2 ) 2 3 3 极线校正 图像校正就是指通过对两幅图像各进行一次映射变换，使得图像投影到平行 于两个摄像机基线的同一个空间平面上。这就从软件上校正了机械上的偏差，使 得校正后的图像如同由平行双目计算机立体视觉系统采集而来一样。这一方面能 够使两幅图像对之间匹配像素的极线在同一水平扫描线上，从而使匹配问题变为 在一维扫描线上的搜索问题；另一方面也能够使图像匹配点的邻域像素具有更高 的相关性，从而有利于基于相关运算的立体匹配算法的实施。 平行双目计算机立体视觉的极线平行于图像的水平扫描线，其极点位于无穷 远点( 1 ，0 ，o ) r 。所以通过映射变换的方法进行极线校正第一步要将极点映射到无 穷远。这就需要寻找一个能够将图像极点映射到无穷远点的变换矩阵。虽然这样 的映射变换矩阵并不唯一，但为了避免变换过程中出现图像扭曲，往往按以下三 个步骤来进行： 第一步：将图像坐标原点移到事先给定的一点( ，v o ) ，在这一点周围图像 变换近似为刚体变换，变换矩阵如有公式( 2 1 3 ) 所示。 r 1 0 一甜o 卜0o 一l l00 1 i lj 公式( 2 - 1 3 ) 第二步：构造旋转矩阵r 。第一步的变换之后，图像的极点e 变为虿= 死， 令：虿= ( 万，矿，1 ) r ，0 ：口t a n f 兰1 ，则经过( 2 1 4 ) 所示的旋转变换，图像的极点变 为( 厂，0 ，1 ) r 。 v 1 2 吲o形o o o 第二章立体视觉基本理论 b 降 公式( 2 1 4 ) 第三步。构造如有公式( 2 一1 5 ) 所示的变换矩阵，将极点u ，0 ，1 ) r 映射到无穷远 ! ； 公式( 2 1 5 ) 经过上述三个步骤的变换，图像的极点被映射到了无穷远，因此将极点映射 到无穷远的变换矩阵表达式应为：h = g r t 。 对于一对图像- ，和，校正的具体过程就是将两个映射变换矩阵日和日7 分 别作用于，和- ，然后对变换后的图像重采样，从而使重采样后的两幅图像的极 线位于同一扫描线上。换而言之，如果，和，是原图像对中两条对应极线，则 h i = h 一，其中日，表示矩阵日的伴随矩阵，符合这个条件的两个变换称为 匹配变换对。 选择匹配变换对的策略是：首先按前面介绍的方法计算作用于图像，的变 换矩阵日，将极点e 映射到无穷远。然后找一个匹配变换矩阵日使如有公式 ( 2 1 6 ) 所示的平方距离和最小 d ( h x ，日研) 2 j 公式( 2 1 6 ) 图像对的基础矩阵f 可分解为f = 【e p 】，m ，其中l 为极点向量p 的斜对称 矩阵给定一个向量，= 以，：) r ，其斜对称矩阵定义如式( 2 1 7 ) 所示。 = 卜x - l 馘( 2 - 1 7 ) 【一，t x 0j 对应于变换矩阵日的匹配变换矩阵日具有式( 2 一1 8 ) 所示形式 b 田= a h m 公式( 2 一i s ) 式( 2 1 8 ) 中彳；l0 10l 。 令葛= 日舛，彰姐峨，l 扫公式( 2 1 6 ) 变为有公式( 2 - 1 9 ) 所示形式。 d ( 做。，彰) 2 公式( 2 1 9 ) 令毫= ( 五，e ，1 ) ，霉= ( 彰，彰) ，有公式( 2 1 9 ) n - - 以写成有公式( 2 2 0 ) 。 1 3 1 - - i i i l i i j o o l 口口 证 璐o s o ， l 0 y 一 -。l = g 点 天津工业大学硕士学位论文 ( 口玩+ 眈+ c 一露炉+ ( e 一彰) 2 公式( 2 2 0 ) l 由于( e 一移；) 2 是个常数，问题转化为最小化式( 2 2 1 ) 的问题。 ( 口玩+ 纸+ c 一露；) 2 公式( 2 2 1 ) j 通过线性最小二乘方法可以求解未知参数a ，b ，c 。从而完成了匹配变换 对的求解。对于映射变换后图像中的点叠，其在原图像中的对应点为x = h _ 1 爻， 曼点的颜色由原图像中x 处的颜色值确定，从而实现了图像的重采样。 2 4 立体视觉图像研究 在立体视觉系统中，理想的平行双目计算机立体视觉系统具有非常突出的优 点。在实际应用中，理想的平行双目计算机立体视觉不可能存在，更糟的是在某 些情况下，为了满足拍摄视角的需要，会故意使两个摄像机光轴保持一定角度。 在这种情况下，计算机视觉系统的极线几何会比平行双目计算机立体视觉的极线 几何更加复杂。但是通过图像校正，实际的计算机视觉系统获得的图像具有理想 平行双目立体视觉系统图像相同的特点。因此立体匹配算法通常都以理想的平行 双目计算机立体视觉系统为背景，即假定进行图像采集的摄像机是并行排列并且 其光轴相互平行。 在这种几何假定下，图像匹配像素对之间存在以下特点。这一方面能够使两 幅图像对之间匹配像素的极线在同一水平扫描线上，从而使匹配问题变为在一维 扫描线上的搜索问题；另一方面也能够使图像匹配点的邻域像素具有更高的相关 性，从而有利于基于相关运算的立体匹配算法的实施。本文下面的研究主要基于 校正后的图像进行研究。 2 4 1 图像中的极线约束 图2 - 4 为平行双目立体视觉示意图，o l 与o r 分别为左右摄像机的光心，o l 与o r 相互平行。我们把o l 与o r 之间的线段称为基线。两个摄像机的坐标系统 都和基线对齐，并且摄像机的x 坐标轴和基线平行。在平行双目立体视觉中，空 间中的点在两幅图像上的像会在同一条水平扫描线上。假设，空间有一点p ， ( x ，y ) 为p 在左图像上像的坐标，( x ，y ) 为p 在右图像上像的坐标，则两个像之 间的坐标差d ( x ，y ) 就是p 在图像对中的视差。在平行双目立体视觉中，有公式 ( 2 - 2 2 ) 成立。 x = x + s d ( x ，y ) ，y = y 公式( 2 2 2 ) 1 4 第二章立体视觉基本理论 。0 l x x ， p ， f l 0 l t o t 图2 - 4 平行双目立体视觉结构图 其中当以左图像为参考图像时s 取值1 ，当以右图像为参考图像时s 取值+ l ， 这样视差在任何情况下都为正数。 以上分析可知，在极线校正后的图像中，空间点在不同图像上投影的y 方向 的坐标是不变的。因此在不考虑遮挡的情况下，在经过图像校正后，空间中的物 体在不同投影面上的像y 方向上存在以下两个特点： ( 1 ) 像的上地址a d d r e s s 。相同： ( 2 ) 像的下地址a d d r e s s 相同。 其中a d d r e s s 肇为区域最上侧像素的y 地址，a d d r e s s d o , , 为区域最下侧像素 的y 地址 在存在遮挡的情况下，以上两个条件中只有部分条件成立。具体分为以下几 种情况： ( 1 ) 如果只是物体的上部存在遮挡，则只有特点( 2 ) 成立； ( 2 ) 如果只是物体的下部存在遮挡，则只有特点( 1 ) 成立。 2 4 2 图像中水平扫描线方向长度的变化 行中长度的变化是指，当物体表面与投影面在水平方向上的夹角不为0 时， 物体的像在两个投影面上行中长度不相等的现象。图2 5 给出了行中长度变化的 示意图， 1 5 天津工业大学硕士学位论文 e c l c 2 图2 - 5 行中长度变化示意图 m 为空间中的一个物体，j 1 和j 2 分别为计算机视觉中两个摄像机的镜头， c 1 和c 2 分别为两个摄像机的光心，e f 为计算机视觉采集到的物体m 的表面， l 为过f 与j 1 ，j 2 平行的直线，e f 在j 1 和j 2 上的投影分别为b 1 和b 2 。根据几 何知识可知( 2 2 3 ) 式成立 b ，a f 二一一 b 2 b f 公式( 2 2 3 ) 由于e f 与l 之间的夹角不为0 ，所以a f 不等于b f ，从而b 1 不等于b 2 。 行中长度的变化指出，即使在极线校正后，物体表面在不同投影面上的像的 大小和形状一般也不相同。但是如果假设这种长度变化的比例是相近的则公式 ( 2 2 4 ) 表示的区域平均高度h 可以作为匹配区域之间的另一个特征。 一 g h = 二，w = a d d r e s s , 辔h f a d d r e s s l e 孵 公式( 2 2 4 ) w 公式( 2 2 4 ) 中s 为区域中像素的个数，w 区域的宽度，a d d r e s s 棚为区域 最右侧像素的x 地址，a d d r e s s t 研为区域最左侧像素的x 地址。 另外立体视觉不确定性这的光度匹配约束指出同名像点灰度应匹配，从而匹 配区域之间的颜色平均值也可以作为区域匹配的一个特征。 综上所述，校正后的立体图像中，能够用于区域匹配的特征信息有四种，分 别为：区域的上地址，区域的下地址，区域的平均高度h 和区域的平均颜色值。 1 6 第三章图像分割算法研究 第三章图像分割算法研究 为了降低匹配误差的同时，提高匹配速度，有学者把图像分割应用到匹配算 法中。经图像分割处理后，原始图像中灰度连续变化的场景变成一些相对独立的 几何区域，整个图像的信息量大大减小，有利于目标特性的分析该方法对于缺 失纹理区域的匹配这个计算机视觉领域中的经典难题的处理上取得较好结果。 在基于图像分割的立体匹配算法中，图像