（航空宇航制造工程专业论文）基于gpu的双目立体匹配技术研究.pdf

1 iiiiiilji n 锄j i n gu i l i v 盱s i 够o f a e r o n a u t i c s 肌d a s t r o n a u t i c s t h e ( h a d u a t es c h o o l c o l l e g eo fm e c h a l l i c a la n de l e c 仃i c a le n g i n e e r i n g 帅l | | i i 1 1 i i l l l l l f f f f i f f l l | i | l | | | 洲 y 18 2 5 4 0 5 r e s e a r c ho ng p u b a s e db i n o c u l a rs t e r e o i m a g em a t c h i n g a t h e s i si l l a e r o s p a c em a i l u f a c t u r i n ge n g i n e e r i n g b y z h ub i n a d v i s e d b y p r o z h a l l gl i - y a i l s u b 瑚- i t t e di np a r t i a lf u l f i l l m e n t 0 fm ei k q u i r e m e n t s f 0 rm e d e g r e eo f m a s t e ro fe n g i n e e r i n g m a y ，2 0 1 0 j j 承诺书 本人声明所呈交的硕士学位论文是本人在导师指导下进 行的研究工作及取得的研究成果。除了文中特别加以标注和致 谢的地方外，论文中不包含其他人已经发表或撰写过的研究成 果，也不包含为获得南京航空航天大学或其他教育机构的学位 或证书而使用过的材料。 本人授权南京航空航天大学可以将学位论文的全部或部 分内容编入有关数据库进行检索，可以采用影印、缩印或扫描 等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本承诺书) 作者签名： 南京航空航天大学硕士学位论文 摘要 随着g p u ( 胁p l l i cp m c e 鼹i i l gu i l i t ) 硬件的发展，特别是其构架的改变，g p u 已经不再是 固定流水线的图形处理器，而是类似单指令多数据( s d 订d ，s i n g i ei n s t r u c t i o nm u p i ed a 切) 结构的并行可编程流处理器，从而近几年兴起了基于g p u 的通用计算的研究热潮，并在许多领 域中得到了应用。 本文将g p u 应用到双目立体图像匹配技术研究中，大幅度提高了算法执行的效率。立体匹 配算法根据得到的视差图分布情况分为稀疏型和稠密型，稠密型的方法对于以生成物体表面点 云数据为目标的三维重建而言更为理想，但是同时计算量也更大。另一方面，为了实现稳健的 图像匹配，尽可能减少误匹配，越来越多的研究采用基于能量最小模型的全局优化方法，而这 类全局能量优化方法本质上往往是，难问题，计算规模是问题规模的几何倍数，因此也存在 算法的时间效率低，无法满足快速三维重建的问题。针对这一问题，本文以自主知识产权的双 目立体三维点云实时重建系统研发为背景，围绕基于图割的立体图像稠密像点匹配算法的加速 技术进行了深入研究，着重采用了两个提高速度的方法：一是通过快速图像校正方法，减少匹 配点搜索范围；二是应用g p u 实现算法的并行化。主要工作如下： 1 )研究了g i u 的硬件构架t e s l a ，分析了g p u 作为一种近似s m m 的并行流处理器的工 作原理。在此基础上，研究了n v d 认公司开发的c u d a 编程工具，重点分析了其线程模型和 存储器模型，并对于c u l ) a 程序如何有效使用g p u 资源从而提高算法速度进行了深入的研究。 2 )研究了基于摄像机标定结果的图像校正原理，分析了校正前后图像的遮挡关系，并结 合本文采用的双目立体匹配测量系统r e c 他a t o r ，对已有的图像校正算法提出了改进。同时提出 了基于g p u 的图像校正实现方案，针对图像校正过程中最为耗时的图像插值过程利用c l d a 编程工具实现了多种插值算法，结合理论分析和实验结果对比讨论了四种插值效果。实验对比 了各算法采用g p u 和普通c p u 的运行时间，表明本文基于g 】p u 的插值算法有很好的算法效率 优势。 3 ) 研究了能量最小化模型和图论中的最大流最小割理论，在图像校正的基础上，建立了 双目立体匹配的能量模型和网络图模型。对比分析了邳s w 印和a e x p a 璐i 两种图割算法，指 出a e 印a 璐i 傩算法更适合用于g p u 实现。同时对两类最大流最小割算法一压入重标记算法 和增广路径算法进行了分析研究，通过比较得出了压入重标记算法并行化的可行性和必要性。 最终利用g p u 实现了基于图割的双目立体匹配，用多个合成图像和实拍图像对文中算法进行了 验证，并通过实验研究了能量参数对立体匹配结果的影响。对算法运行时间进行了比较，结果 显示采用g p u 编程后算法效率提高在几百倍以上。 关键词：图割，双目立体匹配，图像校正，图像插值，图形处理器，能量最小化 i 基于g p u 的双目立体匹配技术研究 a b s t r a c t 舡m ed e v e l 叩m 舳to f g p u ( 雠州cp 加i c c s s 吨u 硫) ，s p e c i a l 啦，v 伽嘲to f i t s 撒h i t e c t 啪， g p ui sn ol g 盯j u s tg r a l 炯cp 鲒0 rw i m 毓dp i p e l i n e ，b u ta k 曲弱as m d ( s i i l g l el 璐衄觚 m u l 卸kd a t a ) w l l i c hi sap a m l l e lp r o g 即m m e dp i p e l i n ep r 0 h c e s s 睨s 0i nt h er e my e a 鹉，g p g i u 乜饥e m l 岬c o i i 驴u t a t i o n o n t h e g p u ) i s p o p u l 缸t o b e 璐e d i l l n 珈1 y a r e 弱a h e 嘶 l l lm i sf h e s i s ，g p ui sl 塔e di nt h e 她a r c ho ft h eb i n o c u l 盯s t e r i 瑙i t c l l i n g s t 讹om a t c h i i l g m c l o d sc 觚b ec l a 蹒i f i e di n t ot 啪t y p e 卜他es p 躺e 锄dt h ed 饥，i i lt e r n 塔o ft l l ed i s 恤i b i n i 嘶o f d i s p 撕t ) ，m a p 1 1 圮d 朋i sb c t t c r 矗d r3 dt l l ep o i n t sc l o u dr 伽枷c 6 m e 州t s 如r f a ，b l l t t h ec a l c u l a 缸舡小m mi sl a r g e o nt l l eo t l l 盯h 锄d s ，t 0 把a l i 如h l s ti m a g em a t c b j n g 跹dt 0 d u t l l em 纳c t l i i l ge r r 0 璐，伽i e f g ym i i l i i i l i 砑t i o ni su d 雒a9 1 0 b a l 哪岖m 妇i 衄m e t l l o di n 黼觚d 撇 r e a r c h e s ，b u ti ne s m e ，i ti s 啪n yn pk 帕邮b l 锄，w h 0 c a l c u l a t i s c a l ei s v e r a i 缸骼 蛔盯t h a i lt h e a l eo f i t s l e 比s ot h eh m ee 伍c i e 眦yi sl o w 锄d 曲e 唧m i i l m l i z a 缸o ni s t 丘tf o rt h c m p i d3 dr o 璐蛔t i o n c o 地i d e r i l l go ft l l i s ，t h ct l l e s i s i sb 舔e d t h eb 咖u n do fd e v e l 叩i n g 心a 1 血鹏b i n o c u l 盯s t e f e o3 dp o i n t sc l o u d c o 璐t n j c t i s y s t c m w m c hh 蠲m e 诚姊吼d 髓t i i l t e l k c t u a lp r o p 曙r 呗锄dd p a r c hi sc a r r i e do u tf i o rt h e c c l 枷0 nt e c l l i 岫鹏si i l l cd 舶 s t 即m a t c h i i l gb a do ng m p hc u t s h e 他，t w om e t h o d sa 锄：】p h a t i c a l l ya d | o p t e df o r c e l e 础g ： f i i 售t ，r e d u c et l i e a r c h i i l gr 锄g ef 0 rt h em a t c l l i n gb yq u i c ki m a g ec o r 他c 6 0 n ；c o n d 呻l e m 肌tm e p a r a l l e l i z a t i o fa l g 耐娜b yg p u m 岫蝴o f m e m e s i s 躺驯咖妇d 舔f o l l o 髑： 1 ) 1 1 托h 砌w a 他眦l l i t e c t u t c s l ao fg p ui s 他s e a r c h e d 圮w o r i 【t l l e o 猡o fg p u ，w 】 l i c hi sa p i p e l i m 即s s 甜雒s 巩d ，i sa m l y z c d b a d 也i s ，吐l et l 聆a dm o d e la n dm 即1 0 r ym o d e lo f t h e g p us 叩p o r t i n gd 地p r o 萨哪m i i l gt i ic u 】) ad e v e l o p e db yn d 认i s 麟e a r c h e d ，a n dn 撒lt t 砖 p m 髓珊i n i i l g 砌d d c lo fh o wt oe 彘c t i v e l yu n 把g p u 托峨sb yc u d a 幻l e 眦t i l e a l 剃t h m si s c 枷e d o 此 2 ) m 岫o f i i i l a g e 玳娟b 勰e d t h e 他g u ho f c 扰肌c a l i 嘶i s 他鲫嘲a n d 恤 o c c l 璐i o nb e 俺髂m 也eo r i g i i l a l 锄dc o 盯t o di m a g 鹤i sa n a l y z e d b 勰e d t h eb i n u l a r 鼬湘o m e a s 曲gs y s t a n 腻r e a t i d r ，t h ee x i s 蛀n gi m a g e c t i 丘c 砸m e t h o di si n 聊f 0 i v c d a n da h 黜t o r e a l i 船t h ci n 豫g cc o l l r e c o nb y 潮，i sp l d p o s e d ，s p e c i a lf 0 rt h ei m g ei n t c i p o l a 6 0 n 砌c hi sm o 吼 6 m e c m 坞i l i | 呜i l lt h i sp a n ，v e r a li n t e f p o l a t i 伽a l g o r i t h m sa 陀i n l p l 既嗽n t c db yc u d a n dt l i c 嘲矧m e 删麟i l l t s 玳c o 呷刹a n d 衄a l y z e db ym e 哪t h ee x p 删i s c 枷e d0 u tt o 唧眦 m e 姗t i i m o f c p ua n d g p u ，a n d 位删伍i n d i 钯她a d 【i 姆o f g p u t o i 烈：斌t h ea l g 研t h m e 伍c i e ：) ro fi m a g ei n 白e i p o 蜥o n - 南京航空航天大学硕士学位论文 3 ) t h et t l 叮o f 饥e 瑁：) rm i i l i r i l i z a t i o n 啪d e l 锄dm a xn o w 如【i nc u ta 托他s e a r c h c d b 勰e d i m a g e c t i f i c a t i o i l l e 饥e r g ym o d e la l l dt 砖t 、) l ，o r k 黟a p ho fb i i l o c u l 盯s t e 他om a t c l l i n ga 传b u i l t c o n l p a r i n g 锄da i l a l y z i i i g 锕og m p hc u t sm e l o 椭ps w a p 锄dae x p a 璐i ，i ti sc o 眦l u d e dt l l a ta e x p a 璐i o ni sm o s u i t e dt 0b c 他a l i 笳db yg p u t h 饥坞s e a r c l l i n ga n d 锄a 1 ) ，z i i l g 铆om 觚i m m nf l o w l i l i i l i m 哪c u tm e t l l o d s 卜- p 晒h 他l d b e l 觋da u 孕m m t i i l gp a m ，i ti si i l d i c a t e d l en e s s i t y 锄dm e f e 弱i b i l i t yo f p u s h 啪l a b e lt ob e 糟a l i z c db yg p u a t 她d ，g i ui s 惦e dt 0i r n p l 锄e n tm cb i r 瑚u k s t c r e om a t c l l i l l gb 弱e d g r a p hc u t s ，m ce x p e r i m e 吣a 他c 缸矗e d 叭l t t i i es y i l t i 圮s i s 锄dm e 蒯 i m a g e s ，t 0 坞s e a r c h1 1 0 、n l ep 盯锄e t e 璐o fe n e r g yf i l 眦t i o na 丘- c c tt h e 心s u l t s c 伽驴撕n gt h e 棚i m i l l g t i l mo fc p u 锄dg p u ，吐圮他踟l ti i l d i c 疵st i l a t 地e 伍c i e 眦yi s 硫r e 雒e db yh 吼d r e d so f 吐m e s 璐i i l g g p i ， k e y w o r d s ：鲫hc u t s ，b i i l o c u l 缸s t c r e o 删舭h i l l g ，i m g c 托c t i 矗c a t i o i i i m a g e 帅l a t i o n ，g p u ， e n e 增：ym i i l i m 妇i h i 基于g p u 的双目立体匹配技术研究 南京航空航天大学硕士学位论文 目录 第一章绪论1 1 1 弓i 言1 1 2 双目立体视觉测量系统1 1 2 1 双目立体视觉l 1 2 2 立体匹配方法。2 1 2 3 图割法在计算机视觉中的应用。4 1 3 基于g p u 的算法并行化。：5 1 3 1 现有的并行算法。5 1 3 2 基于g p u 通用计算机的国外应用7 1 4 本文的主要研究工作8 第二章c u d a 编程模式。1 0 2 1 引言1 0 2 2t c s l a 体系构架。1 0 2 3c u d a 线程模型1 3 2 3 1 线程模型。1 3 2 3 2 线程间的通信1 3 2 4a m a 存储器模型。1 4 2 5c im a 程序优化设计l6 2 6 本章小结1 7 第三章立体图像对的快速校正1 8 3 1 引言18 3 2 摄像机模型l8 3 2 1 坐标系定义1 8 3 2 2 摄像机针孔模型1 9 3 2 3 外极线约束2 1 3 3 立体图像校正基本原理2 2 3 3 1 校正前后的图像坐标变换2 2 3 3 2 校正前后图像遮挡关系分析2 4 3 3 3 校正后的图像大小的确定2 5 v 基于g p u 的双目立体匹配技术研究 3 3 4 校正后的图像像素灰度插值2 6 3 4 图像像素灰度插值的g p u 实现2 6 3 4 1 固定存储器应用2 7 3 4 2 纹理存储器应用2 7 3 4 3 最近邻点差值3 0 3 4 4 双线性插值3 0 3 4 5 双三次插值3 l 3 4 6 双l 丑眦ss i i 垃插值3 3 3 5 实验验证与分析3 4 3 5 1 图像校正算法正确性验证3 5 3 5 2c p u 与g p u 的速度比较。3 6 3 5 3 各插值算法结果直观比较3 7 3 6 本章小结3 8 第四章基于图割的快速立体匹配算法3 9 4 1 引言3 9 4 2 图割基本概念柏 4 2 1 网络流的概念4 0 4 2 2 割的概念4 l 4 2 3 最大割最小流4 l 4 3 基于能量最小化的网络模型4 3 4 4 基于图割的立体匹配算法g p u 实现。4 4 4 4 1 视差范围估计4 4 4 4 2 多元问题转化为二元问题4 5 4 4 3 网络模型构造的g p u 实现。4 6 4 4 4 压入重标记法的g p u 实现4 8 4 4 5b f s 广度优先的g i u 实现5l 4 4 6 基于图割的立体匹配算法流程5 l 4 5 实验结果及分析5 2 4 5 1 立体匹配算法匹配率5 2 4 5 2g p u 实现的图割算法验证。5 3 4 5 3 立体图像匹配实验5 4 4 6 本章小结“ 南京航空航天大学硕士学位论文 第五章全文总结与展望6 5 5 1 本文的主要工作6 5 5 2 进一步研究展望6 6 参考文献6 7 致谢。7 2 在学期间的研究成果及发表的学术论7 3 v n 基于g p u 的双目立体匹配技术研究 图表清单 图1 1 能量最小化网络图模型4 图1 2 图割法示意图4 图1 3 基于图割理论求解计算机视觉问题的框架5 图1 4 并行处理的几种实现方式6 图2 1 ( k f o k e 8 8 0 0 图形处理器的示意图1 0 图2 2 佃c s m 架构。l l 图2 3 线程块网格1 3 图2 4g p u 与c p u 间的两种通信模式1 4 图3 1 三个坐标系定义1 8 图3 2 摄像机针孔模型2 0 图3 3 外极线约束2 l 图3 4 双目立体图像对校正2 2 图3 5 校正前后图像投影比较2 5 图3 6 图像校正后前后投影变化2 6 图3 7 最近邻点插值及双线性插值示意图3 0 图3 8 双三次插值示意图3 1 图3 9 校正前的立体图像对。3 5 图3 1 0 校正后的立体图像对3 6 图3 1 l 双l a 眦毗s 疵插值不同窗口大小c p u 与g p u 运行时间曲线图。3 7 图3 1 2 各插值算法效果直观比较3 8 图4 1 一个网络基础有向图4 0 图4 2 网络图中的一个割4 l 图4 3 网络图中边的构造4 3 图4 4 视差范围估计4 4 图4 5q b 弧，印l 和a - c x p a 璐i 蚰图割的结果4 6 图4 6 相邻节点间所有可能的割4 7 图4 7 基于图割的立体匹配算法流程图5 2 图4 8 基于g p u 的图割算法正确性验证5 3 图4 9s a 删左右图像对5 4 图4 1 0s 钾瞅舭图的伊叫叮d 仇i m 图5 5 v i 南京航空航天大学硕士学位论文 图4 1 1s 删o o m 图不同a 值生成的视差图5 6 图4 1 2 允对s 删o o 吐l 图匹配率影响曲线图5 6 图4 1 3s 删o o t l l 图不同珈，1 船生成的视差图5 7 图4 1 4f 7 l ，劣对s a 训d 0 t l l 图匹配率的影响曲线图5 8 图4 15m a p 左右图像对5 8 图4 16m 印右图的g r o u n d 饥m l 图5 9 图4 1 7m 印图不同灰度梯度阀值生成的视差图6 0 图4 1 8 肪，豁对m a p 图匹配率的影响曲线图6 0 4 图4 1 9m a p 图不同旯生成的视差图6 l 一图4 2 0 a 对m a p 图匹配的影响的曲线图6 2 图4 2 l 校正前的左右实测图6 3 一图4 2 2 校正后的左右实测图6 3 图4 2 3 实测图第3 部分匹配结果。6 3 图4 2 4 实测图第4 部分匹配结果6 4 表3 1 图像校正的时间对比( 左图右图) ( 单位s ) 3 6 表3 2 双l 矗n c o zs i 眦插值不同窗口大小c p u 运行时间与g p u 运行时间3 7 表4 1 最大轫时最小割算法的复杂度。4 0 表4 2 各变量对应的存储器。4 8 表4 3 基于图割的立体匹配算法的g p u 和c p u 运行时间比较5 4 表4 4s a 叭0 0 t 1 1 图不同允值的匹配率。5 6 表4 5s a 咖o m 图不同髓，缎值的匹配率5 8 表4 6m a p 图不同灰度梯度阀值的匹配率6 0 表4 7m a p 图不同a 的匹配率6 l 表4 8 各组匹配实验g l u 与c p u 的比较“ 基于g p u 的双目立体匹配技术研究 x c 伽叩u t eu 匝f i e dd e 、，i c ea l l i t e c t 哦 s c a l a b l es 骶觚l i n gp r e s s o r 岫 n 鹏a dp r e s s h l gc h 塔t e r s 虮锄1 1 i n gm u l 石p m c 部s o r & 托岫g p r o c e s s o r s 吨l ek 眦缸m u l 卸l e d a t a g 伽眦lp l l r p 0 c 伽甲删o no n 岫 g p u m a dl ，e lp a i 锄l c l m e s s a g ep 黜吨h i c e i f a n 鹏a d b u i l d i n gb 1 0 c k o p 钮m u l d - p m 锚i l l g h i g l lk v e ls l l a d i l l gk g m g e 图形处理器 计算统一构架 流处理器阵列 线程处理器群 流多核处理器 流处理器 单指令多数据 图形处理器的通用计算 线程级并行 消息传递接口 线程构建模块 开放式多处理 高级着色语言 删 一 吾| 僦 蹦 e 5 一 唧 姗 珊 一一 l 乞 王 t 支 丘 z & 殳 m n 屹 b 南京航空航天大学硕士学位论文 第一章绪论 1 1引言 逆向工程技术是数字化和快速响应制造大趋势下的一项重要技术，是c a d 领域中一个相对 独立的范畴。鉴于目前有关逆向工程的研究和应用大多数针对的是实物三维几何模型的反求，在 这个意义下，逆向工程可以理解为是根据已有实物模型的三维坐标测量数据，重新建立实物的数 字化模型，而后进行分析、加工等处理。坐标数据采集是逆向工程中的第一个环节，是数据处理、 模型重建的基础。目前，逆向工程的应用已很广泛，例如：由于种种原因，在只有模型实物而 没有模型c a d 数据情况下需要对模型进行分析修改时，就需要利用逆向工程手段快速有效地将 实物模型转化为c a d 数据模型，从而充分利用数字化的设计分析手段；对于汽车车身等一些 外形美学要求较高的零部件的设计制造，一般都需要先制作全尺寸的木质或者黏土模型，因为在 计算机上直接完成这样高要求的三维复杂外形设计是非常困难的。当实物模型制作好之后，就需 要使用逆向工程的测量设备将实物模型转化成数字化模型输入到计算机辅助设计系统中去；将 逆向工程和快速原型系统相结合，组成产品设计、制造、检测和修改的闭环系统，实现快速测量、 设计制造、再测量修改的反复迭代，从而高效率地完成产品的初始设计。 从这些逆向工程的典型应用中可以看到，对实物模型的快速测量是实现逆向工程的重要基础 和技术关键之一 1 2 双目立体视觉测量系统 1 2 1 双目立体视觉 m a 一2 】【3 】【4 】【习综合了图像处理、心理物理学、神经物理学及临床精神病学的研究成果，提出了 第一个较为完善的视觉理论框架，使得基于视觉理论的三维数据重建方法越来越受到人们的重 视。 由不同位置的两台数字摄像机( c c d c m o s ) 或者一台摄像机经过移动或旋转拍摄同一幅场 景，即从两个或多个视点去观察同一场景，获得在不同视角下的一组图像，通过计算空间点在两 幅图像中对应点的视差，获得该点的三维坐标值，并进而重建场景中目标物体的空间几何形状和 位置，这种方法称为双目立体视觉。 相比其它类的三维测量和检测方法，三坐标测量机、机械臂式、激光跟踪仪等方法，双目立 体测量直接模拟人类双眼处理景物的方式，可靠简便，在许多领域均极具应用价值，如运动物体 的位姿检测与控制、机器人导航与航测、三维测量及虚拟现实等。 双目立体测量技术的实现可分为以下步骤：图像获取、摄像机标定、立体匹配，三维重建。 基于g p u 的双目立体匹配技术研究 1 ) 图像获取 双目立体测量的图像获取是由不同位置的两台摄像机拍摄同一场景，获取立体图像对。假定 两个位置上的摄像机内部参数都相等，两摄像机的光轴互相平行，两个成像平面重合，则这两个 相机获取的立体图像对可以使得后续的图像匹配过程更加容易。但一般情况下，针孔模型两个摄 像机的内部参数不可能完成相同，摄像机安装时也无法看到光轴和成像平面，故实际应用中一般 难以实现这样的双目立体测量结构。而采用图像校正睁1 2 1 的方法，可以人为地调整摄像机的姿态 和内部参数，使得两个摄像机具有相同的内部参数、相互平行的光轴和重合的成像平面。 2 ) 摄像机的标定【1 3 】 对双目立体测量而言，数码摄像机是对物理世界进行数字化三维重建的基本信息传感工具， 对它们的标定是实现立体视觉基本而又关键的一步。摄像机的标定的方法，目的是要得到两个摄 像机的焦距、光心的图像坐标等内参数，以及两个摄像机之间的位置和姿态关系，即系统外参数。 3 ) 立体匹配 图像匹配是指给定同一场景的两幅图像，寻找同一场景点投影到这两幅图像中的像素之间的 对应关系。在立体匹配中，图像是从同一时间不同视点拍摄得来的，所以图像的对应点反应了视 差信息。与普通的图像配准不同，立体像对之间的差异是由摄像时观察点的不同引起的，而不是 由景物本身的变化、运动等其它因素引起的。 4 ) 三维重建 在得到空间任一点在两个图像中的对应坐标和两摄像机内、外参数的条件下，即可进行空间 目标点三维坐标的解算，得到景物的深度信息。 在上面的四个步骤中，立体匹配是双目立体测量中十分关键，通常也是最为困难的一步。本 文主要围绕双目立体视觉系统中的立体图像匹配问题展开研究，并致力于实现立体匹配算法的实 时性，为实时重建动态物体的三维外形奠定基础。 1 2 2 立体匹配方法 根据匹配算法所生成的视差数据分布情况，可以将目前的立体图像匹配算法分为稀疏视差匹 配和密集视差匹配两大类。 稀疏视差匹配亦称为特征匹配。一般地，用于匹配的特征应满足以下特性：唯一性、再现性、 具有物理意义。作为匹配基元的特征分为局部特征和全局特征两大类。局部特征的属性包括点的 灰度阶跃特性，边缘和线段的走向、强度、长度、曲率，以及区域的平均亮度等。全局特征的性 质可描述为局部特征问的结构关系，包括多边形邻边的夹角、边缘间的最短距离等。基于特征的 匹配一般含有特征提取和定位、特征描述、特征匹配三个步骤在图像匹配算法中，角点是一种 十分常用的匹配基元，如经典的h a r t i s 角点i 堋，就常用于图像的稀疏特征匹配。h 卸凼角点对仿 射变换和旋转变换具有不变性，但对于尺度变换却不存在不定性为解决匹配中的尺度变换不变 2 南京航空航天大学硕士学位论文 性，k l w e d g 在2 0 0 4 年提出了s i f r 特征匹配【1 5 】【1 6 】。在基于特征点的立体匹配框架中，l 0 w e d g 提出用d i 侬 r e eo f g a 吣s i 锄( d o g ) 算子来建立尺度空间，利用图像梯度信息，引入基于三维梯 度方向直方图作为区域特征描述符，这种邻域方向性信息联合的思想增强了算法抗噪声的能力和 对图像变换的鲁棒性，同时对于含有定位误差的特征匹配也提供了较好的容错性，而且计算量较 小，速度较快。 密集视差匹配的特点是定位精度高，恢复视差密度大，因而可以在其基础上获得物体表面的 三维点云数据。密集视差匹配的典型算法是区域相关匹配【1 7 】，以左图的待匹配点为中心创建一 个窗口，用邻域像素的灰度值分布来表征该像素，然后在右图中寻找这么一个像素，以其为中心 创建同样的一个窗口，并用其邻域像素的灰度值分布来表征它，根据两个窗口之间的相关程度作 为判别依据。相位匹配是近二十年才逐步发展起来的一类密集视差匹配技术，是继区域匹配和特 征匹配后，提出的另一种立体视觉匹配算法【嘲。八十年代以来，r o b s 进一步从生理学角度证 明了人类视觉系统中的简单视细胞是以正交相位关系成对出现的，并且可以用一对实部与虚部相 互正交的复数滤波器来模拟；j u l e s 【2 0 】也指出相位信息可能是人类立体视觉融合中最理想的基元。 相位匹配基于这么一个假定，即认为像对中对应点的局部相位是相等的。根据傅立叶平移定理， 信号在空间域上的平移产生频率域上成比例的相位平移。考虑傅立叶变换的空间支撑为无限，一 般地，相位匹配方法对带通滤波信号的相位信息进行处理而得到像对间的视差。最常用的相位匹 配方法有相位相关法【2 1 】和相位差频率法【2 2 l 。在此基础上，由于g a b o r 函数可以同时在时域和频 域获得最佳的局部化，s a n g 阿和j e i l l 【血等【2 3 】提出了基于( 址町滤波相位的立体图像匹配算法。此 后随着小波理论的逐渐发展和完善，利用复数小波( 矧【2 5 1 获取图像视差成为研究的热点之一。 不论是特征匹配、区域匹配还是相位匹配，都是只考虑像素点自身某种局部意义下的最佳匹 配点，而不是从全局考虑对整幅图像求最佳匹配组合解，较容易产生误匹配。 近几年来，很多研究者用能量最小化模型来描述立体匹配问题【2 3 1 ，得到立体匹配的全局或 近似全局最佳匹配结果。能量最小化为许多计算机视觉问题提供了一个自然的框架，已广泛应用 于很多问题。通过最小化能量的方法解决问题主要包含两个步骤。第一步，创建目标函数。它量 化了所有候选解的好坏程度。一个目标函数通常表述为一些约束项的和，这些约束项对应了问题 的硬性或软性约束条件。这里的目标函数就是能量函数。第二步，最小化能量函数。计算机视觉 中的能量函数往往是多维的并且存在很多的局部最值。许多研究者已经尝试一些通用的优化技 术，例如坡度递降法或模拟退火法。前者应用于具有连续变量的能量函数，而后者应用于具有离 散变量的函数。然而，这些通用方法得到的结果常常会陷入局部最小，或者需要很长的时间才能 收敛。 现在比较主流的一种优化技术是图割法( 触p hc u t ) 【3 1 】【3 2 】【3 3 】，相比其它的优化技术，它的优 点是在某些情况下它们能提供能量的全局最小化，或者在其它情况下能产生具有很强性质的局部 3 基于g p u 的双目立体匹配技术研究 最小化。基本过程是先将能量最小化模型转化为单源点单汇点的网络图，如图l - 1 ，s 是源点，只 有输出流，f 是汇点，只有输入流，分别代表的不同标示值，而其它的节点分别对应着图像中的 像素点，在图像四邻域范围内相邻的像素点对应的节点之间也有边连接。 图1 1 能量最小化网络图模型 优化的过程采用图论中的最大湖最小割理，如图1 2 ，将网络图中的节点最终划分成两个节 点集合，这两个节点集合之间分别包含了源点和汇点，连接这两个节点集合的边的容量都达到饱 和，而这些饱和边就构成了图中的一个割。包含j 的节点集合中所有的节点的解等于s 所代表的 标示值，而包含f 的节点集合中所有节点的解等于f 所代表的标示值。 图1 2 图割法示意图 1 2 3图割法在计算机视觉中的应用 计算机视觉中以图割( g h p hc u t ) 理论为基础进行能量函数最小化的匹配算法不断出现。虽 然图割是一种强有力的优化方法，但它们仅能被用于求具有某些约束的问题的离散解。研究者们 已经把两种常用的约束放进了基于图割的能量最小化框架中，包括数据项约束和平滑项约束。数 据项约束用来直接描述被观察到的数据，平滑项约束能控制解的空间平滑。在图割法中把所有可 能解组成一个集合，称这些可能解为标示。 4 南京航空航天大学硕士学位论文 图割法是一些图论算法的基础，可以用于许多情况下的数学建模，例如最短路径和图的双向 匹配等等。在计算机视觉中基于图割的能量最小化方法求解的问题越来越多，包括图像分割 【3 町、图像恢复嗍、三维重构4 h 7 】、体素填充【4 引、目标识别捌、纹理合成【5 0 1 等等。不同的问题 中解的意义不同，即标示具有不同的意义。例如，通过图割法的二值标示进行图像前景背景分割， 这里的标示是l ，0 ，分别表示前景和背景；图像复原中，标示表示的是离散的灰度值；在立体匹 配中，标示表示的是离散的视差值；而多视角场景重建中，标示所表示的是不同场景元素。图1 3 描述了基于图割法求解计算机视觉问题的基本框架。 视觉问题 ( 标号问题) jl - 1r 能量函数 最小化问题 卜- - 网络图 最小割问题 jl 一一一 1r 网络 最大流问题 一-一1：圈 图1 3 基于图割理论求解计算机视觉问题的框架 文献【5 1 1 中证明了能量函数不受约束时，基于图