离散Gabor变换的快速算法及其应用（可编辑）

离散Gabor变换的快速算法及其应用（可编辑） 学植代码:? 学 号: 名疆吠学 硕士学位论文 离散变换的快速算法及其应用 卸 姓 陈靖远 名 电路与系统 学科专业 研究方向 多维信号处理 ? 亮 指导教师 完成时间 年月安徽人学硕十学位论文 中文摘要 在信号的分析与处理中,很自然的是采用时域方法来描述信号, 为了更好 的理解与处理信号,人们又采用了频域描述方法,变换建立了时 域与频 域信号对应关系的桥梁。但是实际牛活中人们遇到的夫多是非平 稳信号,分析 与处理非甲稳信号变换将无能为力,在此基础上,人们研究了加窗傅立 叶变换??短时傅立叶变换等一些时频联合分析方法。其中包括著名的 变换。它由英国物理学家提出,经过许多科学家的研究逐步完善与发展。 变换作为重要的时频分析工具在语音与图象处理、雷达、声纳、振动信号 的处理与理解等很多领域被认为是非常有用,然而实时应用却因其很高的计算 复杂性而受到限制。为了有效地和快速地计算变换,本文在系统介绍 变换基本理论的基础上详细论述了一维离散变换的块时间递归并行格型 结构这一兜速算法。其中包括一维离散变换系数求解的块时间递归算法 以及由变换系数重建原信号的块时间递归算法,研究了两算法使用并行格型结 构的实现方法,并讨论和比较了算法的计算复杂性和优越性。通过实验验证了 它的正确性,研究了该算法的可行性。并将其应用于语音分析与数字图像水印 生成中,展示了离散变换快速算法的应用前景。 关键词:时频分析;离散变换;并行格型结构;块时间递归算法;数 字 水印垒丝查兰堡?:兰生堡壅?? , ? . ? ? ?. ?. ?., ? ? . 、王 。. 至 . ,, ? . ; “. 塌 . ,., “ 而 ;,. ; . , ‘ .订. , : 珏, 盛, 怖 , 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的 研究成果。据我所知,除了文中特别加以标注和致谢的地方外,论文中不包含其 他人已经发 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 或撰写过的研究成果,也不包含为获得受簿鱼灰争其他教育机构 的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均 已在论文中作了明确的说明并表示谢意。 学位论文作者签名: 签字日期: 沙口‘年月%日 阵& 学位论文版权使用授权书 本学位论文作者完全了解勰弓有关保留、使用学位论文的规定, 有权保留并向国家有关部门或机构送交论文的复印件和磁盘,允许论文被查阅和 借阅。本人授权 可以将学位论文的全部或部分 内容 财务内部控制制度的内容财务内部控制制度的内容人员招聘与配置的内容项目成本控制的内容消防安全演练内容 编入有关数据库进行 检索,可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。 保密的学位论文在解密后适用本授权书 学位论文作者签名: 导师签名: 琢雪有丑 隅韶 签字日期: 签字日期:%年月/日 砂年厂月/日 学位论文作者毕业去向: 工作单位: 电话: 通讯地址: 邮编:箜二里?旦亘 窒塑叁堂堡?堂堡堡皇 第一章引言 . 变换与联合时频信号分析法 众所周知一个给定的信号有多种表示方法。不同的表示方法有不同的用途。 在 工程 路基工程安全技术交底工程项目施工成本控制工程量增项单年度零星工程技术标正投影法基本原理 应用当中得到的信号往往是时域信号。然而当研究和没计系统时,人们 喜欢在频域研究信号与系统,这是因为在频域比在时域更容易刻画和描述信号 与系统的特征。 尽管表示信号的方法很多,但最重要的和最根本的变量仍然是时间和频率。 时间函数表示信号幅值随时间变化的情况。而频率函数则表示这一变化的快慢 程度。连接时间和频率的桥梁是傅立叶变换。而逆变换则建立了信号从 频域到时域的变换桥梁,这两个域之间的变换为一对一映射,时域和频域构成 了观察一个信号的两种方式。 傅立叶变换原始的基本思想是把~个信号分解成一序列正弦函数的加权 和。然而实际生活中遇到的常常是时间有限或历时很短的信号,搏立叶变换尽 管简单明了,但并不是表示实际信号的最佳方法。变换是在整体上将信 号分鳃为不同的频率分量,面缺乏时间局域性信息,即它并不能告诉我们某种 频率分量发生在哪些时间内,而这对非平稳信号是十分重要的。与诳变换 相关的傅氏谱、能量谱及功率谱都是信号变换到频域的一种表示,对于频谱不 随时间变化的确定性信号与平稳信号,都可用它们进行分析和处理。但当信号 的频率随时间变化时,如入的语音信号与脑电信号、生物医学信号和地 震信号“’。”“““、通过时变信道传输的信号及非平稳信号等。 这些信号都是历时 有限的,并不是从负无穷到正无穷,所以并不适合用正弦信号序列来表示它们。 除了线性变换外,傅立叶变换的平方??功率谱的应用也相当广泛。然而功率 谱没有时间信息同样不适合表示这些时变信号非平稳信号。 这说明频域表 示法存在严重的不足,因为它不能表示某个时刻信号频谱分布的情况。 于是, 针对频谱随时问变化的确定性信号与非平稳信号,人们开始研究联合时频分析童塑鱼生竺銮垫塑墼望墨鲨墨茎生型 窒塑查堂堡主堂堡垒奎 简称时频分析方法,它将一个。维的时问信号以二维的时间频率密度函数 彤式表示出来,从而揭示信号中包含了多少频率分量,以及每一分量是怎样随 时问变化的。 一个常见的例子是语音信号。图.中底部是一段语音信号的时域波形,它 仅仅是时间的函数。右边是其傅立叶频谱,仅仪是频率的函数,单从频谱图上 反映不出这些频率成分发生的时间信息。左上脚的大图是其联合 时频分析的时 变谱,同时是时间和频率的函数,从图上我们既能看出某一频率成分的大小又 能得知其发生的时间或时段。这就是说,联合时频分析使我们能更好地理解和 分析时变的非平稳信号。 语音信号的时变谱 语音信号的频谱 图,信号的时频分析 由上文的分析可知,经典的傅立叶变换并不适合分析历时很短的信号和频 率成分随时间变化剧烈的非平稳信号。尽管实际信号中某一频率成分有其发生 的时问,但是经典的频谱并未揭示这一重要信息。原因是傅立叶变换中选择的 基元函数在时间上是从负无穷到正无穷,没有集中性。这就是说,用经典的傅 立叶变换来度量信号不包含时间信息。为了克服这一不足,人们又发展了许多 其它的信号表示方法,如:展开、小波时变谱等,并进行了深入的研 究。这螳新的技术被称为联合时频分析。 .时频分析法中的二次时频表示 塑二童?互 耋堂叁堂堡?堂垡丝塞 旦在研究量子力学时提出的这种分布是这类时频表示中非常重 要的一 种。信弓为的?分布‘定义为 。如., 护一詈矿 两信号与毙的互?分布定义为 【 ‰?/ 枣一妒卧:咖胁 若,。【。。。,则 . 哦,,,川‰,,细嘎,,陋也‰也,厂】 由此可见,一?分布的时频集中性高,但交叉项干扰严重,影响其 分辨 率。 年, 提出一种对分布进行时频平滑,并进而 构造新的时频分布的方法,即广义双线性时频分布 酗?去』』』孵?“妒卜扣伽亭弦一例鲥嘶 其中中,表示核函数,它决定了乓,,的特性。采用不同的核函数, 将得到 不同的时频分布。年,, 和. 【提出了一种与信号有 关的最优核函数设计方法。对核函数的要求,是希望既能压缩交叉项干扰又能 有好的特性。常用的类广义双线性时频分布有.分布、广义 指数分布等。重要的二次时频表示方法还有仿射类双线性时频分布‘加】平口重排类 双线性时频分布“,这里不再赘述。 .时频分析法中的线性时频表示 线性时频表示主要有变换、短时交换和小波交换。 小波变换 小波变换由法国学者.于年提出,后经其他几位法国学者的再 塑造,使之成为一种基础坚实、应用,“泛的信号分析工具。小波交换定义为 眦埘击 矽孚户宣墼里坐变堡盟丛望堡鳖墨茎婴坐 窒墼尘堂堡?堂笪丝奎 其中“为尺度,为母小波函数。小波分析本质上是一种时间一尺度分析, 色更适合于分析具有自相似结构的信号;从考察信号的频率成份随时问的演化 特性角度来说,小波变换的结果则难于解释“。”,尽管这一研究领域十分火热 小波变换是以时间和尺度为参数,在时问~尺度平面的不同位置上具有不问的分 辨率,因而是一种多分辨率分析方法。小波分析得益于小波基函数的完备性、 自相似性和多分辨性,它能获得成功的两个最重要的原因是其拥有塔形快速算 法和良好的时频域特性;缺点是一且母小波选择不当,应用效果会大受影响。 短时变换: 若用一窗函数抽取一段信号,并对其作。变换,移动窗函数,重 复上述过程,则得到短时变换: ? 艏 丁:丁,,胛 一,丁已一。”魂窗函数的时移和频移,使得窗函数变成即是时间的函数又是频率的函数,因而 信号与对应于某一时移和频移的窗函数的内积就能反映信号在该时刻的局部频 谱特征,整个变换结果也就能揭示信号频谱的演化特征。短时变换虽然 也有离散形式,但其并不是从展开与内积的角度来研究的,有些重要方面,如 过抽样与信号精确重建之间的关系不明确,特别是对偶窗函数的 计算求和式是 无界的,从而不便于数值计算实施。 . 展开与变换 信号分析中的内积与变换: 对于有限或无限空间中的给定信号,可以表示为该空间中一组基元函数 、,。】。。的线性组合: .、 ?%、,。 上式即为信号的展开。其中为空间中的整数集。当集合。。。构成一个框 架时,则存在一个与之对偶的集合。功于是式.中的展开系数可由下式 求出:对于连续的时间信号: 窒塑丛堂堡?堂垡堡塞 一』至二蔓?呈王 ”如 印。?出 或对丁离散的时间信号: 吼:,,够。:妻啦】 嘲 、 ,女? 以卜两式在工程中被称为变换, 、,。叫做分析函数;与之对应,. 式被称 为反变换,、,。为综合函数。 内积有着明确的物理解释,它反映了信号与对偶函数、,。的相似程度。 这就是说,内积。越大表明信号与分析函数。越接近相似。 珥,描述了信号在空间中的行为特征。内积运算也可以看作是用由函数 集合、,。。。构成的标尺去度量要研究的信号,每一个单独的函数可以看作 是尺子的刻度。展开系数口。就是信号在这些刻度上的投影值。所以信号展 不基元函数选择的好,就能更加精确的“度量”信号。 框架理论与信号分析 对于个给定的框架。。印其对偶框架一般不是唯一的。一种较理想的 情况是、,。、,。,其中为常数,这种情况下, 。。被称为紧框架。 对于紧框架,展开系数口。正好也是信号在综合函数序列上的投影集,只差一 个常数乘子。当对偶框架不唯一的时候,展开是冗余的。 当对偶框架、,。。;唯一时,集合、,。。。构成一个基底。这时就没有冗余, 在这种情演.下; . 旷 ,,,、\ 、、,, 当、,。。。形成一个基底的时候,如果毒。、,。,那么/、,。,。\研”一。】并且 、,。。是丁交的。否则就是双正交的。对于双正交展开,由系数口。描述的信堂墼鱼銮堡堕‘堕堕兰望墨墨壁型 窒墼叁堂堡?鲎堡堡兰 号的特征可能与基元函数集。。。没有明显的联系图.。然而,对丁正 交展不,系数“。必定是信号在基底函数集。。。上的投影图。而. 、,。和、,。的位置是可以交换的。也就是说他们都可以作为分析或综合函数使用。 乓%?图.三维信号空间双正交展开,正交展开。 以上的分析也可以从矩阵的角度来理解。假设信号亨的长度为厶矩阵和 的维数分别为×上和三×,这晕吖?上。如果对于一切长度为工的向量都 有: . 日 我们就说由矩阵日构成的空间是完全的。注意在通常情况下矩阵 不是唯一的。 如果日和是方阵即胙上则~,在这种情况下口和是彼此双正交 的;如果日‘日,则日和是彼此正交的;在这两种情况下,矩阵都 是唯一的。 因为 ,.,将日转置,则得到: 日。”日?” . 上式表明日和都能用做综合或分析。关于这一展开的两个最基本的问题是: .怎样构造基元函数集。。,即框架 ,怎样计算对偶框架,即对应的对偶函数集。。。 其中最著名的展开就是傅立叶级数。对于一个周期为,的周期信号“, 其傅立叶级数: 蔓:至童 窒堂丛堂堕.生兰生堡塞 . 百?口。删‘。 上式中的基元函数集皿?”是彼此正交的无穷序列,其对偶函数集具有相同的 形式。因此,通过内积运算容易得到上式中的展不系数日。: . 吼 一口?“出 因为皿?”在频域中对应于一序列冲击函数集,所以傅立叶变换具有最好的频 率分辨率;傅立叶系数吼精确的描述了信号在频率删/处的行为特征,即 信号中含有该频率成分的多少。 对于一个三空间中的非周期信号?,可以表示为: 印去?‖叼? 对应的傅立时变换为: ? ?叫。出 通常称傅立叶变换的平方为功率谱。由卜定理可知,函数的功 率谱实际上就是自相关函数的傅立叶变换。 . 鲫国 ? 其中,自相关函数订定义为: ?防 /‘?/击 函数的时问和频率特性并非是独立的。他们由傅立叶变换相关联,不存在这样 的函数:它的历时无限短同时带宽可以无限窄。历时短则带宽宽,反之亦然, 带宽窄则历时长。由测不准原理我们知道,高斯函数在时间和频率域有最优良 的局域特性: ?? 鲋,矛冲甜 时频域的集中性由参数?来调节:越小则频带越窄历时愈长,反之亦然。 变换 于年因发明全息照相获得了诺贝尔奖是最早提出在 童墼堂生茎垫塑堡堕茎堡丝墨壁塑 窒丝叁兰婴兰堂生笙茎 信号分析和处理中使用时间和频率两个变量对信号进行描述的学者。年, 他提出了啼同时用时间和频率表示一个时间函数的方法,将信号展开成一组 在时问和频率域都很集中灼函数的加权和。这样展开系数就代表了信号的局域 特性。这种方法就是著名的展,:: . ??口。‰ 式中:。。?丁”“。 。为展开系数。基元函数集岛。由函数同时经过时移和频移而 构成。在的原文中,是如公式.中所示的标准高斯函数,因为其 在时问和频率域同时有较好的集中性。参数,和臼分别为时问和频率域的抽样 间隔。它们的乘积翰决定了抽样网格的疏密。乘积越小,抽样越密。 由于高斯函数序列历时较短,所以更加适合分析瞬变信号和变化剧烈的非 平稳信号。‰。的时间和频率分辨率可以通过调整参数?来调节。鼠愈小则频 率分辨率愈高而时间分辨率愈差,反之愈大则时间分辨率愈高而频率分辨率 愈差。由于‰,集中于叻丁,翻,因此提出系数。。反映了信号在沏,, ”艋域的行为特征。然而实际上,由于空间的集合‰。一般不能构成紧 框架,因此曲系数。不是信号在。上的投影。 洞察到这种展开的前景,在很大的程度上,正是由于他的工作和主张 引发了对联合时频分析的研究热。但无论如何本人在?展开的数学 理论方面并没有实质性的进展,在他的有生之年展开的许多重要的方面 都没有弄明白。此外,将幻局限于高斯函数,且丁,而实际上, 只要抽样网格足够密,,口? 也是可以的。当见芦?时是临界抽样,而乃【 时是过抽样。所有常用的分析函数如指数函数,矩形函数,高斯类的函数等都 能用作展开。注意,这里函数集合岛。一般不是正交的,这时 系数的计算就不是那么容易了。那么怎样来计算系数呢如果系数不是 唯一的,哪一种系数又最能同时在时间和频率领域体现信号的特性呢笙...童壹 窒丝叁兰堕?堂笪堡塞 在回答这些问题之前,让我们先来回顾一下另。种信号时频分析的途径一 一短时傅立叶变换。它与展开几乎在同时出现。“。 与变换/同的是,短时傅立叶变换是把传统的傅立叶变换作了修改: 不再把整个信号做一次性的变换,而是用移动的窗去截取信号中的一小段, 针对每一小段信号做傅立叶变换。这样短时傅立叶变换的结果就可看作是每一 小段区域中信号的频率特性,其处理过程町用下列公式来描述: ,胁,,胛臼】广丫? 弦叩‘。研 . 这里分析窗可以调节时频二域的分辨率:历时愈短刚时间分辨率越好频 率分辨率越差,反之亦然。窗口区域之间可以重叠也可以不连续。 窗口之问重 叠的比例由时间抽样间隔丁和分析窗函数的长度决定。我们把.重新写 成 规则 编码规则下载淘宝规则下载天猫规则下载麻将竞赛规则pdf麻将竞赛规则pdf 的内积形式:玎肌丁,。,一讲 其中: 丫肌。丫一埘删 . 注意 与.正好有同样的形式,都是对母函数的同时做时移和频移的结 果。设展开系数~?,,订纠。则?与.正好构成一。对 展开与变换。其中分析窗函数与综合窗函数的关系为: . ??,.。.”? 由此可见,短时傅立叶变换实际上是展开系数。展开可看作是短时 傅立叶变换的逆变换。这一关系直到年代才被人们明白“””。 由此可见,展开的关键问题是如何由给定的综合窗函数求出对应 的分析窗函数。只要求出了?,由.即可求出展开系数。式虽然 重要,但使用起来不方便,为此人们又推导了与综合窗函数之间的双正 交关系费“。: 萼当,矿。一。?弦”脚出:。。 万 离散变换的快速算法及奠应埘 窒堕叁堂堕.一堂垡堡壅 其中: %/,』而?/丁 ., 然面除了少数的情况外,上式的通解不易求得,即使求得,其局域特性并不好, 求得的系数不能反映信号的局部行为特征。。。因此变换的应用受到了限 制。后柬,在此基础上和又提出了离散的变换”。“。这样 便叮以利用数字计算机来计算,变换作为一种联合时频分析:具才真正 具有实用价值。现在展开和变换已被公认是通信和信号处理中信 号表示尤其是图像表示的最好方法之一。 .本文研究内容 变换的一个重要特性在于变换系数揭示了一个信号或幅图象 的局部频率的分布规律,而不象变换系数仅仅反映了全局频率的信息。 这一优点已被广泛应用在信号和图像处理的各方面。如语音识别,信号的检测, 图像压缩,纹理分析,图像的分割和识别、系统表示、通讯系统的回声消除等。 由此可见,变换是重要的时频分析方法。变换的理论已基本完备 之 后,其计算的高复杂性便成为一个突出的问题。研究其快速算法并推,“其在生 产和科研中的应用是当前时频分析法中亟待解决的课题之一。正如所指出: “若快速算法不解决,许多应用,特别是在线处理就无从谈起”。为了有效地和 快速地计算离散变换,本文主要研究一维的块时间递归特 性和算法以及如何运用并行格型结构快速实现一维块时闯递归的方法。并 行格型结构实现块时间递归算法最初由文献提出,由于其计算复杂性 分摊于各并行处理单元,因而计算速度大幅度提高,但很遗憾的是文献作 者的研究仅局限于临界抽样条件下一维离散变换系数的求解,没有解决 离散逆变换并行算法问题,也没有解决过抽样条件下离散变换和 逆变换并行算法问题。我们的研究表明,不论是在临界抽样条件下还是在过抽 样条件下,离散变换式及逆变换式都同样具有块时间递归特性,因此在 本文第三章中,我们将块时阔递归算法的并行格型结构实现方法 进行推广,不 仅应用于一维系数求解算法,而且应用于由变换系数重建原数据算法即 离散逆变换算法的实现;适用条件既包括临界抽样条件又包括过抽样 第一章引言 安徽人学硕十学位论文 条件。算法经过了模拟实验的验证。在本文的第四章中,对基于离散变 换的数值图像水印技术做了研究与探讨。安徽人学硕十学位沦文 离散变换的快速算法及其应川 第二章变换的基本理论 .概述 展开是一种同时用时间和频率表示一个时间函数的方法。它由英国 物理学家提出,经过许多科学家的研究逐步完善与发展。变换在语 音与图象处理、雷达、声纳、振动信号的处理与理解等很多领域被认为是非常 有用的方法。 .连续展开和变换 连续时间信号的连续展开?定义为 ??,玩。 . ” 式中 ‰,。矗一?,胛臼,,埘,行,士,士,. 称为基本函数,其中?。聊,称为展开或变换系数。通常 设窗函数五受能量归一化约束,即 帅阻 . 在连续展开中,若己选定了窗函数,时移和频率参量丁与力的选 择则决定了连续展开的完备性、唯一性和数值稳定性。连续展开 完备性的必要条件是??,其中抑【条件称为临界抽样条件,可使 展 开系数?”,求解唯一和数值稳定,但这种选择约束性强、自由度 差;而 条件称为过抽样条件,虽可使?,月数值稳定,但不唯一。至于丁 力?条件, 是不完备的,砌,叫失去稳定。 由于基本函数‰.。不是正交的,计算?疗比较困难,可采用辅助 窗函数又称为双正交分析窗函数,,来计算的方法蜘,即 安徽人学硕十学位论文 第一二章变换的基本理论?. :,。, 卜式定义为连续变换,冈此,连续展开为连续变换的逆变 换。上式中 ,一一,月,”力 . 将.式代入.式,就得到下列完备性关系: ??菇。?’ . 这里表示 函数。上述完备性关系可表示成如下双正交条件: . 警 砸币一聊耻一蛾岫枷 上式中%与骗为 瓦言,鼠等 下面来证明.式的双正交条件。由.式得 ?丁’一丁?”卜’占卜,? 月 对下列复指数函数序列应用泊松求和公式九, ?加 瓦?占卜,’一”瓦于是,.式可表示成: 瓦??’~瓦?一州丁,一埘丁一聆瓦? . 再利用泊松求和公式可知下式成立: ?啪?肛丁砂?硼筹砂?卅 式可用于证明下式成立: ?向。一埘,~棚丁一门五 ‘?’ :.嘉;,,。船。,,. 向,,。一。瓦,。。一,聍:。晶,.,,. 塑塑鱼竺壅墼盟丛垄璺鳖丝苎生坐 窒墼生堂堕?堂笪堡茎 将 式代入.式得莓一卜一瓦莓删骗专》 门,瓦一枷骗啪‖ “一,’、 欲使上式成立,必须 . 笔争 砸卜五一聊鼠哟甜沏” 将变量和位置调换后,此式就是.式的双下交条件。 对于某些窗函数,如高斯、单边与双边指数窗函数,双正交窗 函数可出.式求得解析式,而对‘般窗函数,双正交窗函数“则难 于求得解析式,需借助数值方法求解。同样,连续展开和变换也必 须经 采样与求和截断有限化即离散化,才能用数值方法求解。 .由连续变换到离散变换口 选取正整数和面使得 肼瓦面并定义 . ?女 忆,?? . 显然和都是周期为‖的连续周期函数。将 式代入.式得 ‖? ???研,”如膏一州了【.七 三三” .’ 一 ??巩??丁 ??,,一?,船 令,?占。,,?,.童;占一。。~。。,贝 一 。意???肘,%口一明 口 第二二章变换的基本理论 安做人学颂十学位论文 一 ???埘,虹止一,丁】, “ ??%慨”蝴?】? 上式中 . ?,?, 再选耿正整数?和?使得 矿臼岛? ‘ 现以为抽样角频率对和幻进行采样,显然,由骗/关系,在 墙?抽样情况下,其时间抽样间隔应由,降为/丽。这样,连续函数 研, 和 啊小离散化后在一个周期内的抽样数为 姆/甭脚//而廊觋编,?励 即 上厩励 . 已 吼々。/? . ?四 . 显然,这里札 和吮々分别为砘和幻,离散后的周期信号, 离散周 期为三。 将式代入,式,并利用.式,得 :。姐国、 吖一 ??七一?翮七/? ” 令珂目?;,,?,?二;,一?~?,贝 盯一】?一, \ 札七????,?七一而删七/? \, / 、 一?一】 ??%,?,魄一谚咄砌/? , 上式中 陀. 吖,?,??彳,,?离散变换的快速算法及其应用 安徽人学硕士学位论文 式 就是周期或有限长经周期拓展的时间序列的离散展不,序列 周期为 。而离散展开系数。?已变为以 为变量周期分别为、 ?的二维周期函数。 下面再来推导离散变换公式。将.式代入.式得 ?【.??研,, ?? 哪一?洲】卜伽州加冲 ?‘【卜?】一”力,?一,彻 ’莩?一,一盯一”力,专莩占。一/万, 斋莩丁/?’莩,?,/莉一丁一栅一力玎/厕 寺?/万?【丁丽一肼面~埘丁】一册,/? ’ 上式推导中利用了下列泊松公式 ?~‖ ;莩砸刊。 定义协?巾 丁 一。素,“删? 并设抖比;皓,,?,仁;?~?,则 一 ?吨,女一?一女/? . 此式即为离散变换公式。 同理,式.双正交条件也可离散化为 . 』“ 留?”丽觑厕拈嘉瓶坝刃 女 丽,,?,露一;万,,?,万一 .一维离散变换 安徽人学硕十学位论文 第一章变换的基本理论 上文的导出了离散变换的解析式,为了与连续情况相区别,在下 文中 修改了部分符号,统一写成以下的形式。长度为 的有限长离散时 间信号女, 其展开式: .,一一』女??。舭一矿“ ?。月 展不系数。由下式求得: 一。? ’々一?矿”‘‖等 』 々 其中,?一,肘、?分别为时域和频域抽样点数,?、丽分别为时间和频率抽 样间隔,数据长度上?面?。过抽样率伊?/万/厨;稳定的信号重建 条件是丽而?上或脚? 。临界抽样出现在?面彳上。在欠抽样条件 州上下会丢失信息。旬、动分别为综合窗与分析窗,皆为三点的周期序列。 二者的关系由下面双正交关系式确定: .、 ?蒯哚“‘? 式中,表示 ,并且 ???丽一;???一 ‖?等; 将式写成矩阵的形式: ’‖ . 式中声为一面面维列向量: ‖上/?,,,?,为一面?×三矩阵,其组成元素按下式求解: 颃,七七十?阡?; ??~;???一 但. 文献】证明了.式中最小范数解为: 掣, 一, . 当给定综合窗后,可由式求解分析窗。 .二维离散变换 令瓜】,代表一静止图像的采样数据,其中,,?,必:妞:,,?, 离散变换的快速算法及其应圳 安徽人学硕士学位论文 。将,作::维展,:如: 埘,一吖,?.?,一 . /一,恐????%。。。。。。。。。薯,恐 ”; 式中“札以。为二维展开系数。假定二维基函数是可分离的: 。一‰%。:为,而』,。: 一,”五/刀矸/』一啪正,册/. . 上式即为二维离散变换。,疋为窗【移动的步长,??, 乃对 应临界抽样情况。,磊吖,乃尬?。 定义以下矩阵:?。一 ,“ ?..彳一 %。吐忙 ,一,?。』~ 。。 鳊。?一 踟。,一 。,一。? 、 ?×如?维 . 、“ “,一?一 ‘。 肼:一?。 埘:一.?:一?一/, ,,?一 ; ’. ; ×.维 . 厂一,厂?,?一 令口。。是一个×们:?:的行向量,定义为: . 口?.【?.,,,’一,呐一,,??,?,口。。,吖?,,‘一,口.?,?, 一【】 定义矩阵: 爿陋,,?,理,?。小?,圩。吐,?,痒吐?,】 . 第一二章变换的基本理论 安徽人学硕十学位论文 于是,?式可以写作矩阵形式:倒 同理,?式,即二维变换叮表示为: 爿,~。 上式更便丁计算。式中蜀’一和盥 虽然展开和变换已被公认是通信和信号处理中信号表示尤其 是图像表示的最好方法之一。然而,由于基本函数彼此之间互不币交, 展开与变换的计算复杂性很高,实时应用受到很大限制。因此,研究其快 速算法,寻找一种有效、快速计算变换的方法很有实际意义。这正是下 一章要研究和解决的问题。 妻墼鱼些銮垫堕‘墼些翌鲨垄墨翌. 窒墼.叁堂堡主::三堡垒塞 第三章离散变换的快速算法 .概述 第二章从连续展开和变换的定义出发,,回顾了展开和变换的 理论及其算法。在此基础上,本章将详细论述基于并行格型结构和块时间递归 的离散变换和展开的快速算法。并研究了该算法的复杂性、在模拟实验 中碱证了其正确性。 变换是类似于短时变换的一种时频分析方法, 变换系 数揭示了一个信号或一幅图象的局部频率的分布规律,而不仅仅反映全局频率 的信息。变换己被广泛应用在信号和图像处理的各方面。如语音识别,信 号的检测,图像压缩,纹理分析,图像的分割和识别、系统表示、通讯系统的 回声消除等。由此可见,变换是重要的时频分析方法之一,研究其快速算 法并推』“其在生产和科研中的应用是当前时频分析法中亟待解决的课题之一。 快速算法国内外相继提出了很多解决方法,本文提出的块时间递归的并行格型 结构实现方法只是其中的一种,并行格型结构实现块时间递归算法最初由 文】提出,由于其计算复杂性分摊于各并行处理单元,因面计算速度大幅度提 高,但】作者的研究仅局限于临界抽样条件下一维离散变换系数的求 解,没有解决离散逆变换并行算法问题,也没有解决过抽样条件下离散 变换和逆变换并行算法问题。我们的研究表明,不论是在临界抽样条件下 还是在过抽样条件下,离散曲变换式及逆变换式都同样具有块时间递归特 性,因此完全可以将块时间递归算法的并行格型结构实现方法进行推广,不仅 应用于一维系数求解算法,而且应用于由变换系数重建原数据算法即离 散逆变换算法的实现;适用条件既包括临界抽样条件又包括过抽样条 件。 笙三主妻垫鱼壅塑塑:坠鲨璺墨 窒堂叁::堡?堂笪笙奎 .临界抽样条件下一维离散变换的快速算法 ‘维离散变换式可以 临界抽样条件下,三:埘,?:丽,??, 写成下列形式:‰,?? 一?‖“ 为了方便利用块时间递归算法,将上点离散数据分成组,每组?点,上式进 一步可表示为:‰:艺艺。州州,一。? 吒,。??州,丫州??阿? 其矩阵形式为式中 . ,,,, ,,一,,,?,仁.?一,仁,?一。 ,?,肛 ’ . ,..,肛 盖,,?,,,...,乙,,?,三一, . 是一对角元素为值快速一维离散变换矩阵的块对角矩阵, ?,?,?,?而,为一块循环矩阵,%.呻的子块咒为一?×?对角 矩阵,按下式计算: 卅?, ?,?, 川??一.式也可写成: ? 『 ? 】 . : 四 ? 鞭 离散变换的快速算法及其府川 安徽人学硕士学位论文 为了更便于观察,进叮写成: :?。?%? ?%一而?%一? . ?%工??】 设输入信号序列?在输入延迟线上每串行输入?个数据为‘个块, 对应所 需要的时间为一块时间,输入延迟线总长为斛块,如图所示。 互互五正 图. 升块输入延迟线 于是由. 式,定义块时间时刻系数为: ?,一?%一,吖】 ?%一‘工.?一,? ; . 吖一?墨‘??,吖一 而在块时间什时刻的系数可采用下列块时间递归形式 。??,一工, 一?%一‘“一置?一?一】?,”一, 们一?,竹一, 在递归开始前,先将延迟线所有单元清零,并将所有的卢,,?,仁 置零。不难证明,若设序列的第一块数据在块时间时刻串行进入 延迟线, 当全部串行进入延迟线时刻仁,.式经过了次递归,此时的输出, 即为的系数。而在块时间户肘之后,由于串行输入序列句的周期 性, 式中?,于是.式的递归过程进入稳定阶段。.式被称为系 数的块时问递归求解算式。安徽人学硕十学位论文 第一章离散 变换的快速算法 块时间递归算法也可用于信号重建逆变换的计算。在临界抽样条 件 下,逆变换式: . ???一???。?“ 其矩阵形式为 . 式中与构造相似 】 一,一 .其中 爪一州?,一卅?,?,一??一 ,?,,?,?,,? . ?为?点变换矩阵 .式又可写成 一 工 吒?”?吒 一: ,? ? . : %... 工吖? 列 “ 炉? 同样可以写成 而,?,???? 五。?,?。?? ,?? . 嘞一 ,?,???? 于是由.式可定义块时间时刻逆变换为: ‰【,?】,?.十??一,,?,?一 】一,,?,?一,?,月。一。】童墼鱼竺銮垫盟丛堕篁鲨墨苎生型 窒墼?堂堡主鲎堕堡奎 . 而,【,?,?【?.一 而在块时间升时刻的逆变换可采用下列递归形式: 。 十】???, :,‰,?:?, .、 ?,?,吖一, 一』?一, 注意此时输入信号序列是系数。.式就是由系数重建信号的块时间递 归算式,其递归过程与.式类似。 由.式设计的临界抽样条件下并行格型结构如图.所示,最左边的输入 延迟线被均分为舟个块,每块由等单元数?的单位延迟器组成,右边由叫个并 行格型处理单元组成,每个格型处理单元结构相同,主要由一维长度为?的分析 窗函数阵列、阵列加法器及憾快速组成,表示一个块时间单位延迟。并 行格型结构清零后,输入信号序列串行输入到延迟线,在延迟线最前端和最末 端的二个块数据组相减后,被送入每个并行格型处理单元,与分析窗函数阵列 相点乘后产生的信号矢量将在个并行格型处理单元之间递归传输、相加。当 个块时间递归后,即输入信号序列全部进入延迟线后,递归过程 进入稳定阶段, 此时并行格型处理单元中加法器末端的信号矢量经一次?点快速,输出即为 所要计算的系数。 比较.式和.式可发现,两式结构有些不同,.式的并行格型结 构实现如图.所示。延迟线输入为,延迟线最前端和最末端的二个块数据组 相减后的块数据,先进行?点快速,然后再与每个并行格型处理器中综合窗 函数阵列相点乘,产生的信号矢量将在肘个并行格型处理单元之间递归传输、相 加。当个块时间递归后,即输入信号序列全部进入延迟线后,递归过程进入 稳定阶段,此时并行格型处理单元中加法器末端的信号矢量即为所要重建的信安徽人。学硕十学位论文 第二章离散变换的快速算法 号序列。 弘 图,并行格型结构实现临界抽样条件下系数求解。 图并行格型结构实现临界抽样条件下由变换系数重建原信号。 .过抽样条件下一维离散变换的快速算法 如上文所述,对于过抽样,有三万?面,上,?,过抽样率口埘 /面。?/?,‖取正整数。令:,,...,‖一;,,,?,丽一。为了 方便地应用块时间递归算法以及实现,令研亏伊;把变换式 写成下列形式: 肌。?。?一‖一厢‖一“ . 安徽人字硕士学位沦文 禺散变换的快速算法及其心州 再令壮』,‘,,?,丽一;,,,?,』;代入.式: ‖。??』??,~,一厢陟? 写成矩阵的形式: ‘,。 . 式中。是长度为 面?的列向量。令: ,,?,厨一 . %。。,胍【,一,删,, 则有: 【。,?, . .式中是长度为上的输入信号列向量: 。,:‘,‘‘一。‘,‘一,。?一,。?,’,?一‘‘,上一】 、?。 ,,...,吕一.】 式中而,,,?,面一是长度为?的列向量。.式中为块对角阵: 【?,?,?,?】 . 子块加为标准的?点变换矩阵,共有衍个。.式中,为块循环矩阵, 其结构如下式所示: 巧 ,: %一. 峙一。列 玢一: . : 一 芝 其中的子块按下式取值: ?出‖~刃,’‖一廊,.,‖一面?一 . 我们把.式的矩阵形式写成: 。 『? 『,。? ,。 一 ,厅一 ? . : ’. 一 一 ‘厅 ,? ‘ ‰,..硫 ?暇%.?.%一,南,】 :?%一.而写?玢。硫.】 .第二章离散变换的快速算法 安徽人学硕十,产位论文 孟一】?’。列?联哳 设输入信号序列柚在延迟线上每串行输入?个数据为一块,对应 所需时间 为一块时间。于是由上式可定义块时间时刻的: 《?《‘。川?玢。‘厨。 :?%一。薯列薯。?告‘面, . 品?。‘列一?十写,撕一 块时间什时刻的系数求解可采用下列块时间递归形式: ;十;?峙,厅工, ::?击,坷一, . 咯一靠一?。工,撕一, 缸;?写,盯一工, 式即为过抽样条件下系数的块时间递归求解算式。 同理,逆变换原信号重建亦可采用同样算法,考虑到肘邛×砑,可 将逆变换式写成下列形式: ‖】吖? 口一 ?’ . ???%。女一‖~席‖“???一‖一厢芝%。。形“ ,圳。 忙, 仁 其矩阵形式为: . ? 圯’?’ 上式中 ‘ . 《 ??一, ‰。;‘‰。 . ;其中的子块,按下式取值: ‖譬一.,?万,善一.,?一对,?一,譬~.,?一灯?一 ?,?,?,? . 离散变换的快速算法及其应 安徽人学硕士学位论文 式.中 为按.式定义求得的系数。,为。块对角矩阵,子块曩忉 为点变换矩阵,』对角线上共有面个子块段组成。为了导出与. 式 类似的算式,我们将.式的矩阵形式写成如下的形式:工饥,『? 工? ’面,厅 』? ? . :兰 : 拉 ; 。? “一...恼 “ 矾且 。 。?:?:,?;??苦一。?苦】 口 ?【%,?:瓯?:苦:?刍一.】 .? 厅,芝,?:;,?十?,?咯。 同上文,可定义块时间时刻逆变换即由系数重建原信号序列 口 %??一,?;,?略,?『厨一, ~ 。?。眵品一,,?;十?:。??扛:?;坷,】 . 口一】 话一,?暇,?;暖,?‘?;,,啊。 而在什时刻的逆变换信号重建可采用同样的块时间递归形式: 口 。。?%.??; 口 ?:窆%一:,?知~ . 口一 场:岛。?,?一 口一 蜥,‰?,?厨~ 上述块时问递归算法可采用并行格型结构来实现。由.式设计的 过抽样条件笙二三至童墼鱼竺銮垫塑丛丝要鲨 窒堂叁堂堡?三兰笪笙奎 下并行格型结构如图.所示,最左边的延迟线有面个块,每块由? 个延迟 单元组成;并行格型结构主要有丽个并行格型处理单元构成,面 个三角形表示 递归式中的循环矩阵的子块乘子,每个三角形对应‘个?维对角阵子块巧’乘子; 表示一块时间延迟即?个单位延迟;方框内五表示?点标准运算。 图.最右边向量 即为变换系数。值得注意是,按照.式,奶 单元应该在递归过程之前执行,即每递归一次需要执行一次运算类似于 文献。但仔细研究发现,运算完令可以放在递归过程结束之后即整个 输入信号丽块输入之后进行,并且只需执行一次运算即可,从而大 大减少了计算量。 由.式设计对应的并行格型结构如图.所示,其基本结构与求系 数时类似。“加单元为?点逆;三角形表示递归式中的循环矩阵的子块。 乘子;输入向量 为按.式定义求得的系数,每前进一块时间,系统 运算一次,即完成一次递归运算。当输入序列’全部进入延迟线后,递归过程 结束,输出向量即为重建后的信号序列。 过抽样条件下的并行格阵列规模是临界抽样条件下的口倍,但处理方法类 似,当卢时,即变成临界抽样情况。故临界抽样情况可看成是过抽样条件下 届时的特殊情况。 : 吖一 缶 图.并行格型结构实现过抽样条件下系数的求解.:、,口一妻塑里生竺垄塑堂型垡受型薹些翌旦 窒燮尘堂堡?堂笪丝塞 图. 并行格型结构实现过抽样条件下由系数重建原信号序列 .计算复杂性分析 在串行算法中计算时间取决于算法的总计算复杂性;而在并行算法中,由 于总计算复杂性分摊于多个结构一致的并行处理单元,因此并行算法的计算时 问取决于单个并行处理单元的计算复杂性。不难看出,在图中,不论在过抽样 条件下少,还是在临界抽样条件下芦一,对应于每输入一块数据,求解 系数的并行格型结构中每一并行格型处理单元的计算量为?点复数乘和? 点复数加,当整个输入信号面块输入完毕,即面次递归结束后,再 执行一 次?点一维计算复杂性为.??。因此对应于整个输入信号丽块, 每一并行格型处理单元的计算复杂性数量级为 三.?? 同理,在图中,由变换系数重建信号的并行格型结构中,每一并行格型处 理单元在一个块时间内的计算复杂性为?点一维计算复杂性为.? 叼、点复数乘法和‖×?点复数加法。这样一来,对应于整个变换系数输 入面块,每一并行格型处理单元的计算复杂性数量级为: 上 ? 表.给出了所提出的算法与其他算法的计算复杂性对比各算法计算复杂 性只计与算法总计算时间相关部分;“”、“”、“”和“”表示算法适 用条件,分别为临界抽样条件、过抽样条件、可用于求系数、可用于由 系数重建原信号序列。由表.可看出本文算法所提出的与算法总计算 时问相关的计算复杂性明显小于典型的串行算法“”。。。“和并行 算法“。 笙二至塞墼鱼壅丝堕‘鉴垄笪鲨 窒燮.生堂堕?兰生至苎 文献只研究了临界抽样条件下的系数求解,在此条件下,比本文 算 数量级计算量。 法计算复杂性要多出.一 表. 与算法总计算日、』间相关的各算法计算复杂性对比 参考文献 计算复杂性 算法适用条件 犯 】 犯 ,, 【 尬十.上? ,, .三三 且彳 ,: 上 三? , ? ,, 本文算法 上 上? ,, .一维快速算法的应用举例 临界抽样是过抽样,当露时的特殊情况,本次实验采用的综合窗 与对应的分析窗如图.所示。 图.临界情况下综合窗“向与对应的分析窗四 采用的信号序列为截取的~段声音信号,三抽样点。被分 成产个长度为的时间块;求得的系数向量也分成船个长度为? 的块。,,,?,声一;,,,?,一。按照本文所提出的算法计算,重 建的信号与原信号序列的均方差在数量级。图.中同时给出了信号的 系数幅度图。和频谱图?。从时域中可以看出该时间信号 即苴能量主要集中在时域的两个区域,但由此却不能得知组成该时间信号 安徽人学硕十学位论文 离散变换的快速算法及其应 的频率构成。从频谱图中虽可以了解到组成该时间信号的各频率分量的 幅值,但却无法知道其随时间变化的情况。在‰。唧系数幅度灰度图像其 灰度与‰,。的大小成比中,我们不仅能看到组成该信号的各频率分量的幅值, 而且呵以看到该信号的频率分量随时间变化的情况,因此‰。能够较完好地同时 体现信号的时间和频率的局域特性。 图.临界抽样情况下系数‰。』形成的灰度图、频谱 图. 图.中系数。。的三维图形 星三兰曼墼里壅塑堕墨婆鲨 室塑叁堂婴主堂笪堡奎 由于临界抽样是过抽样当时的特殊情况,且此时的算法和推导相对简 单,容易理解,故在上文中单独作了分析。实验表明当卢远大于时,分析窗 和综合窗极其相似,因而有着更好的时频局域化性能。常称为似正交展 ,:。本次实验采用口,综合窗与对应的分析窗如图.所示。 蛇 ? 一《? 【...,........,............。。,?,,,一。。。..,..,.........。。一一~...............。。。,,,?.,.???????????????????????????????? ???? 毛 ??,..???????????.?..???. ???????。?。???????。??一图.过 抽样情况下的综合窗颤动与对应的分析窗的 为了便于比较,本次实验选取了与临界抽样同样的一段声音信号,采用过 抽样离散变换的方法分析。抽样模式: ,?,可,则 椤?/丽;采用综合窗: ??/一 /】 被分成面个长度为?的时问块;求得的系数向量也分成 ×面个长度为?的块‖,?,,?,‖一;‘,,,?,玎~。按照 本文所提出的算法计算,重建的信号与原信号序列的均方差在。数量级。图 .中同时给出了信号的系数幅度图。和频谱图融?。实验 结果表明,由于过抽样情况下的分析窗具有更好的集中特性,因而得到的 系数具有更好的时频局域化特性。 本章论证了一维系数求解算法和由变换系数重建原信号算法,不论是 在隘界抽样条件下还是在过抽样条件下,都同样具有块时间递归特性,并提出 了相应的块时间递归算法及其并行格型结构实现方法,计算机模拟验证了并行 格型结构实现的可行性,计算复杂性分析与比较也说明了块时间递归算法 的并行格型结构在计算时间方面所具有的高速和高效性能。本算法可推广到二 维。限于篇幅,不再重复。 安徽人学硕学位论文 离散变换的快速算法及其应用 缸女 图.过抽样情况下的系数。形成的灰度图、频谱 图. 图.中系数%,。的三维图形 安徽人学硕学位论文 第四章离散变换在数僮尘旦这查主塑壁型 第四章 离散变换在数 值水印技术中的应用 .概论 数字水印是近几年来出现的数字产品版权保护技术,可以标识作者、所有 者、发行者、使用者等,并携带有版权保护信息和认证信息,目的是鉴别出非 法复制和盗用的数字产品,作为密码学的加密或置乱技术的补充,保护数字产 品的合法拷贝和传播。当然数值水印的作用除了产权保护外还有许多。在本文 中的水印仅指用于版权保护的不可见强数值水印。研究了在变换领域中实现数 值水印的具体方法,模拟实验对这一算法做了评估,结果表明,该算法的确是 一例成功的强数值水印算法。 .信息安全 信息安全涉及的领域相当广泛,广义上,凡是涉及到信息的保密性、完整 性、可用性和可控性的相关理论和技术都是信息安全所要研究的领域。通常, 我们讨论的信息安全是指信息内容的安全性,即我们讨论的是狭义的信息安全, 侧重于保护信息的秘密性、真实性和完整性,避免攻击者利用系统的安全漏洞 进行窃听、冒充、诈骗、盗用等有损合法用户利益的行为,保护合法用户的利 益和隐私。 信息安全技术,一直都是国际上的重点研究课题.有两个主要的研究方向: 信息加密与信息隐藏 曲,二者具有深刻研究内容 和广泛应用背景。关于加密技术的研究经历了长久的过程,已经形成了一个完 整有效的体系,有一系列公认的、经典的算法。而对于信息隐藏, 虽然它的历 史可以追溯到遥远的古代,但是却一直没有形成一个有自己特点的研究体系。 世纪年代以来,随着计算机网络的普及和多媒体技术的发展成熟,数字化 信息可以以各种形式在网络上的迅速便捷地传输,国家、政府、企业以及个人 都把网络作为主要的通讯手段。不仅那些往:需要特殊途径和信使才能传递的