《電子技術(shù)應(yīng)用》
您所在的位置：首頁 > 通信與網(wǎng)絡(luò) > 設(shè)計應(yīng)用 > 非下采樣圖濾波器組的設(shè)計方法
非下采樣圖濾波器組的設(shè)計方法
2019年電子技術(shù)應(yīng)用第2期
楊 圣
桂林電子科技大學(xué) 信息與通信學(xué)院，廣西 桂林541004
摘要： 針對圖濾波器組中難以準(zhǔn)確定義一般圖信號下采樣運(yùn)算的問題，提出了非下采樣圖濾波器組的設(shè)計方法。首先，采用樣條濾波器作為分析濾波器組。然后，通過兩種不同的方法設(shè)計綜合濾波器組，其中，算法一利用頂點域的完全重構(gòu)條件，構(gòu)造出綜合濾波器組；算法二從子帶濾波器的頻譜特性考慮，采用帶約束優(yōu)化算法設(shè)計綜合濾波器組。兩種方法可設(shè)計得到完全重構(gòu)的兩通道非下采樣圖濾波器組。最后，在兩通道非下采樣圖濾波器組的基礎(chǔ)上，采用級聯(lián)的方式構(gòu)造出具有多分辨分析特性的多通道非下采樣圖濾波器組。仿真結(jié)果表明，所提出的非下采樣圖濾波器組具備完全重構(gòu)特性。并且，與已有的圖濾波器組相比，設(shè)計所得的多通道非下采樣圖濾波器組具有更好的去噪性能。
中圖分類號： TN911.7
文獻(xiàn)標(biāo)識碼： A
DOI：10.16157/j.issn.0258-7998.182469
中文引用格式： 楊圣. 非下采樣圖濾波器組的設(shè)計方法[J].電子技術(shù)應(yīng)用，2019，45(2)：71-74，79.
英文引用格式： Yang Sheng. Design method of nonsubsampled graph filter banks[J]. Application of Electronic Technique，2019，45(2)：71-74，79.
Design method of nonsubsampled graph filter banks
Yang Sheng
School of Information and Communication，Guilin University of Electronic Technology，Guilin 541004，China
Abstract： In order to overcome the problem that it is difficult to accurately define the downsampling operation for a generalized graph signal in graph filter banks, this paper focuses on the design algorithm of nonsubsampled graph filter banks. Firstly, the spline filters are taken as the analysis filter banks. Then, two different methods are proposed to construct the synthesis filter banks. In the first algorithm, the synthesis filter banks can be constructed with the perfect reconstruction conditions in vertex domain. By taking into account the frequency of the subband filters in the second algorithm, the synthesis filter banks are designed by solving a constrained optimization problem involving the spectrum characteristics of the filters. The design methods can lead to two channel nonsubsampled graph filter banks with perfect reconstruction. Finally, taking the two channel nonsubsampled graph filter banks as a basic building block, multichannel nonsubsampled graph filter banks are constructed，which can realize multiresolution analysis of graph signal through cascading. Simulation results show that the designed nonsubsampled graph filter banks have perfect reconstruction property. Furthermore, the designed multichannel nonsubsampled graph filter banks have better denoising performance than the existing graph filter banks.
Key words : nonsubsampled graph filter bank；perfect reconstruction；multiresolution analysis；graph signal denoising

0 引言

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

    本文首先考慮兩通道非下采樣圖濾波器組的設(shè)計問題。采用樣條圖小波濾波器作為非下采樣圖濾波器組的分析濾波器組，然后通過兩種不同的方法設(shè)計綜合濾波器組。其中，算法一利用定點域的完全重構(gòu)條件，通過正則化目標(biāo)函數(shù)，直接求解出綜合濾波器，但算法一沒有考慮綜合濾波器的頻譜特性。為此，算法二采用優(yōu)化手段綜合考慮濾波器組的重構(gòu)特性和子帶濾波器的頻率特性，將綜合濾波器的設(shè)計問題歸結(jié)為帶約束優(yōu)化問題。其中，以綜合濾波器組的阻帶能量為目標(biāo)函數(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)

tx4-gs1-2.gif

tx4-t1.gif

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

tx4-gs3-6.gif

tx4-t2.gif

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

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

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

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

tx4-gs7-8.gif

tx4-gs9-20.gif

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

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

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

tx4-gs21-27.gif

式中：

tx4-gs28-40.gif

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

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

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

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

    這一部分給出一些仿真實例，所有仿真都是在相同的環(huán)境下運(yù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ù)為：Lh0=2，Lh1=2，Lg0=5，Lg1=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è)計所得的綜合濾波器組具備頻譜特性。

tx4-t3.gif

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

tx4-t4.gif

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

tx4-t5.gif

tx4-t6.gif

4 結(jié)束語

    本文構(gòu)造的非下采樣圖濾波器組結(jié)構(gòu)簡單，可以對任意圖的圖信號進(jìn)行多分辨分析。非下采樣結(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)用。

參考文獻(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] 蔣俊正，劉松遼，歐陽繕.一種設(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)

此內(nèi)容為AET網(wǎng)站原創(chuàng)，未經(jīng)授權(quán)禁止轉(zhuǎn)載。