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

1、第 41 卷第 1 期 应用科技 Vol.41 No.12014 年 2 月 Applied Science and Technology Feb. 2014文章题目文章题目一种改进的广义插值傅里叶变换方法一种改进的广义插值傅里叶变换方法创创新新点点自自述述本文创新点有两个方面： 第一点：在现有广义插值傅里叶变换（GIFT）的基础上提出了一种选择其最优参数的方法，使得插值误差达到最小，提高了直线检测的精度。 第二点：在笛卡尔坐标到极坐标的转换方面，传统做法是通过计算来完(xcos , ysin ) 成，这样做的一个不足是消耗大量的时间。考虑到从笛卡尔坐标到极坐标的转换是一对一映射，这种映射关系

2、与图像的具体内容无关，只与像素点的位置信息有关，因此本文提出了一种快速转换方法。首先，对于大小固定的图像来说，用位置映射文件存储笛卡尔到极坐标的映射信息。然后，通过查找这个映射文件来实现从笛卡尔到极坐标的转换。相对于计算的方法来说，这种查表法大大节省了计算时间。2 应用科技 第 41卷第 41 卷第 1 期 应用科技 Vol.41 No.12014 年 2 月 Applied Science and Technology Feb. 2014doi:网络出版地址：一种改进的广义插值傅里叶变换方法郑丽颖,何萌萌，刘娇（哈尔滨工程大学计算机科学与技术学院，哈尔滨 150001）摘要：摘要：直线检测是

3、计算机视觉领域中一个比较基本的任务。相对于 Hough 变换来说，Radon 变换由于其更加优越的性能在直线检测方面具有广泛应用。本文对广义插值傅里叶变换方法（the Generalized Interpolated Fourier Transform （GIFT)）进行了深入研究,并提出了新的参数选择方法。首先，给出了一种 GIFT 参数的最优选择方法，缩小了插值误差。其次，为了加快 GIFT 的运算速度，在笛卡尔坐标到极坐标转换过程中，建立了一个存储其对应位置信息的映射文件，用查表法来实现笛卡尔到极坐标之间的转换。相对于通过乘法和正余弦实现的转换操作，查表法节省了大量时间开销。仿真结果表明

4、：本文提出的方法在精度和时间复杂度方面明显优于原算法。关键词：关键词： Radon 变换；多层分数傅里叶变换；参数选择；查表法；直线检测中图分类号：（作者本人填写） 文献标志码：A 文章编号：1009-671X（2011）01-0004-04Method for Improving the Generalized Interpolated Fourier TransformZHENG Li-ying，HE Meng-meng, LIU Jiao(College of computer science and technology, Harbin engineering university,

5、Harbin 150001, China )Abstract：Straight line detection is fairly common in computer vision community. Compared with Hough transform, Radon transform has been widely used for detecting Straight lines due to its superior capability in terms of computing time. A method for improving the performance of

6、the Generalized Interpolated Fourier Transform (GIFT) has been proposed in this paper. First, the proposed method presents a principle to optimize the parameters of the GIFT. Then the method establishes a position mapping file for the Cartesian to polar coordinates transformation. Comparing to the o

7、riginal multiplication and cosine operation, looking up mapping files saves a lot of time consuming. Simulation results show that the computational complexity of the proposed method is obviously superior to the original GIFT. Keywords: Radon Transform; Multilayer fractional Fourier transform; Parame

8、ter selection; Look up mapping files; Straight line detection 11 引言收稿日期：2014-09-19. 网络出版日期： 作者简介：何萌萌(1986), 男, 硕士研究生，E-mail；通信作者：郑丽颖(1976), 女, 教授，博士，E-mail：直线特征具有平移、旋转和尺度不变等良好特性。正确有效的提取图像中的直线特征，对于提高感兴趣目标的识别率和算法的鲁棒性有着重要的意义。作为一个比较基本的图像处理任务，直线检测2 应用科技 第 41卷广泛用于目标物体的识别、形状检测、道路/航线检测等应用上123。众所周知，Hough 变换的

9、一个重要应用是直线检测45。但是 Hough 变换存在一些不足。首先，在进行 Hough 变换之前需进行边缘检测，Hough 变换的结果对边缘检测的结果高度敏感6；第二，Hough 变换的大量时间上的花费对一些实时应用来说是不可接受的,比如说车辆自动驾驶系统中的道路边线检测，以及航道检测等3。从数学定义上讲，Radon 变换与 Hough 变换是等效的7。但是从实现方式上看，Radon 变换更优于 Hough 变换。这是因为中心切片定理从理论上保证了可以使用快速傅里叶变换（Fast Fourier Transform(FFT)）方法来实现 Radon 变换，从而使其具有更高的计算效率。然而实际

10、应用表明：这种快速变换方法的结果直接受到笛卡尔-直角坐标变换过程中插值误差的影响。插值误差导致图像的 Radon 变换中存在较多的虚假峰值点，从而影响直线检测的精度68910。Pan 等人在图像配准中提出了一种可修改的多层分数傅里叶方法9，Shi 等人在 Pan 的基础上提出了一种傅里叶变换和 Hough 蝶形区域联合起来，在峰值检测之前加了个一个带通滤波器起到峰值增强作用，从而可以得出更为精确的直线检测结果6。通过中心切片定理1112，Radon 变换可以用快速傅里叶变换来实现，而多层分数傅里叶变换则被用来解决传统快速傅里叶变换的插值误差问题。Zheng等人提出了一种广义插值傅里叶变换（GI

11、FT）的方法10。通过在 X 和 Y 轴分别使用不同的参数使插值更加灵活。GIFT 方法中，参数 L 和Cut =的选择是至关重要的，这里 L 和12() 分别是 GIFT 中分数傅里叶变换的层数和12() X-Y 轴的阶数。Pan 等人的方法中，参数Cut中两个值是相等的，且参数 L 和Cut的选择，12() 只定义了某一种插值情况下的插值误差，计算时只选择了部分点来参与计算9。本文介绍了一种最优选择合适的参数 L 和的方法，使得插值误12() 差尽可能小，从而达到提高直线检测精度的目的。但是，无论 Pan 等人的方法，还是 Shi 和 Zheng 等人的方法68910，都需要计算从笛卡尔坐

12、标到极坐标的转换操作。从笛卡尔坐标到极坐标的转换包含了大量的乘法和正余弦操作，因此这一转换过程需要花费大量时间。考虑到从笛卡尔坐标到极坐标的转换是一对一映射，这种映射关系与图像的具体内第 1 期 作者名，等：文章题目 3容无关，只与像素点的位置信息有关，本文在介绍完 GIFT 参数选择方法之后又提出了一种快速转换方法。首先，对于大小固定的图像来说，用位置映射文件存储笛卡尔到极坐标的映射信息。然后，通过查找这个映射文件来实现从笛卡尔到极坐标的转换。相对于计算的方法来说，这种查表法大大节省了计算时间。2 基于 GIFT 的 Radon 变换Radon 变换在角度 的线积分公式如下：(x,y)( ,

13、 )(x,y) (xcosysin)dxdyRff 其中 R f (x, y)是函数 f(x, y)的二维 Radon 变换7。Radon 变换在数学意义上等效于 Hough 变换，被广泛用于直线检测中。令表示切片操作，F1 和 F2 分别表示一维和S二维傅里叶变换，则傅里叶中心切片定理1112可以表示为：12R f(x,y)( )F f(x,y)( , )( )FS 这里 f(x,y)(x)(xcos ,xsin )Sf其中是 Radon 变换在角度的投影。公式R（2）描述的中心切片定理可表述如下：函数的Radon 变换在角度的投影的一维傅里叶变换等于函数的二维傅里叶变换在同样角度的投影。因

14、此，通过执行函数（图像）的二维傅里叶变换，插值实现笛卡尔到极坐标的转换，对结果的每一行执行一维傅里叶逆变换来实现其 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/2n1,n2N

15、/2-1)是大小为的图像, 。通过叠加具有不同阶1201 数的插值傅里叶变换 F，可以得到类似于12() 极坐标形式的频率插值网格（如图 2 所示10） 。随着阶数取不同的值，所得到的频率插值网12() 格会具有不同的形状，其中水平方向频率的范围为，而垂直方向的范围为。11() 22() 4 应用科技 第 41卷多层联合起来形成一个完整的傅里叶频谱。 这样形成的频率域比传统的单层傅里叶变换包含更多的采样点，从而使得混淆效果最小。图2：GIFT 的频率分布，其中 *, o, +分别对应的 (取值分别为(1,1),(0.8, 0.7) 和 (0.3,0.5)12() GIFT 网格的分辨率依赖于两

16、个参数，分别是层数 L 和近似的分数阶数Cut，其定义为： (4)121212(,)|i1,2,.L,0,1 and 1iiiiLLCut 频率域的插值网格被定于如下：1LitPP其中 11221212(k ,k )|,k,(,)Cut (6)22iiiiiNNPk从笛卡尔到极坐标的转换方面，传统的方法是通过计算每一个对应点。由于(xcos , ysin ) 二维傅里叶谱是关于原点对称的，因此只需计算出其上半部分的傅里叶谱，其下半部分可以通过共轭映射来得到。其上半部分笛卡尔坐标到极坐标xy的转换用了一种线性插值方法：,11rmn 其中，m 和 n 是根据实际需要精确2/ 2rN度而提前定义好的

17、可调整正整数,一般取(m=0.5N)6。图像的大小是，相应的极坐标网格大小是n，通过计算每一个极m(xcos , ysin ) 坐标点在笛卡尔坐标中的位置，并利用其周围的坐标进行插值6。3 GIFT 参数的选取方法对于插值误差来说，层数 L 和参数Cut = 的选择是至关重要的。层数 L 依赖于实际12() 应用的类型。一般来讲，层数越大，插值误差越小。综合考虑到插值误差及其时间消耗，在大多数情况下我们一般推荐 L 取 3 或者 4。实际上，正确的方法应该是如果精确度没有达到要求的话就应该适当的增加层数 L，同时，应该综合考虑时间方面的花费9。一旦层数 L 确定了，对Cut的选择就是非常苛刻的

18、。Pan 等人提出的关于阶数 Cut的选择方法9，其取值一样，而且只定义了一种最近12 邻插值法下的插值误差，由于在计算插值误差时候这个过程比较慢，采用了只计算部分点的插值误差来估计全局插值误差。这样计算出来的插值误差可能会不太精确。而本文提出的方法，定义了不同插第 1 期 作者名，等：文章题目 5值方法下的插值误差，并且在笛卡尔到极坐标转换中本文采用查表法（见第四节） ，对于固定大小的图像，只需计算一次Cut，因此在计算插值误差时可以不用考虑时间方面的花费，通过计算全局插值误差来求得是插值误差最小的参数，从而使得结果更加精确。考虑到从笛卡尔到极坐标的转换过程中，极坐标远离原点的部分将会变得稀

19、疏，而这部分正好对应于高频区域。在直线检测中，高频区域包含更多更有用的信息，所以我们主要考虑高频区域中的插值问题。因此，我们将每一层的Cut = 范12() 围限定在 0.5 到 1 之间。对于不同的插值方法，插值误差的定义是不同的。本文讨论了两种不同的插值方法及其相应的参数选择方法。假定通过计算得出的笛卡(xcos , ysin ) 尔坐标中对应的点为（Xreal，Yreal）a. 最近邻插值法：将 L 层频率谱叠加在一起，找出（Xreal，Yreal）点周围最近邻的四个点，即左上，左下，右上，右下四个方向距离（Xreal，Yreal）最近的四个点。计算出这四个点中距离（Xreal，Yrea

20、l）最近的点作为其插值点。此种插值法下插值误差被定义为：,(,)(8)gridiji jJdis 其中 是计算得出的频率谱中的每( ,)gridijdis 个实际点的插值误差。在最近邻插值法中，即为实际计算得到的点和距离其最近邻点的距离。 (9)222(,)(X)(Y)(9)gridijclosestrealclosestrealdisXY b. 均值插值法：将 L 层频率谱叠加在一起，找出（Xreal，Yreal）点周围最近邻的四个点（同 a 中的四个点） ，将这四个点的平均频率值作为点（Xreal，Yreal）的值。此种插值法下插值误差被定义为：222222()(X)(Y) (X)(Y)

21、(X)(Ygridijleft uprealleft uprealleft downrealleft downrealright uprealright uprdisXYXYXY 222) (X)(Y) / 4ealright downrealright downrealXYCut在 0.5 到 1 之间近似的取(0.5, 0.6, 0.7, 0.8, 0.9, 1)中的一个。使Cut遍历从 0.5 到 1，得到其使得插值误差最小的值作为Cut的最优解。如果Cut已经达到最优，但是插值误差还没有达到实际需要的状态，我们应该再继续增加层数 L 然后接着再继续重新优化Cut。当图像大小确定，插值方

22、法确定，计算出一个使得插值误差最小的Cut值之后，6 应用科技 第 41卷以后对于同样大小的图像，都可以用这个计算出来的参数来达到最佳的插值效果。4 基于查表技术的笛卡尔到极坐标的快速转换方法从笛卡尔到极坐标的转换，每个点需要四次计算，分别是两次正余弦计算和(xcos , ysin ) 两次乘法计算。由于二维傅里叶谱是关于原点对称的，只需计算出其上半部分的频率分布，下半部分可以通过共轭映射得到。对于大小为的图像，则其时间复杂度为 O () =O (2N2)。 对于大小固定的图像 I，由于笛卡尔坐标中的一点对应于极坐标中唯一的一点，因此我们建立了一个文件，用来存储笛卡尔坐标到极坐标对应位置之间的

23、映射信息，对于固定大小的图像，只需第一次计算其笛卡尔坐标和极坐标对应位置，然后将其映射关系存储到的(xcos , ysin ) 文件中。后续在对同样大小的图像进行笛卡尔到极坐标的转换时不用计算只需查文件即可知道笛卡尔到极坐标的对应位置信息。文件中存储的映射关系按极坐标中的顺序存储（从上到下从左到右） ，因此查找时候也按顺序查找，每个元素查找的时间复杂度为 O(1)，根据 2-D 傅里叶谱的对称性，只需找到上面一半即可，剩下一半共轭映射即可得到。因此查文件法的时间复杂度为 O () =O (N2/2)， 速度比原来的线性插值方法有了明显的提高。其查表映射模型如图 3 所示：左侧为笛卡尔频谱图，中

24、间为极坐标频谱图，最右边为存储对应映射信息的查找表。对于每一个初始计算其在笛卡尔坐标的对应坐标，并将其极坐标和笛卡尔坐标对应的位置信息存入查找表中，后续对于同样大小的图像只需读取此查找表即可，对极坐标从左到右从上到下（类似于矩阵的顺序存储）依次在查找表中找到其对应于笛卡尔坐标中的位置（此位置为第三部分插值完成后的对应位置信息） ，从而得到其极坐标频谱。图3：笛卡尔x-y 到极坐标 映射模型，左侧为笛卡尔频谱图，中间为极坐标频谱图，右边为存储对应映射信息的查找表。综合以上，图像中的直线检测可分为以下几个步骤（如图 4 所示）： 第 1 期 作者名，等：文章题目 7（1）用第三节所述的方法选择合适

25、的参数 L和Cut。（2）用（1）中得出的参数计算输入图像 I 的GIFT。（3）通过（2）获得 L 层的频谱图。（4）用第四节所述的方法将笛卡尔坐标转换到极坐标，并通过共轭映射得到完整的极坐标频谱。（5）通过对极坐标谱做 1-D IFFT 得到输入图像的 Radon 变换。（6）在蝶形区域中检测极大峰值点，其对应于输入图像中的直线。输输入入图图像像I IP1PiPL+ +. . . .笛笛卡卡尔尔坐坐标标傅傅里里叶叶谱谱选选择择合合适适的的G GI IF FT T参参数数L L和和 C Cu ut t 极极坐坐标标傅傅里里叶叶谱谱利利用用查查表表法法进进行行笛笛卡卡尔尔到到极极坐坐标标的的转

26、转换换R Ra ad do on n变变换换蝶蝶形形区区域域1D-FFT-1输输出出目目标标直直线线. . . .峰峰值值检检测测图4： 基于改进的GIFT 实现的Radon 变换进行的直线检测步骤方框图5 仿真结果与分析本节通过仿真实验分别分析了所提出的 GIFT参数选取方法和笛卡尔到极坐标的快速转换方法的性能。5.1 GIFT 参数选取方法的仿真结果及分析综合时间花费和精确度方面的考虑，我们取L=3。我们将Cut中前两层的四个值分别从 0.5 取到 1，间隔为 0.1，第三层参数皆取 1，总共有1296（6*6*6*6=1296）种取值。a，最近邻插值法：通过第 3 节 a 中插值方法定义

27、的插值误差公式，Cut不同的取值对应的插值误差如图 5 所示，在第 862 个点，即Cut取（0.8,1）（1，0.8） （1,1）时插值误差最小为 5136.352。在最后一个点，即Cut取（1,1） （1，1） （1,1）时插值误差最大为 9665.285。相应的 Radon 变换结果如图六所示。图5：L=3，Cut取不同值时的插值误差，在第862 个点即（0.8,1） （1，0.8） （1,1） ）取得最小值图6：由左到右依次为原始输入图像，参数为（ 1,1） 8 应用科技 第 41卷（1,1） （1,1）时候得到的Radon 变换图像，参数为 （0.8,1）（1,0.8） （1,1）得

28、到的Radon 变换图像从图 6 可以看出，当参数Cut取（1,1） （1,1）（1,1）时，有明显的虚假峰值点，而当参数Cut取 （0.8,1） （1,0.8） （1,1）时不仅虚假峰值点消失，而且峰值点看起来更加细小锋锐，这样检测出的直线将更加精确。b. 均值插值法：通过第三节 b 中定义的均值插值法的插值误差公式，Cut不同的取值对应的插值误差如图 7 所示，在第 645 个点，即Cut取（0.7,1） （1，0.7） （1,1）时插值误差最小为29300.95 。在最后一个点，即Cut取（1,1）（1，1） （1,1）时插值误差最大为 41023.8。相应的Radon 变换结果如图 8

29、 所示。图7：L=3，Cut取不同值时的插值误差，在第645 个点即（0.7,1） （1，0.7） （1,1） ）取得最小值图8：由左到右依次为原始输入图像，参数为（ 1,1） （1,1） （1,1）时候得到的Radon 变换图像，参数为 （0.7,1）（1,0.7） （1,1）得到的Radon 变换图像从图 7 可以看出，当参数Cut取（1,1） （1,1）（1,1）时，虚假峰值点仍然存在，且峰值点比较粗，不易于其参数的获取。而当参数Cut取 （0.7,1）（1,0.7） （1,1）时虚假峰值点明显消失，而且峰值点更加细小锋锐，这样检测出的直线将更加精确。对于这两种不同的插值方法，由于均值插

30、值法具有平滑作用，可以使不规则的峰值点变得相对平滑规则一点，因此会更加适用于宽直线的检测。而最近邻插值法，则适合于细直线的检测。5.2 笛卡尔到极坐标的转换仿真与分析本节对不同大小的图像做了验证，两种方法的时间花费如表 1 所示。结果显示计算法的时间花费大约是查表法的四倍，这进一步验证了我们在第四部分对时间复杂度的分析。6.结论第 1 期 作者名，等：文章题目 9我们在现有 GIFT 的基础上，定义了不同插值方表 1：对于笛卡尔到极坐标的转换，查表法和计算法在不同大小图像下的时间花费的比较图像大小查表法(S)计算法(S)256 2560.009936 0.03949 512 5120.0667

31、02 0.26682 1024 10240.199045 0.79613 法下的插值误差，给出了一种其参数确定的方法，缩小了插值误差，使得检测结果更加精确。同时在图像频谱从笛卡尔坐标到极坐标转换的过程中，给出了一种基于查表的快速实现方法，用查表代替了原算法的正余弦和乘法操作，减少了基于GIFT 的 Radon 的直线检测的时间开销。对于其他有关笛卡尔到极坐标的转换的应用都有借鉴意义。我们的方法对基于 GIFT 的直线检测的精度和时间复杂度有了一定的提高，对于宽直线、线段及共线线段的检测还需进一步深入研究。参考文献1刘进，闫利，李德仁, 利用点对分析法检测线段J，武汉大学学报.信息科学版 33(

32、3)(2008)314317.Liu jin, Yan li, Li de-ren, Using of analysis method for line segment detection J, Geomatics and Information Science of Wuhan University 33(3)(2008)314317.2Aharon Bar Hillel, Ronen Lerner, Dan Levi, and Guy Raz, “Recent progress in road and lane detection: a surey J,” Machine Vision a

33、nd Applications, pp.1-19,2012 3Enrico Magli, Gabriella Olmo, On high resolution positioning of straight patterns via multiscale matched filtering of the Hough transform J, Pattern Recognition Letters 22(2001)705-713.4P. V. C. Hough, “Method and means for recognizing complex patterns P,” U.S.Patent3069654,1962.5R.O.Duda and P.E.Hart, “Use of Hough transform to detect lines and curves in pictures J,” Commun. ACM, VOL.15, no.1, pp. 11-15, 1972. 6D. Shi, L. Zheng, J. Liu, Advanced Hough transform using a multi layer fractional Fourier method J, IEEE Transactions o