文獻(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.
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],hi(λ)、gi(λ)分別是分析子帶濾波器和綜合子帶濾波器的頻譜核。兩通道非下采樣圖濾波器組的輸入輸出關(guān)系為:
當(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ù)樣條圖小波的定義,任意圖的樣條圖分析濾波器組可表示為:
算法一根據(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ù)為: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ì)所得的綜合濾波器組具備頻譜特性。
例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)造所得的三通道圖濾波器組具備更好的去噪性能。
例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ì)所得的三通道圖濾波器組的去噪性能略?xún)?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)