一种改进的广义插值傅里叶变换方法

第41卷第1期应用科技Vol.41No.12014年2月AppliedScienceandTechnologyFeb.2014文章题目一种改进的广义插值傅里叶变换方法创新点自述本文创新点有两个方面：第一点：在现有广义插值傅里叶变换（GIFT）的基础上提出了一种选择其最优参数的方法，使得插值误差达到最小，提高了直线检测的精度。第二点：在笛卡尔坐标到极坐标的转换方面，传统做法是通过(xcos,ysin)计算来完成，这样做的一个不足是消耗大量的时间。考虑到从笛卡尔坐标到极坐标的转换是一对一映射，这种映射关系与图像的具体内容无关，只与像素点的位置信息有关，因此本文提出了一种快速转换方法。首先，对于大小固定的图像来说，用位置映射文件存储笛卡尔到极坐标的映射信息。然后，通过查找这个映射文件来实现从笛卡尔到极坐标的转换。相对于计算的方法来说，这种查表法大大节省了计算时间。第41卷第1期应用科技Vol.41No.12014年2月AppliedScienceandTechnologyFeb.2014doi:网络出版地址：一种改进的广义插值傅里叶变换方法郑丽颖,何萌萌，刘娇（哈尔滨工程大学计算机科学与技术学院，哈尔滨150001）摘要：直线检测是计算机视觉领域中一个比较基本的任务。相对于Hough变换来说，Radon变换由于其更加优越的性能在直线检测方面具有广泛应用。本文对广义插值傅里叶变换方法（theGeneralizedInterpolatedFourierTransform（GIFT)）进行了深入研究,并提出了新的参数选择方法。首先，给出了一种GIFT参数的最优选择方法，缩小了插值误差。其次，为了加快GIFT的运算速度，在笛卡尔坐标到极坐标转换过程中，建立了一个存储其对应位置信息的映射文件，用查表法来实现笛卡尔到极坐标之间的转换。相对于通过乘法和正余弦实现的转换操作，查表法节省了大量时间开销。仿真结果表明：本文提出的方法在精度和时间复杂度方面明显优于原算法。关键词：Radon变换；多层分数傅里叶变换；参数选择；查表法；直线检测中图分类号：（作者本人填写）文献标志码：A文章编号：1009-671X（2011）01-0004-04MethodforImprovingtheGeneralizedInterpolatedFourierTransformZHENGLi-ying，HEMeng-meng,LIUJiao(Collegeofcomputerscienceandtechnology,Harbinengineeringuniversity,Harbin150001,China)Abstract：Straightlinedetectionisfairlycommonincomputervisioncommunity.ComparedwithHoughtransform,RadontransformhasbeenwidelyusedfordetectingStraightlinesduetoitssuperiorcapabilityintermsofcomputingtime.AmethodforimprovingtheperformanceoftheGeneralizedInterpolatedFourierTransform(GIFT)hasbeenproposedinthispaper.First,theproposedmethodpresentsaprincipletooptimizetheparametersoftheGIFT.ThenthemethodestablishesapositionmappingfilefortheCartesiantopolarcoordinatestransformation.Comparingtotheoriginalmultiplicationandcosineoperation,lookingupmappingfilessavesalotoftimeconsuming.SimulationresultsshowthatthecomputationalcomplexityoftheproposedmethodisobviouslysuperiortotheoriginalGIFT.Keywords:RadonTransform;MultilayerfractionalFouriertransform;Parameterselection;Lookupmappingfiles;Straightlinedetection11引言直线特征具有平移、旋转和尺度不变等良好特性。正确有效的提取图像中的直线特征，对于提高感收稿日期：2014-09-19.网络出版日期：作者简介：何萌萌(1986),男,硕士研究生，E-mail；[e-mail]通信作者：郑丽颖(1976),女,教授，博士，E-mail：[e-mail]兴趣目标的识别率和算法的鲁棒性有着重要的意义。作为一个比较基本的图像处理任务，直线检测广泛用于目标物体的识别、形状检测、道路/航线检测等应用上[1][2][3]。·2·应用科技第41卷众所周知，Hough变换的一个重要应用是直线检测[4][5]。但是Hough变换存在一些不足。首先，在进行Hough变换之前需进行边缘检测，Hough变换的结果对边缘检测的结果高度敏感[6]；第二，Hough变换的大量时间上的花费对一些实时应用来说是不可接受的,比如说车辆自动驾驶系统中的道路边线检测，以及航道检测等[3]。从数学定义上讲，Radon变换与Hough变换是等效的[7]。但是从实现方式上看，Radon变换更优于Hough变换。这是因为中心切片定理从理论上保证了可以使用快速傅里叶变换（FastFourierTransform(FFT)）方法来实现Radon变换，从而使其具有更高的计算效率。然而实际应用表明：这种快速变换方法的结果直接受到笛卡尔-直角坐标变换过程中插值误差的影响。插值误差导致图像的Radon变换中存在较多的虚假峰值点，从而影响直线检测的精度[6][8][9][10]。Pan等人在图像配准中提出了一种可修改的多层分数傅里叶方法[9]，Shi等人在Pan的基础上提出了一种傅里叶变换和Hough蝶形区域联合起来，在峰值检测之前加了个一个带通滤波器起到峰值增强作用，从而可以得出更为精确的直线检测结果[6]。通过中心切片定理[11][12]，Radon变换可以用快速傅里叶变换来实现，而多层分数傅里叶变换则被用来解决传统快速傅里叶变换的插值误差问题。Zheng等人提出了一种广义插值傅里叶变换（GIFT）的方法[10]。通过在X和Y轴分别使用不同的参数使插值更加灵活。GIFT方法中，参数L和{Cut}=12()的选择是至关重要的，这里L和12()分别是GIFT中分数傅里叶变换的层数和X-Y轴的阶数。Pan等人的方法中，参数{Cut}中12()两个值是相等的，且参数L和{Cut}的选择，只定义了某一种插值情况下的插值误差，计算时只选择了部分点来参与计算[9]。本文介绍了一种最优选择合适的参数L和12()的方法，使得插值误差尽可能小，从而达到提高直线检测精度的目的。但是，无论Pan等人的方法，还是Shi和Zheng等人的方法[6][8][9][10]，都需要计算从笛卡尔坐标到极坐标的转换操作。从笛卡尔坐标到极坐标的转换包含了大量的乘法和正余弦操作，因此这一转换过程需要花费大量时间。考虑到从笛卡尔坐标到极坐标的转换是一对一映射，这种映射关系与图像的具体内容无关，只与像素点的位置信息有关，本文在介绍完GIFT参数选择方法之后又提出了一种快速转换方法。首先，对于大小固定的图像来说，用位置映射文件存储笛卡尔到极坐标的第1期作者名，等：文章题目·3·映射信息。然后，通过查找这个映射文件来实现从笛卡尔到极坐标的转换。相对于计算的方法来说，这种查表法大大节省了计算时间。2基于GIFT的Radon变换Radon变换在角度θ的线积分公式如下：(x,y)(,)(x,y)(xcosysin)dxdyRff其中Rf(x,y)是函数f(x,y)的二维Radon变换[7]。Radon变换在数学意义上等效于Hough变换，被广泛用于直线检测中。令S表示切片操作，F1和F2分别表示一维和二维傅里叶变换，则傅里叶中心切片定理[11][12]可以表示为：12{R[f(x,y)]}(){F[f(x,y)](,)}()FS这里[f(x,y)](x')(x'cos,x'sin)Sf其中R是Radon变换在角度的投影。公式（2）描述的中心切片定理可表述如下：函数的Radon变换在角度的投影的一维傅里叶变换等于函数的二维傅里叶变换在同样角度的投影。因此，通过执行函数（图像）的二维傅里叶变换，插值实现笛卡尔到极坐标的转换，对结果的每一行执行一维傅里叶逆变换来实现其Radon变换是完全可行的。但是快速傅里叶变换（FFT）会增加混淆问题，容易产生虚假峰值点（如图1所示），使得直线检测的精确度下降。图1：快速Radon变换中的虚假峰值为了解决混淆问题，Zheng等人提出了一种广义插值傅里叶变换（GIFT）的方法[10]，图像f(n1,n2)的GIFT被定义如下：12121122,1112221212222(nknk)(k,k)(n,n)exp()NNNNnnjFfN其中{f(n1,n2)|-N/2n1,n2N/2-1)}是大小为的图像,1201。通过叠加具有不同阶数12()的插值傅里叶变换F，可以得到类似于极坐标形式的频率插值网格（如图2所示[10]）。随着阶数12()取不同的值，所得到的频率插值网格会具有不同的形状，其中水平方向频率的范围为11()，而垂直方向的范围为22()。多层联合起来形成一个完整的傅里叶频谱。这样形成的频率域比传统的单层傅里叶变换包含更多的采样点，从而使得混淆效果最小。·4·应用科技第41卷图2：GIFT的频率分布，其中*,o,+分别对应的12()(取值分别为(1,1),(0.8,0.7)和(0.3,0.5)GIFT网格的分辨率依赖于两个参数，分别是层数L和近似的分数阶数{Cut}，其定义为：121212{(,)|i1,2,...L,0,1and1}iiiiLLCut(4)频率域的插值网格被定于如下：1LitPP其中11221212{(k,k)|,k,(,)Cut}(6)22iiiiiNNPk从笛卡尔到极坐标的转换方面，传统的方法是通过(xcos,ysin)计算每一个对应点。由于二维傅里叶谱是关于原点对称的，因此只需计算出其上半部分的傅里叶谱，其下半部分可以通过共轭映射来得到。其上半部分笛卡尔坐标xy到极坐标的转换用了一种线性插值方法：,11rmn其中2/2rN，m和n是根据实际需要精确度而提前定义好的可调整正整数,一般取(m=0.5N)[6]。图像的大小是，相应的极坐标网格大小是mn，通过(xcos,ysin)计算每一个极坐标点在笛卡尔坐标中的位置，并利用其周围的坐标进行插值[6]。3GIFT参数的选取方法对于插值误差来说，层数L和参数{Cut}=12()的选择是至关重要的。层数L依赖于实际应用的类型。一般来讲，层数越大，插值误差越小。综合考虑到插值误差及其时间消耗，在大多数情况下我们一般推荐L取3或者4。实际上，正确的方法应该是如果精确度没有达到要求的话就应该适当的增加层