0 引言

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

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

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

1 非下采樣圖濾波器組的結(jié)構(gòu)

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

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

2 非下采樣圖濾波器組的設(shè)計

2.1 非下采樣圖濾波器組設(shè)計算法一

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

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

2.2 非下采樣圖濾波器組設(shè)計算法二

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

式中：

    上述帶優(yōu)化問題為半正定規(guī)劃問題，可利用半正定規(guī)劃工具包有效地求解。

2.3 計算復(fù)雜度分析

    設(shè)計算法一的計算復(fù)雜度來自于式（18）矩陣的求偽逆，算法一設(shè)計簡單，能直接的求解出綜合濾波器組，但對于大規(guī)模圖的計算復(fù)雜度較高。而算法二的計算復(fù)雜度來自于式（38）約束問題的求解，算法二設(shè)計自由度更高，能夠?qū)θ我鈭D進行處理。

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

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

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

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

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

4 結(jié)束語

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

參考文獻

[1] SHUMAN D I，NARANG S K，F(xiàn)ROSSARD 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] 蔣俊正，劉松遼，歐陽繕.一種設(shè)計M通道雙正交過采樣圖濾波器組的新算法[J].電子與信息學(xué)報，2017，39(12)：2970-2975.

[10] EKAMBARAM V N，F(xiàn)ANTI 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.

作者信息:

楊  圣

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