0 引言

    在網絡、計算機視覺和高維云數據等領域中，圖提供了一個靈活的模型來表示數據。圖上的數據為附加到圖上每個網絡節點的信息值，可以把圖上的數據量化為樣本的有限集合，即圖信號^[1]。隨著圖信號處理的發展，越來越多的學者從事圖信號處理領域的研究工作。圖信號處理將傳統信號處理中的諸多概念和理論拓展至圖結構上，引申出了圖傅里葉變換等重要概念。同時，許多學者構造了圖小波和圖濾波器組^[2-10]，其具備多尺度變換特性，適合于處理大規模圖的圖信號。近年來，圖小波和圖濾波器組已被廣泛應用于圖信號的多分辨分析^[2]、壓縮^[3]和去噪^[4]。

    NARANG S K和ORTEGA A最早提出兩通道臨界采樣圖小波濾波器組的設計方法^[5]。在二分圖中，針對上下采樣運算引起的頻譜混疊現象，設計出正交鏡像圖小波濾波器組，該算法設計是針對于二分圖或可以分解為二分圖的圖信號。此后，NARANG S K和ORTEGA A構造出兩通道雙正交圖小波濾波器組^[6]，其具備頻域緊支撐，但此雙正交圖小波的設計方法未考慮濾波器的頻譜選擇性。文獻[7]提出兩通道雙正交圖濾波器組的優化設計方法，此設計算法充分考慮了頻譜選擇性，但是以更高的重構誤差為代價。SAKIYAMA A和TANAKA Y提出通道過采樣圖濾波器組的設計算法^[8]，過采樣對于圖信號的處理有更大的設計自由。文獻[9]綜合考慮M通道過采樣圖濾波器組的性能，采用優化算法設計出整體性能良好的M通道過采樣圖濾波器組，且具備頻譜選擇性，但其算法設計的圖濾波器組的去噪性能較差。文獻[10]針對循環圖提出了樣條圖小波濾波器組，并在循環圖的基礎上擴展到任意圖的樣條圖小波濾波器組。上述圖小波和圖濾波器組的結構中均含有圖信號的下采樣運算，然而對于一般圖結構的圖信號而言，基于圖染色的采樣模式并不精確，基于奇異值分解的采樣模式不適用于連通圖的處理，而基于最大生成樹的采樣模式對復雜圖進行采樣運算時也存在不精確的問題^[11]。目前，在圖濾波器組中，難以準確定義一般圖信號下采樣運算。而非下采樣圖濾波器組無需采樣運算，這樣可以避免由采樣所帶來的諸多問題。并且，目前非下采樣圖濾波器組的設計方法較少，有待深入研究。

    本文首先考慮兩通道非下采樣圖濾波器組的設計問題。采用樣條圖小波濾波器作為非下采樣圖濾波器組的分析濾波器組，然后通過兩種不同的方法設計綜合濾波器組。其中，算法一利用定點域的完全重構條件，通過正則化目標函數，直接求解出綜合濾波器，但算法一沒有考慮綜合濾波器的頻譜特性。為此，算法二采用優化手段綜合考慮濾波器組的重構特性和子帶濾波器的頻率特性，將綜合濾波器的設計問題歸結為帶約束優化問題。其中，以綜合濾波器組的阻帶能量為目標函數，以完全重構條件為約束函數，相應的優化問題是半正定規劃問題，易于求解。兩種方法均可設計得到完全重構的兩通道非下采樣圖濾波器組。同時，根據設計所得的兩通道非下采樣圖濾波器組，本文采用級聯的方式構造出具有多分辨分析特性的多通道非下采樣圖濾波器組。仿真結果表明，本文設計的兩通道非下采樣圖濾波器組具備完全重構特性。在圖信號的去噪仿真實驗中，與現有圖濾波器組相比，本文設計所得的多通道非下采樣圖濾波器組的去噪性能更好。

1 非下采樣圖濾波器組的結構

其中，σ(G)是由圖G的拉普拉斯矩陣所有特征值λ構成的特征空間，P_λ表示特征空間的投影矩陣^[5]，h_i(λ)、g_i(λ)分別是分析子帶濾波器和綜合子帶濾波器的頻譜核。兩通道非下采樣圖濾波器組的輸入輸出關系為：

    當在兩通道非下采樣圖濾波器組的低頻分量上再級聯一個兩通道非下采樣圖濾波器組時，可得三通道非下采樣圖濾波器組。此時，f₀₀、f₀₁、f₁分別表示三通道非下采樣圖濾波器組的子帶系數。進行多通道非下采樣圖濾波器組仿真實驗時，本文以三通道非下采樣圖濾波器組為例。

2 非下采樣圖濾波器組的設計

2.1 非下采樣圖濾波器組設計算法一

    根據樣條圖小波的定義，任意圖的樣條圖分析濾波器組可表示為：

    算法一根據完全重構條件，從頂點域設計綜合濾波器組，但其沒有考慮綜合濾波器組的頻率特性。

2.2 非下采樣圖濾波器組設計算法二

    根據式(7)和式(8)給定的分析濾波器組，算法二從綜合濾波器組的頻譜特性來考慮，采用帶約束優化算法設計綜合子帶濾波器。首先，當n=1時，根據式(9)和式(10)，可得分析子帶濾波器頻譜核為：

式中：

    上述帶優化問題為半正定規劃問題，可利用半正定規劃工具包有效地求解。

2.3 計算復雜度分析

    設計算法一的計算復雜度來自于式（18）矩陣的求偽逆，算法一設計簡單，能直接的求解出綜合濾波器組，但對于大規模圖的計算復雜度較高。而算法二的計算復雜度來自于式（38）約束問題的求解，算法二設計自由度更高，能夠對任意圖進行處理。

3 仿真結果與分析

    這一部分給出一些仿真實例，所有仿真都是在相同的環境下運行。

    例1：首先，采用算法一設計兩通道非下采樣圖濾波器組。其分析濾波器組由式(9)、式(10)構造產生，再利用式(19)、式(20)設計相應的綜合濾波器組，以常用的Minnesota圖信號作為輸入信號^[5]，圖濾波器組的重構信噪比SNR=287.32 dB。接著，采用算法二設計非下采樣圖濾波器組，同樣分析濾波器組由式(9)、式(10)構造產生，并通過求解優化問題(37)來獲得綜合濾波器組，其中參數為：L_h0=2，L_h1=2，L_g0=5，L_g1=5，λ_s0=1.5，λ_s1=0.6，α=1，β=0.1，ε_r=10^-13。所得的濾波器組重構信噪比為SNR=271.62 dB，幅度響應如圖3所示。上述實驗結果表明，兩種算法設計所得的兩通道圖濾波器組都具備完全重構特性。同時，不難發現，算法二設計所得的綜合濾波器組具備頻譜特性。

    例2：根據例1設計所得的兩通道非下采樣圖濾波器組，構造出三通道非下采樣圖濾波器組，然后對Minnesota交通圖采用硬閾值法進行去噪實驗。本文兩通道非下采樣圖濾波器組處理高頻子帶系數f₁，和對比文獻算法一樣，硬閾值取τ=3σ，其中σ為加性噪聲標準差。三通道非下采樣圖濾波器組對不同的高頻子帶系數取不同的硬閾值進行處理，處理高頻子帶系數f₀₁，通過實驗驗證，硬閾值取τ=1.2σ，處理高頻子帶系數f₁，硬閾值取τ=3σ。算法二參數設為：L_h0=2，L_h1=2，L_g0=2，L_g1=2，λ_s0=1.4，λ_s1=0.6，α=1，β=0.1，ε_r=10^-13，所得重構信噪比為SNR=291.40 dB。圖4給出了噪聲標準差σ取不同值時的去噪結果。仿真結果表明，與現有算法設計的圖濾波器組相比，本文算法二構造所得的三通道圖濾波器組具備更好的去噪性能。

    例3：采用與例2相同的兩通道和三通道圖濾波器組，對實測的美國溫度網絡數據進行去噪實驗。首先，采用最近距離的方式構造了溫度圖結構，鄰接矩陣A設為A(i，j)=1/(Dist_i，j)²，如果節點i和節點j不是同一節點且有一條邊相連，否則A(i，j)=0，Dist_i，j表示節點i和節點j間的距離。本文選取第130天的溫度測量信號為例。其中文獻[6]采用的是過采樣的采樣方式進行去噪^[8]。本文算法與現有文獻[4]設計的圖濾波器和文獻[6]算法設計的圖濾波器組對比，圖5給出了加性噪聲標準差σ取不同值時的信噪比對比。當σ=10時，參考文獻算法與文中構造所得的三通道非下采樣圖濾波器組進行去噪的仿真實驗對比，仿真結果如圖6所示。對比實驗仿真結果表明，本文算法構造的圖濾波器組與參考文獻[6]算法相比，本文算法對于實際圖信號有著更好的去噪性能。本文算法二設計所得的三通道圖濾波器組的去噪性能略優于文獻[4]算法。

4 結束語

    本文構造的非下采樣圖濾波器組結構簡單，可以對任意圖的圖信號進行多分辨分析。非下采樣結構極大地簡化了子帶濾波器的設計和實現過程。本文提出了兩種不同的設計方法，用于設計綜合濾波器組。仿真數據和實測數據實驗均表明，與已有圖濾波器組對比，本文算法設計的多通道非下采樣圖濾波器組在圖信號重構和去噪中有著優異的處理性能。后續工作將考慮圖濾波器組在更廣泛的實測傳感器網絡數據處理的應用。

參考文獻

[1] SHUMAN D I，NARANG S K，FROSSARD P，et al.The emerging field of signal processing on graphs：extending high-dimensional data analysis to networks and other irregular domains[J].IEEE Signal Processing Magazine，2013，30(3)：83-98.

[2] NARANG S K，CHAO Y H，ORTEGA A.Graph-wavelet filterbanks for edge-aware image processing[C].IEEE Statistical Signal Processing Workshop(SSP)，Ann Arbor，MI，USA，2012：141-144.

[3] CHAO Y H，ORTEGA A，YEA S.Graph-based lifting transform for intra-predicted video coding[C].IEEE International Conference on Acoustics，Speech and Signal Processing(ICASSP)，Shanghai，China，2016：1140-1144.

[4] ONUKI M，ONO S，YAMAGISHI M，et al.Graph signal denoising via trilateral filter on graph spectral domain[J].IEEE Transactions on Signal and Information Processing Over Networks，2016，2(2)：137-148.

[5] NARANG S K，ORTEGA A.Perfect reconstruction two-channel wavelet filter banks for graph structured data[J].IEEE Transactions on Signal Processing，2012，60(6)：2786-2799.

[6] NARANG S K，ORTEGA A.Compact support biorthogonal wavelet filterbanks for arbitrary undirected graphs[J].IEEE Transactions on Signal Processing，2013，61(19)：4673-4685.

[7] JIANG J Z，ZHOU F，SHUI P L.Optimization design of two-channel biorthogonal graph filter banks[J].Circuits，Systems，and Signal Processing，2016，35(2)：685-692.

[8] TANAKA Y，SAKIYAMA A. M-channel oversampled graph filter banks[J].IEEE Transactions on Signal Processing，2014，62(14)：3578-3590.

[9] 蔣俊正，劉松遼，歐陽繕.一種設計M通道雙正交過采樣圖濾波器組的新算法[J].電子與信息學報，2017，39(12)：2970-2975.

[10] EKAMBARAM V N，FANTI G C，AYAZIFAR B，et al.Spline-like wavelet filterbanks for multiresolution analysis of graph-structured data[J].IEEE Transactions on Signal and Information Processing Over Networks，2015，1(4)：268-278.

[11] NGUYEN H Q，DO M N.Downsampling of signals on graphs via maximum spanning trees[J].IEEE Transactions on Signal Processing，2015，63(1)：182-191.

作者信息:

楊  圣

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