（机械电子工程专业论文）基于双幅图像的匹配算法及3d重建不确定性研究.pdf

摘要计算机视觉是实现模式的自动识别即以计算机完成对视觉信息处理的科学，是基础研究和应用研究中重大的挑战之一。而图像匹配由于其涉及的问题众多，是计算机视觉中最困难、最关键的一步。为了认识影响3 d 重建精度的来源和规律，在计算机视觉系统中引入三维重建的不确定性描述是必要的。本文探索性地提出了一种基于梯度场相似性和邻域膨胀的快速图像匹配算法。用s u s a n 法检测到我们感兴趣的特征一角点，改进的s c o t t 和l o n g u e t h i g g i n s 算法完成角点的匹配，进而进行基础矩阵估计。从一点的某邻域内梯度场相似性出发，利用极线约束完成全象素匹配。提出的邻域膨胀方法能有效处理多候选点的问题，与传统的利用连续1 眭约束、匹配强度算法等相比能明显加快匹配速度，自适应邻域的匹配策略能够保证较高的精度和可靠性，算法受光照条件的影响较小且适合不同尺度图像。方法的多样性及采用的分析工具的不同，建立统一的误差分析模型并不现实。由于得到基于误差传播理论的重建不确定性显式公式并没有直观性，本文在推导出三维重建扰动分析模型的基础上，应用多元分析的统计方法研究了图像量化误差、匹配误差、标定误差等对重建精度的影响。采用计算机仿真图像进行实验，向重建模型中输入高斯噪声进行扰动分析，这样有利于对不确定性的评定。对三维重建点伸展不确定性的可视化也进行了探讨。本文给出的扰动模型和多元分析的方法具有更大的通用性。对提出的匹配算法及重建不确定性研究的理论与方法，本文给出了其软件实现及实例分析结果。介绍了模块的整体设计并给出几个关键问题的程序分析。实验验证了匹配算法的有效性并得出了重建不确定性研究的若干重要结论。关键词：计算机视觉，图像匹配，梯度场相似性，邻域膨胀，三维重建，不确定性，多元分析，扰动分析a b s t r a o tc o m p u t e rv i s i o ni st h es c i e n c eo fi m p l e m e n t a t i o no fp a t t e r nr e c o g n i t i o na u t o m a t i c a l l yi nw h i c hc o m p u t e rf i n i s h e si n f o r m a t i o np r o c e s s i n ga n dw h i c hi sr e a l l yat r e m e n d o u sc h a l l e n g ed u r i n gt h ep r o c e s st h ef u n d a m e n t a la n dp r a c t i c a lr e s e a r c ho fm a n k i n d h n a g em a t c h i n gi sm o s td i f f i c u l ta n dc r u c i a li nc o m p u t e rv i s i o nf o rw h i c hi n v o l v e sn u m e r o u sp r o b l e m s t ou n d e r s t a n df a c t o r sa n dr u l e st h a ti n f l u e n c et h ep r e c i s i o no fr e c o n s t r u c t i o n ，t oi n t r o d u c e3 dr e c o n s t r u c t i o nu n c e r t a i n t ya n a l y s i si sn e c e s s a r y t h i sp a p e rp r e s e n t st h er e s e a r c ho f p r o b l e m sm e n t i o n e da b o v e af a s ti m a g e sm a t c h i n ga l g o r i t h mi sp r o p o s e di nt h i sp a p e r , w h i c hi sb a s e do ng r a d i e n ts i m i l a r i t ya n dn e i g h b o re x p a n s i o n ，i n t e r e s t i n gf e a t u r e s ( c o m e r s ) a r ed e t e c t e du s i n gs u s a nm e t h o da n dt h e ya r em a t c h e dw i t hi m p r o v e ds c o t ca n dl o n g u e t h i g g i n sa l g o r i t h m ，t h ef u n d a m e n t a lm a t r i xi se s t i m a t e da f t e rt h a t f r o mt h eg r a d i e n tf i e l ds i m i l a r i t yo ft h et w op o i n t s a 1 1p i x e l sc a r lb em a t c h e du n d e rt 1 1 ec o n s t r a i n to fe p i p o l a rg e o m e t r y t h en e i g h b o re x p a n s i o nm e t h o da n ds e l g a d a p t e dn e i g h b o rs e l e c t i o ns t r a t e g yc a i lh a n d l et h em u l t i c a n d i d a t ep r o b l e me r i e c t i v e l ya n dr o b u s t ，r a p i de n o u g ht ob ei m p l e m e n t e du n l i k em e t h o d sw i t hc o n t i n u i t yc o n s t r a i n t sa n dm a t c h i n gi n t e n s i t ya l g o r i t h m t h ea l g o r i t h mi ss l i g h t l ye f f e c t e db yl i g h t i n ge n v i r o n m e n ta n ds u i t a b l ef o rm u l t i s c a l ei m a g e s u n i f o r mp r e c i s i o na n a l y s i sn l o d e li sh a r dt oa c h i e v ef o rl a r g en u m b e r so fm e t h o d sa n dt o o l su s e d s i n c et h ee x p l i c i tu n c e r t a i n t ye q u a t i o no f3 dr e c o n s t r u c t i o na c h i e v e db ye r r o rp r o p a g a t i o nt h e o r yi sn o ti n t u i t i o n i s t i c ，t h i sp a p e rp r e s e n t sap e r t u r b a t i o na n a l y s i sm o d e lo f3 dr e c o n s t r u c t i o na n ds t u d i e sr e c o n s t r u c t i o np r e c i s i o na f f e c t e db yi m a g ed i g i t a l i z a t i o ne r r o r , m a t c h i n ge r r o ra n dc a l i b r a t i o ne r r o ru s i n gm u l t i d i m e n s i o n a la n a l y s i so fs t a t i s t i cm e t h o d g a u s s i a nn o i s ei sa d d e dt ot h er e c o n s t r u c t i o nm o d e lf o rp e r t u r b a t i o na n a l y s i su s i n gs y n t h e t i ci m a g e s ，t h u si sh e l p f u lf o ru n c e r t a i n t ye v a l u a t i o n f i n a l l y ,e x p a n d e du n c e r t a i n t yo f t h er e c o n s t r u c t e dp o i n t si sv i s u a l i z e d p e r t u r b a t i o na n a l y s i sm o d e la n dm u l t i d i m e n s i o n a la n a l y s i sa r em o r eu n i v e r s a l s o f t w a r eo ft h em a t c h i n ga l g o r i t h ma n dr e c o n s t r u c t i o nu n c e r t a i n t ym e t h o di si m p l e m e n t e da n de x p e r i m e n tr e s u l t sa r eg i v e n g r o s sm o d u l ed e s i g ni si n t r o d u c e da n dd e t a i l sa r ep r e s e n t e df o rk e yp r o b l e m s e x p e r i m e n t st e s t e dt h ee f f e c t i v e n e s so ft h em a t c h i n ga l g o r i t h ma n di m p o r t a n tc o n c l u s i o n so fr e c o n s t r u c t i o nu n c e r t a i n t yp r o b l e ma r e1b r o u g h t k e yw o r d s ：c o m p u t e rv i s i o n ，i m a g e se x p a n s i o n ，3 dr e c o n s t r u c t i o n ，u n c e r t a i n t y ,a n a l y s i sm a t c h i n g ，g r a d i e n ts i m i l a r i t y , n e i g h b o rm u l t i d i m e n s i o n a la n a l y s i s ，p e 心b a t i o n 大连媸工人学碳士学位论文第1 章绪论1 1 引言视觉是人类获取信息强有力而又最有效的手段，人类是通过眼睛与大脑来获取、处理和理解视觉信息的。周围环境中的物体在可见光的照射下，在人眼的视网膜上形成图像，由感光细胞转换成神经脉冲信号，再经神经纤维传入大脑皮层进行处理与理解。视觉，不仅指对光信号的感受，它包括了对视觉信息的获取、传输、处理、存储与理解的全过程。信号处理科学与计算机技术出现以后，人们试图用摄像机获取景物图像并转换成数字信号，用计算机实现对视觉信息处理的全过程，从而逐渐形成了一门新兴的学科，即计算机视觉( c o m p u t e rv i s i o n ) ”1 。现实世界中的物体都是三维的，人眼所获得的景物图像却是二维的，但是人类的视觉系统能够很容易地从二维图像中感知三维世界，获得三维世界的信息。计算机视觉的研究目标就是使计算机具有通过一幅或多幅图像认知周围环境信息的能力。这种能力不仅使计算机能感知环境中物体的几何信息，如其形状、位置、姿态、运动等，而且能对它们进行描述、存储、识别与理解。计算机视觉是一个多学科交叉的新领域，涉及到计算机科学、人工智能、机器人、信号处理、模式识别、控制理论、生物医学、心理学等多个学科领域。其发展得益于神经生理学、心理学与认知科学对生物系统的研究，需要各学科的研究人员联合起来对人脑的认知过程进行从宏观到微观的深入研究。其研究的内容很广泛，包括成像设备及数字化设备；图像滤波及变换、图像特征检测、轮廓表达、基于特征的分割、距离图像分析、形状模型及表达、由单幅图像信息重建三维形状、立体视觉、运动分析、颜色视觉、主动视觉、几何不变量、系统标定、物体检测、三维物体识别及定位等高、中、低层视觉；并行结构、分层结构、信息流结构、拓扑结构等体系结构的研究“。计算机视觉应用领域也很广泛，己应用于遥感图像分析、文字识别、医学图像处理、多媒体技术、图像数据库、工业检测与军事等方面”3 。工业机器人的手眼系统是计算机视觉应用最为成功的领域之一，由于工业现场的诸多因素，如光照条件、成像方向均是可控的，使得问题大为简化，有利于构成实用的系统。目前已有相当数量的手眼系统。对移动机器人而言，主要关心的视觉问题是道路跟踪、避障、特定目标识别等问题。典型的用于道路分析和避障的视觉系统，如卡耐基梅隆大学研制的自主行驶汽车n a v l a b 上的视觉系统。在医学上，与计算机视觉有关的工作包括分类、判断和快速三维结构的重建等方面。近年来与这一主题相关专集的出版和国际会议的举办促进了这一领域的快速发展。通用的物体三维形状分析与识别一直是计算机视觉的重要研究目标。在景物的特征提取、表示，知识的存储、检索以及匹配识别等方面都取得了一定的进展，并且已构建了一些用于三维景物分析的系统。图( 1 1 ) 列举了几个成功应用的例子，计算机视觉在诸多领域的应用和研究浩如烟海。虽然由丁入脑的高度复杂性，这种跨学科的研究还远远不够深入但从事计算机视觉的研究者们已经发展起来一套独立的计算理论和算法，从而能对视觉信息( 或壁翌堕堕垡堕些墼墨垄丝! 旦曼些尘些塞丝业! ! 一者说，对图像) 进行分析和处理。随着跨学科基础研究的不断深入，随着计算机性能的快速提高，计算机视觉会有更为广阔的应用前景。图( 1 1 ) 几个计算机视觉系统f i g u r e1ls e v e r a lc o m p u t e rv i s i o na p p l i c a t i o ns y s t e m s1 2 计算机视觉系统与理论计算机立体视觉的基本原理是从两个或多个视点观察同一景物，获取在不同视角下的感知图像，然后通过视觉计算重建景物的三维信息。这一过程与人类视觉的立体感知过程是类似的。一个完整的计算机立体视觉系统通常包括以下五个部分：数字图像采集、摄像机标定、图像预处理及特征提取、立体匹配以及三维重建“。如图( 1 ，2 ) 所示。牵卤塌哟凹( 1 2 ) 计算机立体视觉系统组成结构f i g u r e12c o m p u t e rs t e r e ov i s i o ns y s t e ma r c h i t e c t u r e计算机视觉的研究开始于五十年代中期，当时的研究主要集中在二维景物图像的分析。利用二维图像解释三维目标和景物的研究始于1 9 6 5 年r o b e r t s 对多面体识别中提出的“积木世界”。在这之后，随着研究的深入，提出了有代表性的计算机视心用领域发例丁_ ：参考于h t t p ：w w w - 2 c sc m ue d u c i l v i s i o nh t m l ( t h e c o m p u t e r v i s i o nh o m e p a g e ) 等州络资源查堑些! 叁兰塑! 堂丝丝苎觉的三个理论框架：m a r r 的计算视觉理论框架；基于知识的视觉理论框架；主动视觉理论框架。但上述的视觉信息理论还都不能自成系统地、可靠地处理视觉问题，一些研究者提出了各种对上述理论进行修改的设想。基于模型的视觉( m o d e lb a s e dv i s i o n ) 是其中有代表性的一种，它认为信息的概念是与从一组候选的对象中做出选择相联系的。如果不知道一组可供选择的刺激或响应，人们就对刺激或响应无从、蜕起。此外，人们还必须知道定义这组候选对象以及能够对这组候选对象的成员之间进行区别的特征，而且随着要解决任务的不同，这些特征也是不同的。在感知中，选择是根据不变量( c o n s t a n c i e s ) 和参数( p a r a m e t e r s ) 做出的。如果一个婴儿能听到声音，而他的感知不变量只包括”安静”和”噪声”的话，那么任何音乐对他来说将包括一样多的信息，但是这些音乐对一个训练有素的音乐家来说则包含丰富得多的信息。这种视觉理论利用特征检测器的概念把点状的图像数据与宏观信息相联系”1 。另一种有代表性的理论是基于连接机制的模型，它提供了一种并行计算结构，其前提是认为单个神经元并不传递大量的符号信息，而是通过与许多相似的神经元以适当豹方式联结来完成计算处理的。1 3 选题背景及文献综述1 3 1 选题背景计算机视觉作为一个多学科交叉领域，吸引着大批包括视觉生理、心理、物理、数学以及计算机科学等多种学科的研究人员运用不同的技术手段对之进行深入的研究；并且在现代工业、国防、医学、空间技术等领域有着广阔的应用前景。对计算机视觉的研究不仅具有重要的理论意义，而且具有重要的实用价值。( i ) 人们生活和工作在三维几何空间中，对外界的感性认识首先是各种三维物体的形体，三维几何的信息处理是人类活动中最重要的也是最基本的信息处理内容。与几何处理及其显示相关的学科实际是一个大学科群。一方面，研究从主观构思到生成模型和模拟客观世界显示的正向过程，主要是计算机图形学、c a d 等；另一方面，研究从客观世界实物原始数握进行分析建模的逆向过程，主要是计算机视觉、数字图像和视频处理、模式识别等。其中，逆向过程因其从二维信息求取三维信息，存在多义和多解的障碍，需要进行大量的智能分析和推理，较之正向过程的难度相对更大。但是，如果逆向处理识别重构技术能够取得进展，必将促进整个几何处理及显示大学科群的发展。计算机视觉属于基于影像的重构技术，具有非接触性测量、实施较为简易的特点，具有广阔的应用前景，是有待于进一步开发的领域。( 2 ) 计算机视觉是在图像处理的基础上发展起来的新兴学科。计算机视觉从信息处理的层次研究视觉信息的认知过程，研究视觉信息处理的计算理论、表达与计算方法。进入八十年代后，计算机视觉理论获得了蓬勃的发展，尤其是受高分辨率数字相机出现的影响。三维重建就是利用图像或其它信息和手段定量研究实物或场景的三维空问特征的技术。出十存在直建精度、系统复杂性、数学模型的有效性等问题，= 维重建的研究颇赋挑战性”1 。基于图像的立体匹配和三维重建长期以来一直是个热点研究问早于职幅剀像的匹配算法及3 d 重硅小确定研究题，而基于双幅图像的研究更具一般性。( 3 ) 随着对应用系统的自动化程度和智能水平要求的提高，许多实际应用系统都希望增加机器视觉功能。而近年来，c c d 光电输入和数字化技术的不断进步，数码相机的普及，硬件装置价格的不断下降，计算机性能的不断提高，也为计算机视觉技术的应用准备了条件，使得计算机视觉技术的应用更加广泛和普及。且论文得到了国家自然科学基金( 5 9 8 0 5 0 0 1 ) 资助。13 2 文献综述计算机视觉中的3 d 表达和重建( 3 dr e p r e s e n t a t i o na n dr e c o n s t r u c t i o n ) 主要应用在工业过程动态监控与质量控制、工业产品的外观设计、机器人视觉、自动车导航、会议电视与可视电话、医学整形和美容、军事上跟踪多目标、测量飞行体动态学以及运动目标识别和检测、虚拟现实、三维轮廓测量、艺术雕塑、建筑等领域，是计算机视觉的热门研究问题。尽管目前还面临一些困难，进展比较缓慢，但认知神经科学、视觉计算理论等基础科学的发展，必将推动计算机视觉的发展与广泛应用。立体匹配( s t e r e om a t c h i n g ) 是计算机视觉中最重要也是最困难的问题，其早己引起了国内外众多学者的兴趣。图像匹配问题一旦解决，计算机视觉中的诸多问题便迎刃而解了。计算机视觉的初期研究深受摄影测量方法的影响，基本上不考虑测量误差或认为测量误差是各向同性的。而两者有很大差别，前者通常不用专用底片或c c d 设备，成像畸变、低分辨率等的影响使其初始测量误差远远高于摄影测量系统。测量误差定量描述的弓i 入是必要和有效的，定量的误差分析( e r r o ra n a l y s i s ) 已渐成气候”1 。一3 d 重逢3 d 重建就是利用图像或其它信息和手段定量研究实物或场景的三维空间特征的技术。属初级视觉问题。立体视觉方法进行3 d 重建，是指由两幅或多幅两维图像获取实物的深度信息来恢复3 d 形状的方法。立体视觉方法涉及到了三维重建中一些共性问题，具有代表性。i 图像获取图像的获取是立体视觉的物质基础。图像一般是双目图像或多目图像，摄像机视点可在直线、平面或呈立体分布。图像含有丰富的三维信息。2 摄像机标定是求解摄像机内外参数( 焦距、象素点间距、变形系数、摄像机与实物的空间关系等) 的过程。目前主要方法有：1 ) 传纺粝毫涕即传统的摄影测量学标定方法。标定中考虑了摄像机成像中的各种因素，应用最优化算法，需先选择较好的初始值迭代。计算量大，精度高。考虑了镜头的变形情况。+2 ) 童旅缘拦耍攒苈先设中间变量，通过线性优化建立和求解内外参数。不需迭代，计算量小，没有考虑非线性畸变问题。3 ) l 垂龆耍攒矩绎躇从透视变换角度建立摄像机成像模型。类似直接线性变换法，无需优化，可得到较好的隐式解。没考虑非线性畸变，若加入非线性因素，求解复杂。4 ) 历步荔窟甚t s a i 提出考虑畸变因素的两步标定法。首先用透视矩阵变换查堕些三生堂堡! ：兰些丝苎的方法求解线性解，以此为初始值，考虑畸变，采用优化方法提高标定精度。只考虑了二阶畸变因子( 径向畸变) 没考虑三阶的切向因子。5 ) 立筋扭劳旃宕甚先对每个摄像机标定，再通过同一世界坐标中的一组定标点建立摄像机之间的位置关系。标定中要有精确的摄像机外部参数。国廖菝定技恭以上方法都需要在摄像机前放置己知实物，即标定参照物。自标定无需参照物，利用投影几何中绝对二次曲线不变量性质等采用多幅图像来综合分析得到摄像机的内外参数。3 特征提取与匹配根据视差确定3 d 信息关键是要找出不同图像中特征的对应关系。特征是泛指的，可以是象素、象素集合或它们的抽象表达。如点状、线状、区域等特征。大尺度特征信息丰富，匹配快，但提取和描述复杂，定位精度差。小尺度特征则相反。立体匹配是立体视觉中最关键的一步。匹配指根据计算特征，建立其对应关系并由此得到相应的视差图像。由于噪声干扰、量化误差、成像畸变、光照条件等等原因，匹配也是最困难的。4 3 0 信息恢复立体匹配得到视差图后便可实现3 d 重建，即恢复实物的3 d 信息。但出于数字量化效应、摄像机标定误差、特征检测与匹配误差等影响了距离测量的精度。5 后续处理后续处理主要是解决3 d 信息恢复的不完整性和误差等。基于特征的立体匹配算法只能得到特征处的视差图，因此要经过最临近插值、双线性插值、样条插值、基于模型的内插等深度插值技术得到非特征处的视差值。由于成像畸变、躁声干扰、光滑区域的存在、遮挡效应、约束不严格、量化误差等的影响，需要对匹配进行误差校正。获得一般立体视觉象素级视差后，有时要进一步改善达到亚象素级视差精度“。有些方法不需要获得立体图像，计算深度获得3 d 信息。如采用莫尔条纹干涉法、傅立叶变换轮廓法、相位测量法、主动三角形法j 几何光学聚焦法、飞行时间法等经过处理后直接获得实物深度信息进行重建。立体视觉重建方法的优点是几何关系明确，但需要确定特征及匹配，这是很困难的。且受遮挡效应等原因而无法进行匹配。缩短基线长度可以减弱遮挡效应但匹配精度降低。为了避免匹配，也可以从系列单目图像信息来进行3 d 重建。从图像中各种3 d 线索来求解实物形状称为“从x 得到形状( s h a p ef r o mx ) ”，其中x 可以是阴影、轮廓、纹理、运动等等。“。二立体匹配立体匹配是计算机立体视觉中最重要也是最困难的问题。当空间三维场景被投影为二维图像时，同一景物在不同视点下的图像会有很大不同，而且场景中的诸多因素，如光照条件，景物几何形状和物理特性、噪声干扰和畸变以及摄像机特性等，都被综合到了图像的灰度值中。因此，要准确地对包含了如此多不利因素的图像进行无歧义的匹配，是十分困难的。立体匹配方法的有效性有赖于三个问题的解决，即：选择正确的匹配特征，寻找特征问的本质属性及建立能正确匹配所选特征的稳定算法。闸绕这i 个方丽的t 作目前已有大量备具特色的阢配方法。但是由于立体匹配涉及的问题太多，至今仍未得到很好的解决，特别是在复杂场景中，如何提基于双幅幽像的匹削算法及3 d 重建刁i 确定件研究高算法的无歧义匹配和抗干扰能力，降低实现的复杂程度和计算量，都需要进行更深入的探索和研究“”“。1 9 7 6 年，m a r r 首先提出了模拟人类立体视觉机制的匹配算法，g r i m s o n 实现了该算法”。其核心是首次采用多分辨率v2 g 零交叉作为匹配基元，利用零交叉分布特性和由粗到细引导的多通道协同匹配技术来解决歧义性和搜索空间大的问题。1 9 8 5 年g r i m s o n 对该算法进行了改进”，在匹配中利用视差沿零交叉轮廓线连续的约束来保证匹配的一致性。m a y h e w 等以视觉生理学的观点对m a r r 的零交叉匹配基元和匹配约束进行了补充修正，提出v2 g 的卷积峰也应是人类立体视觉的匹配输入基元，并基于人类视觉首先观察重要的目标轮廓信息这一事实，提出了形状连续性约束2 “。相位是图像的一个重要信息，为立体匹配提供了一种新的思路。早在七十年代，r o b s o n 就从生理学角度证明了人类视觉系统中的简单视细胞是以正交相位关系形式成对出现的，并且可以用一对实部与虚部相互正交的复数滤波器来摸拟。”。j u l e s z等也指出相位信息在人类解释景物像点之间关系的过程中起着重要的作用。，相位信息可能是人类立体融合中最理想的基元形式。基于此，s a n g e r 和j e n k i n 等提出了基于g a b o r 滤波相位的立体视觉系统“。游索亚等于1 9 9 3 年提出了采用h a r d y 小波变换相位为基元的匹配算法。该方法模拟了人类视觉细胞的正交相位关系，利用h a r d y 小波基函数将原始图像对表示成一系列具有良好空频域定位性的正交带通分量，以带通分量的相位信息作为匹配基元，从而将视差估计转化为小波相位差估计问题。1 。根据匹配特征和方式的不同，立体匹配技术基本上分为两大类：狄度区域相关匹配和基于特征的匹配。与灰度相关法不同，基于特征的匹配方法是有选择地匹配能表示景物自身特性的特征。b a k e r 和a r n o l d 等提出以边缘点为匹配特征的匹配算法”“3 “，并在匹配时首次采用了动态规划技术，将左右图像同一扫描线上的匹配特征，分别等效为动态规划的阶段与状态，通过在二维规划平面上搜索最佳路径得到最优匹配。此后，o h t a 提出了以边缘线为匹配特征的动态规划算法1 。l l o g d 的算法以边缘点为匹配基元，综合利用动态规划和概率型的松弛标记技术o “。松弛技术也是解决立体视觉匹配的有效手段。首先利用简单的相似准则求得初始匹配，然后根据匹配特征间的几何和视差约束，利用松弛迭代技术增强初始匹配结果，使正确匹配的概率上升，从而达到解决歧义匹配的目的。b a n a r d 提出一种匹配算法，采用h o r a v e c 算子的“兴趣点”作为匹配基元，以视差连续性约束为松弛迭代准则，通过迭代处理得到视差连续意义下的最佳匹配”3 。k i m 的零交叉匹配，m e d i o n i 的直线段匹配，n a s r a b a d i 的曲线段匹配以及l e e 的分割区域匹配算法中都采用了松弛迭代技术。= ”。”1 。在立体匹配领域，一般是利用匹配连续性约束将匹配视差限制在平滑解空i 目早。在这罩，存在两个需解决的问题，其一是如何有效地保护视差表面的不连续信息，t e r z o p o u l o s 提出了含有不连续信息的通用正则化模型“，通过引入一个可控制平滑度的权函数来保护解的不连续信息，m 此推出下则化| 兀配算法。其二是如何避免出现局部最小的问题，在b a r n a r d 提出的方法中，采用由粗到细的多尺度引导策略和火连理t 大学顾二l 学位论文模拟退火技术来解决这一问题“”。三误差分析3 d 重建方法是多样的，加之所涉及数学工具的五花八门，建立公认的重建理论框架、统一的误差分析模型是很困难的。我们在这里对几种误差模型进行了分析，对3 d 重建误差的进一步研究具有重要意义。1 象素的量化误差传感器数字图像的空间量化效应( e f f e c to fd i g i t i z a t i o n )带来的特征像素定位误差是很重要的。最早对其深入分析的是b l o s t e i n 和h u a n g 等人。w o n g 采用特征函数方法研究误差传播过程。周凌翔也详细研究三维重建误差模型。一般的研究中，把视觉系统的测量值和系统参数看成随机向量，用他们的期望值和协方差来表征特征，采用向量和矩阵代数为数学工具的多元分析是一种常用的方法。假定像点在一个像素面积上是均匀分布，其期望是像素中心，并用正态核心来表示一个象素面积上的位置的不确定性。另一方面，把任意空间点的位置看成服从三维正态分布的随机向量。误差协方差矩阵的一个0 奇异值对应的方向是从原点到目标的视线方向，另外的两个有限值表征了与视线垂直方向的观测误差均方差。误差协方差矩阵的最大特征值表征了物体表面法线方向的误差均方值。基于m a h a l a n o b i s 距离统计最优化意义下获得的测量数据融合和误差演化的计算方法与基于k a l m a n 滤波理论的结果是一致的。郝颖明提出了种在已知模型或信息条件下，即约束条件下的非线性规划模型来减小量化误差。并介绍了改进的约束最小二乘解法。量化误差分析和精度改善的方法有待进步研究“。2 摄像机标定误差早期研究的是线性模型( 针孔模型) 的摄像机标定( c a m e r ac a l i b r a t i o n ) 。当精度要求较高时，线性模型不能准确描述摄像机的成像几何关系。方法简单、成熟，误差较大3 。考虑非线性模型摄像机的标定问题。当普通c c d 摄像机在成像时有较大的成像误差，摄像机标定是确定摄像机的成像参数，并对成像误差进行修正的过程。有效的成像误差修正是摄像机高精度标定的必要环节。造成成像坐标偏差的因素有透镜的径向畸变、切向畸变、偏心畸变等。偏心畸变可以通过使用变焦镜头方法准确估算光心来克服，a t k i s o n 提出的非线性畸变模型中的径向畸变己能足够描述非线性畸变，t s a i 指出由于在考虑非线性畸变时对摄像机标定需要非线性优化，引入过多的非线性参数往往不能提高精度且引起解的不稳定。因此径向畸变是影响精度的主要因素。高立志提出了一种新的径向畸交模型，推出了能精确标定摄像机的线性算法，同时提出了其修正模型，取得了很好的效果n “。以上只介绍了部分内部参数的标定问题，立体视觉标定和自标定等不同数学模型方法有各自的标定误差成因n “】。+3 立体匹配误差出二维图像信息进行3 d 重建的立体视觉方法中，立体匹配是最关键、最困难的问题。关于立体匹配算法和误差分析，国内外学者已做了大量研究，但仍然是比较棘手的问题。被动视觉中图像匹配的方法大致分为两类；基于区域的匹配和基于特征的匹配。前者利用图像局部灰度信息之间的相关性，寻找和计算匹配基元的空间坐标，对细基于双幅图像的匹配算法及3 d 重建不确定性研究节丰富的景物特别有效。缺点是在匹配过程中没有充分利用图像之间的相互约束关系，在处理细节不够丰富的景物时不很成功。且匹配基元的数目多，计算量大。而后者更多地利用图像的结构信息，特征点的数目较前者要少，匹配速度快。特征提取的精度将直接影响后续的重建误差”。文；j 柏高讨论了图像匹配中轴平行、轴相交、轴转动三种摄像机模型和误差。提出各模型中，焦距、基线长、景深等对误匹配的影响“。立体匹配的精度对重建精度的影响较大，匹配技术是3 d 重建中的关键环。4 基础矩阵法重建误差在同一目标的末标定图像中，如果图像点已经匹配，则对极线约束是能得到的唯一信息。而基础矩阵正是描述这一几何关系的，包括摄像机的内、外参数。它是未标定图像间对极几何关系的基础o 。对基础矩阵的估计( f u n d a m e n t a lm a t r i xe s t i m a t i o n ) 己成研究热点，其方法广泛应用在3 d 重建、立体图像匹配、运动摄像机的自标定等方面。l o n g u e t h i g g i n s 首先提出并给出了8 点法，属线性算法，但对噪声敏感，不稳定“。6 a u g e r a s 将投影矩阵简化为两个投影参数的函数，得到了基础矩阵的基本关系式“。h a r t l e y 改进了8 点法，通过在计算前对数据规范化处理( 平移和尺度变换)来降低噪声干扰及非线性的7 点法。l u o n g 提出了利用3 幅未标定图像的6 点法”“。随后涌现出多弛对基础矩阵的估计方法。在估计基础矩阵时，常用的非线性算法有m 一估计法、最小中值法( l m e ds ) ，这些方法的共同点就是将问题归结为无约束优化，然后用非线性最d , - - 乘法( l s 法) 求得最优解，6 点法和双对极约束算法的思路也是如此。胡明星引入了代数余数标准方差的s a m p s o n 加权算予的迭代法，克服了图像噪声点为非高斯白噪声的情况。在双对极约束算法中，目标函数的解析表达式很复杂，计算困难。陈泽志简化双对极约束的表达式，得到简单、有效的求解无约束规划的方法。提出一种鲁棒的基础矩阵估计方法来防止解的多义与退化是很重要的。m i n p r a n 、l m s 、r a n s a c 是三种基本的随机采样方法。其不同与传统的平滑技术，采用较少的样点、重复估计并给定阈值选出最佳。采用代数距离平方和、正交距离平方和、s a m p s o n 距离平方和等方法评估基础矩阵”。5 ，矩阵分解法重建误差利用矩阵分解算法( m a t r i xf a c t o r i z a t i o na 1 9 0 r i t h m )从未标定图像序列进行3 d 重建是由t o m a s i 于1 9 9 2 年首先提出的。近年来，这种方法又推广到了正交投影、弱透视、准透视模型中。这些算法的特点是可以在仿射意义下，将由二维图像点坐标构建的测量矩阵分解为表示摄像机运动和空间物体3 d 几何形状的两个矩阵，再进行欧氏空间的重建。而基于透视摄像机模型的算法中，摄影深度的估计是个很难的问题”。s u n 和r a m e s h 应用矩阵扰动理论和线性模型协方差传播理论对矩阵分解法进行了误差分析。主要的工作是对图像的特征点精度及其小扰动对3 d 重建精度影响的定量分析。s v d 分解法能够得到平方误差全局最小解，两非线性迭代优化法仅能得到局部最小。然而s v d 法要求特征误差的x 、y 方向不相关且同一分布。加权s v d 法在加权平方误差和加权协方差( 马氏距离) 意义下能够解决问题。有的文献以仿射投影来逼近透视投影，给出一个测量矩阵秩为4 的测量指标，人连螋工大学硕j ：学位论文并以最小化此指标为估计摄影深度的标准，采用共轭梯度法来迭代估计摄影深度后，实现摄影重建，再完成欧氏重建。图像特征点匹配、测量矩阵的构建、模型的误差和摄影深度的估计等误差是这种重建精度的影响因素。模型和误差分析方法的改善势必能使这种很新颖的重建方法得到发展。6 深度图误差分析近年来，从图像获取深度信息( d e p t hi n f o r m a t i o n ) 的方法大致有基于特征的( f e a t u r eb a s e d ) 、基于区域的( a r e ab a s e d ) 、基于相位的( p h a s eb a s e d ) 和基于能量( e n e r g yb a s e d ) 等。基于特征的，从提取出的边缘点、角点、直线、曲线等匹配出发获得深度信息。缺点是只能得到局部深度信息。基于区域的，考虑同一区域灰度级相似性。区域倾斜和物体轮廓遮挡很难处理。这种方法没有充分利用边缘信息。基于相位的梯度光流方法利用傅立叶相位信息获得深度。基于能量的方法克服了以上缺点”，能量方程的形式是多样的，但方程中不可能考虑所有因素加之受到光度学条件等的限制，基于能量的方法也有其局限性。7 数学模型误差以仿射投影来逼近透视投影重建方法，局限于正交投影的基于仿射意义的曲线重建方法，选定一误差模型后进行的束调整，矩阵分解法，基础矩阵法等具有各自不同的数学模型误差。国内外文献对重建误差作了部分研究，一般只限于对具体重建方法的讨论。g r o s s m a n n 、z s u n 、l i e b o w i t z 、p p e r o n a 、j w e n g 等人对建立误差分析模型进行了一定的尝试。w e n g 等是最早研究噪声对重建精度影响的。g r o s s m a n n 对比了事先标定与未标定的重建精度。同时推导出能够评定内参数对重建精度影响的几种估计算子的协方差模型。讨论了采用的图像数目、相机方位、相机视线夹角、图像中噪声和点数对精度的影响。指出图像数目小于十时采用事先标定重建效果较好，多幅图像、合理的相机方位能大幅度地改善重建质量。基于统计方法的优化理论实现较困难。z s u n 应用矩阵扰动理论和误差传播的线性模型分析分解法误差。其所作的敏度分析误差来源仅限于图像的小特征匹配误差。误差在测量矩阵分解、仿射重建、欧氏重建中传播。由于仿射重建中的运动和形状矩阵分别由测量矩阵s v d 分解的三个最大特征值和特征向量组成，所以他也采用了矩阵特征问题的扰动理论。重建的不确定显示表现为三维的椭球，六个自由度的三个比例和三个旋转系数由协方差矩阵分解出。对最终重建精度影响的因素是很多的。s v o b a d a 和s t u r m 仅从两幅未标定的图像出发，由其确定的极线几何关系，考虑了匹配噪声和内参数标定误差对摄像机运动参数估计的影响。他们的研究理论基础也没重大突破：应用奇异值分解理论分解本质矩阵得到外参数、用近似的一阶误差模型和协方差理论研究误差传播、向标定好的内参数矩阵加高斯噪声应用统计的方法研究内参数的变化对外参数估计的影响，当然也用到了矩阵特征问题的扰动理论。得出的结论是，：，、u 。的变化对r ，的估计影响较大， 、v o 的变化对f ，的估计影响较大( 、工、v o 、r 。、f 。分别是内外参数) af i o r o u 和m o h r 应用统计的方法研究参数标定误差对重建精度的影响。p e r o n a 等研究了在分解法中特征定位误差对重建精度的影响。o ! a g u e 和m o h r 优化相机布局以提高重建精度，将三维重建点p 写成以内外参数和图像点为参数的函数形式，推出了p 的协方差矩阵并应用在评价准则里。最后采端十双幅幽像的巡利算法擞3 d 重建小确定性蚓f 究用遗传算法的优化过程得到合理的相机布局“。基于图像的三维重建存在重建精度、系统复杂性、数学模型的有效性等问题，三维重建的研究颇赋挑战性，长期以来一直是个热点研究问题。重建误差定量描述的引入是必要的，可对重建方法、采用模型、重建精度等问题进行系统评价。可对重建模型、参数等进行优化，提出更有效的解决问题的途径。建立系统的不确定性分析模型是对基于图像的三维重建的内在规律认识的过程，是计算机视觉中三维重建研究领域所必需的。14 论文的主要研究工作本文围绕计算机视觉中的图像匹配和三维重建误差分析为内容展开探索性研究，在分析当前相关内容研究现状的基础上提出了基于梯度场相似性与邻域膨胀的匹配算法；对影响三维重建精度的误差来源进行了分析，得出了重建不确定性规律。最后，给出了其软件实现和实例分析。论文的结构图如图( 1 ，3 ) 所示。图( 1 3 ) 本文的总体组织结构f i g u r e1 3t h eo r g a n i z a t i o no f t h ep a p e r第1 章绪论，分析了计算机视觉的研究内容及应用，概括了计算机视觉系统与理论，给出计算机视觉相关研究的文献综述，阐述了本文的研究背景和意义，并给出本文的组织结构和内容安排。第2 章相关数学基础及计算机视觉理论，统一介绍矩阵的奇异值分解、矩阵扰动分析、不确定性基础、s u s a n 角点检测、基础矩阵估计、摄像机模型及极线约束等。第3 章基于梯度场相似性和邻域膨胀的匹配算法，简短总结了目前该领域的现状，提出了一种匹配算法并给出算法设计思路和具体实现。第4 章基于双幅图像3 d 重建的不确定性研究，分析了研究意义，推导了重建扰动分析模型，给出了扰动分析过程并讨论了重建不确定性的显示，最终得到若干重要结论。第5 章匹配算法及重建不确定性研究的软件实现，主要是3 、4 两章内容的程序实现及实例分析。第6 章总结与展望，对全文进行总结，并对于下一步的研究工作进行展望。人连理工人学颂l 学位论文第2 章相关数学基础及计算机视觉理论21 引言本章对基于梯度场相似性和邻域膨胀的快速图像匹配算法和3 d 重建不确定性的多元分析统计方法所涉及的主要相关数学基础及计算机视觉理论作一简单的介绍，以便于后续章节的阅读。主要包括：矩阵的奇异值分解( s v d ，s i n g u l a rv a l u ed e c o m p o s il i o n ) 、矩阵扰动分析( p e r t u r b a t i o na n a l y s i s ) 、不确定性基础( u n c e r t a i n t yp o u n d a t i o n ) 、s u s a n 角点检测( s u s a nc