第12卷第3期 智能系统学报 Vol.12 No.3 2017年6月 CAAl Transactions on Intelligent Systems Jun.2017 D0I:10.11992/is.201606037 网络出版地址：http:/kns.cmki.ne/kcms/detail/23.1538.TP.20170404.1218.002.html 易于硬件实现的压缩感知观测矩阵的研究与构造 李霞丽，吴立成，樊艳明 (中央民族大学信息工程学院，北京100081) 摘要：在压缩感知过程中，观测矩阵在信号采样及重构中具有重要作用，构造易于硬件实现、结构简单且占内存较 小的观测矩阵是压缩感知理论能否实际应用的关键问题之一。提出两种易于硬件实现的观测矩阵，即顺序部分哈 达玛观测矩阵和循环伪随机观测矩阵，其中循环伪随机观测矩阵可分为循环m序列和循环g序列，并证明了伪随 机序列所构造的观测矩阵满足有限等距准则。为验证上述两种观测矩阵性能，对二维图像信号进行仿真，结果表 明，在较低的采样率下顺序部分哈达玛观测矩阵的重构效果最优，但是采样信号长度必须是2的k次幂：循环伪随机 观测矩阵的重构效果虽然弱于顺序部分哈达玛观测矩阵，但是明显优于高斯随机观测矩阵，克服了顺序部分哈达玛 矩阵观测信号必须是2的k次幂的限制。提出的两种观测矩阵易于硬件实现，避免了随机矩阵的不确定性且克服了 随机矩阵浪费存储资源的缺陷，具有良好的实际应用价值。 关键词：图像处理；机器视觉：压缩感知：采样及重构：观测矩阵：顺序部分哈达玛：循环伪随机矩阵：有限等距 中图分类号：TP391文献标志码：A文章编号：1673-4785(2017)03-0279-07 中文引用格式：李覆丽，吴立成，樊艳明.易于硬件实现的压缩感知观测矩阵的研究与构造[J].智能系统学报，2017,12(3)： 279-285. 英文引用格式：LI Xiali,WU Licheng,FAN Yanming..Study and construction of a compressed sensing measurement matrix that is easy to implement in hardware[J].CAAI transactions on intelligent systems,2017,12(3):279-285. Study and construction of a compressed sensing measurement matrix that is easy to implement in hardware LI Xiali,WU Licheng,FAN Yanming (School of Information Engineering,Minzu University of China,Beijing 100081,China) Abstract:In the compressed sensing process,the measurement matrix plays a significant role in signal sampling and reconstruction.Therefore,a measurement matrix that is simple in structure,has a small memory,and is easy to implement in hardware is the key to applying compressed sensing theory.Based on the partial Hadamard measurement matrix and a circulating pseudo-random sequence,this paper presents two measurement matrixes that are easy to implement in hardware,namely the sequence partial Hadamard measurement matrix and the recycled pseudo-random sequence measurement matrix.The latter consists of a recycled m sequence and a recycled gold sequence measurement matrix.This further proves that a measurement matrix constructed by a pseudo-random sequence complies with the RIP principle.To test the performance of the two measurement matrixes,a two- dimensional image signal was simulated.It was found that under a low sampling rate,the reconstruction of the sequence partial Hadamard measurement matrix is optimal provided that the length of the sampling signal is 2. Although reconstruction of the recycled pseudo-random sequence measurement matrix is inferior to the sequence partial Hadamard measurement matrix,it exceeds the Gaussian random measurement matrix,and also overcomes the sequence partial Hadamard measurement matrix's limitation of a 2 signal length.These two types of measurement matrix are easy to implement in hardware,and avoid the uncertainty and storage waste of a random matrix.Therefore,they are suitable for practical application. Keywords:image processing;machine vision;compressed sensing;sampling and reconstruction;measurement matrix;sequence partial Hadamard;sequence pseudo-random;restricted isometry property 压缩感知(compressed sensing,CS)[-)通过利 下，用随机采样获取信号的离散样本，然后通过非 用信号的稀疏特性，在远小于Nyquist采样率的条件 线性重建算法重建信号。由于压缩感知理论具有 “轻编码、重解码”的特点，压缩感知理论应用到低 收稿日期：2016-06-21.网络出版日期：2017-04-04. 功耗无线传输的硬件系统中是一个比较合理的选 基金项目：国家自然科学基金项目(51375504,61602539) 通信作者：吴立成.E-mail:wulicheng@tsinghua.edu.cn. 择。压缩感知主要解决的3个问题分别为信号的稀第 １２ 卷第 ３ 期 智 能 系 统 学 报 Ｖｏｌ．１２ №．３ ２０１７ 年 ６ 月 ＣＡＡＩ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｉｎｔｅｌｌｉｇｅｎｔ Ｓｙｓｔｅｍｓ Ｊｕｎ． ２０１７ ＤＯＩ：１０．１１９９２ ／ ｔｉｓ． ２０１６０６０３７ 网络出版地址：ｈｔｔｐ： ／ ／ ｋｎｓ．ｃｎｋｉ．ｎｅｔ ／ ｋｃｍｓ／ ｄｅｔａｉｌ ／ ２３．１５３８．ＴＰ．２０１７０４０４．１２１８．００２．ｈｔｍｌ 易于硬件实现的压缩感知观测矩阵的研究与构造 李霞丽， 吴立成， 樊艳明 （中央民族大学 信息工程学院， 北京 １０００８１） 摘 要：在压缩感知过程中，观测矩阵在信号采样及重构中具有重要作用，构造易于硬件实现、结构简单且占内存较 小的观测矩阵是压缩感知理论能否实际应用的关键问题之一。 提出两种易于硬件实现的观测矩阵，即顺序部分哈 达玛观测矩阵和循环伪随机观测矩阵，其中循环伪随机观测矩阵可分为循环 ｍ 序列和循环 ｇｏｌｄ 序列，并证明了伪随 机序列所构造的观测矩阵满足有限等距准则。 为验证上述两种观测矩阵性能，对二维图像信号进行仿真，结果表 明，在较低的采样率下顺序部分哈达玛观测矩阵的重构效果最优，但是采样信号长度必须是 ２ 的 ｋ 次幂；循环伪随机 观测矩阵的重构效果虽然弱于顺序部分哈达玛观测矩阵，但是明显优于高斯随机观测矩阵，克服了顺序部分哈达玛 矩阵观测信号必须是 ２ 的 ｋ 次幂的限制。 提出的两种观测矩阵易于硬件实现，避免了随机矩阵的不确定性且克服了 随机矩阵浪费存储资源的缺陷，具有良好的实际应用价值。 关键词：图像处理；机器视觉；压缩感知；采样及重构；观测矩阵；顺序部分哈达玛；循环伪随机矩阵；有限等距 中图分类号：ＴＰ３９１ 文献标志码：Ａ 文章编号：１６７３－４７８５（２０１７）０３－０２７９－０７ 中文引用格式：李霞丽，吴立成，樊艳明．易于硬件实现的压缩感知观测矩阵的研究与构造［ Ｊ］． 智能系统学报， ２０１７， １２ （ ３）： ２７９－２８５． 英文引用格式：ＬＩ Ｘｉａｌｉ， ＷＵ Ｌｉｃｈｅｎｇ， ＦＡＮ Ｙａｎｍｉｎｇ． Ｓｔｕｄｙ ａｎｄ ｃｏｎｓｔｒｕｃｔｉｏｎ ｏｆ ａ ｃｏｍｐｒｅｓｓｅｄ ｓｅｎｓｉｎｇ ｍｅａｓｕｒｅｍｅｎｔ ｍａｔｒｉｘ ｔｈａｔ ｉｓ ｅａｓｙ ｔｏ ｉｍｐｌｅｍｅｎｔ ｉｎ ｈａｒｄｗａｒｅ［Ｊ］． ＣＡＡＩ ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ ｉｎｔｅｌｌｉｇｅｎｔ ｓｙｓｔｅｍｓ， ２０１７， １２（３）： ２７９－２８５． Ｓｔｕｄｙ ａｎｄ ｃｏｎｓｔｒｕｃｔｉｏｎ ｏｆ ａ ｃｏｍｐｒｅｓｓｅｄ ｓｅｎｓｉｎｇ ｍｅａｓｕｒｅｍｅｎｔ ｍａｔｒｉｘ ｔｈａｔ ｉｓ ｅａｓｙ ｔｏ ｉｍｐｌｅｍｅｎｔ ｉｎ ｈａｒｄｗａｒｅ ＬＩ Ｘｉａｌｉ， ＷＵ Ｌｉｃｈｅｎｇ， ＦＡＮ Ｙａｎｍｉｎｇ （Ｓｃｈｏｏｌ ｏｆ Ｉｎｆｏｒｍａｔｉｏｎ Ｅｎｇｉｎｅｅｒｉｎｇ， Ｍｉｎｚｕ Ｕｎｉｖｅｒｓｉｔｙ ｏｆ Ｃｈｉｎａ， Ｂｅｉｊｉｎｇ １０００８１， Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：Ｉｎ ｔｈｅ ｃｏｍｐｒｅｓｓｅｄ ｓｅｎｓｉｎｇ ｐｒｏｃｅｓｓ， ｔｈｅ ｍｅａｓｕｒｅｍｅｎｔ ｍａｔｒｉｘ ｐｌａｙｓ ａ ｓｉｇｎｉｆｉｃａｎｔ ｒｏｌｅ ｉｎ ｓｉｇｎａｌ ｓａｍｐｌｉｎｇ ａｎｄ ｒｅｃｏｎｓｔｒｕｃｔｉｏｎ． Ｔｈｅｒｅｆｏｒｅ， ａ ｍｅａｓｕｒｅｍｅｎｔ ｍａｔｒｉｘ ｔｈａｔ ｉｓ ｓｉｍｐｌｅ ｉｎ ｓｔｒｕｃｔｕｒｅ， ｈａｓ ａ ｓｍａｌｌ ｍｅｍｏｒｙ， ａｎｄ ｉｓ ｅａｓｙ ｔｏ ｉｍｐｌｅｍｅｎｔ ｉｎ ｈａｒｄｗａｒｅ ｉｓ ｔｈｅ ｋｅｙ ｔｏ ａｐｐｌｙｉｎｇ ｃｏｍｐｒｅｓｓｅｄ ｓｅｎｓｉｎｇ ｔｈｅｏｒｙ． Ｂａｓｅｄ ｏｎ ｔｈｅ ｐａｒｔｉａｌ Ｈａｄａｍａｒｄ ｍｅａｓｕｒｅｍｅｎｔ ｍａｔｒｉｘ ａｎｄ ａ ｃｉｒｃｕｌａｔｉｎｇ ｐｓｅｕｄｏ⁃ｒａｎｄｏｍ ｓｅｑｕｅｎｃｅ， ｔｈｉｓ ｐａｐｅｒ ｐｒｅｓｅｎｔｓ ｔｗｏ ｍｅａｓｕｒｅｍｅｎｔ ｍａｔｒｉｘｅｓ ｔｈａｔ ａｒｅ ｅａｓｙ ｔｏ ｉｍｐｌｅｍｅｎｔ ｉｎ ｈａｒｄｗａｒｅ， ｎａｍｅｌｙ ｔｈｅ ｓｅｑｕｅｎｃｅ ｐａｒｔｉａｌ Ｈａｄａｍａｒｄ ｍｅａｓｕｒｅｍｅｎｔ ｍａｔｒｉｘ ａｎｄ ｔｈｅ ｒｅｃｙｃｌｅｄ ｐｓｅｕｄｏ⁃ｒａｎｄｏｍ ｓｅｑｕｅｎｃｅ ｍｅａｓｕｒｅｍｅｎｔ ｍａｔｒｉｘ． Ｔｈｅ ｌａｔｔｅｒ ｃｏｎｓｉｓｔｓ ｏｆ ａ ｒｅｃｙｃｌｅｄ ｍ ｓｅｑｕｅｎｃｅ ａｎｄ ａ ｒｅｃｙｃｌｅｄ ｇｏｌｄ ｓｅｑｕｅｎｃｅ ｍｅａｓｕｒｅｍｅｎｔ ｍａｔｒｉｘ． Ｔｈｉｓ ｆｕｒｔｈｅｒ ｐｒｏｖｅｓ ｔｈａｔ ａ ｍｅａｓｕｒｅｍｅｎｔ ｍａｔｒｉｘ ｃｏｎｓｔｒｕｃｔｅｄ ｂｙ ａ ｐｓｅｕｄｏ⁃ｒａｎｄｏｍ ｓｅｑｕｅｎｃｅ ｃｏｍｐｌｉｅｓ ｗｉｔｈ ｔｈｅ ＲＩＰ ｐｒｉｎｃｉｐｌｅ． Ｔｏ ｔｅｓｔ ｔｈｅ ｐｅｒｆｏｒｍａｎｃｅ ｏｆ ｔｈｅ ｔｗｏ ｍｅａｓｕｒｅｍｅｎｔ ｍａｔｒｉｘｅｓ， ａ ｔｗｏ⁃ ｄｉｍｅｎｓｉｏｎａｌ ｉｍａｇｅ ｓｉｇｎａｌ ｗａｓ ｓｉｍｕｌａｔｅｄ． Ｉｔ ｗａｓ ｆｏｕｎｄ ｔｈａｔ ｕｎｄｅｒ ａ ｌｏｗ ｓａｍｐｌｉｎｇ ｒａｔｅ， ｔｈｅ ｒｅｃｏｎｓｔｒｕｃｔｉｏｎ ｏｆ ｔｈｅ ｓｅｑｕｅｎｃｅ ｐａｒｔｉａｌ Ｈａｄａｍａｒｄ ｍｅａｓｕｒｅｍｅｎｔ ｍａｔｒｉｘ ｉｓ ｏｐｔｉｍａｌ ｐｒｏｖｉｄｅｄ ｔｈａｔ ｔｈｅ ｌｅｎｇｔｈ ｏｆ ｔｈｅ ｓａｍｐｌｉｎｇ ｓｉｇｎａｌ ｉｓ ２ ｋ ． Ａｌｔｈｏｕｇｈ ｒｅｃｏｎｓｔｒｕｃｔｉｏｎ ｏｆ ｔｈｅ ｒｅｃｙｃｌｅｄ ｐｓｅｕｄｏ⁃ｒａｎｄｏｍ ｓｅｑｕｅｎｃｅ ｍｅａｓｕｒｅｍｅｎｔ ｍａｔｒｉｘ ｉｓ ｉｎｆｅｒｉｏｒ ｔｏ ｔｈｅ ｓｅｑｕｅｎｃｅ ｐａｒｔｉａｌ Ｈａｄａｍａｒｄ ｍｅａｓｕｒｅｍｅｎｔ ｍａｔｒｉｘ， ｉｔ ｅｘｃｅｅｄｓ ｔｈｅ Ｇａｕｓｓｉａｎ ｒａｎｄｏｍ ｍｅａｓｕｒｅｍｅｎｔ ｍａｔｒｉｘ， ａｎｄ ａｌｓｏ ｏｖｅｒｃｏｍｅｓ ｔｈｅ ｓｅｑｕｅｎｃｅ ｐａｒｔｉａｌ Ｈａｄａｍａｒｄ ｍｅａｓｕｒｅｍｅｎｔ ｍａｔｒｉｘ ’ ｓ ｌｉｍｉｔａｔｉｏｎ ｏｆ ａ ２ ｋ ｓｉｇｎａｌ ｌｅｎｇｔｈ． Ｔｈｅｓｅ ｔｗｏ ｔｙｐｅｓ ｏｆ ｍｅａｓｕｒｅｍｅｎｔ ｍａｔｒｉｘ ａｒｅ ｅａｓｙ ｔｏ ｉｍｐｌｅｍｅｎｔ ｉｎ ｈａｒｄｗａｒｅ， ａｎｄ ａｖｏｉｄ ｔｈｅ ｕｎｃｅｒｔａｉｎｔｙ ａｎｄ ｓｔｏｒａｇｅ ｗａｓｔｅ ｏｆ ａ ｒａｎｄｏｍ ｍａｔｒｉｘ． Ｔｈｅｒｅｆｏｒｅ， ｔｈｅｙ ａｒｅ ｓｕｉｔａｂｌｅ ｆｏｒ ｐｒａｃｔｉｃａｌ ａｐｐｌｉｃａｔｉｏｎ． Ｋｅｙｗｏｒｄｓ： ｉｍａｇｅ ｐｒｏｃｅｓｓｉｎｇ； ｍａｃｈｉｎｅ ｖｉｓｉｏｎ； ｃｏｍｐｒｅｓｓｅｄ ｓｅｎｓｉｎｇ； ｓａｍｐｌｉｎｇ ａｎｄ ｒｅｃｏｎｓｔｒｕｃｔｉｏｎ； ｍｅａｓｕｒｅｍｅｎｔ ｍａｔｒｉｘ； ｓｅｑｕｅｎｃｅ ｐａｒｔｉａｌ Ｈａｄａｍａｒｄ； ｓｅｑｕｅｎｃｅ ｐｓｅｕｄｏ⁃ｒａｎｄｏｍ； ｒｅｓｔｒｉｃｔｅｄ ｉｓｏｍｅｔｒｙ ｐｒｏｐｅｒｔｙ 收稿日期：２０１６－０６－２１． 网络出版日期：２０１７－０４－０４． 基金项目：国家自然科学基金项目（５１３７５５０４，６１６０２５３９）． 通信作者：吴立成．Ｅ⁃ｍａｉｌ：ｗｕｌｉｃｈｅｎｇ＠ ｔｓｉｎｇｈｕａ．ｅｄｕ．ｃｎ． 压缩感知（ ｃｏｍｐｒｅｓｓｅｄ ｓｅｎｓｉｎｇ，ＣＳ） ［１－３］ 通过利 用信号的稀疏特性，在远小于 Ｎｙｑｕｉｓｔ 采样率的条件 下，用随机采样获取信号的离散样本，然后通过非 线性重建算法重建信号。 由于压缩感知理论具有 “轻编码、重解码”的特点，压缩感知理论应用到低 功耗无线传输的硬件系统中是一个比较合理的选 择。 压缩感知主要解决的 ３ 个问题分别为信号的稀