数字视频 文章编号 ：１００２－８６９２（２００8）12-0016-03 压缩感知理论简介 * 综述 · · 华南理工大学 电子与信息学院 广东 广州 ， （1. 喻玲娟 1， 510640； 2. 谢晓春 2，3 赣南师范学院 物理与电子信息学院 江西 赣州 ， 341000； 中国科学院空间科学与应用研究中心 北京 ， 100190） 3. 摘 要 【 】 压缩感知 （CS） 理论是在已知信号具有稀疏性或可压缩性的条件下 对信号数据进行采集 编解码的新理论 主要阐述了 。 、 ， 理论框架以及信号稀疏表示 编解码模型 ， 并举例说明基于压缩感知理论的编解码理论在一维信号 二维图像处理上的应用 、 。 CS 【 【 关键词 】 压缩感知 稀疏表示 ； ； 中图分类号 】 TN919.81 解码 ； ； 受限等距特性 文献标识码 【 】 A 、CS 编码 Brief Introduction of Compressed Sensing Theory YU Ling-juan1， XIE Xiao-chun2,3 （1.School of Electronic and Information Engineering, South China University of Teconology, Guangzhou 510640, China ; 2. School of Physics and Electronic Information, Gannan Normal University, Jiangxi Ganzhou 341000, China ; 3. Center for Space Science and Applied Research, Chinese Academy of Sciences, Beijing 100190, China ） 【Abstract】 Compressed Sensing(CS) theory is a novel data collection and coding theory under the condition that signal is sparse or compressible. In this paper, the CS framework, CS coding model are introduced, after which the application of CS theory in one-dimensional signal and two-dimension image are illustrated. 【Key words】 compressed sensing; sparse presentation; encoding; decoding; restricted isometry property 引言 1 得到增强 过去的几十年间 传感系统获取数据的能力不断地 而传统的 采样定理要求信号的采样率不得低于信号带宽 需要处理的数据量也不断增 多 ， ， ， 、 ， ， 2 。 2004 Donoho （Compressed Sensing，CS） 这无疑给信号处理的能力提出了更高的要求 处理方法成为一种必然 等人提出的压缩感知 Nyquist 倍 的 也给相应的硬件设备带来了极大的挑战 。 采集 年 ， 寻找新的数据 由 与 理 Candes 论是一个充分利用信号稀疏性或可压缩性的全新信号 当信号具有稀疏性或 采集 可压缩性时 通过采集少量的信号投影值就可实现信号 理论的提出是建立在已有的盲源 的准确或近似重构 分离和稀疏分解理论基础上的 理论提 。 通过测量编码值实现信号 供了在未知源信号的情况下 重构的思路 解码 重构所用 稀疏分解中的具体算法已直接被 编解码理论[1-2]。 盲源分离为 该理论表明 。 CS CS CS ， ， ， ； 、 。 理论框架 2 CS CS 理论是编解码思想的一个重要突破 编解码过程如图 所示 、 再对所有采样值进行变换 采集 样 度和位置进行编码 1 ， ： ， ， 。 传统的信号 编码端先对信号进 行采 并将其中 重要系数的幅 信 ； 最后将编码值进行存储或传输 、 ， 反变换后得到恢复信号 接收的信号经解压 这种传统的编解码方法存 由于信号的采样速率不得低于信号带 这使得硬件系统面临着很大的采样速率的压 大量变换计算得到的小系数 号的解码过程仅仅是编码的逆过程 缩 在两个缺陷 宽的 力 ； 2） 被丢弃 倍 在压缩编码过程中 造成了数据计算和内存资源的浪费 ： 1） 2 ， ， 。 。 ， 编 码 端 信号 X 采样 变换 、 压缩编码 Y 解 码 端 接收数据 Y 解压缩 反变换 、 恢复信号 X赞 图 1 传统编解码理论的框图 CS 理论的信号编解码框架和传统的框架大不一样 所示 理论对信号的采样 、 ， ， ， 2 而是从高维到低维的投影值 。 CS 利用信号的稀疏性 如图 一个步骤 以远低于 的速率对信号进行非自适应的测量编码 号本身 个 测 量 值 是 传 统 理 论 下 的 每 个 样 本 信 号 的 组 合 函 数 即 一 个 测 量 值 已 经 包 含 了 所 有 样 本 信 号 的 编 码 端 X 接收数据 稀疏信号 解 码 端 基于 图 ， ， Y 2 CS ， 压缩编码发生在同 采样率 Nyquist 测量值并非信 每 从数学角度看 。 ， 测量编码 Y 恢复信号 解码重构 X赞 理论的编解码框图 江西省教育厅青年科学基金项目 * （GJJ09581） 电视技术 16 年第 ２００8 卷第 期 总第 （ 12 32 322 期 ） 

。 解码过程不是编码的简单逆过程 而是在盲 少量信息 利用信号稀疏分解中已有的重 源分离中的求逆思想下 构方法在概率意义上实现信号的精确重构或者一定误差 下的近似重构 [1]， 解码所需测量值的数目远小于传统 理 论下的样本数 。 ， ， 信号的稀疏表示 3 CS 由于 理论的前提条件是信号具有稀疏性或可压 的离散实值信 能够 由信号理论可知 只考虑长度为 为使模型简单化 ， 记为 N ， x（n），n∈[1，2，…，N]。 x 缩性 号 x， 用一组基 T Ψ =[ψ1， ψ2，… ，ψm，… ，ψM] 的线性组合表示 其中 （ Ψ T代表 Ψ 的转置 则 ）， N x= ΣΨkαk=Ψα k=1 （1） 多数情况下信号无法满足严格稀疏的要求 与 式中 当信号 于零的系数 ：αk=，α 在某个基 时 x Ψ 称 是 N×1 x 上仅有 矩阵 是 ，Ψ N×N 个非零系数 矩阵 。 或远大 K垲N x 为信号 的稀疏基 。 （ ）αk ， Ψ 信号在稀疏基上只有 ， K 个非零系数属于严格稀疏 但 即信号的变换系数经排序后可以指数 信号也是可以近似稀疏表示 使得信号的稀疏系数个数尽 而且有利于 正 常用的稀疏基有 Ψ， ， ， ： ， ， 的情况 仍具有可压缩性 级进行衰减趋近于零时 合理地选择稀疏基 的 可能少 ， 减少存储 弦基 余 。 （ ） 、 传输信号所占用的资源 小波基 基以及 、 测量编码的模型 、chirplet 。 不仅有利于提高采集信号的速度 curvelet 基等 。 4 CS 在 本 身 x ， CS φ2， …，φm，…，φM] 阵形式为 编码测量模型中 并不是直接测量稀疏信号 ， x 而 是 将 信 号 投 影 到 一 组 测 量 向 量 而得到测量值 上 ， ym=。 Φ＝[φ1， 写成矩 式中 阵 。 式中 y=Φx 是 ：x 将式 矩阵 ，y N×1 代入 （1） （2）， 矩阵 是 ，Φ M×1 M×N 是 有 （2） 的测量矩 y=Φx=ΦΨα=Θα 是 矩阵 ：Θ=ΦΨ M×N 由于测量值维数 的逆问题是一个病态问题 M 。 远远小于信号维数 N， 所以无法直接从 （3） 求解式 （2） 个测量值中解出信号 即仅有 个非零系数 疏分解理论中已有的稀疏分解算法 而由于式 而且 x。 K ， ， K0。 RIP 满足不相关性的要求[1，3-4]。 Ψ 准则的一种等价的情况是测量矩阵 实际测量中稀疏基 可能会因信号的不同而改变 Ψ 。 Ψ 测量矩阵 对一维信号而言 都能满足和测量基 因此希望找到对任意的稀疏基 Φ 不相关 选取服从高斯分 Φ 布的基矢量能保证和任意稀疏基 不相关的概率很高 ， 类似的矩阵还有 有文献 对二维图像 提出了能快速计算随机扰动的部分傅立叶变换矩阵 [5]、 随机扰动的 Ψ 矩阵等[2]。 Bernouli ， ， Hadamard 矩阵[6]等 。 解码重构的模型 中的矩阵 满足 Θ RIP 准则时 ，CS （3） 理论能够 （3） 将稀疏度为 通过对式 式 K 正确地恢复出来[1-2]。 求解式 （1） （3） 的最优化问题 的逆问题先求解稀疏系数 T α=Ψ x， 从 的信号 解码的最直接方法是通过 维的测量投影值 M x 后代入 中 范数下 y l0 a ， 。 s.t. 问题 ‖α‖l0 min 从而得到稀疏系数的估计 y=ΦΨα 由于 （5） 式的求解是个 而该最优化问题与信号的稀疏分解中的 所以有学者从信号稀疏分解的相关理论中寻 最小范数下在一定 那 表明 最小范数具有等价性 ，l1 可得到相同的解 NP-hard 十分类似 找更有效的求解途径 条件下和 么 最小范数下的最优化问题 式转化为 文献 （5） [7] l0 ， 。 ， 。 （5） l1 min ‖α‖l1 s.t. y=ΦΨα 最小范数下最优化问题又称为基追踪 a l1 内点法和梯度投影法 （BP）， 内点法速度慢 。 （6） 其常 但 但没有内 ， 为充分利用 ， 而梯度投影法速度快 二维图像的重构中 ， 可修正为整体部分 （Total Variation， 最小范数下的算法速度慢 新的快 （MP）[9]和正交匹配 如匹配追踪法 有效的算法还有迭代阈值法 [10]以 ， ： 用实现算法有 得到的结果十分准确 ； 点法得到的结果准确[8]。 图像的梯度结构 最小化法 ， 由于 TV） l1 速贪婪法被逐渐采用 ， 追踪法 此外 （OMP）[4]。 及各种改进算法 。 ， 。 理论的应用举例 6 CS 6.1 一维信号情况下的实验仿真 源信号是一维离散稀疏信号 ， 长度 N=256， 选余弦基 Ｎｏ．12 Vol.32 ２００8（Sum Ｎｏ．322 ） ＶＩＤＥＯ ＥＮＧＩＮＥＥＲＩＮＧ 17 

数字视频 在基于 ， 得到稀疏个数 编码端采用高斯测量矩阵 ， 仿真实验首先观察 为稀疏基 码框架中 法进行恢复重构 数量对信号重建效果的影响 K＝30。 由图 ， 。 。 理论的编解 解码的 CS 15.49 dB。 小结 7 解码端采用 ， 3 M CS 可知 ， 增加时 OMP 理论下测量值 当测量值的 信号 数量 成功恢复的概率同步 而且当样本数 增加 目 达 到 信 号 已 经 能 够 准 确 恢 可以 复 看出信号得到了准确 的解码重构 此时由图 M=110 时 4 。 ， 。 。 、 。 ， CS CS CS 理论框架 以及基于 编解码理论 笔者主要阐述了 通过对一维信号 理论的 二维图像进行编解码的 理论是一种能够使用少量测量值实 理论 编解码模型 仿真实验说明了 现信号准确恢复的数据采集 对处理大规模稀疏或可压缩数据具有十分重要的意义 所以该理论提出后在许多研究领域得到了关注 目前 ， 国外研究人员已开始将 医学图 理论用于压缩成像 、 雷达成像 作为国外 像 。 将有着更广 刚出现的新理论 泛的应用前景 理论的研究方兴未艾 CS 天文学 通信等领域 模数转换 由于 ，CS CS 。 。 ， ， 、 、 、 、 、 。 （a） 源信号 长度 ， N=256 （b） CS 解码重构得到 个稀疏系数 K=30 参考文献 [1] DONOHO D. Compressed sensing[J]. IEEE Trans. Information The- ory, 2006, 52(4): 1289-1306. [2] CANDES E. Compressive sampling[C]//Proceedings of the Interna- tional Congress of Mathematicians. Madrid, Spain: [s.n.], 2006:1433 - 1452. [3] CANDES E, ROMBERG J, TAO T. Robust uncertainty principles: Exact signal reconstruction from highly incomplete frequency informa- tion[J]. IEEE Trans. Information Theory, 2006, 52(4): 489-509. [4] TROPP J, GILBERT A C. Signal recovery from random measure- ments via orthogonal matching pursuit [J]. IEEE Trans. Information N=256 Theory, 2007, 53(12): 4655-4666. （c） CS 解码重构后信号 ， 解码重构稀疏系数 长度 、 4 源信号 解码重构信号图 图 二维图像情况下的实验仿真 源图像为 图 测量编码端采用分块 boat 理论的编解码框架中 256×256 的 ， 、 6.2 选小波基为稀疏基 。 块 （ 最小 解码端基于 ， 图像的测量样本数 TV M= 在传统的编解码理论 个大系数进行 仿 25 000 基于 CS 大小为 化的梯度投影法进行恢复重构 32×32）Hadamard ， 测量矩阵 其重构结果如图 。 对图像小波变换后保留其中的 5a 。 所示 25 000， 下 ， 编码 真结果表明 理论下的恢复图像 后进行解码 ， ， 反变换重建 所示 。 在编码端的测量值个数相同的情况下 其结果如图 5b ， 、 达到 PSNR 27.9 dB， ，CS 远远高于传统编 方式 （a） CS 图 5 CS 与传统编解码 boat 传统方式 （b） 图恢复效果比较 电视技术 18 年第 ２００8 卷第 期 总第 （ 12 32 322 期 ） [5] ZOU J, GILBERT A C, STRAUSS M J, et al. Theoretical and ex- perimental analysis of a randomized algorithm for sparse Fourier trans- form analysis[J]. Journal of Computational Physics, 2006, 211(2): 572 -595. [6] GAN Lu. Block compressed sensing of natural images[C]//Proceed- ings of the International Conference on Digital Signal Processing. [S.l.]: IEEE Press, 2007:403-406. [7] DONOHO D, TSAIG Y. Extensions of compressed sensing[J]. Signal Processing, 2006, 86(3): 533-548. [8] FIGUEIREDO M A T, NOWAK R D, WRIGHT S J. Gradient pro- jection for sparse reconstruction: application to compressed sensing and other inverse problems[J]. IEEE J-STSP,2007,1(4): 586-598. [9] TROP J A. Greed is good: algorithmic results for sparse approxi- mation[J]. IEEE Trans. Information Theory, 2004, 50(10):2231-2242. [10] FORNASIER M, RAUHUT H. Iterative thresholding algorithms[J]. Applied and Computational Harmonic Analysis, 2008, 25(2):187-208. 笕 作者简介 ： 喻玲娟 （1982－）， 谢晓春 责任编辑 ： （1975－）， 哈宏疆 硕士生 副教授 ， ， 研究方向为视频图像处理 ； 从事信号与信息处理方面的研究 。 收稿日期 ：2008-11-11