《電子技術(shù)應(yīng)用》
您所在的位置：首頁(yè) > 通信與網(wǎng)絡(luò) > 設(shè)計(jì)應(yīng)用 > 非下采樣圖濾波器組的設(shè)計(jì)方法
非下采樣圖濾波器組的設(shè)計(jì)方法
2019年電子技術(shù)應(yīng)用第2期
楊 圣
桂林電子科技大學(xué) 信息與通信學(xué)院，廣西 桂林541004
摘要： 針對(duì)圖濾波器組中難以準(zhǔn)確定義一般圖信號(hào)下采樣運(yùn)算的問(wèn)題，提出了非下采樣圖濾波器組的設(shè)計(jì)方法。首先，采用樣條濾波器作為分析濾波器組。然后，通過(guò)兩種不同的方法設(shè)計(jì)綜合濾波器組，其中，算法一利用頂點(diǎn)域的完全重構(gòu)條件，構(gòu)造出綜合濾波器組；算法二從子帶濾波器的頻譜特性考慮，采用帶約束優(yōu)化算法設(shè)計(jì)綜合濾波器組。兩種方法可設(shè)計(jì)得到完全重構(gòu)的兩通道非下采樣圖濾波器組。最后，在兩通道非下采樣圖濾波器組的基礎(chǔ)上，采用級(jí)聯(lián)的方式構(gòu)造出具有多分辨分析特性的多通道非下采樣圖濾波器組。仿真結(jié)果表明，所提出的非下采樣圖濾波器組具備完全重構(gòu)特性。并且，與已有的圖濾波器組相比，設(shè)計(jì)所得的多通道非下采樣圖濾波器組具有更好的去噪性能。
中圖分類號(hào)： TN911.7
文獻(xiàn)標(biāo)識(shí)碼： A
DOI：10.16157/j.issn.0258-7998.182469
中文引用格式： 楊圣. 非下采樣圖濾波器組的設(shè)計(jì)方法[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ì)算機(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)而言，基于圖染色的采樣模式并不精確，基于奇異值分解的采樣模式不適用于連通圖的處理，而基于最大生成樹的采樣模式對(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)

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)在兩通道非下采樣圖濾波器組的低頻分量上再級(jí)聯(lián)一個(gè)兩通道非下采樣圖濾波器組時(shí)，可得三通道非下采樣圖濾波器組。此時(shí)，f00、f01、f1分別表示三通道非下采樣圖濾波器組的子帶系數(shù)。進(jìn)行多通道非下采樣圖濾波器組仿真實(shí)驗(yàn)時(shí)，本文以三通道非下采樣圖濾波器組為例。

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

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

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

tx4-gs7-8.gif

tx4-gs9-20.gif

    算法一根據(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)，可得分析子帶濾波器頻譜核為：

tx4-gs21-27.gif

式中：

tx4-gs28-40.gif

    上述帶優(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ù)為：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所示。上述實(shí)驗(yàn)結(jié)果表明，兩種算法設(shè)計(jì)所得的兩通道圖濾波器組都具備完全重構(gòu)特性。同時(shí)，不難發(fā)現(xiàn)，算法二設(shè)計(jì)所得的綜合濾波器組具備頻譜特性。

tx4-t3.gif

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

tx4-t4.gif

    例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/(Disti，j)2，如果節(jié)點(diǎn)i和節(jié)點(diǎn)j不是同一節(jié)點(diǎn)且有一條邊相連，否則A(i，j)=0，Disti，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]算法。

tx4-t5.gif

tx4-t6.gif

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)

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