改進的廣義插值傅里葉變換方法

鄭麗穎，何萌萌，劉嬌

哈爾濱工程大學計算機科學與技術學院，黑龍江哈爾濱 150001

改進的廣義插值傅里葉變換方法

鄭麗穎，何萌萌，劉嬌

哈爾濱工程大學計算機科學與技術學院，黑龍江哈爾濱 150001

直線檢測是計算機視覺領域中一個比較基本的任務。相對于Hough變換來說，Radon變換由于其在計算時間上的優越性能在直線檢測方面具有廣泛應用。通過對廣義插值傅里葉變換方法（GIFT）進行研究，提出了參數選擇方法。首先，給出了一種GIFT參數的最優選擇方法，縮小了插值誤差。其次，為了加快GIFT的運算速度，在笛卡爾坐標到極坐標轉換過程中，建立了一個存儲其對應位置信息的映射文件，用查表法來實現笛卡爾到極坐標之間的轉換。相對于通過乘法和正余弦實現的轉換操作，查表法節省了大量時間開銷。仿真結果表明所提出方法在精度和時間復雜度方面明顯優于原算法。

Radon變換；多層分數傅里葉變換；廣義插值傅里葉變換；參數選擇；查表法；直線檢測

直線特征具有平移、旋轉和尺度不變等良好特性。正確有效地提取圖像中的直線特征，對于提高感興趣目標的識別率和算法的魯棒性有重要的意義。作為一個比較基本的圖像處理任務，直線檢測廣泛用于目標物體的識別、形狀檢測、道路／航線檢測等方面［1-4］。

眾所周知，Hough變換的一個重要應用是直線檢測［5-7］。但是Hough變換存在一些不足。首先，在進行Hough變換之前需進行邊緣檢測，Hough變換的結果對邊緣檢測的結果高度敏感［7］；第二，Hough變換花費的大量時間對一些實時應用來說是不可接受的，比如說車輛自動駕駛系統中的道路邊線檢測，以及航道檢測等［4］。

從數學定義上講，Radon變換與Hough變換是等效的［8］。但是從實現方式上看，Radon變換更優于Hough變換。這是因為中心切片定理從理論上保證了可以使用快速傅里葉變換（fast Fourier trans-form，FFT）方法來實現Radon變換，從而使其具有更高的計算效率。然而實際應用表明：這種快速變換方法的結果直接受到笛卡爾－直角坐標變換過程中插值誤差的影響。插值誤差導致圖像的Radon變換中存在較多的虛假峰值點，從而影響直線檢測的精度［9-12］。

Pan等［11］在圖像配準中提出了一種可修改的多層分數傅里葉方法，Shi等［9］在Pan的基礎上提出了一種傅里葉變換和Hough蝶形區域聯合起來，在峰值檢測之前加了個一個帶通濾波器起到峰值增強作用，從而可以得出更為精確的直線檢測結果。通過中心切片定理［13-14］，Radon變換可以用快速傅里葉變換來實現，而多層分數傅里葉變換則被用來解決傳統快速傅里葉變換的插值誤差問題。Zheng等［12］提出了一種廣義插值傅里葉變換（generalized interpolated Fourier transform，GIFT）的方法。通過在X和Y軸分別使用不同的參數使插值更加靈活。GIFT方法中，參數L和C＝（α1，α2）的選擇是至關重要的，這里L和C分別是GIFT中分數傅里葉變換的層數和X-Y軸的階數。Pan等的方法中，參數C中（α1，α2）的值是相等的，且參數L和C的選擇只定義了某一種插值情況下的插值誤差，計算時只選擇了部分點來參與計算［11］。文中介紹了一種最優選擇合適的參數L和（α1，α2）的方法，使得插值誤差盡可能小，從而達到提高直線檢測精度的目的。但是，無論Pan等［11］的方法，還是Shi［9］和Zheng等［12］的方法，都需要計算從笛卡爾坐標到極坐標的轉換操作。從笛卡爾坐標到極坐標的轉換包含了大量的乘法和正余弦操作，因此這一轉換過程需要花費大量時間?？紤]到從笛卡爾坐標到極坐標的轉換是一對一映射，這種映射關系與圖像的具體內容無關，只與像素點的位置信息有關，文中在介紹完GIFT參數選擇方法之后又提出了一種快速轉換方法。首先，對于大小固定的圖像來說，用位置映射文件存儲笛卡爾到極坐標的映射信息；然后，通過查找這個映射文件來實現從笛卡爾到極坐標的轉換。相對于計算的方法來說，這種查表法大大節省了計算時間。

1 基于GIFT的Radon變換

Radon變換在角度θ的線積分公式如下：

R（f（x，y））＝λ（ρ，θ）＝

?f（x，y）δ（x cosθ＋y sinθ－ρ）d x d y（1）

式中R（f（x，y））是函數f（x，y）的二維Radon變換［8］。Radon變換在數學意義上等效于Hough變換，且根據中心切片定理可以通過快速傅里葉變換來快速實現，因此被廣泛用于直線檢測中。

在執行方面，Sθ表示切片（投影）操作，其中

Sθ［f（x，y）］（x′）＝f（x′cosθ，x′sinθ）

令F1和F2分別表示一維和二維傅里葉變換，則傅里葉中心切片定理［13-14］可以表示為

F1｛Rθ［f（x，y）］｝（υ）＝

Sθ｛F2［f（x，y））］（μ，η）｝（υ）（2）

式中Rθ是Radon變換在角度θ的投影。

式（2）描述的中心切片定理可表述如下：函數的Radon變換在角度θ的投影的一維傅里葉變換等于函數的二維傅里葉變換在同樣角度的投影。因此，通過執行函數（圖像）的二維傅里葉變換，插值實現笛卡爾到極坐標的轉換，對結果的每一行執行一維傅里葉逆變換來實現其Radon變換是完全可行的。但是FFT會增加混淆問題，容易產生虛假峰值點（如圖1所示），使得直線檢測的精確度下降。

圖1 快速Radon變換中的虛假峰值

為了解決混淆問題，Zheng等［12］提出了一種廣義插值傅里葉變換（GIFT）的方法，N×N圖像f（n1，n2）的GIFT被定義如下：（3）式中：｛f（n1，n2）｜－N／2≤n1，n2≤N／2－1）｝是大小為N×N的圖像，0＜α1，α2≤1。通過疊加具有不同階數（α1，α2）的插值傅里葉變換F，可以得到類似于極坐標形式的頻率插值網格［12］（如圖2所示）。

圖2 GIFT的頻率分布

圖2中橫軸縱軸分別表示笛卡爾坐標的XY軸，即圖像的長和寬，單位為像素。隨著階數（α1，α2）取不同的值，所得到的頻率插值網格會具有不同的形狀，其中水平方向頻率的范圍為（－πα1，πα1），而垂直方向的范圍為（－πα2，πα2）。多層聯合起來形成一個完整的傅里葉頻譜。這樣形成的頻率域比傳統的單層傅里葉變換包含更多的采樣點，從而使得混淆效果最小。

GIFT網格的分辨率依賴于2個參數，分別是層數L和近似的分數階數C，其定義為

C＝（α1i，α2i）｜i＝1，2，…，L

其中：0＜α1i，α2i≤1，α1L＝α2L＝1

頻率域的插值網格被定于如下：

從笛卡爾到極坐標的轉換方面，傳統的方法是通過（x＝υcosφ，y＝υsinφ）計算每一個對應點。由于二維傅里葉譜是關于原點對稱的，因此只需計算出其上半部分的傅里葉譜，其下半部分可以通過共軛映射來得到。其上半部分笛卡爾坐標x－y到極坐標υ－φ的轉換用了一種線性插值方法：

2 GIFT參數的選取方法

對于插值誤差來說，層數L和參數C＝（α1，α2）的選擇是至關重要的。層數L依賴于實際應用的類型。一般來講，層數越大，插值誤差越小。綜合考慮到插值誤差及其時間消耗，在大多數情況下推薦L取3或者4。實際上，正確的方法應該是如果精確度沒有達到要求的話就應該適當的增加層數L，同時，應該綜合考慮時間方面的花費［11］。

一旦層數L確定了，對C的選擇就是非?？量痰?。Pan等［11］提出的關于階數C的選擇方法，其（α1，α2）取值一樣，而且只定義了一種最近鄰插值法下的插值誤差，由于在計算插值誤差時候這個過程比較慢，采用了只計算部分點的插值誤差來估計全局插值誤差。這樣計算出來的插值誤差可能會不太精確。而文中提出的方法，定義了不同插值方法下的插值誤差，并且在笛卡爾到極坐標轉換中文中采用查表法，對于固定大小的圖像，只需計算一次C，因此在計算插值誤差時可以不用考慮時間方面的花費，通過計算全局插值誤差來求得是插值誤差最小的參數，從而使得結果更加精確。

考慮到從笛卡爾到極坐標的轉換過程中，極坐標遠離原點的部分將會變得稀疏，而這部分正好對應于高頻區域。在直線檢測中，高頻區域包含更多有用的信息，所以要考慮高頻區域中的插值問題。因此，將每一層的C＝（α1，α2）范圍限定在0．5～1。

對于不同的插值方法，插值誤差的定義是不同的。文中討論了2種不同的插值方法及其相應的參數選擇方法。

假定通過（x＝υcosφ，y＝υsinφ）計算得出的笛卡爾坐標中對應的點為（Xreal，Yreal）。

1）最近鄰插值法：將L層頻率譜疊加在一起，找出（Xreal，Yreal）點周圍最近鄰的4個點，即左上、左下、右上、右下4個方向距離（Xreal，Yreal）最近的4個點。計算出這4個點中距離（Xreal，Yreal）最近的點作為其插值點。此種插值法下插值誤差被定義為

式中dgrid（γi，θj）是計算得出的頻率譜中的每個實際點的插值誤差。在最近鄰插值法中，即為實際計算得到的點和距離其最近鄰點的距離：

2）均值插值法：將L層頻率譜疊加在一起，找出（Xreal，Yreal）點周圍最近鄰的4個點（同1）中的4個點），將這4個點的平均頻率值作為點（Xreal，Yreal）的值。此種插值法下插值誤差被定義為

C在0．5～1近似的?。?．5，0．6，0．7，0．8，0．9，1）中的一個。使C遍歷從0．5～1，得到其使得插值誤差最小的值作為C的最優解。如果C已經達到最優，但是插值誤差還沒有達到實際需要的狀態，應該再繼續增加層數L然后接著再繼續重新優化C。當圖像大小確定，插值方法確定，計算出一個使得插值誤差最小的C值之后，以后對于同樣大小的圖像，都可以用這個計算出來的參數來達到最佳的插值效果。

3 基于查表技術的笛卡爾到極坐標的快速轉換方法

從笛卡爾到極坐標的轉換，每個點需要4次計算（x＝υcosφ，y＝υsinφ），分別是2次正余弦計算和2次乘法計算。由于二維傅里葉譜是關于原點對稱的，只需計算出其上半部分的頻率分布，下半部分可以通過共軛映射得到。對于大小為N×N的圖像，則其時間復雜度為O（N／2×N×4）＝O（2N2）。

對于大小固定的圖像I，由于笛卡爾坐標中的一點對應于極坐標中唯一的一點，因此建立了一個文件，用來存儲笛卡爾坐標到極坐標對應位置之間的映射信息，對于固定大小的N×N圖像，只需第一次計算其笛卡爾坐標和極坐標對應位置（x＝υcos φ，y＝υsinφ），然后將其映射關系存儲到的文件中。后續在對同樣大小的圖像進行笛卡爾到極坐標的轉換時不用計算只需查文件即可知道笛卡爾到極坐標的對應位置信息。文件中存儲的映射關系按極坐標中的順序存儲（從上到下，從左到右），因此查找時候也按順序查找，每個元素查找的時間復雜度為O（1），根據二維傅里葉譜的對稱性，只需找到上面一半即可，剩下一半共軛映射即可得到。因此查文件法的時間復雜度為O（N／2×N）＝O（N2／2），速度比原來的線性插值方法有了明顯的提高。其查表映射模型如圖3所示。對于每一個（υ，φ）初始計算其在笛卡爾坐標的對應坐標，并將其極坐標和笛卡爾坐標對應的位置信息存入查找表中，后續對于同樣大小的圖像只需讀取此查找表即可。對極坐標從左到右，從上到下（類似于矩陣的順序存儲）依次在查找表中找到其對應于笛卡爾坐標中的位置（此位置為第3部分插值完成后的對應位置信息），從而得到其極坐標頻譜。

圖3 笛卡爾x-y到極坐標

綜合以上，圖像中的直線檢測可分為以下幾個步驟（如圖4所示）：

1）用第2節所述的方法選擇合適的參數L和C；

2）用步驟1）中得出的參數計算輸入圖像I的GIFT；

3）通過步驟2）獲得L層的頻譜圖；

4）用第3節所述的方法將笛卡爾坐標轉換到極坐標，并通過共軛映射得到完整的極坐標頻譜；

5）通過對極坐標譜做一維IFFT得到輸入圖像的Radon變換；

6）在蝶形區域中檢測極大峰值點，其對應于輸入圖像中的直線。

圖4 基于改進的GIFT實現Radon變換進行的直線檢測

4 仿真結果與分析

本節通過仿真實驗分別分析了所提出的GIFT參數選取方法和笛卡爾到極坐標的快速轉換方法的性能。

4．1 GIFT參數選取方法的仿真結果及分析

綜合時間花費和精確度方面的考慮，取L＝3。將C中前2層的4個值分別從0．5取到1，間隔為0．1，第3層參數都取1，共有1 296種取值。

1）最近鄰插值法。通過第2節1）中插值方法定義的插值誤差公式，C不同的取值對應的插值誤差如圖5所示。

圖5 最近鄰插值法L＝3，C取不同值時的插值誤差

在第862個點，即C取（0．8，1）（1，0．8）（1，1）時插值誤差最小為5 136．352。在最后一個點，即C取（1，1）（1，1）（1，1）時插值誤差最大為9 665．285。相應的Radon變換結果如圖6所示。

圖6 最近鄰插值法不同參數下得到的Radon變換圖像

從圖6可以看出，當參數C?。?，1）（1，1）（1，1）時，有明顯的虛假峰值點；而當參數C?。?．8，1）（1，0．8）（1，1）時不僅虛假峰值點消失，而且峰值點看起來更加細小鋒銳，這樣檢測出的直線將更加精確。

2）均值插值法：通過第2節2）中定義的均值插值法的插值誤差公式，C不同的取值對應的插值誤差如圖7所示，在第645個點，即C?。?．7，1）（1，0．7）（1，1）時插值誤差最小為29 300．95。在最后一個點，即C?。?，1）（1，1）（1，1）時插值誤差最大為41 023．8。相應的Radon變換結果如圖8所示。

圖7 均值插值法法L＝3，C取不同值時的插值誤差

圖8 均值插值法不同參數下得到的Radon變換圖像

從圖8可以看出，當參數C取（1，1）（1，1）（1， 1）時，虛假峰值點仍然存在，且峰值點比較粗，不易于其參數的獲取。而當參數C?。?．7，1）（1，0．7）（1，1）時虛假峰值點明顯消失，而且峰值點更加細小鋒銳，這樣檢測出的直線將更加精確。

對于這2種不同的插值方法，由于均值插值法具有平滑作用，可以使不規則的峰值點變得相對平滑、規則，更加適用于寬直線的檢測；而最近鄰插值法，則適合于細直線的檢測。

4．2 笛卡爾到極坐標的轉換仿真與分析

對不同大小的圖像做了驗證，2種方法的時間花費如表1所示。結果顯示計算法的時間花費大約是查表法的4倍，這進一步驗證了本文對時間復雜度的分析。

表1 對于笛卡爾到極坐標的轉換花費時間比較

5 結束語

在現有GIFT的基礎上，定義了不同插值方法下的插值誤差，給出了一種其參數確定的方法，縮小了插值誤差，使得檢測結果更加精確。同時在圖像頻譜從笛卡爾坐標到極坐標轉換的過程中，給出了一種基于查表的快速實現方法，用查表代替了原算法的正余弦和乘法操作，減少了基于GIFT的Radon的直線檢測的時間開銷。對于其他有關笛卡爾到極坐標的轉換的應用都有借鑒意義。文中方法對基于GIFT的直線檢測的精度和時間復雜度有了一定的提高，對于寬直線、線段及共線線段的檢測還需進一步深入研究。

［1］劉進，閆利，李德仁．利用點對分析法檢測線段［J］．武漢大學學報：信息科學版，2008，33（3）：314-317．

［2］HILLEL A B，LERNER R，LEVID，etal，Recentprogress in road and lane detection：a surey［J］．Machine Vision and Applications，2014，25（3）：727-745．

［3］HANJ，KIMD，LEE M，et al．Enhanced road boundary and obstacle detection using a downward-looking lidar sensor［J］．IEEE Transactions on Vehicular Technology，2012，61（3）：971-985．

［4］MAGLI E，OLMO G．On high resolution positioning of straight patterns via multiscale matched filtering of the Hough transform［J］．Pattern Recognition Letters，2001，22：705-713．［5］HOUGH P V C．Method and means for recognizing complex patterns：USA，3069654［P］．1962-12-18．

［6］DUDA R O，HART P E．Use of Hough transform to detect lines and curves in pictures［J］．Commun ACM，1972，15（1）：11-15．

［7］MOCHIZUKIY，TORIIA，IMIYA A．N-point Hough trans-form for line detection［J］．Journal of Visual Communication and Image Representation，2009，20（4）：242-253．

［8］DEANS S R．Hough transform from the Radon transform［J］．IEEE Transactions on Pattern Analysis and Machine Intelligence，1981（2）：185-188．

［9］SHID，ZHENG L，LIU J．Advanced Hough transform using amultilayer fractional Fouriermethod［J］．IEEE Transac-tions on Image Processing，2010，19（6）：1558-1566．

［10］HO C G，YOUNG R C D，BRADFIELD CD，et al．A fast Hough transform for the parametrisation of straight lines u-sing Fourier methods［J］．Real Time Imaging，2000，6（2）：113-127．

［11］PANW，QINH K，CHENY．An adaptable-multilayer fractional Fourier transform approach for image registration［J］．IEEE Transactions on Pattern Analysis and Machine Intelligence，2009，31（3）：400-414．

［12］ZHENG L，SHID．Advanced Radon transform using gener-alized interpolated Fouriermethod for straight line detection［J］．Computer Vision and Image Understanding，2011，115：152-160．

［13］MERSEREAU R M，OPPENHEIMA V．Digital recon-struction ofmultidimensional signals from their projections［J］．Proceedings of the IEEE，1974，62（10）：1319-1338．

［14］Jr EASTONR L，BARRETT H H．Tomographic transfor-mations in optical signal processing［M］．New York：Aca-demic Press，1987：335-386．

Method for improving the generalized interpolated Fourier transform

ZHENG Liying，HEMengmeng，LIU Jiao
College of Computer Science and Technology，Harbin Engineering University，Harbin 150001，China

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．The generalized interpolated Fourier transform（GIFT）is researched and on this basis a new parameter selec-tion method is proposed in this paper．First，the optimal selectionmethod for GIFT parameters is used to reduce in-terpolation error．Then in order to quicken the computation speed of GIFT，a look-upmapping filewhich stores cor-responding position information is established in the transformation process from Cartesian to polar coordinates．Comparing with the originalmultiplication and cosine operation，the look-up mapping file saves a lot of time cost．Simulation results show that the proposed method is obviously superior to the original GIFT in precision and time complexity．

Radon transform；multilayer fractional Fourier transform；generalized interpolated Fourier transform；parameter selection；look-up mapping files；straight line detection

TP391

A

1009-671X（2015）03-055-06

10．3969／j．issn．1009-671X．201409012

2014-09-19．

日期：2015-04-20．基金項目：國家自然科學基金資助項目（61003128）．作者簡介：鄭麗穎（1976-），女，教授，博士；何萌萌（1986-），男，碩士研究生．

鄭麗穎，E-mail：zhengliying＠hrbeu．edu．cn．

http：／／www．cnki．net／kcms／detail／23．1191．U．20150420．1013．010．html