基于广义插值傅里叶方法的先进Radon变换直线检测法中文

1、大学文）附件华北电力毕业设计（论外文文献学号：201102020322姓名：徐楠所在院系：自动化系专业班级：自动化专业自动实1101指导教师：程海燕原文标题：AdvancedRadontransformusinggeneralizedinterpolatedFouriermethodforstraightlinedetection2015年4月29日华北电力大学本科毕业设计（论文）华北电力大学本科毕业设计（论文） # I基于广义插值傅里叶方法的先进Radon变换直线检测法摘要在计算机视觉中直线检测较为常见。相比于Hough变换，Radon变换因为其效率和准确性已备受关注。在本文中，提出了一个广

2、义插值傅立叶变换（以下简称GIFT）用于加快Radon变换。基于GIFT可以实现一种无需任何预处理的从灰度图像检测直线的方法。需要提一下两方面的贡献。第一，潘等人最近的工作中以一种更清晰的方式重新解释和实现了传统的傅立叶变换在频率域采样上实现的精确插值。第二，在二维度应用于二维图像弹性参数测定的插值傅里叶变换的进一步推广。实验结果表明，我们提出的方法优于标准的Radon变换，具有较低的计算负载和更高的精度。实验还表明，GIFT直线检测比得上随机抽样的一致性，是一种广泛应用于计算机视觉领域的有鲁棒性的估计。关键字：Radon变换；广义插值傅里叶；直线检测华北电力大学本科毕业设计（论文）华北电力大

3、学本科毕业设计（论文）目录TOC o 1-5 h z HYPERLINK l bookmark6 摘要I HYPERLINK l bookmark22 1引言1 HYPERLINK l bookmark24 2广义插值傅里叶变换（GIFT）2 HYPERLINK l bookmark54 3基于GIFT的直线检测4 HYPERLINK l bookmark56 3.1投影切片定理4 HYPERLINK l bookmark70 3.2用于直线检测的GIFT算法5 HYPERLINK l bookmark78 4实验结果及分析74.1GIFT的参数规格和峰值检测8 HYPERLINK l boo

4、kmark82 4.2合成图像的评价11 HYPERLINK l bookmark84 4.2.1多线图像114.2.2噪声图像124.3真实图像的评价13 HYPERLINK l bookmark88 5结论15华北电力大学本科毕业设计(论文)华北电力大学本科毕业设计（论文） 1引言图像的直线检测是多模式识别问题的要求，这是因为各种自然和人为因素通常可以通过其独特的线性特征组合识别出来。在过去几十年的文献中已经描述了一些直线检测方法，其中有许多是基于标准的或变形的Hough变换（HT）1-9，因为当图像有噪声和数据缺失发生时，应用Hough变换有稳定性和鲁棒性。然而，基于直线检测的HT计算效

5、率随着图像尺寸和/或分辨率的增加而急剧下降。很难用这些方法获得实时性能。Radon变换（RT）在概念上与HT相同，但比HT计算效率更高，因此基于直线检测的RT备受关注。Deans】10首先描述了如何推断HT在图像中寻找直线，作为二维欧氏空间中定义的RT的特殊情况。他的工作表明RT能够变换图像中的直线为可能的直线参数范围，其中图像中的每一条直线将会给一个峰值（亮线）或一个谷值（黑线）对应在相应的直线参数。随后，墨菲提出了一个基于雷达图像噪声的直线检测RT方法111。此后，大量的工作已经完成来提高基于直线性特征检测的RT的质量12-20。在大多数情况下，RT算法的计算效率是基于投影切片定理来实现的

6、，其中直角坐标到极坐标映射是一个必要的步骤。因此，直角坐标到极坐标映射的插值误差强烈影响最后的结果。Ho等人，使用补零和种植技术来降低插值误差18。根据他们的方法，在转化之前,输入图像用零来填充以从N*N到（N*2b）*（N*2b）中增加图像的尺寸。任何补的零在一维离散傅里叶变换（DFT）阶段后删除。尽管他们已经表明该策略可以有效消除混淆现象，但是浪费时间。假设一个图像的大小为N*N，然后二维DFT所需的快速傅立叶变换的计算复杂度为0N2log（N）这说明如果b不等于零，计算成本将大大增加（近似的为4b的一个因素）。在本文中，我们提出了一个广义插值傅里叶变换（GIFT）实现一个快速的RT。有一

7、点必须强调的是，我们推广的是潘等人提出的采用在水平和垂直方向的不同比例因子的插值傅里叶变换。与x轴和y轴1的原始参数相比，在本研究中提出两个参数使变换更灵活和实用。本文中，术语“差值傅里叶变换”代替早期文献中的“多层分数傅里叶变换（MLFFT）”，2。，这是因为在长期以来分数傅里叶变换不太合适，以及可以与传统的郑丽英：哈尔滨工程大学，计算机科学与技术学院史大明：密德萨斯大学，工程与信息科学学院分数傅里叶变换(FRFT)混淆，FRFT与信号时频分布密切相关。然而，无论是MLFFT在19或本文的GIFT当应用于图像时不提供空间信息和频率信息。本文的其余部分组织如下。章节2给出GIFT的技术细节。章

8、节3中，阐明了GIFT算法的实现。实验结果及分析在章节4中给出，随后第5节的结论。2广义插值傅里叶变换(GIFT)f(n)ln=-N/2,.,0,.N/2-1的被DFT定义为N/2-1F(k)=乙f(n)exp(-j2兀kna/N)(1)n=-N/2式中exp(.)是指数函数，j=口。要注意F(k)的频率N均匀分布于L兀，兀。Ne-1Fa(k)=乙f(n)exp(-jiRkna/N)(2)n=-N/2式中0aw1。显然，Fa(k)的频率N分布在Ca兀，a兀。基于等式2，潘19等人他们称为错层分数傅里叶变换(MLFFT)的二维变换如下所示:Fa(k，k)=f(n,n)exp(-j2兀(nak+n

9、ak)/N)12121122n=-N/2n=-N/212式中，f(n,n)|-N/2n,nN/2-1是二维的离散信号。Fa(k，k)的N*N频域分散121212于-a兀,a兀x-a兀,a兀。肯容易证明:Fa(k，k)=F(ak，ak)(4)1212等式4表明，人们可以计算非整数的频率。根据式3,如果使用特有的a和多个傅立叶变换实例，可以得到一组分布在整数和非整数网格的频率。因此我们称之为差值傅立叶变换的这种特殊的傅立叶变换比潘等人提出的多层分数傅立叶变换在那些应用，如笛卡尔对数极坐标映射和直角坐标到极坐标映射上更加合适。进而我们注意到，由于X轴和Y轴均匀的比例因子，式3得到插值网格的分布是有限

10、制的。例如，如果k=-2,-1,0,1,2以叹=-2,-1,0,1,2，则在(0.2,0.3)的频率不能直接计12算。根据式（4）,我们可以选择=.2,0.3或者其它一些值进行两次变换得到处于（020.2）和（0.3,0.3）的频率，然后使用一些差值方法，如邻插值和双线性插值，来计算（0.2,0.3）的频率。为了来解决上述问题，我们提出如下广义差值傅立叶变换（GIFT）：小2打Q)乙f(n,n)exp(-j2兀(nak+nak)/N)121z1222i-N/2n=N/2式中，0a,a1.通过这样的归纳，针对上述问题，我们只需要选择12a=0.2,a=0.3（或者a=0.1,a=0.15）,然后

11、进行一次变换得到在（0.2,0.3）的精确频率。1212与MLFFT相似，GIFT网络的分辨率取决于两个参数：逼近层数L和近似值Cut，如下定义:(6)Cut=a,a)|i二1,.L,0a,a1,anda=a二1TOC o 1-5 h z1i2i1i2i1L2L在频域范围内插值网格的定义:p二Up（7）t=1 HYPERLINK l bookmark50 P=（ak,ak）lN/2k,kN/2-1,（a,a）eCut（8）i11i2212i1i2因为GIFT除了L还有两个可调参数a,a，它比MLFFT更加灵活。图1说明了一个1i2i三层插值网络是如何通过三层GIFT网络构成的。上面描述的GIF

12、T有如下重要特性:当a=a，其中i=1,2,.L,它降级到原始的MLFFT。1i2i当a=a=1,它相当于传统的二维DFT。1i2i当0a,a1,GIFT返回N阶频域值，其均匀分布于频率域1i2i-a兀,a兀xLa兀,a兀。1122当0a,a1,Fa1；a2（k,k）=F（ak,ak）。12121122根据特性3、4与等式7、8,结合不同a和a的GIFT导致了一个高分辨率网（见图1）。12特性4意味着可以计算任何坐标网的频率。因此，使用一些特殊的步骤，可以得到准确的ooO0oi十十十-.PH)o-+*).QhO00OO0-1ii-+申+iii1+伞+0oyU1ooj十吉十oo：O0：O061(

13、十+-,O()16,J-+)o:0o：,0o:傅里叶谱。图1.当Cut=&).3,0.5)(0.8,0.7)(1,1)的GIFT网。+P网，oP2网，*P3网3基于GIFT的直线检测3.1投影切片定理一个二维函数f(x,y)的RT定义为函数在轴上的积分投影，与X轴的角度有角度910九(p,9)=RNDf(x,y)Ip)9二Jf(Pcos9-ysin9,psin9+ycos9Ay=f(x,yb(p-xcos9-ysin9)ixdy式中，RND是是随机算子，()是一维狄拉克三角函数。据了解为了获得充分的转换，9与P不同以至于九由9与p的随机值所确定。让SLC9成为二维函数ffx，y)切片算子，角9

14、在关系：SLcVfC,y)Xx)二fCcos9,xsin9)(10)然后可以得到JRND、f(x,y)Kp)exp(-j2兀pv)dp=JJJf(x,yG-xcos9-ysin9)xexp(-j2兀pv)dpdxdy=JJf(x,y)kG-xcos9-ysin9)exp(-j2兀pv)dpdxdydy=SLC9=JJf(x,y)expj2兀(xvcos9+yvsin9)Jf(x,y)expl-j2兀(xv+yvll/xdyv)(11)使F1和F2分别成为一维和二维的傅里叶算子，然后方程（11）可以重新描述为:(12)0DNf(x,y)Kv)=SLCpIf(x,y)亦)人)002方程（12）是投

15、影切片定理：一维傅里叶变换在角0的积分投影等于二维傅里叶变换在同一角度的投影切片。为了计算RT,它必须执行以下三个步骤11：（1）计算f（x,y）的二维傅里叶变换。（2）插值二维傅里叶变换得到的一组函数A（v,O）=Fk（p,0）,每个被定义在频率沿径向线定位在一个角度O。（3）计算每个函数A（v,O）随v的傅里叶反变换，产生一组投影函数九G,O）共同构成图像的RT。基于以上三个步骤，Ho等人a详细描述了利用RT实现直线检测。他们采用零填充和种植策略解决插值误差的问题。因此，输入图像首先用零填充，以避免混叠效应；然后进行了一个直角坐标到极坐标变换来得到九G,0）的一维傅里叶变换。之后，进行一维

16、滤波增强边缘，提高正弦图中峰结构。在得到一维滤波和一维傅里叶谱逆DFT之前进行共轭镜像得到新的数据。任何补的零在之后删除，在随机空间的最大值位于裁剪不正的数据。最后查明直线对应的极大值。在概念上类似HT的基于直线检测RT的一个优势是提高了它提供的计算效率。另一个是可以很容易在九G,0）从傅里叶域到对一维傅里叶反变换中得到一些图像增强算子。如上所述，零填充和种植技术的过程导致了计算时间的大量增加，因此有必要采取一种替代技术进一步加快基于直线检测的RT。3.2用于直线检测的GIFT算法图2总结了基于直线检测的GIFT所需的主要阶段。原始输入图像的灰度图像。一个尺寸为sxr（s和r与Cut的近似计算

17、值有关）的二维精确傅里叶谱可以通过应用L-层GIFT到输入图像来获得。注意补零操作省略。然后从直角坐标x-y网到尺寸为m*n极坐标v-0网（在这里，我们假设m=0.5r）通过计算每个在笛卡尔网格（x=vcos0,y=vsin0）的v-0华北电力大学本科毕业设计（论文）华北电力大学本科毕业设计（论文） 像素的位置和从周围的像素插值来得到准确的二维傅里叶谱的上半部分。显然，对于直线检测中的应用，在高频率的插值精度比其他的频率更重要，因为边缘比其他部分更重要。因此，在GIFT和笛卡尔到极坐标的映射阶段极，以下步骤进行:Cut二（1）设置可调参数L和GIFT的Cut。由于高频率更重要，我们假设,a）1

18、0.5a,a1,i=1,2,.,l1i2i1i2i(2)执行L-层GIFT得到准确的傅里叶谱。(3)让0=)，A0,2A0，._，兀A0=兀/（n-1）,其中n必须为了确保最佳的像素覆盖率高。、Jr2+s2.，0,Av,2Av，.2(5)使用插值方案，如最近或双线性插值，计算在x=vcos0,y=vsin0的频率。经过以上五个步骤，得到了m*n阶的傅里叶谱AC,0）。接下来，执行一个一维滤波来增强边缘。在这里，采用了方程（13）中给出的高斯（DOG）一维差分滤波器，因为它是一个边缘检测器和峰结构增强器a】。）（A(v,0)=expJv2/d2)-expJv2/d2hei(13)1式中，d=Q和

19、G是两个高斯函数兴奋和抑制的标准偏差。e,ii2kgeie,i最后，运用共轭镜和沿每排AC,0）的一维DFT，得到了增强的输入图像。然后，通过定位正弦图的局部峰值，可以在原始图像中直线检测。的基于直线检测的GIFT的一个优势是其无需任何预处理在灰度图像中检测直线的能力，如需要基于HT的方法细化图像。根据以上的描述，在基于直线检测的GIFT中总共指定六个参数，即L，Cut，n，v，d和d.。其中，L和Cut描述插值网格。一般来说，L越大，插值误差越小。考虑到插值ei误差和时间消耗，根据我们的实验结果，L=3是合适的。Cut的选择很关键。在这里，采用下面的搜索方案。首先，随机产生20个Cut，其成

20、分组合是属于0.5，0.6,0.7,0.8,0.9，1。然后，选择以下函数的最小值:(14)J=Ydis_grid（r,0）ij式中，dis_grid是是实际的插值点和插值网格隐藏点之间的欧氏距离。参数n和Av与正弦图的分辨率有关。n越大，Av越小，正弦图越好。参数d和d.1与正弦图的峰结构相关。正弦图蝴蝶效应可以通过选择合适的de和d.来大大降低。二r*xhI-DFouriertrtiiifbfirisGIFTwiiJtLlayersFL-I11i1P|Wr1S-VilrCartBfiianicpdhrLocalpe趾-Dfilteringandconjugatemirror图2基于GIFT

21、的直线检测流程图4实验结果及分析在这一部分，图像的三种类型，即混合型图像，多线无噪声图像，和真实图像被用来测试基于GIFT的直线检测。图像的大小是128*128。得到的结果与图2的程序流程图是一致的。在正弦图中检测峰，我们采用迭代识别-拆除程序：当一个峰值的确定，它从正弦图中随着其周围的山峰删除。在下面的实验，我们假设直线的数量是已知的，而这些线可以用特定数量的识别去除重复来得到211。图3混合形状的图像华北电力大学本科毕业设计(论文)华北电力大学本科毕业设计(论文) #4.1GIFT的参数规格和峰值检测如图3所示的混合形状的图像是用来测量不同的参数设置对算法的影响。分别设L=1,2,和3,不

22、做任何过滤操作。根据3.2节中介绍的主要步骤，除了L和Cut，在直角坐标到极坐标映射中有两个参数需要优先选择，即，角样本数n和径向采样增量Av。首先，设定n=256和Av=-J2。采用最近的插值。结果如图4所示，其中Cut值在3.2节中描述的搜索都是最优的方案。图5所示的结果与n=512和Av=相一致，当n=256和Av=0.5迂的结果在图6显示。从图4可以看出正弦图(a)表现出一些锯齿，这是由于由于忽略零填充以及大的径向采样增量。图4中b和c表明使用GIFT可以有效降低，其可平行计算出且比补零法更快。图4还表明，GIFT的层数越多，正弦图的混淆现象越小。原因是多层次意味着更高的插值分辨率(见

23、图1)和更小的插值误差。图5表明，n的增加不能减少混叠。n越大使正弦图更清晰，但会增加计算时间。在计算时间和可读性之间权衡，设置n=256和n=512适用于大多数情况下。图6表明降低不仅导致一个清晰的正弦图还减轻混淆。Cut=(0.7,0.8),(1,1)的结果(图6b)没有混淆，类似于Cut=(0.8,0.9),(0.9,0.7),(1,1)。通过0.5个因素减少Av导致从直角坐标到极坐标映射双倍的计算时间。考虑到GIFT可以并行计算，我们建议增加GIFT的层而不是使用一个非常小的Av来实现同样的目的。在本小节结束，评价不同的插值方案。在这里，我们固定n=256，Av=p2，Cut=(0.&

24、0.9),(0.9,0.7),(1,1)，最近的，双线性，和样条插值的结果分别如图4c和7所示比较图4c和7,正弦图的清晰度已经通过一个更复杂的插值方案的得到了改进。包括复杂的计算和正弦质量，双线性插值法在余下的研究中使用。华北电力大学本科毕业设计（论文）华北电力大学本科毕业设计（论文） ab图4.n=256,Av=、2(a)Cut=(l,l),(b)Cut=(0.7,0.8),(l,l),(c)Cut=(0.8,0.9),(0.9,0.7),(l,l)的正弦图图5.n=5l2,Av=2,(a)Cut=(l,l),(b)Cut=(0.8,0.9),(0.9,0.7),(l,l)的正弦图图8.K

25、=3的十张图4.2合成图像的评价4.2.1多线图像在这里，测试图像是由K线和一个圆组成，其中K分别为2,3,4,5和6。每条线的斜率与相交是随机选择的。所以标记圆的直径和位置。每个K都有10个实例。图8显示了K=3的10个图像。GIFT法的参数设置是L=3，Cut=（0.8,0.9）,（0.9，0.7）,（1,1）,n=256，和Av=迈。此外，等式（13）中在（d,d）=（180,105）时的一维DOG滤波器应用于在笛卡尔到极坐标映ei射的阶段。考虑到两个事实：（1）我们的方法与RT有密切关系，（2）比较基于直线检测的GIFT、RT和与RANSAC方法，RANSAC22,24与随机抽样一致，

26、在计算机视觉领域中是一个常见的鲁棒估计。我们设置RT的角分辨率为兀/256。对于RANSAC，设置样本数100。距离阈值是2。无论是RT还是RANSAC算法可以处理灰度图像，使用Sobel算子产生一个二进制图像。考虑到RANSAC方法无法每时每刻找到两或多条直线，我们一个一个的检测线。检测到一条线后，我们保存它从数据集中删除所有有助于这条线的点，然后重复这个过程以减少图像直到K条线都被检测到。以上三种方法在MATLAB中实现。每个方法直线提取的平均正确率，平均角误差，和平均值计算时间分别显示在表1-3中。首先，表1-3表明GIFT比RT有较高的正确率，较低的平均角误差和计算负荷。其次，表1显示

27、了GIFT可以比得上RANSAC。再次，表2意味着GIFT的精度比RANSAC更好。最后，表3显示了GIFT的计算时间与检测直线有一点关系，这对于RANSAC是不正确的。尽管表3表明GIFT比RANSAC更快，但是需要注意的是事实上，使用GIFT的快速傅里叶变换是用C语言实现的，而RANSAC的所有代码使用MATLAB。所以，我们不能说哪一个更快，但从这张表中我们可以推断出，与RANSAC相比，至少GIFT的速度还可以，特别是当执行并行检测多线的GIFT。以下两个优势导致了GIFT的良好性能。首先，它更准确，因为通过对傅里叶谱的插值获得了更多的频率。其次，它的速度更快，因为该方法忽视了补零和边

28、缘检测。表1:直线提取的正确率（）Kmethod23456RT1001009239080GIFT10096.797.59S95RANSAC10096.710092箔表2：直线提取的平均误差角（度）Kmethad23456RT2302.461.93234231GIR1.7421L652.05ftANSACL722202.422.132A7表3：平均计算时间（秒）Kmethod23456RT0.3410348a泗0351GIFT0.2480.24905202510.251RANSAC0.2910.317034203770.421表4：噪声图像直线提取的正确率（）gmethod0.050.090.100J10.120.14KT93菊9596.709090GIFTwirhDOG96.796.796796.396l793.393.3RANSAC10D10010D96.793.396.79v74.2.2噪声图像在这一部分中，有些图像是基于图8所产生来验证我们所提出的相对噪声的鲁棒性的方法的性能。为了产生噪声图像，将具有零均值的噪声和不同方差添加到由随机位置