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

1、文章题目文章题目一种改进的广义插值傅里叶变换方法一种改进的广义插值傅里叶变换方法 创创 新新 点点 自自 述述 本文创新点有两个方面： 第一点：在现有广义插值傅里叶变换（GIFT）的基础上提出了一种选择其最优参数的方法，使 得插值误差达到最小，提高了直线检测的精度。 第二点：在笛卡尔坐标到极坐标的转换方面，传统做法是通过计算来完(xcos , ysin ) 成，这样做的一个不足是消耗大量的时间。考虑到从笛卡尔坐标到极坐标的转换是一对一映射，这 种映射关系与图像的具体内容无关，只与像素点的位置信息有关，因此本文提出了一种快速转换方 法。首先，对于大小固定的图像来说，用位置映射文件存储笛卡尔到极坐

2、标的映射信息。然后，通 过查找这个映射文件来实现从笛卡尔到极坐标的转换。相对于计算的方法来说，这种查表法大大节 省了计算时间。 doi: 网络出版地址： 一种改进的广义插值傅里叶变换方法 郑丽颖,何萌萌，刘娇 （哈尔滨工程大学计算机科学与技术学院，哈尔滨 ） 摘要：摘要：直线检测是计算机视觉领域中一个比较基本的任务。相对于 Hough 变换来说，Radon 变换由于其更加优越的性能在直线 检测方面具有广泛应用。本文对广义插值傅里叶变换方法（the Generalized Interpolated Fourier Transform （GIFT)） 进行了深入研究,并提出了新的参数选择方法。首先

3、，给出了一种 GIFT 参数的最优选择方法，缩小了插值误差。其次，为了 加快 GIFT 的运算速度，在笛卡尔坐标到极坐标转换过程中，建立了一个存储其对应位置信息的映射文件，用查表法来实现笛 卡尔到极坐标之间的转换。相对于通过乘法和正余弦实现的转换操作，查表法节省了大量时间开销。仿真结果表明：本文提 出的方法在精度和时间复杂度方面明显优于原算法。 关键词：关键词： Radon 变换；多层分数傅里叶变换；参数选择；查表法；直线检测 中图分类号：（作者本人填写） 文献标志码：A 文章编号：1009-671X（2011）01-0004-04 Method for Improving the Gener

4、alized Interpolated Fourier Transform ZHENG Li-ying，HE Meng-meng, LIU Jiao (College of computer science and technology, Harbin engineering university, Harbin , China ) Abstract：Straight line detection is fairly common in computer vision community. Compared with Hough transform, Radon transform has b

5、een widely used for detecting Straight lines due to its superior capability in terms of computing time. A method for improving the performance of the Generalized Interpolated Fourier Transform (GIFT) has been proposed in this paper. First, the proposed method presents a principle to optimize the par

6、ameters of the GIFT. Then the method establishes a position mapping file for the Cartesian to polar coordinates transformation. Comparing to the original multiplication and cosine operation, looking up mapping files saves a lot of time consuming. Simulation results show that the computational comple

7、xity of the proposed method is obviously superior to the original GIFT. Keywords: Radon Transform; Multilayer fractional Fourier transform; Parameter selection; Look up mapping files; Straight line detection 11 引言 直线特征具有平移、旋转和尺度不变等良好特 性。正确有效的提取图像中的直线特征，对于提高 收稿日期：2014-09-19. 网络出版日期： 作者简介：何萌萌(1986), 男

8、, 硕士研究生，E- mail； 通信作者：郑丽颖(1976), 女, 教授，博士，E- mail： 感兴趣目标的识别率和算法的鲁棒性有着重要的意 义。作为一个比较基本的图像处理任务，直线检测 广泛用于目标物体的识别、形状检测、道路/航线检 测等应用上123。 众所周知，Hough 变换的一个重要应用是直线 检测45。但是 Hough 变换存在一些不足。首先， 在进行 Hough 变换之前需进行边缘检测，Hough 变 换的结果对边缘检测的结果高度敏感6；第二， Hough 变换的大量时间上的花费对一些实时应用来 说是不可接受的,比如说车辆自动驾驶系统中的道路 边线检测，以及航道检测等3。 从

9、数学定义上讲，Radon 变换与 Hough 变换是 等效的7。但是从实现方式上看，Radon 变换更优 于 Hough 变换。这是因为中心切片定理从理论上保 证了可以使用快速傅里叶变换（Fast Fourier Transform(FFT)）方法来实现 Radon 变换，从而使 其具有更高的计算效率。然而实际应用表明：这种 快速变换方法的结果直接受到笛卡尔-直角坐标变换 过程中插值误差的影响。插值误差导致图像的 Radon 变换中存在较多的虚假峰值点，从而影响直 线检测的精度68910。 Pan 等人在图像配准中提出了一种可修改的多 层分数傅里叶方法9，Shi 等人在 Pan 的基础上提出

10、了一种傅里叶变换和 Hough 蝶形区域联合起来，在 峰值检测之前加了个一个带通滤波器起到峰值增强 作用，从而可以得出更为精确的直线检测结果6。 通过中心切片定理1112，Radon 变换可以用快速傅 里叶变换来实现，而多层分数傅里叶变换则被用来 解决传统快速傅里叶变换的插值误差问题。Zheng 等人提出了一种广义插值傅里叶变换（GIFT）的方 法10。通过在 X 和 Y 轴分别使用不同的参数使插 值更加灵活。GIFT 方法中，参数 L 和Cut = 的选择是至关重要的，这里 L 和 12 () 分别是 GIFT 中分数傅里叶变换的层数和 12 () X-Y 轴的阶数。Pan 等人的方法中，参

11、数Cut中 两个值是相等的，且参数 L 和Cut的选择， 12 () 只定义了某一种插值情况下的插值误差，计算时只 选择了部分点来参与计算9。本文介绍了一种最优 选择合适的参数 L 和的方法，使得插值误 12 () 差尽可能小，从而达到提高直线检测精度的目的。 但是，无论 Pan 等人的方法，还是 Shi 和 Zheng 等 人的方法68910，都需要计算从笛卡尔坐标到极坐 标的转换操作。从笛卡尔坐标到极坐标的转换包含 了大量的乘法和正余弦操作，因此这一转换过程需 要花费大量时间。考虑到从笛卡尔坐标到极坐标的 转换是一对一映射，这种映射关系与图像的具体内 容无关，只与像素点的位置信息有关，本文

12、在介绍 完 GIFT 参数选择方法之后又提出了一种快速转换 方法。首先，对于大小固定的图像来说，用位置映 射文件存储笛卡尔到极坐标的映射信息。然后，通 过查找这个映射文件来实现从笛卡尔到极坐标的转 换。相对于计算的方法来说，这种查表法大大节省 了计算时间。 2 基于 GIFT 的 Radon 变换 Radon 变换在角度 的线积分公式如下： (x,y)( , )(x,y) (xcosysin)dxdyRff 其中 R f (x, y)是函数 f(x, y)的二维 Radon 变换7。 Radon 变换在数学意义上等效于 Hough 变换，被广 泛用于直线检测中。 令表示切片操作，F1 和 F2

13、 分别表示一维和S 二维傅里叶变换，则傅里叶中心切片定理1112可以 表示为： 12 R f(x,y)( )F f(x,y)( , )( )FS 这里 f(x,y)(x)(xcos ,xsin )Sf 其中是 Radon 变换在角度的投影。公式R （2）描述的中心切片定理可表述如下：函数的 Radon 变换在角度的投影的一维傅里叶变换等于 函数的二维傅里叶变换在同样角度的投影。因此， 通过执行函数（图像）的二维傅里叶变换，插值实 现笛卡尔到极坐标的转换，对结果的每一行执行一 维傅里叶逆变换来实现其 Radon 变换是完全可行的。 但是快速傅里叶变换（FFT）会增加混淆问题，容 易产生虚假峰值点

14、（如图 1 所示） ，使得直线检测 的精确度下降。 图1：快速 Radon 变换中的虚假峰值 为了解决混淆问题，Zheng 等人提出了一种广 义插值傅里叶变换（GIFT）的方法10， 图 像 f (n1, n2)的 GIFT 被定义如下： 12 12 11 22 , 111222 1212 22 2 (nknk ) (k ,k )(n ,n )exp() NN NN nn j Ff N 其中 f(n1,n2)|-N/2n1,n2N/2-1)是大小为 的图像, 。通过叠加具有不同阶 12 01 数的插值傅里叶变换 F，可以得到类似于 12 () 极坐标形式的频率插值网格（如图 2 所示10） 。

15、随 着阶数取不同的值，所得到的频率插值网 12 () 格会具有不同的形状，其中水平方向频率的范围为 ，而垂直方向的范围为。 11 () 22 () 多层联合起来形成一个完整的傅里叶频谱。 这样 形成的频率域比传统的单层傅里叶变换包含更多的 采样点，从而使得混淆效果最小。 图2：GIFT 的频率分布，其中 *, o, +分别对应的 (取值分别为(1,1),(0.8, 0.7) 和 (0.3,0.5) 12 () GIFT 网格的分辨率依赖于两个参数，分别 是层数 L 和近似的分数阶数Cut，其定义为： (4) 1212 12 (,)|i1,2,.L,0,1 and 1 iiii LL Cut 频

16、率域的插值网格被定于如下： 1 L i t PP 其中 11221212 (k ,k )|,k,(,)Cut (6) 22 iiiii NN Pk 从笛卡尔到极坐标的转换方面，传统的方法是 通过计算每一个对应点。由于(xcos , ysin ) 二维傅里叶谱是关于原点对称的，因此只需计算出 其上半部分的傅里叶谱，其下半部分可以通过共轭 映射来得到。其上半部分笛卡尔坐标到极坐标xy 的转换用了一种线性插值方法： , 11 r mn 其中，m 和 n 是根据实际需要精确2/ 2rN 度而提前定义好的可调整正整数,一般取(m=0.5N)6。 图像的大小是，相应的极坐标网格大小 是n，通过计算每一个极

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

18、义了一种最近 12 邻插值法下的插值误差，由于在计算插值误差时候 这个过程比较慢，采用了只计算部分点的插值误差 来估计全局插值误差。这样计算出来的插值误差可 能会不太精确。而本文提出的方法，定义了不同插 值方法下的插值误差，并且在笛卡尔到极坐标转换 中本文采用查表法（见第四节） ，对于固定大小的 图像，只需计算一次Cut，因此在计算插值误差时 可以不用考虑时间方面的花费，通过计算全局插值 误差来求得是插值误差最小的参数，从而使得结果 更加精确。 考虑到从笛卡尔到极坐标的转换过程中，极坐 标远离原点的部分将会变得稀疏，而这部分正好对 应于高频区域。在直线检测中，高频区域包含更多 更有用的信息，所

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

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

21、gridijleft uprealleft upreal left downrealleft downreal right uprealright upr disXY XY XY 2 22 ) (X)(Y) / 4 eal right downrealright downreal XY Cut在 0.5 到 1 之间近似的取(0.5, 0.6, 0.7, 0.8, 0.9, 1)中的一个。使Cut遍历从 0.5 到 1，得到其 使得插值误差最小的值作为Cut的最优解。如果 Cut已经达到最优，但是插值误差还没有达到实际 需要的状态，我们应该再继续增加层数 L 然后接着 再继续重新优化Cut。当

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

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

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

25、 （1）用第三节所述的方法选择合适的参数 L 和Cut。 （2）用（1）中得出的参数计算输入图像 I 的 GIFT。 （3）通过（2）获得 L 层的频谱图。 （4）用第四节所述的方法将笛卡尔坐标转换 到极坐标，并通过共轭映射得到完整的极坐标频谱。 （5）通过对极坐标谱做 1-D IFFT 得到输入图 像的 Radon 变换。 （6）在蝶形区域中检测极大峰值点，其对应 于输入图像中的直线。 输输入入图图像像I I P1 Pi PL + + . . . . . . 笛笛卡卡尔尔坐坐标标傅傅 里里叶叶谱谱 选选择择合合 适适的的 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，间隔

27、为 0.1，第三层参数皆取 1，总共有 1296（6*6*6*6=1296）种取值。 a，最近邻插值法：通过第 3 节 a 中插值方法定 义的插值误差公式，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：由左到右依次为原始输

28、入图像，参数为（ 1,1） （1,1） （1,1）时候得到的Radon 变换图像，参数为 （0.8,1） （1,0.8） （1,1）得到的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）时插值误

29、差最小为 29300.95 。在最后一个点，即Cut取（1,1） （1，1） （1,1）时插值误差最大为 41023.8。相应的 Radon 变换结果如图 8 所示。 图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）时，虚假峰值点仍然存在，且峰值点比较粗， 不易于其参数的获

30、取。而当参数Cut取 （0.7,1） （1,0.7） （1,1）时虚假峰值点明显消失，而且峰值 点更加细小锋锐，这样检测出的直线将更加精确。 对于这两种不同的插值方法，由于均值插值法 具有平滑作用，可以使不规则的峰值点变得相对平 滑规则一点，因此会更加适用于宽直线的检测。而 最近邻插值法，则适合于细直线的检测。 5.2 笛卡尔到极坐标的转换仿真与分析 本节对不同大小的图像做了验证，两种方法的 时间花费如表 1 所示。结果显示计算法的时间花费 大约是查表法的四倍，这进一步验证了我们在第四 部分对时间复杂度的分析。 6.结论 我们在现有 GIFT 的基础上，定义了不同插值 方 表 1：对于笛卡尔到

31、极坐标的转换，查表法和计算法在 不同大小图像下的时间花费的比较 图像大小查表法(S)计算法(S) 256 2560. 0.03949 512 5120. 0.26682 1024 10240. 0.79613 法下的插值误差，给出了一种其参数确定的方法， 缩小了插值误差，使得检测结果更加精确。同时在 图像频谱从笛卡尔坐标到极坐标转换的过程中，给 出了一种基于查表的快速实现方法，用查表代 替了原算法的正余弦和乘法操作，减少了基于 GIFT 的 Radon 的直线检测的时间开销。对于其他 有关笛卡尔到极坐标的转换的应用都有借鉴意义。 我们的方法对基于 GIFT 的直线检测的精度和时间 复杂度有了一

32、定的提高，对于宽直线、线段及共线 线段的检测还需进一步深入研究。 参考文献 1刘进，闫利，李德仁, 利用点对分析法检测线段J，武 汉大学学报.信息科学版 33(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

33、Guy Raz, “Recent progress in road and lane detection: a surey J,” Machine Vision and 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. 4

34、P. V. C. Hough, “Method and means for recognizing complex patterns P,” U.S.Patent,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 Tran