基于改进RANSAC算法的道路直线提取方法

吴剑亮，李 艳，高 扬，黄小赛

（1.南京大学 国际地球系统科学研究所， 江苏 南京 210023；2.江苏省地理信息技术重点实验室，江苏 南京 210023）

基于改进RANSAC算法的道路直线提取方法

吴剑亮1,2，李 艳1,2，高 扬1，黄小赛1

（1.南京大学 国际地球系统科学研究所， 江苏 南京 210023；2.江苏省地理信息技术重点实验室，江苏 南京 210023）

直线检测是计算机视觉领域的一项重要内容，也是遥感影像信息提取的基本过程。随机抽样一致性算法（RANSAC）常用来进行包括直线在内的目标提取，是在计算机视觉领域应用较广泛的估计算法之一，但其计算效率较低。因此提出了一种基于序贯概率的改进型多目标RANSAC算法，在利用边缘检测限定随机抽样原始样本集的基础上，运用该算法提取了高分辨率航空影像数据中的道路边界线，大大提升了计算效率。

RANSAC算法；直线检测；边缘检测

直线检测是计算机视觉领域的一项重要内容，是图像分割的基础，在多目标跟踪、人脸识别和车道线提取等方面有着广泛的应用[1]。现有的直线检测算法主要分为两大类：一类是通过图像预处理得到目标边界点的集合，然后再结合直线识别的基本方法提取目标边界上的直线；另一类是通过图像预处理直接得到图像边界线的集合，然后在该集合中进行直线检测[2]，本文采用第一类方法。传统的霍夫（Hough）变换是一 种参数化的对象检测方法[3]，是一种根据投票机制检测特定形状的算法。在空间A中具有相同特征的曲线或直线可通过Hough变换映射到空间B中的一点，从而形成峰值，即把检测形状问题转换为统计峰值问题。虽然传统的Hough变换不受直线间断等缺陷的影响，但其对于在高噪声环境下的检测结果不佳。RANSAC算法由Fisheler和Bolles提出[4]，作为一种普遍的鲁棒性模型参数估计方法，其对于含有错误数据50%的样本集依然具有很强的鲁棒性[5]，因此它在计算机视觉领域应用广泛，如图像匹配、拼接等。本文以高分辨率航空影像数据为数据源，选取日本东京地区作为研究区，在序贯概率和多次迭代算法的基础上提升了RANSAC算法的效率，并将其运用于提取东京地区平直道路的边界线。结果表明，在高噪声环境下，提升效率后的RANSAC算法具有很好的多直线检测结果。

1 RANSAC算法

1.1 RANSAC算法的基本思想

传统的数据拟合技术是先使用尽可能多的数据得到初始解，再消除无效的数据点；而RANSAC算法与传统的数据拟合技术不同，是选择少而有效的初始数据集，然后在一定容差范围内尽可能地扩大这一初始数据集[6]。

一般而言，假设一组数据集中包含适应于观测数据的参数化模型，在总体样本中抽样选择一组最小子集（直线为2），得到符合该子集的参数化模型M，预先设定误差阈值t。若在阈值t的范围内，初始数据集中存在符合模型M的元素，则把该元素归入子集；然后统计子集内元素的个数n即局内点数，用它们反演模型参数M*。经K次重复试验之后，得到满足一定条件的参数化模型M。

当置信概率为P时，假设估计模型需选定n个局内点[7]，θ为这n个数据点符合该模型的概率，根据概率理论，K和n之间关系满足：

式中，θ= n/N；N为全部数据点数。

RANSAC算法过程为：

1）在指定置信概率P（一般设置为0.99）的情况下，根据局内点数的比例θ，由式（1）确定试验次数K。

2）随机抽样计算模型参数，用全部数据点检验模型参数，得到该模型的局内点数n'。

3）以局内点数最多或点数相同时局内点对模型的误差方差最小为原则选择最优模型。

4）用最优模型对应的n'个局内点重新估算最终模型参数。

在足够多的试验次数条件下，该算法一定能找到最优模型。如图1所示，黑色圆点表示含有噪声的一 组二维点集，在该点集中，噪声点达到40%以上；蓝色圆点表示两个随机抽样点；蓝色直线表示由它们确定的直线模型；红色圆点表示局内点。通过拟合技术得到最终的直线模型如图2中红色直线所示。

图1 RANSAC算法第一次抽样图

1.2 RANSAC算法优化

确定RANSAC算法时间复杂度的公式为：

式中， TM为每次随机抽样的时间；为抽样样本中每个数据点验证该模型的平均时间；N为抽样样本中数据点个数；K为迭代次数。通常TM和对一个特定问题而言可认为是不变的，所以RANSAC算法的时间复杂度由K和N决定。

由式（2）可知，样本模型越复杂，θ随之越小，在保证置信概率P的前提下，就必须提高迭代次数K，算法的时间复杂度也随之升高。

通过上述分析，对RANSAC算法进行了3个方面的优化，使其能够更加快速和准确地提取多直线：

1）在选取数据子集时，可给予一定的条件约束，而非完全随机抽样。例如，对于图像而言，可利用边缘检测并结合直方图信息，缩小子集的选取范围。本文提取对象为平直道路的边界线，与周围背景具有一定灰度差异，可利用Canny算子进行边缘检测的预处理。

2）在数据集随机采样子集并估计子集的模型后，采用序贯概率检测技术[8-9]进行预检验优化，随机选取数据集中部分而非全部点来检验模型的正确性。若模型在早期被拒绝，则进行重新估计和检验；若模型被最终接受，则把剩余的点代入模型进行全部检验。由于大部分模型受错误点影响，所以可较快速地过滤掉大多数错误模型，提高算法速率。

3）为了检测多直线，在一次检测后标记出符合此次检测最佳模型的数据，然后把这些数据从总体样本中去除，再进行下次检验，如此循环直到总体数据中没有满足最佳模型条件的数据子集。

1.3 改进RANSAC算法步骤

根据算法分析和优化方案，结合RANSAC算法的基本步骤，对高分辨率航空影像数据中的平直道路边界线进行了多直线提取，主要步骤为：

1）预设参数：序贯检测局内点数阈值为N1，最少提取点数阈值为N2（直线提取停止条件之一），误差阈值为D，试验次数阈值为T，当前步数s=0。

2）利用Canny算子对原始图像边缘进行提取。3）数据随机抽样并计算模型参数及局内点数n'i。4）s=s+1；进行序贯检测，若n'i＞N1，则模型通过预检验，进入下一步，否则返回步骤3）进行重抽样。

5）把剩余点逐个代入模型进行误差检验，并由此更新局内点数n'i。

6）若n'i＞N2，比较n'i与上一次迭代的局内点数n'i-1：选择局内点数较多的模型为较优模型，n'i=max{n'i, n'i-1}；若n'i=n'i-1，则选择方差较小的模型为较优模型，n'i=maxvar{n'k|Vark,k=i,i-1}，i=i+1，进入下一步；否则返回步骤3）。

7）若当前步数s＞T，则停止；否则输出一个模型，返回步骤3）。

8）利用最优模型对应的n'个局内点重新估算最终模型参数。

2 直线检测结果及分析

如图3所示，本文以东京地区为研究区，运用Canny算子对该区域进行边缘检测，最终通过二值化等预处理操作，生成一系列数据点，即图4中的白色像素点。

图3 东京高分辨率航空遥感影像数据

通过Canny边缘检测图可以看到有很多噪声数据干扰，同时在公路边界和高架铁轨两侧具有明显的直线特征。设局内点的最少个数为800，误差阈值为3，迭代次数为150，运用改进RANSAC算法进行多直线提取。该算法基于Python3.1环境和Opencv图像处理库实现，得到满足条件的多条直线模型的局内点分布，如图4所示。把局内点分别叠加到原始图像，得到最终的多直线检测效果图。由图5可知，改进RANSAC算法从大量数据点中准确有效地提取了多直线，且无论直线是否间断都具有很好的效果。

图4 局内点分布图

图5 多直线检测结果图

因此，改进RANSAC算法需要确定的参数有：局内点的最少个数和误差阈值。下面介绍多直线检测参数的设定方法。

由表1可知，若最少局内点数N2设置过大，则最终检测直线的条数并不会增加，如实验1～4；若设置过小，则会检测出过多的直线，如实验7～9。因此，在样本数据较大的情况下，最少局内点数应设置为总体样本点数的2%～3%。误差阈值决定了数据是否适用于模型，本文利用点到直线的欧氏距离衡量点适用于直线模型的尺度，将误差阈值设置为2个像素单位。通过表2可知，改进RANSAC算法的平均计算效率比原始方法有所提高，运行时间相应缩短。

表1 区域参数和检测直线条数的关系

表2 时间效率比较表

3 结 语

本文提出了一种改进RANSAC算法，通过对数据的预处理缩小样本集合，再进行多目标提取。通过对高分辨率航空影像数据中的平直道路边界线多直线提取的实验表明，通过序贯检验缩短了约1/4的验证模型计算时间，对连续多直线的提取具有较好的实验效果。本文探讨了参数对算法最终结果的影响，其中若干参数的设置原则是试验性的，在今后的研究中将根据参数与数据的关系，在理论上给出合理的设置原则。

[1] 曲天伟,安波,陈桂兰.改进的RANSAC算法在图像配准中的应用[J].计算机应用,2010,30(7)：1 849-1 851

[2] 孙涵,任明武,杨静宇.一种快速实用的直线检测算法[J].计算机应用研究,2006,23(2)：256-257[3] CHUNG KL，CHANG T C，HUANG Y H，Comment on：“Extended Hough Transform for Linear Feature Detection”[J]. Pattern Recognition,2009,42(7)：1 612-1 614

[4] Chum O,Matan J,Kitfler J.Locally Optimized RANSAC[A]// In：Michaelis B,Krell G.Eds：Proceedings of the 25th DAGM Symposium[C].Berlin,Germany：Springer-Verlag,2003：236-243

[5] 高洪智,卢启鹏,丁海泉,等.基于随机抽样一致性算法的近红外光谱稳健模型研究[J].光学学报,2013,33(B12)：220-224

[6] 袁清珂,张振亚,毕庆.改进RANSAC算法在直线拟合中的应用[J].组合机床与自动化加工技术,2015(1)：123-125

[7] 陈付幸,王润生.基于预检验的快速随机抽样一致性算法[J].软件学报,2005,16(8)：1 431-1 437

[8] 周骏,陈雷霆, 刘启和,等.基于序贯概率及局部优化随机抽样一致性算法[J].仪器仪表学报,2012,33(9)：2 037-2 044 [9] 张红民,曾祯.一种改进的相邻概率随机抽样一致性算法[J].激光杂志,2013(5)：29-30

P237

B

1672-4623（2017）05-0042-03

10.3969/j.issn.1672-4623.2017.0051.3

吴剑亮，硕士研究生，研究方向为遥感图像处理与信息提取。

2016-06-13。

项目来源：国家自然科学基金资助项目（41371331）。