基于RANSAC 的道路影像控制点选取方法研究

方林波，石昊苏，路雅宁，武鹏辉

（西北政法大学 商学院，陕西西安 710122）

近年来，随着计算机处理速度的快速提升，基于多传感器融合的移动近景摄影快速测量新技术得到了迅速发展[1-2]。一个典型的近景移动测量系统是将IMU、CCD 和GPS 3 种类型的传感器集成在一起，如在移动载体上，用IMU 和GPS 两种传感器对移动载体进行组合定位，同时，对CCD 拍摄获取的立体影像进行处理，最后基于前方交会计算出立体影像中地物的坐标位置[3-7]。从以上过程可以看出，自主定位问题是移动测量的一个基本问题，在GPS 信号受到干扰（或遮挡）的情况下，由于漂移等造成的误差逐渐积累增加，仅仅依靠IMU 进行独立定位，无法获得所需要的精度。为解决这一问题，数字可量测影像（Digital Measurable Image，DMI）技术被引入到自主定位中，基于DMI 的坐标信息、基于后方交会计算出移动载体的位置坐标，并将其与GPS、IMU 结合，形成DMI/IMU/GPS 组合定位系统[8-10]，其优点是把多种技术结合起来，使各子系统的优势互补，最终提高定位的精度和稳定性。在影像匹配方面，这些研究均采用SIFT 算法对影像进行特征点的提取，但没有对大量的特征点进行有效的分析和筛选，并提取控制点。控制点是影像中不受光照、形变和角度等变化影响的特征点，具有稳定、准确和分布均匀等特征。控制点的提取是影像匹配、图像拼接、以及利用道路立体影像进行车辆定位的前提。在影像匹配方面通常采用SIFT 算法对影像进行特征点的提取，针对该算法的改进和扩展一直是研究热点[11-13]。

道路立体影像中地物平面层次多、背景复杂，控制点往往隐没在背景噪音中，直接用SIFT 算法获取的特征点多数是背景产生的，可靠性和均匀性较差，必须通过特定的方法将其中稳定、准确、分布均匀的控制点筛选出来，才能使下一步的移动测量、定位导航高效准确。

文中针对道路立体影像的SIFT 特征，提出了基于RANSAC 和均匀度理论相结合的控制点筛选方法，该方法保证了特征点选取的均匀、准确。实验表明，该方法能够从道路立体影像中提取出稳定、准确、分布均匀的控制点，为后续的定位导航奠定基础。

1 相关理论

1.1 SIFT算法

在图像匹配的众多算法中，SIFT 算法具有良好的尺度和空间旋转的不变性，得到了广泛的应用，该算法提取特征分为以下4 步[14-15]：

1）尺度空间极值检测。该步骤的主要任务是得到多尺度图像序列，如式（1）所示。

其中，σ为尺度因子，G为σ的高斯核，I为原图像，L为I在尺度σ下的空间表示。

在式（1）的基础上建立DOG 金字塔，如式（2）所示。

DOG 金字塔中每个像素均与相邻以及上、下邻层的26 个邻域像素进行比较，如果是极值点，则该点为候选的特征点，并记录该点的位置与尺度。

2）精确确定关键点。主要任务是确定关键点的参数，并将不稳定的边缘响应点筛选掉。

3）确定特征点的梯度模值和方向。应用公式（3）、（4）计算出特征点(x,y)处的梯度模值m(x,y)和方向θ(x,y)值。

每个特征点具有3 个方面的属性值，分别为所在的位置、尺度和方向。

4）生成SIFT 特征描述子为了增强特征点的稳健性，每个特征点用相邻的种子点描述，即每个特征点用4×4×8=128 维的向量描述。

1.2 RANSAC算法

即使经过多重筛选，两幅影像间的SIFT 特征点匹配的结果中还会有许多的错误匹配对，需要进一步优化。随机抽样一致性估计算法（Random Sample Consensus，RANSAC）可以进行较为鲁棒的优化[16]。RANSAC 的主要特点随着迭代次数的增加模型的参数正确概率会相应提高。

1.3 均匀度理论

定义1 独占球：对n维欧氏空间的至多可数的有限点集s，对于任意x∈s，记M(x)=min(d(x,y))，y∈s，y≠x，则 存 在x1∈s使 得M(x)=d(x,x1)，记 紧 邻MP(x)=x1，M(x)为紧邻距离。其中d(·)是欧氏距离。把x作为球的中心，M(x)/2 为球的半径的闭球，B(x)称为x的独占球，其体积记为v(x)。B(x)的外切闭立方体的数量很多，但体积相等，记其一为CU(x)，称为x的独占体，体积记为vc(x)。

引理1 在一定的边界内点集中，所有点的独占球互不重叠，而且这些独占球最近的空间关系是相切的。

定义2 均匀度：设pt:S⊂A⊂Rn为一个格局。独占球的总体积为为多面体A的体积，称为格局S的均匀度。

2 维的均匀度定义：长方形内所有点的总独占圆面积与长方形总面积的π 4 倍之比称为格局均匀度。把点的总独占圆面积记为a，长方形面积记为A，则格局均匀度的值为。

2 基于RANSAC和均匀度理论的立体影像控制点筛选

文中方法包括4 个主要步骤：1）SIFT 特征点提取；2）基于区域均匀度的特征点初步筛选；3）立体像对特征点匹配；4）基于RANSAC 和均匀度的特征点筛选。

2.1 SIFT特征点提取

道路立体影像平面层次多、背景复杂，而且受天气、光线影响较大，获得稳定、准确、分布均匀而且尽量多的特征点是道路立体影像进一步研究和应用的前提和难点。SIFT 特征点对图像各种变化具有较强的稳定性，相对边缘、角点、形状等特征，更适合道路立体影像。

2.2 基于区域均匀度的特征点初步筛选

区域均匀度是影像中某一特定区域的均匀度。用a(x,y)表示影像的某一个SIFT 特征点的坐标，t为设定的均匀度阈值。特征点初步筛选的步骤如下：

1）把a(x,y)作为中心，距其上、下、左、右各20 像素为边长，形成一个正方形；

2）对该正方形中所包含的SIFT 特征点计算均匀度；

3）当均匀度小于t时，除去该正方形中梯度峰值最小的特征点；

4）重复2）和3）直到该正方形内均匀度大于或等于t。

文中实验中t设为0.28。

通过以上步骤，大量SIFT 特征点中满足设定均匀度、大梯度峰值的特征点被筛选了出来。

2.3 立体像对特征点匹配

对立体影像进行SIFT 特征点提取和初步筛选后，需要对像对中的左图和右图进行特征点匹配，以查找像对中的同名像点。取出左图的一个SIFT 特征点，基于K-D 树搜索策略，在右图SIFT 特征点中找出最近邻（NN）特征点和次近邻（SCN）特征点。计算NN 距离和SCN 距离的比值，当该比值小于设定的阈值时，接受这一对匹配点，阈值越低，SIFT 匹配点越少，匹配越稳定。但稳定的代价是损失掉大量有效的特征点，所以该阈值取值较为关键。根据查阅文献和实验，该阈值取在[0.6,0.7]区间最为合适。

2.4 基于RANSAC和均匀度的特征点筛选

基于RANSAC 算法的SIFT 特征点筛选方法在图像拼接、图像配准等方面应用广泛。由于RANSAC 主要依靠符合模型的匹配点数量的大小为评判条件，而忽略了这些匹配点的分布情况，所以只适合于特征点分布较为均匀的图像，对于特征点分布不均匀的图像，不但不能提高其筛选结果的均匀度，甚至会把一些非常重要但分布较为离散的特征点除去，降低了筛选的质量。道路立体影像平面层次多、特征点分布不均匀，直接使用RANSAC 进行筛选效果差。

文中将均匀度理论引入RANSAC 中，将符合模型的匹配点数量与该点集均匀度的乘积作为评判标准，使得RANSAC 对特征点的筛选既满足几何一致性，又满足特征点的均匀性。基本步骤如下：

1）利用2、3 节中介绍的方法对像对进行特征点匹配，得到的匹配点数量设为M，根据公式N=log(1-pn)/log[1-(1-a)m]确定随机采样次数N，其中，pn=0.95，m=4，a为数据错误率；

2）利用随机选取的4 对匹配点计算初始单应矩阵；

3）设置约束条件，满足者为内点，不满足者为外点。约束条件设置方法为：把左图中的匹配点通过单应矩阵进行变换，对变换后的匹配点与右图对应的匹配点进行欧式距离计算，此欧式距离d即为约束条件，d＞4 的点为外点，d≤4 的点为内点；

4）计算内点集的均匀度L，记内点数量c与均匀度乘积R=cL，如果R大于等于设定阈值时，用内点数重新估计单应矩阵，结束本轮运算；如果R小于阈值，则重新在数据集中选取数据样本，重复2）、3）、4）三步；

5）经过N次迭代，得到N个内点集，选取R值最大的内点集，算法结束。

3 实验结果分析

文中采用的道路立体影像大小为1 392×1 040像素，在野外道路、乡村道路和城市道路3 个场景下进行实验，首先对立体像对进行SIFT 特征提取，然后对文中算法和传统的RANSAC 算法的筛选结果进行比较。

图1 像对的SIFT特征点检测

图1 是野外道路立体影像的SIFT 特征点提取图，图1（a）、（b）分别为像对中的左图和右图，包含的特征点数分别为308 和508。

图2 是该像对的SIFT 特征点进行区域均匀化后的特征图，像对的左图和右图分别得到144 和235 个特征点。对比图1 和图2 可以看出：经过区域均匀化，扎堆的特征点得到了有效抑制，特征点的分布更加均匀。

图2 区域均匀化后的SIFT特征点

图3 是对野外道路立体影像进行特征点匹配和匹配点筛选的4 个实验结果。图3（a）是对SIFT 特征点进行直接匹配的结果，匹配点数为79；图3（b）是对SIFT 特征点进行区域均匀化后进行匹配的结果，匹配点数为48；图3（c）是对图3（a）匹配点利用RANSAC算法进行筛选的结果，匹配点数为17；图3（d）是对图3（b）匹配点利用文中方法（2.4 节）进行筛选的结果，匹配点数为15。可以看出，图3（c）中的匹配点都集中到了两个区域，均匀度较差；图3（d）中匹配点均匀度分布有明显的改善。

图4 是对乡村道路立体影像进行特征点匹配和匹配点筛选的4 个实验结果。图4（a）是对SIFT 特征点进行直接匹配的结果，匹配点数为204；图4（b）是对SIFT 特征点进行区域均匀化后进行匹配的结果，匹配 点数为82；图4（c）是对图4（a）匹配点利用RANSAC 算法进行筛选的结果，匹配点数为64；图4（d）是对图4（b）匹配点利用文中方法（2.4 节）进行筛选的结果，匹配点数为35。可以看出，图4（c）中的匹配点过于扎堆，均匀度较差；图4（d）中匹配点均匀度分布有明显改善。

图5 是对城市道路立体影像进行特征点匹配和匹配点筛选的4 个实验结果。图5（a）是对SIFT 特征点进行直接匹配的结果，匹配点数为236；图5（b）是对SIFT 特征点进行区域均匀化后进行匹配的结果，匹配点 数 为97；图5（c）是 对图5（a）匹 配点利用RANSAC 算法进行筛选的结果，匹配点数为52；图5（d）是对图5（b）匹配点利用文中方法（2.4 节）进行筛选的结果，匹配点数为42。可以看出，图5（c）中的匹配点过于集中，均匀度较差；图5（d）中匹配点均匀度分布有明显的改善。

图3 野外道路像对匹配点筛选对比

图6 是传统方法与文中方法在3 种典型场景（野外道路、乡村道路、城市道路）的筛选结果对比图，可以看出：

1）对于3 种类型的图像，在经过区域均匀化后，匹配点数量均大幅减少，匹配正确率优于传统方法。

2）文中方法筛选出的匹配点分布的均匀度大大提升。

综上所述，文中方法相对传统方法是一种更有效的道路立体影像特征点提取和筛选的方法。

4 结束语

图4 乡村道路像对匹配点筛选对比

图5 城市道路像对匹配点筛选对比

基于DMI 的车辆定位导航技术是移动测量领域的前沿和趋势，其中，立体影像控制点的筛选是难点和关键，控制点必须是准确、稳定的特征点，而且分布尽量均匀。目前，立体影像控制点筛选技术还未见报道。文中结合SIFT 算法、RANSAC 算法和均匀度理论，将均匀度理论引入RANSAC-SIFT 过程中，提出了一套道路立体影像控制点筛选方法。实验结果表明，该方法能够获取准确、稳定、分布均匀的控制点，为立体影像匹配、控制点运动轨迹的Kalman估算、以及车辆自主定位导航的研究奠定基础。

图6 两种方法的控制点筛选结果对比