（信号与信息处理专业论文）基于epi和颜色分割的立体匹配算法及图像合成.pdf

中文摘要 立体匹配技术是计算机视觉研究中经久不衰的领域，主要应用于图像合成和 恢复3 一d 信息，并做为第三代新技术应用于视频领域。而本文主要讨论其在图象 合成中的应用。目前有多种立体匹配算法可以用来合成新视点的图像。本文对立 体匹配算法的两大类别：局部算法和全局算法，进行了介绍并列举了一些实例。 如局部算法中的固定窗口算法、自适应窗口算法，以及全局算法中的动态规划、 基于分层的颜色分割算法等。之后，利用基于m e a ns h i f t 的颜色分割对图像的平 滑作用，以及e p i 算法在边缘部分的预测较基于相关的匹配算法的天然优势，对 图象序列提取特征点。根据提取的特征点，在颜色分割得到的每个小分块内部进 行d e l a u n a y 三角分割。将划分得到的每个三角形取一个平面模型，并根据顶点 位差内插三角形内部像素位差，构造了一个合成新视点图像的系统。系统没有采 用e p i 中运用的图形学方法来通过变形合成新图像，而是根据计算得到的位差值 合成图像。合成则采用了z b u f f e r 技术，通过左右两个位差图来计算新图像中匹 配点的位置，并且保证了前景物体在发生遮挡情况下的可见性。合成图像的评估 由一个专门为立体匹配算法构建的评价系统来完成。 算法中e p i 提取、边缘检测、特征点提取、d e l a u n a y 三角分割以及位差计算、 图像合成等步骤，由m a t l a b 实现，而颜色分割则通过c + + 实现。 关键词：立体匹酉己，e p i ，z - b u f f e r ，位差，m e a n s h i f t a b s t r a c t s t e r e om a t c h i n ga l g o r i t h mi sa f r e q u e n t l yd i s c u s s e dt o p i ci nt h ea r e ao fc o m p u t e r v i s i o n i ti su s e dt o s y n t h e s i z ei m a g e sf r o mn o v e lv i e w sa n dr e c o n s t r u c t3 - d i n f o r m a t i o n m o r e o v e r , a st h et h i r dg e n e r a t i o no fn e wt e c h n o l o g y , i th a sb e e na p p l i e d t ot h ea r e ao fv i d e o p r o c e s s i n g t h i sp a p e rf o c u s e so ni t sa p p l i c a t i o ni ni m a g e s y n t h e s i s a tp r e s e n t ，m a n ya l g o r i t h m sc a l lb eu s e df o ri m a g es y n t h e s i s t h i sp a p e r i n t r o d u c e st w om a i nc a t e g o r i e so fs t e r e om a t c h i n ga l g o r i t h m s ，t h el o c a la l g o r i t h m s a n dg l o b a la l g o r i t h m s s u c h 硒t h ef i x e dw i n d o wa l g o r i t h ma n da d a p t e dw i n d o w a l g o r i t h m ，w h i c hb e l o n gt ot h el o c a la l g o r i t h m s a n ds o m eg l o b a la l g o r i t h m sa s d y n a m i cp r o g r a m m i n ga n dl a y e r - b a s e dc o l o rs e g m e n t a t i o n a l g o r i t h ma r ea l s o i n t r o d u c e d a st h em a i nc o n t e n to ft h i sp a p e las y n t h e s i ss y s t e mi sc o n s t r u c t e db y u s i n gt h et e c h n o l o g yo fm e a n - s h i f tb a s e dc o l o rs e g m e n t a t i o na n de p i ，w h i c h i n s t i n c t i v e l y a v o i d s p r o b l e m s i n i n t e n s i t y i n c o n t i n u o u sr e g i o n sm e tb y c o r r e l a t i o n - b a s e da l g o r i t h m s f i r s tt h ef e a t u r ep o i n t sa l ee x t r a c t e dt h r o u g he p i a n d a c c o r d i n gt ot h o s ep o i n t s ，d e l a u n a yt r i a n g u l a t i o ni sa p p l i e di ne v e r yc o l o rs e g m e n tt o c o n s t r u c ts e v e r a lp l a n e s ，a n dt h e n e v e r y p l a n ef u n c t i o ni sc a l c u a l t e du s i n gt h e d i s p a r i t yv a l u eo ft h e p i n n a c l e s i m a g ew a r p i n ga n dm o r p h i n gt e c h n o l o g yi s a b a n d o n e di nt h i sp a p e r i n s t e a d ，z - b u f f e rt e c h n o l o g yi su s e dt os y n t h e s i sn e w i m a g e s t h r o u g hd u a l d i r e c t i o nc o m p e n s a t i o nw i t ht w oc a l c u l a t e dd i s p a r i t ym a p s ，e n s u r i n gt h e v i s i b i l i t yo ff o r e g r o u n do b j e c tw h e no c c l u s i o nh a p p e n e d a ne v a l u a t i o ns y s t e mt h a t s p e c i a l l yc o n s t r u c t e df o re v a l u a t i n gs t e r e om a t c h i n ga l g o r i t h m si si n t r o d u c e dt o e v a l u a t et h er e s u l t si nt h i sp a p e r i nt h i sp a p e r , t h ef o r mo fe p i ，e d g ed e t e c t i o n ，e x t r a c t i o no ff e a t u r ep o i n t s ， d e l a u n a yt r i a n g u l a t i o na n dd i s p a r i t yc a l c u l a t i o na r ea l lc o m p l e t e di nt h ee n v i r o n m e n t o fm a t l a b ，a n dt h ec o l o rs e g m e n t a t i o ni sf i n i s h e db yc + + c o d e k e yw o r d s ：s t e r e o m a t c h i n g ，e p i ，z - b u f f e r , d i s p a r i t ym a p ，m e a n s h i f t 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的 研究成果，除了文中特别加以标注和致谢之处外，论文中不包含其它人已经发表 或撰写过的研究成果，也不包含为获得墨鲞盘堂或其它教育机构的学位或证 书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中 作了明确的说明并表示了谢意。 学位论文作者签名：亥予了 签字日期： 、，阳，7 年 彳月，e t 学位论文版权使用授权书 本学位论文作者完全了解叁盗盘堂有关保留、使用学位论文的规定。 特授权叁鲞盘鲎可以将学位论文的全部或部分内容编入有关数据库进行检 索，并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校 向国家有关部门或机构送交论文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者签名：负t 亍乡 导师签名： 1 乏幽主 签字日期：年月e l 签字目期：红移7 年易月c9e i 天津大学硕：t 学位论文第一章绪论 1 1 多视点系统简介 第一章绪论 多视点系统( m u l t i v i e ws y s t e m ) ，是两个或者两个以上的摄像机，对同一场 景或物体从不同角度拍摄得到多个二维图像的系统。多视点系统在图像处理领域 应用较多，而在视频应用中则属于新一代视频技术。在实际应用中，摄像机的个 数从两个到多个不等。由于平行配置( 即所有摄像机排列在一条直线上，每个摄 像机的焦距和该直线垂直) 有更充足的约束条件，故一般的研究都以摄像机的平 行配置为基础，计算空间物体对应于摄像机的3 d 信息，即深度信息。在视频系 统中，发送端将输入视频以及计算出的深度信息同时发送，接收端利用接收到的 参考图像( 帧) 以及深度信息合成一个或多个虚拟视点的视频，可以很大程度地 减少传输的数据量。 立体匹配算法是多视点系统中非常关键的部分，它源于对人类视觉的研究。 人通过左右双眼成像而得到三维空问物体的立体信息。计算机视觉则希望通过用 摄像机模拟人类视觉来得到物体的3 d 信息，从而还原物体的立体图像或者通过 这些信息合成一个或多个其它视点上得到的图像，而不需要摄像机来拍摄图像。 立体匹配过去一直并且今后仍将是计算机视觉领域关注和研究的重要问题。 如今国内外已经提出了很多匹配算法。但是对于视频传输来说，由于系统实时性 的需要，一般都采取最简单快速的匹配算法来保证对速度上的严格要求。 1 2 立体匹配技术简介 1 2 1 外极几何 在介绍立体匹配技术之前，首先需要说明一些概念： 1 位差( d i s p a r i t y ) t j j 假设有两台摄像机对同一空间物体取像，空间物体上某一点在左右图像 上都存在可见映射( 考虑到可能有遮挡部分) ，将这两幅图像重叠，空问此点 在左右两幅图像上对应的映射点之间的偏移便称为位差。 2 外极约束( e p i p o l a rc o n s t r a i n t ) t 2 j 如图1 1 所示，x 为空间某一点，工和工7 所在的平面分别为两个摄像机的成 天津大学硕二l ：学位论文 第一章绪论 像平面，x 和x 分别为x 在左右两个摄像机成像平面上的映射点。那么，由 x ，x 7 ，x 三点组成的平面称为外极平面( e p i p o l a rp l a n e ) ，外极平面与摄像机成像 平面的交线称为外极线( e p i p o l a rl i n e ) ，两个摄像机之间的连线成为基线( b a s e l i n e ) x 所在外极平面上的点在摄像机平面上的映射点必在外极线上，所有空间 上的点所在的外极平面均相交于基线。 图1 1 外极几何示意图 图l 一1 给：的是仃意位置的两个摄像机，伊i 一般情况下，我们从最简单的 种情况开始研究，那就是两台摄像机平行放置，两个成像平面共面，与基线平行， 并处在同一高度，焦距与基线垂直。在这种情况下，空间某点在仃一图像中的映 射点，在无遮挡的情况下，必可以在另外一幅图像中同位置的水平线上找到。即 两个映射点在两幅图像的同一水平搜索线上，如图l 一2 所示。空问点p 在，中的 映射点为只，在水平线，上。那么p 在，中的映射点只必然在同样位置的水平搜索 线，上。 本文之后的讨论中，无论摄像机个数多少，均采取上述位置配置，即匹配点 的搜索是一维的。 天津大学硕【j 学位论文第章绪论 图1 - 2 平行配置的摄像* l 外极坐标示意图 1 2 2 立体匹配算法简介 由输入图像台成新视点图像的立体匹配算法，大概有咀下三种吼 第 娄是基于全光采样( p l e n o p t i cs a m p l i n g 的方法由h a n r a h a n i ”利 g o n l e r t5 】等人提出。新视点的图像台成是由对输八图像台适的射线进行采样而得 到的。这种方法在本文不做进一步研究。 第二类方法是对客观景物建立一个详细的几何模型，来计算每个像素的深度 信息，这类算法基本都是基于相关运算。l a v e a u 柚df a u g e r a s 【6 j ，p o l l e f e y s 1 等很 多人都提出了此粪立体技术，通过输入图像获得需要的深度信息或者位差图( 位 差和深度意义是等同的，具体的说，位差和深度是成反比的) 。一旦获得位差图， 合成新图像就很简单，只需要通过位差图，计算参考图像里的点对应出现在新视 点的图像里的位置。s h a d e 等人提出的分层位差图像 8 1 是一种非常有效的方法。 1 4 前，在视频处理中广泛麻用的宙口算法，即块算法就属于此类算法中的局部 算法。局部算法普遍的特点是速度快，仇位差计算的结粜准确度不高因为在铷 频传输中传输的是差值所以对准确度的要求远没有对迷度的要求严格。而和局 部算法相对的全局算法则刚好相反预测的准确度较高”处理进度较慢。 f h 是，基于相关运算的方法存在个较明显的问题，即在两类区域内很难得 到比较准确的位羞信息。第一种是无纹理区域比如空墙壁。这类区域役有充足 天津大学硕士学位论文第一章绪论 的纹理来提供相关信息。另外，遮挡区域也会造成位差计算错误。因为边缘周围 一般都会存在部分被遮挡的区域，这种情况下会造成边缘部分相关信息匹配错 误。 第三类方法是基于c h e n 和w i l l i a m s 9 1 提出的图像变形( i m a g em o r p h i n g ) 。 s e i t z 和d y e r t l 0 】提出了一种在一对参考图像之间插入图像的技术，这种技术可以得 到视觉上比较准确的合成图像。l h u i l l e r 和q u a n t l l , 1 2 】提出了一种基于图形学的技 术，也是在图像之间内插出新图像，得到的新图像能够准确地复制场景中特征点 的运动轨迹。通过把输入图像进行三角分割，尽量照顾到亮度不连续的边缘。这 些算法都特别注意避开估计特征点实际的3 d 位置，通过变形来合成新图像，从 而避免了估计实际3 d 位置时会遇到的问题。本文重点讨论的e p i ( e p i p o l a rp l a n e i m a g e ) 技术，在基于图像变形的算法中也有应用。 基本上所有立体匹配算法，都建立在某些对成像平面和物理世界的假设和约 束之上，这些假设和约束包括1 1 , 1 3 】： 1 我们看到的物体的表面是郎伯( l a m b e r t i a n ) 表面( 不透明，反射所有的 入射光线，并且在所有方向具有相等亮度的理想表面) 。所以，两个匹配的像素 应具有相同的颜色和亮度。 2 唯一性假设。假设对于参考图像中的每一个像素在匹配图像中至多存在 一个像素与之对应。这样图像中的每个匹配像素最多只能有一个位差值。 3 平滑性假设( 也称为连续性假设) 。物体表面一般是平滑的，所以假设匹 配得到的位差值的变化除了在边界等深度不连续的地方，在图像中几乎处处保 持连续变化。 这个假设是建立在如下基础上：我们认为和物体表面到观察者的距离相比 较，物体表面凹，、引起的变化或者由观察者到表面的距离变化造成的差异都很 小，因此物体表面可以看成是平滑的。 4 一致性约束。一致性约束也称为相容性约束，根据几何学不变性，两幅 图像中描述对像的几何结构相同。例如沿外极线进行搜索时，左图的a 点在b 点的左边，那么在匹配图像中a 点和b 点的相对位置不变。虽然有时候可能出 现遮挡，导致一幅图中的某些点在另一幅图中不可见。 这些假设在本文中同样适用。 1 3 论文内容简介及章节安排 本文提出了一种基于e p i 和颜色分割的立体匹配算法。文章首先对计算机 视觉以及立体匹配算法的基本概念进行了介绍，之后简单介绍了现有的一些立体 天津大学硕：t 学位论文第一章绪论 匹配算法的类别以及立体匹配算法中默认的一些约束条件。之后对e p i 和基于 m e a ns h i f t 的颜色分割进行了介绍，并讨论了两者结合算法的具体步骤以及部分 代码，并给出了算法计算得到的合成图像。 第一章是绪论部分，主要介绍了立体匹配算法的基本概念和一些通用假设， 并介绍了现有算法的发展和简单分类。 第二章是对e p i 算法的介绍。主要描述了算法的核心理论和步骤，省略了合 成部分的介绍。 第三章是基于m e a ns h i f t 理论进行的颜色分割。介绍了核函数估计，m e a n s h i f t 滤波以及图像分割的基本步骤，并给出了典型结果。 第四章针对本文所提出的算法，即基于e p i 和颜色分割的立体匹配算法进行 了详细介绍，包括部分实现代码。并给出了实验结果，即合成的新视点图像。 第五章介绍了一个针对立体匹配算法构造的评价系统，给出了评价结果。 第六章是对将来的展望，对基于e p i 和颜色分割的图像合成系统中仍需要解 决的问题进行了分析。 天津大学硕：i ：学位论文 第二章一些常见的立体匹配算法 第二章一些常见的立体匹配算法 2 1 基于区域( 窗口) 的局部立体匹配算法 基于区域亮度的算法是利用图像处理中所称的区域相关方法，也称为窗口算 法( w i n d o w b a s e da l g o r i t h m ) 。它是解决像素匹配问题的一个最直观、最简单 的方法。这种算法在一幅图像中以一个像素作为中心像素，并以它为中心选定一 个区域，在另一幅图像，即匹配图像中寻找相关系数最大的区域，把找到的区域 中心认为是参考图像区域中心的匹配像素。 窗口算法通常在匹配图像对应的水平搜索线上利用窗口进行搜索( 以第一 章第二节里提出的摄像机配置以及外极约束为前提) ，找到具有最大对应关系的 对应点。在这种算法里，并不施加任何平滑性( 连续性) 约束，也就是说，匹配 误差和相邻像素的位差是相互独立的，因此，窗口算法在无纹理区域很难得到正 确的位差。窗口算法隐含了连续性：即假设同一个窗口内的所有像素具有相同的 位差。这个假设在位差不连续处不成立，因此会得出很多错误的匹配，并且会产 生前景物体膨胀效应。通常来说，选择合适的窗口大小是一个关键因素。一方面， 小窗口因为无法捕捉足够的亮度或者色度变化信息，则在纹理不多的区域很难得 出正确的结果。另一方面，大窗口会模糊深度边缘并且很难捕获很小的细节和对 像。这促进了有关自适应窗口算法的研究，所谓自适应窗口算法，是针对不同情 况调整窗口的大小、形状、或者中心像素的位置，使其适应特殊区域的相关特性。 关于窗口算法，目前很多文献对其采取不同策略做了研究和优化，从最简单的固 定大小窗口、到自适应可变窗口【1 4 ，1 5 1 6 17 1 、多窗口策略【1 8 1 等等。 2 1 1 简单窗口算法 下面首先介绍位差空问( d s i ) 的概念。 位差空间由x ，y ，d 三个轴构成，对于每个d 值( 即位差) ，x ，y 平面为以该位差 进行预测后与实际匹配图像计算的残差图像。 选取固定大小的矩形为窗口进行搜索匹配，是最简单的一种窗口算法。设 f a x ，y ) 和厶( z ，y ) 分别为参考图像和匹配图像，( z ，y ，) 为参考图像中的一点，取 以( z ，y ，) 为中心的临域为窗口，大小为肌胛。在大部分立体匹配算法中，最为 通用的匹配误差项包括，亮度误差平方( s q u a r e di n t e n s i t yd i f f e r e n c e ，s d ) 【1 9 2 0 ， 天津大学顶l 学位论文 第一章蝗常见的立体匹 l 算法 亮度绝对值误差( a b s o l u t ei n t e n s i t yd i f f e r e n c e a d ) e 2 ”。在视频处理领域这些量分别 称为均方误差( m e a n s q u a r e de r r o r , m s e ) 和绝对平均误差( m e a na b s o l u t e d i f f e r e n c e ，m a d ) t ”i 在这里我们采用s d 。 设窗口在匹配图像中移动了x 和v 后的覆盖区域为s ，t 为参考图像中的 窗口覆盖区域则有m i 吐= 跚，) 一t ( i ，川( 2 - 1 这个窗口在匹配图像巾不断移动并汁算误差项，直到找到误差最小的那个窗口， 将其中心像素定为参考图像窗口中心像素的匹配点。在第一章中我们已经将搜 索范闱从维减小至一维。由此定义的互相关测度函数为： 帅，：杰壶掣篙筹竺l i ，j q 。【l ，j + pj 其巾，f ( x ，) ，l ( x ，y ) 分别为参考图像和匹配蚓像- 相关匹配区域是以( f ，jj 为 q j 心的( 2 “+ l 】x ( 2 + ”大小的矩形宙u 蜱m j 、“，( ，+ 户】和o - ( i ，j 、 o - ( i ，+ p ) 分别足曲个隹彳口的均值和方差品终由 dp ( d 】_ m a x 来确定化茇 图21 为一组实验结粜，在( b j 中，右图为真实位差图其中位差值较小的 部分颜色较深位差大的部分蕊色较浅。从圈q j 可咀看出在培罐车地栀纹刚轳 少的部打，位麓计算出班误差较大本来应该是觑咆较浅的部分i l ；观了黑色块状 天津大学颂i ：学亿论义 第一审些常见的立体匹配尊浊 如涵圈_ 2 1 2 可变窗口算法 ( b ) 图2l 宙口算往计算的f t 蔗结粜 由上文i - r 知，在一幅图像巾，不同的像素j 1 - 往往要求1 ：同的支持窗口，而且 宙口的大小f _ j 形状最好有较强的适心代。为此t k a n a d e 和m0 k u t o m i 口4 提出了自 适应宙口模刊f h 简口形状仅限于方形。* 外卟f 泛麻用的算法是多窗门算 注i ”j ，该算法对r 每个像素点引算肯限的儿个小刮形状的商口性能晟好n 0 饪彳 u 被保留。下i n j 彳r 绍两种白近庸谢u 算洼。 1 中心像素可变的筒几算法 这种算法是由g p l g e r ”】，i n i i l l ；等人提出的算法简化而米裔口算法的 中心点一般在窗u 的中心， 当f r i 心像素在边缘叫，商u 内部计算得到的误差就 会很大，为了改善在边缘等不连续k 域的儿日e 敛粜采用了f | 2 - 2 几个窗口，这 些窗口的中心- 1 二分别存边缘或角上。在匹配过程中对每个像素分别用这几种宵 口进行搜索，取隈差最小的窗口揲测到的像素作为匹配像素。 天津大学硕士学位论文第二章些常见的立体匹配算法 图2 2 中心可变窗口示意图 2 基于区域的动态形状可变窗口 为衡量视差匹配的有效性，首先给出窗口的误差函数，然后根据该函数动态 地进行窗口增长。 误差函数：设待处理的图像为l ( x ，y ) ，r ( x ，y ) ，是同一物体在同一光照条 件下拍摄的左、右图像。则定义匹配误差函数为 2 il ( x ，y ) 一r ( x d ，川 ( 2 3 ) 其中d 为位差值。对于其它的误差匹配函数参见文献【4 1 。窗口误差函数如下给定： o = 虿+ a v a r ( e ) + , 8 ( x s 。+ y ) ( 2 4 ) 一e - - 白( 训) o i ，( j j l ” v a r ( p ) ：厨 p 2 = 白( w ) 2 j w ( j ，y ) e w 其中：s 。为窗口大小，也就是像素点的个数；口和为比例系数；y 为小窗口抑 制参数。式( 2 - 4 ) 中的第1 项是指在该窗口中的平均错误率。显然，如果对于给定 视差d 越接近真实视差，则该项的值就越小。用窗口的大小6 w 进行正规化，使 得不同大小窗口的误差具有可比性。式( 2 - 4 ) 中的第2 项是方差信息，同样，给定 视差d 越接近真实视差，则该项的值就越小。当窗口越大时，第3 项的值就越小。 这是因为大窗口包含的信息更多，匹配的视差结果更准确，在前面2 项的值相同 时，更希望采用较大的窗口。系数口，和参数y 的值通过权衡三者的关系，由 实验给出。 动态窗口增长策略：对于考察点，首先构造以该点为中心的最小支持窗口。 对固定视差d 计算该窗口误差函数o 。然后，开始动态窗口增长。窗口的动态 口曰宙口口圈圈口口 天津大学硕士学位论文第二章。些常见的立体匹配算法 增长策略描述如下： 1 以考察点为原点，沿x 轴分别向正方向和负方向增长窗口，每加入一 个像素点就重新计算窗口误差e ，一旦新得到的窗口误差巴与前一个s 冈1 m , 1 2 的误差e 的差值大于给定的阈值或者窗口边界值大于给定的最大值，则停止 生长，并且记录x 轴的边界。 2 采用步骤1 的方法动态增长y 方向的点。 3 对于每个给定的位差d ，采用前两个步骤计算动态窗口的误差函数， 最后保留窗口误差函数值最小的窗口和对应的位差d 。 动态增长过程如图2 3 所示。 豳豳豳 ( a ) 最小支持窗口( b ) x 方向增长结果( c ) y 方向增长结果 图2 3 窗口增长过程 该方法对于边界和遮挡部分也有比较好的检测效果。如果窗口在增加过程中 生长到边界部分，那么由于前景物体和背景部分像素之问的位差有较大差异，必 然会导致计算出的误差值增大，那么窗口就不会向这个方向继续牛长。 进一步地，可将整幅图像分成若干块，估计每个小块内的位差范同( 比如蒙 托卡洛随机实验 】4 】) ，然后在各子块上计算位差。图2 4 为简化的采样点。 图2 4 简化的采样点 天津大学硕士学位论文 第= 章些常见的立体匹配算法 另外还有一些算法致力于使用非矩形窗口进行匹配搜索，如文献 2 9 利用 一族具有相对小的周长面积比的窗口，使用最小比例循环算法( m i n i m u mr a t i o c y c l e ，m r c ) 在这些窗口中进行优化。图2 - 56 1 j ) bo l g av e k s e r 计算得到的宙口。 2 2 全局算法 图2 - 5 一个非矩形窗口 相对于窗口等局部算法，全局算法直接采用了平滑性假设，通过求解毋优化 问题来实现匹配。一般这些算法都不去执行一个单独的误差累计步骤，而是寻找 一个能够最小化全局误差函数( 包括一个数据项和一个平滑项) 的位差分布函数。 一般的误差函数基本结构为 e ( a ) = 正o ( d ) 十 占。( d )( 2 - 5 ) 其中加( d ) 为数据琐t 测量像素之问亮度或色度等的匹配程度，丘删( d ) 为平 滑项，一个典型的平滑函数为， ( d ) = 2 二p ( d ( x ，y ) 一d 扛+ l ，y ) ) + p ( d ( x ，) 一d ( x ，y + 1 ) ) ( 2 。6 ) f j l 其中p 是位差差值的单调递增函数。 2 2 1 动态规划 基于动态规划的立体算法属于全局算法，该算法将匹配问题转化为在参考图 像和匹配图像对应位置的水平搜索线上从左到右寻找最短路径的问题。算法假设 匹配过程符合顺序约束，然后在一个d s i 切片中寻找一条路径来使全局误差方程 达到最优。这个误差方程通常为最小化亮度误差并且会伴随一个“遮挡惩罚项”。 因为并没有加强搜索线之间的平滑约束单点像素的错误匹配将会影响同一扫描 线上后续像素的迎配，就使得计算出来的垃差图通常有水平“条毁”效应。f h 是， 动态编程方法在计算复杂度上大大小于其它全局算法因此也是实叫应用的一个 有利的候选，图2 - 6 给出了一个动态编程算法的基本说明。对于每一对对应的 搜索线，在上述的矩阵中选择一条匹配误差晟小的路径小写字母( 扩k ) 表不 天津大学硕j 二学位论文第二章r 一些常见的立体匹配算法 各个搜索线上的像素。大写字母表示矩阵中选择的路径。如果左右两幅图的搜索 线上对应的像素匹配，则标上m 。而那些部分被遮挡( 在其中的一幅视图中看不 见的像素) ，表示为l 或者r 。通常只考虑较小的位差范围，比如说位差d d ( q ) v p 2 q j 丁。船i 。= ( 1 0 c c rl + l o c c i ) 五一 o c c 凡= u ，p z ，i 了曰z ，：d ( p ) d ( 曰) o c c l = u 。z ，i 乙。= 0 t s m o o t h n e s s = 幽z 训，篡净删。j ( 2 - 9 ) ( 2 1 0 ) ( 2 - 1 1 ) ( 2 - 1 2 ) ( 2 - 1 3 ) ( 2 - 1 4 ) ( 2 1 5 ) 其中w ( p ) 和g ( p ) 分别为合成图像和匹配图像中的点，胁为在合成图像中，当 多点映射到同一位置时，位差值最大的点的集合，也就是可见点集合，z 。为同 一位置所有映射像素，d i s ( p i ，p ，) 在彩色图像中是r g b 三个颜色分量的绝对值之 和。 基于分层的颜色分割算法，就是通过这个误差函数，也就是优化函数，将由 段形成层的步骤反复迭代，不断将不适合某个层的段分配到另外的层中去，来得 到最后的分层结果。图2 1 1 显示了对v e n u s 的分层结果。 天津大学顾i 学位论文 第一覃些常见的立体匹配算法 2 3 本章小结 ( a ) 胤幽像 佑1 分层结果 图2 1 1 最后竹分崖纠，粜 本章介绍了局部算法耳u 全局算法两大类立体匹配算法中的一些典型算法。其 中局部算法丰要为隹口算法。简门算法是立体匹d c 算法中昂经 | 、最传统的算法 之一，它由最开始简单的矩形不变商口运渐拄展出多窗口、自适廊窗口等算法： 而全局算法的种类则很多，这里还有很多算法没有提及比如模拟退火、几何分 割等等，这些算法大部分仍然或多或少利用了_ 。个像素与周匍像柔之间的相关 性。相对来说全局算法的敬粜比局部算法要好， 叫问较慢，不过如今改良后 天津大学硕上学位论文 第二章一些常见的立体匹配算法 的窗口算法在效果上有了很大提高，故其为一种应用十分广泛的立体匹配算法。 天津大学顶l 学他论立 第三章e p i 算泣 第三章e p i 算法 r o b e r tcb o l l e s hh a r l y nb a k e r 和d a v i dhm a r i m o m 等人对静态景物的_ 二维 立体描述提出了两种想法，萁中一种是利用外极几何约束来寻找匹配的特征 点，另外一种是把一系列连续拍摄的图像紧密放置在一起。m o r a v e c 提出了将图 像序列故嚣成滑动立体f s l i d e rs t e l - e o ) 的j 醪式c 2 7 j ，e p i 算法将图像序列的数h 扩 展到了t 百幅米寻找特征点进行匹配，在找到特征点后通过图像形态学的方法 进行扭曲映射。下面介绍e p i 算法的核心步骤对于如何将特征点连结成的三角 进行映射不做研究。 3 1e p ! 的形成 e p i 算法可以分为四个步骤，f 而将按顺序介 r 吐 第一个步骤是用摄像机得到个图像序列。摄像机沿着一条与它的光轴垂直 的轴，每m 一个幽定的刚问间隔对扪擞埘像取一次像在图3 一】中，给山了这 个摄像机扪摄系统的构造。 图3 - 1 获取图像序列帕摄像机系统 在计算机的控制下可以在运动轴上准确地控制摄像机的位置。因为拍摄的 天津大学硕j ：学位论文 第三章e p i 算法 是静态对像，该方法得到的时问序列可以用来作为空间图像序列，并且得到准确 的拍摄图像的间隔距离。这种滑动立体配置是由m o r a v e c 【2 引、 b a k e r 、b o l l e s 和m 撕m o n t 【2 6 】给出的，摄像机的内部参数( 如焦距和图像中主要点的位置) 由 z h a n g t 2 9 j 提出的校准步骤得出。 当得到图像序列之后，第二个步骤便是数据重构。所谓数据重构，就是把得 到的图像序列按照图3 2 排列成一个立方体，来获取一组e p i 。 列 图3 - 2e p i 形成示意图 - - 翌曼个覆e p 器i 一个切面 然后将所有得到的图像堆成一个类似立方体的结构，一个e p i 对应于此立方 体的一个横截面。也就是说，将得到的一个序列的图像矩阵从相同的位置分别抽 出一行，将这些行按照拍摄的时间顺序从下至上排列成一幅新的图像，即一个 e p i 。 图3 3 给出了一个典型的e p i ，需要注意的是，图中的条纹代表了图像序列 中的同一个特征点，图像序列中的这些特征点在e p i 图像中连成一条条直线。这 是由于摄像机在连续的时问间隔拍摄静态物体，相当于n 台摄像机在同样的距离 间隔同时拍摄，在绪论中曾经提到过，空间中的一点，在这些拍摄到的图像中的 位置是线性变化的，因此在图像序列的数日较大时，e p i 可以清楚地显示出某个 特征点在e p i 中呈直线( 带有一定斜率) 的位置变化。 i 堡查竺堡i 竺竺堕! ! 三! ! ! ! ! 堕 囝3 4 增强边缘后n e p i 这些线段代表了3 - d 特征血。那么这些特征点的位置就可以通过在e p i 中的 位置利斜率来计算得到。敞e p l 分析得到了一系列的3 - d 特征血并且准确对麻 天津大学硕f 学化论文 第三章e r l 抖垃 于图像中亮度不连续的边缘。 不同于基于丰日关的算法，这种获_ ： 图像中特征点位差的方法不需要对应的一_ 在图像中有很强的相关关系。它只足简单对麻于e p i 图像中的直线。这样的匹配 方法提高了算法的准确性和抗干扰性。从图3 _ 4 中可以看出，即使出现某一特征 点代表的直线被另外一行直线截断，叫在实际的图像中，该点在一部分视角被其 它部分遮挡，也丝毫不影响对该直线斜率以及在原始图像序列中位置的计算。故 这种方法能够有效i i j 准确地亍璜测被遮挡部分的位芹，既而得到它在合成的新图像 中的位置。 3 3 三角分割 在笫四个步骤中采用d e l a u n a y 三角分割米将得到的特征点连接成三角形。 系统中原始图像序列都采取上述方法计算特征点的位置，之后将每幅圈的特 征点连接成三角网格。这种 法的卟很好的特性，是得到的= 角形能够比较准 确地划分圉像，而不跨越图像中的亮度边缘( f h 是实际看来，仍然有一小部分三 角形内部包括了前景物体和行景的边缘) 。也就地说划分的= 三角形很近似地刈 麻着物体表而的小平面。井h ，当图像巾有很多噩度不琏续的边缘时这种方法 能够时图像进行报细致的划分而对十无纹圳k 域j l l i | 进”简单划分。一个划分过 的图像如罔3 - 5 所小。 圈3 - 5d e l a 曲a y 二珀划分后的图像 天津大学硕士学位论文第三章e p i 算法 在这一步骤的最后，利用了图像变形来合成两个视角中的新图像。但本文并 不采用这种方法合成新图像。并且，在第一步骤中，为了合成e p i ，摄像机拍摄 了5 0 0 幅图像的大序列来组成数据库。图像数目的增多有利于提取e p i 及提取特 征点。但对于合成新视点来说，如此庞大的数据量并不是必须的。在本文研究的 算法中，只利用了典型测试序列的9 幅图像来构建e p i ，并且根据z b u f f e r 算法 的需要，对序列中的2 幅图像进行了三角分割，然后通过计算位差图( d s i ) 来 合成新图像。 3 4 本章小结 本章介绍了e p i 算法的核心概念以及基本步骤。e p i 能够比较直观准确地表 现边缘部分的位差信息，并且在理论上对遮挡部分的位差有很好的预测效果。 天津大学硕士学位论文第四章基于m e a n s h i f t 的颜色分割 第四章基于m e a n - s hif t 的颜色分割 m e a ns h i f t 概念最早由f u k 加a g a 等人在1 9 7 5 年在一篇关于概率密度梯度函 数的估计中提出，就是偏移的均值向量。c o m a n i c i u 年i m e e r ( 3 2 1 将m e a ns h i f t 运用于 特征空间的分析。c o m a n i c i u 等人在文章中证明了m e a ns h i f t 算法在满足一定条件 下，一定可以收敛到最近的一个概率密度函数的稳态点。c h r i s t o p h e r , b o g d a n g e o r g e s c u 和m e e rt 3 3 糯j ：m e a ns h i f t 算法用于颜色分割和边缘提取。 4 1 密度梯度估计 4 1 1 核函数 无参密度估计一般也称为非参数估计，属于数理统计学的一个分支。形成于 2 0 世纪4 0 年代。常见的非参数估计技术有：直方图法、最近邻域法及核密度估 计法。 2 0 世纪5 0 到6 0 年代，提出了核密度估计方法。即对一组采样数据，把数 据的值域分成若干相等的区间，数据按区问分成若干组，每组数据的个数与总参 样个数的比率为每个区问的概率值。这种方法运用了核函数。 所谓核函数，也称为窗口函数。常见的有均匀核函数、三角核函数， e p a n e c h i k o v 核函数、双权核函数、高斯核函数等等。常见的核函数图形见图4 1 。 u n i f o r mu ( - 1 ，1 ) t r i a n g l e1 一l ， 天津大学硕士学位论文第四章基于m e a n - s h i f t 的颜色分割 图4 - 1 几种常见的核函数 g a u s s i a nn ( o ，1 ) 核函数都遵循一些基本特征：对称，单峰，有限局部支撑。 4 1 2 核密度估计 核密度估计：给定一组r 1 个d 维欧几里德空i 司r 。的点 薯 ，： 数k ( x ) 和窗口半径厅在x 点计算得到的多元核密度估计为 夕( x ) = 万1 台 = 二a 。t x - x i ) 定义密度梯度估计为核函数密度梯度估计，则 移( x ) = 嗍) - m i _ _ ! z 百争v k ( x - ，7 x , ) 对e p a n e c h n i k o v 核函数来说，( 3 2 ) 式可写为 影( 加而1 丁d + 2 而豺 。，那么由核函 ( 4 - 1 ) f 4 2 2 丽g 训d 矗+ 。2 ( 1 以玉戮矿如 ( 4 - 3 ) s h ( x ) 是以x 为中心，半径为h 的超球面，体积为h e 白，内含仇个数据点。令 鸲 净亡而磊。，k 叫卜去而磊，葺叫 ( 4 4 ) 蛳功黼m e 圳m 啪量酌高艄馓醐秘崩帆蝴嬲面 s ( x ) 得到的核密度估计，所以( 4 4 ) 可以写成 盯( x ) = 衲下d + 2 地( 工) ( 4 - 5 ) 蛐) = 是鬻 ( 4 6 ) 天津大学硕士学位论文第四章基于m e a n - s h i f t 的颜色分割 ( 4 6 ) 说明m e a ns h i f t 向量与在x 点处得到的核密度梯度估计方向一致，即m e a n s h i f t 向量总是指向密度增加最大的方向，它给出了一个指向密度增加最大的路 径。如图4 2