（计算机科学与技术专业论文）基于未标定图像的三维重建技术研究.pdf

摘要 从运动恢复三维形状是计算机视觉领域的中心问题。而非定标图象序列的运 动结构问题是近十年的研究热点。在理论方面，从多视角几何关系、射影重建到 相机自定标技术都得到长足进展。在应用方面，随着计算机及网络技术的飞速发 展，许多应用领域对三维图形数据提出更高的要求。如何尽可能自动地获取复杂、 逼真的三维图形模型是当前的一个前沿课题。本文针对这一课题进行探讨，在一 些非定标图像三维重建的关键算法上提出一些新的改进。其有效性在仿真数据和 真实场景图象序列实验中得到了证明。 首先，在角点检测方面，针对s u s a n 角点算法在实际应用中的不足，提出了 改进的s u s a n 角点算法，使角点均匀的分布在图像上，有利于角点的匹配。 其次，根据基本矩阵的计算往往转化为最优化问题，研究了基于遗传算法的 基本矩阵估计方法，对基本矩阵的鲁棒求解进行了一次有意义的尝试。 最后，通过摄像机白标定，利用矩阵分解的方法和三角形法建立了场景的三 维模型。通过实际图像的仿真实验，表明了本文方法的有效性。 关键词：s u s a n 算法，基本矩阵，摄像机自定标，三维重建 a b s t r a c t t h es t r u c t u r ef r 伽m o t i o n( s f m )p r o b l e mi st h ec e n t r a lp r o b l e mi n c o m p u t e rv i s i o nc 伽n u n i t y t h eu n c a l i b r a t e ds t r u c t u r ef r o mm o t i o np r o b l e m ( u s f m ) i st h eh o tt o p i ci nt h er e c e n tl oy e a r s m a n yt h e o r i e s ，i n c l u d i n g 叫l t i p l e v i e w g e o 嘴t r y ，p r o j e c t i v e r e c o n s t r u c t i o n a n dc 锄e r a s e l f c a li b r a t i o ne t c h a v e b e e np r o p o s e da n d 宵e 11d e v e l o p e d i nt h e a p p l i c a t i o n s ， a st h et e c h n 0 1 0 9 i e so fc o m p u t e ra n di n t e r n e td e v e l o p i n g ， m a n ya p p l i c a t i o n sr e q u i r e3 dg r a p h i cd a t ao fh i g hq u a l i t y o n ec h 8 1 1 e n g i n g p r o b l e mi sh o wt oo b t a i nc o m p l i c a t e da n dr e a l i s t i c3 dg r a p h i cm o d e l sa s a u t o 衄t i c a l l ya sp o s s i b l e t h i st h e s i si sf o c u s e do nt h i sp r o b l e ma n d i m p r o v e ss o m ek e ya l g o r i t h m si nt h eu s f mp r o b l e m t h ee f f e c t i v e n e s so f o u ra l g o r i t h m si se v a l u a t e di nt h ee x p e r i m e n t sw i t hs i 叫l a t e dd a t aa n d r e a li m a g es e q u e n c e s f i r s t l y ，o nt h er e s e a r c ho fi n t e r e s tp o i n td e t e c t i o n ，s i n c e 霄h e nu s e s u s a na l g o r i t | 1 n lt od e t e c tr e a li m g e ，t h en u m b e ro ff e a t u r e si st o o 舢c h ， s ow ep r o p o s eai m p r o v e ds u s a na l g o r i th it od e c r e a s et h en u m b e ro fc o r n e r s a n dt oc o n t r o lt h ed e n s i t yo ff e a t u r e si ht h ei i i l a g e e x p e r i m e n tp r o v e s o u ra l g o r i t h mc a nr e s e r v eg o o df e a t u r e sa n dm a t c ht h 鲫p r o f i t a b l y ： s e c o n d l y ， i nt h ec o m p u t a t i o no ff u n d 硼e n t a l 髓t r i x ，i ta l w a y st u r n s t oo p t i m i z a t i o np r o b l e m a na l g o r i t h mb a s e do ng e n e t i ca l g o r i t h mi s r e s e a r c h e da n dt h ea t t e m p tt og e tr o b u s t s o l u t i o nt of u n d a i n e n t a lm a t r i x m a k e ss e n s e ： f i n a l l y 。 a f t e rd e t e r m i n et h ec a m e r a 8i n t r i n s i cc 8 l i b r a t i o n p a r a i i l e t e r s ae u c l i d e a ns c e n er e c o n s t r u c t i o ni ss e tu pu s i n g 嬲t r i x d e c o m p o s i t i o nm e t h o da n dt r i a n g u l a t i o nm e t h o d i ts h o w se x p e r i m e n t a l r e s u l t st od e m o n s t r a t et h ee f f e c t i v e n e s so ft h ep r o p o s e dm e t h o d s k e y l r o r d s ：s u s a na l g o r i t h m ，f u n d a i i l e n t a lm a t r i x ，s e l f - c a l i b r a t i o n ，3 d r e c o n s t r u c t i o n i i 西北工业大学硕士学位论文 第一章绪论 第一章绪论 1 1 本文的研究背景及意义 随着计算机技术的不断发展和人类对数字化信息的需求不断增加，人们迫切 地希望能突破现有数字计算机的信息处理能力，将其扩展为能处理多维信息的智 能计算机系统。近二三十年以来，科技工作者为实现这个目标进行了不懈和艰苦 的努力，其中大多数人又以计算机视觉作为处理多维信息的突破点。据统计，人 类从外界获取的信息中有7 0 9 6 8 0 是通过眼睛得到的。计算机视觉的研究目的 就是使计算机具有通过二维图像认知三维环境信息的能力，它是一门融合了数字 图像处理、计算机图形学、模式识别、神经生物学等研究成果的学科，基于图像 序列的三维重建正是利用了计算机视觉的一些原理来实现模拟人眼的一些功能 的。 近年来，三维造型技术在机械、电子、建筑、飞机和汽车船舶制造业等各个 领域得到越来越广泛的应用。常规的空间造型采用的方法较为复杂，通常需要先 定义形体，再进行各种几何运算等一系列复杂的步骤，同时需要大量的数据和较 为复杂的结构，适合于结构设计等涉及形体内部结构相互关系的工作。但对于诸 如外观造型设计这种一方面只需要了解形体表面特征，另一方面要求更新速度快 的设计来说，这种普通的造型方法就显得过于繁琐，而且需要存储的数据量也显 得冗余。 基于未标定图像的三维重建技术是近年来计算机视觉技术和计算机图形学 技术相结合而产生的一门新的技术。计算机图形学技术主要包含两个研究方向： 其一是对物体的几何形状和材料建模用于辅助设计和制造：其二是模拟物理世界 的光线传播等现象合成高度真实感的图形或者构造虚拟现实。计算机视觉技术主 要研究如何从已经获得的二维图像中恢复形体的三维几何特征、光照和材料等特 性。基于未标定图像的三维重建技术正是将计算机视觉中的三维重建技术与计算 机图形学中的真实感绘制技术相结合，试图利用二维图像来生成具有真实感的物 体三维表面模型，最终用基于图像的建模方法来代替传统的基于几何特征的建模 方法。由于基于未标定图像的三维重建技术是利用图像序列根据视觉技术获取几 何造型数据，不需要进行复杂的几何建模，因此可以大大减少劳动，同时通过图 像可以获得场景或物体的纹理，减少了对光照等物理特性的设计，这样就降低了 对计算能力的要求。 基于未标定图像的三维重建技术由于具有建模简单、更新速度快等优点，因 西北工业大学硕上学位论文 第一章绪论 此有着广阔的应用范围，包括考古学、建筑学、地质学、虚拟现实、场景漫游、 机器人导航、精密工业测量、物体识别、影视广告、现场勘测以及军事等领域等。 可以预见，随着需求的增多以及技术的进一步完善，基于未标定图像的三维重建 技术必将取得更大的发展。 1 2m a r r 的计算机视觉理论框架 m a r r 的视觉计算理论立足于计算机科学，系统地概括了心理生理学、神经 生理学等方面业已取得的所有重要成果，是视觉研究中迄今为止最为完善的视觉 理论。m a r r 建立的视觉计算理论，使计算机视觉研究有了一个比较明确的体系， 并大大推动了计算机视觉研究的发展。人们普遍认为，计算机视觉这门学科的形 成与m a r r 的视觉理论有着密切的关系。事实上，尽管2 0 世纪7 0 年代初期就有 人使用计算机视觉这个名词，但正是m a r r7 0 年代末建立的视觉理论促使计算机 视觉这一名词的流行。下面简要地介绍m a r r 的视觉理论的基本思想及其理论框 架。 1 2 1 视觉系统研究的三个层次 m a r r 认为，视觉是一个信息处理系统，对此系统研究应分为三个层次：计 算理论层次，表示( r e p r e s e n t a t i o n ) 与算法层次，硬件实现层次，如表卜1 所示。 表卜1 计算理论表示和算法硬件实现 计算的目的是什么?如何实现这个计算理论?在物理上如何实现 为什么这一计算是合适的? 输入、输出的表示是什么?这些表示和算法? 执行计算的策略是什么? 表示与表示之间的变换是什么? 按照m a r r 的理论，计算视觉理论要回答视觉系统的计算目的和策略是什么， 或视觉系统的输入和输出是什么，如何由系统的输入求出系统的输出。在这个层 次上，信息系统的特征是将一种信息( 输入) 映射为另一种信息( 输出) 。比如，系 统输入是二维灰度图像，输出则是三维物体的形状、位置和姿态，视觉系统的任 务就是如何建立输入输出之间的关系和约束，如何由二维灰度图像恢复物体的三 维信息。表示与算法层次是要进一步回答如何表示输入和输出信息，如何实现计 2 西北工业大学硕士学位论文第一章绪论 算理论所对应的功能的算法，以及如何由一种表示变换成另一种表示，比如创建 数据结构和符号。一般来说，不同的输入、输出和计算理论，对应不同的表示， 而同一种输入、输出或计算理论可能对应若干种表示。在解决了理论问题和表示 问题后，最后一个层次是解决用硬件实现上述表示和算法的问题，比如计算机体 系结构及具体的计算装置及其细节。从信息处理的观点来看，至关重要的乃是最 高层次，即计算理论层次。这是因为构成知觉的计算本质，取决于解决计算问题 本身，而不取决于用来解决计算问题的特殊硬件。换句话说，通过正确理解待解 决问题的本质，将有助于理解并创造算法。如果考虑解决问题的机制和物理实 现，则对理解算法往往无济于事。 上述三个层次之间存在着逻辑的因果关系，但它们之间的联系不是十分紧 密，因此，某些现象只能在其中一个或两个层次上进行解释。比如神经解剖学原 则上与第三层次即物理实现联系在一起。突触机制、动作电位、抑制性相互作用 都在第三个层次上。心理物理学与第二层次( 即表示与算法) 有着更直接的联系。 更一般地说，不同的现象必须在不同的层次上进行解释，这会有助于人们把握正 确的研究方向。例如，人们常说，人脑完全不同于计算机，因为前者是并行加工 的，后者是串行的。对于这个问题，应该这样回答：并行加工和串行加工是在算 法这个层次上的区别，而不是根本性的区别，因为任何一个并行的计算程序都可 以写成串行的程序。因此，这种并行与串行的区别并不支持这种观点，即人脑的 运行与计算机的运算是不同的，因而人脑所完成的任务是不可能通过编制程序用 计算机来完成。 1 2 2 视觉表示的三个阶段 视觉过程划分为三个阶段，如表卜2 所示。第一阶段( 也称为早期阶段) 是将 输入的原始图像进行处理，抽取图像中诸如角点、边缘、纹理、线条、边界等基 本特征，这些特征的集合称为基元图( ”i m i t i v es k e t c h ) ；第二阶段( 中期阶段) 是指在以观测者为中心的坐标系中，由输入图像和基元图恢复场景可见部分的深 度、法线方向、轮廓等，这些信息的包含了深度信息，但不是真正的物体三维表 示，因此，称为二维半图( 2 5d i m e n s i o n a ls k e t c h ) ；在以物体为中心的坐标系 中，由输入图像、基元图、二维半图来恢复、表示和识别三维物体的过程称为视 觉的第三阶段( 后期阶段) 。 3 西北工业大学硕士学位论文 第章绪论 表卜2 由图像恢复形状信息的表示框架 名称目的 基元 图像光强表示图像中每一点的强度值 表示二维图像中的重要信零交叉，斑点，端点和不连续 息，主要是图像中的强度变点，边缘片断，有效线段，组 基元图 化位置及其几何分布和组织合群，曲线组织，边界 结构 在以观测者为中心的坐标系局部表面朝向( “针”基元) 中，表示可见表面的方向、离观测者的距离 2 5 维图 深度值和不连续的轮廓深度上的不连续点 表面朝向的不连续点 在以物体为中心的坐标系分层次组成若干三维模型，每 3 维模型表 中，用由体积基元和面积基个三维模型都是在几个轴线 元构成的模块化多层次表空间的基础上构成的，所有体 不 示，描述形状及其空间组织积基元或面积形状基元都附 形式。着在轴线上。 m a r r 理论是计算机视觉研究领域的划时代成就，但该理论不是十分完善的， 许多方面还有争议。比如，该理论所建立的视觉处理框架基本上是自下而上， 没有反馈。还有，该理论没有足够地重视知识的应用。尽管如此，m a r r 理论给 了我们研究计算机视觉许多珍贵的哲学思想和研究方法，同时也给计算机视觉研 究领域创造了许多研究起点。 1 3 国内外研究现状 基于未标定图像的三维重建技术主要是分匹配、摄像机标定和三维重建三个 部分进行研究。三维重建的先决条件是要解决两幅图像间的对应关系即匹配。匹 配包括两个子问题：特征检测和特征匹配。常用的匹配特征有特征点、特征线、 特征区域，其中以点特征研究较多。d r e s c h l e r 和n a g e l 等 4 提出了基于 g a u s s i a n 曲率原则的检测方法。k i t c h e n 和r o s e n f e l d 1 6 提出的角点检测器利 用了灰度沿边界轮廓梯度方向变化最大的性质。n o b e l 2 1 试图用微分几何给出 角点检测的理论公式。m o r a v e c 2 0 于1 9 7 7 年首次提出了用“兴趣算子”提取 角点的方法。1 9 8 8 年h a r r i s 和s t e p h e n s 7 对m o r a v e c 算子进行了改进，提出 了p 1 e s s e y 算子。s m i t h 2 9 提出了著名的s u s a n 角点检测算子，该方法对像素 周围区域最小化，用统计特性来决定该像素的属性，即角点、边上的点还是圆上 的点。 特征匹配往往以灰度相似性为基础，辅以对极几何约束或其它约束进行搜 索。b e a r d s l e y 等 1 提取角点作为特征点，运用相关性进行匹配，将匹配的结 4 西北工业大学硕士学位论文 第一章绪论 果用奇异值分解求取了基础矩阵。p r i t c h e t t 和z i s s e r 衄n 等 2 7 提出了用单应 矩阵( h o m o g r a p h y ) 取代传统的灰度相似性和极线约束作为匹配的准则，他们近似 认为特征点及其周围小块区域是空间中平面的成像，因此匹配点对之间应近似满 足单应矩阵的关系。另外，他们试图寻找一种整体相似变换，以使两幅图像在相 差一个常数因子的情况下具有最大相关性，根据整体变换，估计图像间局部区域 的仿射变换，用局部变换来寻找匹配点。p r i t c h e t t 等的方法对于某些含有丰富 平面信息的图像特别有效。l h u i l l i e r 和l u o n g 等 1 7 提出了一种稠密匹配的新 策略，该策略综合了以对极几何约束为代表的全局约束和以灰度相似、单应矩阵 为代表的局部约束，在每次匹配过程中，选取当前灰度相似性最大的匹配对，在 它的周围小区域内寻找更多的匹配对，重复这种过程直至匹配对充满整幅图像， 最后再应用对极几何约束去除错误匹配。该方法对于纹理稠密的图像特别有效， 缺陷是精度不高。m p i l u 2 2 提出了一种基于奇异值分解的匹配方法，首先构 造一个包含特征点的g a u s s i a n - w e i g h t e d 距离信息的强度矩阵g 并对其进行奇异 值分解，接着将得到的对角矩阵的对角元素全部替换为1 而得到一个同维矩阵p ， 通过矩阵p 中各个元素的值就能判断出对应的特征点是否匹配。由于整个计算过 程中全部是代数意义下的运算，所以匹配的精度有待进一步提高。 要实现欧氏空间下的三维重建，必须确定摄像机的参数即进行标定。微软研 究院的张正友 3 8 提出了一种利用平面模板的标定方法，该方法只需从不同角度 对模板拍摄几幅图像，通过每幅图像的单应矩阵即可计算出摄像机内参数，缺点 是每次都需要标定，且都需要标定物。近年来，无需标定物、基于图像序列的自 标定方法己成为标定研究的一个重要方向。f a u g e r a s ，l u o n g 和m a y b a n k 等 5 ， 1 9 首先提出了自标定的概念，从射影几何的角度出发证明了每两幅图像间存在 着两个形如k r u p p a 方程的二次约束，通过直接求解i ( r u p p a 方程组可以解出内参 数，但是i ( r u p p a 方程只能表示图像两两之间的关系，不能将整个图像序列相联 系，且求解困难。鉴于直接求解k r u p p a 方程的困难，研究者们又提出了分层逐 步标定的思想，即首先对图像序列做射影重建，在此基础上再进行仿射标定和欧 氏标定，该类方法以h a r t l e y 的q r 分解法 1 0 、t r i g g s 的绝对二次曲面法 3 6 ， p o l l e f e y s 的模约束法 2 5 等为代表，这些方法的本质都是求解无穷远平面的绝 对二次曲线或曲面，缺点是都对输入的数据有很高的精度要求。自标定方法不能 使用解析式表达，需要使用非线性优化，非线性优化带来的计算难度误差不可避 免。 西北工业大学硕士学位论文 第一章绪论 1 4 本文的研究内容 本文需要解决的具体问题是：在一个静态刚体场景中，使用一个未标定的摄 像机，假定摄像机内参数在拍摄过程中不发生变化，在场景的不同位置拍摄，得 到场景的序列图像；以场景的二维序列图像作为输入，通过计算，恢复出摄像机 的运动参数( m o t i o n ) 和场景的三维形状信息( s t r u c t u r e ) 。摄像机运动参数包 括平移矢量和旋转矩阵。场景的三维形状信息用几百个稀疏的空间点表示。 本文选择点作为场景恢复的基元，原因是点比较通用，任何场景都可以用点 来表示。直线，线段和二次曲线多存在于人工的场景中，应用受到了限制。 本文针对所提出的问题，研究的算法包括： 在提取特征点方面，总结了现有的角点检测算子，分析了不同方法的优缺点， 在此基础上提出了改进的s u s a n 算子。 在匹配方面，研究了结合相关技术和约束的方法。这里使用了极线约束，把 匹配过程的二维搜索范围减小为一维搜索范围。 在基本矩阵估计方面，论述和分类总结了基本矩阵估计的基本原理和方法， 研究了用遗传算法来计算基本矩阵。 在摄像机自标定方面，介绍了摄像机内参数固定情况下的摄像机自标定。实 现了摄像机内参数不变的标定方法。 在欧氏重建方面，研究了对本质矩阵分解的方法来估计运动参数，使用三角 形法来恢复场景点的位置。 本文共分六章，章节安排和主要内容如下： 第一章绪论。本章主要介绍了m a r r 的计算机视觉计算理论，国内外研究现 状，本文的研究背景、意义和主要内容。 第二章计算机视觉算法基础。本章主要介绍了射影几何，透视投影摄像机 模型，透视投影的各种线性近似，为介绍后面的内容打下基础。 第三章角点检测和匹配。本章的第一部分是提取特征点，提出了对s u s a n 算法的改进，第二部分是匹配特征点，介绍了本文采用的匹配策略。 第四章基本矩阵和射影重建。本章首先概述了估计基本矩阵的算法，并研 究了用遗传算法来计算基本矩阵。最后用基本矩阵进行了射影重建。 第五章摄像机标定和三维重建。本章首先介绍了几种摄像机自标定算法， 然后介绍了利用s f m 算法求取空间点坐标的计算过程。 第六章总结和展望。本章总结了全文的研究工作，并对系统的进一步完善 和未来的研究方向进行了探讨。 6 西北工业大学硕士学位论文 第二章计算机视觉算法基础 第二章计算机视觉算法基础 摄像机模拟人类视觉系统将三维场景投影到二维图像上，这一过程可以用摄 影几何来描述。因此本章介绍计算机视觉的常用概念，为后面各章奠定理论基础。 并且在这一章统一各种符号说明公式。本章内容包括射影几何，摄像机模型和四 种坐标系。 2 1 射影几何基础 从运动恢复三维形状是计算机视觉研究的子领域。计算机视觉的主要研究对 象是距离和运动。不难理解视觉计算理论的基础涉及几何学。平面解析几何和立 体解析几何是大家所熟知的。但是在计算视觉中，接触更多的是射影几何学，而 不仅仅是平面和立体几何学。这是因为三维景物不是水平的投影到视网膜上，而 是经过晶状体投射到视网膜上。因此，需要借助于射影几何来研究投影等性质。 点： 一 一个n 维射影空间中的点，用一个n + 1 维的矢量来表示，j2 【而，x 2 ”毛+ 】j ， 其中，至少有一个坐标不为零。这种表示方法是齐次坐标。如果点x 和点y 的每 一个子坐标，都满足x ，= 砂；( 1 f 打+ 1 ) ，则点x 和点y 相等。可以记做工 y 。无限远处的点可以表示为z 。+ = 0 。 平面： 射影空间中的平面是二维射影空间。一个二维射影空间中的点可以记为 m = x ，y ，z 】7 。同样，直线也使用三个坐标来表示。一个点m 在直线1 上，当且 仅当： ，所= o 。 ( 2 1 ) 这个方程也可以被解释为直线l 在点m 上。这种表示的对称性，说明了在二 维射影空间中，点和直线没有表示的差异，称为对偶性。一条经过点和m ：的 直线1 可以由确肼：得到。也可以被记作： ，=所。朋：=r埘。，。坍：，其中c埘。，。=_： 7 mj ，1 1 o 而i ( 2 2 一_ oj 西北工业大学硕士学位论文第二章计算机视觉算法摹础 两条直线的交点由公式( 2 1 ) 的对偶形式定。通过一个特定点的所有直线 被称为线束。如果，t 和，z 是一个线束1 中的不同的直线，则线束1 可以表示为： ， + 五，2 ( 2 3 ) 其中，只有粤的比值起作用。 如 三维空间： 一个三维射影空间中的点可以被表示为膨= 【x ，y ，z ，矿】7 。在三维射影空间 中，点的对偶实体是平面，和点的表示形式一样。一个点m 位于平面n 上，当且 仅当： 7 肘= 0 ( 2 4 ) 直线可以看作是两个点的线性组合 m 。+ 如且如，还可以表示为两个平面的 交集n ，n 2 。 变换： 二维平面上的变换可以由一个3 3 的矩阵h 表示，h 和舾表示相同的变换。 点和直线的变换公式分别为： 埘砀”( 2 5 ) l 日一7 ，( 2 6 ) 同样的，也存在三维射影空间中的变换，可以用一个4 4 的矩阵t 表示。 点式和平面的变换公式分别为： ，刀m( 2 7 ) 丁一7 兀( 2 8 ) 二次曲线： 二维射影空间中的二次曲线被定义为满足以下二次方程的点m 的集合： s ( m ) = m 2 渤= o ( 2 9 ) c 是一个3 3 的对称矩阵，二次曲线由5 个参数决定。 对偶二次曲线： 为二次曲线的对偶实体，被定义为满足以下二次方程的所有曲线，的集合。 c = c 一1 ，7 c ，= o ( 2 1 0 ) c 是3 3 的对称矩阵，因此对偶二次曲线也由五个参数决定 c = c 。 ( 2 1 1 ) 8 西北工业大学硕士学位论文第二章计算机视觉算法摹础 直线与二次曲线的交点： 令两个点m 与埘。定义一条直线，则在直线上的点可以被表示为埘+ 旯坍，点 在二次曲线s 上当且仅当s ( 朋+ 五肌= 0 也可以写作 s ( 脚) + 2 五s ( m ，所+ 旯2 s ( 埘= o ( 2 1 2 ) 其中 s ( 所，历= 舻c 锄= s 沏：功 这表示通常一条直线与二次曲线有两个交点，包括实数点和复数点，可以通 过解式( 2 1 2 ) 求解。 二次曲线的切点： 当式( 2 1 2 ) 的判别式为零时，直线与二次曲线的两个交点重合，可以写为： s ( 肼，肌一s ( 历) 文州 = o 如果点埘被认为是不变的，这形成了关于肌的二次方程，表示从脚到二次 曲线的两个切线。如果珊属于二次曲线，则s ( 小) 2 0 切线方程变为 s ( 朋，脚2 m 7 c 坍一o ，坍。的系数是线性的，这表示对于二次曲线的一点只有一 条切线。切线，可以被表示为 ，c 7 埘= c 胁 ( 2 1 3 ) 二次曲线和对偶二次曲线的关系： 当点m 沿着二次曲线变化时，它满足脚1 ( 轫并且点所处的二次曲线的切线， 满足，c 1 ，= o 。这表示二次曲线c 的切线属于对偶二次曲线c + c - 1 ( 假设c 满 秩的) 二次曲线和对偶二次曲线的变换： 由公式( 2 6 ) 和( 2 7 ) 可以得到： 埘“c 聊埘7 日7 日一7 c 日一1 肠打：o ，。c ? ，7 胃一1 日c 日7 目一7 ，= o 所以 c 日。c 日“ ( 2 1 4 ) c ”脚 ( 2 一】5 ) 观察( 2 1 4 ) 与( 2 1 5 ) 可以得到( c ) = ( c ) 二次曲面： 三维射影空间中的二次曲面被定义为满足以下二次方程的点m 的集合： m 1 叫= o ( 2 1 6 ) 9 西北工业大学硕士学位论文 第二章计算机视觉算法皋础 q 是一个4 4 的对称矩阵，因此曲面由有9 个参数决定。 对偶二次曲面： 定义为满足以下二次方程的所有平面n 的集合 n 7 q n = o ( 2 1 7 ) q 是4 4 的对称矩阵，因此对偶二次曲面也由有9 个参数决定。 二次曲面的切面： 当切点m 沿着二次曲面变化时，切点m 的切面沿着对偶二次曲面变化， 类似公式( 2 一1 3 ) ，二次曲面的切面方程为 n 。叫 ( 2 1 8 ) 二次曲面与对偶二次曲面的关系： 当点m 沿着二次曲面变化时，它满足m 1 q 膨并且点m 处的切面满足 2 q 。1 2 0 。这表示二次曲面q 的切面属于对偶二次曲面 矿q ( 假定q 是满秩的) 。 二次曲面与对偶二次曲面的变换： 由公式( 2 8 ) 与( 2 9 ) 得到： m “q 。m m 7 丁7 r 4 q r 一1 n ，= o 。q n n 7 r - 1 z q r 7 r 一7 = o 所以 q r q 一 ( 2 1 9 ) q 彤， ( 2 2 0 ) 观察得( q ) = ( q + ) 2 2 摄像机模型 摄像机坐标系： 摄像机成像几何关系可由图2 1 表示，其中c 点称为摄像机的光心，x 轴和 y 轴分别与图像的x 轴和y 轴平行，z 轴为摄像机的光轴，它与图像面垂直。光 轴与图像平面的交点为成像平面坐标系的原点。由点c 与x ，y ，z 轴组成的直角 坐标系称为摄像机坐标系。c p 为摄像机焦距。 i o 西北工业大学硕士学位论文第二章计算机视觉算法基础 图2 1 摄像机坐标系 摄像机坐标系和成像平面坐标系之间存在一个线性变换： x y z l ( 2 2 1 ) 世界坐标系 由于摄像机可安放在环境中的任何位置，可以选择一个基准坐标系来描述摄 像机的位置，并用它描述环境中任何物体的位置，称为世界坐标系。摄像机坐标 系和世界坐标系之间的关系可以用旋转矩阵r 与平移矢量t 来描述。 摄像机内部参数 在摄像机成像过程中，图像坐标和成像面的实际物理坐标是不一致的。这两 个坐标之间的关系取决于摄像机象素的大小和形状以及摄像机内c c d 芯片所处 的相对位置。考虑的因素有： 1 图像坐标系的原点不一定与光轴和图像平面的交点( 即主点) 重合； 2 图像坐标系中两坐标轴的单位由实际设备的采样率决定，它们不一定相同； 3 图像坐标系中两坐标轴不一定成直角； o ，o 厂o o -。l ，一z = 1，j x y l 。l 西北工业大学硕士学位论文第二章计算机视觉算法基础 图2 2 摄像机的内参数，图像平面上的坐标变换 如果考虑以上因素的影响，得到了一个矩阵a ： 舯 i = 其中， u ，v ，1 是图像坐标系中的点的齐次坐标， x ，y ，1 是成像面坐标系中 点的齐次坐标。 因为a 矩阵中所有的参数只和摄像机的内部参数有关，同时，透视投影模型 ( 2 2 1 ) 中，也有摄像机的内部参数焦距的影响，可以把所有的摄像机内参数放 到一起考虑。得到了一个矩阵k ，这样，考虑摄像机外部参数时( 摄像机的位置 和方向) ，就可以不用理会摄像机的类型( 由摄像机内参数决定) 。 摄像机的内参数矩阵k ： 舯 i = px o 0 ( 2 2 2 ) f 是焦距，以和p ，分别是象素的宽度和高度，口是摄像机象素的倾斜角， 。2 【。，。，1 】是主点。这里， u ，v ，1 是图像坐标系中的点的齐次坐标，而 x ，y ，1 是归一化后成像面坐标系中点的齐次坐标，注意这里采用的标记方法和成像面坐 标系相同，但归一化的坐标考虑了焦距的影响。以后，如果不做特殊说明，本文 采用 x ，y ，1 表示归一化后的成像面坐标。 1 2 q q o上以。 l 儿o o c c 1 厂一岛 计上如o n魄 西北工业大学硕士学位论文 第二章计算机视觉算法基础 i = 。l 乏： i c z z s ， 部分c m o s 和c c d 摄像机满足这个条件) ，则s = o 。如果象素为正方形，则_ ，= _ ，。 【o olj o oo it loo 怍 o1o 怦 o ll ( 2 2 4 ) 可见，对于归一化的图像坐标而言，透视投影的摄像机焦距为1 。在许多文 献的公式中，假设焦距为1 ，其推导过程中使用的都是归一化的图像坐标。在已 知摄像机内参数的情况下，可以利用公式( 2 2 3 ) ，将归一化的图像坐标转换成 实际的 公式( 2 2 4 ) 是考虑了摄像机内部参数情况下的透视投影方程。 摄像枧内参数的获得可以通过察看摄像机生产厂商的说明书，标定或自标定 而获得。本文在摄像机自标定一章来讨论如何获得摄像机内参数。 摄像机外部参数 公式( 2 2 3 ) 和公式( 2 2 4 ) 说明了图像坐标和摄像机坐标之间的关系，即 在摄像机坐标系的一个空间点m 如何被透视投影模型投影到图像的一个象素上。 如果采用世界坐标系来描述空间点m ，可以得到以下关系： m ：= x c e z 。 1 ix 。 rf fl 2 1 0 71 j k il = 列m 。 ( 2 2 5 ) 1 o 0 。l = 1j x y 1 。l 乙 西北工业大学硕士学位论文 第二章计算机视觉算法基础 公式描述了世界坐标系和摄像机坐标系之家的关系。其中r 是一个3 x 3 的正 交矩阵，描述了欧式空间中的旋转变换，t 是一个平移矢量，描述了两个坐标系 原点之间的位移。这个公式的几何意义是：先在世界坐标系下做一个r 描述的旋 转变换，然后再做一个t 描述的平移变换，即可以得到摄像机坐标系。 r 和t 被称为摄像机的外参数。r 矩阵为3 3 ，9 个参数，但是只有3 个自 由度，t 是一个3 1 的矢量，3 个自由度。 通过公式( 2 2 2 ) ，( 2 2 4 ) 和公式( 2 2 5 ) ，得到了使用世界坐标系描述的 空间点m 和图像象素坐标系的投影关系： 獬潍譬 = 哞嗨括鼢 ( 2 2 6 ) 蝎完全有以，q ，q 和c ，决定，由于以，q ，c ，和勺只与摄像机内部结 构有关，称这些参数为摄像机内参数；m ，完全由摄像机相对于世界坐标系的方 位决定，称为摄像机外部参数，确定某一个摄像机的内外部参数，成为摄像机定 标。 p 矩阵完全表述了一般情况下的透视投影关系，p 矩阵被称为摄像机投影矩 阵。 2 3 四种坐标系 射影坐标系： 三维空间的射影变换可被表示为4 4 的不可逆矩阵 r p a 1a 2 仍i 见2 p 3 1 胁2 鼽l 风2 a ，p 1 4 p 竹p h p 拈p m p op 有1 5 个自由度。 入射，共线性和相切的关系是射影几何的不变量。 交比也是射影几何的不变量，定义为：m = m + 丑m t m ，鸩；鸩，= 砉：砉 一九 一九 仿射坐标系： 仿射几何通过定义一个无穷远的平面不同于射影几何， w = o ，死= 【o ，o ，o ，1 r 1 4 ( 2 2 7 ) ( 2 2 8 ) 这个面通常定义为： ，陟m m 一 一 g 5 o ，一易o 一一旧 一 rilijll【 m hn叫l 堕! ! 三些盔兰堡主兰丝堡壅j e 童生生竺垫塑兰兰望! i 堕 射影空间可以通过映射包含仿射空间。斗p 3 ：【岛_ ) ，z 】r _ ，y ，z ，1 1 这是1 对1 的映射。严格的说，这个面( w = o ) 不是仿射空间的一部分。 仿射变换通常表示如下： 撒心矿妒。 丁，f ：乏：i r ，la 2 1 锄吒4l 。i 吗l 锄码4l lo o ol j 有1 2 个自由度。 ( 2 2 9 ) 仿射变换的一个新的性质是平行性，线或面的交点如果在无穷远的平面上称 为平行。另一个性质是在一个特定方向上的长度比例，它与交比类似( 一个点在 即睢抖豳 防 正交矩阵的系数_ 有6 个限制善帆一( 1 螂月，3 ) 磊2 1当f = j 时 毛2 0 当f ，时 且7 r = r 月7 = ，。所以r 一1 = 足7 当且仅当职7 = ，并且( 1 e t r = 1 时，r 是旋转矩阵。 通常，正交矩阵只有3 个自由度。 盯 d r 2 3f y 仃乞 0l 有7 个自由度，3 个方向，3 个位移和1 个比例。 这样，就有两个新的不变量：相对长度和角度一 ( 2 3 1 ) q 吒q ，。一 i i 1j，。l 为 写改被以可 西北丁业大学硕士学位论文第二章计算机视觉算法基础 同仿射情况相类似，m e t r i c 几何也提出了几何不变量，绝对二次曲线 q ：x 2 + 】，2 + z 2 = 0 ，并且肜= o 。 对偶绝对二次曲面 l o o o o j io o1 0l 盯j o 1oo l0ooi 欧式坐标系： 毛艟 ( 2 3 2 ) ( 2 3 3 ) 吒2，i 3l 吒2 仫0 2 屯i oolj 有6 个自由度，3 个方向，3 个变换( 2 3 4 ) 下面分别用表格来总结四种坐标系 表2 1 四种坐标系 自由度 变换不变量 p l la 2 a 3 a 4 见l 易2 仍3p 2 4 p r o j e c t i v e 1 5 乙 交比 p np np ”p p n p n p ”p 一 q 1q 2q 3q 4 吒i 啦2 哆3 仿比 缅n e1 2 死一平行 锄锄 无穷远平面 oo0l 盯吒l盯2盯吒3 盯吒lc 7 吃2c 7 眨3 相对距离 m e m c7 角度 o 码l盯吩2盯吩3 乞 绝对二次曲线 o0ol 吒i瞄2吒3 吒1吒2吒3f ， e u c l i d e 锄6 五绝对距离 弓i ，缸吩3乞 ooo1 1 6 西北工业大学硕上学位论文第二章计算机视觉算法基础 2 4 小结 本章介绍了计算机视觉理论的基础计算知识，为以后章节的讨论作了一个铺 垫。几何学分层次，由一般到特殊分别是射影几何，仿射几何，近似的欧式几何， 欧式几何。本文介绍了射影几何中几何元素的表示和性质，是因为透视投影的实 质是一个射影变换，只有交比这个几何量保持不变。这些表示法和性质在投影重 建，自标定等领域得到了广泛的使用。透视投影是实际摄像机的线性模型，如果 使用了广角镜头，需要讨论非线性畸变。如果把透视投影的矩阵由射影变换调整 到仿射变换，可以得到对图像坐标和世界坐标系非齐次坐标变换的线性投影模 型。这些模型简化了投影关系，由于仿射摄像机可以有更多的几何不变量如简比、 平行性，在一定的应用条件下，满足了仿射摄像机要求的近似条件，同时，应用 只需要仿射不变量就可以得到解决。所以，这些简化模型也得到了广泛的应用。 1 7 西北工业大学硕士学位论文 第三章角点检测和匹配 第三章角点检测和匹配 特征的提取和匹配是三维重建过程中最为关键的一步，它的精度与重建场景 的准确性密切相关。特征的提取需要解决三个问题，即提取什么样的特征，按照 什么规则对特征进行提取和怎样提取特征。特征匹配则是建立三维空间中同一基 元在不同图像中的对应关系。经过特征的提取与匹配，就可由空间几何关系获取 三维信息，重建初始模型。目前，图像匹配经常用到的特征有特征点、边缘和区 域等。本文采用特征点作为匹配对象。 3 1 角点的检测 到目前为止，在计算机视觉和图像处理领域中关于角点还没有很好的数学定 义，存在多种数学描述方法，因而在相关文献中涌现出很多角点检测方法。一般 来说，角点定义为图像中周围亮度变化剧烈的点或者图像边界曲线上具有足够大 曲率的点。由于其信息含量高且相对于图像像素总数的数量较少，角点检测在许 多计算机视觉问题中如目标识别，图像匹配，图像融合，光流计算和三维重建等 领域具有重要意义。 3 1 1 角点检测算法概述 对于角点检测，目前主要分为两类方法：基于图像边缘的方法和基于图像灰 度的方法。基于图像边缘的方法往往需要对图像边缘进行编码，这在很大程度上 依赖于图像的分割和边缘提取，而这两种操作本身就具有相当大的难度和计算 量，况且一旦待检测目标局部发生变化( 例如被部分遮挡) ，则很可能导致图像分 割和边缘提取操作的失败，所以这种方法的适用范围很小。而基于图像灰度的方 法则避开了上述这些缺陷，它考虑的是像素点邻域的灰度变化，而不是整个目标 的边缘轮廓。这类方法主要通过计算点的曲率及梯度来检测角点，目前此类方法 已经取得了很大的进展，出现了各种各样的角点检测算子，下面将这些算子分为 基于图像导数的方法和基于图像灰度对比关系的方法作以介绍。 ( 一) 基于图像导数的方法 1 9 西北工业大学硕t 学位论文第三章角点检测和匹配 m o m v e c 算子： m o r a v e c 2 0 于1 9 7 7 年首次提出了用“兴趣算子”提取角点的方法。该算子 计算各像素沿不同方向的平均灰度变化，选取最小值作为对应像素点的角点响应 函数c r f ( c o r n e rr e s p o n s ef u n c t i o n ) 。定义在一定范围内具有最大角点响应的 像素为角点。具体实现为：确定图像中的一个局部窗口，通过窗口在图像中的移 动，确定各个方向的均方误差和。在移动的过程中，需要考虑如下三种情况： ( 1 ) 假如窗口内的图像块的亮度值是恒定的，那么所有不同方向的偏移仅 导致一个小的变化。 ( 2 ) 假如窗口跨越一条边，那么沿着边的偏移将导致一个较小的变化，但 是与边垂直的偏移将导致一个较大的变化。 ( 3 ) 假如窗口块包含角点或者是一个孤立的点，那么所有不同方向的偏移 将导致一个较大的变化。因此角点被检测出来。 m o r a v e c 角点检测算子可以简单描述为：在角点的某个领域内，亮度的变化 在任意一条通过该点的直线上都很大。对每一个待检测的象素点取窗口，从各个 方向来计算这个象素的非正则化自相关值，并且选择最小值