一种改进的直线检测算法

朱书华

（国家知识产权局专利局专利审查协作广东中心，广东 广州 510530）

0 引言

直线段、曲线段和角点是组成物体的最基本的几何特征，它们是对目标物体进行高层研究的基础，从图像中准确识别这些特征是计算机视觉领域的重要研究内容之一，对智能交通、数字地图的更新和城市交通状况监测具有重要意义[1-3]。

经典的直线检测算法由霍夫变换(Hough Transform)来实现。Hough变换是由Paul Hough提出的，其最初是用来检测图像中的直线的一种方法[4]。由于Hough变换是通过在两个笛卡尔坐标系之间的变换来进行直线检测的，所以当直线的斜率趋向于无穷大时，用该方法来检测直线就带来了一定的困难。

基于相位编组检测直线是另一种检测直线的方法，相位编组是由Brian Burn J[5]在1986年提出的，由P.Kahn做了全面的改进。该算法涉及到两个概念，即边缘支持区和梯度相位。边缘支持区是由梯度方向相同的相邻像素点组成。在像素的邻域范围内，其灰度变化最大的方向即为梯度相位。相位编组检测直线的原理即是基于梯度方向一致性。该算法将提取直线简化为链接和分组两个过程，同时该方法还可以计算出直线的宽度、长度等。Hough变换实质上也涉及到了边缘的相位问题，但是在Hough中，只有幅值大的边缘才能被检测出来，而相位编组算法则在提取直线的过程中不受对比度、局部宽度等的影响。

基于主成分分析(Principal components analysis，PCA)或基于协方差矩阵最小特征根检测直线的方法是近几年提出的一种新的检测直线的方法。该方法利用了直线的连续性，它以边界上的一点和包含该点的一段连续边界为对象来研究，首先构造协方差矩阵，并计算最小特征根，如果其最小特征根小于预先设定的阈值，则表示此段边界为直线[6]。2004年，Guru提出了基于最小特征根检测直线的方法[7]，该方法由于计算简单、高效，因此得到了广泛的应用。但是由于此方法在检测过程中，使用传统的局部窗口进行检测，因此会出现将平滑曲线误判为直线的问题，且对噪声也较敏感。2006年，Yun-Seok Lee等人对该方法进行了改进[8]，该方法通过将边缘图像的像素点分为行像素图和列像素图，从而避免了局部窗口产生噪声的影响，且在时间上也有了大大的提高，但是当两直线相交形成的角度比较大时，用此方法就会出现严重的漏检情况，且还会把部分光滑曲线检测为直线。引入链码算法可以较好的解决此问题，但是由于链码算法易受噪声的影响，且加入链码后，检测直线所有的时间较长。

从目前的研究现状来看，现有的上述算法对直线的检测存在困难，据此，本文提出了一种直线检测改进算法，对边缘检测的图像进行线段拆分，基于协方差矩阵特征根初步检测出直线、圆、曲线，并基于各个像素点的方向变化而将初步检测出的曲线进行进一步检测获得其含有的直线部分，通过结合初步检测的直线和曲线中检测的直线部分实现直线检测。

1 算法模型

1.1 线段拆分

自然场景中的线段端点通常有两种情况：（1）两向交点：线段与另一条曲线或直线的交点；（2）多向交点：线段与其它两条或两条以上曲线或直线的交点。根据线与线相交的仿射不变性，自然场景映射为数字图像后，端点将仍然存在，并且大部分两向交点会映射成为角点，多向交点会映射成为交叉点。基于此，连续边缘终点、交叉点和角点必然是最有可能构成线段端点的特征。

因此，从线段入手，通过对线段分解及每条线段的方向变化来对物体的特征识别进行研究，其中包括对物体的直线段，平滑曲线识别。为了提取准确的直线，本文采用能够连接局部弱边缘的Canny算子对源图像进行边缘检测，设其边缘图像为E，E中边缘具有单像素宽度，对边缘图像E进行线段拆分，其具体过程如下所示。

图1 3×3邻域内的交叉点结构

考察E(x,y)中某边缘像素P的3×3邻域，像素点序号如图1(a)所示。设x(i),i=1,…,9表示P的3×3邻域内的像素值(0或1)，定义：a=[x(1),x(2),x(3),x(6),x(9),x(8),x(7),x(4)]，b=[x(2),x(3),x(6),x(9),x(8),x(7),x(4),x(1)]，如果其满足：

则为交叉点，如图1(b)所示，对经过Canny边缘检测之后的图像E，依据式（1），对E进行交叉点检测，如果某边缘像素满足式（1）中条件，则将该像素赋值为0。重复检测，直到E中不存在交叉点。其具体实例如图2所示，其中2(a)是源图像，图2(b)是Canny边缘检测的图像，其交叉点和端点如图2(c)所示，其中十字交叉点表示线段的端点，圆圈表示三叉交点，其中不同的颜色代表了各个不同的拆分出来的线段。依据上述规则，检测E中的交叉点，如果某边缘像素满足式（1）中条件，则将该像素赋值为0。重复检测，直到E中不存在交叉点，此时定义不含交叉点的边缘图像为Ed：

其中，mi表示组成线段Ci的像素点数，其中，(xij,yij)表示第i条线段上第j个像素点的坐标，Ci上每个点的值为1。其对Canny边缘检测之后的图像进行边缘拆分，其线段拆分之后的结果如图2(d)所示。

图2 端点和交叉点结果图

1.2 基于协方差矩阵特征根的线段形状初步检测

经过边缘分解，Ed中包含若干条独立且连续的线段Ci，其形状可能是曲线、圆或直线。根据微分几何定理，以弧长表示C2类平面曲线Ci:r=r(s)，则Ci在一点pj=r(s0)的邻近结构利用泰勒公式展开后，结合伏雷内公式，可得：

式（3）中，α,β 为平面曲线基本向量，κ 为曲率，ε1,ε2为微小量，Δs为局部曲线弧长，取r(s0)为直角坐标系原点，以α,β为坐标系基向量，在r(s0)点邻近，曲线的近似方程为：

即曲线在一点的邻近结构有三种可能：二次抛物线，三次抛物线和直线。对于数字图像而言，局部范围内很难区分三次抛物线和直线，因此可忽略三次抛物线的情况，即在数字图像中，考虑曲线在一点的邻近结构只有二次抛物线和直线这两种可能。

对 Ci={pj=(xij,yij),j=1,…,mi},i=1,…,n，取 pj=(xij,yij)左右 4 相邻点组成局部支持集Cij={pj｜i-4≤j≤i+4}。根据协方差矩阵检测直线的原理[7-8]，定义向量 x1=[xi(j-4),…,xij,…,xi(j+4)]，x2=[yi(j-4),…,yij,…,yi(j+4)]，如果设输入矩阵为X={x1,x2},xi∈Rn,(i=1,2)，则有协方差矩阵：

对 CX进行特征根分解，可得 p 特征向量和两个特征值 λ1,λ2(λ1＞λ2)：

其中，特征向量p1代表数据X主方向，p2⊥p1，两个特征值λ1,λ2分别代表数据X在方向p1和p2上的方差。从微分几何的观点，可认为p1，p2是平面曲线 Ci在点 pj=(xij,yij)的伏雷内标架，p1=α,p2=β。

（1）基于协方差矩阵最小特征根λ2检测直线

由文献[8]可知：如果由 Cij={pj｜i-4≤j≤i+4}定义的 CX计算所得的最小特征值λ2=0，则Cij上的点满足直线方程，且最小特征根的值越接近于0，表示像素点的共线性越好。因此，当λ2为0时，检测为直线。

（2）基于协方差矩阵两特征根比值λ1/λ2检测圆和曲线

由文献[9]可知，如果支持集中的边界像素点共圆，则其两特征根满足关系式 λ1=λ2。 因此，当两特征根 λ1/λ2的比值等于1时，检测为圆。协方差矩阵的两个特征值λ1/λ2的比值大小反映了线段的弯曲程度，比值越小，即其值越接近1，其弯曲越大，等于1时表示的是圆；反之，比值越大弯曲越小，当λ2为0时，比值为+∞，表示的是直线。

1.3 曲线中直线部分的进一步检测

对于前述初步检测出的直线、圆、曲线，其中曲线还可能含有直线部分，对此，可利用曲线中的方向变化检测出曲线中的直线部分，从而细分出曲线中的直线部分，并结合前述初步检测的直线实现直线检测。设待检测的连续边缘为Ci(1≤i≤n)，统计曲线上各像素点的方向值dir，得到局部直线方向直方图，设定如果某一方向值dir出现的次数大于预设阈值Tdis，则对这些像素点进行最小二乘直线拟合，求解最小化问题：

求得式（13）的参数ka和ba后，再考虑Ci上其他点到拟合直线的距离误差值：

如果dis(i)＜Tdis(Tdis为预设阈值)，则认定该像素点i属于直线部分，统计所有满足条件的像素点的坐标构成新的直线集合Ldir，记为检测出的直线部分。

2 实验结果与分析

为了验证本文算法对直线识别的有效性，我们选取了三类图像进行试验，并分别将直线检测的结果与三种经典算法：Hough变换直线检测、相位编组、最小特征根算法[8]进行对比，其中三类图像分别为人工合成图像、含有曲线的建筑物图像、含有圆的道路指标图像。

2.1 人工合成图像

图3(a)为源图，图3(b)是Canny边缘检测的图像，图3(c)是Hough变换直线检测结果，图3(d)是相位编组检测结果，图3(e)是最小特征根检测结果，图3(f)是本文算法检测结果。对比图3(c)-(f)与边缘检测得到的图3(b)中右上角的圆、椭圆、矩形检测结果可以发现，本文算法直线检测效果最好，成功去除了圆和椭圆，Hough变换和相位编组检测结果均不能去除圆和椭圆，最小特征根直线检测仅去除了椭圆的一部分。

图3 人工合成图像检测结果

图4 建筑物图像检测结果

2.2 含有曲线的建筑物图像

图4为含有曲线的建筑物图像检测结果，通过图4(c)-(f)与边缘检测得到的图4(b)比较，可以发现：本文算法检测效果最好，较成功地去除了右下角草坪的大圆弧，Hough变换和相位编组均将弧当作部分直线，最小特征根法在去除弧的效果上也没有本文算法理想。

2.3 道路指标图像

图5为道路指标图像检测结果，通过图5(c)-(f)与边缘检测得到的图5(b)比较，可以发现，本文算法在检测过程中能成功的去除圆，且对于检测出的直线，本文算法能较好的将检测出的各个直线段断开，方便了后续各个直线段的拟合。

图5 道路指标图像检测结果

3 结论

提出了一种直线检测的改进算法，该算法包括线段拆分、初步检测和曲线的进一步直线部分细分，相比传统的直线检测算法，本算法可以在较准确检测直线的同时，有效地去除边缘图像中的曲线和圆。

[1]Li Q F,Shi J F,Li C.Fast Line Detection Method for Railroad Switch Machine Monitoring System [C]//International Conference on Image Analysis and Signal Processing,2009:61-64.

[2]Ding Weili,Wang Wenfeng,Zhang Xuguang et al..Extracting straight lines from building image based on orientation image[J].Acta Optica Sinica,2010,30(10):2904-2910.

[3]Chen G,Li L,Ma J W,A Gradient BYY.Harmony Learning Algorithm for Straight Line Detection[J].Lecture Notes in Computer Science,2008,5263:618-626.

[4]Hough P V C.Method and Means for Recognizing Complex Patterns[P].US Patent,No 3069654,1962,2.

[5]Brian,Burns J,Hanson A R et al..Extracting Straight Lines[J].IEEE Transactions on Pattern Analysis and Machine Intelligent,1986,8(4):425-455.

[6]Kuang Ping,Zhu Qingxin,Chen Xudong.Line Detection Algorithm Based on the Smallest Eigenvalue Analysis[J].Journal of Electronic Measurement and Instrument,2007,21(3):33-38.

[7]Guru D S,Shekar B H,Nagabhushan P.A Simple and Robust Line Detection Algorithm Based on Small Eigenvalue Analysis[J].Pattern Recognition Letters,2004,25(1):1-13.

[8]Lee Y S,Koo H S,Jeong C S.A Straight Line Detection using Principal Component Analysis[J].Pattern Recognition Letters,2006,27(4):1744-1754.

[9]Tsai D M,Hou H T,Su H J.Boundary-based Corner Detection using Eigenvalues of Covariance Matrices[J].Pattern Recognition Letters,1999,20(1):31-40.