一种基于改进Hough变换的直线快速检测算法_段汝娇

第31卷 第12期2010年12月仪器仪表学报Ch i nese Journa l o f Sc ientific Instru m entV o l 131N o 112D ec .2010收稿日期:2010-07 R ece i ved D ate :2010-07*基金项目:铁道部-清华大学科技研究基金(J 2008X011)资助项目一种基于改进H ough 变换的直线快速检测算法*段汝娇,赵 伟,黄松岭,陈建业(清华大学电机系电力系统国家重点实验室 北京 100084)摘 要:针对传统H ough 变换计算量大、耗费内存空间、参数空间峰值点被次峰值点包围、易造成漏检或误检等缺陷,提出一种改进的H ough 变换直线快速检测算法。

首先检测图像中相邻的像素点并进行聚类,形成一些相连的像素点的集合,然后将聚类后的像素点进行感知编组,细分成比原聚类线段更接近直线的线段,最后对每段近似直线用随机H ough 变换进行检测,从而精确地检测出图像中相应的直线。

实验表明,与传统H ough 变换相比,改进后的算法计算量小,节省内存,无需先验知识,且抗干扰性有显著提高,并降低了误检率和漏检率。

关键词:像素点聚类;感知编组;随机H ough 变换;直线检测;快速检测中图分类号:TP391.41 文献标识码:A 国家标准学科分类代码:510.4050Fast line detecti on al gorith m based on improvedH ough transformati onDuan Rujiao ,Zhao W e,i H uang Song li n g ,Chen Jianye(State K ey Lab of P o w er Syste m,D e p ar t m ent of Electrical E n g ineer i ng,T singhua Uni ver sity,Beijing 100084,China)Abst ract :H ough transfor m (HT)is a popu l a r too l for li n e detecti o n due to its r obustness to noise and m issi n g data .H o w ever ,the co m putati o na l cost and m e m ory space consu m ption assoc i a ti n g w ith its voting sche m e have prevented its applicati o ns .H ere an i m pr oved HT algo rithm is proposed to so lve these pr oble m s .Firstly the neighbor pixels are clustered ,and then the c l u sters are subd i v ided i n to sets ofm ost perceptua ll y si g nificant stra i g ht li n e seg m ents .For each seg m en,t its best fitting line can be found usi n g rando m H ough transfor m (RHT ).Co m pared w ith trad itional HT algor ithm ,the proposed approach can not on ly accelerate the co m puting speed and save m e m ory space ,but a lso produce a m uch cleaner vo ti n g m ap and m ake the transfor m m ore robus.t K ey w ords :pixel cluster ;perceptua l organ izati o n ;RHT;li n e detecti o n ;fast detection1 引 言自动识别图像中的直线,是图像处理和计算机视觉领域的一个重要课题。

Hough 变换是处理此问题的一种有效工具,具有良好的鲁棒性和抗干扰能力,在许多领域得到了应用[1-6]。

H ough 变换算法的主要思想是,先将参数平面按一定步长离散化为许多小格,然后采用/多对一0映射,计算图像空间中共线的多个像素点在参数平面中对应的参数值,若计算结果落在参数平面某一小格内,就使该小格的累加器加1,累积值最大的小格即为图像空间中直线的参数。

这种从图像域/投票0到参数域的穷尽式搜索模式,不仅计算量大,占用内存多;同时,参数域中得票最多的小格被得票数次多的小格所包围,容易对检测造成干扰,导致对直线的误检或漏检。

针对H o ugh 变换的上述缺陷,一些学者提出了改进措施。

K ir yati 等人提出了概率Hough 变换(P HT )[7],具体是将图像数据映射到参数域中具有更大概率的单元,而非所有单元。

Due 等人提出了随机H ough 变换(也称RHT )[8-11],即通过对像素点的随机采样,避免传统H ough 变换需庞大计算量,且降低了内存需求;但其处理复杂图第12期段汝娇等:一种基于改进H ough变换的直线快速检测算法2775像时,会引入大量无效采样和累积,使算法性能大为降低。

Gonzalo Pajares提出利用梯度方向信息对R HT采样点对的选择和累积进行改进[12],但对梯度方向分散、梯度信息利用价值不大的图像,该方法并不适用。

邱桑敏介绍了一种快速霍夫变换算法[13],虽然其较传统霍夫变换的计算时间有减少,但占用内存空间增加了近一倍。

J.M atas提出了一种新的自适应P HT算法[14],通过比较包含像素点的各个小区域的差别来减少检测直线所需的计算量。

文献[15]中采用全局阈值和局部阈值相结合的方法去除虚假尖峰,但该方法对直线的断裂较为敏感。

针对上述问题,本文试提出一种基于改进H ough变换的直线快速检测方法。

2基于H ough变换的直线检测算法H ough变换[16]的基本思想是,利用图像域与参数域的点与线之间的对偶原理,具体地,图1(a)x-y坐标系中直线y=k0x+b上的任意两点P1、P2分别与图1(b)所示k-b坐标系中的两直线L1、L2相对应;而L1、L2的交点P0对应于x-y坐标系中的直线L。

图1H ough变换的点-线对偶原理示意F i g.1T he pr i nciple diag ram ofH ough transf o r m针对在x-y坐标系中垂直于x轴的直线的k值为无穷大的情况,通过将x-y坐标系对偶到H-Q参数坐标系就可解决此问题,见图1(c)。

H ough变换将H-Q参数平面量化为许多小格,对x-y坐标系中的每一个像素点(x,y),逐一计算不同H量化值对应的Q值,并在对应的量化小格累积加1,或称/投票0。

最后,检测整个量化参数空间累加器的峰值,此峰值即为对应的图像域中直线的参数。

把检测到的峰值及其一定范围内的邻域值置零,然后继续检测,直到检测出了所关注的所有条直线为止。

3基于改进的H ough变换的直线检测算法3.1相邻像素点的聚类受外部噪声和图像采集设备性能不完备等因素的影响,实采图像经滤波、分割、细化、边缘检测等预处理后,在结果图像中得到的仍会是不平滑的直线、由不平滑直线组合成的折线,以及未滤除噪声所形成的小短线等。

若利用传统H ough变换,在图像处理过程中因噪声形成的小短线很容易对检测真正的直线造成干扰,导致对直线的误检或漏检。

故为减小这种干扰,首先应将图像中相邻的像素点聚为一类[17],具体算法步骤如下:1)在已知的二元图像)中任取一点P,判断是否P=1,即是否为特征像素点,若不是,则重新选取,若是,则执行步骤2;2)将新找到的特征点的位置记为P,记录该特征点,放入特征点集合一端S+P v S,并将该点的像素值置为零P=0;3)依次对P点所有的邻域进行判断,是否为特征点,若是,则立即返回步骤2,若未找到特征点,则执行步骤4;4)重新搜索P点邻域,判断是否存在其他方向相连的特征像素点,若存在,则立即执行步骤5,若不存在,则结束;5)将特征点放入集合的另一端P+S v S,其余操作与步骤2相同;6)继续判断P点所有的邻域,看是否为特征点,若是,则返回步骤5,若未找到特征点,则结束。

图2为像素点聚类算法的流程图,经上述过程处理后,图像中的所有不相连的像素点就分别聚合到了一起;同时,图像中那些孤立的像素点则被剔除了。

这样做的好处是,将像素点分别聚类成近似直线,缩小了检测直线的范围,使检测目标更明确,且即使距离很近的平行线也会被分离开,避免了误检或漏检,同时减少了计算量和计算时间。

2776 仪 器 仪 表 学 报第31卷图2 像素点聚类算法流程图F i g.2T he flo w cha rt of p i xe l cl uster a l gor it hm3.2 直线的感知编组图像聚类后,相连的像素点可能为近似直线,也可能是若干近似直线段组合成的折线。

为便于检测,需对折线作进一步细分,以使细分后的每一段更接近直线。

如图3所示,假设图中曲线A 为聚类后的某线段,(x 1,y 1)、(x 2,y 2)分别是该线段两端点的坐标,而B 为由这两端点确定的直线,(x 3,y 3)是线段A 偏离直线B 的偏离距离为d 的点的坐标,d 可由几何变换推导得到,见如下算式:d =[(y 3-y 1)(x 2-x 1)-(x 3-x 1)(y 2-y 1)]/L(1)式中:L =(y 2-y 1)2+(x 2-x 1)2。

用曲线两端点间的直线距离与曲线相对直线的最大偏离距离之比代表此段曲线接近直线的程度[18-19],即:R =L /m ax d(2)该比率R 仅与近似直线本身的性质有关,而与图像的尺寸无关,不会随图像大小的变化而改变。

从偏移距离最大的点对原线段进行二分割,并计算分割后两子线段的比率R i (i =1,2),且将其与原线段的比率进行对比,若它们均大于原线段的比率,则用两子线段代替原线段,并以相同代替段到最小细分值为要对折线进行进一步细分从而能过的小短线,方式对子线段再做细分,直至达到最少细分像素点个数阈值为止;否则,保持前一步线段不变,表示其更接近直线,无需再作细分。

图3 直线最大偏移距离计算示意F i g.3T he calculati on of t he li nem ax dev i a tion图像经过感知编组后,每条线段更接近直线,使被检测直线进一步明确,提高了检测精度。