一种基于轮廓边缘的直线拟合算法*

谭仁虎，胡小平，彭向前*，陈立锋，黄 泓

(1.湖南科技大学机电工程学院，湖南 湘潭 411100；2.湖南科技大学机械设备健康维护湖南省重点实验室，湖南 湘潭 411100)

直线是日常生活中常见的一种几何结构，通常会出现在物体的边缘[1]，直线段包含了场景中最基本的几何信息和拓扑信息，可以作为检测图像高层特征或分析图像内容的基础[2]。 直线特征作为一种规则离散点集，相对于点特征能够提供更加明确、丰富的结构信息，直线特征提取是图像分析领域的一个经典问题，被广泛应用于自动驾驶、工业检测[3]、图像匹配和相机标定等诸多领域。 因此，研究出快速而准确的直线特征提取算法是非常有意义的。

在直线检测方面的研究中，国内外学者已经取得了不少研究成果。 董晶等人[4]提出了一种结合主元方向和梯度方向的快速直线段检测算法，根据主元一致性和直线误差度筛选出有效检测直线段，并利用最小二乘拟合得到正确的直线段。 但是该算法依赖于用canny 算子提取边缘特征，算法的调整参数较多，自适应调整不佳。 亢洁[5]提出一种抗干扰性强的作物行检测算法，通过轮廓查找，求取轮廓的外接矩形，然后在所求矩形内进行线扫描，记录直线上的绿色像素数量最大时为最佳作物行直线，该算法的应用比较局限，对其他领域的适用性不足。

Grompone von Gioi 等人[6]提出了一种快速检测直线段方法，称为LSD 算法。 通过降采样的方式提高图像的质量，结合像素的梯度信息生成直线拟合区域，之后将区域看成矩形候选直线段，依据Helmholtz 原则[7]对直线段进行验证。 该算法检测的是图像矩阵中所有的直线，但是在很多视觉任务中往往只需要最具代表性的直线特征，并且将截断的线段重组起来，检测出更接近人类感知的线段。

Naila Hamid[8]提出了一种算法合并破碎的线段，该算法根据线段的角度接近度和空间接近度进行分组，将每组内符合算法要求线段合并为单个线段，重复此步骤，直到没有更多的线段可以合并。 该算法虽然能检测出更接近人类感知的线段，但是它求得的是多条直线特征，并不能找出最具代表性的直线特征，而且实际检测中的目标直线往往会受到种类各异和不定大小的噪声干扰，该算法容易受到背景信息与噪声的干扰，达不到高精度检测任务的要求。

鉴于上述算法的不足，本文提出了一种基于轮廓边缘的直线拟合算法，实验证明该算法具有良好的抗干扰性和适用性。

1 边缘检测

本文研究的核心是基于图像轮廓边缘提取直线特征，于是准确获取目标直线的轮廓边缘尤为重要。以图1(a)为例，用二值化边界扫描、canny 算子边缘检测、Laplace 算子边缘检测、Sobel 斜向算子边缘检测四种边缘提取算法和本文边缘提取算法的效果作对比。

如图1(b)所示，二值化扫描边界的方法，抗干扰性极差，会导致目标像素的大量损失；如图1(c)所示，Canny 算子是一种不错的边缘检测方法，但是高、低阈值的设置，不能根据图像自身的特点来确定，需要根据经验，人为预先设定，而且容易使噪声形成虚假的边缘[9]，给算法的计算带来难度。 如图1(d)所示，Laplace[10]算子是一种各向同性的算子，对孤立像素的响应比对边缘或线的响应更敏感，所以它只适用于无噪声的图像，会产生双边效果，不容易得到单像素的边缘特征，也不能得到离散的轮廓线，无法准确的进行分类计算。 Sobel 算子具备一阶算子算法简单，处理速度快的优点，由于使用了加权平均算法，因此对图像中的一些噪声具有一定的抑制能力[11]。 如图1(e)所示，Sobel 斜向算子可以快速而准确地获得目标直线的单像素点集，还能初步筛选掉一些干扰噪声[12]；但是检测目标的位置会对检测效果产生影响，而且对水平线段不敏感，提取的边缘特征连续性不好。

综合检测有效像素点的个数和实际边缘检测的准确度，以及减少后续算法的难度，本文选用了改良的Sobel 斜向算子和Sobel 水平算子3×3 的掩膜矩阵结合筛选条件作为边缘提取算法。 针对检测目标的位置，选择相应的方向梯度矩阵，梯度突变的地方就是轮廓边缘的位置，将突变的连续像素点作为一个轮廓点集记录下来，得到轮廓边缘的集合。

图2(a)为图像任意一个3×3 子区域像素点的位置示意图，P为对应像素点的灰度值。 式(1)为掩膜计算公式、通过式(2)计算得出Sobel 斜向算子和Sobel 水平算子3×3 掩膜矩阵卷积到的梯度值。本算法是在二值化的图像中提取边缘特征，通过归一化把灰度值低于二值化阈值的置为0，高于二值化阈值的置为1；图2(b)中的W为3×3 的Sobel 斜向算子卷积核权重的大小。

图2 卷积核

本文提出的改良Sobel 斜向算子，降低了中心四邻域像素权重(W2、W4、W6、W8)与对角邻近像素权重[13](W1、W3、W7、W9)；以45 度梯度方向作为实例详解，常规的斜向G常规45°与改良的斜向G改良45°(其余梯度方向对应适用)，图3(a)示例1 表示一个孤立的像素点，图3(b)示例2 表示连续的两个像素点，用式(1)和常规的斜向g常规45°计算两个示例的梯度值都为2，无法区分像素边界情况，通过本文改良的斜向g改良45°能计算出图3(a)梯度值为3，图3(b)梯度值为4，据此可以设定梯度阈值为3 来排除图3(a)的假边界像素，检测出更贴近真实边缘的像素点集。 式(4)中的P(i，j)为像素点的位置，J为对应条件下求出的梯度值，当J大于3 时即可将像素点P(i，j)判断为边缘像素点，纳入初步预测点集。

图3 示例边缘

本文边缘提取算法是为了获得最具代表性的直线特征，如图4 所示，设置了①截断线段、②粗线段、③分割线段、④曲线、⑤锯齿线段五种情况来验证本文改良的Sobel 边缘检测算法较常规Sobel 算法的优越性，图5 为边缘检测算法效果图，算法结果分析见表1。

虽然我国政府目前对林业的重视程度较高，但在投资上仍存在一些不足，基础设施不完善，林业道路建设尚未实施，部分受损道路未能及时修复。此外，基层工作环境恶劣，人才外流，部分林业种植基地因投入资金不足而未能种植优质苗木。相关科研宣传工作尚未落实。

图4 测试图2

图5 边缘检测算法效果图

表1 算法结果分析

2 边缘分类

2.1 优化的最小二乘法拟合直线

最小二乘法通过使误差的平方和最小化，寻找数据的最佳函数匹配，利用最小二乘法，可以方便地求出未知的数据，并将所得数据与实际数据之差的平方累积和最小。 传统的最小二乘法拟合直线的原理是用“残差平方和最小”求出直线的函数模型，但是，很容易受到离散噪点的干扰。

式中:纵坐标yi为对应横坐标xi的实际值，a为斜率，b为截距，δi为残差值。 如式(6)求残差值的平方，残差值等于实际的纵坐标值yi减去拟合得出的纵坐标。可以把残差值平方看作以a、b为变量的函数求偏导，得到极值点时的a、b值即为所求，如式(7)。

用最小二乘法[14]除了计算比较方便外，此方法能给出在统计意义上最好的参数拟合结果，但是这种方法对噪声非常敏感。 所以本文对最小二乘法进行了优化，首先把目标点集进行初步的最小二乘法拟合，通过式(8)计算出点集中每一个点到拟合直线的距离。

根据拟合精度的要求设置距离阈值(与精度成正相关)，判断Dis 是否小于设定的距离阈值，将符合筛选条件的点放入到拟合点集中进行第二次直线拟合，然后将设定的阈值减1，继续用目标点集里的点对新拟合出来的直线进行点到直线的距离筛选，如图6 所示(方形为有效像素点，圆形为无效像素点)。 直到拟合点集中的点到拟合直线的距离都在一个像素点之内后输出直线拟合结果，流程图如图7 所示。

图6 优化最小二乘法算法示意图

图7 优化最小二乘法算法流程图

2.2 角度空间分类

对每个轮廓用优化的最小二乘法拟合出相应的直线，用拟合优度R2来验证直线拟合的准确性和可靠性。 拟合优度评价是用于检验总体中的一类数据的分布是否与某种理论分布相一致的统计方法。

用式(9)来计算拟合优度，R2最大值为1，如果R2的值越接近1，说明直线拟合算法的拟合程度越好；反之，R2的值越小，说明直线拟合算法的拟合程度越差。

求解出符合拟合优度大于0.9 的直线斜率，因为直线的斜率k的范围为(-∞，+∞)，而且不是线性变化，无法将其分类，所以将斜率k转换成角度，取值范围为(-90，90)，为了便于计算与编程，让转换的角度都加上90°[15]，于是取值范围就变成了(0，180)，继而以每个区间的大小为1 度把其分成180 个区间，通过计算取模将各个轮廓拟合出来的角度大小进行分类，并把每个区间轮廓的长度累加，筛选长度最长的角度区间作为目标区间。

图8 插值计算示意图

然后通过相应的角度值找到对应的轮廓序号将所有求出的轮廓放到一个容器中并以黑底白线画到另一张临时图像中，得到点集筛选后的效果图，如图9所示。

图9 点集筛选效果图

3 边缘重组

确定一条直线需要知道斜率和截距，斜率的取值可以转换为角度进行量化分类，但截距不好进行量化，在直角坐标系中截距受斜率的影响，它不是线性变化的，所以本文算法提出了一种旋转扫描的办法来获取目标点集。

首先，计算出目标区间所有直线拟合的角度平均值；然后减去前面分区间时附加的90°作为图像矩阵旋转[16]的角度，让目标区间里的轮廓线处于水平状态，式(10)为旋转矩阵，式(11)为逆旋转矩阵[17]。 考虑到目标轮廓线如果是一条跨越整个目标图像的对角线，进行旋转后，轮廓线端部的像素点会超出图像边界造成像素点的损失，影响准确度，所以需要扩大目标图像的边界。 式(12)中的H和W分别为源图像的高和宽，计算出对角线L的长度，然后用式(13)向上取整得到需要扩展后的图像宽度＾W。 本算法的目的是把目标线段旋转为水平状态，为减少后续算法的计算量，只需扩展图像的宽。如图10，原图大小为696×564 pixel，经过扩展的大小为896×564 pixel。

图10 图像旋转效果图

经过图像旋转后，目标线段会旋转到与x轴角度很小的位置，在创建扫描矩阵时，为了防止目标像素的损失，将扫描矩阵的宽度与图像的宽度设为一致，高度的设定按边缘分类时的区间宽度根据式(14)算出，式中h为扫描区间高度大小。

如图11 所示，像素原点为遍历的起始位置，按箭头遍历全图后，得到目标区间。

图11 扫描矩阵示意图

图12 为测试图的局部灰度分布图，通过扫描矩阵以像素坐标y轴从小到大进行遍历，统计出所有非0 的像素点，得到像素个数最多的扫描区间。 然后通过式(11)对图像进行逆旋转得到点集图13，再用式(14)在图14 上截取一个起始点为(X，Y)，高和宽与源图像一致的矩形框，截取ROI得到图15，最后，再遍历复原图像中的非0 像素得到最终的目标点集，进行优化的最小二乘法拟合。

图12 局部灰度图

图13 筛选效果图

图14 逆旋转处理图

图15 复原点集图

4 验结果及分析

本文算法在处理器Intel(R)Core(TM)i5-8300H CPU＠2.30GHz，内存8GB，操作系统为Windows 10 64 位的电脑上使用 C + + 在 Visual Studio2017 仿真实现。

为了验证本文算法的有效性和优越性，对测试图片分别使用了霍夫直线检测和最小二乘法做比较，效果图如图16。

图16 拟合效果对比图

图16(a)的霍夫直线检测需要人为地根据图像调整参数阈值，工程适用性极差，算法检测出来的直线都是一些离散的线段，就算是在同一条线段上也会检测出多条离散的线段，每一条线段都有它的直线特征，所以导致目标不明确；而且离散的线段没有整合起来的线段的像素个数多，导致拟合的准确性较低。 图16(b)是用最小二乘法拟合出来的效果图，该算法极易受到噪声的干扰，算法稳定性差，无法找到准确的直线特征。 图16(c)是本文提出算法的效果图，克服了上述两种检测算法的弊端，能够准确地找出目标线段的直线特征。

本文算法在工程实践中也得到了较好应用，如表2 展示了对某注塑件的几种恶劣情况的图像处理效果，通过对1 000 个产品进行测试，用霍夫直线检测和最小二乘法检测都无法得到正确的产品边缘，而本文算法能精准地抓取目标边缘，准确地提取直线特征，产品定位合格率达98.5%，实验应用表明，采用该算法进行特征定位能满足实际应用的要求。

表2 实验结果对比

5 结束语

本文算法主要是通过改良的边缘检测算子得到单像素的轮廓边缘，按设定的拟合优度阈值初步筛选出候选轮廓线，用初步拟合的直线角度进行分类，然后对分类后的直线集合重组，并用优化的最小二乘法对其进行拟合得出直线特征。

本文提出的直线检测算法具有良好的抗干扰性和适用性，相对于传统的直线拟合算法，在复杂的图像背景下，拟合结果更贴近实际直线。 此算法适用于多种工业场景下产品的直线特征提取，以对产品进行准确的定位。