0 引言

    在网络、计算机视觉和高维云数据等领域中，图提供了一个灵活的模型来表示数据。图上的数据为附加到图上每个网络节点的信息值，可以把图上的数据量化为样本的有限集合，即图信号^[1]。随着图信号处理的发展，越来越多的学者从事图信号处理领域的研究工作。图信号处理将传统信号处理中的诸多概念和理论拓展至图结构上，引申出了图傅里叶变换等重要概念。同时，许多学者构造了图小波和图滤波器组^[2-10]，其具备多尺度变换特性，适合于处理大规模图的图信号。近年来，图小波和图滤波器组已被广泛应用于图信号的多分辨分析^[2]、压缩^[3]和去噪^[4]。

    NARANG S K和ORTEGA A最早提出两通道临界采样图小波滤波器组的设计方法^[5]。在二分图中，针对上下采样运算引起的频谱混叠现象，设计出正交镜像图小波滤波器组，该算法设计是针对于二分图或可以分解为二分图的图信号。此后，NARANG S K和ORTEGA A构造出两通道双正交图小波滤波器组^[6]，其具备频域紧支撑，但此双正交图小波的设计方法未考虑滤波器的频谱选择性。文献[7]提出两通道双正交图滤波器组的优化设计方法，此设计算法充分考虑了频谱选择性，但是以更高的重构误差为代价。SAKIYAMA A和TANAKA Y提出通道过采样图滤波器组的设计算法^[8]，过采样对于图信号的处理有更大的设计自由。文献[9]综合考虑M通道过采样图滤波器组的性能，采用优化算法设计出整体性能良好的M通道过采样图滤波器组，且具备频谱选择性，但其算法设计的图滤波器组的去噪性能较差。文献[10]针对循环图提出了样条图小波滤波器组，并在循环图的基础上扩展到任意图的样条图小波滤波器组。上述图小波和图滤波器组的结构中均含有图信号的下采样运算，然而对于一般图结构的图信号而言，基于图染色的采样模式并不精确，基于奇异值分解的采样模式不适用于连通图的处理，而基于最大生成树的采样模式对复杂图进行采样运算时也存在不精确的问题^[11]。目前，在图滤波器组中，难以准确定义一般图信号下采样运算。而非下采样图滤波器组无需采样运算，这样可以避免由采样所带来的诸多问题。并且，目前非下采样图滤波器组的设计方法较少，有待深入研究。

    本文首先考虑两通道非下采样图滤波器组的设计问题。采用样条图小波滤波器作为非下采样图滤波器组的分析滤波器组，然后通过两种不同的方法设计综合滤波器组。其中，算法一利用定点域的完全重构条件，通过正则化目标函数，直接求解出综合滤波器，但算法一没有考虑综合滤波器的频谱特性。为此，算法二采用优化手段综合考虑滤波器组的重构特性和子带滤波器的频率特性，将综合滤波器的设计问题归结为带约束优化问题。其中，以综合滤波器组的阻带能量为目标函数，以完全重构条件为约束函数，相应的优化问题是半正定规划问题，易于求解。两种方法均可设计得到完全重构的两通道非下采样图滤波器组。同时，根据设计所得的两通道非下采样图滤波器组，本文采用级联的方式构造出具有多分辨分析特性的多通道非下采样图滤波器组。仿真结果表明，本文设计的两通道非下采样图滤波器组具备完全重构特性。在图信号的去噪仿真实验中，与现有图滤波器组相比，本文设计所得的多通道非下采样图滤波器组的去噪性能更好。

1 非下采样图滤波器组的结构

其中，σ(G)是由图G的拉普拉斯矩阵所有特征值λ构成的特征空间，P_λ表示特征空间的投影矩阵^[5]，h_i(λ)、g_i(λ)分别是分析子带滤波器和综合子带滤波器的频谱核。两通道非下采样图滤波器组的输入输出关系为：

    当在两通道非下采样图滤波器组的低频分量上再级联一个两通道非下采样图滤波器组时，可得三通道非下采样图滤波器组。此时，f₀₀、f₀₁、f₁分别表示三通道非下采样图滤波器组的子带系数。进行多通道非下采样图滤波器组仿真实验时，本文以三通道非下采样图滤波器组为例。

2 非下采样图滤波器组的设计

2.1 非下采样图滤波器组设计算法一

    根据样条图小波的定义，任意图的样条图分析滤波器组可表示为：

    算法一根据完全重构条件，从顶点域设计综合滤波器组，但其没有考虑综合滤波器组的频率特性。

2.2 非下采样图滤波器组设计算法二

    根据式(7)和式(8)给定的分析滤波器组，算法二从综合滤波器组的频谱特性来考虑，采用带约束优化算法设计综合子带滤波器。首先，当n=1时，根据式(9)和式(10)，可得分析子带滤波器频谱核为：

式中：

    上述带优化问题为半正定规划问题，可利用半正定规划工具包有效地求解。

2.3 计算复杂度分析

    设计算法一的计算复杂度来自于式（18）矩阵的求伪逆，算法一设计简单，能直接的求解出综合滤波器组，但对于大规模图的计算复杂度较高。而算法二的计算复杂度来自于式（38）约束问题的求解，算法二设计自由度更高，能够对任意图进行处理。

3 仿真结果与分析

    这一部分给出一些仿真实例，所有仿真都是在相同的环境下运行。

    例1：首先，采用算法一设计两通道非下采样图滤波器组。其分析滤波器组由式(9)、式(10)构造产生，再利用式(19)、式(20)设计相应的综合滤波器组，以常用的Minnesota图信号作为输入信号^[5]，图滤波器组的重构信噪比SNR=287.32 dB。接着，采用算法二设计非下采样图滤波器组，同样分析滤波器组由式(9)、式(10)构造产生，并通过求解优化问题(37)来获得综合滤波器组，其中参数为：L_h0=2，L_h1=2，L_g0=5，L_g1=5，λ_s0=1.5，λ_s1=0.6，α=1，β=0.1，ε_r=10^-13。所得的滤波器组重构信噪比为SNR=271.62 dB，幅度响应如图3所示。上述实验结果表明，两种算法设计所得的两通道图滤波器组都具备完全重构特性。同时，不难发现，算法二设计所得的综合滤波器组具备频谱特性。

    例2：根据例1设计所得的两通道非下采样图滤波器组，构造出三通道非下采样图滤波器组，然后对Minnesota交通图采用硬阈值法进行去噪实验。本文两通道非下采样图滤波器组处理高频子带系数f₁，和对比文献算法一样，硬阈值取τ=3σ，其中σ为加性噪声标准差。三通道非下采样图滤波器组对不同的高频子带系数取不同的硬阈值进行处理，处理高频子带系数f₀₁，通过实验验证，硬阈值取τ=1.2σ，处理高频子带系数f₁，硬阈值取τ=3σ。算法二参数设为：L_h0=2，L_h1=2，L_g0=2，L_g1=2，λ_s0=1.4，λ_s1=0.6，α=1，β=0.1，ε_r=10^-13，所得重构信噪比为SNR=291.40 dB。图4给出了噪声标准差σ取不同值时的去噪结果。仿真结果表明，与现有算法设计的图滤波器组相比，本文算法二构造所得的三通道图滤波器组具备更好的去噪性能。

    例3：采用与例2相同的两通道和三通道图滤波器组，对实测的美国温度网络数据进行去噪实验。首先，采用最近距离的方式构造了温度图结构，邻接矩阵A设为A(i，j)=1/(Dist_i，j)²，如果节点i和节点j不是同一节点且有一条边相连，否则A(i，j)=0，Dist_i，j表示节点i和节点j间的距离。本文选取第130天的温度测量信号为例。其中文献[6]采用的是过采样的采样方式进行去噪^[8]。本文算法与现有文献[4]设计的图滤波器和文献[6]算法设计的图滤波器组对比，图5给出了加性噪声标准差σ取不同值时的信噪比对比。当σ=10时，参考文献算法与文中构造所得的三通道非下采样图滤波器组进行去噪的仿真实验对比，仿真结果如图6所示。对比实验仿真结果表明，本文算法构造的图滤波器组与参考文献[6]算法相比，本文算法对于实际图信号有着更好的去噪性能。本文算法二设计所得的三通道图滤波器组的去噪性能略优于文献[4]算法。

4 结束语

    本文构造的非下采样图滤波器组结构简单，可以对任意图的图信号进行多分辨分析。非下采样结构极大地简化了子带滤波器的设计和实现过程。本文提出了两种不同的设计方法，用于设计综合滤波器组。仿真数据和实测数据实验均表明，与已有图滤波器组对比，本文算法设计的多通道非下采样图滤波器组在图信号重构和去噪中有着优异的处理性能。后续工作将考虑图滤波器组在更广泛的实测传感器网络数据处理的应用。

参考文献

[1] SHUMAN D I，NARANG S K，FROSSARD 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] 蒋俊正，刘松辽，欧阳缮.一种设计M通道双正交过采样图滤波器组的新算法[J].电子与信息学报，2017，39(12)：2970-2975.

[10] EKAMBARAM V N，FANTI 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.

作者信息:

杨  圣

(桂林电子科技大学 信息与通信学院，广西 桂林541004)