范宜凯,刘石坚,潘正祥,2

(1.福建工程学院人工智能研究所，福建 福州 350118;2.山东科技大学计算机科学与工程学院，山东 青岛 266590)

1 引言

基础矩阵估计是利用运动中恢复结构(Structure from Motion)[1,2]、多视角立体视觉(Multi-view Stereo)[3,4]等方法获取空间目标信息的关键问题，被广泛应用于基于图像的建模(Image-based Modeling)[5,6]、即时定位与地图构建(Simultaneous Localization and Mapping)[7,8]等计算机视觉领域前沿热点研究中。

从一组不同角度、不同距离拍摄的同一场景所得的二维序列图像中还原出目标对象的三维空间信息，其理论基础是彼此之间存在的对极几何约束[9,10]。基础矩阵在对极约束下描述了相关图像中匹配特征点对之间的数学关系。相关研究最早可见于摄像机自标定[11,12]等算法中。

令pi=(xi,yi,1)T和p′i=(x′i,y′i,1)T分别是第1幅图像I和第2幅图像I′中匹配的第i(1≤i≤n，n是特征点的对数)个特征点的齐次坐标。式(1)描述了这些特征点之间的对极约束关系。

p′iTFpi=0

(1)

其中，F即基础矩阵(Fundamental Matrix)。

F的估计是一个方程组超定问题，在数学上可通过给定的8对特征点进行求解。鉴于误差的普遍存在，可将n对特征点分成2类，即与其真实值相比误差较小的内点和误差较大的外点。那么，要得到较为准确的估计结果，关键在于8对特征点的选取方法。称由8对内点组成的集合为最小内点子集，每组最小内点子集可确定一个基础矩阵估计模型。本文提出一种基于改进拟仿射变换的基础矩阵估计方法，其核心思想在于：基础矩阵估计模型对所有特征点的拟合能力越强，所选取的最小内点子集越好。

准确性和效率是衡量基础矩阵估计算法的主要指标。当准确性不够时，往往需要在后期花费高昂的计算代价对其进行校正[13]。效率低则会影响系统运行的实时性。针对上述问题，本文将智能算法QUATRE(QUasi-Affine TRansformation Evolutionary)[14]引入基础矩阵的估计问题，主要贡献包括：

(1)提出一种基于特定“基因-染色体”模式的种群协作方法，用于基础矩阵估算。具体来说，与最小内点子集由8对特征点组成相对应，本文提出的种群协作方法将匹配的特征点对看作基因，由8个基因组成1条染色体，通过这种特定的种群协作方式估计基础矩阵。

(2)对原有QUATRE算法进行改进，重新定义齐次坐标系所表示的离散解空间中的种群初始化、变异和交叉等操作，使得利用QUATRE 算法框架解决基础矩阵估算问题成为可能。

(3)提出一种基于置信度的迭代次数确定方式，用于算法加速。与QUATRE算法采用固定迭代次数寻优求解不同，本文提出的迭代次数确定方式基于给定的置信度实时计算终止条件，提升运行效率。

2 相关工作

2.1 基础矩阵估计方法

基于计算机视觉的基础矩阵估计方法主要包括线性法、迭代法和鲁棒法3类。

线性法的典型代表是8点算法及其相关扩展算法。8点算法由Longuet-Higgins[15]提出，使用随机选取的8对特征点来计算基础矩阵。该算法对噪声和误匹配较为敏感。在其基础上Hartley[16]提出一种改进的8点算法，该算法首先对匹配特征点进行尺度和平移上的规则化处理，再使用8点算法计算基础矩阵，最后进行逆规则化操作。实验结果表明，改进的策略对噪声有一定的抑制作用。然而，由于8对特征点仍使用随机的方法获得，因此无法从根本上消除外点对估计结果的影响。

迭代法主要包括M-估计法[17]和事件删除法[18]。M-估计法的特点是采用所有特征点进行迭代，并对其中的外点和内点赋予不同的权重。例如文献[19]中方法所引入的动态惩罚加权机制。该方法在噪声抑制问题上有不错的效果，但在外点较多的数据集上效果不佳。事件删除法就该问题进行了一定的改进，但计算复杂度仍然较大。

鲁棒法的代表有最小中值法LMedS(Least Median Squares)[20,21]、随机抽样一致性算法RANSAC(RANdom SAmple Consensus)[22,23]及其相关改进算法(如高于最小子集算法HMSS (Higher than Minimal Subset Sampling)[24]和M估计抽样一致性算法MSAC(M-estimator Sample Consensus)[25])等。其中，LMedS算法比较简单，对噪声和误匹配比较敏感。许金山等人[26]在LMedS的基础上提出一种单应性矩阵自适应方法，以剔除外点并减少迭代次数。RANSAC算法的核心思想在于使用特征点到极线的距离作为依据，对大量的特征点子集进行测试，从中找到最优的结果，是目前主流的基础矩阵估计方法之一。但是，RANSAC算法需要大量随机初始化最小子集，针对该问题HMSS算法使用一种高于最小子集的抽样算法来加速最优内点子集的寻找。然而，HMSS算法无法明确算法准确性与所使用内点子集规模间的关系。针对RANSAC结果的优劣性依赖于阈值选取的问题，MSAC算法引入损失函数予以解决，但该算法收敛速度有待提高。

由于进化算法具有在解空间中智能寻优的特点，本文方法采用改进的QUATRE算法[14]解决基础矩阵估计问题。与线性法相比，可以有效剔除由噪声和误匹配产生的外点干扰。相对迭代法来说，由于应用了粒子群协作的方式，能快速汇聚到全局最优解。与鲁棒法相比，能有效减少抽取子集的数量。下面就QUATRE算法的基本概念进行阐述。

2.2 QUATRE算法

QUATRE是一种粒子群进化算法，由Meng等人[14]提出，QUATRE算法种群进化的核心思想如式(2)和式(3)所示：

B=Xgbest+c*(Xr1-Xr2)

(2)

(3)

(4)

上述进化方法从本质上来说是一种特定的寻优求解策略，从种群进化的角度来理解是一种包含变异、交叉操作在内的种群演化过程，因此B和M也可分别称为变异矩阵和交叉矩阵。

基础矩阵估计问题可看作从给定有限匹配特征点对空间中选取8对内点的寻优问题，问题空间是离散的，而原始QUATRE寻优算法是定义在连续域上的，因此，需要对上述寻优策略进行相应的改进，才能将其应用于基础矩阵估计问题求解。

3 本文方法

本节主要介绍基于改进拟仿射变换的基础矩阵估计方法。具体来说，本文方法用匹配的特征点对组建种群，结合粒子群的寻优能力和QUATRE算法解决组合问题的优势来估计基础矩阵，基本流程如图1所示。以匹配的特征点对作为输入，首先基于特定的“基因-染色体”模式对第1代种群进行初始化。然后基于内点率对染色体进行排序，并计算迭代终止条件(最大迭代次数GEN)。当终止条件满足时，方法结束并输出对应的基础矩阵估计值；否则，依次通过变异、交叉和选择操作迭代式地实现种群的进化。

Figure 1 Workflow of the proposed method图1 方法流程图

3.1 初始化

与QUATRE算法在连续坐标空间中生成指定数量具有随机坐标的粒子群初始化方法不同，在基础矩阵估计中，候选特征点是已知的，且通常使用齐次坐标表示，以简化运算。另外，由于8对特征点可确定一个基础矩阵的估计模型，因此本文方法将匹配特征点对的齐次坐标作为基因，使用8个基因组成一条染色体的方式初始化种群。

具体来说，首先使用特定的特征点识别算法(例如SURF(Speeded Up Robust Features)[27])获得2幅图像中的N对匹配特征点，然后按照如式(5)所示的方式将其表示为N×2矩阵A:

(5)

其中,pi,1=(xi,1,yi,1,1)和pi,2=(xi,2,yi,2,1)(1≤i≤N)分别是第i对特征点的2个齐次坐标。

(6)

其中，xu,v=(p(u-1)×8+v,1,p(u-1)×8+v,2)(1≤u≤NP,1≤v≤8),X(1)的每一行就是1条染色体。

3.2 内点率及终止条件

进化算法要求设定一种指标来衡量个体的优劣，以便进行寻优。本文方法使用内点率作为衡量指标。具体来说，对于任意染色体，可利用其所包含的8对特征点确定一个基础矩阵的估计模型。通过该模型可进一步计算得到任意给定特征点到对应极线的距离d，将d小于给定阈值的特征点定义为内点。记N对特征点中，依照某染色体对应估计模型所确定的内点数目为Nin，则该染色体的内点率w可定义为w=Nin/N。根据w可对每代种群X中的所有染色体进行排序，w值最大的染色体即最优染色体，其坐标值用Xgbest表示。

为保证算法的有穷性，QUATRE的种群进化具有固定的最大迭代次数GEN=10000×D/NP,其中NP是种群的规模，D是每个种群个体的维度。也就是说，当种群代数k增长至GEN时算法才能停止。本文方法则提出基于置信度的算法终止策略，即在满足给定置信度要求的情况下按照式(7)求得迭代终止条件值GEN。

(7)

其中，p为预先指定的置信度(例如p=99%)，代表从特征点集中随机选取8行均为内点的概率；wbest即Xgbest对应的内点率。如果当前种群代数k≥GEN,将结束算法，否则按照下文所述的变异、交叉和选择操作继续迭代进化种群。

3.3 进化策略

按照物种进化的思想，种群演化的过程存在个体的变化。通过自然选择，优秀的基因将被保留，不好的突变则被淘汰。对于进化算法来说，令种群当前代数为k，上述过程表现为依次对种群X(k)进行变异、交叉和选择操作，以产生新一代种群X(k+1)。其中，变异操作产生突变的内容，交叉操作实现基因的变化，选择操作则表示优胜劣汰。

3.3.1 变异操作

由于染色体是由基因决定的，根据3.2节有关内点率w值越高染色体越优秀的讨论，可进一步衍生出w值越高的染色体所包含的基因越优秀的结论。与式(2)所示QUATRE所使用的变异方法不同，本文方法将变异基因(p′i,1,p′i,2)(1≤i≤N′)定义为主要来自X(k)中排名前r位染色体中的基因，以及少量来自后N′-r位染色体中基因，其总数为N′，所组成的矩阵A′如式(8)所示：

(8)

为便于实现后续的交叉操作，可从A′中随机抽取D个基因作为一条染色体，连续执行NP次(NP为种群的规模)该操作，得到如式(9)中NP×D矩阵B所示的变异种群。

(9)

3.3.2 交叉操作

交叉操作实现种群的突变，将采用QUATRE所提出的类仿射变换形式进行。若当前种群X通过基因突变产生的种群记为X′，则X′中应既保留X的部分基因，也包含一些来自B中的变异基因，其实现方法如式(10)所示。

(10)

3.3.3 选择操作

种群的进化取决于基因的优胜劣汰，记k为种群X(k)的当前代数，X′(k)为变异种群，则下一代种群X(k+1)的各个染色体应选取X′(k)与X(k)中对应位置中更优的那个，即选择操作。其中，染色体优劣的比较方法仍然通过基于3.2节所述的内点率的比较来实现。

4 实验与结果分析

本节将通过实验说明本文方法的准确性和高效性。实验数据为使用小米MIX 2S手机拍摄的30个场景，共计60幅图像(分辨率为1440×1080)。所有实验均在一台处理器为英特尔双核i5(主频2.5 GHz)、内存16 GB的笔记本电脑上运行，编程环境为Matlab R2017a。为便于展示，从30个场景中选取6个SURF[27]特征点对规模不等的典型场景，并将其编号,如表1所示。

Table 1 Information of six typical scenes of the experiment dataset表1 实验数据中的6个典型场景信息

SA、SB和SA∩B中的点对分别在图2中以“+”“×”和“○”表示(为便于展示，图中仅随机标记1/3的SURF特征点)。

Figure 2 Demonstration of the overlapping of scene A and scene B图2 场景图A和场景图B的重叠度展示

4.1 有效性分析

首先，将本文方法应用于所采集的数据，对各个场景所表示的基础矩阵进行估计，以测试方法的有效性。图3a～图3f分别展示了场景1～场景6的测试结果，其中2幅图中相匹配的特征点用线段连接。每幅子图的上部分是使用SURF[27]算法得到的结果(对应于表1第2列)，下部分是在SURF特征点对基础上使用本文方法所得基础矩阵估计模型所确定的所有内点(对应于表1第3列)。可见，对于不同规模的求解问题，本文方法都能够有效剔除SURF匹配特征点对中的误匹配点。

Figure 3 Results of applying our method to 6 typical scenes after getting rid of the outliers图3 将本文方法应用于6个典型场景的外点剔除效果

图3中每幅子图的上部分为SURF算法生成的特征点对，下部分是在SURF特征点对基础上使用本文方法所得基础矩阵估计模型所确定的所有内点。

4.2 准确性对比及分析

接下来，为评价本文方法的准确性，将基于式(11)对极距离d开展对比实验。

(11)

其中,B是通过评估方法得到的基础矩阵，p和p′分别是特征点对的2个点，(*)1和(*)2分别表示向量的第1个和第2个分量。

使用平均对极距离及标准差作为衡量指标，对LMedS[20]、RANSAC[21]、MSAC[25]和本文方法开展对比实验。具体来说，对6幅场景图像，分别运行LMedS、RANSAC、MSAC 和本文方法各100次，然后计算相应的平均对极距离和标准差。图4展示了各方法在场景1～场景6中的实验结果。

Figure 4 Comparison of the average epipolar distance and their standard deviations in 6 typical scenes图4 6个典型场景中各方法的平均 对极距离及其标准差的对比

就整体表现对不同方法进行横向对比，本文方法在平均对极距离方面与MSAC和RANSAC相当，且明显优于LMedS;在标准差方面与LMedS和RANSAC相当，且优于MSAC。就应用于不同场景中的纵向对比可知，本文方法在特征点数多的场景下仍表现出较好的准确性。

4.3 效率对比及分析

除准确性以外，还可从运行效率方面对本文方法进行评价。将对比实验中各方法的平均运行时间记录下来，如图5所示。由图5可见，本文方法的运行效率比其他方法都要好。随求解问题规模(即特征点对数目)的增大，本文方法的运行时间略微有所增加，但整体上保持平稳。

Figure 5 Average time consumption of each method applying to 6 typical scenes图5 6个典型场景中的各方法平均运行时间对比

5 结束语

本文提出了一种改进拟仿射变换的基础矩阵估计方法，结合粒子群的寻优能力和QUATRE算法解决组合问题的优势来估计基础矩阵。首先，提出一种基于特定“基因-染色体”模式的种群协作方法，用于基础矩阵估算。其次，重新定义齐次坐标系所表示的离散解空间中的种群初始化、变异和交叉等操作，使得利用QUATRE 算法框架解决基础矩阵估算问题成为可能。此外，提出一种基于置信度的迭代次数确定方式，用于加速本文方法。与传统方法相比，本文方法能有效剔除噪声和误匹配所产生的外点干扰，具有快速寻优求解等优势。实验结果表明，本文方法在准确性和效率方面都优于LMedS、RANSAC和MSAC等基础矩阵估计方法。后续工作将对种群演化中的变异和交叉策略作进一步的优化，以进一步提升算法的效率和准确性。