第7卷第1期 智能系统学报 Vol.7 No.1 2012年2月 CAAI Transactions on Intelligent Systems Feh.2012 D0I:10.3969/i.issn.16734785.201110010 网络出版t地址：htp://www.cnki.net/kcma/detail/23.1538.TP.20120216.2036.002.html 压缩感知理论及其在成像技术中的应用 赵春晖，刘巍 (哈尔滨工程大学信息与通信工程学院，黑龙江哈尔滨150001) 摘要：在传统的Shannon/Nyquist采样定理指导下，信号处理往往面临两大难题：A/D转换器技术的限制和海量采 样数据的处理压力.压缩感知(CS)理论表明当信号具有稀疏性或可压缩性时，可以通过全局非自适应线性投影的方 式，用远低于Shannon/Nyquist采样定理要求的颍率获取信号的全部信息.以CS理论为基础的压缩成像(CI)技术在 近年来得到了快速的发展.在概述CS理论的基础上，着重介绍了CI技术的原理及其发展状况，并从稀疏分解、观测 矩阵的构造和重建算法3个方面对其关键问题进行了分析.CI系统可以显著节省感光器件的数量，避免了传统成像 技术“先采样再压缩”方式带来的资源浪费. 关键词：压缩感知：压缩成像：稀疏分解：观测矩阵：重建算法 中图分类号：TP391.41;TN911.73文献标识码：A文章编号：1673-4785(2012)01-0021-12 Compressive sensing theory and its application in imaging technology ZHAO Chunhui,LIU Wei College of Information and Communication Engineering,Harbin Engineering University,Harbin 150001,China) Abstract:Under the guidance of the traditional Shannon/Nyquist sampling theorem,signal processing often faces two problems:technology limitation of the A/D converter and processing pressure caused by a mass of sampled da- ta.Compressive sensing (CS)theory suggests that when the signal is sparse or compressible,by means of global non-adaptive linear projection,all the signal information can be obtained with the samples much less than the sam- pling theorem required.CS theory based compressive imaging(CI)technology has been developed significantly in recent years.This paper first reviewed the principles of CS,and on this basis,discussed the theory and develop- ment of CI technology.The key issues of CI were also analyzed from three aspects of sparse decomposition,con- struction of measurement matrix,and the reconstruction algorithm.The CI system can significantly cut down on the number of photosensitive devices to avoid resource waste caused by a traditional"sample-then-compress"frame- work. Keywords:compressive sensing (CS);compressive imaging (CI);sparse decomposition;measurement matrix; reconstruction algorithm 作为信号处理领域的一块基石，传统的Shan 宽带通信等领域中，Shannon/Nyquist采样定理所要 non/Nyquist采样定理给出了一种将模拟信号离散 求的采样频率超出了一般A/D转换器的处理能力， 化的局部采样方案并确定了采样间距的下限，它作 导致信号包含的信息难以在采样过程中得到完整的 为信号处理领域中的一个核心原理指导着现今几乎 保存并且极易引入混叠和各种噪声，其导致的另一 所有的信息采集工作；但是在诸如雷达、医学成像、 个结果就是接收端被淹没在海量数据之中.而为了 存储和传输这些海量的采样数据，又必须额外引入 收稿日期：2011-10-28.网络出版时间：201202-16. 基金项目：国家自然科学基金资助项目(61077079)；高等学校博士学 复杂的压缩算法.随着社会的进步，人们对于信息的 科点专项基金资助项目(20102304110013)；哈尔滨市优秀 需求正在成倍的增长，传统的采样方式已经成为了 学科带头人基金资助项目(2009 RFXXG034). 通信作者：赵春晖.E-mail:zhaochunhui(@hrbeu.edu.cn. 当前信息技术发展的主要瓶颈之一，迫使人们开始
·22 智能系统学报 第7卷 在信息获取和处理等方面寻找新的出路 式中：更是一个以（*表示共轭转置)为行的 近些年来，一种名为“压缩感知”(compressive M×W矩阵，表示一个普遍意义下的采样行为，不妨 sensing,CS)[1s]的理论开始频繁出现在人们的视线之 称其为观测矩阵，这样可以简单地将信号与波形 中，该理论证明了当信号具有稀疏性或可压缩性时， P()联系起来：如果P(t)是冲击函数，那么y就 可以通过全局非自适应线性投影的方式，用远低于 是理想的信号时域抽样序列；如果9：()是正弦波， Shannon/Nyquist采样定理要求的频率获取信号的全 那么y就是信号的傅里叶系数，这也正是核磁共振 部信息，并且采用非线性优化方法重建该信号.2004 成像(magnetic resonance imaging,MRI)等医学类断 年加州理工大学的E.Candes等在研究医学图像重建 层成像技术的信号获取模型。利用这种采样机制可 的过程中发现了这一现象4]：2006年D.Donoho所撰 以通过M个向量P.(t)∈R"来获取信号f∈R“的 写的一篇以“压缩感知”为名的论文发表在EEE 信息.令人真正感兴趣的是M≤N的情况，也就是说 Transactions on Information Theory上，该理论因此得 当观测值∫的长度远远小于信号值∫的长度时是否 名；随后E.Candes等又进一步证明了采用非自适 有可能从少量的测量值中精确恢复信号呢？是否可 应的随机线性投影方法，可以在观测值高度不完备和 以人为地设计M(M≤N)个P:(t)使其获得信号的 不精确的情况下以极大的概率实现信号重建6).在 全部信息呢？ 此基础上D.Donoho等又在多篇文章中对这一技术进 从数学的角度来看上述想法几乎是不可能的， 行了深人的分析与进一步的探索[8]，使得该理论的 要解决这样的问题就涉及到求解一个条件远远少于 框架日趋完善.作为一种全局采样方式，CS采样过程 未知数的“欠定”方程组，而这种方程组的解应当有 需要同时操作信号的全部采样值.由于潜在像素时间 无穷多个，但是如果信号具有某种特殊的形式，比如 上的同时性，以及自然图像的成像恰好符合这一要 一个信号的值在大部分时间里都是0，只有S个位 求，因此以CS理论为基础的压缩成像(compressive 置有值，那么只要有M≥S个观测样本，方程组中的 imaging,CI)技术241可以显著节省传感器的数量， 方程数量相对于未知数来讲就显得“充足”了，这就 避免了“先采样再压缩”带来的资源浪费，该项技术的 涉及到了信号中普遍存在的稀疏性和可压缩性， 发展将会对诸多领域产生革命性的影响.例如在非可 1,2信号的稀疏性和可压缩性 见光谱成像中，感光器件的价格往往是极其昂贵的， 如果将信号∫的支撑集的势定义为sup(f):= 若要使用传统方法在某一波段对特定的场景成像，那 {i:f≠0}，那么包含在集合s:={fup()≤S}中的 么一次就要根据成像精度的要求使用几百万或上干 信号就称为S稀疏信号，换句话来说S稀疏信号就是 万个针对该频谱的感光器件，但是如果调整成像波 指信号中非零值元素个数最多不超过S个的信号. 段，那么就要将这几百万个感光器件全部更换，假如 信号的稀疏性并不仅仅体现在时域上，考虑一 能够通过CS理论将感光器件的数量降低到一个，那 个长度为N的实值一维离散时间信号f∈R“(高维 么将大大节省成本 信号可以向量化为一维信号).对于一组N×1维正 CS理论的魅力在于其暗示了一种全新的信号 交基向量{中：1，可以将信号表示为这组正交基的 获取准则，引领人们从另外一个角度审视信息与载 线性组合： 体信号之间的深层联系，在此基础上发展起来的CI 技术在降低成像成本、优化成像方式等方面拥有巨 (1) 大的发展潜力，在医学成像、空间探测、非可见光成 式中：x为正交变换的系数.如果以少作为列，构成 像等领域具有广阔的应用前景.本文在概述CS理 一个N×N维的正交基矩阵平的话，式(1)可以方 论的基础上，着重介绍了CI技术的原理及其发展状 便地表示为 况，并对其关键问题进行了分析。 f=Vx. (2) 1 式中：x是以x:为元素的N×1系数向量 压缩感知的基本原理 显然时域形式∫或频域形式x在表示同一个信 1.1常规采样机制 号时是等价的.从这个角度上来说，如果系数矩阵x 为了便于后续的讨论，首先要介绍一下信号处 的支撑集的势为sup(x):={i:x:≠0}，那么当 理中常规的采样机制.一个信号f(t)的获取可以表 sup(x)≤S时，依然可以将信号f称为S-稀疏信号， 示为 只是该信号的稀疏性表现在了频域上. y=(f,p〉，k=1,2,…,M 在实际的处理过程中很难遇到严格的稀疏信 或者等价的 号，待处理信号的能量不会仅仅集中在时域或频域 y =f. 中的若干个点上，大多数情况下它们是散布于整个
第1期 赵春晖，等：压缩感知理论及其在成像技术中的应用 ·23· 信号持续的范围之内的.一般来讲信号的频域系数 于信号∫，即整个观测过程不必是自适应的，它是独立 会遵循一种指数规律516，例如对于一个信号∫ 于信号的形式而存在的；另外业可以认为是由任意一 R“,用一组正交基{少：将其分解为f=∑1x:, 组将信号∫分解为稀疏形式的正交基（或紧框架）组成 如果将系数：按照从大到小的递减顺序重新排列 的矩阵，它只与信号的重建有关 的话，即x)≥xl2≥…≥xlwM,那么对于每个1≤ 在CS理论中，观测矩阵的构造问题实际上就 n≤V来说，各系数应该满足6] 等同于编码模式的选择问题，规测系统的设计与实 xl(am≤R·np 现都是围绕着观测矩阵展开的.观测矩阵在对信号 式中：0≤p≤∞.在这个前提下可以知道，一般信号 进行采样观测的同时需要保持原信号的结构，因为 的系数x中只有少数几个较大的系数，其他系数相 一旦观测过程破坏了信号中的信息，那么精确重建 对较小，称这样的信号为“可压缩信号”，信号的“可 就是不可能的了].观测矩阵的构造问题同时涉及 压缩性”是普遍存在于自然界中的，在此基础上可 到观测矩阵和压缩感知矩阵，因为对于一个严格稀 以在不造成太大感官损失的情况下抛弃小系数，仅 疏的信号来说，观测矩阵Φ就是压缩感知矩阵Q. 仅保留较大的系数。 在CS过程中，压缩感知矩阵⊙必须保证长度为N 1.3压缩感知的编解码原理 的x可以通过M(MN)个观测值y恢复出来.由 1.3.1编码观测原理 于M<N,这个问题似乎是病态的.然而如果x是S 对于一个长度为N的信号f∈R",假设其在时 稀疏的，并且x中的S个非零系数的位置已知，那么 域不具有稀疏性，考虑一个线性观测过程y=,其 只要令M≥S就可以解决这个问题.将这个问题简 中更为一个M×N矩阵.假定MgN,得到一个M× 化成为良态问题的一个充要条件是，对任意x与具 1向量y.显然观测向量y就是信号∫在中上的一个 有相同非零元素的向量y来说，压缩感知矩阵⊙需 线性投影，如果∫对于一组正交基是稀疏的（或可压 要满足一定的原则. 缩的)，那么根据式(2)，可以用变换域系数x的S 在文献[8]中E.Candes等介绍了一种“一致不 稀疏形式（或近似稀疏形式）代替其时域形式∫，则y 确定原则”(uniform uncertainty principle,UUP）,即 可以表示成 压缩感知矩阵⊙必须满足 y=时=Φ%=⊙x, (3) 式中：压缩感知矩阵⊙=ΦD亚是一个M×N矩阵，观 %11≤161≤1I 测向量y由⑧中对应于信号稀疏值位置的S列线 UUP在本质上阐明了®具有一种“受限等距特 性叠加而成.以上构成了CS的基本编码步骤， 性”(restricted isometry property,RP).之后在文献 如图1所示. [11]中这一原则又被进一步修改为如式(4)形式， 若从⑨中提取T列(TC{1,2,…,N},IT1≤S)构成 子矩阵⊙，则⑨，满足 1-d≤I8,≤1+d 2 (4) 式中：δ为⊙的S-受限等距常数.这一原则本质上 要求压缩感知矩阵⑨表现为近似正交的（由于M (a)时域形式 N,所以不可能完全正交).式(4)所表示的就是IP 的具体形式，IP从本质上说明了一个问题：要想完 全重建原始信号，必须确保观测矩阵不会把2个不 NXI 同的S-稀疏信号映射到同一个观测集合当中，这就 要求从观测矩阵中抽取的每T个列向量构成的矩 阵都是非奇异的. 尽管RP理论特性完美，但是它只是观测矩阵 (b)变换域形式 的一个充分条件，而不是必要条件.换句话说，满足 图1压缩感知编码原理 P条件的矩阵可以作为观测矩阵，但是可以作为 Fig.1 Encoding schematic diagram of compressive 观测矩阵的矩阵未必都满足RP条件.另外RP条 sensing 件不具有可计算矩阵结构的简单易行的公式，这样 这里称M×N矩阵Φ为观测矩阵，N×N矩阵亚 一来很难用它来判断某一观测矩阵是否拥有这种特 为稀疏分解矩阵此处需要强调的是Φ的形式不依赖 性，并且也很难用它来指导观测矩阵的设计.R.G
24 智能系统学报 第7卷 Baraniuk给出的RP的等价条件是观测矩阵Φ和 的一个高度非线性空间.解集空间H=N(⊙)+x由 稀疏矩阵业不相关，其具体内容就是Φ的行不能 于矩阵®的随机性而具有一个随机的角度，如 由业的列来表示，反之亦然。 图2(a)所示（在实际使用中M,S≥3，此处为了直观 1.3.2解码重建原理 选择三维)，整个优化过程可以想象成是一个“弱球 考虑S-稀疏系数向量x,如果⑨x=y,那么对于 体”从原点开始慢慢膨胀，这个“球”首次与解集空 任意位于⊙的空集空间N(⊙)中的向量r(⑨=0) 间H接触的点即为最终的解，由于所期望得到的解 来说，都有O(x+r)=y成立.这样在式(3)中，当 是稀疏形式的，所以“球”和H首次接触的点应该位 M<N时应该有无穷多个解x'满足⊙x'=y.因此， 于坐标轴（或若干坐标轴组成的超平面）上.2-最小 重建算法的目标就是在解集空间H=N(⊙)+x中 化得出的解x是在H上最接近原点的点，这个点可 找到信号的稀疏系数向量x,欲在众多候选向量之 以通过一个与H相切的超球面(1,2-球)来找到.考虑 中找到最符合稀疏条件的解，自然要求助于最优化 到H方向的随机性，最近点x有很高的可能性出现 算法.若将向量x的，范数定义为 在远离坐标轴的位置，因此可能既不稀疏又不接近 正确答案x.与此相对地，图2(b)中的L-球具有坐 (IxI)P=∑I:IP (5) 标轴上的点：因此，当构建球从原点开始膨胀的 这里有3种范数优化方式可供选择： 时候，它会首先与解集空间丑相交于一个靠近坐标 1)最小化2范数重建.一般来讲，解决这类优 轴的点，这个点正是稀疏向量x的位置. 化问题的经典方法是通过求解优化方程： x=min‖x'‖2满足r'=y, 找到变换空集空间中，2范数（能量）最小的向量x. 这种最优化方法有方便的近似解x=Q(⑨0)-y, 遗憾的是，范数最小化方法几乎难以找到一个真 正S稀疏的解，取而代之的是含有大量非0值的x. 这是因为从能量的角度上讲，2范数最小化是在众 多信号可能的形式中寻找使其能量最小的解，而将 能量散布于整个信号范围内往往是将能量降低的有 效形式，显然这不是希望见到的形式 2)最小化范数重建.由于2范数最小化表示 (a)l,2范数最小化视觉效果 的信号能量不具有稀疏性，所以考虑针对x中非零 值计算的，范数(S-稀疏向量的，范数等于S).将 优化方程修改为 x=min‖x'‖o满足r'=y, (6) 求解这一优化方程可以精确恢复一个S稀疏信号. 但一般来讲，求解式(6)既是数值不稳定的同时也 是NP-hard的，即无法设计有效的算法进行计算，只 能通过穷举x中非零值位置的全部可能性来一一验 证，直到找到满足条件的解为止 3)最小化1范数重建.相比以上2种方法，求 解基于最小化11范数的优化方程： (b),范数最小化视觉效果 x=min‖x'‖1满足⊙r'=y, (7) 图2重建算法的几何解释 可以精确恢复S稀疏信号和近似可压缩信号.这是 Fig.2 Visualization of reconstruction algorithm 一个凸优化问题1，可以简化为计算复杂度约为 1.4模拟信号的压缩感知 O(N3)的基追踪(basis pursuit,BP)问题9T, CS是从离散信号处理中发展起来的，当然关心它 文献[2-3]分别在二维和三维空间中对最小化 是否可以推广到模拟信号处理当中.在实时处理摸拟 1:范数重建信号的有效性做出了几何解释.通过图 信号时，通常采用的模数(A/D)转换技术往往受到 2可以直观地了解为什么2-最小化所无法求得的稀 Shannon/Nyquist采样率的限制，为了摆脱这种束缚人 疏解，1-最小化却可以找到.在R中所有的S-稀疏 们开始转向更进一步的深层次转换—模拟/信息 向量x的集合是由坐标系中全部S-维超平面组成 (analog-to-information,A/I)转换n2].A/I转换针对模
第1期 赵春晖，等：压缩感知理论及其在成像技术中的应用 ·25· 拟信号本身处理，不必将其转换为数字形式就可以通 下限首先要引入矩阵相关性的概念.观测矩阵Φ和 过一系列的步骤得到离散形式的观测值， 稀疏分解矩阵业之间的相关性可以采用矩阵间的 对于模拟信号f(t),利用一组连续的正交基 相关系数（Φ，）表示， {中.(t)}=可以将其分解为 u(D,)=Nmw（,,〉l. ft)=∑，.(t). 式中：（中，业）∈[1，√n].简单来说，相关系数表征 这里假设系数向量x是严格S稀疏的.尽管每一个 了2个矩阵所包含的元素之间最大的相关关系。 业(t)都可能具有极宽的带宽，但是信号f八t)却可以 (中，)越大表示2个矩阵之间的相关性越大，反 只用很少的自由度确定， 之则越小 A/I转换的处理过程大致分为3步：调制、滤波 定理1】假设信号fR"在稀疏分解矩阵 和采样21，如图3所示.首先利用元素为±1的伪 亚下其系数x是S稀疏的，在Φ域中随机选择M 随机序列P。(t)对模拟信号f(t)进行调制（即相 个规测值满足 乘)，这样做的目的是使信号的频域成分被分散开， M≥C×u2(Φ，)×S×logN, 不受后续滤波处理的破坏，此处的调制速率必须大 式中：C为一个正值常数那么式(7)表示的1-最小 于或者等于输入信号f(t)的Shannon/Nyquist采样 化将以极大的概率取得精确解 率；之后用冲击响应为(t)的低通滤波器对其进行 对定理1有如下4点说明： 滤波；最后使用传统的模数(A/D)转换器以频率 1)相关性的作用是十分明显的，相关性越小则 采样.尽管输入信号是模拟量，但该系统得到的观测 需要的采样数就越少， 值y依然是离散形式的 2)每一个观测值中都包含着原始信号的一部 分信息，可以通过任意M个观测值的组合获得信号 y[m]= v.(r)p.(r)h(mg-)dr. 的全部信息 (8) 3)可以通过解一个凸优化问题，从任意M个观 测值中重建原始信号∫，这个重建过程是独立于信 榄拟 号的，不需要知道任何与原始信号有关的先验知识， 滤波器) 只要原始信号足够稀疏就可以得到精确的结果。 量化器 p0{-1,lH 4)“以极大的概率取得精确解”暗示了例外情 况存在的可能性，某些经过人为精巧安排的不遵守 图3A/I转换 此定理的信号是可能存在的，但是它们几乎不可能 Fig.3 Schematic diagram of A/I conversion 在自然情况下出现 为了与离散形式的CS统一起来，依然希望y是 2.2对可压缩信号的重建 由f(t)通过一个M×N压缩感知矩阵⊙来得到.根 在前面介绍的CS技术都是针对严格稀疏的信 据式(8)可以如此构造压缩感知矩阵，令其第m行、 号的，但是实际应用中遇到的信号往往不是严格稀 第n列的元素0m,n为 疏的，而是可压缩的.那么自然要问这样的问题：CS 0-v.(r)p.(r)h(mg-r)dr. 对于可压缩信号的重建性能如何？显然精确重建是 显然压缩感知矩阵⊙仍然由两部分组成：稀疏分解 不可能的；但是考虑到可压缩信号能够由严格稀疏 矩阵亚将模拟信号分解为频域系数；观测矩阵Φ 信号近似，那么重建信号也应该是精确解的近似.假 从模拟信号中提取离散的观测值.如此一来，模拟信 设对于任意向量x∈R“,保留其中最大的S个元素 号的CS就被纳入到离散CS的轨道中来了，离散形 并将其余置0得到xs,下面将以xs为标准来衡量可 式中的理论可以简单地推广到模拟信号的处理当 压缩信号的重建效果， 中，以实现对更加复杂的模拟信号进行灵活的处 定理20假设6s<2-1,那式(7)的解x满足： 理23241 Ix-xI2≤Cx-‖山 2压缩感知的性能 √3 lx-x‖1≤C川x-x3‖… 2.1压缩能力 观测值向量y作为最终的编码结果，其长度与 式中：C为常数.如果x是可压缩的并满足指数规律 观测矩阵Φ的某一维长度M相关，M的大小显然 xl(m≤R×n,即x属于一个半径为R的弱l。球 不可能是任意的，它必然有一个下限为了找到这个 时，根据经典计算可知：
.26 智能系统学报 第7卷 lx-xs‖2≤C2XRxS2-n “压缩感知数码相机”[24]更是将这一新兴技术的 ‖x-xs‖1≤C1xRxS-p 实际价值与发展潜力展露无遗，为CI的实际应用奠 通过定理2可知，当x为严格S-稀疏的，即x= 定了基础.在此基础上，W.Chan等在文献[27]中讨 x3,那么重建结果是精确的.当x为非稀疏信号时， 论了相似的问题，A.Heidari等也分析了2-D相机系 CS的效果将和预先知道x的S个最大元素的大小 统的设计问题1.另外L.Gan在文献[29]和文献 与位置，并用xs近似的效果是一样好的， [30]中分别提出了分块压缩成像方法和快速算法； 2.3鲁棒性 S.Mun等也提出了一种基于方向性变换的分块压 在实际应用中噪声是不可避免的，一般很难获 缩感知方法31]：关于彩色图像的内容也在文献[32] 得没有误差的观测值y,如果用e表示误差且其大 中有专门的论述；除静态图像以外，视频的编码与重 小满足‖e‖2≤B,那么压缩感知的模型变为 建等相关问题也得到了关注3)，V.Cevher等在文 y =Ox +e. 献[36]中提出了一种用于视频监控系统中的背景 由于引入了误差项e,观测值y变得不再准确，以此 减除方法，实验证明该方法在提取视频中的动态物 为基础的信号重建过程也将会随之出现偏差.如果 体的轮廓方面效果理想 CS技术想在实际应用领域中发挥作用的话，那么它 3.2系统原理 必须具有鲁棒性，即小的误差干扰只对信号重建产 压缩成像系统最具代表性的设计就是文献[12 生小的影响.将重建的条件放宽为 14]的单像素“压缩感知数码相机”，本文以该系统 x=min‖x"‖，满足‖⊙x”-y‖2≤e.(9) 为例介绍压缩成像技术的实现原理，其系统原理如 式(9)依然是一个凸优化问题，可以归纳为二次锥 图4所示.系统主要由2个镜头：1个数字微镜系统 规划问题(second order cone program,SOCP),它与 (digital micromirro device,DMD)和1个感光器件 式(7)的区别在于仅要求把⊙所-y控制在噪声水平 (单像素)组成.要对某一场景成像，首先将其人射 内，也可以得到惟一的解。 光场通过第1个镜头汇聚并由N个小镜面组成的 定理3161假设82s<2-1,那么式(7)的解x DMD反射，然后第2个镜头接收反射光并将其汇聚 满足 到感光器件上.在这个系统中，DMD起到了测量矩 x-xl2≤C×8+C,×E-山 阵的作用，等效地从N×N沃尔什矩阵中（将-1用 √S 0代替)随机抽取M行（忽略全为1的第1行）组成 式中：C1、C2为常数，并且值很小，例如62s=1/4时 测量矩阵.DMD中的每一个小镜面之间的动作相互 C1≤5.5，C2≤6 独立，并受一个随机数生成器(random number gen 由定理3可知，信号重建的误差是有限的，它受 erator,RNG)控制.为了生成测量向量g,RNG对 到2个误差项之和的限制，第1个误差项是由噪声 DMD中每一个小镜面发出随机的0或1的指令，控 引入的，第2个误差项是在无噪声干扰环境下系统 制小镜面朝向（指令1）或不朝向（指令0）感光器 自身的误差，从另一个角度上来讲，这也说明在噪声 件，这样每次测量就等效为将场景中潜在的像素按 ‖e‖2≤e的干扰下没有性能可以超过式(9)的重 列序排成一维，然后与测量向量做内积.如果用I表 建算法了 示成像场景对应的数字图像，∫表示I按列序组织成 一列形成的向量，则感光器件上的电压就等于测量 3 压缩成像的发展及系统原理 值y=〈9)，将这一过程重复M次即可以得到全 3.1发展状况 部的测量值向量y=对在获得了一系列测量值之 作为一种全局采样方式，CS采样过程需要同时 后，可以根据CS重建原理选择适当的优化算法从 操作信号的全部采样值.由于潜在像素时间上的同 这些观测值中重建出原始图像。 时性，自然图像的成像恰好符合这一要求.将CS应 这种相机的成像效果如图5所示，图5是对同 用于成像系统可以显著节省传感器的数量，避免了 一场景下不同方式的成像效果进行比较的结果，图 “先采样再压缩”带来的资源浪费.J.Haupt等在文 5(a)为目标图像，即用65536个像素按常规方式成 献[25]中探讨了压缩成像相对于传统成像的优势； 像的效果；图5(b)为11000个测量值重建为65536 在文献[26]中J.Romberg设计了一种用CS描述高 个像素的效果（测量值是重建像素的16.78%）；图 频细节配合低频系数的成像方式，取得了不错的实 5(c)为利用相当于重建像素1.98%，即1300个测 验效果；而M.Duarte等设计并实现的一种单像素 量值成像的效果
第1期 赵春晖，等：压缩感知理论及其在成像技术中的应用 ·27 场景 感光器件 (单像素) PD A/D 发射机 DMD 接收机 随机模式 DMD阵列 图像重建 DSP 图4压缩感知相机原理 Fig.4 Compressive sensing camera block diagram RR (a)常规成像效果 h)11000个测量值效果 (c)1300个测量值效果 图5压缩感知相机的成像效果 Fig.5 Effect of compressive sensing camera 4 首先要确定一组将图像表示为稀疏形式的基.只有 压缩成像的关键问题 确定了合适的基来表示图像，才能保证在足够稀疏 在整个CS体系中，需要解决的关键问题可以 的变换域内进行观测，进而保证重建的精度(TV最 被划分成3个方面： 小化算法除外). 1)信号的稀疏表示问题，即如何找到一组正交 将信号进行稀疏分解的方法有很多，其中最简 基（或者紧框架）将信号表示成简洁的形式； 单的方法就是使用基本的谐波分析中常用的变换方 2)观测矩阵的选择问题，即如何选择一个平稳 法.以DCT变换为基础的静态图像压缩标准JPEG 的且与稀疏变换矩阵不相关的观测矩阵，以保证稀 和以小波变换为基础的新一代静态图像压缩标准 疏向量在降维观测时重要信息不遭到破坏； JPEG-2000就是其中最典型的应用371.在文献[38] 3)重建算法的设计问题，即如何设计一个快速 中，G.Peyre把稀疏变换基的条件做了进一步的扩 有效的重构算法，从少量的观测值中准确地恢复出 展，使其从正交基扩充到了由多个正交基构成的正 原始信号。 交基字典.除此之外，通过设计一定的算法来计算信 以CS理论为基础的CI技术可以看成是CS针 号分解的稀疏字典也是可行的，例如FOCUSS算 对图像信号进行处理的特殊情况，所以CI技术中的 法39]、K-SVD算法[o)、NMF算法[和MoTIF算 关键问题实际上与CS是一致的，其中的区别仅在 法[21等. 于CI更加注重利用和配合图像的特殊属性.本节将 因为完备的正交基可以惟一将信号表示成简单 参照CS理论概述CI的相关问题. 的形式，所以目前在CS理论的研究中通常使用完 4.1稀疏分解 备的正交基.然而对于图像、声音等具有复杂特征的 找到信号最佳的稀疏域就可以得到信号最简洁 信号而言，仅用固定的正交基不足以将其特征完整 的表达形式，这是CS理论应用的基础和前提.CI技 地表征出来，因此此类信号在正交基下的分解往往 术处理的是图像信号，其中只有某些二值场景成像 不够稀疏.基于超完备冗余字典的信号稀疏表示是 能够满足时域严格稀疏的性质，而大部分图像都是 近年来又一个新的研究方向和热点，其基本思想是 相对于某个变换域的可压缩信号.为了获得观测值， 用称之为字典的超完备的冗余函数系统取代基函
28 智能系统学报 第7卷 数，字典的选择尽可能好地符合被逼近信号的结构， 重建的效果 其构成可以没有任何限制，字典中的元素被称为原 59 子.从字典中找到具有最佳线性组合的若干项原子 T(·) 16 来表示一个信号，称作信号的稀疏逼近或高度非线 性逼近4.对灵长目动物的视觉研究表明，视觉 皮层对复杂刺激的表达采用稀疏表示的原则，视觉 区细胞对感受区细胞发放输出的信息的特征表达存 4 在“超定”性质，它的编码表达空间的维数大于其输 入空间的维数「].这说明使用超完备稀疏表示是图 像稀疏表达的一种有效策略.超完备信号的稀疏表 234567N90L 示方法始于1993年，S.Mallat等在文献[46]中首次 提出了应用超完备冗余字典对信号进行稀疏分解的 思想，并引入了匹配追踪(marching pursuit,MP)算 X T 法，文中论述了超完备冗余字典对信号表示的必要 图62D-DCT等效矩阵原理 性并强调了超完备字典的构成应符合信号本身所固 Fig.6 The mechanism schematic diagram of 2D-DCT 有的特性以实现MP算法的自适应分解.之后D. equivalent matrix Donoho等又于1999年提出了基追踪(basis pursuit, 4.2观测矩阵的构造 BP)算法1，并在2001年发表的另一篇重要文章 在CS理论中直接构造一个满足RP条件的压 中给出了基于BP算法的稀疏表示具有惟一解的边 缩感知矩阵⊙是很难实现的.由于稀疏分解矩阵亚 界条件，同时提出了字典的互不相干性的概念[， 是固定的，要使得⊙=Φ业满足P条件，因此可以 显然，采用超完备冗余字典可以更加有效地获取信 通过设计观测矩阵Φ来解决.构建一个观测矩阵Φ 号的最稀疏形式，从而有效地减少CI的观测值数 使得⊙=D业满足RP条件，需要对N长向量y的S 量，使重建算法的效率更高.但是由于目前基于超完 个非零元素的每种可能组合验证式(7)，这是相当 备冗余字典的信号稀疏表示理论还不够成熟，超完 复杂的.然而，若简单地将Φ当作随机矩阵选取，则 备字典中的原子数量一般情况下都很大，算法所涉 能够以极大的概率同时满足P条件和非相关性的 及的计算十分繁重，因此会给其实际应用于CI带来 要求.一些常见的满足要求的观测矩阵如下： 定的困难 1)高斯观测矩阵：构造M×W观测矩阵Φ的每 上述不同的稀疏分解手段都可以看成是对图像 一个元素都独立地满足均值为0、方差为1/M的高 所进行的一种变换，但需要特别注意的是，CS理论 斯分布N(0,1/M).高斯观测矩阵有2个优越的性 发展自一维信号，目前尚没有研究出处理二维及以 质：a)高斯观测矩阵Φ几乎与所有的稀疏信号都不 上信号的有效算法，无论采用何种变换方法处理高 相关与之等价地，高斯观测矩阵Φ与亚=I不相 维信号均需要做“降维”处理.对于二维图像来说， 关，当M≥C×S×log(N/S)时（其中C为一个很小 “降维”可以是将图像按照列序排成一维向量.然而 的常数)，压缩感知矩阵⊙==Φ以很高的概率 在“降维”过程中，原本相邻的像素会被人为地分 满足RP条件.b)当采用高斯观测矩阵Φ时，无论 开，使得构成视觉信息的结构受到了破坏.图像的二 正交矩阵业如何选择，观测矩阵⊙=Φ业都将是独 维变换系数中包含着结构信息，但是二维变换对应 立同分布(independent and identically distributed, 的矩阵在计算中会出现维数不匹配的情况.目前通 D)的高斯矩阵，因此必将以极高的概率满足RP. 常根据一维变换构造稀疏分解矩阵，在重建中图像 2)一致球面观测矩阵051：矩阵的列在球S- 被等效为一维数据，结构信息难以准确重建.文献 上是独立同分布且随机一致的，并且当观测次数为 49]提出了构造等效矩阵来解决图像重建问题的 M=O(Kn(N))时，可以在极大的概率下准确重建 思想，构造等效矩阵所遵循的原则是，构造出的矩阵 信号 与“降维”后的图像相乘得到的系数均来自未“降 3)二值随机观测矩阵)：M×N观测矩阵Φ的 维”图像通过相应二维变换得到的系数矩阵，其原 每一个元素均独立地服从对称伯努利分布 理如图6所示.文中通过构造2D-DCT等效矩阵将图 (P(Φ，=±√M)=1/2).研究表明当M≥C×S× 像DCT系数中包含的结构信息引入到图像的重建 ln(N/M)时，准确重构信号的概率极大，并且重建的 中，令CI技术可以在使用快速贪婪算法的同时保持 速度很快， 图像的结构信息，且不增加软硬件成本，改善了图像 4)部分傅里叶观测矩阵752]：从N×N维傅里
第1期 赵春晖，等：压缩感知理论及其在成像技术中的应用 29 叶变换矩阵中随机地选择M行构成Φ，并对Φ的 到目前为止出现的主要重构算法可以分为以下3 每一列进行归一化.部分傅里叶矩阵的一个突出优 类n556 点是可以利用快速傅里叶变换进行快速计算，大大 1)凸松弛法.这类方法通过将非凸优化问题转 降低了采样系统的复杂性，然而由于其通常只与时 化为凸优化问题求解，找到信号的逼近，代表算法包 域稀疏的信号不相关，所以应用范围受到了限制. 括基追踪算法(basis pursuit,BP)[]、内点法(interi- 5)局部Hadamard观测矩阵o):从W维矩阵中 or-point method)I]、梯度投影法(gradient projec- 随机选择M行得到.如果用B表示分块的大小， tion)s】、迭代阈值法(iterative thresholding algo- 那么当M≥S√W/Bn(W)2时，置乱块Hadamard矩 rithm)[s]和迭代硬阈值法(ierative hard thresholding 阵可以以极大概率精确重构信号. algorithm,IHT)【6o] 6)Toeplitz观测矩阵和循环矩阵[g]:当M≥C× 2)贪婪算法.这类方法通过每次迭代时选择一 M×ln(N/M)时，这2种矩阵使观测矩阵以很大概 个局部最优解来逐步逼近原始信号.代表算法包括 率满足P条件，并且可以直接应用快速傅里叶变 匹配追踪算法(maching pursuit,MP)[o]、正交匹配 换得到快速的重构算法，能够明显降低高维问题的 追踪算法(orthogonal matching pursuit,OMP)[6]、分 计算和存储复杂度，因而对高维问题特别有效， 段正交匹配追踪算法(stagewise orthogonal matching 在性能表现方面，Y.Tsaig等对一致球面观测矩 pursuit,SOMP)[、正则化正交匹配追踪算法(reg 阵、二值随机观测矩阵、局部Hadamard观测矩阵以 ularized orthogonal matching pursuit,ROMP)3 及部分傅里叶观测矩阵的性能进行了比较，实验表 缩感知匹配追踪算法(compressive sampling matching 明使用这几类矩阵作为观测矩阵时，CS重建信号的 pursuit,CoSaMP)[s5] 误差都比较小，并且随着观测样本数量的增加误差 3)组合算法.这类方法要求对信号进行高度结 将会进一步减小9)，该结论对于现有已被验证的所 构化地采样，通过分组测试快速重建.代表算法包括 傅里叶采样[6]、链式追踪s]和HHS(heavy hitters 有观测矩阵都是成立的.文献[54]也通过实验对比 on steroids)追踪[]等 了常用观测矩阵的性能优劣程度，在信号稀疏度和 CS观测数均相同的条件下，局部Hadamard观测矩 上述3类算法各有其固有的优缺点，其中凸松 阵的性能优于其他观测矩阵，且稀疏度越大效果越 弛法在重建时需要的观测值最少，精度最高，但是计 算复杂度也最高；组合算法的运行效率最高，但是其 明显，其次是Toeplitz观测矩阵，而随机高斯观测矩 需要的观测值数量最多：贪婪算法则是在运行效率 阵、二值随机观测矩阵在各种稀疏度下重建效果皆 对观测值的需求和重建精度方面都取得了折衷的效 ·致，重建效果最差的是部分傅里叶观侧矩阵 果.目前CS应用中使用较多的主要是前2类算 对于CI技术来说，最理想的观测矩阵是只包含 法1 0和1的二值矩阵，而且其中0与1的比例越高观 由于图像的特殊性，其重建可以采用TV最小 测效率就越高，这也同样适用于CS的其他应用领 化方法「]对像素间梯度进行优化，这种算法的优势 域。一方面来说，二值矩阵具有的状态最少，因而最 是在重建过程中不必提供稀疏分解矩阵，并且可以 容易实现；另一方面来说，获得观测值后一般要通过 求解出精确结果；其缺点在于计算复杂，求解效率非 量化才能进行编码操作，如果采用诸如高斯观测矩 常低，在处理尺寸较大的图像时可能需要若干天的 阵、一致球面观测矩阵或部分傅里叶观测矩阵等作 时间.令‖I‖v表示二维图像I的全变差，若图像 为观测手段的话，那么量化过程会导致更大的信息 的每一个像素为I(t1,t2),0≤t,t2≤N-1,则 丢失并直接影响图像的重建效果.因此如何构造满 足RP并且O、1比例高的二值观测矩阵将是CI技 I1lw=∑√D1(1,2)2+1D2l(4,2) 术今后发展中的热门问题之一 式中：D为有限差分， 4.3重建算法 D1I(t1,2)=I(61,2)-I(t1-1,2), 设计稳定有效的重建算法是实现CS的关键问 D2I(t1,2）=I(t1,2)-I(61,2-1). 题之一，也是当前CS研究中最热门的方向之一.由 通过求解式(10)即可精确重建原始图像I. 于从观测值中重建出原始信号的方式不是惟一的， '=min‖I‖w满足=y. (10) 因此构造重建算法的手段也多种多样.目前已有大 5 量的文献从不同的角度设计出了许多行之有效的方 结束语 案来解决稀疏信号的重建问题，这些算法在求解精 CS理论从出现至今短短的数年内已经得到了 度、运行效率和适用范围都不各相同，但归纳起来， 长足的发展，新的理论层出不穷；而CI作为CS理论
·30 智能系统学报 第7卷 应用于实际的一个典型技术在近年来也得到了极大 [12]TAKHAR D,LASKA J N,WAKIN M B,et al.A new 的发展.本文作为一篇综述性的文献，笔者在撰写期 compressive imaging camera architecture using optical-do- 间深刻感受到该领域内研究进展之神速，许多并行 main compression[C]//Proceedings of Computational Ima- 的理论难以充分涵盖，对于无法尽述之处深感遗憾， ging IV at SPIE Electronic Imaging.San Jose,USA, 2006:606509. CS是一种利用数学计算来减少前端传感器件， [13]WAKIN M B,LASKA J N,DUARTE M F,et al.An ar- 解放信号获取能力的技术.CI系统可以显著节省感 chitecture for compressive imaging[C]//IEEE Interation- 光器件的数量，避免了传统成像方式带来的资源浪 al Conference on Image Processing.Atlanta,USA,2006: 费.该技术在降低成像成本、优化成像方式等方面拥 1273-1276. 有巨大的发展潜力，在医学成像、空间探测、非可见 [14]DUARTE M F,DAVENPORT M A.TAKHAR D,et al. 光成像等领域具有广阔的应用前景.随着此项技术 Single-pixel imaging via compressive sampling[J].IEEE 研究的深人，人们将对图像及其采集方式之间的深 Signal Processing Magazine,2008,25(2):83-91. 层次的联系形成更加深刻的认识，相信在不久的将 [15 ]DEVORE R.Nonlinear approximation[J].Acta Numeri- 来更加行之有效的图像获取框架将在此理论基础上 ca,1998,7:51-150. [16]DONOHO D,VETTERLI M,DEVORE R,et al.Data 被建立起来。 compression and harmonic analysis J].IEEE Transac- 参考文献： tions on Information Theory,1998,44(6):2435-2476. [17]石光明，刘丹华，高大化，等.压缩感知理论及其研究进 [1]CANDES E J.Compressive sampling [C]//International 展[J].电子学报，2009,37(5)：1071-1081. Congress of Mathematics.Madrid,Spain,2006,3:1433- SHI Guangming,LIU Danhua,GAO Dahua,et al.Ad- 1452. vances in theory and application of compressed sensing [2]BARANIUK R G.Compressive sensing[J].IEEE Signal [J].Acta Electronica Sinica,2009,37(5):1071-1081. Processing Magazine,2007,24(4):118-121. [18]BOYD S,VANDENBERGHE L.Convex optimization[M]. [3]CANDES E J,WAKIN M B.An introduction to compres- Cambridge,USA:Cambridge University Press,2004. sive sampling J].IEEE Signal Processing Magazine, [19]CHEN S,DONOHO D,SAUNDERS M.Atomic decompo- 2008,25(2):21-30. sition by basis pursuit[J].SIAM Journal of Scientific [4]CANDES E J,ROMBERG J,TAO T.Robust uncertainty Computing,1998,20(1):3361. principles:exact signal reconstruction from highly incom- [20]KIROLOS S,LASKA J N,WAKIN M B,et al.Analog-to- plete frequency information[J].IEEE Transactions on In- information conversion via random demodulation [C]/ formation Theory,2006,52(2):489-509. IEEE Dallas Circuits and Systems Workshop (DCAS)on [5]DONOHO D.Compressed sensing[J].IEEE Transactions Design,Applications,Integration and Software.Dallas, on Information Theory,2006,52(4):1289-1306. USA,2006:71-74. [6]CANDES E J,TAO T.Near optimal signal recovery from [21]LASKA J N,KIROLOS S,MASSOUD Y,et al.Random random projections:universal encoding strategies?[J]. sampling for analog-to-information conversion of wideband IEEE Transactions on Information Theory,2006,52 (12): signals[C]//IEEE Dallas Circuits and Systems Workshop 5406-5425. (DCAS)on Design,Applications,Integration and Soft- [7]CANDES E J,ROMBERG J,TAO T.Stable signal recover- ware.Dallas,USA,2006:119-122. y from incomplete and inaccurate measurements[J].Com- [22]LASKA J N,KIROLOS S,DUARTE M F,et al.Theory munications on Pure and Applied Mathematics,2006,59 and implementation of an analog-to-information converter u- (8):1207-1223. sing random demodulation[C]//IEEE Interational Sym- [8]CANDES E J,TAO T.Decoding by linear programming posium on Circuits and Systems (ISCAS).New Orleans, [J].IEEE Transactions on Information Theory,2005,51 USA,2007:1959-1962. (12)：42034215. [23]MISHALI M,ELDAR Y C.Blind multi-band signal recon- [9]TSAIG Y,DONOHO D.Extensions of compressed sensing struction:compressed sensing for analog signals[].IEEE [J].Signal Processing,2006,86(3):549-571. Transactions on Signal Processing,2009,57(30):993- [10]CANDES E J,ROMBERG J.Quantitative robust uncer- 1009. tainty principles and optimally sparse decompositions[J]. [24]MISHALI M,ELDAR Y C.From theory to practice:sub- Foundations of Computational Mathematics,2006,6(2): Nyquist sampling of sparse wideband analog signals[J]. 227-254. IEEE Journal of Selected Topics on Signal Processing, [11]CANDES E J,ROMBERG J.Sparsity and incoherence in 2010,4(2):375-391. compressive sampling[J].Inverse Problems,2007,23 [25 ]HAUPT J,NOWAK R.Compressive sampling vs.conven- (3):969985. tional imaging[C]//IEEE International Conference on Im-