八点算法的辩护_译文.doc

对于八点算法的辩护 Richard I. Hartley, GE-Corporate Research and Development? Schenectady, NY, 12309, email : hartley@ 摘要 基础矩阵是对两个非定标相机拍取的图像进行分析的基本工具，而八点算法是在从一系列的八个及以上的点阵中计算基础矩阵时常被引用的方法。它有实施简单的优势。然而，普遍的观点是：它极其容易受到噪声的影响，所以实际上对大多数的目标没用。这篇论文通过显示在算法前对匹配点的坐标进行简单的单位化（平移和缩放），其结果比得上最好的迭代算法来挑战上面的观点。这种改善的表现被理论所证实，并在扩展的真实图片的实验上得到验证。 1介绍 八点算法用于计算基础矩阵（essential matrix）是通过Longuet-Higgins在一篇现在很经典的论文（[7]）中介绍的。在那篇论文中，基础矩阵（essential matrix）是用来通过非定标照相机的两个视角来计算一个场景的结构。八点算法一个很大的优点是这个算法是线性的，所以能很快很简单的实施。如果8个匹配点知道了，那么一系列线性等式的解就有了启示。如果多余八个点，那么线性最小方阵最小化问题必须得到解决。在这篇文章中我们将用八点算法这个术语来描述这个方法，无论是只有八点还是八点以上。 本质属性的本质矩阵，是它方便的概括了极几何的影像配置。有人马上注意到，相同的算法可能用来计算由非标定相机得来的具有相同特性的矩阵。在这个非标定相机的案例中，习惯把这个矩阵派生成基础矩阵。正如在校准的情况下，基础矩阵可以被用来从两个非标定的视点重建现场，但在这种情况下，只相当于一个投影变换（[3，5]）。 不幸的是，尽管具有简便性，8点算法还是经常因为对规格的匹配点的噪声过于敏感而受到批评。事实上，这种普遍的信仰已成为普遍的智慧。因此，由于它的重要性，很多另类的算法已被提议来计算基础矩阵。文献[8]比较和描述了几种寻找基础矩阵的算法 。毫无例外，这些算法都比8点算法要复杂得多。其他迭代算法也在[6，1]中有描述（简单）。 本文的目的在于挑战那种8点算法是不完善的，比其他复杂的算法要低劣的普遍的观点。八点算法的不佳表现大致可以追溯到实施时没有对数值考虑，以及订定的线性方程组集得到解决的最具体状况进行充足的估计。在本文中将说明，对图像中点集在明确的表述线性方程组前进行一个简单的变换（平移和缩放）将在问题的条件下产生一个巨大的改善并因此而得到稳定的结果。做到这点转换而增加的算法复杂性是微不足道的。 并不是在这里说改善后的8点算法能有最好的迭代算法一样的表现。不过，在图片上的数以千计的实验表明，改善的8点算法与迭代的差别不大。事实上，改善后的八点算法比有些迭代算法还要好。 2 八点算法的纲要 2.1 记法 向量以粗体的小写字母来表示，比如u，并且所有这样的向量都被视为是列向量，除非是明确的转置矩阵（比如就是行矩阵）。向量像矩阵一样的相乘。特别是对于向量u和v，v的结果体现的是他们的内积，而是一个矩阵。向量f的标准等于总合方阵的平方根，也就是向量的欧几里德长度。相似的，对于矩阵，我们使用Frobenius范数， 它被定义为总合方阵的平方根。 2.2 基础矩阵的线性解 基础矩阵是由如下方程定义的： （1） 对两幅图片中的任意匹配点均成立。只要给出足够多的匹配点对（最少八个），方程（1）就可以用来计算未知的矩阵F。特别是写成和的每一个点对产生一个关于未知变量Ｆ的线性方程。此方程的系数是很容易通过已知变量u和写出来的。具体的来说，方程相对一对点和展开如下： 方程矩阵的行可以表示为一个向量，从所有的点对，我们得到一系列如下形式的线性方程： Af=0 （2） 其中f是一个含有基础矩阵入口的9个向量，A是方程矩阵。基础矩阵F，因此解向量f只被定义为由一个不为人知的缩放比例。基于这个原因，也为了避免意义不大的解f，我们添加了一个额外的约束||f||=1，这样，f就变成了规范的f。 在这些条件下，通过8个一样少的相配的点数来找出系统的解成为可能，我们有一个超过指定的系数方程式。假设这系列方程的非零解存在，我们推断出矩阵A必须是秩亏。换言之，尽管A有9列，A的秩最多也只能是8。事实上， 除特殊配置外，矩阵A的秩正好是8，并且对于f有唯一解。 这个以前讨论假设的数据是完美的，无噪声的。事实上，因为失实测量或者匹配点的规格，矩阵A将不会出现秩亏，将会出现秩为9的情况。在这种情况下，我们找不到方程Af=0的