基于单目视频帧的基础矩阵鲁棒估计算法

邹云龙, 杨 杰

(青岛大学 机电工程学院，山东 青岛 266000)

0 引 言

同一场景中的2个不同角度所拍摄的图像，具有相应的几何约束关系，即対极几何约束，在数学上用代数表示为基础矩阵。基础矩阵在三维重建[1]、相机标定[2]等诸多方面具有重要的地位，如何获得精确的基础矩阵，也是目前计算机视觉领域的研究热点。研究者们对此提出了各种算法，目前，主要估算基础矩阵的方法有鲁棒法和迭代法。典型的算法有RANSAC(random sample consensus)[3]，通过随机抽取，去除异常点，再通过内点集估算基础矩阵，具有稳健的效果。但效率较低，尤其随着误匹配率的增加，计算时间也随着大量增加。迭代法的代表有M估计法[4]，通过定义权重函数，加权迭代整个数据集，对噪声较大的点有良好的抑制效果。但需要良好的初始值，对误匹配率较大的数据集处理，效果较差。颜坤等人[5]将野值去除融入到计算基础矩阵的过程中，从而实现稳定的基础矩阵估计。张永祥等人[6]提出对M估计法引入动态惩罚加权的思想，提高估计的精度，但增加了运行时间。WANG L等人[7]在M估计法上重定义加权函数来估计基础矩阵。

本文基于前人的工作提出了一种新的适用于视频的基础矩阵鲁棒估计算法，先确定最优和次优的2个子样本集，在次优的样本集上RANSAC拟合模型，并对最优子集中的测试数据进行检测，达到阈值，则标记为成功模型，利用成功模型对全体样本进行检测，能够有效减少错误的模型检测时间，成功模型的数量达到一定值，则将包含最大内点集的基础矩阵，作为初始矩阵。然后引入匹配点的分数和内点率，作为权重因子，进行加权估计，得到待优化矩阵。最后利用第一帧和第三帧在中间帧的两条极线交于一点的关系，进行光束平差法优化。

1 基础矩阵与RANSAC

1.1 基础矩阵

从2个不同的相机角度观察空间中的3D点X，在2个成像平面I和I′分别成像于p和p′，并形成对极约束

p′FTp=0

(1)

式中F可以用一个秩为2，3×3的奇异矩阵表示，即基础矩阵，自由度为7，至少需要7对点求解。并且不与相机内参产生联系，只与场景有关。

1.2 RANSAC

传统的RANSAC算法通过大量的随机抽样数据点来拟合模型F，然后用F求出所有匹配点到极线的距离，与设定的阈值作比较，确定内点集，经过多次采样后，得到数量最多的内点集N，再对N进行归一化八点算法，求出基础矩阵。该方法存在一些缺陷，1)随着误匹配率增加，迭代次数增长过快，2)每次采样拟合的模型，都会对所有的匹配点进行检测，即使该模型是错误的，这样将造成计算效率不高。针对这个问题，本文对此提出了新的预检验方法，能够有效的减少计算时间。

1.3 新的预检验方法

传统RANSAC每次迭代都会检测所有内点，当拟合的是错误模型时，这样的步骤是毫无意义的。然而可以使用少数的点去预检测模型，便能够有效地减少计算时间，于是如何找到这些少数点，以及确定它们的准确性，又是一个需要面对的问题。

本文通过Sift匹配对的欧氏距离判断它们的优劣程度，并作为先验信息。随机测试5组真实图像的匹配对，并按照匹配对的欧氏距离由低到高排序，采用人工判断和算法后验，统计各自前5 %匹配对的内点率。实验结果表明这5组的内点率变化随着匹配对的增加，前5 %匹配对的内点率大都维持在70 %以上。因测试数据有限，不能代表所有图像匹配对的前5 %内点率均在70 %以上，依然可以作一个可行性假设。本文假设图像匹配对的前5 %的内点率在50 %以上，以此为前提，提出新的预检验方法。

首先，去除匹配距离过大以及重匹配的匹配对，然后根据匹配点的欧式距离，将匹配点由低到高排序，选取前5 %匹配点为最优子集S1，前10 %为次优子集S2，设置迭代次数为300，每次对S1子集随机抽取8个点拟合模型，利用该模型对S1子集内的匹配点由式(2)进行内点判定，当r小于等于阈值T时，T设为3，判定为内点，否则为外点。统计当前模型的内点总数N，如果内点总数N与S1集合中的数量的比值大于50 %,则将这8个点作为测试点，退出迭代。否则继续采样，直至达到最大迭代次数，若依然没有得出测试点，则上述假设失败，将测试点设为空

(2)

2 初始值计算

经过预检验后，便可计算初始基础矩阵，初始矩阵计算步骤如下：对子集S2进行RANSAC,迭代次数设为1 000，随机采样8个点，并用归一化八点法[8]拟合模型。

1)如果预检验后的测试点不为空：则通过式(2)对模型用这8个测试点进行检测，并求这8个点的平均值。当误差平均值大于T时，抛弃模型，继续采样。当误差均值小于等于T时，记为成功模型Fj，j为检测内点的次数，初始值设为0，检测次数j加1，接着对所有匹配点进行内点检测，若为内点，该匹配点被标定为内点的次数f加1，f初始值为0，并记下当前拟合的Fj的内点集的数目Nj，当j≥10，退出循环迭代。循环结束后j大于0，则取出最大内点集所对应的基础矩阵作为初始矩阵。否则失败，退出程序。

2)如果预检验后的测试点为空：则退化为一般的RANSAC结构，每次拟合模型，测试所有匹配点，记录该模型对应的内点数，以及更新匹配对被标记为内点的次数f，直至达到最大迭代次数，取出拥有最大内点数的模型，作为初始矩阵，此时检测次数j为1 000。

3 加权估计

通过上一步骤获得的初始矩阵，需要优化。受文献[10]启发，提出改进方法，将匹配点分数和内点率结合作为权重因子，为内点集的匹配点分配不同的权重，对初始矩阵的内点集进行一次加权估计,可以得到更精确的基础矩阵。本文采用Sampson误差作为最小化函数

(3)

式中wi为权重函数。对权重函数重新定义，并将匹配点的分数和内点率引入。匹配点分数G定义如下

G=G(p,p′)=e-t,t∈[0,1]

(4)

式中t为匹配对的归一化欧氏距离，取值范围为[0,1]。内点率I定义

I=f/j

(5)

式中f为该点被标记为内点的次数，j为拟合模型成功的总次数，最终的权重函数wi定义如下

(6)

式中r由式(2)解出，η为当前内点集数量占全部匹配对的百分比例，α，β，φ均为常数，α设为0.2，β设为0.8，φ,σ参照文献[10]。

4 光束平差法优化

(7)

式中ξ(i)为公共集中第i组特征点产生的残差值。该方程依然存在一些问题，即可能会产生退化情形，当两条极线趋于重合时，该残差方程会失效，即当pi2与两个极点ei12,ei32趋于共线时。为防止退化情形对优化结果产生不利的影响，定义退化阈值χi

(8)

分别为极线L12，L32的斜率。最终优化的目标函数

(9)

5 实验结果比较与分析

为验证算法的鲁棒性和精确性，用真实的图像数据进行验证，并将本算法与传统算法RANSAC，LMedS[9],以及最近的ORSA[10]算法进行比较，因基础矩阵不存在唯一性，相差一个常数因子下，具有等效性。采用点到对应极线的平均距离作为评价标准，用式(10)表示，间接地反映基础矩阵的估计准确性。实验平台基于OpenCV,操作系统为Ubuntu

(10)

选取4个场景的视频，包含2个室内环境，以及2个室外环境，如图1所示，并从每个视频中任意截取具有重叠区域的3帧，获得4组数据。

图1 4组测试图像

5.1 实验效果

为了更加直观地表示算法的精确度，选取其中一组，比较前2张图像的未估计基础矩阵的匹配图，优化后的匹配图以及极线图。从图2中可以看出，经过算法处理后的匹配点有明显的改善，几乎去除了所有的误匹配点，匹配点也都落在相应的极线上。

图2 室内一图像的算法处理效果

5.2 算法比较

本文算法与RANSAC，LMedS,以及近期ORSA算法分别应用于这4个场景，比较它们的平均差，及其标准差。本文算法计算了2个基础矩阵，因篇幅有限，取前2帧的基础矩阵作为比较对象。表1中mea代表平均值，std代表标准差，斜杠/表示数据过大。Proposed为本文算法。从表中看出本文算法相比先进算法ORSA，大致相当，在室外一的数据上的表现甚至超过该算法，而LMedS在室外一的数据上表现很差，因为这组数据的误匹配率超过50 %，相对而言传统RANSAC虽然总体上不如LMedS算法，但当数据误匹配率较大时，RANSAC比LMedS更鲁棒，而本文算法在误匹配率较大的数据上依然有较好的表现。

表1 算法精度比较 像素

6 结 论

本文提出了一种适用于视频帧的基础矩阵鲁棒估计算法，使用新的预检验方法减少了传统RANSAC的计算时间，并将匹配点的分数和内点率结合，作为权重因子，对内点集加权估计，并利用对极转移构建残差方程，然后利用光束平差法进行优化，在不同的真实图像数据上，相比以前算法，均有不错的提升。本文算法依然有些许不足，假设全部匹配点前5%的内点率超过50%的情况，在某些数据上，存在失败的可能，导致预检验失效。另外使用光束平差法优化，也会稍微增加计算时间，因此，提高算法的精度和计算效率，依然是下一个研究方向。