基于冗余字典的信号超完备表示与稀疏分解

《基于冗余字典的信号超完备表示与稀疏分解》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、基于冗余字典的信号超完备表示与稀疏分解张春梅①*，尹忠科②，肖明霞①（①西北第二民族学院电信系，银川750021，②西南交通大学计算机与通信学院，成都610031，*联系人Email:zhangchm@nxu.edu.cn）摘要：基于冗余字典的信号稀疏分解是一种新的信号表示理论。它采用超完备的冗余函数系统代替传统的正交基函数，从而为信号自适应地稀疏扩展提供了极大的灵活性。稀疏扩展一方面可以实现数据压缩的高效性，更重要的是可以利用字典的冗余特性捕捉原始信号的自然特征。本文从超完备信号稀疏分解和非线性逼近理论的一系列

2、最新成果出发，综述了基追踪和匹配追踪等主流算法在信号表示方面的稀疏性与字典的相干系数的关系问题，并评述了目前字典构成的发展趋势。关键词：超完备表示；冗余字典；稀疏分解；基追踪；匹配追踪1引言在众多信号处理的应用中，都希望找到一种稀疏的数据表示，用稀疏逼近取代原始数据表示可从实质上降低信号处理的成本，提高压缩效率。传统的信号表示理论基于正交线性变换，但许多信号是各种自然现象的混合体，这些混合信号在单一的正交基变换中不能非常有效地表现出来。例如，一个含有脉冲和正弦波形的混合信号，既不能用单一的脉冲基函数，也不能用单一

3、的正弦基函数有效地表示。在这个例子中，有两种结构类型同时出现在信号里，但他们却完全不同，没有其中那一个能有效地模拟另一个。所以，人们希望寻找一种能够同时建立在两种基函数之上的信号表示，其结果应该比采用其中任一种基函数有效的多。在图像和视频处理方面，常用的信号分解方式通常是非冗余的正交变换，例如离散余弦变换、小波变换等。离散余弦变换其基函数缺乏时间/空间分辨率，因而不能有效地提取具有时频局部化特性的信号特征。小波分析在处理一维和二维的具有点状奇异性的对象时，表现出良好的性能，但图像边缘的不连续性是按空间分布的，小波

4、分析在处理这种线状奇异性时效果并不是很好。因而说，小波分析对于多维信号来说并不是最优的，他们不能稀疏的捕捉到图像结构的轮廓特征，因此在图像和多维编码方面的新突破，必定取决于信号表示的深刻变革。最近几年，研究者们在改变传统信号表示方面有了很大的进展。新的信号表示理论的基本思想就是：基函数用称之为字典的超完备的冗余函数系统取代，字典的选择尽可能好的符合被逼近的信号的结构，其构成可以没有任何限制，字典中的元素被称为原子。从字典中找到具有最佳线性组合的m项原子来表示一个信号，被称作是信号的稀疏逼近(SparseAppro

5、ximation)或高度非线性逼近(HighlyNonlinearApproximation)[1]。从非线性逼近的角度来讲，高度非线性逼近包含两个层面：一是根据目标函数从一个给定的基库中挑选好的或最好的基；二是从这个好的基中拣选最好的m项组合。利用贪婪算法和自适应追踪从一个冗余函数系统中进行m项逼近或阈值逼近也属此例。我们对高度非线性逼近方法的理解只是些零星的片段，用高度非线性方法以指定的逼近速率来描述函数仍然是一个富有挑战的问题（R.A.DeVore语）[2]。从基函数的形成来讲，在图像表示方面体现为多尺度几

6、何分析[3]，无论是curvelets[4]、bandlets[5]还是contourlets[6]都强调基函数应具备下述特点：（Ⅰ）多分辨率分析，（Ⅱ）时频定位能力，（Ⅲ）全角度分析（方向性），（Ⅳ）各向异性的尺度变换。这些新的冗余函数系统的不断涌现，使信号稀疏表示的方法更加成为研究的热点。超完备信号稀疏表示方法肇始于上世纪九十年代，1993年S.Mallat和Z.Zhang首次提出了应用超完备冗余字典对信号进行稀疏分解的思想，并引入了匹配追踪(MarchingPursuit)算法[7]。在这篇文献中，作者举自

7、然语言表述做浅显的类比，说明超完备冗余字典对信号表示的必要性，同时强调字典的构成应较好的符合信号本身所固有的特性，以实现MP算法的自适应分解。新思想的提出引起人们极大的关注，但由于算法所涉及的计算量十分繁重，因而早期研究的焦点集中在如何实现该算法的快速计算，降低算法的复杂度，以及选择何种类型的原子构造合适的字典两方面。这期间，许多音视频信号处理方面的实验都对MP算法做出了有利的支持，尤其在甚低码率视频编码方面，MP算法更显示出极大的优越性[8]。1999年D.Donoho等人又另辟蹊径，提出了基追踪（BasisP

8、ursuit）算法[9],并从实验的角度举证了MP、MOF[10]和BOB[11]算法各自的优劣。稍后，又在2001年发表的另一篇重要文章[12]中，给出了基于BP算法的稀疏表示具有唯一解的边界条件，并提出了字典的互不相干性（incoherentdictionaries）的概念.本文以稀疏信号的精确重构条件为主线，综述了基于冗余字典的信号稀疏分解和非线性逼近领域的一系列最