第24卷 第4期 电子测量与仪器学报 Vol. 24 No. 4 · 314 ·
JOURNAL OF ELECTRONIC MEASUREMENT AND INSTRUMENT
2010年4月
本文于2010年1月收到。
*基金项目: 国家自然科学基金(编号: 60827001)资助项目。
DOI: 10.3724/SP.J.1187.2010.00314
基于隐马尔科夫树模型的小波域压缩
采样信号重构方法*
赵贻玖 王厚军 戴志坚
(电子科技大学自动化工程学院, 成都611731)
摘 要: 压缩传感理论利用信号的稀疏性, 对其非自适应线性投影进行压缩采样, 通过最优化问题准确重构原始信号。传统重构算法仅利用了信号的稀疏性, 而未对转换后的信号结构进行分析。提出了一种基于4状态的隐马尔科夫树模型的小波域压缩采样信号的重构方法, 相对2状态的隐马尔科夫树模型, 该模型能够获取相邻尺度小波系数的更多相关特性, 通过仿真结果表明, 该算法具有更高的重构精度。
关键词: 压缩采样；非自适应线性投影；小波变换；隐马尔科夫树模型 中图分类号: TN911.7 文献标识码: A 国家标准学科分类代码: 510.40
Compressive sampling signal reconstruction in wavelet-domain
based on hidden Markov tree model
Zhao Yijiu Wang Houjun Dai Zhijian
(School of Automation Engineering, University of Electronic Science and Technology of China, Chengdu 611731, China)
Abstract: Compressed sensing theory enables the reconstruction of sparse signal from a small number of non-adaptives linear projections. Conventional reconstruction algorithm involves linear programming or greedy algo-rithms, these reconstruction techniques are generic and assume no particular structure in the signal aside from sparsity. The compressive sampling signal reconstruction in wavelet domain is inspired based on tow-state wavelet hidden Markov tree model. In this paper, we propose a four-state wavelet Hidden Markov Tree model, it can capture more in-terscales dependencies of wavelet coefficients between two neighboring scales, the simulation shows that it reconstruc-tion precision is improved.
Keywords: compressive sampling; non-adaptives linear projection; wavelet transform; hidden markov tree model
1 引 言
压缩传感理论[1-3]作为一种全新的信息获取理论,
突破了香农采样定理的限制。该理论指出: 以实际信号的“信息率[4]”相当的采样速率获取稀疏信号的非自适应线性投影, 通过最优化问题仍能准确重构原始信号。压缩采样信号重构算法可以分为两类: 以l 1范数极小化为代表的凸优化算法和以正交匹配追踪为代表的贪婪算法。
不管是凸优化算法还是贪婪算法, 均以信号的
稀疏性为基础对信号进行重构, 未对信号的结构进行分析。然而, 信号的某些先验知识能够显著提高重构算法的性能, 如: 分段光滑信号[5]不仅在小波域有稀疏表示, 而且其小波系数集中在某一子树[6]。在该统计特性基础上, 文献[7]提出了基于隐马尔科夫树模型的小波域压缩采样信号重构算法, 其基本思想是利用分段光滑信号小波变换系数的树结构相关性, 基于隐马尔科夫树模型的迭代加权l 1范数极小化的算法, 该算法采用2状态隐马尔科夫树, 能够有效地获取子节点与其父节点的相关性, 但是对于子节点
第4期 基于隐马尔科夫树模型的小波域压缩采样信号重构方法 · 315 ·
与父节点相邻节点的相关性不予考虑。
本文在文献[7]的算法基础上引入4状态隐马尔科夫树模型[8], 该模型能够更多地获取相邻尺度节点间的相关性。首先介绍了压缩传感的基本理论以及压缩采样信号的重构算法, 根据小波域压缩传感的特点, 介绍了基于4状态的隐马尔科夫树模型的迭代加权l 1范数极小化的重构算法, 最后通过仿真对该算法进行了评估。
2 压缩传感
压缩传感理论对稀疏信号进行压缩采样, 并能通过重构算法精确恢复原始信号。本节首先介绍了压缩传感的基本原理, 然后引出了迭代加权1l 范数极小化重构算法。 2.1 基本理论
稀疏性和非相关性是压缩传感理论的两个重要先验条件[9], 稀疏性是指信号在某种转换基Ψ的变换下具有稀疏或者近似稀疏的表达式, 变换基可以根据信号本身的特性选择(快速傅里叶变换基、离散小波变换基[10-11]等), 如信号x 在基Ψ下的变换系数为,i i x =Ψα, 如果α中非零元素的个数为K (K N )时, 则称信号x 为K 稀疏的; 与稀疏性相反, 非相关性是指采样波形在Ψ中有稠密的表达式, 即: 测量矩阵Φ与转换基Ψ不相关。实际采样过程中, 大多数信号都具有稀疏性, 可以通过压缩采样序列重构原始信号。如图1所示, 对于信号x ∈R N , 可以找到它的L 个线性测量
y α=ΨΦ, (1) 式中: x =Ψα, y ∈R L , 压缩测量矩阵Φ∈R L ×
N ()L N , 通过这L (L =cK , c >1)个线性测量值y 重构原始 信号x 。
图1 压缩采样模型
Fig. 1 Scheme of compressive sampling
2.2 信号重构
重构原始信号需要求解式(1),由于y 的维数远远
小于x 的维数, 式(1)是一个欠定方程, 有无穷多个解。Candés 证明了利用信号的K 稀疏性, 原始信号x 可由线性测量值y 求解l 0范数最优化问题精确重构。
0?arg min ..s t y α
==Ψ&&ααΦα, (2)
式中: ||·||0为向量的l 0范数, 表示向量α中非零元素的个数。然而最小l 0范数问题本质上是NP-hard (nondeterministic polynomial-time hard)问题, 即: 多项式时间内难以求解, 需要将问题进行转化。采用l 1范数[12-13]代替l 0范数, 得到l 1范数最优化问题, 1?arg min ..s t y α
==Ψ&&ααΦα, (3)
文献[14]证明了问题(2)与(3)等价, 问题(3)是凸优化问题, 可以将其转化为线性规划问题求解[4]。
然而, 通过l 1范数最优化问题需要比l 0范数最优化问题更多的线性测量值重构原始信号, 即: 使用问题(3)进行信号重构时的c 取值更大。
为了解决这一问题, 文献[15]提出了迭代加权1
l 范数极小化算法(IRWL1), 该算法首先求解问题
(3)(结果为0?α
), 通过连续迭代求解
1?arg min ..i i s t y α
==Ψ&&ααΦαW , (4)
式中: W i 为N ×N 对角矩阵, 对角元素为
,1
1
?||i n n i n ε
?=
+W α, (5)
式中: i 为迭代次数, ε为取值大于0的规划常数, 当求解结果?i α
满足重构误差要求或i 达到最大迭代次数时停止迭代。
3 小波域稀疏信号统计特性
小波变换广泛应用于信号处理中, 小波变换不仅具有频域分辨率, 而且还能反应信号的时域局部特性。小波变换是通过移位和伸缩, 采用带通小波函数ψJ ,K (t )和低通尺度函数φJ ,K (t )对信号进行分解。小波函数ψJ ,K (t )和低通尺度函数φJ ,K (t )分别为:
/2,()2(2)J J J K t t K ψψ??=?
/2,()2(2)J J J K t t K φφ??=?, (,J K ∈Z ) (6)
则信号x (t )可以分解为:
0,,,()()()J K J K J K J K K
J K
x t u t w t φψ=?∞=+
∑∑∑ (7)
式中: u K 为尺度系数, w J ,K 为小波系数。
在基于小波的信号处理中, 是通过信号小波变
·316 ·电子测量与仪器学报第24卷
换的尺度系数和小波系数对信号进行处理。小波变换具有时间和频率上的局部特性、稀疏性和多分辨率特性(称为小波变换的第一性[7])。由于小波变换的多分辨率特征, 信号可以被分解到多个尺度上进行分析。随着分析尺度的增加, 小波系数的数量以2的指数次幂减少, 并且粗尺度上的小波系数仅与其分解的下一尺度上的小波系数相关, 因此可以采用二进制树对小波系数进行描述, 如图2所示。
图2 一维信号的小波系数对应的二进制树 Fig. 2 Binary tree of wavelet coefficients of 1-D signal 统计研究表明, 大多数信号小波变换后的同一尺度小波系数呈现尖峰、长拖尾的非Gaussian分布特征。这是由于小波系数间所存在的相关性所致, 小波变换的第二性[7]很好地解释了存在这一现象的原因, 1)聚类性: 如果某小波系数值为大值或小值, 那么它附近的小波系数也为大值或小值; 2)持续性: 小波系数值在不同尺度间传播。聚类性表明了同一尺度间存在相关性, 而持续性则表明不同尺度间的小波系数存在相关性。
4隐马尔科夫树模型
由第三节对小波系数的统计特性分析可知, 对信号小波变换系数的分析不能采用简单的Gaussian 分布。文献[7]提出了基于隐马尔科夫树模型的混合Gaussian概率分布模型, M.F.Duarte将该模型引入了小波域的压缩采样信号重构算法中, 显著提高了信号的重构精度。该模型是基于2状态的隐马尔科夫树模型, 为了获取相邻尺度小波系数间的更多相关性, 提高信号重构的精度, 本文对M.F.Duarte的重构算法进行改进, 引入4状态隐马尔科夫树模型(HMT-2[8])。如图3(a)所示, 每个黑点表示小波系数w, 每个与其相连的白点表示w的混合状态变量s。
在HMT-2模型中, 每个子节点的小波系数w不仅与父节点的状态有关, 而且和父节点的相邻节点也存在相关性。图3(b)是HMT-2模型的简化表示方式, 该模型除了每个节点对应2个小波系数以外, 其结构与2状态隐马尔科夫树模型的结构基本相同。
(a) HMT-2模型
(a) HMT-2 model
(b)
(b) HMT-2简化描述模型
(b) A simplified interpretation of the HMT-2 model
图3 4状态隐马尔科夫树模型
Fig. 3 4 status Markov tree model
HMT-2模型采用混合Gaussian密度分布模型对小波系数的分布进行估计, 隐含状态变量的值决定了小波系数的大小, 小波系数的持续性通过马尔科夫树中父节点及相邻节点和子节点的状态的相关性获得。为了方便分析, 做如下定义: W表示一个小波系数的随机变量; S为W对应的具有M(HMT-2模型中, M=4)个状态的随机变量, 其概率聚集函数为ps(m), m=0,…,3, m与小波系数值的大小有关, 取值越小, 对应小波系数越小。对于给定状态S=m, W的概率密度函数为均值为μm方差为σm的Gaussian分布, 一般情况下, 具有M个状态Gaussian混合模型的随
第4期 基于隐马尔科夫树模型的小波域压缩采样信号重构方法 · 317 ·
机变量W 的概率密度函数由2部分组成: 状态变量S 的概率聚集函数ps (m )和Gaussian 条件概率密度函数f W |S (w |S =m )。 3
|0
()()(|)W W S
m f w ps m f w S m ==
?=∑ (8) 其中
2
|(|)W S f w S m ==
(9)
给定一组分析尺度为J 的小波系数, 假定W j ,i 和
S j ,i 分别表示小波系数w j ,i 的随机变量和状态变量, 其中i =0,…,N j , j =0,…,J , N j 表示在分析尺度为j 的小波系数个数。在HMT-2模型中, 对于给定状态S j ,i =m , W j ,i 与其他所有随机变量条件独立。HMT-2模型由参
数,2,,,1{(),,,}m n J j m j m j j ps m εμσ+Θ=描述, 其中:
1) ()J ps m : 根节点J S 的概率聚集函数; 2)
,,,1
1,/2(|)m n
j i j j j i p S m S n ε++??
??===: 尺度j 与尺度(j +1)间的转移概率;
3) ,j m μ与2,j m σ: 给定状态S j ,i =m 下, W j ,i 的均值和方差。
参数Θ可以通过迭代期望最大(EM)算法进行估计, 文献[8]给出了HMT-2模型的训练算法。
5 基于HMT-2的IRWL1重构算法
由2.2节可知, IRWL1算法在保证计算复杂度的情况下具有灵活的信号抑制功能。以IRWL1算法为基础, 本文提出了一种基于HMT-2模型的改进加权规则的重构算法, 以状态概率p (S =m |w ,Θ)代替小波系数, 重新构造加权系数如下:
,11
?((|,))i n n i r
n W p S m αε?==Θ+, (10) 式中: α为小波系数, ε为规划常数, r 为惩罚力度参数。
对于每个小波系数, 通过HMT-2模型获取其状态的概率, 在下一次迭代过程中, 根据状态的取值和当前状态下的概率选取加权系数。加权的目的是为了对那些具有大幅度、小概率的小波系数进行抑制, 这些系数是产生重构误差的主要因素。
基于HMT-2的IRWL1重构算法基本步骤如下: 1) 对模型HMT-2进行训练, 即采用EM 算法对参数Θ进行估计;
2) 通过标准IRWL1算法(4)获得迭代初始值
?α
; 3) 以维特比算法计算随机状态变量S 的概率,
根据前一次迭代加权计算结果1?i α
?, 更新加权系数W i ;
4) 在IRWL1算法(4)式中, 加权系数取值i W 对
信号进行重构, 重构结果为?i α
; 5）重复执行步骤3和4, 达到迭代次数或满足重构误差要求停止计算。
6 仿 真
以均方差(MSE)为指标, 通过仿真对基于HMT-2的IRWL1重构算法进行评估。设置仿真输入为分段光滑信号, 信号长度为N 为1 024, 幅度峰峰值为10 V , 采用db6小波对其进行稀疏化。在基于HMT-2的IRWL1重构算法中, 设置ε取值为10?10, r 取值分别为0.01和0.2, 迭代次数为30次, 测量值序列长度L 为256, 仿真波形如图4所示。
(a) 原始信号
(b) IRWL1重构信号
(c) r =0.01时, 基于HMT-2的IRWL1重构信
号
(d) r =0.2时, 基于HMT-2的IRWL1重构信号
图4 重构波形仿真
Fig. 4 Simulation of reconstruction waveform
·318 ·电子测量与仪器学报第24卷
以IRWL1算法重构波形的均方差为1.37, 而基于HMT-2的IRWL1算法重构波形的均方差在r=0.2时为0.06, 当r减小到0.01时, 相同迭代次数下的均方误差为0.47。显然, IRWL1算法中引入HMT-2模型后重构精度得到显著提高, 而惩罚力度常数r的取值影响到该算法下重构信号均方误差的收敛速度。
7结论
提出了一种基于4状态隐马尔科夫树模型(HMT-2)的迭代加权l1范数极小化(IRWL1)压缩采样信号重构算法。介绍了小波域4状态隐马尔科夫树模型的基本结构, 通过维特比算法获取各个小波系数状态变量的概率, 以小波系数状态变量的概率构造加权系数, 从而有效地抑制了具有大幅度、小概率的小波系数对信号重构精度的影响。仿真说明, 基于小波域4状态隐马尔科夫树模型的迭代加权1l范数极小化算法具有更高的重构精度。
参考文献:
[1] CANDES E, WAKIN M. An introduction to compressive
sampling [J]. IEEE Sig. Proc. Mag, Mar 2008, 25( 2):
21-30.
[2] CANDES E, ROMBERG J, TAO T. Robust uncertainty
principles:Exact signal reconstruction from highly
incomplete frequency information [J]. IEEE Trans.
Inform. Theory, 2006, 52: 489-509.
[3] 李树涛, 魏丹. 压缩传感综述 [J]. 自动化学报, 2009,
35: 1369-1377.
LI SH T, WEI D. A survey on compressive sening [J].
Acta Automation Sinica, 2009, (35): 1369-1377.
[4] BLU T, DRAGOTTI P L, VETERLI M. Sparse sam-
pling of signal innovations [J]. IEEE Signal Processing
Magazine, Mar 2008, 25(2): 31-40.
[5] MALLAT S. A wavelet tour of signal processing [M].
San Diego:Academic Press, 1999:431-454.
[6] CROUSE M S, NOWAK R D, BARANIUK R G.
Wavelet-based statistical signal processing using Hidden
Markov Models [J]. IEEE Trans.Signal Processing, Apr.
1998, 46(4): 886-902.
[7] DUARTE M F, WAKIN M B, BARANIUK R G.
Wavelet-domain compressive signal reconstruction using
a hidden markov tree model [C]. Las Vegas:Proceedings
of Intl. Conf. Acoustics, Speech and Sig. Proc.
(ICASSP’08), 2008: 5137-5140.
[8] FAN G L , XIA X G. Improved hidden Markov models in
the wavelet-domain [J]. IEEE Trans. Signal proc essing,
2001, 49: 115-120.
[9] CANDES E, ROMBERG J. Sparsity and incoherence in
compressive sampling [J]. Inverse Problems, 2007, 23:
969-986.
[10] 李如玮, 鲍长春, 窦慧晶. 基于双正交小波包分解的
自适应阀值语音增强 [J]. 仪器仪表学报, 2008, (29):
2135-2140.
LI R W, BAO CH CH, DOU H J. Speech enhacement
using adaptive threshold based on bi-orthogonal wavelet
packet decomposition [J]. Chinese Journal of Scientific
Instrument, 2008, (29): 2135-2140.
[11] 冯登超, 杨兆选. 基于小波包最优基的图像压缩算法 [J].
电子测量与仪器学报, 2007, (21): 20-22.
FENG D CH, YANG ZH X. Image compression
algorithm based on best basis of wavelet packets [J].
Journal of Electronic Measurement and Instrument, 2007,
(21): 20-22.
[12] TROPP J A. Algorithms for simultaneous sparse
approximation. Part II: Convex relaxation [J]. Signal
Process. (Special Issue on Sparse Approximations in
Signal and Image Processing), 2006, (86): 589-602. [13] 付宁, 彭喜元. 基于改进L1范数最小化组合算法的欠
定盲源分离 [J]. 电子测量与仪器学报, 2009, (23): 1-6.
FU N, PENG X Y. Underdetermined blind source
separation based on improved combinatorial algorithm
for L1-norm minimization [J]. Journal of Electronic
Measurement and Instrument, 2009, (23): 1-6.
[14] DONOHO D L, ELAD M, TEMLYAKOV V. Stable
recovery of sparse overcomplete representations in the
presence of noise [J]. IEEE Transactions on Information
Theory, 2006, 52(1): 6-18
[15] CANDES E, WAKIN M. Enhancing sparsity by
reweighted l1 minimazation [J]. Journal Fourier Anal.
Application, 2007, 14: 877-905.
作者简介:
赵贻玖:男, 1980年出生, 2004年于
电子科技大学获得学士学位, 2007年于
电子科技大学获得硕士学位, 现为电子
科技大学自动化工程学院博士生。主要研
究方向为数据采集与信号处理。
E-mail:zhao812@https://www.doczj.com/doc/6911803183.html,
Zhao Yijiu: received BS degree and M
S degree from University of Electronic
Science and Technology of China (UESTC) in 2004 and 2007 respectively. Now he is PhD can-didate in Measuring and Test Technologies and Instruments from UESTC. His research interests are signal sampling and signal processing.
赵贻玖