0 引言

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

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

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

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

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

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

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

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

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

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

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

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

式中：

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

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

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

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

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

    例1：首先，采用算法一設(shè)計(jì)兩通道非下采樣圖濾波器組。其分析濾波器組由式(9)、式(10)構(gòu)造產(chǎn)生，再利用式(19)、式(20)設(shè)計(jì)相應(yīng)的綜合濾波器組，以常用的Minnesota圖信號(hào)作為輸入信號(hào)^[5]，圖濾波器組的重構(gòu)信噪比SNR=287.32 dB。接著，采用算法二設(shè)計(jì)非下采樣圖濾波器組，同樣分析濾波器組由式(9)、式(10)構(gòu)造產(chǎn)生，并通過(guò)求解優(yōu)化問(wèn)題(37)來(lái)獲得綜合濾波器組，其中參數(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所示。上述實(shí)驗(yàn)結(jié)果表明，兩種算法設(shè)計(jì)所得的兩通道圖濾波器組都具備完全重構(gòu)特性。同時(shí)，不難發(fā)現(xiàn)，算法二設(shè)計(jì)所得的綜合濾波器組具備頻譜特性。

    例2：根據(jù)例1設(shè)計(jì)所得的兩通道非下采樣圖濾波器組，構(gòu)造出三通道非下采樣圖濾波器組，然后對(duì)Minnesota交通圖采用硬閾值法進(jìn)行去噪實(shí)驗(yàn)。本文兩通道非下采樣圖濾波器組處理高頻子帶系數(shù)f₁，和對(duì)比文獻(xiàn)算法一樣，硬閾值取τ=3σ，其中σ為加性噪聲標(biāo)準(zhǔn)差。三通道非下采樣圖濾波器組對(duì)不同的高頻子帶系數(shù)取不同的硬閾值進(jìn)行處理，處理高頻子帶系數(shù)f₀₁，通過(guò)實(shí)驗(yàn)驗(yàn)證，硬閾值取τ=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給出了噪聲標(biāo)準(zhǔn)差σ取不同值時(shí)的去噪結(jié)果。仿真結(jié)果表明，與現(xiàn)有算法設(shè)計(jì)的圖濾波器組相比，本文算法二構(gòu)造所得的三通道圖濾波器組具備更好的去噪性能。

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

4 結(jié)束語(yǔ)

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

參考文獻(xiàn)

[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] 蔣俊正，劉松遼，歐陽(yáng)繕.一種設(shè)計(jì)M通道雙正交過(guò)采樣圖濾波器組的新算法[J].電子與信息學(xué)報(bào)，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)