第一章 绪 论
人类感知外界环境信息主要是通过视觉来实现的，使计算机或机器人具有类似于人类的视觉功能，是人类长期的梦想。随着计算机技术和信号处理理论的发展，人们开始尝试利用摄像机拍摄环境图像并将其存储到计算机中，然后让计算机完成视觉信息处理的全过程，由此就产生了一门新兴的学科——计算机视觉。
计算机视觉是一门综合性学科，它的研究涉及到图像处理与图像理解、模式识别、计算机图形学、信号处理、数学以及生物物理学等。计算机视觉的研究目标是使计算机具有通过二维图像（视图）认知三维环境信息的能力。这种能力将不仅使计算机能感知三维环境中的几何信息（包括它的形状、位置、姿态、运动等），而且能对它们进行描述、存储、识别与理解。概括起来，计算机视觉要达到的基本目的有以下几个：
①根据一幅或多幅二维图像计算观察点到目标物体的距离； ②根据一幅或多幅二维图像计算目标物体的运动参数； ③根据一幅或多幅二维图像计算目标物体的表面特性； ④根据多幅二维图像恢复出更大空间区域的投影图像。
显然，计算机视觉的问题是一个逆问题（inverse problem），输入的图像为二维图像的灰度，它是三维物体几何特征、光照、物体材料表面性质、物体的颜色、摄像机参数等许多因素的函数，由灰度反推（估计）以上各种参数是十分困难的逆问题。这些问题往往是非线性的，问题的解不具有唯一性，而且对噪声、离散化引起的误差甚至对初始值的选择极其敏感。目前的计算机视觉方法一般都没有完美地解决视觉信息处理中的问题，它们都或多或少地存在一些不足，需要进一步地深入研究。
从计算机视觉理论的发展历史来看，主要分为两个阶段。第一个阶段是MIT的D.Marr在八十年代初提出的视觉系统框架。该视觉系统框架是Marr从信息处理的角度，综合了图像处理、心理物理学、神经生理学及临床精神病学等的研究成果提出的第一个较为完善的理论框架，它大大地促进了计算机视觉这门学科的形成与发展。第二阶段是近十年来发展起来的所谓几何计算机视觉，它把复杂的数学（尤其是射影几何等）引入到计算机视觉的研究中，形成了所谓的“多视图几何”。多视图几何为理解和形式化多视图成像几何奠定了坚实的理论基础，使得十几年前被认为无法解或难以解的问题得以求解，甚至能得到十分漂亮的结果。多视图几何最重要的特点是“未标定”方法，即没有必要已知或必须计算摄像机内参数，就
[4]
[3]
[1]
[2]
1
可以达到计算机视觉的基本目的。多视图几何的出现使计算机视觉的研究进入了新的热潮，本章1.1节将给出其中若干热点问题。
1.1 目前计算机视觉研究的若干热点问题 （1）三维重构
在计算机视觉领域中，所谓三维重构是指由多幅（至少两幅）图像获取空间物体的三维几何信息。在传统的计算机视觉技术中，至少需要两台摄像机来观察物体，摄像机的内参数是已知的并且摄像机之间的相互位置也是已知的，换言之，整个视觉装置是已标定（校准）的。研究表明这种情况下可以实现三维重构（欧氏重构）。
问题：在视觉系统未标定的情况下，能否实现三维重构，以及如何实现三维重构，这是近年来计算机视觉领域研究的热点问题之一。 （2）摄像机自标定
摄像机标定是完成欧氏重构和运动分析必不可少的关键一步，即在摄像机未标定的情况下，我们只能实现射影重构
[6][7]
[5]
。传统的摄像机标定方法都需要在摄像机前放一个已知形状和
尺寸的物体，称为标定物或标定参照物（reference object），摄像机获取该物体的图像，并由此计算摄像机的内参数。
问题：能否实现摄像机自标定（self-calibration）？也就是能否直接从场景图像求解摄像机内参数？这是近年来计算机视觉领域中非常热门的问题。因为这一问题的解决，我们就可以从未标定图像实现三维欧氏重构和运动分析。 （3）运动分析和PNP问题
在计算机视觉和机器人领域中，运动是非常重要的概念，因为周围的环境经常是动态的，而且机器人必须运动才能完成某一特定的任务。在一个动态环境中，一台摄像机在两个不同时刻摄取两幅图像，如果两幅图像是同一刚性物体的投影，估计物体的运动参数(R t)和形状参数，称之为运动分析。
此问题与下述问题等价：两个摄像机在同一时刻摄取两幅图像，如果场景是静止的，求两个摄像机的相对位置及景物的形状参数。
在摄像机内参数已知的情况下（即摄像机已标定），关于运动参数可利用本质矩阵等求解（参见第二章2.3节）。
问题：在摄像机未标定的情况下，可否求解运动参数，以及如何求解运动参数，这是近
[8]
2
年来计算机视觉领域研究的另一热点问题。
另外，机器人定位与导航的经典方法是在机器人的工作环境中设置一些控制点，并测量出它们在世界坐标系中的坐标，然后根据它们与其二维图像点间的对应关系，来求解机器人方位。由于机器人工作环境的限制，所能给出的控制点是非常有限的，因此在摄像机视场范围内可见的控制点是极少的，于是研究至少需要多少个控制点才能确定机器人方位的问题具有非常重要的意义，这就导致了所谓的PNP问题（Perspective N Points）的研究。PNP问题也是近年来计算机视觉领域研究的热点问题之一。
当然还可以归纳出更多的热点问题，但上述几个问题在理论和实用上都是十分重要的，也是本论文要着重研究的问题。为了便于论文的展开，下面将在1.2节、1.3节和1.4节分别对上述热点问题的背景和现状作进一步的介绍。与上述热点问题有关的形式化介绍和推导将在本论文的后续章节中给出。
说明：因为多幅图像可以由多视点或序列图像得到，所以，在后续章节中，除非特别说明，我们将统称为多视图。
1.2 多视图三维重构
在计算机视觉领域中，由多幅图像恢复摄像机运动参数和空间物体三维几何形状的问题称为多视图三维重构，它一直是计算机视觉研究的重点和热点之一。该问题的研究成果可以直接应用于机器人导航、精密工业测量、物体识别、虚拟现实以及军事等方面。近年来，该问题又引起多媒体和计算机图形学界的极大关注，为了生成已知景物和虚拟物体的合成环境，必须进行三维重构，否则用虚拟技术合成的环境只能用于浏览，而不能进入其中漫游。因此对三维重构理论和方法的研究无论是在计算机视觉中还是在工程应用中都具有十分重要的理论意义和实用价值。
三维重构不仅仅只局限于空间点的重构，也可以进行空间直线、曲线、曲面等更高级的三维物体基元的重构，研究这些基元的重构对提高重构效果有积极的作用。由于空间点的重构是三维重构的基础，所以本论文的主要工作是基于点的三维重构。
从立体视觉的角度来讲，有时不需要（或者说在有些视觉任务中不需要）在某一个特定的坐标系下（例如欧氏世界坐标系或欧氏摄像机坐标系）重构几何物体的表达，只要任意两种重构结果S1与S2（由于坐标系选择的不同得到的解）之间存在S1?TS2，T属于某一变换群G，则称S1与S2在变换群G的意义下等同，我们称重构在变换群G的意义下等同的S中
3
的任何一个，为在变换群G意义下的重构。如果G是欧氏变换群，或者仿射变换群，或者射影变换群，则我们分别称为欧氏几何意义下，或仿射几何意义下，或射影几何意义下的重构。由于欧氏变换群是仿射变换群的子群，而仿射变换群又是射影变换群的子群，所以射影重构是最一般意义下的重构。
早期的三维重构方法都必须对摄像机进行预标定，这就大大限制了其应用范围，只能应付静止和已知环境下的重构工作。1992年Faugeras和Hartley提出的利用未标定图像序列计算射影结构的理论，使这方面的工作有了显著地提高。在这种理论框架下，可以从未标定图像序列进行三维射影重构，这是一种与欧氏几何相对独立的表达，它给出某一三维射影空间下关于深度、三维结构和运动的描述。这种描述在许多应用中可以直接采用。如果某些应用要求得到度量（欧氏）结果，只要给出进一步信息（如摄像机内参数等），就可以从射影重构恢复欧氏度量（欧氏重构），这是一种与早期欧氏几何意义下的三维重构不同的研究方法。这种两步计算结构称为分层重构
[10]
[6]
[9]
[1]
。
在实现分层重构的过程中，射影重构是关键的第一步，它对欧氏重构结果的精度起着决定性作用，因此许多研究者都把射影重构作为主要研究对象，提出了许多方法和技术，其中矩阵分解方法经理论和实验证明是一种非常有效的方法分解实现三维重构的算法是由Tomasi等
[12]
[11]
，是近年来研究的热点。利用矩阵
于1992年首先提出的，该算法是在摄像机正交射
[13]
影模型基础上实现的，后来又被Poelman和Kanade扩展到弱透视和准透视投影，但由于其
简单性和可靠性被广泛引用。这些算法的显著特点是可以在仿射几何意义下，将由二维图像点坐标构建的测量矩阵分解为分别表示摄像机运动和空间物体三维几何形状的两个矩阵，称为仿射分解（affine factorization）。近年来，出现了一些基于透视摄像机模型的矩阵分解算法，称为透视分解（perspective factorization），透视分解和仿射分解的本质区别在于每个图像点的射影深度未知，故测量矩阵也未知，这就意味着不能直接利用仿射分解算法来获取数据。因此，在这些算法中最关键的问题是如何估计射影深度参数。1996年Christy和Horaud
[14]
提出
了一种由透视投影图像恢复物体欧氏形状的算法，该算法从准透视摄像机模型开始，通过测量矩阵的迭代分解，估计深度参数，该算法必须已知摄像机的内参数。另外，1996年Sturm和Triggs
[15]
对于未标定透视投影图像提出了一个非迭代分解算法，通过基本矩阵和极点来计算
射影深度，该算法对图像之间对应点的定位误差相当敏感，必须特别注意才能获得可靠的结果。1997年Charlie Rothwell等
[11]
对若干种射影重构方法进行了综合比较和实验，并指出基于
矩阵奇异值分解（SVD）方法提供的结果最好。在矩阵分解方法中最关键的问题是估计射影深度参数，一旦获得正确的射影深度后，就可以构建一个关于射影深度和图像坐标的测量矩
4
阵，通过矩阵分解的方法将测量矩阵分解为射影空间下的摄像机运动和空间物体三维几何形状，即实现射影重构。然后在摄像机内参数已知的情况下，利用上述结果求解一个非奇异矩阵，通过此矩阵可以将射影空间下的摄像机运动和物体形状变换为欧氏空间下的摄像机运动和物体形状，即实现欧氏重构。
概括地说，基于矩阵分解的分层重构，主要包括以下两个内容： （1）射影重构 ①估计射影深度；
②构建一个关于射影深度和图像坐标的测量矩阵；
③通过矩阵分解的方法，求解射影空间下的摄像机运动参数和空间物体三维几何形
状。
（2）欧氏重构
①摄像机自标定（求解摄像机内参数）； ②求解射影空间到欧氏空间的变换；
③恢复欧氏空间下的摄像机运动参数和空间物体三维几何形状。 目前，三维重构算法可分为两大类
[11]
：显式重构（explicit reconstruction）和隐式重构
（implicit reconstruction）。所谓显式重构是指利用三维框架中的几何理论直接计算空间点的三维坐标；而隐式重构是通过计算对应图像的基于Cayley代数和交比（cross ratios）等射影不变量来完成的。本论文将集中注意力于显式重构的理论和算法研究。
1.3摄像机标定
摄像机标定是计算机视觉领域中从二维图像获取三维欧氏空间信息必不可少的关键一步。图像上每一点的亮度反映了空间物体表面某点发射光的强度，而该点在图像上的位置则与空间物体表面相应点的几何位置有关。这些位置的相互关系，由摄像机成像几何模型所决定。该几何模型的参数称为摄像机内参数，这些内参数必须由实验与计算来确定，实验与计算的过程称为摄像机定标。
传统的摄像机标定方法需要在摄像机前放一个已知形状和尺寸的物体，称为标定物或标定参照物（reference object），摄像机获取该物体的图像，并由此计算摄像机的内参数。由于在某些视觉系统中（如机器人视觉系统），需要经常调整摄像机光学系统（如焦距、光圈等），摄像机的位置也会根据周围的环境而移动，因此，需要在每次调整后对摄像机的内参数重新进行标定，在这种情况下，若每次标定都需要在摄像机工作环境中放一个已知的标定物常常
[1]
5