融合解析模型和综合模型的压缩感知算法

练秋生,韩　敏,石保顺,陈书贞

(燕山大学信息科学与工程学院,河北秦皇岛066004)



融合解析模型和综合模型的压缩感知算法

练秋生,韩敏,石保顺,陈书贞

(燕山大学信息科学与工程学院,河北秦皇岛066004)

摘要：如何利用更多的图像先验知识来提高图像的重构质量是压缩感知的一个关键问题.本文将综合稀疏模型与近几年提出的Cosparse解析模型结合,利用图像在综合字典和解析字典下的稀疏性提出了一种融合两种稀疏先验的图像重构算法,并利用交替方向乘子法(ADMM)求解对应的复杂优化问题.为进一步提高算法性能,该算法还充分利用了图像中任意位置图像块的稀疏性.实验结果表明,本文算法能有效提高图像重构质量.

关键词:压缩感知;稀疏表示;Cosparse解析模型;图像重构

1引言

传统的奈奎斯特采样定理指出,信号的采样频率必须大于带宽的两倍才能确保完全重构原始信号.随着现代信息技术的高速发展,人们对信息数据量的需求不断增加,从而对传统信号处理框架的采样和处理速度都提出了更高的要求.作为奈奎斯特采样定理的另一种选择,Donoho等人于2006年正式提出了压缩感知(Compressed Sensing,CS)理论[1],其思想是将传统的采样和压缩合为一体,通过测量矩阵获得原始信号的少量随机投影,然后利用信号的稀疏先验知识,通过重构算法从远低于奈奎斯特采样率的观测值中获得稀疏解,这种方式大大缓解了采样端的压力,使得宽带信号处理成为现实.

该理论一经提出,迅速成为信息领域的一个研究热点,世界知名大学都成立专门的课题组研究.稀疏字典、测量矩阵和重构算法的设计是压缩感知理论研究的三个核心问题.学者们经过多年的理论研究,已将压缩感知应用在了很多领域,如合成孔径雷达成像、探地雷达成像、核磁共振成像、无线传感器网络和语音识别等领域.

稀疏表示模型是信号与图像处理领域普遍使用的信号模型,CS理论是以其为基础建立的.信号x可以通过综合稀疏模型表示为字典中少量原子的线性组合,即x=Dα.与综合模型对应的是Cosparse解析模型(Analysis Model)[2,3],解析模型假定信号x在解析字典Ω下的变换系数Ωx是稀疏的.当D与Ω正交时,解析模型与综合模型是完全等效的,但在过完备的情况下,它们有着本质的区别,综合模型假定信号是处于由少量原子张成的子空间中,而解析模型则假设信号与大量解析原子张成的子空间正交,所以这两种模型有一定的互补性,本文则根据它们的互补性提出了一种新的重构算法,将综合模型和解析模型融合在一起,期望获得高质量的压缩感知图像重构性能.

2综合与解析稀疏表示模型

从一组带有噪声的测量值:

y=Mx+e

(1)

中恢复出原始信号x∈RN是信号与图像处理领域要解决的主要问题,其中M∈RM×N是已知线性算子,e∈RM为加性高斯白噪声,多数情况下Μ<Ν,因此从y中恢复出信号x是一个NP-hard问题,如何在无穷多解中找到最逼近信号x的解则依赖于稀疏先验知识.

综合稀疏模型假设信号x可以表示为综合字典D∈RN×L中少量原子的线性组合:

x=DαK:=‖α‖0

(2)

其中α∈RL是信号x在综合字典D下的稀疏表示系数,如果α中仅有K(K<

基于综合稀疏模型的图像重构可归结为求解非凸优化问题:

(3)

求解该问题的方法主要包括凸松弛法和贪婪算法,贪婪算法是通过每次迭代时选择一个局部最优解逐渐逼近原始信号,主要包括正交匹配追踪(OMP),压缩采样匹配追踪(CoSaMP),子空间追踪(SP)等算法[4].

近几年,Cosparse解析模型作为综合稀疏模型的对偶模型得到越来越多的研究学者关注,并相继出现了一些关于解析字典学习及应用的文献[5～7].对于信号x,通过线性算子Ω∈RP×N可变换为:

z=ΩxL:=P-‖z‖0

(4)

如果变换系数z∈RP中有许多零元素,则称信号x是共稀疏(Cosparse)的,此模型称为解析模型,其中线性算子Ω称为解析字典,变换系数z中零元素的个数L称为共稀疏度,解析字典Ω中与信号x正交的所有原子的索引值集合称为x的共支撑集Λ,即ΩΛx=0.

对于解析模型,可以通过求解下列最优化问题来进行图像重构:

(5)

目前基于解析模型的压缩感知重构算法分为两类,第一类是解析l1最小化算法(Analysis L1-minimization,AL1)[2];第二类是贪婪算法,主要包括解析贪婪追踪法(Greedy Analysis Pursuit,GAP)[2],解析压缩采样匹配追踪法(ACoSaMP)与解析基追踪法(ASP),解析迭代硬阈值法(AIHT)与解析硬阈值追踪法(AHTP)[8～10].

3融合解析和综合两种稀疏先验的重构算法

与综合模型相比,解析模型把焦点集中在稀疏表示系数的大量零元素上而不是非零元素,在相同维数的情况下,子空间数量更多,有更丰富和更灵活的稀疏表示能力.在解析模型中,信号x与稀疏表示系数Ωx中为零的系数所对应的解析原子张成的子空间正交,而综合模型中信号x处于由少量原子张成的子空间,根据两个模型的互补性,本文提出了融合解析和综合两种稀疏先验的重构算法SAL0(Synthesis and Analysis L0-minimization):

‖α‖0≤K,‖Ωx‖0≤P-L

(6)

+λ2‖αi‖0+λ3‖Ωxi‖0}，i∈C1

(7)

式中xi=Rix∈Rn是原始图像的第i个局部块,Ri∈Rn×Ν定义为取块操作算子;yi是xi在观测矩阵MB下的测量值;C1为非重叠图像块集合;λ1,λ2,λ3为数据保真项与各正则项之间的权衡因子.

本文采用交替优化方式求解式(7)的优化问题,具体包括两个步骤(对于第k次迭代),首先固定xi,更新稀疏系数αi:

(8)

对于稀疏求解问题,常用方法有匹配追踪法(MP)和正交匹配追踪法(OMP),本文采用OMP算法求解式(8).

当稀疏系数αi固定时,更新xi的优化问题为:

(9)

求解式(9)是解析模型下的稀疏求解问题,本文采用GAP算法求解,具体步骤为:

步骤1初始化:共支撑集Λt=[1,P],t=0

步骤2信号估计:

(10)

对xi求偏导数并令其为0得到xi的解:

(11)

综上所述,交替迭代优化式(8)和(9)便可得到图像块xi的最优解,再通过下式求解得到整幅图像x的最优解:

(12)

SAL0算法描述的是非凸优化问题.用l1范数代替l0范数,可将其转换成凸优化问题(SAL1,Synthesis and Analysis L1-minimization):

+λ2‖αi‖1+λ3‖Ωxi‖1},i∈C1

(13)

本文根据交替方向乘子法(ADMM,Alternating Direction Method of Multipliers)的尺度形式[12],令zi=Ωxi,将式(13)的优化问题转换为:

(14)

式中μi为尺度对偶变量(scaled dual variable).上式有四个变量需要优化,同时对这四个变量进行优化能获得全局最优解.虽然式(14)中优化的目标函数为凸函数,但由于式中的l1范数是不光滑且不可微的,目前还没有有效的算法对四个变量同时进行优化.ADMM算法采用交替优化的策略解决这类复杂的凸优化问题,即先固定其它变量,只优化其中的一个变量,从而将原来的复杂优化问题分解为若干简单的子问题进行交替优化.对ADMM算法[12]的理论分析表明,当优化的目标函数是凸函数并且子问题能被有效求解时,ADMM算法能够收敛并且获得满意解.

利用ADMM算法优化式(14)的具体步骤如下:

步骤1固定图像xi、对偶变量μi与解析稀疏系数zi,更新综合稀疏系数αi:

(15)

求解该优化问题的方法很多,本文采用迭代收缩法(Ierative Shrinkage/Thresholding,IST)对其求解.

步骤2固定图像xi、对偶变量μi与综合稀疏系数αi,更新解析稀疏系数zi:

(16)

x=soft(y,λ)=sign(y)·max{|y|-λ/2,0}

(17)

步骤3固定对偶变量μi、解析稀疏系数zi与综合稀疏系数αi,更新图像xi:

(18)

对xi求偏导数并令其为0,从而得到:

(19)

步骤4更新对偶变量μi:

(20)

本文进行了大量实验,在参数λ1=0.4,λ2=0.02,λ3=0.2,β=0.03时得到了较好的图像重构效果.综上,SAL1算法的具体步骤如算法1所示.

----------------------------------------------------------输入:观测值yi(i∈C1),观测矩阵MB,综合字典D,解析字典Ω

fork=1:iter

end

由于上述算法只利用了测量值对应图像块(非重叠图像块)的稀疏性,并没有考虑图像中任意位置图像块的稀疏性,因此在低采样率时重构图像有可能出现块效应[13].为进一步提高图像重构质量,充分利用图像中任意位置图像块在综合字典和解析字典下的稀疏性,本文提出O-SAL1算法 (Synthesis and Analysis L1-minimization with Overlapping Patches Sparsity).考虑任意位置两种字典表示的稀疏性,则式(13)变为:

(21)

式中C1为非重叠块集合,C2为重叠图像块集合,它保证了图像中任意位置图像块的稀疏性.用ADMM算法对其进行变量置换,令zi=ΩRix得到:

(22)

该优化问题的求解十分困难,为了减少算法的运算开销,本文将其分解为两个部分进行交替迭代优化,第一部分为非重叠分块,与式(14)相同;第二部分为重叠分块,其对应的优化问题为:

(23)

式(23)描述的优化问题中αi与zi的优化方法与SAL1算法相同,当对偶变量μi、解析稀疏系数zi与综合稀疏系数αi固定,更新图像x:

(24)

对x求偏导数并令其为0得到:

(25)

(26)

当β1充分大时,式(26)和式(24)是等效的.固定x,对wi求偏导数并令其为0得到:

(27)

固定wi,更新x:

(28)

对x求偏导数并令其为0得到:

(29)

综上,O-SAL1算法的具体步骤如算法2所示.其中SAL1(yi,xk-1)表示SAL1算法中x的初始值由0改为xk-1.

4实验结果

为了验证本文算法的有效性,本文采用了Lena、Couple、Girl、Boat、Clown和Goldhill六幅标准灰度图像作为测试图像进行压缩感知图像重构实验,图像大小均为512×512,它们均来源于文献[14]的程序包,可从http://www.ece.msstate.edu/～fowler/BCSSP/下载.

在本文的实验中,图像的分块大小为8×8,所有算法使用的观测矩阵MB均为相同的高斯随机矩阵,综合字典D是从Berkeley自然图像库中学习到的冗余度为4的通用K-SVD字典[15],大小为64×256.目前关于解析字典Ω的学习算法还比较少,主要包括Analysis K-SVD学习算法[5]、约束解析算子学习(Constrained Analysis Operator Learning,CAOL)[6]算法和几何解析算子学习(Geometric Analysis Operator Learning,GAOL)[7]算法.GAOL算法采用了与其他算法完全不同的方式,它将ΩT看作是矩阵空间中斜流形(oblique manifold)上的一个元素,将解析字典的学习问题转化为矩阵流形的优化问题,该算法复杂度适中,收敛特性较好,本文使用的解析字典是由GAOL算法学习获得,其冗余度为4,大小为256×64.

在采样率为10%、20%、30%时,用本文提出的算法对六幅测试图像进行重构实验,然后将实验结果与基于综合模型的凸优化算法SL1(Synthesis L1-minimization)和基于解析模型的凸优化算法AL1比较(代码可从http://www.cs.technion.ac.il/～raj下载),结果如表1所示.

表1　图像重构结果PSNR比较(dB)

从表1可以看出O-SAL1算法的图像重构结果优于其他算法,以图像Lena为例,在三种采样率下,重构图像的平均PSNR值比SL1、AL1、SAL0、SAL1算法分别提高了2.16dB、1.62dB、1.21dB、0.81dB.

为了检验本文算法的收敛性,图2给出了采样率为20%时,SAL1算法的重构图像PSNR值随迭代次数变化的曲线.从图2可以看出,在采样率为20%时,本文算法通过60次迭代就基本达到了收敛,具有较好的收敛性.

图3给出了采样率为20%时部分算法对Lena图像的重构图像.从图3可以看出,基于综合稀疏先验的SL1算法和基于解析稀疏先验的AL1算法重构质量较差,细节信息丢失较多,并且边缘部分具有明显的块效应.融合两种稀疏先验的SAL0与SAL1算法重构效果比SL1、AL1算法好,但边缘和细节部分仍有轻微的锯齿效应.O-SAL1算法的重构图像块效应最少,保留了更多的细节信息,边缘和纹理更清晰.表1和图3的实验数据表明,融合综合稀疏和解析稀疏两种先验的图像重构算法比单独利用综合稀疏或解析稀疏的重构算法具有明显优势,而考虑图像中任意位置图像块的稀疏性比仅利用非重叠图像块(测量值对应图像块)的稀疏性能有效提高图像重构质量.

为了进一步证明本文算法的优越性,本文将重构结果与文献[11,14]中提出的算法进行比较,如表2所示.文献[11]中提出的BCS-SPL-DDWT算法是基于双复数小波和分块随机投影的压缩感知重构算法,文献[14]提出的MH-BCS-SPL算法是在BCS-SPL-DDWT算法基础上根据多重假设预测提出的改进算法,它是近几年压缩感知图像重构较为优秀的算法之一.为了使实验结果具有可比性,BCS-SPL-DDWT算法和MH-BCS-SPL算法中的图像块大小均改为8×8.

表2　图像重构结果PSNR比较(dB)

表2中DDWT代表BCS-SPL-DDWT算法,MH表示MH-BCS-SPL算法.从表中可以看出,O-SAL1算法的图像重构质量明显优于DDWT算法,在三种采样率下,六幅重构图像的平均PSNR值比DDWT算法分别提高了1.04dB、1.84dB、2.11dB、0.95dB、2.20dB、1.31dB;比MH算法分别提高了0.29dB、0.83dB、0.46dB、0.47dB、0.45dB、0.99dB.

5结论

本文针对综合稀疏模型和Cosparse解析模型的互补性,提出了融合综合稀疏先验和解析稀疏先验的压缩感知重构算法.该算法将两种稀疏模型结合到压缩感知图像重构的代价函数中,利用ADMM算法有效地求解所对应的优化问题.实验证明该算法无论是从客观评价标准还是主观视觉效果都有明显的提高,如何将两种稀疏模型融合应用到其它图像反问题中是将来的一个研究方向.

参考文献

[1]D L Donoho.Compressed sensing[J].IEEE Transactions on Information Theory,2006,52(4):1289-1306.

[2]M E Davies,M Elad.The cosparse analysis model and algorithms[J].Applied and Computational Harmonic Analysis,2013,34(1):30-56.

[3]T Peleg,M Elad.Performance guarantees of the thresholding algorithm for the co-sparse analysis model[J].IEEE Transactions on Information Theory,2013,59(3):1832-1845.

[4]杨海蓉,张成,丁大为,韦穗.压缩传感理论与重构算法[J].电子学报,2011,39(1):142-148.

Yang Hai-rong,Zhang Cheng,Ding Da-wei,Wei Sui.The theory of compressed sensing and reconstruction algorithm[J].Acta Electronics Sinica,2011,39(1):142-148.(in Chinese)

[5]R Rubinstein,T Peleg,M Elad.Analysis K-SVD:A dictionary-learning algorithm for the analysis sparse Model[J].IEEE Transactions on Signal Processing,2013,61(3):661-677.

[6]M Yaghoobi,S Nam,R Gribonval,M E Davies.Constrained overcomplete analysis operator learning for cosparse signal modeling[J].IEEE Transactions on Signal Processing,2013,61(9):2341-2355.

[7]Hawe S,Kleinsteuber M,Diepold K.Analysis operator learning and its application to image reconstruction[J].IEEE Transactions on Image Processing,2013,22(6):2138-2150.

[8]R Giryes,M Elad.CoSaMP and SP for the cosparse analysis model[A].The 20th European Signal Processing Conference[C].Bucharest,Romania:IEEE Press,2012.964-968.

[9]R Giryes,S Nam,M Elad,R Gribonval,M E Davies.Greedy-like algorithms for the co-sparse analysis model[J].Linear Algebra and Its Applications,2014,441:22-60.

[10]R Giryes,S Nam,R Gribonval,M E Davies.Iterative cosparse projection algorithms for the recovery of cosparse vectors[A].The 19th European Signal Processing Conference[C].Barcelona,Spain:EUSIPCO,Poland,2011.1460-1464.

[11]S Mun,J E Fowler.Block compressed sensing of images using directional transforms[A].IEEE International Conference on Image Processing[C].Cairo,Egypt:IEEE Press,2009.3021-3024.

[12]S Boyd,N Parikh,E Chu,B Peleato.Distributed optimization and statistical learning via the alternating method of multipliers[J].Foundations and Trends in Machine Learning,2010,3(1):1-122.

[13]练秋生,张红卫,陈书贞.基于图像块整体稀疏性与流形投影的压缩成像[J].电子学报,2013,41(5):905-911.

Lian Qiu-sheng,Zhang Hong-wei,Chen Shu-zhen.Compressive imaging algorithm based on the integrated sparse property of image patches and manifold projection[J].Acta Electronics Sinica,2013,41(5):905-911.(in Chinese)

[14]C Chen,E W Tramel,J E Fowler.Compressed sensing recovery of images and video using multi-hypothesis predictions[A].Proceedings of the 45th Asilomar Conference on Signals,Systems,and Computers[C].Pacific Grove,CA:IEEE Press,2011.1193-1198.

[15]M Aharon,M Elad,A Bruckstein.K-SVD:An algorithm for designing overcomplete dictionaries for sparse representation[J].IEEE Transactions on Signal Processing,2006,54(11):4311-4322.

练秋生男,1969年8月生于江西遂川,现为燕山大学信息科学与工程学院教授,博士生导师,主要研究方向为图像处理,稀疏表示,压缩感知及相位恢复等.

E-mail:lianqs@ysu.edu.cn

韩敏女,1989年9月生于河北沧州,现为燕山大学信息科学与工程学院硕士研究生,主要研究方向为图像稀疏表示,压缩感知.

E-mail:mnhanmin@163.com

石保顺男,1989年2月生于河北唐山,现为燕山大学信息科学与工程学院博士研究生,主要研究方向为盲压缩感知、字典学习及相位恢复.

E-mail:shibaoshun@stumail.ysu.edu.cn

陈书贞女,1968年11月生于河北定州.现为燕山大学信息科学与工程学院副教授.主要研究方向为图像处理,压缩感知及生物识别等.

E-mail:chen-sz818@163.com

Compressed Sensing Algorithm Fused the Cosparse Analysis Model and the Synthesis Sparse Model

LIAN Qiu-sheng,HAN Min,SHI Bao-shun,CHEN Shu-zhen

(SchoolofInformationScienceandEngineering,YanshanUniversity,Qinhuangdao,Hebei066004,China)

Abstract:How to improve the reconstructed image quality using more prior knowledge of the image is still a crucial issue of compressed sensing.In this paper,we combine the synthesis sparse model and the cosparse analysis model proposed in recent years,and propose a novel reconstruction algorithm based on the sparsity of the image over a synthesis dictionary and an analysis dictionary.Moreover,alternating direction method of multipliers (ADMM) is exploited to solve the corresponding complicated optimization problem.To further improve the performance,the sparsity of patches in any position of the image is utilized by the proposed algorithm.The experimental results show that our algorithm can effectively improve the quality of image reconstruction.

Key words:compressed sensing;sparse representation;cosparse analysis model;image reconstruction

作者简介

DOI:电子学报URL:http://www.ejournal.org.cn10.3969/j.issn.0372-2112.2016.03.018

中图分类号:TN911.73

文献标识码：A

文章编号：0372-2112 (2016)03-0613-07

基金项目:国家自然科学基金(No.61071200,No.61471313);河北省自然科学基金(No.F2014203076)

收稿日期:2014-07-31;修回日期:2015-01-15;责任编辑：梅志强