鄭麗穎，何萌萌，劉嬌

哈爾濱工程大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院，黑龍江哈爾濱 150001

改進(jìn)的廣義插值傅里葉變換方法

鄭麗穎，何萌萌，劉嬌

哈爾濱工程大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院，黑龍江哈爾濱 150001

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

Radon變換；多層分?jǐn)?shù)傅里葉變換；廣義插值傅里葉變換；參數(shù)選擇；查表法；直線檢測

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

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

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

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

1 基于GIFT的Radon變換

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

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

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

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

在執(zhí)行方面，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）描述的中心切片定理可表述如下：函數(shù)的Radon變換在角度θ的投影的一維傅里葉變換等于函數(shù)的二維傅里葉變換在同樣角度的投影。因此，通過執(zhí)行函數(shù)（圖像）的二維傅里葉變換，插值實(shí)現(xiàn)笛卡爾到極坐標(biāo)的轉(zhuǎn)換，對結(jié)果的每一行執(zhí)行一維傅里葉逆變換來實(shí)現(xiàn)其Radon變換是完全可行的。但是FFT會增加混淆問題，容易產(chǎn)生虛假峰值點(diǎn)（如圖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。通過疊加具有不同階數(shù)（α1，α2）的插值傅里葉變換F，可以得到類似于極坐標(biāo)形式的頻率插值網(wǎng)格［12］（如圖2所示）。

圖2 GIFT的頻率分布

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

GIFT網(wǎng)格的分辨率依賴于2個參數(shù)，分別是層數(shù)L和近似的分?jǐn)?shù)階數(shù)C，其定義為

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

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

頻率域的插值網(wǎng)格被定于如下：

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

2 GIFT參數(shù)的選取方法

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

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

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

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

假定通過（x＝υcosφ，y＝υsinφ）計算得出的笛卡爾坐標(biāo)中對應(yīng)的點(diǎn)為（Xreal，Yreal）。

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

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

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

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

3 基于查表技術(shù)的笛卡爾到極坐標(biāo)的快速轉(zhuǎn)換方法

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

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

圖3 笛卡爾x-y到極坐標(biāo)

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

1）用第2節(jié)所述的方法選擇合適的參數(shù)L和C；

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

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

4）用第3節(jié)所述的方法將笛卡爾坐標(biāo)轉(zhuǎn)換到極坐標(biāo)，并通過共軛映射得到完整的極坐標(biāo)頻譜；

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

6）在蝶形區(qū)域中檢測極大峰值點(diǎn)，其對應(yīng)于輸入圖像中的直線。

圖4 基于改進(jìn)的GIFT實(shí)現(xiàn)Radon變換進(jìn)行的直線檢測

4 仿真結(jié)果與分析

本節(jié)通過仿真實(shí)驗分別分析了所提出的GIFT參數(shù)選取方法和笛卡爾到極坐標(biāo)的快速轉(zhuǎn)換方法的性能。

4．1 GIFT參數(shù)選取方法的仿真結(jié)果及分析

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

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

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

在第862個點(diǎn)，即C?。?．8，1）（1，0．8）（1，1）時插值誤差最小為5 136．352。在最后一個點(diǎn)，即C?。?，1）（1，1）（1，1）時插值誤差最大為9 665．285。相應(yīng)的Radon變換結(jié)果如圖6所示。

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

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

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

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

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

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

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

4．2 笛卡爾到極坐標(biāo)的轉(zhuǎn)換仿真與分析

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

表1 對于笛卡爾到極坐標(biāo)的轉(zhuǎn)換花費(fèi)時間比較

5 結(jié)束語

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

［1］劉進(jìn)，閆利，李德仁．利用點(diǎn)對分析法檢測線段［J］．武漢大學(xué)學(xué)報：信息科學(xué)版，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．基金項目：國家自然科學(xué)基金資助項目（61003128）．作者簡介：鄭麗穎（1976-），女，教授，博士；何萌萌（1986-），男，碩士研究生．

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

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