信号处理领域的利器-压缩感知

Original 江上中国保密协会科学技术分会 2022-10-02

随着信息量的不断增多，数据的采集、传输和存储设备正面临着日益严峻的压力；同时数据处理过程中也会伴随着信息泄露的风险，一部分数据的丢失都有可能威胁生命和财产的安全，而如今数据泄露已经屡见不鲜。因此在大数据时代，人们亟需寻找一种新的数据处理方式来降低信息处理过程中数据泄露风险，同时也释放内存、传感器等硬件设备的压力。

压缩感知理论是在这样的背景下产生的一种新兴的信号采集和编解码理论。该理论指出，不管是何种类型的信号，其在原始域或者某些变换域中，总是存在稀疏或者可压缩的表示，在传输过程中可用远低于传统奈奎斯特采样的线性投影值，实现对信号的准确或者高概率重建。

这一理论带来了信号采样理论的变革，对于信息安全也有重要的意义。学者将压缩感知应用至图像的加密与传输、信息的安全编码技术、信息的安全存储、无线传感器网络的数据采集之中，有很多的信息处理以及信息安全领域学者对压缩感知产生了较浓厚的研究兴趣。本文首先简单介绍压缩感知的诞生，然后扼要地介绍一下理论内容和一些应用方法，最后结合实际谈一谈目前一些比较成功的应用。

一

压缩感知的起源

“压缩感知”思想最早出现在一篇2000年左右的博士论文《Near-Optimal Signal Recovery From Random Projections》^[1]中。它的发现可以说是一次意外，当时加州理工学院教授Emmanuel Candès在研究名叫Shepp-Logan Phantom的图像，这种标准图像常被计算机科学家和工程师用来测试图像还原算法。检查的图像质量非常差，充满了噪声，他使用了L-1范数最小化的数学算法来去除噪声条纹，结果算法真的起了作用。这种算法是将一个NP难问题转化为一个凸优化问题，也将压缩感知的思想充分的体现：通过对信号不完备观测后通过优化算法来高概率还原信号（如图1所示）。“就像给出10位银行卡账号的前三位，我就能猜出后七位一样，并且，屡试不爽。”这就是压缩感知思想的开端。

图1 加入各种噪声后的图像还原图

后来，Candès与陶哲轩进行了交流，陶哲轩也开始思考这个问题，上述交流成为第一篇关于压缩感知论文的基础。另外一位奠基人是Donoho，他的一篇代表作《Compressed sensing》^[2]可以说是第一篇较为完整系统地阐述压缩感知原理以及推导的论文。

以上这些都是压缩感知的起源。

二

压缩感知理论内容以及获取和求解方法

压缩感知理论本身的含义为“通过对信号的高度不完备线性测量的高精确重建^[3]”，在该理论框架下，采样速率不再取决于信号的带宽，而在很大程度上取决于两个基本准则：稀疏性和非相关性。

压缩感知理论

主要包括三部分：

（1）信号的稀疏表示；

（2）设计测量矩阵，要在降低维数的同时保证原始信号x的信息损失最小；

（3）设计信号恢复算法，利用M个观测值无失真地恢复出长度为N的原始信号。

理论依据^[4]（主要由陶哲轩以及Candès推导和证明）

（1）设长度为N的信号X在某个正交基Ψ上是K-稀疏的（即含有k个非零值）；

（2）如果能找到一个与Ψ不相关（不相干）的观测基Φ；

（3）用观测基Φ观测原信号得到长度M的一维测量值M个观测值Y，K<M<<N；

（4）那么就可以利用各种优化方法从观测值Y中高概率恢复X。

压缩感知高概率重构信号方法流程如下图2所示：

图2 压缩感知信号恢复流程图

数学表达

压缩感知方程为：y=Φx=ΦΨs=Θs。（图3）

其中设x为长度为N的一维信号，稀疏度为k（即含有k个非零值），y为长度为M的一维测量值，Φ为观测矩阵，Ψ为稀疏基，s为稀疏系数。

然后将原来的测量矩阵Φ变换为Θ=ΦΨ，解出s的逼近值s’，则原信号x’ = Ψs’。

图3 压缩感知方程表示图

压缩感知获取和求解方法

压缩感知在应用时主要存在两个问题：

问题1：如何设计观测矩阵和信号的稀疏基从而获取到较好地观测值，求解方法如下表1：

表1 压缩感知获取策略表

问题2：如何有效地进行信号的重构即求出压缩感知方程中信号x的近似解。求解方法如下图4所示：

图4 压缩感知信号重构方法

三

压缩感知的应用领域和应用事例

压缩传感技术是压缩感知理论的应用之一。它是一种抽象的数学概念，最初用在图像处理之中，并逐步扩展应用到成像以外的许多领域。

要说到压缩感知较为成功的应用事例，首当其冲的那就是美国Rice大学发明的单像素相机^[14]。在整套系统中，被拍摄物体的图像经过镜头打在DMD（数字微镜芯片，Digital Micromirror Device）上，而经过DMD反射的图像又经过二次镜头聚焦在只有一个像素的传感器上，形成一个光信号。而在拍摄过程中，DMD上每个镜片反射的明暗矩阵以伪随机码的形式快速变换，每变化一次形成一个像素的信号。最后，经过对每次的信号和伪随机码综合进行计算，就得到了物体的影像。相机的模型与结构如下图5所示:

图5 单像素相机结构图

这款相机的关键部件是由德州仪器生产的数字微镜芯片（DMD），这款芯片主要用在数字背投或是投影机中。DMD由大量只有细菌大小的镜片组成，每块微型镜片都一面反光一面不反光，并可以快速翻转。

以下是其中几个应用：

• 图像信息安全。压缩感知具有同时采样、压缩和加密数据的良好特性,在图像安全方面引起了研究人员的广泛关注。目前融合压缩感知，学者将其应用到图像加密、图像哈希、数据隐藏和安全图像检索技术之中。例如一些基于压缩感知的水印方法被提出来，它们可以用于有损信道的数据传输，将有用信息隐蔽传输。

• 无线传感器网络（WSN）。由于传感器节点采集的数据有时空相关性，满足压缩感知理论应用中信号是稀疏性和可压缩性的条件，且传感器节点资源有限，汇聚节点性能强大，正好适用于压缩感知理论编码简单、解码复杂的特点，因此，基于压缩感知的 WSN 数据收集的技术得到逐步深入和广泛的研究和发展。比如Bajwa和Haupt等将压缩感知理论应用于无线传感器网络的数据采集^[15]。

• 磁共振成像（MRI）。在医学上，磁共振的工作原理是进行许多次（但次数仍是有限的）测量（基本上就是对人体图像进行离散拉东变换—或称为X光变换），再对数据进行加工来生成图像。由于测量次数必须很多，整个过程对患者来说太过漫长。压缩传感技术可以显著减少测量次数，加快成像（甚至有可能做到实时成像，也就是核磁共振的视频而非静态图像）。此外我们还可以以测量次数换图像质量，即用与原来一样的测量次数可以得到更高的图像分辨率。

• 线性安全编码。压缩传感技术提供了一个简单的方法，让多个传送者可以将其信号带纠错地合并传送，这样即使输出信号的一大部分丢失或毁坏，仍然可以恢复出原始信号。例如，可以用任意一种线性编码把1000比特信息编码进一个3000比特的流。那么，即使其中300位被（恶意）毁坏，原始信息也能完全无损失地完美重建。这是因为压缩传感技术可以把破坏动作本身看作一个稀疏的信号（只集中在3000比特中的300位）。

四

总结与展望

随着压缩感知理论及其技术的发展，信号处理的诸多领域发生了革命性变化，人们将其应用至信号处理的诸多领域之中，例如视频目标追踪^[16]、无线传感器网络之中的数据安全传输与采集^[17]、图像的加密算法^[¹⁸^]等等，这些技术也都可以用于信息安全之中。压缩感知已经成为信号处理领域的利器。由于有严格的数学证明以及推导，压缩感知具备较为深厚的理论基础。压缩感知的信号采集与重构算法因信号而异，因此拥有一个通用的压缩感知信号采集和重建策略将是非常有益的，这也将是所有研究者所追求的目标。

参考文献：

[1] E. J. Candès, Tao T . Near-Optimal Signal Recovery From Random Projections: Universal Encoding Strategies?[J]. IEEE Transactions on Information Theory, 2006, 52(12):5406-5425.

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

[3] E. J. Candès, Emmanuel & Romberg, Justin & Tao, Terence. Robust Uncertainty Principles:Exact Signal Frequency Information. [J] IEEE Transactions on Information Theory,2006, 52:489-509.

[4] E. J. Candès and M. B. Wakin,‘An introduction to compressive sampling’ IEEE Signal Process. Mag., vol. 25, no. 2, pp. 21–30, Mar. 2008.

[5] Laska J N , Kirolos S , Duarte M F , et al. Theory and Implementation of an Analog-to-Information Converter using Random Demodulation[C]// IEEE International Symposium on Circuits & Systems. IEEE, 1962.

[6] Mishali M , Eldar Y C . From Theory to Practice: Sub-Nyquist Sampling of Sparse Wideband Analog Signals[J]. IEEE Journal of Selected Topics in Signal Processing, 2010, 4(2):375-391.

[7] Yoo J , Becker S , Monge M , et al. Design and implementation of a fully integrated compressed-sensing signal acquisition system[C]// Acoustics, Speech and Signal Processing (ICASSP), 2012 IEEE International Conference on. IEEE, 2012.

[8] Tropp J A . Random Filters for Compressive Sampling[C]// Conference on Information Sciences & Systems. IEEE, 2006.

[9] Romberg, Justin. Compressive Sensing by Random Convolution[J]. SIAM Journal on Imaging Sciences, 2009, 2(4):1098-1128.

[10] Slavinsky J P , Laska J N , Davenport M A , et al. The compressive multiplexer for multi-channel compressive sensing[C]// IEEE International Conference on Acoustics. IEEE, 2011.

[11] Chen S S , Saunders D M A . Atomic Decomposition by Basis Pursuit[J]. SIAM Review, 2001, 43(1):129-159.

[12] S. G. Mallat and Z. Zhang, Matching pursuits with time-frequency dictionaries, [J]IEEE Trans. Signal Process, 1993.

[13] Y. C. Pati, R. Rezaiifar, and P. S. Krishnaprasad, Orthogonal matching pursuit: Recursive function approximation with applications to wavelet decomposition,[C] in Proc. 27th Asilomar Conf. Signals, Syst. Comput., vol. 1. Pacific Grove, CA, USA, 1993, pp. 40–44.

[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] Bajwa W U Z , Haupt J , Sayeed A M , et al. Compressive wireless sensing[C]// Proceedings of the Fifth International Conference on Information Processing in Sensor Networks, IPSN 2006, Nashville, Tennessee, USA, April 19-21, 2006. ACM, 2006.

[16] Liu J, Han C, Han F. A novel compressed sensing based track before detect algorithm for tracking multiple targets.[C]// International Conference on Information Fusion. 2013.

[17] 包明杰, 张浩然, 王妃. 压缩感知在无线传感网络的应用综述[J]. 微型机与应用, 2016, 35(14):16-18.

[18] 王海娇. 基于压缩感知的图像加密和检索方法的研究[D].

中国保密协会

科学技术分会

长按扫码关注我们

作者：江上

责编：蔡北平

往期精彩文章TOP5回顾