信号稀疏分解及压缩感知理论应用研究

西安电子科技大学博士学位论文信号稀疏分解及压缩感知理论应用研究姓名：刘丹华申请学位级别：博士专业：电路与系统指导教师：石光明20091201摘要摘要信号稀疏表示能够有效地提取信号昀本质的特征，在信号压缩、特征提取、去噪、超分辨重建等信号处理领域有着广泛的应用。近年来备受国内外研究学者关注的压缩感知理论正是建立在信号稀疏表示理论基础上的，它进一步表明了稀疏表示理论的重要价值和巨大应用潜力。但无论是压缩感知理论还是稀疏表示理论都仍有许多问题有待进一步研究。本文围绕信号稀疏表示和压缩感知理论展开深入研究，重点研究了过完备字典下的信号稀疏分解方法，并将压缩感知框架应用于多描述编码和图像加密领域，取得了一定的研究成果。本文的主要工作和研究成果如下：1.提出一种基于正交级联冗余字典的分组匹配追踪算法。该算法利用正交分解快速算法，首先从由多个正交基构成的过完备字典中选出和原信号昀匹配的一个正交基中的多个正交原子，得到第一批少量的重要系数，接下来再在剩余的正交基中找到和残余信号昀匹配的一个正交基，得到下一批重要系数。如此反复迭代，直至达到残余信号的精度要求（或迭代次数要求），就可以得到原始信号的稀疏逼近。由于迭代过程均采用的是正交分解快速算法，因此计算复杂度大大降低。实验结果表明，在同等稀疏条件下，本文算法与匹配追踪（MP）算法相比，计算速度提高了大约几十倍，而且可以避免MP算法的过匹配现象。2.提出一种基于原子库树状结构划分的诱导式稀疏分解算法。该算法从已构造好的原子库入手，首先根据其原子库自身结构特点对其进行逐层树状结构划分，然后，在每次分解过程中都利用该树状结构，有目的、有导向性地指引信号的分解方向。原子库的树状层次结构一旦形成可用于适合该类字典的任意信号的分解，因此这种划分只需一次完成就可以一劳永逸地加快信号分解速度，极大降低了分解过程中的计算复杂度。而且，该算法适用于任何类型的过完备字典。仿真实验结果表明，和MP这一经典算法相比，本文算法在同等稀疏度和逼近误差的情况下，计算量大约降低为MP算法的1/40。3.提出一种新的抗丢包能力强且编码简单的压缩感知-多描述编码方法，简称CS-MDC方法，并提出了相应的率失真函数模型，对码率问题进行了研究。CS-MDC首先对小波变换后的图像进行交织抽取分块，再对各子块进行随机观测、量化、打包形成多个描述子的码流。解码端根据接收码流的情况通过求解优化问题重建原图像。由于CS随机观测过程简单易实现，该方法可以以较低的计算复杂度编码生成较多的描述子，有效解决了高质量重构所需描述个数增多时编解码复杂度急剧增加的问题，且具有其他多描述编码方法所不具备的保信号稀疏分解及压缩感知理论应用研究西安电子科技大学博士学位论文密性能。更为重要的是，即使在每一个描述中都存在丢包现象，只要正确接收到的观测值个数满足CS重构条件，就能够重构出原始图像。实验结果表明，本文方法的抗丢包能力明显优于基于小波SPIHT编码的多描述编码方法。4.提出了基于压缩感知理论的图像加密算法。该算法首先对明文数据进行变换得到一组稀疏系数，然后用一个与变换基不相关的随机观测矩阵（即密钥）将稀疏系数向量投影到一个降维的空间中得到观测值向量，添加随机扰动后得到密文数据。即使接收方仅接收到部分密文数据，仍可通过优化算法解密，得到可理解的图像。仿真实验结果表明该算法不仅具有良好的混淆性，扩散性及密钥敏感性，更重要的是抗丢包性能极好。关键词：稀疏表示，匹配追踪，过完备字典，压缩感知，1l范数，随机观测，多描述编码，率失真函数，图像加密ABSTRACTABSTRACTThesparserepresentationcanextractthemostintrinsiccharactersofasignal.Ithasbeenwidelyusedinthesignalprocessingfields,includingsignalcompression,featureextraction,denoising,super-resolutionreconstructionandsoon.CompressiveSensingtheory(abbreviatedasCS),whichhasbeenpaidtheutmostattentionofscholarsfromabroadandathomeinrecentyears,isjustbasedonsparserepresentation.CStheoryfurtherrevealsthatsparserepresentationisofgreatscientificvalueandhastremendousapplicationpotential.However,therearestillsomeproblemstosolveinCStheoryandsparserepresentationtheory,soboththemneedfurtherresearch.ThisdissertationfocusesonsparserepresentationofsignalandCompressiveSensingtheory.Itmainlystudiesthemethodsofsignalsparserepresentationoverredundantdictionary,andappliestheCStheorytomultipledescriptioncodingandimageencryptionandobtainscertainresearchresults.Themaincontributionsandinnovationpointsofthethesisareasfollows:1.Anewiterativegroupmatchingpursuitalgorithmbasedonanorthogonalconcatenatedictionarywithseveralorthonormalbasesisproposed.Thealgorithmadoptsthetheideaofiterativegroupmatchingpursuit,selectsseveralorthogonalatomsoftheoptimalbasisfromthedictionarybycomparingthematchingdegreebetweenthesignalortheresiduaandeverybasis,andobtainsthefirstbatchfewimportantcoefficients.Then,inthesameway,thesecondbatchfewkeycoefficientsoftheresiduaareobtained.Thisiterationprocessisrepeateduntilreconstructionerrororiterationnumberisinconsistentwithrequirements.Finally,wecangainthesparseapproximationoftheoriginalsignal.Ineachiteration,fastalgorithmoforthogonaldecompositionisused,sothecomputingcomplexityisverylow.SimulationresultsshowthatthecalculatingspeedofthealgorithmweproposedincreasesbythirtytimesthatofMPandcanavoidover-matching.2.Anewguidingpyramidalsparsedecompositionalgorithmisproposed.Inthisalgorithm,theredundantatomdictionaryisfirstlydividedintoseveralsubsetsaccordingtoitscharacteristics,theneachsubsetisfurthersubdividedintosmallersets,afterseverallayer-by-layerpartition,atreestructureoftheatomdictionaryisformed.Theninthefollowingiterativedecomposition,thistreestructurecanguidethesignaltobedecomposedincorrectdirection.Oncethetreestructureisfinished,itwillincreasethedecomposingspeedonceandforall.Experimentresultsshow信号稀疏分解及压缩感知理论应用研究西安电子科技大学博士学位论文that,underthesamesparsityandapproximationerror,thecalculatingamountofthenewalgorithmisonlyabout1/40ofMP’s,andthecomputingtime1/100ofMP’s.3.Anewmultipledescriptioncodingmethodbasedoncompressivesensing(abbreviatedasCS-MDC)ispresented.Therate-distortionfunctionisalsoputforwardandtheoptimalrateallocationproblemisalsodiscussed.CS-MDCmethodfirstlypartitionsanimageintoseveralblocksbyinterleavingextractinginWaveletDomain,thenformsmultipledescriptionafterseveraloperations,includingrandommeasuring,quantizingandpacketizing.Thereconstructedimageisobtainedbysolvinganoptimizationproblemaccordingtothereceivedbitstreamatthedecodingend.TheprocessofCSrandommeasuringissimpleandeasytooperate,sothisnewmethodcanproducemoredescriptionswithlowercomplexity.Moreover,thismethodcangenerateanynumberofdescriptionswithlowcodingcomplexity.It’swellknownthatthemorethenumberofdescriptionsis,thequalityofreconstructedimagethebetter.However,intraditionalMDCmethods,thecodingandencodingcomplexityarerapidlyincreasingwiththeincreasingdescriptionnumber.So,CS-MDCcansolvetheproblemeffectivelyandhasthesecuritypropertyothermethodshavenot.Moreover,evenwhenthereexistspacketlossineachdescription,aslongasthequantityoflostpacketsisnotlargeenough,CS-MDCcanstillrecovertheoriginalimage,whilet