基于IRANSAC-IRLS 直线拟合算法及应用

罗金鐄，胡小平，彭向前，黄泓

（湖南科技大学 机电工程学院，湘潭 411201）

直线边缘是工业生产零件中最常见的轮廓特征[1]，它包含了最基本的几何信息和拓扑信息。在对工业生产的零件图像进行处理的过程中[2]，往往需要对直线边缘进行拟合或定位，但是由于零件表面存在脏污，或者加工工艺的问题，使得直线边缘存在沾连、毛刺等噪声，导致直线上的边缘点会偏离直线，对图像处理的结果产生较大地影响。因此，研究在噪声较多的情况下，快速而准确地拟合出直线边缘是非常有意义的[3]。

在直线拟合方面的研究中，国内外学者已经取得了不少研究成果。文献[4]提出将霍夫变换[5]和梯度下降结合的方法拟合边缘直线，但是该方法对线性噪声敏感，容易出现误判，而且拟合精度不高；传统最小二乘法（least-squares line fitting，LS）拟合速度很快，但其容易受到噪声点的干扰，在噪声点多于10%的情况下就不能精确的拟合出直线的参数；文献[6]提出迭代重加权最小二乘直线拟合算法，该算法在噪声点少时能够得到很高的拟合精度，但是在噪声点较多，导致初始拟合偏差较大的情况下，不能拟合出高精度的直线边缘。以上算法在噪声点多的情况下，都不能拟合出准确的直线。

为解决噪声点对拟合精度的影响，文献[7]提出随机抽样一致性算法，它具有优良的鲁棒性，能够通过迭代在含有70%噪声点的点集中寻找出最优模型，但其最终的拟合精度依赖于额外的拟合算法，而且算法的耗时会随着噪声点的增加呈指数增长[8]；文献[9]为了提高RANSAC 算法的运行速度，提出一种基于预检验的抽样一致性算法，总的来说确实能提高算法的运行速度，但是在其随机的子集选取过程中，可能会将正确的模型误判成错误的模型，在噪声多时，可能会陷入无限次的抽样与检验的过程中。综上所述，如何在含有大量噪声点的点集中快速而准确地拟合出直线的参数是十分重要的。

针对直线边缘存在大量噪声点的情况下，RANSAC算法效率低、精度不高的问题，提出IRANSAC-IRLS算法。首先，通过Canny 算子提取出直线的边缘；然后，利用直线上的边缘点的梯度方向相近，将梯度方向引入边缘点RANSAC 拟合，降低错误的随机抽取次数，筛选出拟合时的部分噪声点；最后，对IRANSAC 提取出来的局内点进行迭代加权最小二乘拟合，降低数据本身的误差对拟合的影响，提高拟合的精度。仿真实验和实际产品实验证明该算法具有良好的时效性和鲁棒性。

1 直线边缘提取

在进行拟合之前，都需要获取直线的边缘点集，微分算子是图像处理的各种边缘检测方法中最常用的方法，Canny 算子[10]具有良好的边缘检测效果，该方法通过建立梯度幅值图，利用高低两个阈值来提取图像中的边缘，考虑了梯度幅值与梯度方向之间的关系，抗干扰能力最强，对于图像中的弱纹理也具有良好的检测效果，本文通过Canny 算法提取出直线边缘，其算法步骤如下：

（1）用高斯函数对图像进行滤波，作平滑运算，然后对图像进行卷积处理，得到该点x 方向上的梯度值Fx，该点y 方向上的梯度值Fy。

该点的梯度幅值F：

该点梯度方向θ：

（2）通过高低阈值来判断点是否为边缘，对图像中的弱纹理是通过判断该点的梯度幅值是不是梯度方向上的局部最大值，保证了该算法良好的弱纹理检测效果。

2 RANSAC 算法

2.1 RANSAC 算法基本思想

RANSAC 是一种从模型数据中随机抽取满足模型的最小样本数来估计样本的数学模型的方法，其利用模型的余集对随机抽取的样本进行检验[11]，然后通过迭代的思想进行最优模型的寻找，由于算法通过迭代进行寻求最优，牺牲了算法的时效性，算法的运行时间随着噪声点的增加呈指数增长，不能满足工业实时性的要求[12]。

2.2 RANSAC 算法改进方向

通过RANSAC 算法的基本思想，可以分析出RANSAC 算法的基本的优化方向，可向着以下两个方向进行优化：

（1）在样本子集选取的时候，可以根据某些约束条件对随机抽样的样本子集进行约束，来减少错误抽取和检验的次数。

（2）当通过样本子集估计出总体模型后，可以只利用剩余点中的一部分来对估计的总体模型进行验证，但该优化方向在噪声点多时可能会造成误检验，从而陷入无限次的抽取和检验中。

3 基于IRANSAC-IRLS 的直线拟合算法

经Canny 提取的直线边缘数据中包含了大量噪声点，而随着噪声点的增加，RANSAC 算法的运行时间呈指数增长，为解决这一问题，利用同一条直线上的点的梯度方向相近，将梯度方向引入RANSAC算法中，提出IRANSAC-IRLS 直线拟合算法，该算法利用梯度方向对RANSAC 算法中随机抽取的样本进行约束，减少误抽取，提高算法的效率，同时引入梯度方向对内点的判断模型进行改进，减少提取出来的局内点点集中的噪声点，然后再结合迭代加权最小二乘法对提取出来的最优局内点点集进行拟合，提高最终的拟合精度，其算法的流程如图1所示。

图1 算法流程Fig.1 Algorithm flow chart

3.1 IRANSAC 算法

（1）在边缘点集上随机抽取确定直线方程的最小点数，即2 个点，设点1 的梯度方向为G1，点2 的梯度方向为G2，如果随机抽取的2 个点在同一条直线上，则两点的梯度方向差的绝对值应在一定范围内，自定义2 个抽样点梯度方向差的阈值Tg，公式如下：

如抽取的两点的梯度方向不满足公式（3），则重新抽取。如满足，那么使用这两点计算直线估计模型，并以这两点的梯度方向的平均值作为直线的梯度方向的主方向Mg：

（2）遍历剩余的点，如果点为直线上的点，应满足2 个条件：

①首先，该点的梯度方向应和直线的梯度方向主方向差值的绝对值小于阈值t：

式中：Gi为该点的梯度方向，然后计算该点到直线的距离di：

②设定距离阈值D，若di＜D，则满足第2 条件；若同时满足上述2 个条件，则可认为该点为局内点，否则是局外点，即噪声点。遍历结束后，计算出所有局内点的数目，并计算内点的比例ε＝局内点总数/数据点总数。

（3）重复进行步骤（1）和步骤（2），进行迭代，保存局内点最多的最优模型，保存当前迭代次数N，直到N 大于终止迭代次数m。

RANSAC 的迭代终止次数m 可以根据理论计算，计算公式如下：

由文献[13]可知，在置信度为η0的条件下，循环多次后，应至少存在一次采样，使得选择出来的b个抽样子集均为局内点，置信度η0为在样本中抽取一个好样本的概率，一般设置在［0.95，0.99］的范围内；b 表示模型估计所需要的最小点数，本文取2；ε 表示局内点在所有样本点中所占的比例。

对改进算法进行分析，首先该方法在样本点抽取后，利用抽样点的梯度方向对初始抽样模型进行预检验，降低了计算的时间；其次，在样本点检验时利用梯度方向条件，进一步对拟合时的部分噪声点进行二次筛选，降低了局内点集合的误差。

3.2 迭代加权最小二乘法拟合

经IRANSAC 提取出的局内点需要进行拟合，传统的拟合常使用标准的最小二乘拟合法，与直线距离较远的点和与直线距离相近的点都拥有相同的权重，得到的直线参数并不是理想的。因此，引入迭代加权最小二乘法对局内点进行拟合，根据点到直线的距离对每个点进行加权，其目标损失函数如下：

式中：Wi为各边缘点对应权重，i=1，2，…，num；k 为斜截式直线的斜率；b 为斜截式直线的截距。

将点到直线的距离d 作为权函数变量：

权函数有Tukey、Geman-MClure、Huber 等类型，本文采用Huber 权函数，各点对应的权函数如下：

式中：u 为设置距离阈值。

为求解式（8），对式（8）的k 和b 分别求偏导，得到：

采用常规最小二乘法求解，解得初始k0和b0；代入式（8）～式（12），更新权重，多次迭代求解斜率k和截距b，然后根据角度和截距的变化量来设置迭代终止条件。

4 实验与分析

4.1 仿真实验

为了验证IRANSAC-IRLS 直线拟合算法的有效性，在2.50 GHz 的i7-6500U～CPU 平台上进行仿真，假设要拟合的直线为y=0.1x+20，其角度为5.7106°，构建噪声点比例分别为20%、40%、60%、80%的300数据点，直线上的点的梯度方向设置在直线主方向角的［-10，+10］之间随机分布，噪声点的梯度方向在直线主方向角的［-90，+90］之间随机分布。

设置IRANSAC-IRLS 算法中的计算模型参数需要的最小数据点b=2，置信概率η＝0.98，抽样点梯度方向差的阈值Tg=2°，点与直线的梯度主方向差的阈值t=30°，点到直线的距离阈值D=1。设置迭代最小二乘法距离阈值u=0.8，终止迭代条件为直线的角度变化量小于0.008°。对不同噪声点比例下RANSAC-LS 与IRANSAC-IRLS 算法的直线拟合精度和效率进行仿真分析，100 次数据的平均值如表1 所示。

表1 300 数据点时RANSALC-LS 和IRANSAC-IRLS 的数据分析Tab.1 Data analysis of RANSALC-LS and IRANSAC-IRLS at 300 data points

4.2 实际产品实验

为验证IRANSAC-IRLS 算法在工业实际数据中是否有实际的应用价值和应用效果，对比分析不同的直线拟合算法在实际应用的使用效果。将本文算法在两种产品中进行测试，并与霍夫拟合、IRLS和RANSAC-LS 直线拟合算法进行对比，其中产品1为某含噪试管直线边缘，具有440 个数据点；产品2为某液晶屏幕直线边缘，具有2700 个边缘数据点。通过实验可得，对于两种实际工业图像数据，本文提出的IRANSAC-IRLS 拟合精度相较于霍夫直线拟合和IRLS 的拟合精度有较大地提高。霍夫直线拟合容易受噪声点的干扰拟合出多条直线，而工业环境下往往是需要拟合出最优直线，IRLS 受噪声点的影响导致初始偏差大的情况下，也无法拟合出精准的直线参数。RANSAC-LS 在产品1 和产品2 中的拟合时间分别为22 ms 和788 ms；IRANSAC-IRLS在产品1 和产品2 中的拟合时间分别为11 ms 和144 ms；IRANSAC-IRLS 算法在产品1 和产品2 中的拟合效率相较于RANSAC-LS 分别提高50.0%和81.7%，拟合精度也有所提高。

5 结语

本文提出的IRANSAC-IRLS 直线拟合算法，在RANSAC-LS 的基础上通过引入梯度方向对随机抽取的样本进行约束，减少了错误抽取的次数，提高了算法的时效性；对提取出来的局内点进行迭代加权最小二乘直线拟合，降低数据本身的误差对拟合的影响，提高了最终的拟合精度。仿真实验结果表明，在噪声点比例20%、40%、60%、80%的条件下，IRANSAC-IRLS 拟合效率比RANSAC-LS 分别提高16.3%、41.9%、47.5%、53.2%，拟合精度分别提升14.3%、16.7%、44.0%、69.0%，能有效地提高含有大量噪声点的直线边缘的拟合效率和精度。将本文算法应用于不同的工业产品图像的直线拟合中，验证了本文的算法具有良好的时效性和鲁棒性，能广泛地应用于自动化行业，但是该算法只适用于直线拟合，未来如何让其适用与多种形状的拟合，是后续要研究的方向。