（信息与通信工程专业论文）基于cuda的立体匹配及去隔行算法.pdf

浙江大学硕士学位论文摘要 摘要 立体视觉是计算机视觉领域中的一个研究热点，是被动深度测量的重要方 法。立体匹配是立体视觉中的重要步骤，也是难点之一。本文对实时立体匹配算 法进行了研究。在立体匹配算法中，基于区域的局部匹配方法运算简单规整，适 合于硬件加速实现，且能够得到致密的视差图。匹配窗口的合理选择直接影响到 匹配的效率和准确性，但使用适当的立体匹配加速方法可以使算法复杂度大大减 小。 在典型的视频监控场景中，有人的走动和车辆的快速移动，监控摄像机的隔 行扫描使得人和车辆边缘模糊，视频图像质量下降。为了获得清晰的监控视频， 需要将隔行扫描信号转成逐行扫描信号。主流效果较好的去隔行方法有运动自适 应和运动补偿两种，本文对这两种方法都进行了研究。运动自适应中采用同极性 4 场运动检测法提取运动信息，将图像分为静止区域、运动区域和混合区域；对 静止区域采用直接的场合并，对于运动区域采用改进的基于边缘的插值，混合区 域则采用基于运动向量的加权平均。运动补偿去隔行算法采用双向运动估计法， 根据运动矢量的幅值将场图像块分成三类，快速运动的块采用基于边缘的场内插 值，较慢的块采用沿运动矢量的线性平均，中间速度的块再细分，判断后采用上 述两种方法之一进行插值计算。 c u d a 是n v i d i a 公司发布的用于g p u 的通用计算开发环境和软件体系， 借助于g p u 强大的运算能力，可实现并行处理。本文基于c u d a 对立体匹配及 去隔行算法进行加速。在立体匹配中，比较了不同算法结构通过c u d a 加速在 性能上的区别。对于去隔行算法，进行了有针对性的算法结构调整，对运动自适 应去隔行中的运动检测和运动补偿去隔行中的运动估计进行了c u d a 加速，取 得了很好的结果。 关键字：立体匹配；去隔行；运动自适应；运动补偿；c u d a i i 浙江大学硕士学位论文 a b s t r a c t h b st l a c t a sa ni m p o r t a n tp a s s i v ed e p t hm e a s u r e m e m ，s t e r e ov i s i o ni so n eo ft h er e s e a r c h f o c u s e si nt h ef i e l do fc o m p u t e rv i s i o n s t e r e om a t c h i n gi sak e ys t e pf o rs t e r e ov i s i o n t h et h e s i si n v e s t i g a t e sh o wt od e s i g nar e a l - t i m es t e r e om a t c h i n gm e t h o d a m o n g r e l a t e dl i t e r a t u r ec o n c e m i n gm a t c h i n ga l g o r i t h m s ，l o c a la r e ab a s e dm a t c h i n gm e t h o d h a sa d v a n t a g eo fs i m p l eo p e r a t i o n sa n dh a r d w a r el o g i cc i r c u i ti m p l e m e n t a t i o n t h e s e l e c t i o no fm a t c h i n gw i n d o wh a sas i g n i f i c a n ti n f l u e n c eo nt h em a t c hr e s u l t f u r t h e r m o r e ，p r o p e ra c c e l e r a t i o nm e t h o dc a nb eu s e dt or e d u c ec o m p u t a t i o n a lt i m e i nt h et y p i c a ls u r v e i l l a n c es c e n e ，t h e r ea l ed y n a m i co b j e c t s ，l i k em o v i n gc a r sa n d p e d e s t r i a n s t h ei n t e r l a c e ds c a no fs u r v e i l l a n c ec a m e r a si st h em a i nf a c t o rf o rv i d e o q u a l i t yd e t e r i o r a t i o n t h u sd e - i n t e r l a c i n ga l g o r i t h mi sr e q u i r e dt oc o n v e r ti n t e r l a c e d v i d e oi n t op r o g r e s s i v es c a nf o r m a tf o rf u t u r ep r o c e s s i n g c l a s s i c a ld e i n t e r l a c i n g m e t h o d sm a i n l yi n c l u d e sm o t i o na d a p t i v ed e i n t e r l a c i n ga n dm o t i o nc o m p e n s a t e d d e i n t e r l a c i n g b o t ha r ea n a l y s i z e di nt h et h e s i s m o t i o na d a p t i v em e t h o de m p l o y st h e s a m e - p a r i t y4 - f i l e dm o t i o nd e t e c t i o nt oe x t r a c tm o t i o ni n f o r m a t i o n t h e nt h ei m a g ei s d i v i d e di n t ot h r e ep a r t s ：s t a t i ca r e a , m o t i v ea r e aa n dm i x e da r e a t h ea l g o r i t h m i m p l e m e n t sf i e l dm e r g i n gi ns t a t i ca r e a , e n h a n c e se d g e d e p e n d e n ti n t e r p o l a t i o ni n m o t i v ea r e aa n dp e r f o r m sm o t i o nv e c t o rb a s e dw e i g h t e da v e r a g ei nm i x e da r e a m o t i o n - c o m p e n s a t e dd e i n t e f l a c i n gu s e sb i l a t e r a lm o t i o ne s t i m a t i o na n dt h e nd i v i d e s f i e l db l o c k si n t ot h r e ep a r t sb a s e do nt h em o t i o nv e c t o r t h ea l g o r i t h mi m p l e m e n t s e n h a n c e de d g e d e p e n d e n ti n t e r p o l a t i o nf o rf a s tm o t i o nb l o c k sa n dl i n e a ra v e r a g e a l o n gt h em o t i o nt r a je c t o r yf o rs l o wm o t i o nb l o c k s o t h e rb l o c k sa r ed i v i d e di n t o s m a l l e rp a r t sb yu s i n go n eo ft h et w oi n t e r p o l a t i o nm e t h o d s c u d ai si n t r o d u c e db yn v i d i a i ti sa p o w e r f u lg e n e r a lp u r p o s ep a r a l l e l c o m p u t a t i o na r c h i t e c t u r ew i t has o f t w a r ee n v i r o n m e n to fg p u i ta l l o w sp a r a l l e l p r o c e s s i n g 、衍t 1 1t h eh e l po ft h ep o w e r f u lg p up a r a l l e lc o m p u t a t i o n a lc a p a b i l i t y b a s e do nc u d a ，t h et h e s i sc a na c c e l e r a t e sp r o c e s s i n gt i m eo fs t e r e om a t c h i n ga n d d e i n t e r l a c i n ga l g o r i t h me f f e c t i v e l y i tm a k e sac o m p a r i s o nf o rt h ec u d ap e r f o r m a n c e i i i 浙江大学硕士学位论文 a b s t r a c t b e t w e e nd i f f e r e n ta l g o r i t h ms t r u c t u r e so fs t e r e om a t c h i n g a l g o r i t h ms t r u c t u r e a d j u s t m e n ti sc a r r i e do u tf o rd e i n t e r l a c i n ga l g o r i t h m a n dag o o d r e s u l ti so b t a i n e df o r m o t i o nd e t e c t i o nw i t h i nm o t i o na d a p t i v em e t h o da n dm o t i o ne s t i m a t i o nw i t h i nm o t i o n c o m p e n s a t e dm e t h o d a f t e rc u d aa c c e l e r a t i o n k e y w o r d s ：s t e r e om a t c h i n g ；d e i n t e r l a c i n g ；m o t i o na d a p t i v e ；m o t i o nc o m p e n s a t e d ； c u d a 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的 研究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其 他人已经发表或撰写过的研究成果，也不包含为获得堑江盘堂或其他教育机 构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献 均已在论文中作了明确的说明并表示谢意。 学位论文作者签名：声乳于岛 签字同期：l o o 年弓月g 日 学位论文版权使用授权书 本学位论文作者完全了解逝姿态堂有关保留、使用学位论文的规定， 有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和 借阅。本人授权盘姿盘堂可以将学位论文的全部或部分内容编入有关数据库 进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名：参乱编 导师签名： 签字目期：二。0 年岛月召日签字同期： 劢( c 年5 月7 日 学位论文作者毕业后去向： 华内 工作单位：华南寸叉? k 看限公司7 随十 l 研唬卢i 电话：f 5 8 6 8 牛弓2 4 6 1 6 通讯地址：杭州市滨江区滨玳路o f 号慧滩邮编：弓l 。d 砬 致谢 在攻读硕士学位期间，有幸师从杜歆老师，杜老师给了我求学深造、参与前 沿技术研究的机会。杜老师渊博的知识、严谨的治学态度和对学科前沿与研究方 向敏锐的洞察力将使我受益终身。正式由于杜老师的精心指导，我才得以树立明 确的目标，打下扎实的理论基础，培养了良好的学习方法和研究习惯，启发了创 造性的思维。 此外还要感谢实验室的一起工作学习的朋友们，感谢他们真诚的关心和鼓 励，感谢他们毫无保留的传授经验。他们是王倩、张飞、王迅、陈国赞，以及已 经毕业的凌波、吴婧、许慧等。感谢一起走过两年半研究生生活的好朋友陈建娟、 童丸丸、蔡立凤，生活因她们而快乐，并祝她们一路顺风。 最后感谢我的父母及家人对我的关心和照顾，是他们的支持和鼓励促使我不 断学习进取，始终保持积极乐观的态度，顺利完成学业。感谢所有关心、帮助和 鼓励我的老师、亲人和朋友。 颜瑞 2 0 1 0 年1 月1 4 日 浙江大学硕七学位论文基于c u d a 的立体匹配及去隔行算法 1 1 立体匹配概述 1 1 1 立体匹配研究背景 第一章绪论 视觉是人类获取信息的最有效手段，场景中的光线在人眼这个精密的成像系 统中被采集，通过神经中枢被送入大脑中处理，得到实时的高准确度的深度信息， 从而使人类在不同的环境中完成各种复杂的运动。计算机立体视觉就是用计算机 模拟人的视觉功能，通过两台或多台图像传感器获得同一场景的不同图像，计算 场景中物体的深度信息n 1 。 目前，计算机视觉是一个非常活跃的研究领域，在计算机科学、三维场景重 建等领域发挥着重要作用，可以说，需要人类视觉的场合几乎都有立体视觉的研 究存在。然而在很多应用场合，立体视觉的实时性非常重要，如机器人导航、目 标跟踪、工业自动化控制等。在立体视觉中立体匹配算法是其中的关键核心，本 文研究的内容之一就是立体匹配算法的鲁棒性及实时性实现。 1 1 2 立体视觉原理 立体视觉基本概念是根据视差理论，运用两个或者多个摄像机对目标场景摄 取一组同一时刻不同视角的图像，通过各种算法匹配出对应的像点，从而计算出 视差，进一步得出场景的深度信息。 1 1 2 1 视差理论 由于双眼的观测角度稍有不同，使得物体在两眼视网膜上投影的位置不同， 所以人眼在观察场景时可以感知到被观测物体的距离，这个位置差就被称为双目 视差( b i n o c u l a rd i s p a r i t y ) 。视差反映了物体的深度信息，人所感知的深度是大 脑在视差的基础上进行加工而得出的。根据这个原理，在计算机视觉中，我们使 用多个摄像机获取一组不同视角的图像，如图1 1 所示，通过匹配算法求取图像 对的匹配点，计算出视差，再根据三角测量方法得出场景深度。 浙江大学硕士学位论文基于c u d a 的赢体匹配及去隔行算法 z = 厂吾 ( 1 1 ) 其中d = 工一x ，即该点的视差，基线为b ，相机焦距为f 。由此成像模型 可知，正确求取视差是得到物体深度信息并恢复出场景三维结构的关键。 图1 1 立体视觉成像模型 1 1 2 2 立体匹配前期工作 立体匹配是通过获取图像间的匹配点，进而计算出视差的过程。在立体匹配 前，需要进行两个前期工作，一是摄像机标定，二是图像校正。 摄像机成像是确定三维物体影像的过程，而立体视觉面对的是它的逆问题， 即由影像恢复出三维物体表面信息的问题。由于从三维世界向二维影像投影的过 程中丢失了大量的信息，立体视觉系统中必须引入一些约束条件才能获得确定的 解，常用的约束条件有脏3 1 ： ( 1 ) 外极线约束( e p i p o l a r c o n s t r a i n t ) ：根据透视投影成像的几何原理，对应的 匹配点一定是位于另一幅图像对应的外极线上，立体图像对经过外极线校正后， 外极线与图像行重合，匹配点搜索只需沿图像的扫描线进行，从而将二维搜索空 间降至一维。 ( 2 ) 唯一性约束( u n i q u e n e s sc o n s t r a i n t ) ：一幅图像上的一个特征点只能与另 一幅图像上唯一一个特征点相对应。 ( 3 ) 相似性约束( s i m i l a r i t yc o n s t r a i n t ) ：场景中同一点在图像对中的投影点应 该具有相似的亮度值。 ( 4 ) 平滑性约束一致性约束( s m o o t h n e s s c o h e r e n c ec o n s t r a i n t ) ：除了遮挡和 视差本身不连续的区域外，小邻域范围内视差值的变化量应很小或者相似，即视 差曲面应是分段连续的。 2 浙江大学硕士学位论文 基于c u d a 的立体匹配及去隔行算法 ( 5 ) 视差范围约束( d i s p a r i t yl i m i tc o n s t r a i n t ) ：人类的视觉系统只能接受视差 小于某个值的立体图像，该约束限制了寻找对应点时的搜索范围。 ( 6 ) 顺序约束单调性约束( o r d e r i n g m o n o t o n i c i t yc o n s t r a i n t ) 。 ( 7 ) 遮挡约束( o c c l u s i o nc o n s t r a i n t ) 。 ( 8 ) 互对应约束( m u t u a lc o r r e s p o n d e n c ec o n s t r a i n t ) 。 为了降低立体匹配算法的复杂度，提高匹配的准确性，一般根据上述的外极 线约束，对两幅图像进行校正，校正后立体图像对的外极线具有平行且水平的特 性。在此约束下，匹配点已经位于两幅图像对应的外极线上，立体匹配的视差搜 索范围由二维图像降为一维外极线。图像的校正需要根据摄像机的内外参数处 理，参数是由摄像机标定获得的。 三维空间中每一点在图像上的位置是由空间物体表面相应点的几何位置与 摄像机成像几何模型共同决定的，该几何模型的参数称为摄像机参数，这些参数 必须由实验计算来确定，实验与计算的过程被称为摄像机标定h 。对于目标跟踪 等领域立体视觉系统来说，有效视野区为双目摄像机视野重叠的区域。为了扩大 视野范围，必须使用较短焦距的摄像机镜头，而较短焦距的镜头会引入严重的非 线性畸变，摄像机标定的另一个目的是消除镜头畸变所带来的影响。 1 2 去隔行概述 1 2 1 去隔行研究背景 去隔行处理根源于电视信号的历史原因。隔行扫描广泛应用于不同的电视标 准中，包括n t s c 、p a l 和s e c a m 。电视系统利用人体视觉系统对视频图像小 面积闪烁没有对大面积闪烁敏锐的特性，在有限的传输带宽内提供尽可能高的垂 直分辨率，同时消除由低帧率引起的视频图像闪烁问题。 但是隔行扫描带来许多视觉缺陷，概括起来主要有爬行、行间闪烁和锯齿效 应等。爬行出现在没有运动和细节较少的视频图像中，由于每条扫描线每帧只更 新一次，新的扫描线在旧的扫描线之间出现，看起来似乎这一组扫描线向上或是 向下移到了一个新的位置。行间闪烁主要和细节及水平边缘有关，精细的水平边 沿只能在一场中出现在另一场中消失，从而产生闪烁的感觉。锯齿效应包括两方 浙江大学硕上学位论文基于c u d a 的立体匹配及去隔行算法 面，一是在静止或运动较少的视频图像中由于较低的垂直分辨率引起台阶效应， 二是由于每场只有一半的行数进行更新，导致运动图像损失了边缘细节，当边缘 动起来之后，下一场边缘就会有位移，锯齿状的边缘就这样产生了。 近年来以液晶显示器( l c d ) 、等离子体平板显示器( p d p ) 为代表的逐行 扫描显示器得到了飞速发展，只有将隔行的原始视频转换成逐行视频后才能在这 些显示器上有效显示；而且，目前h d t v 系统为了提供更好的图像质量支持逐 行扫描。为了能与现存的t v 和摄像机系统兼容，去隔行算法应运而生。 随着数字视频压缩编码技术的日益成熟和p c 机的普及化，视频监控从过去 的模拟处理方式转向数字处理方式，开始使用计算机处理图像信号。隔行扫描技 术在监控摄像机中也有应用，本文也针对监控摄像机的视频去隔行问题进行了研 究。 1 2 2 去隔行原理 访刚戤d i _ n - i n 刚獬d 图1 2 视频去隔行模型 如果把隔行扫描看作一种时空二次采样的话，那么将隔行视频转化为逐行视 频的去隔行过程就是它的逆过程。时间方向上的视频信号场结构如图1 2 所示， 视频信号按奇偶场的次序依次传输b 1 ，每隔一场极性相同。去隔行就是经过插值 将场转化为帧，这些帧和场表示的是同一幅图像，所不同的是帧包含所有的行。 去隔行算法用公式可以表示为： c g ，y ；刀，= 长羔暑 少m o d 2 = n m 。d 2 ( 1 2 ) 0 t h e r w i s e 其中g ，j ，) 为二维空间的位置坐标，z 为场序号，f g ，少；玎) 表示输入场，它只有 4 浙江大学硕上学位论文 基于c u d a 的立体匹配及去隔行算法 在ym o d 2 = n m o d 2 时才有信号，即偶场的偶行像素和奇场的奇行像素， f b ，y ；挖) 表示插值场，f o ( x ，y ；刀) 表示对应的完整的帧。 视频去隔行算法的基本原理就是利用待插值场和其它场信息求解 z ( x ，y ；n ) ，最大限度的恢复出逐行扫描图像，改善画面质量。 1 3 算法实现硬件平台 实时立体视觉算法要求算法处理的速度要快，但立体匹配一般具有较大的计 算量。以区域匹配算法为例，假设n n 大小的灰度图像，相关窗口尺寸为w w ， 视差搜索范围d 为例，直接计算的复杂度为o ( n 2 w 2 d ) 。通过一定的优化算法虽 然可以减小冗余计算，使复杂度降至o ( n 2 d ) 7 1 ，但仍旧无法满足实时性要求。 针对立体匹配的加速问题，已有大量学者提出了解决方案，大体上可以将硬 件加速方法分为两类，一是基于指令集结构的p c 或者d s p 实现，例3 2 0 n a s a 火星 车( m a r se x p l o r a t i o nr o v e r ，m e r ) 使用r a d 6 0 0 0 计算机，最高频率2 5 m h z ，计 算一次2 5 6 2 5 6 图像对的匹配需3 0 s 睛1 ；二是利用f p g a 或者开发专用集成电路， 如北京理工大学研发的微型立体视觉机( m i n i a t u r es t e r e ov i s i o nm a c h i n e ， m s v m ) 使用三目c m o s 摄像头，可以在一片f p g a 上完成图像校正、滤波预处 理及基于区域的图像匹配侈1 。 视频去隔行也是一种对实时性要求很高的应用，算法处理时间必须小于每场 的刷新间隔时间，以往的加速解决方案与立体匹配类似“n 上述加速解决方案虽然有其优势，但也有一定的局限性。一般基于指令的系 统可以通过调整指令结构达到优化程序性能的目的，但是不适合大数据流的操 作。d s p 是通用处理器和f p g a 两者的折衷，由于指令的并行化程序不高，性能 方面较欠缺。对于f p g a 来说，非常适合并行特征任务的处理，但f p g a 缺乏高 级语言的支持，可编程性较差，开发复杂的立体视觉算法较困难。专用集成电路 由于投入高，开发周期过长也难以普及。 g p u 作为图形显示卡的计算引擎，具有高度的可程序化能力，由于g p u 具有 相当高的内存带宽，以及数量众多的执行单元，正逐渐引起了学者们的重视，被 浙江人学硕上学位论文 基于c u d a 的立体匹配及去隔行算法 作为协处理器用到了数值计算的各个领域，即g p g p u ( g e n e r a lp u r p o s eg p u ) 。 c u d a ( c o m p u t eu n i f i e dd e v i c ea r c l l i t e c t u r e ，计算统一设备架构) 是n v i d i a 公 司于2 0 0 7 年正式发布n2 1 ，不需要借助图形学a p i 就可以使用类c 语言进行通用计 算的开发环境和软件体系，与以往的传统g p g p u 开发方式相比，具有编程更加 方便，功能更加完善的优点。 1 4 本文主要研究内容 本文研究了两个主要内容，一是以实时立体视觉为研究背景，探讨了实时立 体匹配算法及其在c u d a 上的加速；二是研究了隔行摄像机的视频去隔行方法以 及c u d a 加速。各章的具体内容安排如下： 第一章绪论部分介绍了立体视觉的研究背景，着重介绍了立体视觉的基本原 理。同时对隔行视频的缺陷和去隔行的基本原理进行了介绍。最后概括了两者相 关的加速研究方案，并对各方案的缺陷进行了分析。 第二章介绍了立体匹配方法的研究，重点在于易于硬件实现的区域匹配，突 出了算法的实时性要求。整个研究内容包括：相似度度量因子、匹配窗口大小以 及区域法立体匹配加速技巧，并采用标准人工合成立体图对进行了定性分析。重 点突出在强实时性要求的背景下且易于硬件加速实现的立体视觉算法的研究，确 定了立体匹配实现方案。 第三章分析了常用的视频去隔行算法，主要讨论性能较好的运动自适应和运 动补偿去隔行算法及在监控视频中的应用。在运动自适应去隔行算法中，通过同 极性4 场运动检测法来提取运动信息，将图像分为静止区域、运动区域和混合区 域。对静止区域采用直接的场合并，对于运动区域采用改进的基于边缘的插值， 混合区域则采用基于运动向量的加权平均，使得效果得到较大的提高。运动补偿 去隔行算法则采用了双向运动估计法，根据运动矢量的幅值将场图像块分成三 类，快速运动的块采用基于边缘的场内插值，较慢的块采用沿运动矢量的线性平 均，中间速度的块再细分，判断后采用上述两种方法之一进行插值计算。 第四章为c u d a 加速方案的具体实现。首先通过对c p u 和g p u 硬件结构的分 析，总结出各自更适于执行的数据处理任务类型。同时，以g e f o r c e9 8 0 0g t x + 为例详细说明了n v i d i a 的g p u 架构，并详细介绍了在该型号g p u 上c u d a 的执 6 浙江大学硕士学位论文基于c u d a 的立体匹配及去隔行算法 行模型、存储器模型以及常用的程序优化方法。其次对立体匹配算法的c u d a 实 现方案进行介绍，涉及采用加速算法的立体匹配和没有采用加速算法的立体匹配 两部分，对处理的时间结果进行分析。最后对去隔行算法的c u d a 实现方案进行 介绍，针对g p u 的处理性能，只对运动自适应去隔行中的运动检测和运动补偿去 隔行中的运动估计进行加速，并采用自然场景监控视频对两种去隔行算法的处理 效果和加速时间进行分析。 第五章为全文总结及后续工作的展望。 浙江大学硕士学位论文基于c u d a 的立体匹配及去隔行算法 第二章双目立体视觉匹配算法 在双日立体视觉中，立体匹配是寻找三维空间中同一物体在不同视点下投影 图像间的一一对应关系，即给定一幅图像上的已知点( 源匹配点) 后在另一幅图 像上寻找与之相对应的目标匹配点( 同名像点) ，使这两点都是空间中三维物体 上同一点在摄像机图像中的投影点，从而获取视差。立体匹配技术是立体视觉中 研究的核心问题。 2 1 匹配基元的选择 视差的求取需要根据匹配基元寻找对应的匹配点，匹配基元的选择是立体匹 配中首先要解决的问题。匹配基元是指用以进行匹配的图像特征，由于立体成像 的视点差异以及噪声干扰等因素的影响，要对图像对中的所有像素都进行无歧义 的匹配是很困难的，因此，应该选择能表征物体属性的特征为匹配基元h 1 。根据 匹配基元的不同，目前立体视觉匹配算法主要分为两类：区域匹配、特征匹配 【1 4 - 1 7 】 ( 1 ) 区域匹配 区域匹配是目前最简单、最易于实现的匹配方法，它的基本思想是以统计的 观点将图像看作二维信号，采用统计相关的方法，利用图像上局部区域的相关性 来确定两个对应点间的匹配关系。 因为单个像素的灰度值不能够提供足够多的信息，区域匹配先以基准图中一 个像素点为中心创建一个窗口，用邻域像素的灰度值分布来表征该像素，然后从 待匹配图中寻找对应的像素，以其为中心创建相同大小的窗口，计算左右视图对 应像素点的相似性。若两者具有匹配的关系，两者问的相似性必然满足一定的阂 值关系。 ( 2 ) 特征匹配 在提取图像显著特征的基础上，特征匹配旨在建立这些稀疏特征之问的对应 关系。作为匹配基元的特征分为两类：局部特征和全局特征。局部特征包括点、 边缘、线段、小面和局部能量。全局特征包括多边形和图像结构等。基于特征的 浙江大学硕士学位论文基于c u d a 的立体匹配及去隔行算法 匹配一般分为特征提取和定位、特征描述、特征匹配三个步骤。特征的提取减少 了匹配基元的数目和匹配的模糊度，从而减少了匹配问题的复杂度。由于有些特 征提取( 如边缘提取) 可以达到亚象素精度，因而也提高了匹配精度。 匹配基元应根据具体的应用背景来选择。实时性是实时立体视觉系统中非常 重要的指标，即算法处理的速度要快。基于特征的匹配算法处理立体视觉问题十 分鲁棒，但是特征在图像中的稀疏性决定了特征匹配只能得到稀疏的视差图，要 获得致密视差图必须辅以插值过程。为了确保插值点的精确度，插值过程往往较 为复杂，特征的提取与定位过程也比较耗时，算法整体实时性不高。区域匹配算 法计算复杂度不高，匹配速度可以很快，计算结构易于硬件加速，所以本文将关 注于基于局部区域的立体匹配算法的研究。 2 2 确定相似度度量因子 在双目立体视觉立体匹配研究中，为了对匹配的结果进行判断，需要选取适 当的相似性测度。相似性测度可以表达为一种求解匹配代价值的函数形式，对立 体匹配判断的正确与否至关重要。基于区域匹配的常用度量因子有三类：互相关 ( c r o s sc o r r e l a t i o n ) 、灰度差( i n t e n s i t yd i f f e r e n c e s ) 和排列( r a n km e t r i c s ) 1 ， 下面以左图像( 基准图) 1 1 0 ，v ) 和右图像( 配准图) ，0 ，1 ，) 为例分析这三种度 量因子的性能。 对于区域匹配来讲，当图像对的对应点间存在尺度变化或直流分量的差异 时，相关系数有助于去除此类线性畸变。最常用的互相关度量因子为归一化灰度 互相关方式( n o r m a l i z e dc r o s sc o r r e l a t i o n , n c c ) ： c 鼎咖蕃趔糍t u 鬻t 牒ud 尸 z ， 、仃厂，炒；+ ，v j 式( 2 1 ) 中，仃? 0 ，v ) 和仃； ，v ) 分别是左右图像匹配窗口的方差，五g ，v ) 与 7 ，g ，v ) 是窗口内像素灰度的均值。从式中可以看出，该度量因子计算量大，且 包含开方等复杂运算，不太适合硬件加速实现。 灰度差方式比互相关方式运算简单，其中灰度差绝对值( s u mo fa b s o l u t e d i f f e r e n c e s ，s a d ) 以及灰度差平方方式( s u mo fs q u a r e dd i f f e r e n c e s ，s s d ) 广泛应 9 浙江大学硕上学位论文基于c u d a 的立体匹配及去隔行算法 用于实时立体匹配系统中，计算结构规整，适合并行加速实现： c 0 ，v ) = i ，0 ，v ) - i ，0 + d ，v 】 甜v c s 劬 ，v ) = o ，u ，v ) 一， + d ，v ) ) 2 掣p ( 2 2 ) ( 2 3 ) 非参数化区域变换的基本思想是定义一种局部的图像变换，这种变换能够反 映像素局部的变化信息，且图像对中相关点的变换结果是相似的。非参数化区域 变换考察灰度排列信息而非灰度值本身，对亮度偏差等影响具有较好的鲁棒性。 c e n s u s 变换是常用的非参数化区域匹配算法之一n 引，是对局部空间结构的度量。 对于图像中的某个像素点p ，0 ) 表示该点的灰度值，( 尸) 表示该点某个 半径为d 的邻域内像素点的集合。c e n s u s 变换是将邻域p ) 内的像素映射为一 个比特串，定义映射关系为孝( 尸，p ) ： 舢) = ：i ，裂 4 ， p ) 内所有的孝p ，p ) 顺序相连得到比特串： c p ) = 砭多善( 尸，尸+ f ，歹d ( 2 5 ) d ，j _ | d 其中0 表示比特串联。c e n s u s 变换后的图像使用汉明距离( h a m m i n gd i s t a n c e ) 计算相似度，即两个比特串中不同比特的数目。 c e n s u s 变换可以很好的反映图像的纹理特性，克服了传统参数式匹配算法 在视差不连续区域产生的匹配歧义性问题。运算结构比较单一，涉及像素值的比 较及汉明距离计算，适合大规模并行加速的实现。 从实时性角度考虑，本文将讨论s a d 、s s d 及c e n s u s 变换算法的实现。 2 3 匹配窗口选取 由于基于单个像素的匹配不可靠，区域法采用相关窗口区域来替代单个像素 进行度量。基于区域的立体匹配方法基于这样一个重要假设，就是匹配窗口内像 素的视差值是相同的。匹配窗口的选取受两个矛盾条件的限制：为了获得可靠匹 配，应选择足够大的匹配窗口，使其能包含足够多的图像信息以提高匹配窗口内 的信噪比；但是如果窗口过大，由于覆盖了视差不连续区域造成对这一假设的违 浙江大学硕士学位论立基十c l r d a 的立体配厦击隔行算祛 背。因此，对于立体匹配来说合理地选择匹配窗口的尺寸至关重要 5x5 变换窗口1 1x 1 1 变换窗口17x 17 变换窗口 浙大学硕学位论文 基于c o d a 的立体配及去隔行算法 7x7 匹配窗口 1 1x 1 1 匹配窗口i 5x 1 5 匹配窗口 图22c e n s u s 窗口不同尺寸的选取 c e n s u s 方法中除了匹配窗口的选取以外，还涉及到变换窗口的选取。c e n s u s 变换窗口描述了图像像素的邻域信息，如图2 2 所示，上半部分匹配窗口固定为 1 1x 1 1 ，c e n s u s 变换窗口越大，包含的灰度相对信息越多，匹配越准确；下半部 分c e r l s u s 变换窗口固定为9x9 ，随着匹配窗口的增大，噪声得到有效抑制，效 果明显变好，相对于c e n s u s 变换窗口的变化而言，匹配窗口的改变对整个匹配 结果的影响更大。但是c e n s u s 变换后的比特串要参与匹配，比特串的大小随窗 口宽度w 增加呈o ( w 2 ) 增长，需要占用更大容量的存储器以及占用更多的数据读 取时间窗口的选取应从计算量及性能方面综合考量，最终将在第四章加速中根 据硬件条件讨论c e i l s u s 变换窗口的大小。 2 4 区域立体匹配加速算法 基于区域的立体匹配计算复杂度较高，按原始计算量来说，窗口增大，计算 代价也随之增加。对于n n 大小的双目图像对，当匹配窗口尺寸为w ，视差搜 索范围为d 时，直接计算的复杂度为l 爿_ 2 w2 d ) ，因此，匹配的加速尤为重要。 2 4 1 金字塔多分辨率匹配 金字塔多分辨率匹配是立体匹配中的一种常用加速技巧”，其基本原理是将 图像分解为一组多分辨率图像，匹配搜索时，先对目标在粗分辨牢图像上进行粗 略定位，然后将匹配结果作为预测值，传到较低一级分辨率的图像上，这时搜索 浙江大学硕士学位论文基于c u d a 的立体匹配及去隔行算法 区域仅限制在上一级中粗略定位点的邻域，依次逐级处理，精度不断提高，直到 最底层图像为止。其加速的实质是减少了高分辨率匹配时视差的搜索范围，同时， 由于视差搜索范围的减少，降低了误匹配的发生概率。 l e ri m a g e r i g h ti m a g e 图2 3 金字塔模型 l e v e l2 l e v e l1 l e v e l0 金字塔多分辨率匹配要根据事先确定的金字塔级数k 和逐级缩放比例，来构 造图像金字塔，高层金字塔可以通过对低层图像厂，区域的像素平均获得，如图 2 3 所示。由下到上每一级金字塔图像的像素数目减少到低一级的，2 分之一，视 差搜索范围降为低一级的，分之一。对高层金字塔( 低分辨率图像) 进行立体匹 配时，由于像素数目的减少和视差搜索范围的降低，匹配可以很快完成。最后将 高层金字塔的匹配结果通过线性插值传播到低一级金字塔( 高分辨率图像) ，视 差的搜索可以限制在一个很小的范围之内，这样逐级传播，直至匹配完成。 由于视差搜索范围与立体匹配的计算复杂度成正比，因此缩小这个范围可以 大大减少计算时间。 2 4 1 盒滤波技术加速 匹配窗口在图像上滑动时每次只改变部分像素，无需对窗口内所有数据重新 计算。盒滤波就是基于上述思想，在计算窗口匹配代价时利用前一个窗口的累加 结果，从而消除了冗余计算哺1 ，如图2 4 所示。以s a d 算法为例，设s a d ( x ，y ，d ) 是左图中点g ，y ) 在视差搜索为d 时的s a d 值，窗口大小为( 2 n + 1 ) x ( 2 ，2 + 1 ) ，则 1 3 浙江大学硬士学位论文基于c u d a 的立体匹配厦去隔行算法 s a d ( x ，* d ) 可以由下式得到： t 毗弘d ) = 姐虹一1 ，y , d ) + c o l ( x + n ，y ，d ) ( 2 6 ) 也就是田2 4 中的下半部分，其中，c o t ( x ，几种表示匹配窗口移动中最新一列与 最早一列的s a d 值之差，同时它在垂直方向满足如下规律： 例d 讹) = c o l ( y x , 制y - l , d 加) + l l , ( x 抄, y , d ) - 2 i 。, 刊( x , y , d 】 ( 2 7 ) 一【扛，y 一2 一1 ，卅一，b ，y 一2 一1 ，训 也就是如图2 4 中的上半部分所示。 瑁 熊= 豳+ 匪畦 田2 4 盒滤波加速方法 盒藕波方法在计算当前窗口匹配度时充分利用了之前窗口的计算结果，极大 的减少了计算量，使得算法复杂度减少为o n 2 d l ，从而将匹配窗口的大小与整 个算法复杂度解耦，大大减少了程序运行时问 盒蟪波方法数据处理具有连续性，且计算规整，适合并行实现。叠字塔加速 方法虽然也大幅度的减少了程序运行时间，但是低分辨率的顶层图像尺寸较小， 不能充分利用g p u 的运算性能，而且在图像分层时逶级缩放，并行处理效率不 如盒滤波因此，本文将采用第二种方法即盒滤敢对立体匹配进行加速 2 5 本章小结 本章主要对实时立体视觉的匹配方法进行了选择通过比较各种匹配方法的 优缺点，选择了基于区域的匹配方法接着对区域匹配的各种相似度度量方法进 行讨论，并结合立体视觉应用中对算法的实时性要求，选择了s a d 、s s d 及筒i 目b 浙江大学硕士学位论文基于c u d a 的立体匹配及去隔行算法 变换匹配方法。匹配窗口的选取直接影响到匹配结果的正确性，在区域匹配算法 中，应选取适当的窗口尺寸，通过对不同大小匹配窗口效果的比较，得出窗口应 在合理的范围内适当加大的结论。区域匹配算法通常复杂度较高，因此需要一定 的优化方法进行加速，减少冗余计算，本章例举了金字塔及盒滤波加速方法，并 加以比较。 浙江大学硕七学位论文基于c u d a 的它体匹配及去隔行算法 第三章视频去隔行算法 在典型的视频监控场景中，有人的走动和车辆的快速移动，监控摄像机的隔 行扫描使得人和车辆边缘模糊，视频图像质量下降。为了获得清晰的监控视频， 在进一步处理前需要将隔行扫描信号转成逐行扫描信号，实现实时的去隔行处 理。 3 1 去隔行算法分类 去隔行处理的基本原理是利用视频图像序列在时间和空间上的相关性，计算 出待插值像素点。目前，去隔行算法大致上可分为三类：线性去隔行( l i n e a r t e c h n i q u e s ) 、运动自适应去隔行( m o t i o na d a p t i v ed e i n t e r l a c i n g ) 和运动补偿 去隔行( m o t i o nc o m p e n s a t i o nd e i n t e r l a c i n g ) h 1 。 线性去隔行算法是最简单的一种去隔行算法，易于硬件实现，有三种不同的 类型：空间滤波( s p a t i a lf i l t e r i n g ) 、时间滤波( t e m p o r a lf i l t e r i n g ) 和时空滤波 ( s p a t i a l t e m p o r a lf i l t e r i n g ) 。空间滤波只使用同一场内相邻点的信息计算插值， 最简单的空间滤波是行复制( l i n er e p e t i t i o n ) ，一场中待插值像素点直接取它 上面相邻点的值；稍复杂的形式为行平均( l i n ea v e r a g i n g ) ，待插值点取其上 下两个相邻点的平均值。空间滤波的缺点是降低了图像在垂直方向上的分辨率。 时间滤波是利用所有相邻场求取插值，最简单的方式是场合并( f i e l dm e r g i n g ) ， 即用上一场中的已知像素代替待插值像素。时间滤波的缺点是造成视频运动信息 的损失。时空滤波综合考虑空间相邻点和时间相邻点，是上述两种方法的结合， 但是仍存在图像