对偶在DSP中的应用

1、Primal-dual method in DSP1 DSP 技术的最新发展及其应用现状2 对偶理论3 对偶原理在小波框架的应用4 基于对偶树复小波变换的织物纹理识别DSP 技术的最新发展及其应用现状D S P 的发展历程D S P 系统构成及其特点D S P 芯片的应用D S P 的发展前景1 D S P 的发展历程DSP即数字信号处理器(Digital Signal Processing)，在模拟信号变换成数字信号后进行高速实时处理的专用处理器.DSP 的发展大致分为四个阶段： 第一阶段是70年代理论先行，70年代有人提出了DSP的理论和算法基础。 第二阶段是80年代产品普及，随着CMOS

2、技术的进步与发展，DSP芯片运算速度进一步提高，其应用于范围逐步扩大到通信、计算机领域。 DSP演变图1 D S P 的发展历程 第三阶段是90年代突飞猛进，将DSP芯核及外围组件综合集成在单一芯片上； 第四阶段是21 世纪再创辉煌。DSP 芯片引脚数量的增加，意味着结构灵活性的增加。 2 D S P 系统构成及其特点如下图1所示为一个典型的D S P 系统，输入信号首先进行带限滤波和抽样，然后进行A/D 变换将信号变换成数字比特流。DSP 芯片的输入是A / D 变换后得到的以抽样形式表示的数字信号，DSP 芯片对输入的数字信号进行某种形式的处理。 图1 DSP系统图2 D S P 系统构成

3、及其特点数字信号处理系统主要具有以下优点： （1）接口和编程方便。D S P 系统与其他以现代数字技术为基础的系统或设备都是相互兼容的，与这样的系统接口以实现某种功能要比模拟系统与这些系统接口容易多。 （2）稳定性和可重复性好。D S P 系统受环境温度、湿度、噪声、电磁场的干扰和影响较小，可靠性高；数字系统的性能基本不受元器件参数性能变化影响，便于测试、调试。 （3）精度高。16 位数字系统可以达到10- 5 的精度。 2 D S P 系统构成及其特点 （4）特殊应用。有些应用只有数字系统才能实现，例如信息无失真压缩、V 型滤波器。 （5）集成方便。DSP 系统中的数字部件有高度的规范性便于

4、大规模集成。 3 D S P 芯片的应用在近20多年时间里，DSP芯片的应用从军事、航空航天领域扩大到信号处理、通雷达、消费等许多领域 2 。主要应用有：信号处理、通信、语音、图形/ 图像、军事、仪器仪表、自动控制、医疗、家用电器等。 3 D S P 芯片的应用DSP 主要应用市场为3C 领域，合占整个市场需求的90%。 数字蜂窝电话是DSP最为重要的应用领域之一。由于D S P 具有强大的计算能力，使得移动通信的蜂窝电话重新崛起。4 D S P 的发展前景定点D S P 是主流。虽然浮点D S P 的运算精度更高，但定点D S P 器件的成本较低，对存储器的要求也较低，而且耗电较省。与可编程

5、器件结合。F P G A 器件配合传统的D S P 器件可以处理更多信道，可在基站中用来实现高速实时处理功能，满足无线通信、多媒体等领域多功能和高性能的需要。WCDMA无线基站4 D S P 的发展前景原对偶法（Primal-Dual Method)在DSP中会广泛应用。从原始问题的最终单纯形表中（最优单纯形算子）可直接得到对偶问题的最优解，原始问题中松弛变量的检验数对应着对偶问题的解（符号相反）。根据对偶理论可以在DSP中将其广泛应用，在进行表征信号的突变特征，信号与图像的压缩，以及在数字信号调制识别中时，小波变换与原对偶法的结合使用其前景非常乐观。 （L）（D） 对 偶 理 论发 展 简

6、史对 偶 理论对 偶 应 用参 考 文 献对 偶 小 波1 对偶理论发展简史 在线性规划早期发展中最重要的发现就是对偶问题，即每一个线性规划问题(称为原始问题)都有一个与它对应的对偶线性规划问题（称为对偶问题）。 1928年美籍匈牙利数学家 J.von诺伊曼在研究对策论时已发现线性规划与对策论之间存在着密切的联系。两人零和对策可表达成线性规划的原始问题和对偶问题。他于1947年提出对偶理论。 1951年G.B.丹齐克引用对偶理论求解线性规划的运输问题，研究出确定检验数的位势法原理。 1954年C.莱姆基提出对偶单纯形法，成为管理决策中进行灵敏度分析的重要工具。对偶理论有许多重要应用：在原始的和

7、对偶的两个线性规划中求解任何一个规划时，会自动地给出另一个规划的最优解；当对偶问题比原始问题有较少约束时，求解对偶规划比求解原始规划要方便得多；对偶规划中的变量就是影子价格。2 对偶理论 每一个线性规划问题都伴随有另一个线性规划问题，称为对偶问题。原来的线性规划问题则称为原始线性规划问题，简称原始问题。对偶问题有许多重要的特征,它的变量能提供关于原始问题最优解的许多重要资料,有助于原始问题的求解和分析。对偶问题与原始问题之间存在着下列关系： 目标函数对原始问题是极大化，对对偶问题则是极小化。 原始问题目标函数中的收益系数是对偶问题约束不等式中的右端常数，而原始问题约束不等式中的右端常数则是对偶

8、问题中目标函数的收益系数。 原始问题和对偶问题的约束不等式的符号方向相反。 原始问题约束不等式系数矩阵转置后即为对偶问题的约束不等式的系数矩阵。 原始问题的约束方程数对应于对偶问题的变量数，而原始问题的变量数对应于对偶问题的约束方程数。 对偶问题的对偶问题是原始问题，这一性质被称为原始和对偶问题的对称性。2.1 线性规划的对偶理论 2.1.1 线性规划原问题与对偶问题的表达形式任何线性规划问题都有其对偶问题对偶问题有其明显的经济含义 假设有商人要向厂方购买资源A和B，问他们谈判原料价格的模型是怎样的？ 例2.1.1设A、B资源的出售价格分别为 y1 和 y2显然商人希望总的收购价越小越好工厂希

9、望出售资源后所得不应比生产产品所得少目标函数 min g(y)=25y1+15y2 2.1.1 线性规划原问题与对偶问题的表达形式2.1.1 线性规划原问题与对偶问题的表达形式 2.1.2 标准(max,)型的对偶变换目标函数由 max 型变为 min 型对应原问题每个约束行有一个对偶变量 yi，i=1,2,m对偶问题约束为 型，有 n 行原问题的价值系数 C 变换为对偶问题的右端项原问题的右端项 b 变换为对偶问题的价值系数原问题的技术系数矩阵 A 转置后成为对偶问题的技术系数矩阵原问题与对偶问题互为对偶对偶问题可能比原问题容易求解对偶问题还有很多理论和实际应用的意义2.1.3 非标准型的对

10、偶变换表2.1.1 对偶变换的规则约束条件的类型与非负条件对偶非标准的约束条件类型对应非正常的非负条件对偶变换是一一对应的2.2 线性规划的对偶定理 2.2.1 弱对偶定理定理 对偶问题(min)的任何可行解Y0，其目标函数值总是不小于原问题(max)任何可行解X0的目标函数值 为了便于讨论，下面不妨总是假设 弱对偶定理推论max问题的任何可行解目标函数值是其对偶min问题目标函数值的下限； min问题的任何可行解目标函数值是其对偶max问题目标函数值的上限如果原max(min)问题为无界解，则其对偶 min (max)问题无可行解如果原max(min)问题有可行解，其对偶 min (max)

11、问题无可行解，则原问题为无界解注：存在原问题和对偶问题同时无可行解的情况 2.2.2 最优解判别定理定理 若原问题的某个可行解X0的目标函数值与对偶问题某个可行解Y0的目标函数值相等，则X0, Y0分别是相应问题的最优解证：由弱对偶定理推论1，结论是显然的。 即CX0 = Y0b CX, Y0b = CX0 Yb 。 证毕。2.2.3 主对偶定理定理 如果原问题和对偶问题都有可行解，则它们都有最优解，且它们的最优解的目标函数值相等。证：由弱对偶定理推论1可知，原问题和对偶问题的目标函数有界，故一定存在最优解。 现证明定理的后一句话。 主对偶定理的证明 证：现证明定理的后一句话。 设 X0 为原

12、问题的最优解，它所对应的基矩阵是 B， X0= B1 b，则其检验数满足 C CBB1A 0 令 Y0= CBB1，则有 Y0 A C。 显然Y0为对偶问题的可行解。因此有对偶问题目标函数值， g(Y0)=Y0b= CBB1 b 而原问题最优解的目标函数值为 f(X0)=CX0= CBB1 b故由最优解判别定理可知Y0 为对偶问题的最优解。证毕。该定理的证明告诉我们一个非常重要的概念：对偶变量的最优解等于原问题松弛变量的机会成本即对偶变量的最优解是原问题资源的影子价格 2.2.4 互补松弛定理定理 设X0, Y0分别是原问题和对偶问题的可行解，U0为原问题的松弛变量的值、V0为对偶问题剩余变量

13、的值。X0, Y0分别是原问题和对偶问题最优解的充分必要条件是 Y0 U0 + V0 X0 = 0证：由定理所设，可知有 A X0 + U0 = b X0, U0 0 (1) Y0 A V0 = C Y0, V0 0 (2)分别以Y0左乘(1)式，以X0右乘(2)式后，两式相减，得 Y0 U0 + V0 X0 = Y0 b C X0若 Y0 U0 + V0 X0 = 0，根据最优解判别定理， X0, Y0分别是原问题和对偶问题最优解。反之亦然。 证毕。3 对 偶 应 用城市优化选址工业结构优化智能机器人火力发电厂经济指标优化电力系统经济指标优化5 参 考 文 献 1、马建华,刘家壮.关于国民生

14、产总值最优的凸二次规划模型J经济学,1999,(01). 2、刘家壮，赵炳新.对偶理论在经济均衡分析中的应用J中国管理学,1996,(04). 3、陈中基.对偶理论,2002,(06) 4、良少刚.运筹学,清华大学出版社,2003,(07) 欢迎王庆伟、赵素芳同学给大学讲解对偶在dsp中的应用!对偶原理在小波框架的应用小波分析是一门对数学知识和具体工程应用都有相当要求的理论。本课件将会尽量采用比较浅显易懂的语言来描述这个问题，以使其更加容易理解。然而，对于小波理论如果不接触到数学，就像鸟儿没有翅膀在天空飞翔一样，当然是绝对不可能的事，爱因斯坦也告诉我们要“尽可能简单，而不是更简单”在小波变换中

15、，当我们将连续小波离散化处理后自然引出两个问题：1.离散小波变换系数是否能完全的表征原信号的全部信息，即能否从离散小波系数精确的恢复原始信号。2.是否任何信号都可以表示为离散小波基的线性组合，而其中的组合系数需怎样求取。上面两个问题实际上可以归结到一个问题，即离散二进小波的逆变换问题。要回答这个问题，我们必须要借助于框架和对偶小波的理论。预备知识: 在具体讨论框架和对偶小波以前，我们需要大概了解一下小波理论的预备知识，这里让我来先介绍一下各种类型的空间之间的关系。 具体的联系如右图所示：如果设 为一函数序列， 表示 所有可能的线性组合构成的集合，称 为由序列张成的线性空间。如果 是线性无关的,

16、则称 为空间的一个基底，如果设 为内积空间的两个元素，有 = ,则称是正交的，如果内积空间 中元素列 满足其中任意两列的内积为 ，而且每一列的模为 ，我们就说 为标准正交系。如果 为标准正交系，而且空间中再也不存在除了 以外的元素能够使得他和 内所有元素正交的话，我们就说 为完全正交系。 小波框架和对偶基 在小波变换中，我们希望能够通过母小波尺度变换和平移而得到一组正交的小波基底，这样我们就可以很好的将小波信号函数 通过小波投影到基底上而得到一组系数，然后我们就可以通过记录这组系数以及根据已经知道的基底来恢复原来的小波信号。 则有， ，将其代入上式，得：上面的式子在数学上其实是非常完美的，那为

17、什么我们还需要对偶基和小波框架的存在呢？原因其实是很简单的，那就是因为在实际应用中，我们很难找到这样的正交基底。 这个时候，我们就需要引出小波框架和双正交基以及对偶基的概念。 首先，先描叙一下双正交基，双正交基是说在某些情况下，基底并不满足正交关系，对于这种情况，于是我们引入了对偶基这样的话，随着约束条件的降低，我们的小波基底就更加容易找到了。而且一个小波基的对偶不一定是唯一的。能量守恒定理在目前这个世界是普遍存在的，在科学的很多领域都会有能量守恒公式，它的一种形式如下所示：则我们可以取 在对偶基的投影作为系数来恢复信号 ,公式如下： 对于任意 x, 为了使重构更加有效，我们需要原始信号和展开

18、域之间有一个能量对应的关系，以使展开系数能够很好的表达原来的信号，这样我们就引进了框架的概念。利用框架可以将转换前后的能量控制在一个指定的范围内。框架的定义 设 为一个希尔伯特空间， 为空间中的一个函数序列，若对于任意 , 存在 ,使得下列不等式存在： 则称为一个框架 ；称 为框架的上下界。一般的理解 如果找不到正交基，或者找不到双正交基，那么我们得到的序列基底怎样去评价它呢？这时我们用框架来评价它。当 时，我们就称此框架是正交的，这个时候是完全满足能量守恒公式的。退一步来说。如果只有 ，这个时候，虽然是紧框架，但是一般并不是正交的。只要是满足框架约束的，我们都可以顺利的找到一个原基底的一个具

19、有良好性质的对偶基。至于找对对偶基的方法经过很多人的努力，已经找到了很多的方法去寻找合适的对偶基。 下面的这个图，从左至右，对基底的要求越来越严格，而性质也越来越好。 对偶小波实际上如果从数学上来推导的话，是非常复杂和困难的，有兴趣详细研究的朋友可以参考一下Daubechies的Ten Lectures on Wavelets(小波十讲)的框架一章。 个人学习心得对于小波的学习来说，个人认为如果你只是想使用小波解决工程上的一般问题的话。这个是比较容易学到手的，但是如果你自己想真正的了解小波理论的来龙去脉，更好的随心所欲的使用小波，甚至构造自己的小波，则需要下非常大的功夫，傅立叶变换和泛函分析是

20、基本前提条件。这也是有些人说小波容易，也有人说小波难学的原因之一吧。 对于我个人来说，这段时间学习下来，虽然也花了不少精力，但是感觉现在看小波还是只在此山中，云深不之处。目前市面上的小波的书还是比较多的，比如小波变换与工程应用（彭玉华）是相对来说入门比较好的一本书，每次读都会有更深的体会。同样，还有一本国防科技大学出版社出版的实用小波分析入门是相对来说更简单的一本书，可以让你比较容易的对小波有一个全面的理解，也是我看到的所有小波书里面个人感觉最好的一本入门书。1 彭玉华.小波变换与工程应用M.北京:科学出版社,2005:4-34.2 陈武凡.小波分析及其在图像处理中的应用M.北京:科学出版社，

21、2003, 20-25.3 巩萍,潘冬明.小波分析及其在图像处理中的应用, N长沙大学学报,2009,(04).4Ingriddaubechies.小波十讲M.北京：国防工业出版社，2004,70-73.4潘冬明参考文献：4 基于对偶树复小波变换的织物纹理识别 摘 要：离散小波变换(DWT)虽然广泛用于图像处理，但 DWT 存在两个缺点：其一，缺乏平移不 变性，这意味着信号的微小平移将导致各尺度上的小波系数的能量分布有较大变化；其二，缺乏方 向敏感性，可分离的二维小波变换只有三个方向的高频信息即水平、垂直和对角。利用对偶树复小 波变换(DT-CWT)进行图像纹理分类，可以克服上述离散小波变换的

22、不足，该方法具有逼近的平移 不变性和更多的方向选择性，有利于特征的跟踪、定位和保留。复小波变换对偶树复小波变换复小波变换的使用复小波变换的滤波系统与离散小波变换的滤波系统在 结构上完全相同，不同之处只是在于复小波变换中使用的滤 波器的系数都是复数，而且输出结果也都是复数。在可分离 的二维离散小波变换中，二维小波滤波器是一维行滤波器和 列滤波器的乘积。而复小波变换中小波滤波器只在0, 范 围内有响应，如果要以相同的方式来构造二维复小波变换，则等价滤波器只能覆盖单位频率单元的第 1 象限。但是实数 图象数据却包含有第 1 象限和第 2 象限的非冗余信息，为了 不丢失信息，有必要扩展二维可分离操作，

23、使等效滤波器能 覆盖负的水平频率轴。为此，至少需要使行、列滤波器中的 一个滤波器的系数为共轭复数。然而，对于上述类型的复小波树来说，完全重构的设计 十分困难。这样的滤波器在小波树的第 1 层可以很容易 地设计成满足完全重构性条件。即只需限制输出信号必须为 实数，但在更高的分解层中，因为输入输出都是复数，就不 能采用类似的约束条件。而且，对于第 1 层以上各层的完全 重构，必须让由 4 个滤波器构成的滤波器组在全频段上具有 平坦的响应特性。这在 4 个滤波器都可能抑制负频率的情况 下，根本不可能实现。因此，就需要构造一种不同形式的复 小波变换树，于是我们引入了新的方法。 对偶树复小波变换 对偶树

24、复小波变换保留了复小波变换的诸多优良特性 ：近似的平移不变性、良好的方向选择性、有限的数据 冗余和高效的计算效率，与此同时，它还具有完全重构特性。 另外，为了保证两棵树的所有采样值序列都具有统一的间隔，一棵树中的滤波器必须与另一棵树中的滤波器之间保 持相对于各自采样速率的半个采样值间隔的差距。对于线性 相位的滤波器而言，这就要求一棵树中的滤波器应当为奇数 长，两棵树将会呈现较好的对称性。 为了实现对偶树复小波变换的反变换，对每一棵 树分别使用双正交滤波器进行反变换，最后对两棵树的输出结果进行 平均，以保证整个系统近似的平移不变性。 采用对偶树复小波变换分解二维信号与离散小波变换类似，利用可分离

25、的滤波器先沿着列再沿着行实现分解。对偶树复小波变换与离散小波变换一样实现简单、快 速，还有一些离散小波变换或其他复小波变换所不具备的性 质，包括逼近的平移不变性。对偶树复小波变换虽然基于离 散小波变换，但它在两棵树的各尺度消除了下采样，得到了 近似的平移不变性和好的方向选择性。尽管对偶树复小波变 换和离散小波变换一样采用可分离滤波器分解二维信号，但 它可以区分频率空间的正频和负频，在每个象限产生了三个 子带。对偶树复小波变换 解决了复小波变换难以实现完全重构、不容易设计出具有好 的特性的滤波器的问题。对偶树复小波变换是一种冗余的变 换，通过冗余的方式提供了逼近的平移不变性，且通过实变 换分别提

26、供了复数的实部和虚部。所以，虽然离散小波变换广泛应用在信号和图像处理 中，但是它不具有平移不变性和良好的方向选择性。而平移 不变性和良好的方向选择性对图像特征的检测、去噪、分割 和数据压缩等具有重要意义。复小波变换具有平移不变性和 良好的方向选择性，但完全重构的设计却是很困难的。而对 偶树复小波变换在保留复小波的优良特性的同时，通过对偶 树滤波的形式，保证了完全重构性。对偶树复小波变换不但 具有平移不变性和良好的方向选择性外，还具完全重构性、 有限的数据冗余和较小的计算量等优点。 结论 CWT 小波变换，不仅具有时频中的局域化能力，同时还可以自适应变化时频域的窗口宽度，能自适应地处理不 同尺度不同层次的纹理信息。一般图像的能量集中在低频， 而纹理图像能量则是集中在中频。随着分解层数的增加，小 波逐渐向低频方向聚焦，而 DT-CWT 小波分解则