当前位置:首页 >> 信息与通信 >>

一种基于KSVD-ETF的测量矩阵优化方法


Journal of Image and Signal Processing 图像与信号处理, 2014, 3, 15-18 http://dx.doi.org/10.12677/jisp.2014.31003 Published Online January 2014 (http://www.hanspub.org/journal/jisp.html)

The Optimization Design of Measurement Matrix Based on KSVD-ETF
Yizhi Zhao2, Lixin Wang1,2, Jian Qian2
1

No. 36 Research Institute of China Electronics Technology Group Corporation, Jiaxing 2 School of Communication Engineering, Hangzhou Dianzi University, Hangzhou Email: zhao_yizhi@163.com Received: Nov. 26th, 2013; revised: Dec. 9th, 2013; accepted: Dec. 14th, 2013

Copyright ? 2014 Yizhi Zhao et al. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited. In accordance of the Creative Commons Attribution License all Copyrights ? 2014 are reserved for Hans and the owner of the intellectual property Yizhi Zhao et al. All Copyright ? 2014 are guarded by law and by Hans as a guardian.

Abstract: Compressive sensing, a novel signal acquisition method, is a joint sensing-compression process which requires a small number of measurements to reconstruct signal. Measurement matrix, a very important part in compressive sensing, directly affects the adaptive sparsity, the required number of measurements and the reconstruct performance of the signal. In order to decrease the mutual coherence between the measurement matrix and sparse transformed matrix and improve the quality of reconstruction, this paper addresses the joint optimization between measurement matrix and sparse dictionary based on the KSVD-ETF. While optimizing the measurement matrix by ETF, we use the KSVD method to update the dictionary. The PSNR of the reconstructed signal is improved with the optimized measurement matrix from the experimental results, indicating that this method of optimizing the measurement matrix has certain advantages in the effect of reconstruction. Keywords: Compressed Sensing; Measurement Matrix; Sparse Dictionary; Mutual Coherence; KSVD-ETF

一种基于 KSVD-ETF 的测量矩阵优化方法
赵毅智 2,汪立新 1,2,钱
1

建2

中国电子科技集团公司第 36 研究所,嘉兴 2 杭州电子科技大学通信工程学院,杭州 Email: zhao_yizhi@163.com

收稿日期:2013 年 11 月 26 日;修回日期:2013 年 12 月 9 日;录用日期:2013 年 12 月 14 日



要:压缩感知将数据的采样和压缩同时处理,仅需少量测量就能重建信号。测量矩阵直接影响着信号适应

的稀疏度范围和重建效果。为了减小测量矩阵与稀疏变换矩阵的互相干性,提出一种基于 KSVD-ETF 的测量矩 阵和稀疏表达字典联合优化的方法,在对测量矩阵进行 ETF 优化的同时利用 KSVD 方法更新优化表达字典,实 验结果中利用该方法优化矩阵所得重建信号 PSNR 有所提高,表明优化测量矩阵的方法在重建效果方面有一定 的优势。 关键词:压缩感知;测量矩阵;稀疏字典;互相干性;KSVD-ETF

1. 引言
压缩感知是信号处理领域中的一个新颖理论 , 它的核心步骤是在数据采样的同时对数据压缩,充分
OPEN ACCESS
[1]

利用了信号的稀疏性或者可压缩性,为突破传统的信 号处理方法提供了新的方向。压缩感知理论指出,只 要信号在某个变换域是稀疏的或者是可压缩的,那么
15

一种基于 KSVD-ETF 的测量矩阵优化方法

就可以用一个跟变换基不相关的测量矩阵将变换所 得到高维信号投影到一个低维空间上,然后通过求解 一个非线性的优化问题就可以从这些少量的投影中 以高概率恢复出原信号 。该理论突破了传统的奈奎 斯特采样原理需要至少两倍信号带宽的限制,克服了 采样数据量巨大,传感元、采样时间以及数据存储空 间等物理资源浪费严重的问题,理论一经提出便得到 众多学者的高度关注。 测量向量获取和信号重建是压缩感知的核心步 骤,而测量矩阵直接影响着信号适应的稀疏度范围和 重建信号所需测量数目以及重建效果[3],因此测量矩 阵的选取在压缩感知中起着关键作用,所以研究如何 构造性能更好的测量矩阵,或如何优化现有测量矩阵 的性能具有重要的意义。目前应用的测量矩阵主要有 两种,一种是随机测量矩阵,如高斯矩阵、贝努利矩 阵,亚高斯矩阵等;另一种是确定性测量矩阵,如部 分啥达玛矩阵、托普利兹矩阵、多项式矩阵等[4]。近 来研究表明,通过减小测量矩阵与稀疏变换矩阵的互 相干系数可以提高压缩感知的整体性能,互相干系数 影响着信号适应的稀疏度范围和重建信号所需测量 数目以及重建效果:互相干系数越小,信号适应的稀 疏度范围越大,重建信号需要的测量值的数目越少, 信号的重建效果也越好[5]。此类方法首先通过测量矩 阵和稀疏变换矩阵的乘积, 构造其对应的 Gram 矩阵, 该矩阵非对角线元素即是测量矩阵和稀疏变换矩阵 的互相关系数,然后通过研究 Gram 矩阵的特性改善 测量矩阵的性能 。Elad 通过阈值法来减小 Gram 矩 阵非对角线元素,进而减少测量矩阵和稀疏变换矩阵 的相关性[7];Vahid Abolghasemi 采用梯度下降迭代法 来使得 Gram 矩阵接近于单位阵[8];文献[9]则是通过 ETF(等角紧框架)来逐步更新 Gram 矩阵,让 Gram 矩 阵的非对角线元素都等于矩阵的最大的互相干系数, 以获得较好的性能。上述方法都是在减小 Gram 矩阵 非对角线元素,进而得到优化的测量矩阵。本文从另 一角度出发,在对测量矩阵进行优化的同时采用 KSVD 方法对稀疏变换矩阵也进行优化,即测量矩阵 和表达字典的联合优化,通过仿真结果验证表明,联 合优化可以产生更好的信号重建效果。
[6] [2]

采样)和解码(即信号重建),本文的研究重点在信号的 编码部分。压缩感知理论的两个重要前提是稀疏性和 不相干性,稀疏信号在适当的表达基上可以由少量的 非零系数表达出来[10]。 设 x ∈ ? N 是一个时域稀疏信号,如果 x 中只有 s 个非零元素,则 s 称为 x 的稀疏度。压缩感知的测量 过程可表示为

y = Φx
= Φ 其中 y ∈ ? m 为测量值,
量矩阵,一般有 m ? N
[11]

(1)

[φ1

? φm ] ∈ ? m× N 是测
T

。假设 x 在时域中不是稀疏 (2)
T

的,但是它可以在另外的基中被稀疏表示。即有

x = Ψθ

= Ψ [ψ 1 ? ψ K ] ∈ R N × K 称为稀 的稀疏表示形式,则
疏变换矩阵或表达字典, θ = [θ1 ? θ N ] 是信号 x 在 Ψ 上的表达系数矢量。 为了达到较好的压缩感知效 果, 我们寻找与稀疏变换矩阵 Ψ 相干性很小的测量矩 阵 Φ ,即使得矩阵

D = ΦΨ

(3)

有很小的列向量相干系数,这里 D 称为恢复矩阵[12]。
T Elad 引入了互相干系数概念 ? ( D ) = max ? ? di d j ? ?,

然后构造 D 的 Gram 矩阵
G = DT D

i≠ j

(4)

通过优化 Gram 矩阵[13],使其逼近单位阵 I

= G min G ? I
来减小 ? ( D ) 。

2 F

(5)

通过使 Gram 矩阵逼近等角紧框架(ETF)来减小 相干性时,设 Λ N 是一组 m × N 的 ETF 对应的 Gram 矩阵集合[14]:
? ? ? ? N×N T ? ij = : GΛ = ,g ?G ? Λ N =∈ GΛ ?GΛ R ? ? i≠ j ? ?

(6)

使 D 的 Gram 矩阵逼近 GΛ ,即:

min G ? GΛ

2 F

(7)

这是一个迭代更新 G 的过程:首先计算出 通过 GP +1 = γ GP + (1 ? γ ) GP ?1 得到更新的 Gram 矩阵 G , 本文则是利用 对 G 进行 QR 分解可得到更新的 D [15]。 奇异值分解(SVD)的方法获得 D ,最后测量矩阵可由
OPEN ACCESS

GP ?1 = D T D ,然后将它投影到 Λ N 上得到 GP ,最后

2. 基于 Gram 矩阵的测量矩阵优化
压缩感知主要包括两个部分: 编码(即信号的测量
16

一种基于 KSVD-ETF 的测量矩阵优化方法

Φ = DΨ ?1 得到, 经过一系列的迭代运算, 就能达到优
化测量矩阵的效果。

? ,然后由 KSVD 方法得到 D ? 法(OMP)得到 Θ eq ? 从D ? 中得到更新字 (4) 利用 ETF 优化后的 Φ
eq

3. 测量矩阵和表达字典的联合优化
KSVD 方法是一个字典训练算法,若 D ∈ ? n× K , 的稀疏表示稀疏向量, Y = { yi }i =1 为 N 个训练信号的
N

? , ? 去优化测量矩阵 而在下一轮的迭代中再用 Ψ 典Ψ ? ? ,继续利用 KSVD 方法获得更新的字典 Ψ Φ

(5) K= k + 1 ,重复上述过程 输出:以上算法输出为 Φ Iter 和 Ψ Iter 。

x ∈ ? , y ∈ ? 分别代表字典、训练信号、训练新号
K
n

集合, X = { xi }i =1 为 Y 的解向量集合,则 KSVD 训练
N

4. 仿真实验
我们随机选取 64 × 5000 的训练序列 X ∈ ? N × P , 通 过 ETF 优化和 KSVD 方法来获得优化的测量矩阵 Φ 和更新字典 Ψ 。实验中选择了随机高斯矩阵和 ETF 优化矩阵方法进行对比仿真。 文献[12]中提出了基于 Gram 矩阵的 t ? 平均互相 干性,这样能够更好的描述互相干性的意义。 t ? 平 均互相干性定义为 Gram 矩阵中所有非对角的值大于

方法的目标方程为:
min Y ? DX
D, X 2 F

s.t.?i, θi

?0

≤s

(8)

其中 s 为稀疏表示系数中非零分量的数目上限。上式 的求解是一个迭代过程。 首先, 假设字典 D 是固定的, 用 MP、 OMP 或 BP 算法可以得到字典 D 上 Y 的稀疏 表示系数矩阵 X ;然后根据系数矩阵 X 找到更好的 字典 D 。 联合优化的思想是利用基于 KSVD 方法更新表 达字典和基于等角紧框架(ETF)方法更新测量矩阵的 综合,来解决下面的问题:
Ψ ,Φ ,Θ

t 的元素和的平均值,如下式:
?t { D} =
1≤ i , j ≤ n ;i ≠ j



min α X ? ΨΘ

{

2 F

+ Y ? ΨΦΘ

2 F

}

1≤ i , j ≤ n ;i ≠ j

( g ≥ t)? g ∑ ( g ≥ t)
ij ij

ij

(11)

s.t.?i, θi

?0

≤ s (9)

选取本文优化的表达字典,我们分别计算三种测 量矩阵的 ?t { D} 如表 1。 从表中可以看出 KSVD-ETF 优化矩阵的 ?t { D} 下面我们讨论测量值数目 m 对图像重建结果的

Θ 是 X 在 Ψ 上的稀疏表示,常量参数 0 ≤ α ≤ 1
用来控制 X ? ΨΘ F 的加权误差。 (9)可以写成下面的形式
2

值最小,即本文方法可以减小 t ? 平均互相干性。

?α X ? ?α I ? min ? ? ? ? ? ΨΘ Ψ ,Φ ,Θ ? Y ? ?Φ?

2

s.t.?i, θi
F

?0

≤s

(10)

影响。对于给定的 m 值,我们利用正交匹配追踪重建 算法进行重建,计算重建图像的峰值信噪比 PSNR。 实验中,我们设定测量值数目 m 从 20 到 160 变化, 重建图像的峰值信噪比 PSNR 随测量值数目 m 的变化 情况如图 1 所示,很明显可以看到采用本文提出的优 化方法后的测量矩进行图像重建可以提高重建信号 的 PSNR,改善重建质量。 我们也测试了 KSVD-ETF 方法更新的表达字典 和傅里叶正交变换矩阵两个不同表达基的稀疏对比 情况, 设定信号稀疏度 s 从 6 到 20 变化, 经正交匹配 追踪重建算法进行重建的信号峰值信噪比 PSNR 随信 号稀疏度 s 的变化情况如图 2,可以看出本文方法所 得表达字典具有更好的性能。

?α X ? ?α I ? 若定义 Z = ? ? , W = ? ? ,则上式可写成 Y ? ? ?Φ?
Ψ ,Φ ,Θ

min Z ? Deq Θ

2 F

s.t.?i, θi
eq K

?0

≤s

(11)

= W = Ψ ? ? d ? 这里 D 上式的解可以 eq ?d ?。 通过 ETF 优化测量矩阵和 KSVD 方法获得。具体
eq 1

算法步骤如下: 输入:Ψ -字典,Φ -随机矩阵,α -调整元素, Iter-迭代次数; 初始化:设 X ∈ ?
N ×P

为任意的训练信号序列;

循环:设定 k = 0 ,循环 Iter 此 (1) 将 X 投影到 Φ 上 Y = ΦX , ? , (2) ETF 优化 Φ 得到 Φ (3) (1)、(2)结果带入(11)式中运用正交匹配算
OPEN ACCESS

5. 结论
本文提出一种在压缩感知中优化测量矩阵的算
17

一种基于 KSVD-ETF 的测量矩阵优化方法
Table 1. Different measurement matrix of t ? average mutual coherence, t = 0.8 表 1. 不同测量矩阵的 t ? 平均互相干性, t = 0.8

法,在对测量矩阵进行 ETF 优化的同时,利用 KSVD 方法更新优化表达字典,将测量矩阵和表达字典联合 优化。实验结果表明,联合优化方法使得 Gram 矩阵 的 t ? 平均互相干系数 ?t { D} 明显减小,重建信号峰 值信噪比 PSNR 也有所提高。基于以上讨论,可以证 明采用本文方法优化后的测量矩阵进行可以降低测 量矩阵和稀疏表达字典的相干性,提高压缩感知的性 能和重建质量。

测量数目 m 10 15 20 25
19 18 17 16
PSNR(dB)

?t { D} , t = 0.8
KSVD-ET 优化矩阵 0.6431 0.7023 0.7173 0.7854 ET 优化矩阵 0.7383 0.8174 0.8062 0.8393 随机高斯矩阵 0.8024 0.8491 0.8589 0.8805

参考文献 (References)
[1] [2] [3] [4] [5]
随机高斯矩阵 优化矩阵 ETF 优化矩阵 KSVD-ETF

15 14 13 12 11 20

[6]

40

60

80 M

100

120

140

160

[7] [8] [9]

Figure 1. The reconstructed signal PSNR with measured value changes in number of M 图 l. 重建信号的 PSNR 随测量值数目 m 的变化情况
29

28

[10]

27

[11]
PSNR(dB)

26

25

[12] [13]
傅里叶正交变换矩阵 更新字典

24

23

KSVD-ETF 22 6

[14] [15]

8

10

12 s

14

16

18

20

Figure 2. The reconstructed signal of PSNR changes with the signal sparsity S 图 2. 重建信号的 PSNR 随信号稀疏度 s 的变化情况

Donoho, D. (2006) Compressed sensing. IEEE Transactions on Information Theory, 52, 1289-1306. Candes, E.J. and Wakin, M.B. (2008) An introduction to compressive sampling. IEEE Signal Processing Magazine, 25, 2130. 张凯 , 杜小勇 , 王壮 (2011) 基于压缩感知的空间目标三维 雷达成像方法. 信号处理, 9, 1406-1411 Tropp, J.A. and Gilbert, A.C. (2007) Signal recovery from random measurements via orthogonal matching pursuit. IEEE Transactions on Information Theory, 12, 4655-4666. 刘丹华 , 石光明 , 周佳社 (2008) 一种冗余字典下的信号稀 疏分解新方法. 西安电子科技大学学报, 35, 228-232. Candes, E.J., Romberg, J. and Tao, T. (2006) Robust uncertainty principles: Exact signal reconstruction from highly incomplete frequency information. IEEE Transactions on Information Theory, 52, 489-509. Strohmer, T. (2008) A note on equiangular tight frames. Linear Algebra, 429, 326-330. Renes, J.M. (2007) Equiangular tight frames from paley tournamenrs. Linear Algebra, 426, 497-501. Zahedi, R., Pezeshki, A. and Chong, E.K.P. (2010) Robust measurement design for detecting sparse signals: Equiangular uniform tight frames and grassmannian packings. American Control Conference, Baltimore, June 30-July 2 2010, 4070-4075. Tropp, J.A., Dhillon, I.S., Heath, R.W. and Strohmer, T. (2005) Designing structured tight frames via an alternating projection method. IEEE Transactions on Information Theory, 51, 188209. Endra (2011) Color image reconstruction from compressive sensing with optimized measurement matrix, Binus ICT National Conference, 15-16. Elad, M. (2007) Optimized projections for compressed sensing. IEEE Transactions on Signal Processing, 55, 5695-5702. Duarte-Carvajalino, J.M. and Sapiro, G. (2009) Learning to sense sparse signals: Simultaneous sensing matrix and sparsifying dictionary optimization. IEEE Transactions on Image Processing, 18, 1395-1408. Xu, J.P., Pi Y.M. and Cao, Z.J. (2010) Optimized projection matrix for compressive sensing. EURASIP Journal on Advances in Signal Processing, 2010, 560349. Oey, E. and Gunawan, D. (2011) Image reconstruction from compressive sensing with optimized measurement matrix, 12th International Conference on Quality in Research (QiR), 4-7 July 2011.

18

OPEN ACCESS


相关文章:
更多相关标签: