實值離散多窗Gabor變換窗函數(shù)求解快速算法

周高明,陶　亮,王華彬,李　銳

(安徽大學 計算智能與信號處理教育部重點實驗室,安徽 合肥　230039)

實值離散多窗Gabor變換窗函數(shù)求解快速算法

周高明,陶亮*,王華彬,李銳

(安徽大學 計算智能與信號處理教育部重點實驗室,安徽 合肥230039)

摘要:針對多窗實值離散Gabor變換(real-valued discrete Gabor transform，簡稱RDGT),綜合窗簇與分析窗簇之間雙正交性關(guān)系的窗函數(shù)計算復(fù)雜性高的問題,提出一種快速窗函數(shù)求解算法．該方法利用快速離散Hartley變換(discrete Hartley transform，簡稱DHT)及Hartley函數(shù)的正交性簡化了窗函數(shù)的雙正交條件關(guān)系式,從而降低窗函數(shù)計算復(fù)雜度．實驗結(jié)果表明了該快速算法的高效性．

關(guān)鍵詞:實值離散Gabor變換;多窗;快速算法

Gabor變換是有力的時頻分析工具之一[1-5],Gabor變換的系數(shù)能夠同時反映信號在時域與頻域的局部化信息,這一特點使得Gabor變換在信號檢測、圖像壓縮、圖像識別等非平穩(wěn)信號處理方面有廣泛的應(yīng)用[6-8]．傳統(tǒng)復(fù)值離散Gabor變換(complex-valued discrete Gabor transform，簡稱CDGT)采用單個固定窗函數(shù),具有固定的時頻分辨率這一缺點．受窗函數(shù)時寬-帶寬之間的制約關(guān)系,也即不確定性原理[9]限制,單窗CDGT時間分辨率和頻率分辨率存在著矛盾關(guān)系,不可能同時最好．為改善單窗CDGT時頻分辨率,文獻[10-11]將傳統(tǒng)單窗CDGT推廣到多窗CDGT,但僅局限于框架理論,而且沒有給出具體的快速算法,由框架理論求解多窗函數(shù)有局限性,相比之下,由雙正交分析法求窗函數(shù)比框架理論方法簡單、局限性小且易于給出快速算法[3]．另外,由于多窗CDGT比單窗CDGT的計算要復(fù)雜得多,研究快速多窗離散Gabor窗函數(shù)計算算法和快速多窗離散Gabor展開與變換算法,對Gabor變換的實時應(yīng)用有重要意義．為此,Hu等[12]提出了基于高斯窗的多窗RDGT方法,這種方法由實數(shù)運算代替?zhèn)鹘y(tǒng)CDGT的復(fù)數(shù)運算,并且利用快速DHT(discrete Hartley transform)加快了運算速度,因而在求解滿足雙正交關(guān)系的對偶窗、變換系數(shù)以及信號重建等方面都比CDGT簡單,易于硬件實現(xiàn)．作者在文獻[12]的基礎(chǔ)上推導(dǎo)出了一種多窗RDGT的窗函數(shù)的快速求解方法,這種方法利用Hartley函數(shù)的正交性可將原求解窗函數(shù)的雙正交約束條件式簡化,即將原非齊次方程組分解成若干獨立的子方程組,然后分別求解各個降維后的子方程組,這樣可以正確地求解分析窗并且節(jié)省了大量的計算時間．文中對比實驗結(jié)果表明利用該方法求解窗函數(shù)具高效性．

1基于高斯窗的多窗RDGT

1.1單窗RDGT

設(shè)x={x(0),x(1),…,x(L-1)}是長度為L的有限長序列,將其以L為周期進行拓展,關(guān)于信號x的RDGT展開式和變換式分別定義為式(1)、(2)[4]

(1)

(2)

其中:分析窗函數(shù)h(x)和綜合窗函數(shù)γ(x)也是以周期為L的進行拓展的有限長序列,如式(3)、(4)

(3)

(4)

(5)

其中：δ(k)表示Kronecker delta．在給定綜合窗的情況下,相關(guān)文獻[2-3]論述了如何由雙正交性關(guān)系式求解分析窗,這里不再贅述．

1.2多窗RDGT

設(shè)x(k)是離散時間周期為L的信號序列,關(guān)于x的多窗RDGT展開式和變換式定義如下[12]

(6)

(7)

其中

(8)

(9)

h(p)(k)=α(-p/2)h(α(-p)k),α≥1，

(10)

cas(x)=sin(x)+cos(x)，

(11)

(12)

由式(12)可知,只要給出P個綜合窗h(p)(k)即可求出對應(yīng)的P個分析窗γ(p)(k),而且不難看出第p個分析窗γ(p)(k)不只是與第p個綜合窗h(p)(k)有關(guān),而是與全部P個綜合窗h(p)(k)有關(guān)．式(12)矩陣形式可表示為

Hγ=v，

(13)

其中

(14)

(15)

γ(p)={γ(p)(0),γ(p)(1)，…，γ(p)(L-1)}1×L，

(16)

(17)

(18)

過抽樣條件下(13)式中有多解,取其最小范數(shù)解,即

γ=HT(HHT)-1v.

(19)

2多窗RDGT窗函數(shù)的快速求解方法

(20)

簡寫為

(21)

其中

(22)

(23)

即

(24)

矩陣形式為

Hjγj=vj,

(25)

其中

(26)

(27)

(28)

(29)

(30)

求解式(25),在過抽樣條件下求其最小范數(shù)解是

(31)

3實驗

實驗使用編程工具是MATLAB R2013a、Windows 732位操作系統(tǒng),系統(tǒng)內(nèi)存4.00 GB．采用形式為式(32)所示.以長度為L=512點的離散高斯函數(shù)作為基本窗,如圖1(a)所示.取綜合窗的個數(shù)P=4,調(diào)制參數(shù)α=2,有

(32)

由公式(10)可求得子綜合窗族h(p)(k),形如式(33),4個子窗的形狀如圖1(b)所示．

(33)

由快速算法求出的分析窗族和非快速算法求出的分析窗族分別如圖1(c)～(f)所示.其中M=16,N=32,臨界抽樣,如圖1c、1d所示;M=32,N=64,過抽樣率為4,如圖1(e)、1(f)所示．相同抽樣條件下兩種方法得到的差值如圖1g、1h所示,差值控制在10-16～10-14數(shù)量級范圍內(nèi),由此驗證了論文提出的快速算法的正確性．

兩種算法在不同抽樣條件下的計算時間比較如表1所示,算法運行時間均是多次運行取平均值.由表1可以看出,在不同抽樣條件下,采用論文快速算法求解分析窗所需要的計算時間比文獻[12]的非快速算法明顯減少,可以看出論文算法的高效性．兩種算法在不同數(shù)量綜合窗下的計算時間如表2所示,實驗采取了過抽樣條件(M=64,N=128), 算法運行時間均是多次運行取平均值.由表2可以看出,在不同數(shù)量的綜合窗下,快速算法求解分析窗的時間均比非快速算法要少,這再次體現(xiàn)了論文算法的優(yōu)越性．

表1　兩種算法在不同抽樣點下的計算時間比較

表2　兩種算法在不同數(shù)量綜合窗下的計算時間比較

4結(jié)束語

Gabor變換是廣泛應(yīng)用的時頻分析方法之一,快速求解Gabor變換窗函數(shù)是Gabor變換算法首要解決的問題．論文首先回顧了基于高斯窗的單窗和多窗RDGT展開與變換理論,然后提出了一種采用雙正交分析法計算M-RDGT窗函數(shù)的快速算法并給出了理論推導(dǎo)過程,最后通過實驗驗證了該方法的高效性．由于算法的本質(zhì)是將大的線性方程組求解問題轉(zhuǎn)化成多個彼此獨立的小線性方程組的求解問題,再將各個獨立的解綜合得到分析窗的最終解的過程,由于多窗RDGT算法復(fù)雜性比單窗RDGT要高,考慮實時應(yīng)用,可以將窗函數(shù)快速算法并行化實現(xiàn)加速變換,即將每個分解后的子方程組求解用一個并行通道去計算,下一步的工作可考慮采用并行處理方法進一步減少運算時間．

參考文獻：

[1]Gabor D. Theory of communication: The analysis of information[J].J Inst Electr Eng, 1946,93(3):429-457.

[2]Wexler J, Raz S. Discrete Gabor expansions[J]. Signal Processing，1990, 21(3): 207-220.

[3]Qian S, Chen D. Discrete Gabor transform[J].IEEE Transactions on Signal Processing, 1993, 41(7): 2429-2438.

[4]Morris J M, Liu Y. Discrete Gabor expansion of discrete-time signals in l2(Z) via frame theory[J].IEEE Signal Processing Magazine, 1994, 40(2): 151-181.

[5]Daugman J G. Complete discrete 2-D Gabor transforms by neural networks for image analysis and compression[J]. Acoustics,Speech and Signal Processing, IEEE Transactions，1988, 36(7): 1169-1179.

[6]Lagae A, Lefebvre S, Dutre P. Improving Gabor noise[J]. IEEE Transactions on Visualization and Computer Graphics, 2011,17(8): 1096-1107.

[7]Cohen L. Time-frequency analysis[M].New Jersey:Prentice Hall,1995.

[8]Akan A, Chaparro L F.Multi-window Gabor expansion for evolutionary spectral analysis[J].Signal Processing, 1997,63(3):249-262.

[9]Zibulski M, Zeevi Y Y. Discrete multiwindow Gabor-type transforms[J].Signal Processing, IEEE Transactions on,1997, 45(6):1428-1442.

[10]Li S. Discrete multi-Gabor expansions[J].IEEE Transactions on Information Theory, 1999, 45(6):1954-1967.

[11]Balan R, Christensen J G, Krishtal I A, et al.Multi-window Gabor frames in amalgam spaces[J]. Mathematical Research Letters,2014,21(1):143-147.

[12]Hu X, Li R, Tao L. Multi-gabor expension and its fast algorithms based auxiliary biorthogonal function[J]. Journal of Computational Information Systems, 2013, 9(4): 1649-1657. multi-Gabor expansions[J].IEEE Transactions on Information Theory, 1999, 45(6):1954-1967.

[11]Balan R, Christensen J G, Krishtal I A, et al.Multi-window Gabor frames in amalgam spaces[J]. Mathematical Research Letters,2014,21(1):143-147.

[12]Hu X, Li R, Tao L. Multi-gabor expension and its fast algorithms based auxiliary biorthogonal function[J]. Journal of Computational Information Systems, 2013, 9(4): 1649-1657.

(責任編輯朱夜明)

Fast algorithm for window computation in multi-window

real-valued discrete Gabor transform

ZHOU Gao-ming, TAO Liang*, WANG Hua-bin, LI Rui

(Key Laboratory of Intelligence Computing and Signal Processing, Anhui University, Hefei 230039, China)

Abstract:To reduce the high complexity of the window computation using the biorthogonal relationship between the synthesis windows and the analysis windows in the multi-window real-valued discrete Gabor transform(M-RDGT), this paper presented a fast algorithm. It made the bi-orthogonal condition of computing basic window functions simpler by using fast discrete Hartley transform (DHT)and the orthogonality of the Hartley functions so that the computational complexity could be reduced. The experimental results of the algorithm also indicated that the proposed fast algorithm was more effective.

Key words:real-valued discrete Gabor transform; multi-window; fast algorithm

中圖分類號：TP391

文獻標志碼:A

文章編號:1000-2162(2015)05-0031-06

作者簡介：周高明(1990-),男,安徽安慶人，安徽大學碩士研究生;*陶亮(通信作者)，安徽大學教授,博士生導(dǎo)師,博士,E-mail:taoliang@ahu.edu.cn.

基金項目:國家自然科學基金資助項目(61372137);安徽大學信息保障技術(shù)研究中心課題 (ADXXBZ2014-11)

收稿日期：2015-02-10

doi:10.3969/j.issn.1000-2162.2015.05.006