一种检测图像直线倾斜角度的新算法

2014-08-06徐兴东

中南民族大学学报（自然科学版） 2014年4期

徐兴东，程立

(1 中南民族大学实验教学中心, 武汉 430074 ; 2 中南民族大学计算机科学学院, 武汉 430074 )

在图像处理中，通常使用HOUGH变换检测直线的倾斜角度.HOUGH变换的基本思想是利用平面空间和参数空间的点-线的对偶性，将平面空间的直线上的点变换到参数空间，得到直线的表达式[1,2].使用HOUGH变换检测直线倾角，具有很强的抗干扰性，能检测出不连续的直线和具有弯曲变形的直线的倾角.该种算法实际上是一种试探的算法，在一定倾角范围内，检测有没有一定角度的直线出现，并统计落在该直线上的点数.很明显，由于要探测多种可能，HOUGH变换算法计算量大，特别是在直线可能出现的倾角范围很大，并且对直线倾角检测精度要求较高时，必须在很大的范围内进行探测，需要更多的计算时间.同时，对于HOUGH变换来说，还需要比较大的存储空间来存储各种探测直线上的点数.

在很多应用中，需要能快速检测出直线的角度.在这里，采取的方法是首先对直线进行细化，然后找到直线的端点，由端点开始沿着直线进行遍历，记下前进的方向码.遍历完毕后，计算方向码的平均值，并进行修正，即可检测出准确的直线的倾角.

1 方向码与角度的关系

在处理中，首先要对直线图像进行细化，即得到直线的轮廓，通过一些方法很容易得到直线边缘的轮廓[3].对于连续的直线，细化后的骨架也是连续的.根据直线上点的8邻域状况，很容易找到一条直线的起点[4].在此主要考虑的是黑点(背景为白色)，则一个黑点的8邻域如图1所示.其45°以内的细化直线如图2所示.

图1 点P的8邻域Fig.1 Eight neighborhood diagram of point P

图2 45°以内的细化直线Fig.2 Lines thinned in 45°

其中P为直线上的黑点，0～7为点P的8邻域，很明显，如果邻域0为黑点，则P和0点连线为0°，1为黑点则为45°，称n为点P的方向码，可知方向码n(n=0～7)与角度α关系为：α=45n.

2 直线的角度检测

对于细化后的直线，其端点的8邻域中只有一个黑点，依此可以找到直线的起点.要检测出整条直线的倾斜角度，可以从某一端点开始进行遍历，在遍历过程中，记下所有点到下一点的方向码，然后用方向码的总和除以总点数，即可得到直线倾角的大致角度.我们在这里使用该方法以5°为间隔检测了0～90°的直线，其数据如表1所示.

表1 直线的实际值和检测值

依照表1，图3给出了检测角度和误差的曲线图.

图3 误差-测量角度曲线图Fig.3 Error-angle graph

很明显，误差和测量角度间的关系近似于正弦关系.按照表1的数据进行正弦曲线的拟合，将测量的角度加上拟合后正弦的相反数即为补偿.图4为拟合后的曲线.按照拟合的曲线，补偿之后的直线测量角度为：

α′ =Σn/N，

(1)

α=α′ + 4.20sin(4πα′/180)，

(2)

式中n为直线上所有点相对于上一点的方向码，N为总点数，α为修正后的检测角度.

图4 拟合后的误差-测量角度曲线图Fig.4 Error-angle fitting graph

3 补偿的理论依据

在此讨论0～45°的范围，其余范围同理.在0～45°的范围内的直线，细化后，轮廓上的点至下一点(从左至右，从下到上)的方向码只有两种情况，即0和1，如图2所示.设所有方向码为0的点(正右方)总数为n0，所有方向码为1的黑点(右上角)的总数为n1，且直线上点的总数为N(不计起点)，则有N=n0+n1；按照方向码均值求的角度为：

α′ = (45×n1+0×n0)/N= (45×n1)/N，

(3)

按照反正切求的角度应为：

α=atan(n1/N)×180/π ，

(4)

则其误差为：

err= 45×n1/N-atan(n1/N)×180/π.

(5)

由图2知，补偿的正弦规律函数在测量角度为0～90°即为一个整周期，故补偿函数的幅值表达式为：

(6)

对此表达式，使用Matlab从总点数N=10到N=10000，n1从0到N(即角度从0～45°)进行计算，可求出A介于4.1873和4.2207之间，变化很小，取最大值和最小值的均值4.2040，作为补偿函数的幅值，即可得到误差很小的直线倾斜角度.将此补偿幅值作为公式(2)中的参数，并以此作为最终的直线倾角检测角度，在设计的VC检测程序中进行检测，能获得非常精确的直线倾角.

4 异常处理

在直线的细化中，可能出现异常的情况，考虑连续的3个黑点，一共有4种情况，如图5所示.其中(a)、(b)中3个点应该在一条水平线上，(c)、(d)中的3个点应该在一条竖直线上.

图5 细化后的异常情况Fig.5 Abnormal conditions diagram after thinning process

对于图5(a)、图5(b)，遍历直线的方向有从左到右和从右到左两种方式.当采取从左至右遍历时，图5(a)的方向码为1和7，图5(b)为7和1，其和为8，而实际应该为0和0，显然有较大误差.若采用从右至左的方向，则图5(a)、图5(b)的方向码分别为3，5和5，3，其和与实际值4，4之和是相同的.而对于图5(c)、图5(d)无论是采用从上至下还是从下至上的方向进行处理，方向码之和和正常情况都是相等的.很明显，对于图5(a)、图5(b)两图，当采用从左至右的方向遍历时，由于按图(1)图像中任一点P右端3个邻域点的方向码分别为1，0，7，而点P的上侧、左侧和下侧相邻的3邻域中，中间点均为两边点的平均值，所以不用进行处理.综上所述，当出现图5中图5(a)和图5(b)两种情况时，需进行特别的处理，将其变为实际的方向码.

5 时间复杂度分析

本算法相对于HOUGH变换，在时间复杂度和空间复杂度上均具有明显的优势.以图形上某一条具有N个点的直线为例，若采用HOUGH变换检测直线角度，需首先预设直线倾角范围，并设定角度探测步长，也就是检测精度.假设角度范围为[θ1,θ2], 探测步长为Δθ，则采用HOUGH变换时需完成的循环次数为：

(7)

而采用本算法，最坏情况下循环次数为8N, 平均循环次数4N, 即每个点在其8邻域中找其下一点的方向码.采用HOUGH变换时，假设当直线倾角范围为[-45°,45°]，检测步长为0.5°，则需循环次数为180N，很明显本算法处理的循环次数大大低于HOUGH变换.并且采用HOUGH变换时，每次循环需计算所探测角度的正弦和余弦，还需实现两次乘法和一次加法，而本算法只需在循环中完成一次加法.可见本算法在时间复杂度上明显低于HOUGH变换，并且检测时处理时间和直线的倾角范围及检测精度无关，只与直线上的点数成线性关系.

6 结果与讨论

按照遍历直线轮廓，求出各点到下一点的方向码的平均值，并做修正后，可以获得直线的准确的倾角.相对于HOUGH变换，本方法计算量小很多；而相对于求反三角函数的方法，本方法不需要讨论角度的范围.表2为经过修正后的直线的测量角度和实际角度，可见经过补偿后，检测的角度和直线的实际角度非常接近，误差很小.而且使用该方法检测直线的角度，既可以遍历到直线的另一端点结束，也可以只遍历一定的点数，检测所需要的时间与直线的倾角范围无关.当然，本算法只能适用于连续直线的情况，对于断续直线，本算法则不适用[5].而且，在使用算法前，首先必须对直线进行细化处理，或者是单像素的直线边缘，其处理情况和图2类似，只是不同角度的直线，方向码不同，所以文中未给出更多的实验图例.