一種非均勻圖濾波器組的設計方法

盧軍志,蔣俊正

(桂林電子科技大學 信息與通信學院,廣西 桂林 541004)

近年來,隨著科技和社會的不斷發展,信息數據呈現出海量化、多樣化、非規則化等特點。傳統的信號處理很難對非規則信號進行分析處理,即使可以,往往也會忽略網絡本身的一些結構特性。為了更好地處理非規則信號,研究者結合圖論等知識提出了圖信號處理,它能結合數據本身的結構特性對數據進行分析,在處理無線傳感器網絡信號等非規則信號都取得了不錯的效果[1-3]。作為傳統信號處理的一種拓展,圖信號處理同樣也存在傅里葉變換、濾波器及濾波器組等概念,其中圖濾波器組因其具備多分辨分析能力并能對信號進行多速率信號處理而備受研究者的關注。

關于圖濾波器組的研究是先從兩通道開始的。2006年一種可逆圖濾波器組的設計方法[4]被提出,并用于對傳感器網絡上信號進行多分辨分析和處理。Narang等[5]在2012年研究了兩通道臨界采樣正交圖濾波器組的設計,通過用切比雪夫逼近的方法設計出低通分析濾波器,根據正交特性求解出其余濾波器。該方法缺點在于不能滿足緊支撐特性。因此,2013年,Narang等[6]對正交性進行了松弛,變成雙正交,使整個濾波器組系統滿足完全重構特性和緊支撐特性,但其方法是基于對半帶濾波器的分解,因此無法保證良好的頻譜選擇性。隨后,研究者們采用不同的方法[7-8]設計濾波器組,以期達到權衡頻譜選擇性和完全重構特性的目的。漸漸地研究者的關注點從兩通道轉移到M通道上。2014年Tanaka[9]提出了M通道過采樣圖濾波器組的設計方法,通過構造過拉采樣普拉斯矩陣實現過采樣,最后實現完全重構;此后,一些基于循環圖的過采樣圖濾波器組的設計方法[10-13]被提出。2019年,一種M通道臨界采樣圖濾波器組的設計方法[14]被提出,通過用插值操作取代重構部分來實現重構。在目前的設計中,無論是兩通道還是M通道,分析濾波器組的頻帶劃分都是均勻的,但由于圖信號的頻率是離散的,頻率的分布可能會出現分布不均勻且部分集中的情況,這時非均勻的頻率劃分會更有意義。

在圖濾波器組的研究中,分布式實現[15-17]一直都是一個很重要的課題,特別是將其應用到大規模的網絡數據處理時,分布式實現能夠節省計算成本。目前大部分的圖濾波器組都采用切比雪夫多項式逼近的方法[15]來設計,這種方法通過增大階數獲得更好的頻率選擇特性,在階數小的情況下,頻率選擇特性較差,但具備較好的稀疏特性,能進行分布式實現。然而,這種分布式僅限于多項式形式下的濾波器,并不適用于非多項式形式的濾波器,如節點變濾波器組[18]等。2019年,Jiang等[16]提出了一種非下采樣兩通道圖濾波器組的分布式實現方法,濾波器的形式不再局限于多項式形式,也可以是非多項式形式,更具普適性。該方法將重構問題歸結為一個最小二乘問題,利用二階信息及近似牛頓法求解,其中用矩陣近似理論和圖的結構特性對海森矩陣的逆進行近似,從而實現分布式。

針對頻率的分布特性,提出了一種非均勻圖濾波器組的設計方法,并將其進行了分布式實現。根據圖頻率分布不均勻的情況,通過優化方法設計出具備良好頻率特性的多項式形式的分析濾波器,用非多項式形式的濾波器對其進行近似。在已知子帶信號和分析濾波器的前提下,將圖濾波器組的重構問題歸結成一個最小二乘問題。為了避免直接求解矩陣的逆,采用預處理梯度下降法對優化問題進行迭代求解。在迭代過程中,未利用目標函數的二階信息,方法更簡單。

1 基礎知識

圖信號處理中,無向圖G可由三維集合

表示,其中:V為無向圖的所有頂點的集合,N=|V|;E為無向圖的所有邊的集合;W={wij},i,j∈V為無向圖的權重矩陣。根據權重矩陣可得無向圖的度矩陣D,其對角線上元素

進而可定義拉普拉斯矩陣L=D-W及歸一化拉普拉斯矩陣Ln=I-D-1/2WD-1/2。在無向圖中,Ln是對稱的,對其進行特征分解,有Ln=UΛUT,U為特征向量組成的矩陣,Λ=diag([λ1,λ2,…,λN])為對角矩陣,λ1,λ2,…,λN為Ln的特征值,Ln的特征值范圍為[0,2]。無向圖上信號x定義為每個節點上的信號值的集合,x=[x1,x2,…,xN]T,如圖1所示。x的圖傅里葉變換定義為x^=UTx,其圖傅里葉逆變換為x=Ux^。根據圖傅里葉變換的定義及圖2可知,圖頻域上的頻率值即為圖拉普拉斯矩陣的特征值,是離散的,且λ=0.4和λ=0.8處具有明顯的頻率間隔。因此,需要根據頻率的聚集程度對頻譜進行劃分,進而設計出非均勻圖濾波器組。

圖1 節點數為50的隨機圖

圖2 圖1中信號的圖頻域表示

圖濾波的定義是,圖信號x經過圖濾波器后得到濾波后的輸出f,其表達式為

其中φ(k)為濾波器第k階的系數

根據圖2的頻率分布特性,主要考慮的是三通道非均勻圖濾波器組。由于目前圖上的采樣操作并不唯一,且沒有針對奇數通道的采樣設計,因此不討論圖濾波器組上的采樣操作。三通道非均勻非下采樣圖濾波器組結構框圖如圖3所示,x、分別為圖濾波器組的輸入和輸出,{H0,H1,H2}為分析濾波器組,{z0,z1,z2}為濾波器的子帶系數,zm=Hmx,m∈[0,1,2],{G0,G1,G2}為重構濾波器組。該框架的輸入輸出關系可表示為

圖3 三通道非下采樣圖濾波器結構組框圖

為滿足其完全重構特性,整個系統的傳遞函數T應滿足:

其中I為單位矩陣。

目前大部分的濾波器組設計均采用切比雪夫近似的方法同時設計分析濾波器和綜合濾波器。這些方法都是設計多項式形式的,設計自由度不高,且在良好的頻率選擇特性與好的局部特性之間不能很好地權衡。階數越高,頻率選擇性越好,但局部特性越差,越不能分布式實現。而非多項式形式的濾波器在提高設計自由度的前提下盡可能使得頻率選擇性更好,同時也擁有良好的局部特性。因此,選用非多項式形式中的NV圖濾波器作為分析濾波器,其設計步驟為:

1)通過約束濾波器的通帶平坦性和阻帶衰減得到頻率選擇性好的多項式形式的分析濾波器[19],其優化問題可表示為

φ=[φ(0),φ(1),…,φ(K)]T,b(λ)=[1,λ,…,λK]T。式(3)的前項是對濾波器通帶平坦性的約束,a、b為濾波器的通帶截止頻率;后項是對阻帶衰減的約束,c、d為濾波器的阻帶截止頻率,α為可調整參數。確定好濾波器的通帶、阻帶截止頻率后,就能通過求解式(3)的優化問題得到圖濾波器的系數。

2)將設計好的多項式濾波器當作理想濾波器,再用優化的方法設計出階數較低且具有良好頻率選擇性的NV 圖濾波器[18]。在該方法中,通過最小化Frobenius范數

得到最優的濾波器系數,Ck為系數矩陣。NV 濾波器的優點是獲得更小階數、更好頻率選擇特性的濾波器,同時所需設計的系數變多,設計自由度變高,設計難度也變大。

圖濾波器組的重構部分并不需要像分析濾波器一樣具有良好的頻譜選擇特性,只需滿足完全重構特性即可。因此,重構部分的實現也不一定需要通過重構濾波器來實現,且目前并無太多關于非多項式形式圖濾波器組的設計方法。在給定了分析濾波器組{H0,H1,H2}及子帶信號{z0,z1,z2}的前提下,將重構問題歸結為一個優化問題:

此最小二乘問題的最優解為

最優解的求解需要進行矩陣求逆運算,而矩陣求逆的復雜度是O(N3)。若矩陣維度很大,且求逆矩陣無特殊性質的情況下,求逆的計算代價很高,且可能存在矩陣病態問題,因此采用一種預處理分布式梯度下降法來求解這個逆濾波問題。

2 設計方法

逆濾波問題是一個線性問題,可采用梯度法進行迭代求解,并采用預處理技術加速迭代方法的收斂速度。預處理技術的基本思想是在原本的線性問題中加入預處理算子,使之能等價轉換為新的線性問題。這么做的好處是能夠獲得更快的收斂速度,同時在一些條件數很差的系統中,還能起到改善條件數的作用。本研究選取的預處理算子P定義為

其中:B(i,ω(H))={j∈V,ρ(i,j)≤ω(H)}為節點i的ω(H)階以內所有鄰居節點的集合;ω(H)為矩陣H的測地距離,ω(H)≥0;ρ(i,j)為從節點i到達節點j所需的最短路徑。ω(H)與濾波器的階數有關,是階數的2倍。設置=P-1/2HP-1/2,類似歸一化拉普拉斯矩陣的操作,對矩陣H進行歸一化處理。本研究所選的預處理形式是右預處理形式:

將其與梯度法結合后,有

再經過變換后,可得

在整個方法中,避免了復雜矩陣的求逆問題。矩陣的測地距離ω(H)是濾波器階數的2倍,而由于所設計的濾波器階數小,故ω(H)很小。因此,在每次迭代過程中,節點只與其少量的鄰居進行信息交換,整個過程可分布式實現。該方法對每個節點i上信號進行分布式重構的算法流程如下:

將所有的(M)(i)進行組合,可得到所有節點最終的重構信號值。由算法流程可看出,在整個迭代過程中,計算復雜度最高的操作就是矩陣與向量的相乘,此計算復雜度比矩陣求逆的計算復雜度低了一個數量級。因此,該方法的計算復雜度小于直接求解的復雜度,且在圖規模很大的情況,這種優勢會更明顯。

3 仿真實驗

首先給出關于三通道非均勻圖濾波器組的分析濾波器組的設計及分析,然后給出該方法與現有的分布式迭代方法的對比。仿真所用的圖信號如圖1所示,所有仿真均在相同環境下進行。

實驗1根據圖2的頻率分布特性,通過優化非均勻分析濾波器組的系數,設計出如圖4所示的非均勻頻譜劃分的分析濾波器組。h0、h1、h2分別表示低通、帶通和高通非均勻分析濾波器的頻率響應,3個濾波器的階數都是16。從圖4可看出,低通、高通分析濾波器的通帶都比較平坦,頻率選擇特性都很好,高階多項式濾波器雖然頻率選擇特性好,但局部特性很差,并不適合應用于分布式方法中,因此采用NV濾波器[18]對設計好的多項式濾波器進行近似。在實驗中,設計了階數依次為1、2和3的NV 濾波器,分別用K1、K2、K3表示。但由于NV 濾波器并不存在頻率響應的說法,為了說明所得到的NV濾波器的濾波性能與圖4的性能相近,將高頻子帶信號進行比較來說明近似效果,觀察NV濾波器經過高頻濾波后的得到的高頻子帶信號的頻譜圖是否與多項式形式濾波器一致,從而判斷NV形式的濾波器是否達到了較好的近似效果。圖5為輸入信號經過不同形式的高通濾波器后得到的子帶信號頻域表示。從圖5可看出,NV形式濾波器濾波得到的子帶信號頻譜盡管在少許頻率分量上會有幅度上的小差別,但整體上濾波效果與多項式形式的效果接近。因此,采用NV形式濾波器來近似高階多項式形式濾波器的結果是可行的,能取得同樣的效果。

圖4 設計得到的三通道非均勻分析濾波器組的幅度響應

圖5 相同信號經過不同濾波器得到的高頻子帶信號的頻域表示

實驗2對圖信號進行分布式重構的實驗仿真,總的迭代次數為200,分析濾波器基于例1的多項式分析濾波器,是通過優化設計出的非多項式形式的分析濾波器。當濾波器分別為K1、K2和K3時,不同迭代方法的收斂曲線分別如圖6、7和圖8所示。相對誤差為‖(m)-x‖2/‖x‖2。在仿真中發現,當步長取0.9時,分布式梯度法[20]能達到最優的效果。因此,在不同的階數下,該方法均采用相同的步長。根據圖6～8可知,本方法的迭代收斂次數比分布式梯度法[20]要少很多,與分布式牛頓法[17]相差不大,在不使用二階信息的前提下,取得了比一般分布式梯度法更快的收斂速度,表明預處理技術能夠有效加快迭代收斂的速度;在階數不斷增大時,所有算法的收斂次數都在減少,原因在于階數增大,節點與周圍鄰居節點的通信次數變多,獲得的有用信息增多,通過不斷的信息交換,就能更快地達到收斂。表1為迭代完成后本方法在不同階數條件下的重構誤差。從表1可看出,本方法能夠進行分布式重構,且重構誤差比分布式梯度法[20]小,與分布式牛頓法[17]差距不大。

表1 迭代完成后本算法在不同濾波器階數下的重構誤差

圖6 采用K1時,不同方法的收斂曲線

圖7 采用K2時,不同方法的收斂曲線

圖8 采用K3時,不同方法的收斂曲線

4 結束語

針對頻率分布不均勻的情況,提出了一種非均勻非下采樣圖濾波器組的設計方法,并進行了分布式實現。根據圖頻率的分布特性,設計了具備良好頻率劃分特性及稀疏特性的低階非多項式分析濾波器。在已知分析濾波器和子帶信號的前提下,將圖濾波器組的重構問題歸結為一個最小二乘問題,并采用預處理梯度法對其進行迭代求解。仿真結果表明,加入預處理算子后,能夠加快收斂速度,且比利用二階信息的迭代方法擁有更低的計算成本。