（计算机软件与理论专业论文）计算机视觉三维重建理论与应用.pdf

独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的 研究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含 其它人已经发表或撰写过的成果，也不包含为获得西北大学或其它教育机构的 学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均 已在论文中做了明确的说明并表示了谢意。 学位论文作者签字：王宇窗 签字r 期：? 0 0 中年月2 0f 1 摘要 计算机立体视觉研究利用二维投影图像恢复三维景物世界的问题，是计算机视觉 技术的主要任务之一。计算机三维重建理论及其实现技术在战场三维地形建模、战场 监视以及精确导航等领域有着重要的应用。根据军队建设对快速三维地形重建和快速 精确定位的需要，本文对立体视觉计算中的影像特征提取、基于知识的影像分析、宽 基线影像匹配、影像地面控制点自动识别、三维实时重建以及立体视觉模型误差分析 等问题展开了理论和实现技术的研究，取得了一些研究成果。 图像基本特征获取是计算机三维重建多种算法的基础。通过对直线特征的分析， 本文提出了一个新的层次结构化直线提取算法。该算法在不同尺度上利用局部区域直 线特征构造直线段，形成一种具有层次的结构化的直线表示。算法采用自底向上的策 略，首先构造底层局部线段结构，然后利用业已获得的下层结构构造上一层结构，因 此具有较高的效率。算法既利用了局部特征，又利用了全局特征，因此具有较高的可 靠性。 在区域特征提取方面，本文的贡献是提出了一个稳健的区域分割算法。该算法首 先将影像划分为较为平滑的区域和亮度变化较为剧烈的区域。根据像点是否处于平滑 区域采用不同的方法分别处理。对于处于平滑区域的像点采用简单算法处理，对于可 能处于区域边缘的像点采用较为复杂的移动平均算法在色度空间和尺度空问上处理。 因此，算法兼顾了时间效率和稳健性。 影像匹配是三维重建问题的核心。本文提出了一个面向三维重建任务的基于知识 的图像分析系统模型。该模型将相关知识划分为基本影像处理知识、与具体目标影像 相关的知识和与分析任务相关的知识。基于知识的图像分析系统运用基本影像分析知 识和领域专家知识对场景中基本特征关系进行分析，获得场景中透视关系或其它特定 空间几何关系的定性表达。目的是通过正确解释影像中某些空间关系来提高匹配算法 的效率和可靠性。 在影像匹配算法方面，本文的主要贡献是提出了一个基于局部仿射不变量特征的 宽基线条件下的影像匹配算法，处理最一般情况下的影像立体匹配。算法以影像特征 点为定位点，使用分层变尺度窗口内的几何仿射不变量特征和亮度仿射不变量特征实 现宽基线影像立体匹配。该算法利用局部特征进行宽基线立体匹配，因此具有较高的 算法效率。同时，算法在较大窗口范围内构造尺度、旋转不变特征，并考虑到可能存 在的投影变形而对窗口形状进行变换，因而具有较高的匹配可靠性。通过将大窗口划 分为较小的重叠子区域，算法可以获得较好的匹配精度并减少因遮挡造成的不利影响。 在三维重建方面，本文研究了三维射影重建和欧氏重建的基本算法、光束法平差 三维重建算法和实时k a l m a n 滤波修正三维欧氏重建算法。探讨了基于平面图的单视 图约束和多视图约束三维重建算法。 在立体视觉模型方面，本文推导了标准立体视觉模型和汇聚立体视觉模型的三维 重建误差公式，分析了欧氏重建中不同立体模型的点位误差大小及其变化规律。 在计算机三维视觉理论与技术的应用方面，本文提出了一个快速数字地形重建系 统的设计与实现方法。该系统将交互式系统和实时系统集成在一起，利用交互式三维 重建系统获取高精度、高可靠性的三维模型。利用实时三维重建系统获取精度较低的 快速重建结果，通过数据融合消除不可靠的重建结果、提高重建精度。该系统由控制 测量子系统、交互式三维地形重建子系统、三维地形可视化子系统、基于g p s i n s 的 实时三维地形重建子系统和基于平面图的三维重建子系统等多个部分构成，实现高精 度快速三维地形重建任务。该应用系统的设计和部分实现，进一步证明了本文理论研 究和应用研究成果的正确性和实用价值。 关键词：计算机视觉，立体视觉，特征提取，区域分割，图像分析，影像匹配，图像 理解，宽基线影像匹配，三维重建，实时重建，误差分析。 a b s t r a c t c o m p u t e rs t e r e ov i s i o nm a i n l ys t u d i e st h ei s s u e so fr e c o n s t r u c t i o no ft h e3 dw o r l d f r o mt h e2 di m a g e s ，a n di so n eo ft h em a i nt a s k so fc o m p u t e rv i s i o n c o m p u t e rs t e r e o v i s i o nt h e o r i e sa n dt e c h n i q u e sc a nb eu s e di nm a n yi m p o r t a n ta r e a ss u c ha s3 db a t t l e f i e l d s m o d e l i n g ，b a t t l e f i e l d s s i t u a t i o nm o n i t o r i n g ，p o s i t i o n i n ga n dn a v i g a t i o n t om e e tt h e r e q u i r e m e n to ft h em i l i t a r yd e v e l o p m e n tf o rt h e3 dt e r r a i nr e c o n s t r u c t i o na n dp o s i t i o n i n g r a p i d l ya n dp r e c i s e l y , t h i sd i s s e r t a t i o nm a i n l ys t u d i e st h ei s s u e so fi m a g ef e a t u r e sd e t e c t i o n a n dk n o w l e d g eb a s e di m a g ef e a t u r e ss p a t i a lr e l a t i o na n a l y s i s w i d eb a s e l i n es t e r e om a t c h i n g 、 r e a l t i m e3 dr e c o n s t r u c t i o na n de r r o ra n a l y s i sa b o u tt h es t e r e ov i s i o nm o d e l s ，a n dp r o p o s e s s o m en o v e la n de f f e c t i v em e t h o d st oc o p ew i t ht h o s ep r o b l e m s f i n d i n go u tb a s i cf e a t u r e si na ni m a g ei sa l w a y st h en e c e s s a r ys t e pi nm a n ya l g o r i t h m s i nc o m p u t e rs t e r e ov i s i o n a f t e rs t u d y i n gt h ep r o p e r t yo ft h es t r a i g h tl i n e ，an o v e l h i e r a r c h i c a la l g o r i t h ma b o u ts t r a i g h tl i n e se x t r a c t i o ni sp r o p o s e di nt h ed i s s e r t a t i o n t h i s s t r a i g h tl i n e se x t r a c t i o nm e t h o de x t r a c t sl o c a l l i n es e g m e n t sf r o ml o c a li m a g ei n t e n s i t y f e a t u r e sa td i f f e r e n ts p a t i a ls c a l e f i r s t ，t h ea l g o r i t h mf o r m sm a n ys h o r tl i n e si nt h el o w e s t l e v e l t h e ni tm e r g e st h e mi n t ou p p e rl e v e la c c o r d i n gt ot h e i ra d j a c e n c ya n ds t r a i g h tl i n e c o n s t r a i n t s f i n a l l yah i e r a r c h i c a ls t r a i g h tl i n e ss t r u c t u r ei sf o r m e da n df i n a ls t r a i g h tl i n e s w e r ee x t r a c t e d i nt h ea r e ao fr e g i o nf e a t u r e sd e t e c t i o n ，a n o t h e rc o n t r i b u t i o ni n t h i sw o r ki st h a ti t p r o p o s e sar o b u s ts e g m e n t a t i o na l g o r i t h m ，t h i sa l g o r i t h mu s e sd i f f e r e n tm e t h o d sd e a l i n g w i t hd i f f e r e n tp i x e l si nt h ei m a g ea c c o r d i n gt oi t sp o s i t i o n ，n a m e l yu s i n gs i m p l ea v e r a g e m e t h o dd e a l i n gw i t ht h ep i x e l sw h i c ha r ei nt h ep o s i t i o no f d i s t a n c et oe d g e so f r e g i o n s ，a n d u s i n gt h em e a ns h i f ta l g o r i t h md e a l i n gw i t ht h eo t h e rp i x e l s ，w h i c ha r ep o s s i b l yn e a rt h e e d g e so fr e g i o n s ，b o t hi nc o l o rs p a c ea n ds c a l es p a c e i ti s o b v i o u st h a tt h ep r o p o s e d a l g o r i t h mi se f f e c t i v ea n d r o b u s t t h ek e yp r o b l e mt o3 dr e c o n s t r u c t i o ni si m a g ec o r r e s p o n d e n c e ak n o w l e d g eb a s e d i m a g ea n a l y s i ss y s t e mf r a m e w o r ki sp r o p o s e di nt h ew o r ka i m i n gt od e a lw i t ht h ei m a g e m a t c h i n gp r o b l e m si n3 dr e c o n s t r u c t i o n i nt h i sf r a m e w o r k ，k n o w l e d g ec a nb ec l a s s i f i e da s k n o w l e d g ea b o u ti m a g ep r o c e s s i n gi t s e l f ，k n o w l e d g ea b o u ts p e c i f i ct a r g e ti m a g e sa n d k n o w l e d g ea b o u ti m a g ep r o c e s s i n gt a s k s k n o w l e d g eb a s e di m a g ea n a l y s i ss y s t e me m p l o y s f u n d a m e n t a lk n o w l e d g ea b o u ti m a g ea n a l y s i sa n de x p e r t s k n o w l e d g ei ns p e c i a l i s ta r e at o f i n do u ts p m i a lp e r s p e c t i v er e l a t i o n sa m o n gi n t e r e s t e df e a t u r e si nt h es c e n eo ro t h e rr e l a t i o n s s u c ha sp e r s p e c t i v ev a n i s h e dp o i n tp o s i t i o na n d3 dp a r a l l e ll i n e s i nt h i sw o r k ，an o v e la l g o r i t h mb a s e do nl o c a la f f i n ei n v a r i a n t si sp r o p o s e df o r s e a r c h i n gc o r r e s p o n d e n c e sb e t w e e ni m a g e si nt h em o s tg e n e r a lc a s e ，n a m e l y , u n d e rt h e w i d eb a s e l i n ec o n d i t i o n sa n dw i t h o u ta n yp r i o r ii n f o r m a t i o na b o u tt h ei n t e r n a lo re x t e m a l c a m e r ap a r a m e t e r s t h i sa l g o r i t h mu s e si m a g ep o i mf e a t u r e sa sa n c h o rp o i n t sf o ri m a g e m a t c h i n g ，a n dt h el o c a ls p a c e - v a r i a n t sr e g i o n sa r o u n dt h ea n c h o rp o i n ta r eu s e da sl o c a l w i n d o wr e g i o nt og e n e r a t eg e o m e t r i ca f f m ei n v a r i a n t sa n dc o l o ra f f i n ei n v a r i a n t sf o ri m a g e m a t c h i n g t h ep r o p o s e ds t e r e om a t c h i n gm e t h o di se f f i c i e n ti na l g o r i t h m i ct i m eb e c a u s e o n l yt h el o c a li m a g ef e a t u r e sa r eu s e di nt h ei m a g em a t c h i n gp r o c e s s m e a n w h i l e ，t h ei m a g e m a t c h i n gr e s u l t sa r er e l i a b l ea n dr o b u s tb e c a u s ei t sf e a t u r em a t c h i n gr e g i o ni sr e l a t i v e l y l a r g e ，a n dt h es h a p eo fl o c a lw i n d o wr e g i o ni st r a n s f o r m e da c c o r d i n gt op o s s i b l ep r o j e c t i v e d e f o r m a t i o n i na d d i t i o n ，o v e r l a p p e ds u b r e g i o n sa r eu s e di nl o c a lf e a t u r ee x t r a c t i o nt o r e d u c ep a r t i a l l yo c c l u d i n gp r o b l e m s o n 3 dr e c o n s t r u c t i o n ，t h i sd i s s e r t a t i o nd i s c u s s e st h eb a s i cm e t h o d so f3 dp r o j e c t i v e r e c o n s t r u c t i o na n d3 de u c l i d i a nr e c o n s t r u c t i o n ，ab u n d l ea d j u s t m e n ta l g o r i t h mf o r3 d r e c o n s t r u c t i o n , ar e a l t i m ek a l m a nf i l t e r i n g3 de u c l i d i a nr e c o n s t r u c t i o nm e t h o d ，a n dp l a n e b a s e ds i n g l ev i e wa n dm u l t i - v i e wc o n s t r a i n t sa l g o r i t h mf o r3 de u c l i d i a nr e c o n s t r u c t i o n i n t h i sw o r k ，s t e r e oc a m e r am o d e le r r o ri sa l s od i s c u s s e d as e to ff o r m u l a t i o n sa b o u t t h ee r r o r so f3 de u c l i d i a nr e c o n s t r u c t i o na r ed e d u c e db o t ho nc a n o n i c a ls t e r e oc a m e r a m o d e la n dc o n v e r g e n c es t e r e oc a l t l e r am o d e l f r o mt h o s ef o r m u l a t i o n s ，s o m ec o n c l u s i o n s a b o u te r r o r s ，e r r o r sv a r i a t i o na n de r r o r sd i s t r i b u t i o na r ed r a w ni nt h ew o r k i nt h ea p p l i c a t i o no fc o m p u t e rs t e r e ov i s i o nt h e o r i e sa n dt e c h n i q u e s ，t h i sd i s s e r t a t i o n p r o p o s e sas y s t e mf r a m e w o r kc a l l e dr a p i d3 dd i g i t a lt e r r a i nr e c o n s t r u c t i o ns y s t e ma n di t s i m p l e m e n t a t i o nt e c h n i q u e s i nt h es y s t e m ，i n t e r a c t i v es y s t e ma n dr e a l t i m es y s t e ma r e i n t e g r a t e d ，f r o mi n t e r a c t i v es u b s y s t e mt h er e l i a b l ea n dp r e c i s e3 d r e c o n s t r u c t i o nr e s u l t sc a n ；” b ea c h i e v e d ，a n df r o mr e a l t i m es u b s y s t e mr a p i dr e c o n s t r u c t i o nc a nb er e a l i z e d t h i s a p p l i c a t i o ns y s t e m c o n s i s t so f g r o u n d c o n t r o l s u r v e y i n gs u b s y s t e m ，i n t e r a c t i v e r e c o n s t r u c t i o ns y s t e ma n dt h er e a l - t i m er e c o n s t r u c t i o ns u b s y s t e mb a s e do i lm a p so r g p s i n sn a v i g a t i o na n dp o s i t i o n i n gm e t h o d t h ed e s i g na n di m p l e m e n t a t i o no ft h i s a p p l i c a t i o ns y s t e ms h o w st h a tt h ep r o p o s e dm e t h o d si nt h ed i s s e r t a t i o na r eo fc o r r e c t n e s s a n dp r a c t i c a b i l i t y k e y w o r d s ：c o m p u t e rv i s i o n ；s t e r e ov i s i o n ；f e a t u r ee x t r a c t i o n ；i m a g es e g m e n t a t i o n ；i m a g e a n a l y s i s ；i m a g eu n d e r s t a n d i n g ；i m a g es t e r e om a t c h i n g ；w i d eb a s e l i n es t e r e o c o r r e s p o n d e n c e ；3 dr e c o n s t r u c t i o n ；r e a l t i m er e c o n s t r u c t i o n ；e r r o ra n a l y s i s 1 1 计算机视觉三维重建 第一章绪论 视觉是人类获取信息、认识世界的重要途径。人类通过眼睛和大脑来获取、处理 和理解视觉信息。环境中的物体发出的光线通过眼睛在视网膜上成像，经过视网膜感 光细胞的能量转换和视网膜神经元的初步处理，由神经纤维经视交叉和外侧膝状体传 送至视区大脑皮层进行处理、解释和理解。计算机的问世使人类科学与技术取得了长 足的进步，并导致了一批新兴学科的诞生。人们用摄像机获取环境中物体的图像并将 其转换为数字信号，用计算机实现信息处理，试图建立以计算机为中心的视觉系统， 替代或在某种程度上和某种环境下替代人类的部分视觉工作。 计算机视觉要达到的最终目的是实现对于三维景物的理解，即实现人类视觉系统 的某些功能【1 3 0 1 。计算机立体视觉研究的对象是利用二维投影图像恢复三维景物。使用 的理论方法主要是基于几何、概率、运动学计算与三维重构的计算机视觉理论。它的 基础包括射影几何学、刚体运动力学、概率论与随机过程、图像处理、人工智能等理 论。从影像中提取场景的三维结构是计算机视觉几十年来一直在研究的问题。这方面 的研究成果使计算机视觉的应用领域不断拓展。同时，应用需求对计算机三维视觉提 出了进一步要求。这种相互推动作用使得计算机三维视觉研究不断取得进步。 1 2 国内外研究状况 2 0 世纪7 0 年代中期，以m a r t ，b a r r o w 和t e n e n b a u m 等人为代表的一些研究者提 出了一整套视觉计算的理论来描述视觉过程，其核心是从图像恢复物体的三维形状。 s tb a r n a r d 与m a f i s c h l e d 9 5 】系统介绍了上世纪7 0 年代中期到1 9 8 1 年三维视觉的 研究成果，主要包括立体重建的基本方法、算法评价准则以及对当时比较有影响的算 法的评述。上世纪8 0 年代中后期，随着移动式机器人等相关应用的研究，大量运用空 间几何的方法以及物理知识来研究立体视觉，引入了主动视觉的研究方法，并采用了 距离传感器以及引入融合技术等。由于这种研究方法可直接取得深度图或通过移动获 取深度图，因而使很多病态问题变成良态的。u r d h o n d 和j k a g g a r w a l l l 0 4 1 对上世 纪8 0 年代的立体视觉进展进行了详细评述，介绍了大量影像匹配方法，引入了层次体 1 系处理的概念，并采用三目立体约束以减少立体匹配的二义性。到上世纪9 0 年代初， 关于立体视觉的研究在许多方面开始趋于成熟。最近十多年来，计算机立体视觉在多 个领域内取得了重要进展，包括区域匹配和特征匹配的新的算法技术、遮挡处理方法、 多摄像机立体视觉、立体视觉实时实现方法等。m z b r o w n 、d b u r s c h k a 和g d h a g e r 【”1 介绍了1 9 9 3 年以来十年期间计算机三维视觉研究的进展。讨论了影像点对 应方法、处理遮挡的方法以及实时算法等。d s c h a r s t e i n 和r s z e l i s k i l 2 1 】对于近期的算 法性能进行了比较。c s c h m i d 和a z i s s e r m a n 掣1 0 1 讨论了自动直线匹配并通过多视图 重建建筑物的方法。c a r s t e nr o t h e r 等给出了一种线性多视图重建同时恢复摄像机参数 的方法【1 6 1 。h a r t l e y 和z i s s e r m a n 7 5 1 ，0 f a u g e r a s 和q 一t l u o n g 6 5 1 给出了大量的多视图 立体重建方面的算法。 计算机立体视觉按照不同视点拍摄的两幅或多幅图像来确定场景的三维结构。问 题的基础是现实世界中的单一的三维位置投影到唯一的一对影像位置上。因此，给定 两个摄像机的影像，如果能够确定两张图像上同名像素点，那么就可以确定该点的三 维位置。计算机视觉需要解决的主要问题包括摄像机标定、立体匹配和重建。摄像机 标定方法可以分为传统标定方法、自标定方法和基于主动视觉的标定方法。传统标定 方法使用结构已知、精度很高的标定块作为空间参照物，通过空间点和图像点之间的 对应关系建立摄像机模型参数的约束，然后通过优化算法来求取这些参数。摄像机自 标定依靠多幅图像对应点之间的关系直接进行摄像机标定【6 3 1 1 7 3 胴1 ，是上世纪9 0 年代 中后期在计算机视觉领域兴起的最重要的研究方向之一。基于主动视觉的摄像机标定 2 9 1 1 3 2 】是指在已知摄像机的某些运动信息下标定摄像机的方法，已知信息包括定量信 息和定性信息。其主要优点是通过已知摄像机的运动信息，线性求解摄像机模型参数， 因而算法的稳健性较好。 影像立体匹配是计算机三维视觉的核心问题，实现立体匹配可以分为基于区域灰 度的匹配方法和基于特征的匹配。因此，特征的提取和描述也是十分重要的一个环节。 1 2 1 影像特征提取 基于特征的匹配依赖于对特征的定义和特征提取方法。就一般意义上说，基于区 域灰度的匹配方法也是基于特征的匹配，因为影像灰度本身就是一种特征。特征通常 包括区域特征、边缘特征和点特征。 2 1 2 1 1 区域及边缘特征 区域特征可能是具有适当大小的高对比度区域的投影，例如建筑物、水库等。区 域的重心对于尺度变化、旋转是不变量，并且对于随机噪声和亮度变化具有稳健性。 区域特征通过影像分割算法进行检测。区域分割的准确程度对于影像匹配有重要 影响。a g o s h t a s b y 等 4 1 提出了一种逐步求精的处理过程来改善匹配质量。该算法将图 像分割和匹配结合在一起，概略的分割产生概略的匹配，通过概略匹配计算分割参数 再次分割图像。通过迭代获得更好的匹配结果。 近来，区域尺度不变量特征的提取受到广泛注意。a l h i c h r i 和k a m e l l 5 9 1 提出了虚 园的概念。文献f l l o 提出了一种仿射不变量描述方法，该方法使用h a r r i s 算子检测角 点按照过角点的边缘给出仿射不变量描述。解决这个问题的另一种方法是m a t a s 等删 提出的区域不变量特征描述，该算法在影像亮度变化均匀的区域，计算最大稳定区域 极值。 边缘线可以是一般线段、目标轮廓、道路以及区域边界等。线状特征检测算法包 括c a n n y 算子、m a r r 的基于l a p l a c i a no fg a u s s i a n 的算法等。 1 2 1 2 点特征 点特征通常是角 5 6 】、线的交点1 6 】等，也包括局部曲率不连续的点【1 叫、区域重心、 关于具体相似性测度的最具有区分性的点【7 i 等。 在大多数情况下，点特征检测算法按照角点、区域重心或局部幅度极大值束进行。 角点形成一类点特征。大多数相关工作致力于提高算法精度、可靠性以及算法效率上。 文献【1 1 4 给出了角点检测算法的评述。文献【6 3 】较为全面的评述了点特征检测算法， 分析了检测算子的局部性质。角点特征被广泛用作控制点，因为它既具有影像几何特 征不变性，同时也为人的视觉系统所感知。 k i t c h e n 和r o s e n f e l d 提出了利用影像函数的二阶偏导数检测角点的算法。但二阶 偏导数算法对噪声较为敏感。针对这种问题，w f o r s t n e r 提出了一个基于一阶导数的 角检测算法【1 13 1 。该算法优点是稳健性较好，缺点是效率较低。 s m i t h 和b r a d y 选择了更为直观的算法1 9 0 1 ，称为s u s a n 算法，通过计算窗f _ 】内与 窗口中心相同灰度像素的数量来确定角点，具有很好的稳健性。t r a j k o v i c 和h e d l e y 设计了一种算、法【m 2 1 ，其思想是角点上各个方向上亮度变化应该较大。z i t o v a 等3 2 1 提出 了一个参数化的交点检测算法，不使用导数并能够处理模糊影像及噪声。 1 2 2 立体视差计算 在立体视差计算方面，通过使用不同的约束可以获得许多不同的方法。所有这些 方法都需要进行影像匹配，即确定一个影像上的像点在另一张影像上相应像点的位置。 主要的匹配算法可以分为局部算法和全局算法两大类。局部算法主要有块匹配算法 【1 8 】【6 4 】【6 7 】【7 9 】、基于梯度的优化算法【5 】【1 删和基于特征的匹配算法】【2 4 l 【8 7 1 1 9 1 】【1 0 4 】【1 叫等。块 匹配算法在局部小区域内寻找最佳匹配使匹配误差最小，通常使用规范化互相关方法， 包括规范化互相关、平方差之和、规范化平方差之和、绝对差之和方法等。基于梯度 的优化算法在局部区域内通过最小化图像问平方差的和来实现匹配。该算法假设场景 中同一个点在两个视图内的影像亮度不变。通过建立运动和影像亮度的微分方程来计 算局部小区域内的视差。基于特征的匹配算法匹配可靠的特征。块匹配算法和基于梯 度的匹配算法对于图像的局部不连续和一致性纹理问题敏感，无法得到满意的解答， 从而使基于特征匹配的算法得到发展，如基于分层的特征匹配和基于图像分割的匹配 算法等。分层的特征匹配将图像特征分为几个层次( 线、点、边缘和面) ，匹配从最高 层次开始直到最低层次，通过较为粗糙但可靠的上层特征，为较为精细的下层特征提 供支持。基于图像分割的匹配将图像分割后对区域进行匹配。 全局算法使用全局约束解决由于遮挡和一致性纹理造成的局部匹配失败问题。全 局对应算法包括动态规划算法【3 3 】【7 2 】【8 6 】【9 3 m o 】、本征曲线( i n t r i n s i cc u r v e s ) 算法【1 4 】【15 1 、 最大流量图算法、最小割集算法( g r a p hc u t s ) 2 8 3 4 1 1 9 2 1 1 1 0 5 1 【1 1 6 7 1 、非线性扩散( n o n l i n e a r d i f f u s i o n ) 算法【2 1 【2 0 1 1 3 酊、信心传播( b e l i e f p r o p a g a t i o n ) 算法 3 9 1 等。除此以外，还有一 些不寻求图像对应而重建图像的算法，如0 f a u g e r a s 的算法、pf u a 的方法【7 l 】以及 k n k u t u l a k o s 算法【4 5 】。 动态规划算法通过将优化问题分解为更小、更简单的子问题从而降低计算复杂度， 通常使用外极线来实现次序约束。本征曲线是对图像按扫描线计算边缘或点特征的描 述矢量，算法将外极线映射到本征曲线空间从而将搜索问题转化为最小邻居查找问题， 并通过动态规划解决二义性问题。本征曲线的主要优点是它对视差的不变性。最大流 量图划分算法将视差表面作为最大流量图中的最小割边集进行求解，非线性扩散算法 通过局部扩散处理提供聚类支持。 局部算法具有较高的效率，但是容易受到遮挡、纹理等问题的影响。与此相反， 全局算法对上述问题不敏感，但计算效率较差。 4 1 2 3 实时三维重建 近十年来，实时稠密立体视差匹配已经成为现实。但是直到最近，真f 能够实现 实时处理的系统都需要像数字信号处理器( d s p ) 或者可编程门阵列( f p g a ) 这样的 专用硬件支持。 o f a u g e r a s 等使用d s p 和f p g a 硬件开发了一个立体系统畔l ，采用标准化相关 匹配，同时采用左右匹配进行一致性检查。其f p g a 实现能够以每秒3 6 帧的速度处 理2 5 6 x 2 5 6 像素的影像，比他的d s p 实现快3 4 倍，比在s p a r c2 工作站f ：的软件实 现快2 1 0 倍。l m a t t h i e s l 4 8 】报道的实时立体视觉系统采用d a t a c u b em v 2 0 0 影像处理 板和6 8 0 4 0c p u 板，在拉普拉斯影像金字塔上进行s s d 匹配，同时采用左右匹配进 行一致性检查，能够以每秒1 7 帧的速度处理2 5 6 x 2 4 0 像素的影像。j w o o d f i l l 和v o n h e r z e n l 4 i 】介绍的立体匹配系统采用1 6 块x i l i n x4 0 2 5f p g a ，以每秒4 2 帧的速度处理 3 2 0 x2 4 0 像素的影像。而p c o r k e 和d u r r a 的系统1 6 9 】使用相似的算法，采用f p g a 硬 件实现，能够以每秒3 0 帧的速度处理2 5 6 x 2 5 6 像素影像。1 9 9 9 年，k i m u r a 等8 9 1 报道 的称为s a z a n 的有九个摄像机的立体视觉系统，采用多基线立体重建算法，使用线 性非时变数字滤波器实现l o g 滤波和高斯平滑，用f p g a 实现相似性比较，能够以每 秒2 0 帧的速度处理3 2 0 x 2 4 0 像素的影像。h e i k oh i r s c h m u l l e r 【3 0 】改进了基于相关匹配 的立体视觉实时算法。随着计算机系统性能的不断提高，有些系统已经可以在1 4 g h z 的p e n t i u m i v 计算机上以每秒2 0 帧的速度处理3 2 0 x 2 4 0 像素的影像。 1 3 论文的主要工作和内容安排 随着科学发展和技术进步，高性能、高精度的作战武器不断装备军队。这些装备 越来越依赖于对战场环境精确、及时的数字描述。运用计算机立体视觉理论和技术， 通过卫星、侦察机等多种手段获取战场环境信息，实现对战场环境的快速重建十分必 要。数字化战场环境为动态三维战场显示、精确打击武器的运用、计算机辅助作战规 划等提供了精确的三维模型。 目前，计算机立体视觉算法研究已经取得了很多研究成果，包括多视图重建和多 基线重建、实时立体视觉等许多算法确实能够得出良好的结果。但由于图像的复杂性， 自动、实时的视觉导航定位和三维重建的广泛应用还面临一些困难，进展比较缓慢。 许多应用系统需要人工参与，利用人类知识的指导才能顺利实施。随着实时三维重建 5 成为许多领域的应用需求，这种人工参与的处理方法不能满足要求。 本课题的目标是研究和探索能够实现自动、快速三维重建的理论和实现技术。本 文是作者在赵宗涛教授指导下对计算机三维重建理论和实现方法进行研究的一个阶段 性成果的总结。该项研究主要完成了以下几项工作： 1 研究了影像基本特征的提取算法。获取图像基本特征是计算机视觉各种算法的 基础。算法的可靠性、算法精度和速度是后续处理工作的必要前提。 在直线特征提取方面，本文的贡献是提出了一个新的层次结构化直线提取算法， 并分析了算法的时间效率。该算法采用分层构建的思想，在不同尺度上利用局部区域 直线特征构造直线片断，形成一种具有层次的结构化直线描述。算法采用自底向上的 策略，首先构造底层局部直线结构，然后利用业已获得的下层结构构造上层结构，既 利用了影像的局部特征，又利用了整体性质。该算法设计简单，具有较好的算法效率 和稳健性，并可以同时获得不同尺度下的直线特征。 在区域分割方面，本文的贡献是提出了一个稳健的区域分割算法。该算法首先将 影像划分为较为平滑的区域和亮度变化较为剧烈的区域。根据像点是否处于平滑区域 采用不同的方法分别处理。算法采用简单方法处理处于平滑区域的像点，采用相对较 为复杂的移动平均算法在色度空间和尺度空间上处理处于区域边缘的像点。因此，算 法兼顾了时间效率和稳健性。另外，本文还研究了快速影像点特征提取算法，探讨了 图像点模糊程度的描述方法。 2 研究了基于知识的影像分析与解释方法。由于图像的复杂性，任何影像分析算 法都有其局限性及其适用范围。在人类高层知识的指导下，通过选择不同的算法和不 同的算法参数可以获得较好的分析结果。另一方面，人类视觉系统往往通过记忆、假 设与检验的方法迅速得出结论。本文试图将针对具体应用问题的图像分析专家知识融 合到图像分析之中，获得对于平面影像的空间感知，进而可以自动发现影像控制点。 这方面的主要工作和贡献包括： ( 1 ) 针对三维重建任务，本文提出了一个基于知识的图像分析系统模型。该模型 将相关知识划分为基本影像处理知识、与具体目标影像相关的知识和与分析任务相关 的知识。这种划分使影像分析专家知识与过程性影像分析模块分离，从而更好地发挥 领域专家和程序设计者各自的优势，减小影像处理系统的规模。基于知识的图像分析 系统运用基本影像分析知识和领域专家知识对场景中基本特征关系进行分析，以获得 场景中透视关系或其它特定几何关系的定性表达。 6 ( 2 ) 探讨了图像基本特征元素的组织方法以及图像分析知识的表达方法。 ( 3 ) 探讨了几何结构分析与目标识别的算法过程。 3 研究了影像匹配算法。在这一方面，本文的主要贡献是提出了一个基于局部仿 射不变特征的宽基线条件下的影像匹配算法，处理最一般条件下的影像立体匹配问题， 不需要预先获取有关摄像机的内外参数，也不需要预先了解影像的内容。该算法采用 点特征算子提取影像点特征作为匹配定位点，并建立以定位点为中心的分层多尺度各 向同性圆形窗口，通过计算中央区域内的几何仿射不变量特征和亮度仿射不变量特征 建立窗口区域的初始匹配。然后，按照中央区域的特征类型对内外层区域按照局部亮 度、旋转和尺度不变特征进行匹配。算法利用局部特征进行宽基线立体匹配，因此具 有较高的效率。算法在较大窗口范围内构造尺度、旋转不变特征组合，并考虑到可能 存在的投影变形而对窗口形状进行变换，因而具有较高的匹配可靠性。通过将大窗口 划分为较小的重叠子区域，算法可以获得较好的匹配精度，同时减少遮挡造成的不利 影响。实验证明，算法能够较好的解决宽基线立体匹配问题。 4 讨论了未标定摄像机的两视图三维射影重建和欧氏重建的基本算法，光束法平 差三维重建算法，实时k a l m a n 滤波修正算法等。探讨了基于平面图的单视图约束和 多视图约束三维重建算法。 5 研究了标准立体视觉模型和汇聚立体视觉模型，推