一种估计基础矩阵的新鲁棒算法

甄艳，刘学军，王美珍

（南京师范大学地理科学学院，南京师范大学虚拟地理环境教育部重点实验室，江苏 南京 210046）

从两个不同视点处获得的同一场景的两幅图像间存在着一定的约束关系，即对极几何关系。对极几何独立于场景结构，是在非标定情况下可以从图像中获得的唯一信息，包括摄像机所有的内部参数和外部参数信息。基础矩阵是对极几何关系的代数表示，它的准确求解是三维重建［1］、运动估计、相机自标定［2］、匹配及跟踪的基础［3］。

由于在特征点的提取与匹配过程中，不可避免的含有噪声和outliers（粗差数据或异常数据）［4］，因此，利用图像间对应点进行基础矩阵估计，其精度总会受到影响。虽然人们已经在如何精确、鲁棒地估计基础矩阵方面做了大量的研究，但是至今没有一种估算方法可以完全消除误匹配及噪声对估算精度的影响，因此，准确求解基础矩阵仍然是计算机视觉中的难点之一。本文基于RANSAC方法的随机抽样思想，提出了一种估计基础矩阵的新鲁棒算法，以便准确反映对极几何关系，进而提高三维重建的质量。

1 对极几何与基础矩阵

如图1所示，假设C和C′分别为两个摄像机的光心，两个摄像机拍摄获得的图像分别为I和I′，m和m′是三维空间点M 在两幅图像上的投影点，空间点M和两个摄像机的光心C和C′所在的平面用π表示，该平面称为对极平面（Epipolar Plane）。对极平面π与两个图像平面I和I′的交线分别为l和l′，这两条交线称为极线（Epipolar Line），则点m的对应点m′必然在m的对极线l上，反之亦然。

图1 对极几何Fig.1 Epipolar geometry

目前，利用图像间对应点估算基础矩阵的方法主要可分为3类：线性方法、迭代方法和鲁棒方法［5］。线性方法计算速度快，复杂度低，对噪声和错误数据非常敏感，主要有7点法［6，7］和8点法［8－10］；迭代方法［11，12］精度比线性方法高，但计算时间长，并且不能处理错误匹配点；当匹配点集中出现错误匹配时，线性方法和迭代方法不再适用，而鲁棒方法可以解决这类问题，如最小中值法（Least Median Squares，LMedS）［6］、随机抽样一致性法（Random Sample Consensus，RANSAC）［13］以及 M 估计算法（M－Estimator Sample Consensus，M－Estimators）［14］。鲁棒方法的特点是对噪声和错误匹配都有更好的鲁棒性，但每种鲁棒方法都有其自身的局限性，如MEstimators方法对初始值依赖较大，受错误数据影响较大；LMedS方法对outliers的鲁棒性较好，但当原始匹配点集合中错误数据率接近50%时，该方法的误差很大［6］；RANSAC方法是计算机视觉中关于鲁棒参数估计的一个典型方法，应用较为广泛，错误数据超过50%时仍能获得较好的结果，但在某些情况下，容易陷入局部最小。另外，胡明星等［15，16］将遗传算法引入基础矩阵的估计方法中，可在一定程度上提高求解的精度，但遗传算法计算复杂，使得整体算法的复杂度较高。

2 内点集及基础矩阵估计

从现有研究看，目前没有一种方法可以做到完全消除噪声和错误匹配对基础矩阵估计的影响，提高基础矩阵估算精度的关键是获得一个好的内点集，在该内点集中应尽可能少的包含误差点。解决这一问题的一个可行方法是在一个好的初始内点集的基础上，采用鲁棒扩充算法［17］，对初始内点集进行扩充获得一个较优内点，基于该较优内点集，重新估计基础矩阵获得较优的解算结果。

2.1 内点集定义

本文提出一种获取内点集的新方法，首先选择被标记为内点次数与抽样次数相同的点，即选择在每次抽样过程中都被判定为内点的这部分点（当这部分点的数量小于8时，选择被标记为内点次数最多的前8对匹配点）构成初始集合。尽管初始集合中点的概率基本可达到100%的内点，但由于RANSAC方法在判断是否为内点这一问题的解决方案是通过设定一个阈值确定的。因此，从理论上并不能保证初始集合中的点全部是内点，只是使初始集合中尽可能多的由内点构成。为进一步提高精度，在鲁棒扩充过程中，采用C－Step方法［17］对当前集合进行调整。

图2 点到极线的对极距离Fig.2 Epipolar distance from point to epipolar line

内点集B的扩充过程可以用数学模型表示为：

2.2 内点集获取

初始内点集性能的好坏直接决定了最终获得内点集的质量，本文方法在每次抽样判断的过程中标记出每对匹配点是否为内点，完成多次抽样后，最后统计每个点被判定为内点的次数。选择次数较多的匹配点构成初始集合，采用鲁棒扩充方法对初始内点集进行扩充获得一个较优内点集。

设初始集合用Sj表示，采用鲁棒扩充方法，以点的对极距离和作为判断准则对初始子集进行扩充。在初始集合Sj的基础上，需要对匹配点集中剩余的匹配点进行考核。在每次考核过程中，首先将当前被考核匹配点添加到集合Sj中生成新的集合Sj＋1，然后利用Sj＋1计算基础矩阵Fsj＋1，并计算目标函数值Z（FSj＋1）。如果目标函数值Z（FSj＋1）＜Z（FSj），说明当前被考核匹配点可以接受，并采用C－Step方法对当前的内点集进行调整，否则该匹配点需要从集合Sj＋1中删除，进而判断下一个匹配点。

2.3 基础矩阵估计

针对传统RANSAC算法获得的基础矩阵并不一定就是最优解这一问题，本文提出了一种估计基础矩阵的新鲁棒算法。基本原理是：在每次抽样过程中记录每个点是否被判定为内点，完成多次抽样后，统计每对匹配点被标记为内点的次数，并降序排列。选择内点次数与抽样次数相同的点（若这部分点的数量小于8，则选择被标记为内点次数最多的前8对匹配点）构成初始集合。在多次抽样的内点判定过程中，如果该点被认为是内点的次数较多，那么从概率上讲，它为内点的可能性也应较大，因此，在初始集合的构成时，就保证了尽可能多的选择内点。在初始内点集的基础上，采用鲁棒扩充算法，以点到极线的对极距离和作为扩充准则，对初始内点集进行扩充。为了提高算法的鲁棒性与解算精度，在每一次迭代扩充过程中，若有满足约束条件的点添加到当前集合，则需要采用C－Step方法对当前内点集进行调整优化。最后根据获得的内点集估计基础矩阵，整个流程如图3所示。

图3 基础矩阵估计流程Fig.3 Flowchart of the fundamental matrix estimation

3 实验结果与分析

3.1 实验设计

为了验证本文算法的有效性和鲁棒性，通过对模拟数据和文献［17］中的真实图像数据进行实验，将本文的算法与现有主要的鲁棒方法RANSAC、LMedS和M－Estimators进行比较，以平均对极距离作为算法的评价标准。

模拟数据的生成：采用程序生成模拟同一场景不同视角的两幅图像的100对匹配点。模拟数据实验部分从两个不同的角度进行：1）分别添加不同强度的高斯噪声。为了模拟真实图像特征点提取与匹配的效果，在模拟数据中，添加20%的外点数据。2）验证在不同外点比率下算法的精度。为尽量模拟真实图像特征点匹配效果，在模拟数据中分别为每对匹配点叠加均值为0、方差为1的高斯噪声。

另外，由于本文算法以传统的RANSAC算法的抽样思想为基础，结合鲁棒扩充方法，将寻求内点集的过程分为多个阶段完成，在每次扩充过程中，算法都希望添加到内点集中的点能够优化计算结果。因此，在整个寻优过程中，一方面可以提高算法的精度和鲁棒性，另一方面，却增加了时间上的开销，降低了求解的效率。为了比较算法的效率，本文给出了几种算法的时间比较。

3.2 结果分析

（1）模拟数据实验结果。图4为匹配点在不同噪声误差下4种算法计算精度的比较，图5给出了在不同外点比率下不同算法计算精度的比较。

通过实验结果可以看出，与其它3种方法相比，本文算法精度最高。图4中，当匹配点集中包含不同强度的高斯噪声时，LMedS与RANSAC算法的精度相当，但随着噪声增强，RANSAC算法的精度略优于LMedS方法，M－Estimators算法的精度最差，这主要是由于M－Estimators方法的结果依赖于由线性方法估算得到的初始值，而随着误差的增大，由线性算法估算得到的结果精度较差，这导致 MEstimators方法的精度也随之降低。通过图5可以看出，随着外点率的增加，本文的算法一直都能保持较高的精度，具有较好的鲁棒性，当外点率超过40%时，其它3种算法的精度都有较大幅度的降低，外点率接近50%时，LMedS方法的精度迅速降低。

（2）真实图像实验结果。由于篇幅所限，在此以2幅真实图像为例，图像1包含99对匹配点，图像2包含156对匹配点，4种方法的精度及鲁棒性比较结果如表1所示，图6为通过本文算法提取的部分对极线。从表1和图6真实图像的实验结果看，本文提出的方法对基础矩阵的估计精度和稳定性均优于其它3种方法。

表1 真实图像的精度及鲁棒性比较Table 1 The precision and robustness of different methods with real images

图6 2幅真实图像通过本文算法提取的部分对极线Fig.6 Part of the epipolar lines of the real images by the proposed algorithm

（3）计算时间比较。为了验证本文算法的效率，以2幅真实图像为例，本文分别计算了包含不同匹配点数量时4种算法各自所需的计算时间，图7为4种算法计算效率的比较结果。

图7 不同匹配点数量下4种算法所需计算时间Fig.7 Comparing the computing time of 4 methods

本文算法最大的不足在于提高解算精度和鲁棒性的同时，降低了求解的效率，增加了计算时间。在鲁棒扩充过程中，始终需要满足目标函数值保持最小这一约束条件，通过保证局部的最优实现整体最优。从图7可知，M－Estimators方法的效率最高，其次是RANSAC方法和LMedS方法。与其它3种鲁棒方法相比，尽管本文方法的效率相对较低，但在保证解算精度的前提下，可考虑引入并行技术及优化方法对其进行改进。

4 结论

本文针对传统RANSAC方法估计基础矩阵获得的解并不是最优解的问题，提出了一种估计基础矩阵的新鲁棒方法。本文方法在多次抽样过程中，通过记录每对匹配点被判定为内点的次数来确定初始集合，然后采用鲁棒扩充方法获得内点集。从初始集合的选取开始就保证了算法的精度，内点集的确定是经过在扩充过程中各阶段的局部最优选择实现最后的整体最优得到的。实验结果表明，本文方法对特征点的匹配精度没有特殊的要求，能有效剔除错误匹配点，适用于错误数据率和高斯噪声较大的情况，其解算结果的精度和鲁棒性均优于现有的鲁棒方法。本文算法的不足之处在于整个扩充过程中增加了计算时间上的开销，下一步工作将进一步研究如何在保持计算精度的前提下，尽可能提高算法的计算效率。

［1］ 郑顺义，张祖勋，翟瑞芳.基于非量测相机的复杂物体三维重建［J］.武汉大学学报（信息科学版），2008，33（5）：446－449.

［2］ 卢玥，刘学军，王美珍，等.基于数位的相机径向畸变参数计算［J］.地理与地理信息科学，2011，27（6）：18－22.

［3］ 孙凤梅，胡占义.摄像机简化模型对三维重构的影响——分析与实验［J］.计算机辅助设计与图形学学报，2005，17（10）：2257－2262.

［4］ BRANDT S.Maximum likelihood robust regression with known and unknown residual models［A］.Proceedings of the ECCV 2002［C］.Copenhagen，Denmark，2002.97－102.

［5］ XAVIER A，JOAQUIM S.Overall view regarding fundamental matrix estimation［J］.Image and Vision Computing，2003，21：205－220.

［6］ ZHANG Z.Determining the epipolar geometry and its uncertainty：A review［J］.International Journal of Computer Vision，1998，27（2）：161－195.

［7］ 钟慧湘，庞云龙，冯月萍.估计基础矩阵的一个新方法［J］.仪器仪表学报，2005，25（4）：411－413.

［8］ LONGUET－HIGGINS H C.A computer algorithm for reconstructing a scene from two projections［J］.Nature，1981（293）：133－135.

［9］ HARTLEY R I.In defence of the 8－point algorithm［A］.Pro－ceedings of the International Conference on Computer Vision，IEEE Computer Society Press［C］.Boston，1995.1064－1070.

［10］ WU F C，HU Z Y，DUAN F Q.8－point algorithm revisited：Factorized 8－point algorithm［A］.IEEE Int.Conf.on Computer Vision［C］.2005.

［11］ ZHANG Z，DERICHE R，FAUGERAS O，et al.A robust technique for matching two uncalibrated images through the recovery of the unknown epipolar geometry［J］.Artificial Intelligence，1995，78（10）：87－119.

［12］ LUONG Q－T，FAUGERAS O D.The fundamental matrix：Theory，algorithms and stability analysis［J］.International Journal of Computer Vision，1996，1（17）：43－76.

［13］ ONDREJ C，TOMAS W，JIRI M.Epipolar geometry estimation via RANSAC benefits from the oriented epipolar constraint［A］.Proceedings of the 17th International Conference on Pattern Recognition［C］.Los Alamitos，2004.112－115.

［14］ TORR P H S，MURRAY D W.The development and comparison of robust methods for estimating the fundamental matrix［J］.International Journal of Computer Vision，1997，24（3）：271－300.

［15］ 胡明星，袁保宗，唐晓芳.基于混合遗传算法的对极几何估计［J］.电子学报，2003，31（10）：1481－1485.

［16］ TANG C Y，WU Y.Fundamental matrix estimation using evolutionary algorithm with multi－objective functions［J］.Information Science and Engineering，2008，24：785－800.

［17］ 胡玉锁，陈宗海.一种新的基于线性EIV模型的鲁棒估计算法［J］.计算机研究与发展，2006，43（3）：483－488.