改进RANSAC算法在直线拟合中的应用*

袁清珂，张振亚，毕 庆

（广东工业大学机电工程学院，广州 510006）

改进RANSAC算法在直线拟合中的应用*

袁清珂，张振亚，毕 庆

（广东工业大学机电工程学院，广州 510006）

以平板电脑LCD屏幕的边角直线为研究对象，对其进行边缘直线拟合，利用加入预检验的改进RANSAC算法排除大量数据异点，并实现对LCD屏幕边角图像进行边缘点的提取和直线拟合，通过编程实验证明改进后的RANSAC算法对直线拟合的效率和精度都有所提高。实验结果表明：利用改进的RANSAC算法对边缘直线拟合的效率提升10%以上，且样本点数越多，效率提升越明显。

随机抽样一致性；直线拟合；数据异点；预检验

0 引言

在工业自动化生产中，直线边缘是零件最常见的外观轮廓特征，图像中的边缘点不完全处于同一条直线上，采集的图像也会受到环境的干扰，使图像处理的判断结果出现差错。过去工业视觉检测中通常需要对图像进行预处理改善效果，例如空间滤波、阈值分割、形态学等，但常用的图像处理算法的效率达不到自动化设备的要求，所以在工业视觉系统中对采集的图像直接进行特征提取是最常见的处理方法［1］。

本文以平板电脑的LCD屏幕组件边角图像为例，在RANSAC算法的基础上，对图像进行边缘特征点的直线拟合，通过分析算法运行时间对其提出改进方向，最后利用软件编程实现算法在直线拟合中的应用效率的验证，如图1中包含的目标特征是平板电脑LCD右下角的两条直角边。

图1 LCD屏幕组件右下边框边缘图

1 RANSAC算法

RANSAC算法（RANdom SAmple Consensus，随机抽样一致性）是由Fischler和Bolles在1981年最先提出，这种算法对于含有错误数据50%的样本集，仍然能够有效处理，它是最具鲁棒性的算法之一［2］。

1.1 RANSAC算法的基本思想

利用迭代的方法不断从模型中随机抽取样本集，寻求包含更多支持内点、更优的模型参数，再用模型的余集来检验抽取出的样本，通过一定次数的迭代，最后当选取出的样本集接近合理解的概率为最大时，即将其当做最接近合理解的样本集，最后用样本余集来支撑得到的参数解的正确性［3］。

1.2 RANSAC算法的参数确定

根据RANSAC算法的基本思想可设总体模型为M，最小抽样集P的样本数为n，预先设定容忍阈值t，当余集中的元素在容忍阈值范围内，则将其算作一致集S*内的元素，通过一定次数的迭代，最后计算一致集内的元素个数（即一致集大小）来判断抽样集P是否为模型M的最合理解。

通过上述分析可见，抽样过程中所需确定的参数有：

（1）误差容忍阈值t，用来判断样本是否为满足模型的正确解；

（2）迭代次数，即随机抽取样本集的次数；

（3）表征正确模型的一致集的大小N［4］。

2 基于预检验的RANSAC改进算法

2.1 RANSAC算法的效率分析

在RANSAC算法计算过程中，需要选取足够多的抽样数量M，才能保证在一定的置信概率P条件下，抽取的样本中至少有一组抽样数据全部是内点。抽样集数量M与置信概率P、数据错误率ε和计算模型参数必要的最小数据量m之间为指数关系，可由下式表示：

当总体样本模型变得复杂，且数据的错误率相对较高时，抽样集的数量 M将不断变大，这直接使RANSAC算法计算量大大增加，造成算法的计算效率下降，这样就需要考虑采取某种方法去加速RANSAC算法的效率［5］。

分析RANSAC算法的计算时间，首先假设在原始总体样本中随机采样的时间为Ts，随机抽取的样本对总体样本进行参数计算的时间为Tc，一个抽样集对模型参数的检验平均时间为t，再用n表示检验样本的支持点的数量，抽取样本集的数量为M。这样就有RANSAC算法计算时间为：

其中第一项表示抽取M个样本并计算模型参数所需的时间，第二项表示M个模型参与总体模型参数的检验时间［6］。

2.2 RANSAC算法的改进方向

通过分析RANSAC算法的计算时间，可向着以下两个方向对算法进行优化：

（1）在对LCD边缘点样本子集S的选取时，可以根据特定的约束条件进行随机选取，而非完全的随机抽样；

（2）当通过样本子集S估计出总体模型M后，可以只利用剩余点中的一部分而不是全部点来检验模型M的正确性，可设定一个阈值D，若通过剩余点检验得到的模型M正确的点数小于D，则直接舍弃此模型，反之则对所有的剩余点进行检验。

2.3 改进的RANSAC算法步骤

针对样本抽取的方法，可用如下方式进行：对于含有n个元素的点组，从中随机抽取一个点，与点组最后一个点调换位置，再从前n-1个点中随机抽取一个点与倒数第二个点调换位置，以此类推打乱点组，再进行随机抽样。

在样本抽取方法的基础上，改进RANSAC算法的步骤为：

（1）利用式（1）确定置信概率P和预估数据错误率ε，计算抽样的数量M；

（2）考虑每次随机抽取点的个数增加一到两个，利用抽取得到点中的两个来拟合出一条直线；

（3）再计算另外两个点到这条直线的距离，如果距离在误差容忍阈值D范围内，则令这条直线为候选直线；如果不在范围内，则直接放弃这条直线重复第（2）步。

（4）计算该样本对应的直线模型参数；

（5）用全体点检验计算出来的直线参数，获取内点数量；重复（2）（3）（4）步直到抽样M次；

（6）根据内点数量来选择最优直线。

这种方法利用样本本身对整体模型做了预检验，而且由于异点在预检验过程中大部分被过滤掉，所以总的要检验的模型参数是减少的。

假设进行M次样本选择，用Pf表示未被快速抛弃的样本的通过概率，用Nf表示参与预检验的点数。结合式（1）可知，模型是正确模型的概率为（1-ε）mPf，则有改进后的算法计算时间为：

实际上当Pf概率一定时，抽样子集越大，节省的时间越多［7］。

3 改进算法的直线拟合实验

针对LCD边缘图像，建立实验通用条件：预检验样本数Nf=4；预检验通过率Pf≥0.8；计算模型参数需要的最小数据点m=2；置信概率P=0.98。在对数据错误率进行估算的条件下，通过实验对RANSAC算法与改进的RANSAC算法的直线拟合精度和效率做了比对。

实验效果如图2～图4所示，分别设采集到的样本点总数为100、300、500个，在实验中假设数据错误率ε=0.30，图中左边为用基本的RANSAC算法实现的直线拟合效果，右边为用改进的RANSAC算法实现的直线拟合效果。

图2 100个样本点

图3 300个样本点

图4 500个样本点

表1 RANSAC算法改进前后拟合直线的精度分析

表1中数据均是经过30次直线拟合得到的数据平均值。通过实验图片以及表1中数据可以观察到，RANSAC算法与改进的RANSAC算法拟合得到的直线角度与截距相差无几，这说明改进的RANSAC算法仍然保持了其相对较高的精度，对于数据异点的滤出效果很明显。

表2 RANSAC算法与改进后的速率比较

表2中分别给出了RANSAC算法与改进后的RANSAC算法在样本点数分别是100、300和500情况下的运算速度，表中算法运算时间均是进行30次所用时间的平均值。

4 结论

（1）在加入预检验的改进RANSAC算法基础上，实现对错误数据较多的边缘点的直线拟合，算法改进前后，直线拟合精度并未降低，但提高边缘直线拟合效率，节省算法处理时间。

（2）实验得出当样本点总体增大后，改进后的RANSAC算法效率提升了10%以上，且样本总体越大，效率提升幅度越大。

（3）对于基于视觉的工业自动化生产装备而言，设备的每个工作循环可能需要对图像多次直线拟合处理，所以虽然每次处理过程提升的时间并不多，但工业现场环境下设备需要连续运转，所以从长期利益来看，提升的效率依然是可观的。

［1］周波，杨剑，王东平.基于随机采样一致性算法的平面匹配方法［J］.计算机应用，2011，31（4）：1053-1056.

［2］Chum O，Matan J，Kitfler J.Locally Optimized RANSAC［A］. In：Michaelis B Krell.Eds：Proceedings of the25th DAGM Symposium［C］，Berlin，Germany：Springer-Verlag，2003：236-243.

［3］Chum O.，Matas J.Randomized RANSAC with T（d，d）Test［J］.In Proceedings of the British Machine Vision Conference，2002，V2：448-457.

［4］陈付幸，王润生.基于预检验的快速随机抽样一致性算法［J］.软件学报.2005，16（8）：1431-1438.

［5］Capel D P.An Effective Bail-out Test for RANSAC Consensus Scoring［A］.In Clocksin W，Fitzgibbon A，Tort P.eds：Proceedings of Conference on British Machine Vision［C］，Oxford，England：British Machine Visio Association.2005：629-638.

［6］陈付幸，王润生.一种新的消失点检测算法［J］.电子与信息学报，2006，28（8）：1458-1462.

［7］孙强，叶玉堂，宋昀岑，等.基于优化RANSAC算法的二次元快速稳定匹配［J］.计算机工程与设计.2012，33（6）：2373-2377.

（编辑 李秀敏）

Linear Fitting Application Based on the Improved RANSAC Algorithm

YUAN Qing-ke，ZHANG Zhen-ya，BI Qing
（Department of Mechanical and Electronic Engineering，Guangdong University of Technology，Guangzhou 510006，China）

Regard the LCD screen edge horn of the tablets as the research objects.Linear fitting using RANSAC algorithm.Rule out a large number of error data points using the precheck inspection improved RANSAC algorithm.Then realize the LCD screen edge extraction and linear fitting.Programming in the software and through the experiment of linear fitting，the improved RANSAC algorithm has the higher precision and efficiency.Test results show that the efficiency promotion is beyond 10%and the total number of samples bigger，the efficiency promotion higher.

RANSAC；linear fitting；error data points；precheck

TH162；TG82

A

1001-2265（2015）01-0123-03 DOI：10.13462/j.cnki.mmtamt.2015.01.034

2014-05-08

广东省产学研专项（2009B090300340、2011B090400119、2010B090400079、2012B091000033）；广东省数控一代专项（2012B011300009、2012B011300049）；广东省战略性新兴产业LED专项（2012A080303002）；广东省学位与研究生教育改革研究项目（09JGXM-ZD10）

袁清珂（1963—），男，山东青岛人，广东工业大学教授，研究方向为机电一体化与机电控制、知识工程与智能设计、多体动力学与计算机仿真、企业信息化；通讯作者：张振亚（1988—）男，河北保定人，广东工业大学硕士研究生，研究方向为机器视觉、机电系统设计，（E-mail）zhenyazhang3668@gmail.com。