改进的Hough变换

改进的Hough变换（精选7篇）

改进的Hough变换 篇1

在复杂图像中如何快速而准确地检测椭圆目标一直是研究者们努力探索的一个重要问题。这在生物医学显微图像、工业自动化检测、机器人视觉、空间技术和军事防御等领域有重要的应用。Hough变换是曲线检测最有效的方法之一,于1962年由Paul Hough提出,并在美国作为专利被发表[1]。标准Hough变换(SHT)的主要特点是:对于图像中局部信息的缺损不敏感,对随机噪声的鲁棒性;但由于计算量与存储量随着参数空间维数成指数关系增加而难以实用。大量研究致力于改善Hough变换的实用性,并取得了一定的成果。Xu等提出了随机Hough变换(RHT)[2,3]。该方法是多到一的映射, 避免了标准Hough变换一到多映射的巨大计算量。但是在处理干扰较多的复杂图像时,RHT的随机采样会引入大量无效采样,大大降低了算法的性能。文献[4]提出了一种利用椭圆的极点、极弦中点与椭圆中心共线性质的RHT改进方法,但该方法对于多椭圆的检测并不高效。陈燕新等利用梯度信息提出了一种较好地解决无效采样的RHT改进算法[5],但对噪声比较敏感。还有一些利用几何特征降低参数空间维度的方法[6,7,8,9,10],如屈稳太提出了一种新的基于弦中点的Hough变换(CMHT)检测方法[8],利用椭圆上所有点的内切椭圆必经过椭圆中心的性质,先对图像边缘点进行累积求得椭圆中心,再利用椭圆方程计算椭圆另外3个参数;但此方法在处理背景复杂图像时,会出现检测出椭圆中心位置不准、虚假椭圆较多的情况。本文在CMHT算法的基础上,提出一种椭圆检测改进算法,用于真实大便镜检测图像中的虫卵细胞。本文算法对参数空间的计算以及椭圆参数的求解进行了改进,并结合参数方程进行了虚假椭圆的判断,从而提高复杂环境下椭圆的检测精度,降低了误检率。

1CMHT算法原理

椭圆一般性方程为:

设椭圆中心为(x0,y0),则椭圆方程变为:

式(1)有5个自由参数,文献[8]中CMHT算法采用2步检测法:第1步利用弦中点的几何特性投票统计得到关于椭圆中心的2个参数x0,y0;第2步结合椭圆方程式(2)计算出另外3个参数。

1.1基于椭圆中心的投票

性质1:在椭圆上任取一点与椭圆上其他点的连线构成椭圆的一组弦,这组弦的中点构成一个新的椭圆, 该椭圆称为原椭圆在该点的内切椭圆,如图1(a)所示。

性质2:椭圆上外法线方向相反的2个点称为椭圆的一对对偶点,椭圆上所有对偶点连线的中点即为椭圆的中心,如图1(b)所示。

由性质1可知椭圆上非对偶点之间连线的中点散布于各处;由性质2可知椭圆上所有对偶点连线的中点都集中落在椭圆中心处。另外其余非椭圆上的点即噪声点与其他各点连线的中点也散布于各处,并且落在同一点的可能性很小。因此如果把原图像边缘二值图中的每一个边缘点都与其他点相连,并对连线的中点在参数空间进行投票统计,则在每个椭圆中心处将出现统计值的峰值,这正是Hough变换的基本思想。CMHT算法会遍历参数空间中每个点的统计值,当某个点的值大于设定的阈值时则认为该点是一个椭圆中心。

1.2椭圆参数计算

对每个椭圆中心(x0,y0),寻找关于中心对称的3组特征边缘点,代入式(2)中求解未知参数A,B,C。

2本文改进方法

当处理复杂图像时,参数空间会出现多个大于设定阈值点的位置接近的情况,导致检测出较多虚假椭圆中心;且由于干扰点较多,计算出椭圆的另外3个参数会出现较大误差。因此根据出现的问题本文算法增加了以下3点改进。

2.1参数空间计算的改进

检测参数空间统计值的极大值点作为椭圆中心,并根据极大值附近多个较大值点对中心点坐标进行修正。设参数空间H,根据先验知识取椭圆长半轴长为a, 对参数空间任意点P,设以该点为中心,边长为2a的方形块为局部区域R。先假设P点统计值P(x,y)为区域R的极大值Rmax。 遍历区域R,若某点统 计值Q(x,y) > Rmax,则令Rmax= Q(x,y) ,P(x,y) = 0 ;若某点统计值Q(x,y) ≤ Rmax,则令Q(x,y) = 0 。对处理完参数空间所有点之后,参数空间的非零点即是极大值点,每个极大值点对应一个候选椭圆中心。设求出的n个候选椭圆中心为Oi(i=1,2,…,n),对原参数空间H中的每个点O,在其区域R中寻找统计值大于阈值的点组成点集S,S满足:

式中:比例系数λ=0.8,计算点集S的中心坐标O′ 即为椭圆中心的修正值:

2.2Hough变换求解椭圆参数

为了更准确地计算椭圆参数,可采用Hough变换结合椭圆参数方程求解。在中心点Oi附近寻找关于中心点对称的边缘点进行采样存入数组Vi中。对于任意椭圆,设中心坐标为(x0,y0),椭圆长半轴长为a,椭圆短半轴长为b,椭圆倾斜角为θ。则参数方程为:

将中心坐标Oi(x0,y0)带入椭圆方程式(5)中,从数组Vi中取出数据在三维空间中结合式(5)并采用Hough变换对a,b,θ进行量化投票统计,求出参数空间最大值对应的3个参数即为候选椭圆的a,b,θ。

2.3虚假椭圆判断

对于候选椭圆E(x0,y0,a,b,θ),任意点P(x,y)落在椭圆上的判断公式如下:

以点(x0,y0)为中心选 取长方形 区域D,取 T=0.1,若点P(x,y)∈ D且满足式(6),则认为该点落在候选椭圆上。在区域D中计算原图中落在候选椭圆上的实际边缘点数目N1和组成候选椭圆的边缘点数目N2,因为组成椭圆的点数是随着a,b变化而变化的,所以应该以N1,N2的比值是否大于阈值λ来判断候选椭圆是否为真, 即当N1N2> λ 时,候选椭圆为真。

3实验结果

为验证本文算法检测结果,采用2组图片对本文算法与CMHT算法进行了对比检测实验,重点对椭圆检测的准确度和速度进行考察。用Matlab 7.6编程实现了本文算法 。 测试平台 为普通PC机 ,CPU为Pentium E5300,2 GB内存,操作系统为Windows XP。本文的测试程序把检测到的椭圆用红色和绿色画出,分别表示用CMHT算法和本文算法检测得到的椭圆。第1组实验采用简单的合成图像如图2所示,图像大小为248×180,所需检测椭圆1个。第2组实验为真实大便镜检图像的一部分如图3所示,图像大小为448×350,所需检测虫卵3个。从图2中可以看出,对于简单的图像,2种方法都能正确检测得到椭圆,CMHT算法速度稍快一些(见表1)。但对于图3中背景复杂的大便镜检图像,特别是图中处于右下方的椭圆有明显遮盖的情况,CMHT算法检测的椭圆会出现中心位置不准等较大误差,并且在图像右上方出现误检,而采用本文算法仍能较 快地检测 出多个椭 圆 ,并定位准 确(见表2)。由此可见,本文算法在检测精度和误检率上都有很大改善。

4结语

本文提出了一种基于Hough变换的椭圆检测改进算法。利用对参数空间、椭圆参数计算的改进和虚假椭圆的判断,提高了椭圆检测准确度。由实验结果可以看出,即使在背景复杂的图像中,本文的改进算法也能准确快速地检测各个椭圆的参数,运算速度快,检测性能好,抗干扰性强,具有一定的实用性。

摘要：在背景复杂的图像中,针对多椭圆检测时椭圆中心定位不准、虚假椭圆过多的缺点,提出一种基于Hough变换的改进算法。该算法对参数空间和Hough变换计算的改进提高了椭圆检测的准确度,并利用参数方程判断候选椭圆的真假。实验结果表明,该检测方法具有较强地抗干扰能力,能够在复杂的环境中准确快速地检测出多个椭圆。

关键词：Hough变换,椭圆检测,参数方程,检测方法

改进的Hough变换 篇2

纸币清分机采集图像是在纸币高速进纸过程中进行的,纸币会发生倾斜。因此,倾斜校正是图像预处理部分的重要环节,倾斜校正的好坏对后续的图像分析和识别有较大影响。

纸币倾斜校正包括倾斜角度检测和图像的旋转,其核心在于如何检测出图像的倾斜角。目前,倾斜角检测的方法有许多种,主要可分为5类:基于Hough变换的方法[1]、基于交叉相关性的方法[2]、基于投影的方法[3]、基于Fourier变换的方法和K-最近邻簇方法[4]。针对纸币本身的特点,还有人提出通过搜索纸币的边界角点来确定纸币的倾斜角度[5],该方法虽然实现简单,快速,但是算法鲁棒性较差。当纸币图像本身变形,或者纸币图像存在缺角、折角,或者背景中存在干扰等情况时,纸币图像的四条边界并不构成一个矩形,会获得多于四个的边界角点,从而不能有效检测纸币的倾斜角。

1 Hough变换的基本原理

Hough变换[6]是对图像进行某种形式的坐标变换,它将原始图像中一定的几何形状的直线或曲线变换成参数空间的一个点。即图像空间中给定形状的直线或曲线上的所有点都集中到参数空间中的某个单元而形成局部峰值,这样就把在图像空间中检测直线或曲线的问题变成寻找参数空间中峰值单元的问题。

设直角坐标系中的一条直线方程为:

式(1)中,k为该直线的斜率,b为该直线在y轴上的截距。我们也可用参数表示则为:

式(2)中ρ为从原点到直线的垂直距离,θ为从x轴算起的角度,这条直线在ρ-θ平面中为一点,而在xy平面中通过一点的一簇直线变换到ρ-θ平面时,将形成一条类似正弦曲线的轨迹,也即在x-y平面上一个点对应ρ-θ平面上一条曲线。若在x-y平面上有三个共线点,它们变换到ρ-θ平面上为有一公共交点的三条曲线,公共交点的ρ-θ参数就是共线直线的参数。根据这个原理,可以用Hough变换提取直线,通常将x-y平面称为图像平面,将ρ-θ平面称为参数平面。对于直线的检测问题而言,任意一条直线都可以用参数ρ和θ完全确定下来。

2改进的纸币倾斜校正方法

理论上,对于纸币边界直线的检测,其上下边框对应最长的直线段,因此在纸币图像倾斜检测中可以利用纸币边框为最长直线段的特征,通过Hough变换来搜索累加器A(ρ,θ)的峰值,即找到纸币边框的位置直线。然而在实际应用中,由于图像对比度、纸币扭曲、图像数字化等原因,边界直线往往断裂为若干较短的直线,如图1所示,图中存在11条较短的直线段,都存在于纸币的边界上,如果纸币的倾斜角度为θ,则这些直线段的角度应该接近于θ或(θ+90°)的角度。基于本文方法的纸币倾斜校正的具体步骤为:

(1)对纸币图像运用Sobel算子检测图像边缘,从而得到有效的纸币图像边界。

(2) 使用Hough变换检测图像中的所有直线段,并求取它们的角度。此时直线段分别隶属于纸币的上下边界(θ1)和左右边界(θ2),假设直线段总条数为N。

(3) 去除某些非边界的直线段干扰,确定纸币候选倾斜角度θcand。首先,分别统计步骤(2)中隶属于θ1、θ2的平均值θ1c、θ2c,及对应直线段条数n1、n2(有n1+n2=N),然后根据服从多数原则选取直线段较多的一类作为纸币的候选倾斜角度θcand

此时,还无法确定θcand是上下边界还是左右边界的角度。

(4) 通过旋转反馈的方法确定纸币最终的倾斜角度θskew。首先,分别将边缘图像旋转θcand和-θcand角度,获得边缘图像frot+和frot-;然后,对frot+和frot-进行水平和垂直投影,获取对应的边界(u+,d+,l+,r+)和(u-,d-,l-,r-),并计算纸币投影长宽比:

最后,和实际纸币长宽比ratereal最接近的角度即为纸币的倾斜角度θskew

(5) 将图像旋转θskew角度,如图2所示为倾斜校正后的纸币图像。

3 实验与分析

为了验证本文改进方法对纸币倾斜角度检测的有效性,本文对大量纸币图像进行了实验。此外运用本文方法对已分割的车牌图像进行倾斜校正。

如图3,初步分割后的车牌图像存在一定的倾斜,在识别等处理前需要对其进行倾斜校正。运用本文方法检测到倾斜角度为3°,图3(d)是倾斜矫正后的车牌图像。实验结果表明,本文的倾斜校正方法除了用于纸币图像外,也可用于如车牌等其他类似的图像处理中,具有较好的鲁棒性。

4 总结

人民币图像在采集到的整个图像区域会有小幅度的倾斜和偏离正中。本文使用Hough变换检测图像中的所有直线段,并求取它们的角度。此时直线段主要分布在纸币的上下边界θ1和左右边界θ2,二者是近似垂直的,为了去除某些非边界的直线段干扰,算法首先分别统计θ1,θ2的平均值及对应直线段条数,然后根据多数原则选取直线段较多的一方作为纸币的倾斜角度θcand,此时θcand是纸币偏离水平轴的角度,但无法确定其顺时针偏离还是逆时针偏离。本文通过反馈的方法确定纸币倾斜角度。分别进行顺时针和逆时针旋转边缘图像,然后采用投影法获取旋转后纸币的上下以及左右边界,根据先验知识(纸币长宽比)确定θcand的方向。继而采用插值和背景补零的方式对人民币进行倾斜校正。

摘要：纸币清分机采集图像是在纸币快速进纸过程的情况下实现,不可避免地会发生倾斜,这为后续的图像分割和识别带来了困难。针对图像中纸币边缘检测结果通常断裂为若干直线段的现象,提出了一种基于Hough变换的改进倾斜矫正算法,能够较准确地检测到图像的倾斜角度,从而实现纸币图像的倾斜矫正。

关键词：纸币,倾斜校正,旋转反馈

参考文献

[1] Le D S,Thoma G R,Wechsler H.Automated page orientation andskew angle detection for binary document images.Pattern Recogni-tion,1997;27(10):1325—1344

[2] Yan J H.Skew correction of document images using interline cross-correlation.Vision Graphics Image Process:Graphical Models andImage Process,1993;55(6):538—543

[3] Steiherz T,lntrator N,Rivlin E.Skew detection via principal compo-nent analysis.In:Proceeding of International conference of Documentanalysis and Recognition,Bangalore,India,1999:153—156

[4] O'Goman L.The document spectrum for page layout analysis.IEEETrans Pattern Anal Machine Intell,1993;15(11):1162—1173

[5]童春.纸币面值与编号识别的算法研究.广州:中山大学硕士学位论文.2008

改进的Hough变换 篇3

给定一幅图像(一般为二值图像)中的一个点集合,我们想要找到位于直线上的所有点的子集。一种可能的解决方法就是先找到所有由每一对点决定的线,然后找到接近特殊的所有点的子集。这种处理方法的问题是它需要n(n-1)/2-n2条线,然后进行n(n(n-1))/2-n3次每一点与所有线的比较。这种方法计算起来很麻烦,因而一般不采用。霍夫变换HT(Hough Transform)是图像分析中对二值图像进行直线检测的有效方法[1,2],因此是一种应用非常广泛的图像边缘检测技术。这种变换所需要的计算时间和储存量随参数空间的维数增加呈指数增加,为此,不少学者针对不同的应用场合,就基于Hough变换的直线检测提出了许多种改进的算法[3,4,5]。本文提出一种改进的Hough变换用于矩形的检测。

1 Hough变换的原理[6,7]

采用Hough变换时,我们考虑一个点(x,y)和所有通过该点的线。点(xi,yi)的线有无数条,这些线对某些a 值和b值来说,均满足yi=axi+b。将该公式写为b=-xia+yi并考虑ab平面(也称为参数空间),可对一个固定点(xi,yi)相关的直线相交于点(a′,b′),其中a′和b′分别是xy平面上包含点 (xi,yi)和(xi,yi)的直线的斜率和截距。事实上,在这条直线上的所有点都有在参数空间中相交于点(a′,b′)的直线。

从原理上讲,我们可以绘制出与所有图像点(xi,yi)相对应的参数—空间直线,而图像直线可以通过许多参数—空间直线相交来识别。然而,这种方法的实际困难是a(直线的斜率)接近无限大,也就是接近垂直方向。解决该困难的一种方法是使用直线的标准表示法:

xcosθ+ysinθ=ρ,对于水平线来说,θ=0,ρ等于正的x截距。同样,对于垂直线而言,θ=90°,ρ等于正的y截距,或θ=-90°,ρ等于负的y截距。

Hough变换计算上的诱人之处是把ρθ参数空间细分为了所谓的累加器单元。一般来说,值的最大范围是-90°≤θ≤90°和D≤ρ≤D,其中D是图像中角点间的距离。坐标点(i,j)处的单元(累加器的值为A(i,j))对应于与参数空间坐标(ρi,θj)相关的文武。最初,这些单元被设为零。然后,对于图像平面上的每一个非背景点(xk,yk),我们令θ等于θ轴上允许的细分值,并通过公式ρ=xkcosθ+yksinθ 求出相应的ρ值。然后,将得到的ρ值四舍五入为最接近的、ρ轴上允许单元值。相应的累加器然后增加。在这个过程的最后,A(i,j)意味着xy平面上的Q个点位于线xcosθj+ysinθj=ρi上。ρθ平面上的细分数决定了这些点共线的精度。

2 预处理

完成基于Hough变换的图像直线特征的提取,对图像进行一些预处理是必不可少的。

2.1 边缘检测

为提高Hough变换的计算速度,使参加Hough变换的点不是整幅图像的每个像素,采用边缘检测即从图像平面中提取边缘点或特征点,由这些特征点参加以后的Hough变换。本文采用了先对待测图像进行平滑,然后再用Canny[8]算子检测房屋的边缘。这样,能够减少图像中的噪声点,以提高边缘检测的准确性。

2.2 二值化处理与细化[9]

采用“双峰法”确定灰度阈值,将灰度图像二值化变为二值图像。同时,若上述检测出来的特征点均参加Hough变换,由于该特征点形成的边缘表现出一定的宽度,会导致在Hough变换的过程中聚类的混乱,而得不到精确的参数信息。采用细化算法对上述结果进行细化,可减少参加Hough变换的点数。

3Hough变换对建筑的边缘特征检测的实现与实验结果

理想情况下,用edge边缘只产生边缘上的像素。实际上,结果像素由于噪声、不均匀照明引起的边缘断裂和杂散的亮度不连续而难以得到完全的边缘特性。因此,典型的边缘检测算法遵循用链接过程把像素组装成有意义的边缘的方法。一种寻找并链接图像中线段的处理方式是Hough变换[6,7,8]。

3.1 峰值检测

使用Hough变换进行线检测和链接的第一步是峰值检测。在Hough变换中找到一组有意义的明显峰值是一种挑战。因为数字图像的空间中的量化、Hough变换的参数空间中的量化以及典型图像的边缘都不是很直,Hough变换的峰值一般都位于多个Hough变换单元中。解决这个问题的一个方法如下:

(1) 找到包含有最大值的Hough变换单元并记下它的位置。

(2) 把第一步中找到的最大值点的领域中Hough变换单元设为零。

(3) 重复该步骤,直至找到需要的峰值数为止,或者达到一个指定的阈值时为止。

根据上述思想编写了自定义函数houghpeaks来实现。

3.2 找受影响的峰值的非零值点

一旦在Hough变换中识别出了一组候选的峰值,则它们还要留待确定是否存在与这些峰值相关的线段以及它们的起始和结束位置。对每一个峰值来说,第一步是找到图像中影响到峰值的每一个非零值点的位置。为达到此目的,用自定义函数houghpixels来实现。

3.3 相关点连成线段

使用函数houghpixels找到的相关的像素必须组合成线段,可以用面的策略来实现:

(1) 将像素位置旋转90°-θ,以便它们大概位于一条垂直线上;

(2) 下班按旋转的x值来对这些像素位置分排序;

(3) 使用函数diff找到裂口。忽视掉小裂口;这将合并被小空白分离的相邻线段;

(4) 返回比最小阈值长的线段的信息。

这个策略用自定义函数houghlines来实现。

3.4 实验结果

我们将用函数:hough,houghpeaks,houghpixels,和houghlines来寻找二值图像中的一组线段。首先,用一比默认值细的角度间隔(Δθ=0.5)来计算并显示Hough变换。接下来用函数hougheaks找到6个看起来比较明显的Hough变换峰值。图1显示了带有峰值位置重叠的Hough变换。最后用函数houghlines来查找并链接线段,图2中显示了结果,其中检测到的线段叠加为灰色的粗线。

从实验结果中可看出,由于Hough变换的定位精度低及存在过连接线(点)等问题,难以实现直线的高精度快速检测。

4 对Hough变换进行边缘检测的改进方法

根据提出的Hough变换所存在的缺点,提出改进的算法,即基于Hough变换的矩形(正方形、长方形)的检测。

4.1 改进算法的原理

首先介绍以下直线的极坐标方程。将方程ρ=x*cosθ+ y *sinθ 转换成:y=k*x+b,其中k=(-cosθ1)/(sinθ1)和b=ρ1/(sinθ1)+ Oy - Ox*k,(Ox,Oy)为中心坐标。用C(ρ,θ)表示累积值数组。

HT空间中的四个顶点分别为:H1=(ρ1,θ1),H2=(ρ2,θ2),H3=(ρ3,θ3),H4=(ρ4,θ4),四个顶点的一般关系:

(1) 当θ=α1时,形成了H1,H2,即有H1,H2点。当θ=α0时,形成了H3,H4,即有H3,H4点。

(2) 判断是否与θ对称,若以θ轴为对称轴,则有:

ρ1 +ρ2=0 ρ3 +ρ4=0

(3) 直线垂直时Δθ=90° (|α1 –α0|=90)。

(4) 线段的长度:

C(ρ1,θ1)=C(ρ2,θ2)=b C(ρ3,θ3)=C(ρ4,θ4)=a

(5) 点或直线的距离:ρ1-ρ2=a;ρ3 -ρ4=b。

大部分情况下,满足条件(1),(2),(3)。

4.2 算法描述

(1) 找到一个点,在距离[Dmin,Dmax]之间搜索;

(2) 增强C(ρ,θ)模型;

(3) 检测矩形类型。

若在增强之后的C(ρ,θ)中有H1=(ρ1,θ1),H2=(ρ2,θ2)…Hm=(ρm,θm)。

根据Δθ=|θi –θj|< Tθ,注:Tθ表示域值。

Δρ=|ρi+ρj|<Tρ|C(ρi,θi)-C(ρj,θj)|<TL *

(C(ρi,θi)+C(ρj,θj))/2

判断直线i,j是否有关联。若满足上面的关系表达式,就说明有关联。

令Pk=(+/-yk,αk),条件: αk=1/2 *(θi +θj);

yk=1/2 *(ρi-ρj)。

下一步:判断直角线,垂直线:Δα=||αk-αl|-90|<Tα(域值)。

则直线Pk,Pl是垂直的。最后,可以检测到矩形的中心点。方向为αk,两边的长度为2yk与2y1。

4.3 改进方法的优点

由于Hough变换具有明显的几何解析性、良好的抗噪声性能和对间断直线影响不敏感、易于实现并行处理等优点,因此是一种应用非常广泛的图像边缘检测技术。通过实验可以证明它改进了直线检测的一些缺点,如可以精确定位,消除过连接线(点)等的问题,并且该方法使得对矩形的检测可以在一个二维空间上进行,缩短了计算时间,减小了空间复杂度,提高了效率。

5 结束语

通过Hough变换进行房屋边缘的直线检测,由分析可知它存在着一些缺点如定位精度低及存在过连接线(点)等问题,难以实现直线的高精度快速检测,基于此提出了检测矩形的Hough变换的改进算法,实验证明此方法是行之有效的。但也存在一些缺点,如在检测不很明显的角度时效果不佳,在以后的研究中应该针对角度检测进一步地改进。

摘要：Hough变换是对二值图像进行直线检测的有效方法,介绍了Hough变换直线检测对房屋边缘特征检测方法及实验结果,并根据其存在的缺点提出了检测矩形的Hough变换的改进算法。

关键词：Hough变换,边缘检测,矩形检测,Canny算子,灰度阈值

参考文献

[1]Li H F,Derek Pao.Improvements and systolic implementation of theHough transformation for straight line detection.Pattern ecognition,1989,22(6):697-706.

[2]Illingworth J,Kittler J.A survey of the Hough transform.Computer Vi-sion,Graphics&Image Processing,1988,44:87-116.

[3]Clement T P.The extraction of line-structured data from engineeringdrawings.Pattern recognition,1981,14(1):43-52.

[4]Nagasamy V,Langna N A.Engineering drawing processing and vector-ization system.Computer Vision Graphics and Image Processing,1990,49:379-397.

[5]Wu Zhongquan.The robust algorithms for finding the center of arc.Computer Vision and Image Understanding,1995,62(3):269-278.

[6]Gonzalez R C,Woods R E.Digital Image Procesing.2nd ed.,PrenticeHall,2002:460-182.

[7]Castleman K R.Digital Image Processing.Prentice Hall,1996:400-106.

[8]Gonzalez R C,Woods R E,Eddins S L.Digital Image Processing UsingMATLAB.Prentice Hall,2004:286-304.

改进的Hough变换 篇4

关键词：车辆测距,边缘检测,Hough变换,特征提取

0 引言

Hough变换是模式识别领域中对二值图像进行直线检测的有效方法, 它检测已知点的共线性, 是一种全局性的检测方法。当已知数据点集中存在干扰点或噪声时, 可以很好地抑制干扰或噪声, 同时还可以将已知数据的点集拟合成多条直线。Hough变换的传统应用是检测直线, 目前也扩展到用Hough变换检测圆和椭圆。

工程上经常要进行曲线检测或拟合, 对圆形器件或图标进行模式识别和定位是一个常见的问题。在计算数学中圆检测有多种方法, 常用的有:基于圆形边缘积分特性的环路积分微分法[1]、对边界区域进行分区迭代拟合的检测算法、基于最小二乘原理进行拟合的检测算法、通过计算圆形目标的灰度重心提取圆心坐标的Wong-Trinder圆定位算子和模板匹配法、组合法[2]、鲁棒性估计法[3]、形状分析法等;此外还有一类通过代价函数的全局优化来提取几何基元的方法, 如:模拟退火算法、遗传算法[4]、Tabu搜索 (禁忌搜索) [5]等。这些算法 (或其组合) 虽然在一些特定的场合己经得到应用, 在定位精度和计算速度等方面也取得了令人满意的结果, 但是这些方法的使用范围往往有限, 并且不能在底层DSP上运行。本文提出基于圆斜率特性改进圆Hough变换对目标物体进行特征提取以实现测距。

1 Hough变换

1.1 圆的Hough变换原理

Hough变换常常被用于直线段、圆和椭圆的检测。其基本思想是将图像的空间域变换到参数空间, 用大多数边界点满足的某种参数形式来描述图像中的曲线 (区域边界) 。通过设置累加器进行累加, 求得峰值对应的点就是所需要的信息。

下面介绍一下基本的圆检测Hough变换[6]。假设希望在图像平面 (X-Y平面) 考察并确定一个圆周, 令{ (xi, yi) i=1, 2, 3, …, n}为图像中欲确定圆周上的点的集合, 而 (x, y) 为集合中的一点, 它在参数坐标系 (a, b, r) 中方程为:

(a-x) 2+ (b-y) 2=r2 (1)

该方程为三维锥面, 对于图像中任意确定的一点均有参数空间的一个三维的锥面与之对应。对于圆周上的任何点集合{ (xi, yi) }, 这些三维锥面构成圆锥面簇, 如图1所示。

若集合中的点在同一个圆周上, 则这些圆锥簇相交于参数空间上某一点 (a0, b0, r0) , 这点恰好对应于图像平面的圆心坐标及圆的半径。对于离散图像, 式 (1) 可写为:

 (a0-xi) 2+ (b0-yi) 2-r2≤ξ (2)

其中, ξ是考虑到对图像进行数字化和量化的补偿。Hough变换的基本思想在于证据积累, 一般情况下圆变换的参数空间为三维, 在三维积累空间上进行证据累加的时间空间消耗非常大, 在具体应用中几乎是不可能的, 也是不现实的。基于此, 提出基于圆斜率特性的改进圆Hough变换。

1.2 基于圆斜率特性的改进圆Hough变换

从图2可以看出 (采用不同的梯度算子方向可能不同, 在本文中以图2所示的方向为准, 其它可以类推) :

①关于y轴对称的圆边界点 (如a与b) 垂直梯度的方向和大小相同, 水平梯度的大小相同, 方向相反;关于X轴对称的点 (如a与c) 水平梯度的方向和大小相同, 垂直梯度的大小相同、方向相反。在数字图像中, 利用Sobel算子求出的梯度虽然并不精确, 但是这一对应关系却始终成立, 在噪声比较大的情况下, 即使大小不再相等, 方向关系往往依然成立。

②各轴对称点联线的垂直平分线过圆心O, 圆心位于和各点垂直梯度方向相反、水梯度方向相同的位置。

以图3为例, 根据梯度大小和方向, 找出圆上一点A, 然后在水平方向向右搜索, 找出另一点E, 求出AE中点B (xb, yb) 。由于圆心在弦的中垂线上, 在AE的中垂线上, 沿着垂直梯度反方向, 以步进为1求出下一个点C (xc, yc) , 求出C点到A或者E的距离r, 将 (xc, yc, c) 在参数空间中进行累加。然后继续以步进为1求下一个点D, 直到y域r超出设定范围。然后继续寻找下一个符合条件的A点和E点。

2 测距的实现

要实现目标图形在图像中的距离测量, 需要建立测距模型, 搭建测距程序, 组织测距试验, 完成前车距离的计算。

2.1 目标图形特征提取的实现

下面是对特征提取算法的可靠性检验, 在测试面板中共放了三个圆, 其属性为一个小圆和两个同等大小的大圆。检测目的通过设定程序中圆的半径来检测出不同需求的圆。效果如图4所示。

实验表明如果图像中干扰点少且半径检测范围比较有限时, 该方法和其它方法计算时间差不多。随着半径范围的增大和可剔除非圆点的增加, 两者的差距逐渐明显。对不存在对应点的点不进行变换计算。利用梯度信息对图像中的所有像素点进行筛选, 减少了变换的计算量。实验表明, 图像中非圆点对普通Hough变换的影响远远大于对该点算法的影响, 可剔除的非圆点越多, 本文提出的算法的加速效果越明显。

对于半径变化范围大的环境特别有效, 和普通Hough变换每点的半径计算范围 (0, MaxR) 不同, 通过对最小半径的估计, 计算范围仅仅为 (distance (a, b) /2, MaxR) 。

从以上试验可以看出来, 通过基于圆斜率特性的改进圆Hough变换来实现图形的特征提取是可靠稳定的。

2.2 建立试验模型

本文的试验模型是一个单孔摄像头和一个带有目标检测图形的移动物体, 其中目标检测图形在本实验中采用如下方案:两个圆心在同一条直线上, 具有相同的半径的、颜色均匀的、形状规则的圆形, 检测图形如图5所示。

由于实验基础的实际应用环境是两个塔吊之间的安全运行, 其两塔吊间距范围是2m～30m。为防止两个塔吊出现相撞的事故, 在两个塔吊相距2m时安全驾驶系统会使两塔吊强行紧急制动, 本功能的实现是在底层DSP上执行的, 用于研究两塔吊间距离的问题。

2.3 测试结果

通过比较检测试验获得的距离与实际距离, 证明该方法能够较准确地检测前方车辆的距离, 图像处理与计算速度可达到每秒2帧, 表明该方法简洁有效, 具有可操作性, 能够通过一系列操作较准确地获得前方车辆距离, 是一种可行的车距测量方法。试验测试结果如表1所示。

3 结束语

依据图像处理的基本理论与方法, 提出一种基于数字图像处理的测距方案。通过对试验数据与图像的分析, 获得以下结论:

①基于圆斜率特性的改进圆Hough变换对图像中特定图形的特征提取做了验证, 证明该算法是可靠稳定的, 并且大大缩减了运算量, 能够应用于DSP (C6416) 上。同时, 该算法经过适当的改进, 也可应用到图像自动识别方面。

②该算法为现场应用奠定了理论基础, 并应用在某货场, 实现了大型移动吊车之间的准确测距。

参考文献

[1]Daugman J G.High Confidence Visual Recognition of Persons by aTest of Statistical Independence[J].IEEE Trans on Pattern Analysisand Machine Intelligence, 1993, 15 (11) :1148-1161.

[2]Veelacert P.Constructive Fitting and Extraction of Geometric Primitives[J].Graphical Models and Image Processing, 199, 59 (4) :233-251.

[3]Chen D S.A Data-Driven Intermediate Level Feature Extraction Algo-rithm[J].IEEE Trans on Pattern Analysis and Machine Intelligence, 1989, 11 (7) :749-758.

[4]Yin Pengyeng.A New Circle/Ellipse Detector Using Genetic Algo-rithms[J].Pattern Recognition Letters, 1999, 20 (7) :731-740.

[5]唐氓, 李军, 胡占义.随机Hough变换与Tabu搜索算法在基元提取中的比较[J].计算机学报, 1999, 22 (1) :56-65.

[6]Kimme C, Balland D, Sklansky J.Finding circles by an array of accu-mulators[J].Common, ACM, 1972, 15 (1) :11-15.

Hough变换的车道线并行检测 篇5

1 Hough变换原理

Hough变换的原理是利用图像空间和Hough参数空间的点、线对偶性[4]。通过在参数空间里进行简单的累加统计，然后在Hough参数空间寻找累加器峰值的方法检测直线。Hough的基本原理如图1[5]所示，可看出xy平面上的任意一条直线对应pθ平面上的一个点，如图1(b)和图1(c)所示

为找到xy平面上的直线，文中可将ρθ空间量分成等间隔的小网格，每个小格对应一个计数阵元。根据式(2)可知每一个(x0,y0)点对应ρθ平面上的一条曲线，这条曲线所经过的小格，对应的计数阵列元素加1。根据上述原理遍历感兴趣区域中的全部(x,y)点，大计数值的小格对应于共线点其中小计数值的小格则认为是孤立点，不构成直线，应该去除。

用Hough变换识别车道线，抗噪性能强，对直线断裂、局部遮挡等缺陷不敏感，能将断开的边缘相连接，适用于检测不连续的车道线。

2 并行处理

实际检测时，一幅图像要检测出两条车道线，由于在一个CPU上只运行一个进程，因此检测过程数据处理量大、检测速度慢。现将一幅待检测的图像分成左右两幅小图像，即把左右两条车道线分开。然后将两幅小图像分配给两个CPU进行处理，并将其中一个CPU设定为主进程，另一个设为从进程，两个CPU同时对所接收到的图像数据进行处理，各进程完成自身所承担的任务后将运算结果返回给主进程，主进程将另一个从进程的运算结果接收完毕并结合自身进程的运算结果，统一对其进行处理，最终得到检测结果。

2.1 图像预处理

两个CPU分别对左右车道线进行检测，所以先将图像分成左右两部分。因为摄像头安装在汽车的中间位置，所以拍摄的左右车道线基本上是以图像的中间为对称，则以中间为界将图像分解为左右两部分。图像的上半部分多为背景，则可将分解后的左右两边的图像只截取下半部分，那么实际上要处理的有效区域是原图像的左下1/4和右下1/4。图像分解示意图如图2所示。

对分解得到的左右两边的图像进行灰度化，再进行滤波，然后再对滤波后的图像进行二值化。

2.2 检测车道线

首先利用Hough变换对二值化后的图像求直线。由于检测出的直线除了车道线之外可能还有干扰直线，所以要将干扰直线去掉[6,7,8]。因拍摄左右车道线的斜率均是在一个范围内变化的，且变化较小，则可根据斜率来去除干扰直线，然后分别将左右图像上检测出的多条直线连接起来，从而求出两条有宽度的完整车道线[9]。

因利用Hough变换检测出的两条完整的车道线的灰度值为255，文中将在原图像上对应的像素点的G和B值置零，R值置255，原图像上的其他像素点不变，则会在原图像上的左右车道线的位置上分别得到一条红色的线，即检测出的车道线[10]。

3 程序设计流程

本文的实验程序代码是利用C++语言结合Visual Studio 2008软件开发系统编写，并制作了一个基于对话框的简单界面，方便车道线检测的操作。图3是本文的并行车道线检测算法的程序流程图。

由图3可知，车道线的检测过程为:将载入的完整图像分解为左右两个感兴趣区域，分别送给两个CPU进行并行处理，先将图像灰度化、滤波，然后分别求出路面灰度值，根据所求的灰度值进行二值化，对二值化后的图像进行Hough变换，然后根据Hough变换所求的多条直线分别求出一条完整的车道线，最后将并进检测出的两条车道线汇总。

其中二值化是一个重要步骤，二值化结果的优劣直接影响到Hough变换检测直线的质量，所以要选择一个合适的二值化阈值。由图2可知，分解得到的左图像的右下区域和右图像的左下区域基本都是路面区域，则分别求出左图像右下区域和右图像左下区域像素的均值T1和T2，近似看成路面的平均灰度值。左右车道线的灰度值要比求出的左右路面的灰度值大，实验证明以T1+50和T2+60分别作为左右图像二值化的阈值，得到的二值化图像较好。因为左车道线比较靠近路边，则左车道线受环境变换影响较大，相比右车道线灰度值稍小，所以对分解后的左右图像进行二值化的阈值选取也有所不同。

4 检测结果及分析

在由两个双CPU节点组成的集群系统上实验，节点CPU采用处理器。试验中选用的图像在行驶的汽车上用手机拍摄，图像大小为640×360。表1是传统的串行方法和本文所应用的并行方法检测多幅图像时分别求出所用的平均时间。由于左车道线是实线，而右车道线是虚线，则利用Hough变换时参数有所不同，所以检测车道线所用的时间也有所差异。

并行运算结果表明:采用两个CPU并行检测左右车道线比传统串行检测方法的速度提高了39.1%。图4和图5所示分别是车道线串行检测和并行检测结果图。

由图4和图5可看出，传统串行检测方法检测的结果没有并行检测方法的检测结果好。第20帧、70帧、410帧的左车道线以及第130帧、370帧的右车道线的对比结果比较明显。利用Hough串行检测左右车道线时，参数设置相同，往往不能兼顾左右两条车道线。而利用Hough并行检测左右车道线时，可根据左右车道线具体情况分别设置参数求直线，所以并行检测效果更好。

5 结束语

利用Hough变换检测车道线采用多CPU并行处理的方式相比传统的串行处理方式，不仅大幅缩短了检测时间，且由于检测左右车道线时是相互独立的，所以可根据左右车道线的具体情况来分别设定参数，这样的检测效果比串行检测更好。

下一步的工作包括如何在并行检测的情况下优化算法，从而提高检测速度和质量，以及如何通过增加CPU的个数进一步减小检测速度。

参考文献

[1]徐岩,雷涛.基于形态学方法的车道线检测算法研究[J].铁道学报,2009,31(1):107-110.

[2]陈龙,李清泉,毛庆洲.基于成像模型的车道线检测与跟踪方法[J].中国公路学报,2011,24(6):96-102.

[3]孙伟,张小瑞,唐慧强,等.Hough变换和最小二乘拟合的车道线协调检测[J].光电工程,2011,38(10):13-19.

[4]谢茜.基于视觉的车道线检测与识别[D].武汉:武汉理工大学,2013.

[5]刘富强,张姗姗,朱文红,等.一种基于视觉的车道线检测与跟踪算法[J].同济大学学报:自然科学版,2010,38(2):223-229,306.

[6]Liu Z,Wang S,Ding X.ROI perspective transform based road marking detection and recognition[C].Shanghai:2012 International Conference on Audio,Language and Image Processing(ICALIP),2012.

[7]Li W,Gong X,Wang Y,et al.A lane marking detection and tracking algorithm based on sub-regions[C].Qingdao:2014 International Conference on Informative and Cybernetics for Computational Social Systems(ICCSS),2014.

[8]Liu X,Dai B,Song J,et al.Real-time long-range lane detection and tracking for intelligent vehicle[C].Hefei:2011Sixth International Conference on Image and Graphics(ICIG),2011.

[9]Wang J,An X.A multi-step curved lane detection algorithm based on hyperbola-pair model[C].Hong Kong and Macau:2010 IEEE International Conference on Automation and Logistics(ICAL),2010.

改进的Hough变换 篇6

智能车辆是一个集环境感知、规划决策、自动驾驶等多种功能于一体的综合系统。随着智能车辆控制技术的日趋成熟,决定其能否进一步应用于更加复杂、恶劣工作环境的关键是其导引技术[1]。本文采用的有线式视觉导引技术具有获取信息容量大、图像处理速度较快和方法简单实用等优点,是目前智能车辆导引技术的主流方向[2,3]。

视觉导引技术的关键是通过图像处理技术,将道路边缘特征从图像背景中分离出来,从而定位出车辆行驶的正确位置,以便对其行驶进行有效地控制。本文介绍一种基于自适应阈值分割及Hough变换的道路边缘提取方法。试验结果表明,此方法对较复杂的道路环境具有较好的适应性,能提高整个智能车辆系统运行的可靠性。

1 道路图像的边缘提取

在智能车辆运行过程中,由于摄像机安装位置距离地面较近,拍摄到的图像是近视野图像,因此,可以将图像中的道路边缘近似看成直线,这样既能保证一定的准确性,又能减少计算量。道路边缘图像的形状特征为一连续的、具有一定宽度的直线;边缘线与路面背景具有强烈的对比度,在灰度图像中表现为灰度值差别较大,路面背景有时比较杂乱[4,5]。依据道路边缘图像的特点,笔者先应用中值滤波及维纳滤波对图像进行预处理;其次,利用自适应阈值法对预处理后的图像进行分割;然后,采用数学形态学对分割后的图像去噪。

1.1 图像预处理

在实际的图像获取过程中,由于路面情况比较复杂,可能存在污迹、杂物干扰,在采样量化、传递时都会带来噪声。针对这些情况可采用维纳滤波进行图像的噪声处理,维纳滤波可实现自适应去噪,对白噪声滤波效果较好。

由于摄像机获取的道路图像对比度较低,可以使用直方图灰度变换来改善图像的对比度,图像处理中经常用到的直方图均衡化就是使输出像素灰度的概率密度均匀分布的灰度方法。Matlab的图像处理工具箱提供一个灰度变换函数imadjust来实现图像的直方图调节。Imadjust将图像的灰度值重新进行映射,使之填满整个灰度值允许的范围[0,255]。

1.2 道路边缘分割

分割采用阈值技术,用一个或几个阈值将图像的灰度直方图分类,认为图像中灰度值在同一个灰度类的像素属于同一个物体。在实际情况中,由于光照条件和路面对光的反射性能时常变化,因此,必须采用自适应阈值法[6],以适应光线动态变化,实现对道路边缘的最佳分割,本文采用迭代算法来求取最佳阈值,算法步骤如下:

步骤1 选择一个初始阈值的估计值T0:

${\rm T}{}^0=\frac{{\rm Z}{}_{\min }+{\rm Z}{}_{\max }}{2}(1)$

式中:Zmin、Zmax分别为图像的最小、最大灰度值。

步骤2 利用阈值T0将图像分割为2组,R1和R2

$\begin{array}{l}R{}_1=\langle f(x,y)|f(x,y)\ge {\rm T}{}^k\rangle \\ R{}_2=\langle f(x,y)|f(x,y)<{\rm T}{}^k\rangle \end{array}(2)$

步骤3 计算2组的灰度均值Z1和Z2:

${\rm Z}{}_1=\frac{{\displaystyle \sum _{R{}_1}{\rm I}}(x,y)}{{\rm N}{}_1}{\rm Z}{}_2=\frac{{\displaystyle \sum _{R{}_2}{\rm I}}(x,y)}{{\rm N}{}_2}(3)$

式中:N1、N2分别为R1和R2中的像素点个数。

步骤4 选择新的阈值Tk+1:

${\rm T}{}^{k+1}=\frac{{\rm Z}{}_1+{\rm Z}{}_2}{2}(4)$

步骤5 如果Tk=Tk+1,则结束,否则K=K+1,转步骤2。

1.3 基于数学形态学的图像去躁

经过阈值分割后,由于路面存在差异,还存在许多离散的小斑点,而且,道路边缘非常毛糙,影响边缘的提取。对此可采用数学形态学的“闭”运算进行处理。A用B来闭合记为A·B,其定义如下:A·B=(A⊕B)ΘB,即A先被B膨胀,再被B腐蚀。其中膨胀运算符为A⊕B,腐蚀运算符为AΘB。经过处理后可以去除图像中的大部分噪声。

2 Hough变换直线边缘提取

在进行边缘提取之前,先将二值图像中的道路边缘和路径用边缘检测的方法检测出来。可采用数学形态学中的“腐蚀”运算来进行边缘检测,也可以利用各种边缘检测算子来检测边缘。

由于拍摄到的图像是近视野图像,因此,将图像中的道路边缘和路径可近似地视作直线,所以利用Hough变换进行道路边缘提取。Hough变换方法是利用图像全局特性而直接检测目标轮廓,其在预先知道区域形状的情况下,可以得到边界曲线,而将不连续的边缘像素点连接起来,并可以直接分割出某些已知形状的目标。其原理如下。

在参数空间中,曲线的形状取决于用于表示曲线的原始函数。常常使用直线的极坐标形式,这样可以避免直线为垂直线时带来的问题。直线的极坐标方程为

$\rho =x\text{c}\text{o}\text{s}\theta +y\text{s}\text{i}\text{n}\theta (5)$

上述方程中,点(x,y)被映射到空间(ρ,θ)上,如图1所示。如果直线上有n个点,那么这些点就对应参数空间(ρ,θ)上的n条正弦曲线。并且所有正弦曲线都经过(ρ,θ)上的同一个点,如果对求n点的最佳直线拟合感兴趣,可以使用图像空间到参数空间的映射方法,这种方法就是Hough变换[7,8]。Hough变换常把参数空间设计成一个累加器阵列,表示离散参数值。

依照变换方程,图像中的每一点可以表示几个参数,而参数空间的峰值就是表征一条直线的参数。Hough变换算法具体如下。

1) 适当地量化参数空间。

2) 假如参数空间的每一个单元都是2个累加器,将累加器初始化为0。

3) 对图像空间的每一个点(x,y),在其所满足的参数方程对应的累加器上加1。

4) 累加器阵列的峰值就是对应模型的参数。

Hough变换的优点是其抗噪性能比较好,并且能连接共线短直线。

3 试验结果

针对结构化道路边缘和路径的灰度图像进行了大量的试验。图2为原始图像经过预处理和自适应阈值分割后的结果。

从图2中看到,经过滤波处理后的噪声点明显减少了,有利于后续的处理;经自适应阈值分割后,道路边缘与路径明显从路面背景中清晰地分离出来,分割效果较好。为后续的Hough变换提供较为“干净”的图像数据。

图3给出了分割后经过数学形态学处理后的试验结果。从图3中可以看到,经过形态学“闭”运算的进一步去噪以及“腐蚀”运算的边缘检测,道路的边缘以及路径被有效地提取出来。图4为Hough变换直线边缘提取后的试验结果。

根据道路边缘线和路径的结构特点,利用Hough变换的算法在Matlab环境下进行直线提取。在图4中,矩形框部分为笔者获取的道路左右边缘,可看到已清晰地将边缘线和路径从图像中提取出来,结果比较理想,达到了本文研究的目标。

4 结 论

针对智能车辆中视觉导引技术里的道路边缘提取问题,笔者利用图像处理技术,实现了道路边缘线和路径标识线有效识别和提取。其中采用的最优阈值分割法,可以将道路边缘和路径标线清晰地从路面背景中分割出来,其分割效果较理想。采用的Hough变换直线提取算法,在Matlab环境下通过相关语句的编程,大量图像处理试验的结果表明,在分割后的图像中,能较好地将道路的边缘线以及路径标识线较准确地识别出来,为后续的车辆行驶路线定位和控制提供了有效的前提。该方法能够适应各种比较复杂的道路环境,且具有较强的抗干扰能力,自适应性和鲁棒性好,提高了整个智能车辆视觉感知系统的可靠性和适应性。

参考文献

[1]胡小峰,赵辉.Visual C++,Matlab图像处理与识别实用案例精选[M].北京:人民邮电出版社,2004

[2]陈超,叶庆泰.基于图像引导的自动导引小车系统设计[J].机械设计与研究,2004,20(1):65-67

[3]张海波,原魁,周庆瑞.基于路径识别的移动机器人视觉导航[J].中国图像图形学报(A辑),2004,9(7):853-857

[4]王荣本,徐友春,李庆东,等.AGVS图像识别多分支路径的研究[J].中国图像图形学报(A辑),2000,5(8):632-637

[5]钟家祯,王韧,戈素贞.自主式AGV的路径规划及导引[J].物流技术与应用,1997,2(1):14-17

[6]吴谨,李娟,刘成云,等.基于最大熵的灰度阀值选取方法[J].武汉科技大学学报:自然科学版,2004,27(1):58-60

[7]文贡坚,王润生.一种稳健的直线提取算法[J].软件学报,2001,12(11):1 660-1 666

改进的Hough变换 篇7

在单张成品检测中, 人们一般通过获取全局图像特征进行检测并进行校正, Hough算法由于其良好的鲁棒性和抗干扰能力, 使之在图像角度检测上具有非常重要的利用价值。但是由于传统的Hough算法所需的计算量大, 运算速度慢, 从而阻碍了其在产品检测上的进一步应用。

本文提出了一种基于快速Hough算法的局部检测方法, 不仅大大减少了计算量, 还能在像素允许的情况下最大程度地保证特征提取检测的精度。

1 Hough算法的介绍

Hough变换 (Hough Transform, HT) 是P.V.C.Hough在1962年以专利的形式首先提出的, 它实现了一种从图像空间到参数空间的映射关系, 将图像中的检测问题转换到参数空间, 通过在参数空间的简单累加统计完成检测任务。

Hough变换的基本思想是点线的对偶性。一方面, 图像空间中共线的点对应着参数空间里相交的线;另一方面, 在参数空间中相交于同一个点的所有直线在图像空间里都有共线的点与之对应。因此Hough变换把在图像空间中的直线检测问题转换为参数空间中对点的检测问题, 通过在参数空间里进行简单的累加统计完成检测任务。如果参数空间中使用直线方程, 当图像空间直线斜率为无穷大时, 会使累加器尺寸和变得很大, 从而使计算复杂度过大。为解决这一问题, 采用直线极坐标方程, 变换方程为:

根据式 (1) , 原图像空间中的点 (x, y) 对应新参数空间中的一条正弦曲线, 即点—正弦曲线对偶。检测直线的具体过程就是让θ取遍可能的值, 然后计算ρ的值, 再根据θ和ρ的值对累加数组累加, 从而得到共线点的个数。下面介绍ρ和θ取值范围的确定。

设被检测的直线在第一象限, 右上角坐标为 (m, n) , 则第一象限中直线的位置情况如图1所示。

由图1可见, 当直线从与x轴重合处逆时针旋转时, θ的值发生变化, θ的取值范围为0o～180o。由undefined直线极坐标方程可知 (其中undefined, 当且仅当x和y都取得最大且θ+φ=±90o时, ρ取得最大值undefined, 由ρ、θ的取值范围和它们的分辨率就可以确定累加器的大小, 从而来检测直线。

由上可以看出, Hough变换检测的抗噪性能强, 但是这种方法也有明显的缺陷, 即不能同时兼顾速度和精度, 如果要提高m、n的值或者是减小角度检查的步长, 势必会大大提高运算量, 降低检测的效率。由于传统的单张检测是对一整幅图进行Hough变换, 如果每一组ρ、θ都需要4个字节的存储空间, 那么对一幅像素为M×N的图像, 如果有k个不重复的斜率, 就要求计算机的内存S=4MNk。对于一张较大的图片来说, S将为数千兆字节, 这样大的存储量, 单靠物理内存显然难以满足要求。

2 基于局部特征检测的图像纠正

针对上述检测方法存在的弊端, 对其进行改进, 提高运算速度, 减少所需的存储空间, 满足单张成品检测的要求。

由于成品检测中多是检测最长直线的偏移角度, 图像的主要特征点集中在一个小的区域内, 故我们可以将这个小的区域提取出来, 进行局部特征检测, 返回一个偏移角度值, 该角度同时也是图像的偏移角度, 随后再根据该返回值进行旋转、裁边。在局部特征检测时我们采用的方法如下:①在原图上选取一个合适的特征点;②根据经验, 为该特征点确定一个合适的长方形区域, 使得我们感兴趣的直线在该区域中依然是最长的;③划定一块内存区域, 将②中划定的区域的像素点的值复制在该内存区域中;④对赋值过后的内存区域进行快速Hough变换, 检测最长直线与水平方向的夹角。

在第④步的快速Hough变换中, 本文采用斜率分式查表法, 通过建立一个斜率分式表格, 可进一步提高运算速度和效率, 减少所需的内存空间。

单张成品的检测处理流程见图2。

可以看出, 该方法要检测的像素点远远小于传统的全局检测的像素点, 故所需的内存也比较小, 提高了运算速度和效率。

上面是以直线检测为例来说明局部检测的方法, 对于没有直线的图像或者要提取检测的是圆或者是曲线, 同样可以用局部检测的方法, 只要圆或者曲线在我们设定的区域里面即可, 具体方法与直线角度检测大同小异, 只是返回的是半径或者曲率。

3 仿真对比结果

图3是一幅普通烟盒的原始图像, 我们要检测的是图像上最长直线与水平方向的夹角。

本文提取的局部特征图像见图4。处理过后的图像见图5。

该仿真所应用的硬件平台如下:CPU为AMD Athlon (tm) , 内存1 GB, 主频2.01 GHz。操作系统为WindowsXP2002, 算法语言是C++, 编辑环境是VC6.0。

图像大小为656×490, 检测角度的步长为1o。全局检测所用时间为344 ms, 局部检测所用时间为188 ms。这里的数据分别是10次仿真取的平均值。

4 结语

本文提出了一种新的基于快速Hough算法的图像纠正方法, 极大地提高了单张成品检测的速度, 大大减少了所需的内存空间, 具有很高的实用价值。不足之处是其中的一些数据是凭借经验来设定的, 不够精确, 这有待于进一步的研究以及一些智能算法的引入。

(参考文献和英文摘要转第27页)

参考文献

[1]章毓晋.图像工程——图像处理和分析 (上册) [M].北京:清华大学出版社, 1999.

[2]Hough P V C.Method and means for recognizing complexpattern:U S, 3069654[P].1962-12-18.

[3]刘桂雄, 申柏华.基于改进的Hough变换图像分割方法[J].光学精密工程, 2002, 10 (3) :257-260.

[4]Chutatape Q, Guo I.A modified Hough transform for linedetection and its performance[J].Pattern Recognition, 1999, 32:181-192.

[5]Murakami K, Naruse T.High speed line detection byHough transform in local area[C]//IEEE computersociety.Washington DC:[s.n.], 2000:467-470.

[6]Olma G, Magli E.All-integer Hough transformperformance evaluation[G]//Proceedings of InternationalConference on Image Processing.Thessaloniki:[s.n.], 2001:338-341.