（信号与信息处理专业论文）基于正交匹配追踪算法的新生儿疼痛表情识别.pdf

neonatal pain facial expression recognition based on orthogonal matching pursuit algorithm thesis submitted to nanjing university of posts and telecommunications for the degree of master of engineering by li yaming supervisor: prof. lu guanming march 2013 i 摘要摘要 近些年来，经过医学界的研究证明，如果新生儿受到反复的疼痛刺激，这将对新生儿产生 许多的不良影响，因此新生儿疼痛的研究受到越来越多的研究人员的关注。另外，因为新生 儿无法表述其自身的疼痛感觉，这也就需要研究出能够对新生儿疼痛进行评估的工具，在诸 多的评估手段中，新生儿的面部表情被认为是一种比较有效可靠的评估指标。但是人工对新 生儿面部表情进行评估是一项需要大量时间和精力的工作，且易受到主观因素的影响，所以 开发出一种新生儿面部疼痛表情自动识别系统就显得十分有意义。 作为最近在信号处理领域的一个新理论，压缩感知理论有着许多的优点。它主要是针对于 稀疏的或者可压缩的信号，在对这些信号进行采样的时候可以同时进行适当的压缩，由于图 像信号在大多时候是具备稀疏性的，这就为在模式识别和图像处理的问题上使用稀疏表示方 法提供了可能性。本文主要的研究工作包括以下几个方面。 (1)分别采用了下采样和主成分分析法作为特征提取方法，对本文中所用到的新生儿面部 表情图像进行特征提取。 (2)通过对新生儿面部表情图像测试样本的稀疏表示，采用正交匹配追踪算法求得最稀疏 的系数解，经实验证明所求得的系数中具有可以对测试样本进行分类的类别信息，可以实现 对测试表情图像的识别。 (3)分别将采用下采样和主成分分析法两种特征提取方法所得的结果与正交匹配追踪算法 相结合进行实验，通过对比实验结果发现，如果具备充分的训练样本和特征维数，同时系数 解足够稀疏的时候，这两种不同的方法都可以达到较为满意的识别水平。 关键词：关键词：新生儿疼痛，面部表情识别，特征提取方法，稀疏表示，正交匹配追踪算法 ii abstract nowadays, medical research has proven that repeated pain could bring a negative impact to infants. studies about neonatal pain have been concerned by lots of researchers. assessment tools of neonatal pain have been much needed because neonates couldnt tell their subjective feelings. among all the assessment indicators, the infants facial expression is considered as the most reliable and effective one. if the recognition work was completed by the well trained health professors, itll be a time costly and difficult job, meanwhile, the recognition results are vulnerable influenced by the subjective factors. so the research about facial expression recognition is very useful and meaningful, and a kind of auto neonatal pain assessment system is much needed. as a new theory of signal processing, compressive sensing theory has plenty of advantages. it is mainly used under the condition which the signal is compressive or sparse. it can compress a signal when the signal is sampled. this theory is possible used in the area of pattern recognition and image processing, because image signals are always sparse. the research work in this paper mainly includes the followed aspects. (1)we attract features of the neonatal facial expression we used in this paper with down-sampled and primary component analysis separately. (2)we did research on a new kind of neonatal pain facial expression recognition method, which is based on orthogonal matching pursuit algorithm. with this method, the infant facial expression is easy to recognize and classify because the sparse representation of the test infant facial expression image processed by the orthogonal matching pursuit algorithm has distinct class information. (3)the research in this paper proved that the method we raised can achieve a good recognition rate. the experiment results show that when the number of the training sample and abstracted features are sufficient, and the sparse representation is correctly found, the algorithm framework presented in this paper can work well with the feature abstraction such as down-sampled or primary component analysis. key words: neonatal pain, facial expression recognition, feature abstraction method, sparse representation, orthogonal matching pursuit algorithm iii 目目 录录 第一章 绪论 . 1 1.1 研究背景 . 1 1.2 国内外新生儿疼痛表情研究现状 . 2 1.3 本章小结 . 4 第二章 压缩感知相关理论介绍 . 6 2.1 引言 . 6 2.2 压缩感知理论框架 . 6 2.3 信号的稀疏表示 . 8 2.4 测量矩阵的设计 . 9 2.5 压缩感知的重构算法 . 10 2.5.1 最小 l1 范数法 . 11 2.5.2 最小全变分法 . 11 2.5.3 迭代阈值法 . 11 2.5.4 匹配追踪算法 . 12 2.6 本章小结 . 12 第三章 图像的特征提取和稀疏表示 . 13 3.1 特征提取方法介绍 . 13 3.2 图像的稀疏表示 . 15 3.3 正交匹配追踪(omp)算法 . 16 3.3.1 匹配追踪(mp)算法 . 16 3.3.2 正交匹配追踪(omp)算法 . 17 3.4 本章小结 . 25 第四章 基于 omp 算法的新生儿疼痛表情识别 . 26 4.1 新生儿面部图像数据库的建立 . 26 4.2 实验的基本环境和流程介绍 . 27 4.3 用下采样(ds)进行特征提取的实验过程和结果 . 28 4.4 用 pca 进行特征提取的实验过程和结果 . 31 4.5 使用下采样和 pca 特征提取方法的实验对比 . 34 4.6 本章小结 . 36 第五章 总结与展望 . 37 5.1 本文总结 . 37 5.2 进一步的工作 . 38 参考文献 . 39 附录 1 攻读硕士学位期间撰写的论文 . 42 附录 2 攻读硕士学位期间参加的科研项目 . 43 致谢 . 44 南京邮电大学硕士研究生学位论文 第一章 绪论 1 第一章第一章 绪论绪论 1.1 研究背景研究背景 人脸表情识别是一个综合了许多学科内容的新兴领域，这一研究是人机智能沟通的新方 向。而其中的新生儿面部表情识别更是一个具有广阔应用前景和巨大挑战的分支。 以前许多麻醉学者都认为新生儿不会有疼痛感，因此新生儿疼痛的课题一直未引起足够 的重视。近些年来，相关研究认为，疼痛的刺激会对新生儿尤其是早产或危重儿带来短期以 及长期的不良影响，因此开发出新生儿疼痛管理协议以及能够进行疼痛评估的工具就成为了 一项很有实用意义的研究。 在新生儿疼痛的评估过程中，由于新生儿对于其他的一些并无疼痛感的影响也会对有同 样的个体反应1,2，因此找到一种可靠的手段或者途径对新生儿的疼痛进行识别就显得尤为重 要。目前有多种不同的疼痛评估工具，包括新生儿面部编码系统3、cries量表4、新生儿疼 痛评分 5、早产儿疼痛评分6等四种系统来进行评估新生儿的疼痛，这四种不同的新生儿疼 痛评估工具的观测指标有所不同。表1.1是四者的信度、效度和可行性等的比较，其中“”表 示有此项观测指标，“+”表示好，“”表示无或未验证，自左向右依次为以上所提到的四种系 统。通过对表1.1的观察，可以发现，这四个评估系统均将面部表情作为评估的一项，由此可 见面部表情在疼痛测评系统中有较好的有效性和可靠性。广西壮族自治区柳州市人民医院的 袁大华等，用他们所做的新生儿疼痛量表，在常规医疗操作(静脉穿刺和足跟采血等)实施中 及完成后将入选住院的一百个新生儿分两组(评估和对照各五十例)，实施测评，测评项目共 为生理指标、啼哭程度、面部表情、上下肢活动等，也证明了面部表情能较好地反映出新生 儿的疼痛与否7。经过国内外相关专家学者诸多研究证明，从新生儿的面部表情特征以及其 变化对新生儿疼痛与否进行判断能够得到较为准确客观的识别结果8,9,10。 国际上的新生儿疼痛衡量皆是在经受过各种专业训练的医护人员的操作下进行评估的， 面部表情作为新生儿疼痛研究中最有效的检测手段已经逐渐在医学领域受到重视。但是在这 个过程中也存在着许多问题，比如说这将耗费很大的资源和时间，同时评估会受到若干人为 原因的干扰11,12。所以，研究一个有效、快速、客观的新生儿疼痛测评系统就变得很具价值 与意义。新生儿疼痛表情识别是一个多学科的研究课题，它包括了生物以及计算机科学等领 域，它的复杂性也就决定了这一研究仍有许多问题待于解决。 南京邮电大学硕士研究生学位论文 第一章 绪论 2 表1.1 新生儿疼痛评估工具的比较 pipp nips cries nfcs 面部表情 睡眠/觉醒状态 生理指标 哭闹 肢体 孕周 测量者间信度 + + + + 内部一致性 + + + 同期/标准效度 + + + + 结构效度 + + + + 可行性 + + + + 本文所做的工作就是根据新生儿表情图像的不同特征来研究出一种能客观高效地识别出 新生儿疼痛表情的系统，本项目的研究在医疗机构的临床应用上有着十分广阔的应用前景， 在技术成熟后可以在实践中加以推广，为医护人员提供有效，可靠，客观又科学的评估新生 儿疼痛的依据，以便于在临床上采取及时的镇痛治疗措施，从而减少新生儿的疼痛；同时也 可以成为研制相关镇痛药物的评估手段和治疗效果的评价标准。本课题的研究对于改善生命 质量， 提高我国人口出生素质和维持社会的可持续发展都有极其重要的社会效益和现实意义。 另外本课题的实现方法和研究思想对于促进和推动情感计算，模式识别，生物电子学等学科 都有着十分重要的学术价值和理论意义。 1.2 国内外新生儿疼痛表情研究现状国内外新生儿疼痛表情研究现状 国内外对于新生儿疼痛表情识别的研究刚刚起步，新生儿的疼痛表情识别研究还属一个 较为前沿的领域。2007年，美国学者brahnam13发表了有关新生儿疼痛表情识别的算法，对 26名新生儿的面部表情图像进行了疼痛与非疼痛的分类识别。但是由于样本图像数量太少， 该算法的鲁棒性不够，无法应用到实际临床中去。 在国内的相关领域内，南京邮电大学卢官明教授等人对于新生儿疼痛表情识别的研究处 于领先地位，并且取得了较大的进展14,15,16,17。他们在新生儿表情图像处理、表情特征提取、 表情分类识别方面做了大量的工作和研究。他们建立了较为完善的新生儿表情图像数据库， 并分别采用gabor小波变换等方法对新生儿表情图像进行特征提取， 另外还采用过不同种类的 支持向量机(svm)以及其他算法与svm结合的方法对新生儿表情图像进行分类识别。在文献 南京邮电大学硕士研究生学位论文 第一章 绪论 3 17中，采用了gabor小波变换和adaboost算法相结合的方法对新生儿表情图像进行特征提取 和特征选择， 然后使用svms多类分类器对特征向量进行多类分类，从而实现对新生儿疼痛表 情的识别，在使用基于二叉树的svms分类器时能达到较高的识别率，识别率为82.86%。在文 献18中使用了gabor变换对图像进行特征提取，然后利用svm分类器对新生儿面部表情图像 进行识别，另外还采用了pca方法直接对新生儿面部表情图像进行特征提取，然后送入svm 分类器进行表情分类，也可得到较为满意的识别率。其中gabor变换对于图像一定程度的变形 和旋转有较好的适应能力，并且对于光照的变化不是很敏感，这些特点决定了它有良好的性 能；另外svm具有较好的推广性、全局最优和小样本等优异的分类特性。这些研究为本文所 进行的研究提供了许多可以借鉴的方法和理论，也为本文所提出的新生儿疼痛表情识别方法 提供了充分的参照。 目前的新生儿疼痛表情识别方法主要由图像的获取、新生儿面部的检测和定位、图像的 预处理、特征的提取、训练和识别六个功能模块构成，各模块的功能如表1.2所示。 表1.2 新生儿疼痛表情识别系统的功能模块 模块 各模块的功能 图像的获取 该模块从外界获取图像，作为识别系统的输入。该模块可以是一个摄像头等设备。 新生儿面部 检测和定位 处理分析从图像获取模块输入的图像，判断其中是否存在新生儿的脸，如存在则找到新 生儿面部在图像的位置，将新生儿面部从背景图像中分离出来。 图像的预处 理 预处理的主要作用是尽可能的去除或减小光照、成像系统、外部环境等对于待处理图像 的干扰，为后续处理提供高质量的图像。这部分对检测到的新生儿面部图像进行几何的 归一化、消除噪声、灰度归一化、水平与垂直位置的校正等处理，为后面的特征提取创 造条件。 特征的提取 该模块完成从经过预处理模块处理的图像中提取可以用来识别的特征，将原始图像映射 到特征空间中。 训练 此过程结束后将生成可用于识别的参数，也就是可用于分类识别的分类器。事实上，模 式识别问题可以看成是一个分类问题，即把待识别的对象归到某一类中。在新生儿表情 识别问题中就是把输入的不同的新生儿表情图像归入某个表情这一类。这部分的基本做 法是在样本训练集的基础上确定某个判决规则，使按这种判决规则对被识别对象进行分 类所造成的错误识别率最小或引起的损失最小。 识别 根据训练所得的结果完成新生儿疼痛表情的判别工作，给出最后的识别结果并做出相应 的判断。 南京邮电大学硕士研究生学位论文 第一章 绪论 4 从功能上可以将现有的新生儿表情识别系统划分为训练和识别两大部分。本文的主要目 的是基于压缩感知理论，研究和建立一种有效的、具有较好鲁棒性的新生儿疼痛表情识别方 法框架，为今后能够在实用领域开发出一套快捷高效的新生儿疼痛表情识别系统奠定理论基 础。 最近几年在压缩感知研究领域， 有关超完备基的系数线性表示问题成为了一个研究热点， 研究压缩传感的最初目的是为了用在信号的压缩和表示上，但是由于其稀疏表示有较好的可 判别性，文献19用训练样本作为超完备基，利用了稀疏表示的这一特性，较好地实现了人 脸识别，这说明了如果有足够充分的样本，测试样本可以用同类的训练样本的线性组合表示 出来，在整个样本集上的表示自然十分稀疏，这样就可以用压缩感知的方法来解决分类的问 题。因此可以利用这一原理提出一种新型的新生儿疼痛表情识别方法。从理论上可以推导出 这种识别方法的可行性，以及它的诸多优点。本文就是利用稀疏表示这一思想提出一种新的 新生儿疼痛表情识别方法。以后章节将对稀疏表示方法的研究情况做进一步的介绍。 1.3 本章小结本章小结 本文对于如何使用压缩感知理论中的正交匹配追踪算法求解l-1范数作了较为详细的介 绍，本文还从整体上提出了一种基于正交匹配追踪算法的新生儿疼痛表情识别方法，在特征 提取环节分别采用了pca方法和下采样方法，并分别将经过这两种特征提取方法得到的结果 放入本文所提出的方法框架中进行识别和分类。实验结果表明当有足够的特征维数和训练样 本，并且能够准确地得到最稀疏的系数解时，两种不同的特征提取方法对于新生儿疼痛表情 识别结果的影响不是很明显，并都能达到较为满意的识别效果。 本文由五章组成，每章内容如下： 第一章为绪论部分，先介绍了本课题的研究背景以及新生儿疼痛表情识别的国内外研究 现状；然后介绍了当前对于稀疏表示方法的研究情况，并提出了一种基于正交匹配追踪算法 的新生儿疼痛表情识别方法。 第二章将传统的压缩模型与压缩感知理论进行了对比，从而说明了压缩感知理论的诸多 优点；另外本章还较为详尽地阐述了压缩传感理论的三个核心难点：信号的稀疏表示、传感 矩阵和重构算法。这一章为基于正交匹配追踪算法的新生儿疼痛表情识别进行了理论铺垫。 第三章介绍了新生儿疼痛表情识别中所用到的特征提取方法；另外还介绍了压缩感知理 论中重构算法的一种匹配追踪算法，其中较为详细的介绍了正交匹配追踪算法，并通过 实验验证了正交匹配追踪算法在本文所提出的新生儿疼痛表情识别方法框架中能够很好地达 南京邮电大学硕士研究生学位论文 第一章 绪论 5 到目的。 第四章介绍了新生儿疼痛表情识别系统的基本框架；提出了基于正交匹配追踪算法的新 生儿疼痛表情识别方法；并分析和对比了使用pca和下采样两种特征提取方法在不同的训练 样本情况下对于新生儿疼痛表情识别方法的识别效果的影响；另外还拿本文所采用的方法比 较了以往所采用的几种识别方法。 第五章为总结和展望部分，在本章归纳了本文的工作，同时对于本课题下一步的方向做 了展望。 南京邮电大学硕士研究生学位论文 第二章 压缩感知相关理论介绍 6 第二章第二章 压缩感知相关理论介绍压缩感知相关理论介绍 2.1 引言引言 许多年以来，nyquist采样定理一直都是指导信号采样的一个理论基础，它在许多方面都 得到了广泛的应用，譬如核磁共振成像、传感器网络、雷达遥感成像、超宽带通信和信号处 理，在这些情况下如果按照nyquist采样定律对信号进行处理，这将会产生海量的采样数据， 而其中很大一部分数据都是冗余的， 这在很大程度上增加了数据传输以及存储的难度和代价； 另外奈奎斯特采样频率要求必须大于或等于两倍信号带宽，这也是对硬件设备的一个巨大挑 战20,21。这种采样方法有着其自身的缺点，假定一个较高的频率作为最大频率，这就导致了 较小的采样间隔和得到较长的采样信号长度，在之后的压缩过程中这将导致较长的耗时；另 外这种信号处理的鲁棒性也有待提高。 面对传统的采样方法，人们认识到需要寻求一种新的采样方法对其缺点进行弥补。在这 种情况下，美国科学院院士d.donoho、华裔科学家陶哲轩以及e.cand s等人经过长期而又辛 苦的研究工作，提出了我们本章将要介绍的一个重要理论压缩感知理论。这一理论主要 是基于稀疏表示和信号逼近论22,23。此后世界上一些知名的大学也都对这一拥有广阔前景的 理论展开了研究。这一理论试图从原理上降低测量一个信号时的成本，这个理论告诉我们： 对于一个具有稀疏性或可压缩性的信号，对其进行少于或者远少于nyquist采样定律的要求对 信号进行采样24。压缩传感理论的关键字是稀疏、不相关、随机性、非自适应、非线性，这 一原理突破了香农采样定理的极限，可以通过随机采样和更少的采样点来恢复原始信号25。 压缩感知理论针对可以稀疏表示的信号，能同时完成数据的采集和压缩，虽然压缩感知 理论提出的时间不长，但是其诸多优点已经预示了它广阔的应用前景。 2.2 压缩感知理论框架压缩感知理论框架 为了便于对压缩感知理论的讨论，我们先来了解表2.1中的几个概念。 南京邮电大学硕士研究生学位论文 第二章 压缩感知相关理论介绍 7 表2.1 几个基础的概念 压缩感知理论中涉及的重要概念 1 采样定理 采样定理是指在模拟信号与数字信号的转换中，如果满足采样频率大于信号最 高频率的二倍时，采样所得的数字信号就具有了原始信号的所有信息26。 2 奈奎斯特 采样频率 在已知被采样信号的最高频率时，根据采样定理得出的最小的采样频率。 3k-稀疏 如果一个信号的采样点中只有k个非零，其他的都为零，则这个信号被称作k- 稀疏的信号。 4 可压缩信 号 如果一个信号经过某种不丢失任何信息的变换之后是稀疏的，则此信号是可压 缩的。在实际应用中的通信信号和听觉信号是频域内稀疏或近似稀疏的。 5 约束等距 性 约束等距性(restricted isometry property, rip)条件44是指如果有一个矩阵，对 于 常 数 (0,1) 和 任 意 的 c ， 如 果 满 足 式 子 (1- ) (1+ ) ,其中t 1，,n, , 指矩阵中 由索引t所指示的相关列所构成的大小为k 的子矩阵，那么矩阵满足约束 等距性27。 压缩感知的概念在2006年被donoho和e.cand s等人提出。压缩感知和传统的均匀采样不 同之处在于：它是一个非相关测量的过程，设x为一个长度为n的信号，而经过压缩感知之后 就可以得到长度为m的测量值y，y的长度小于x的长度，二者的关系是y=x (是m 的测量 矩阵)28,29。压缩感知是一个非相关编码测量的过程,其核心是对于一个未知的稀疏信号 x ,找到它的m个线性测量值y=x, 测量矩阵 ,其中的每一行可以看做一个传 感器，当信号x经过这个传感器之后可以获得信号的一部分信息，有了测量矩阵和m维的线 性测量值y，通过式2.1就可以重构出原始信号(其中 指求解l0范数)30,31。 (2.1) 在式2.2中，其中x=s,s为k-稀疏的，其中=被称作传感矩阵。这一过程如图2.1所 示。 y=x=s=s (2.2) 由式2.2可知， y可以被看做稀疏信号s关于测量矩阵的测量值， 如果测量矩阵满足约束 等距性条件，则可以得到一个类似于式2.1的最优l0范数求解问题式2.3来重构稀疏信号s。 (2.3) 南京邮电大学硕士研究生学位论文 第二章 压缩感知相关理论介绍 8 图2.1 测量过程（系数s s有4个非零单元，所以矩阵 只有4列起作用） 从上面的叙述中可以看出，在上述的方程组中未知数的数量大于方程的个数，s无法从y 中直接恢复出来，但是可以将这转化成一个求解优化问题，也即是把目标函数等价成 s ，这就将一个无法求解的np难组合最优化问题变成了一个线性规划最优 化求解。 这样我们就能看出使用压缩感知理论进行信号处理，有几个问题需要解决：（1）在前面 的叙述中可以看出对原始信号进行重构的前提是这个信号必须是稀疏信号，所以我们对于非 稀疏信号要进行一些相应的处理。 （2）信号低速采样问题，也即是怎样设计出同变换基不 相关同时为平稳的 维的测量矩阵，并且要保证当稀疏量自 维降至 维的过程中重 要的信息没有被破坏。 （3）已知、y的情况下，选择一个合适的算法来恢复出最优解s， 并通过选择的稀疏基重构x。 2.3 信号的稀疏表示信号的稀疏表示 coimfan和wicker hauesr等人为了对信号更加简洁、灵活并且自适应的表示，他们较深入 地研究了稀疏表示的问题。稀疏的数学定义是：一个信号中仅有少数的采样点为非零的，而 其他的采样点都为零，则这个信号被称作稀疏的32。 自然信号在时域里一般都不是稀疏的，虽然在某些位置的值比较小但不一定为零，可如 果把此信号变换到小波域，小波系数中很大一部分为零或近似于零，即是说通常的时域信号 在小波基上是稀疏的33。zhang和mallat基于小波分析理论，在学习研究后提出了在一个过完 备原子库中对信号进行分解的方法，它是信号分析与处理的一个新方向34。 如果一个信号经过某种不丢失任何信息的变换之后可以稀疏表示，也即是信号在某些变 换域内是稀疏的，则此信号被称作可压缩信号35。一个信号具备稀疏性或者它是可压缩的， 这个条件是压缩感知理论的前提。为了简化模型，我们把一个长度为 的离散实值信号x记成 x(n),n1,2, ，由信号理论可知 ，其中是能够线性表示x的一 南京邮电大学硕士研究生学位论文 第二章 压缩感知相关理论介绍 9 组基的线性组合，在式中 ，为nn的矩阵， 和 都是n1的矩阵。当在 某一个基上信号x只有k(k )个非零的系数 ，此时把称作信号x的稀疏基36。目前使 用较多的稀疏基有正/余弦基37、chirplet基38、curvelet基39以及小波基40等。 信号的稀疏表示具备诸多的长处，这也使对其的研究迅速地延伸到二维信号，并且显示 出了许多的优良特性41。信号的稀疏表示是信号分析的一个新方向。 2.4 测量测量矩阵的设计矩阵的设计 测量矩阵不是根据信号x来进行选择的，这是一个非自适应的过程。测量矩阵所遵从的 设计要求是使信号x转换成y时要保证在后续的步骤中能够精确地重构信号，并且原始信号中 的信息不会被所得到的k个测量值破坏。由前面的介绍可知信号x对于某种变换基是可稀疏 表示的信号，也即是y=x=s=s，是m n维的。由上式可以知道未知数的个数远大于 方程的个数，所以无法对这个方程求解，这个信号也无法重构42。 如果与稀疏表示的基不相关， 那么可以构造出一个测量矩阵， 使得传感矩阵= 满足rip条件。稀疏表示的基不能随意改变，但是可以通过合理地设计测量矩阵来使传感 矩阵满足rip条件。文献44提到并且证明了当测量矩阵为gaussian随即矩阵时，传感矩阵 有较大概率满足rip条件。这样就为我们提出了一个设计测量矩阵的方法：我们可以选择一个 mn维的并且其中的每一个值都服从n(0, )分布， 这个矩阵和任何稀疏信号几乎都是不相 关的，这样可以极大地减少测量次数；这种方法的不足之处是计算过程比较复杂。 测量矩阵在整个压缩感知的过程中的重要性是显而易见的。除了gaussian随机矩阵之外， 表2.2还列出了其它几种常见的能使传感矩阵满足rip条件的测量矩阵以及它们各自的特点。 南京邮电大学硕士研究生学位论文 第二章 压缩感知相关理论介绍 10 表2.2 几种常见的测量矩阵及各自特点 矩阵名称 特点 一致球测量矩阵 矩阵的列在球 上是独立同分布随机一致的, 当测量次数为m = o(k ln(n) 时,能以较大的概率重构信号。 二值随机矩阵 矩阵中每个值都服从对称伯努利分布p( )= ,当k 时，能够以较大概率重构信号，并且重构的速度很快43。 局部傅里叶矩阵 此矩阵是首先从傅里叶矩阵中随机选择m 行, 然后再对列进行单位正则化而得 到的。它的突出优点是可以利用快速傅里叶变换快速计算，大大降低了采样系统 的复杂性；缺点是由于其通常只与时域稀疏的信号不相关,应用范围受到了限制。 局部哈达玛测量 矩阵 此矩阵是从n维哈达玛矩阵中随机选择m 行得到的。当满足条件 m （b为块的维数）时，置乱块哈达玛矩阵可以以极大概率准确 重构信号。 托普利兹矩阵和 循环矩阵 当k 时，这两种矩阵能使传感矩阵以很大概率满足rip条件, 并且可以直接应用快速傅里叶变换得到快速的重构算法, 能够明显减少高维问 题的计算和存储复杂度, 对高维问题特别有效。这两种测量矩阵一般都能带来较 好的重构结果，并且可以明显地加快运算速度以及减少存储空间。 结构化随机矩阵 该矩阵几乎与所有其他正交矩阵(单位阵和极度稀疏矩阵除外) 不相关， 可以分解 成定点、结构化分块对角矩阵与随机置换向量或伯努利向量点积的形式。此矩阵 可以看作是随机高斯/伯努利矩阵和部分傅里叶变换矩阵的混合模型，它兼具了 这几种矩阵的优点。 2.5 压缩感知的重构算法压缩感知的重构算法 信号重构就是指通过m维的测量向量y把长度为n（mn）的信号x重建出来的过程。当 传感矩阵满足约束等距性条件时， 根据式2.2可知， 首先求出稀疏系数s= x， 其中 为 的转置矩阵，然后就可以从根据m维的测量投影值y正确地把稀疏度为k的信号恢复出来，解 决这一问题的直接方法如式2.3所示，这是一个通过l0范数下求解的最优化问题。通过式2.3 虽然在理论上可以得到稀疏解的估计，但实际上此式是一个np难问题，需穷举出 种x中的 非零值的可能性，这是无法求出解的44。为了解决这个问题，许多种求次最优解的方法被提 出， 其中用得较多的几种有： 最小l1范数法、 最小全变分法、 迭代阈值法和匹配追踪算法等。 南京邮电大学硕士研究生学位论文 第二章 压缩感知相关理论介绍 11 下面将对这几种算法分别进行介绍。 2.5.1 最小 l1 范数法 针对l0范数求解的np难问题，文献45,46提出了将此问题转化成一个l1范数进行求解， 也即是将式2.3中的求解问题转化为式2.4。 (2.4) 式2.4是一个凸最优问题，并且它和式2.3是完全等价的。可以利用基追踪方法对其进行求 解，也即是把该问题转化成一个线性规划问题进行研究，该方法的计算复杂度为o( )。这种 方法的优点是仅仅需要较少的测度，可是它的算法复杂度比较高，这也影响到了它在实际中 的应用。另外也可以采用梯度投影法、同伦（homotopy algorithm）算法、内点法对式2.4进 行求解。 在考虑了重构误差的情况下， 式2.4所描述的问题也可转化为式2.5形式的最小l1范数 求解，此时可以通过二阶圆锥规划对其进行求解47。 (2.5) 比较以上的几种方法，他们各自的特点决定了它们对于不同情况的适用性。其中内点法 非常的精确，可是其速度欠佳。为了使测量噪声对于重构算法的影响较小，cand s等人还提 出了通过重置最小化l1范数问题来使稀疏信号重构质量得到提高的方法，这种方法称作加权 最小l1范数重构算法。 2.5.2 最小全变分法 前面所提到的最小l1范数法相对而言更适合对一维信号的重构，但是许多自然图像都具 有稀疏的离散梯度，考虑到这个问题，cand s等人提出最小全变分法来解决此问题，实验证 明这种方法更加适合二维图像的重构。 图像压缩感知的全变分模型如式2.6所示： mintv(s) s.t. (2.6) 其中目标函数tv(s)是图像的离散梯度的和，也即是 （ ） （ ） 。 2.5.3 迭代阈值法 前面介绍的最小l1范数法虽然可以比较有效的重构压缩感知的稀疏信号，但此方法并未 直接对式2.1中的l0范数问题求解。针对此问题，有学者提出了直接对式2.1进行求解的方法， 南京邮电大学硕士研究生学位论文 第二章 压缩感知相关理论介绍 12 即迭代阈值算法。这种算法并不能求得全局最优解，如果不能找到合适的初值，那么该算法 就无法得到全局最优解。这种算法的应用在信号重构中比较受限，一般都是和其他的算法结 合起来使用，由其他的算法来保证能有适合迭代阈值法的初值。 2.5.4 匹配追踪算法 在cs理论中，我们通常把测量矩阵称作冗余字典，测量