离散酉(正交)变换的快速算法及其在信号与图像处理中的应用研究

摘要

离散酉（正交）变换是数字信号与图像处理等领域重要的工具。目前，具有良好的表征信号的能力，在相关领域有着广泛应用的离散酉（正交）变换主要包括三大类:傅里叶分析相关变换、小波分析相关变换以及矩函数。第一类变换是利用正弦曲线或者方波构造相应的基函数，主要包括:离散傅里叶变换(DFT)、离散余弦变换(DCT)、改进的离散余弦变换(MDCT)、复数调制重叠变换(MCLT)、离散哈特雷变换(DHT)、列率复数哈达码变换(SCHT)、共轭对称列率复数哈达码变换(CS-SCHT)等;第二类变换利用小波或者后小波构造相应的基函数，主要包括小波变换(WT)和后小波变换(Beyond Wavelets)。第三类变换利用多项式构造相应的基函数，主要包括:Tchebichef矩（TM)、Krawtchouk矩(KM）等。
　　 上述变换具有如下特性:具有较少的信息冗余度以及简单的反变换形式，从而可以方便地恢复原信号（图像）。但无论是正变换还是反变换，均涉及大量的算术运算。因此，相关的快速算法研究成为一项非常有意义的研究课题，长期以来吸引了众多学者的关注，并取得了许多令人瞩目的成果，比如:1965年，Cooley与Tukey提出了著名的快速傅里叶变换算法(FFT)，该算法入选了20世纪十大算法，被公认为是信号处理领域的一次大飞跃，使得DFT被广泛应用于信息处理领域。1989年，Mallat创造性地将计算机视觉里面的多分辨分析思想引入小波领域，提出了著名的“金字塔算法(Pyramid Algorithm)”，从而使得小波变换从理论研究迅速走向广泛的工程实践。
　　 本文主要致力于傅里叶分析相关的一些较新提出的离散酉（正交）变换（即:MDCT、MCLT、DHT、SCHT、CS-SCHT等）的快速算法研究，降低其算术复杂度以便实际应用中能够实时实现。比较这些新交换与其它已提出的离散酉（正交）变换的性能，探索其在数字信号与图像处理领域潜在的应用。概括全文的研究成果和贡献，主要有如下几个方面:
　　 1.重叠正交变换（包括MDCT和MCLT等）的快速算法理论研究
　　 (1)对于一维MDCT，建立了整个混合基直接型MDCT快速算法体系。该算法体系由基-2频域抽取MDCT算法和统一的基-q MDCT快速算法体系构成，其中q为任意大于0的奇数。后者还包括如下算法:基-3频域抽取算法，基-3时域抽取算法以及任意的基-q时域抽取算法等。对于在MPEG-1以及MPEG-2第Ⅲ层采用序列长度为N=12和N=36的MDCT的场合，提出的混合基MDCT快速算法与目前最有效的Britanak算法计算复杂度一样，但是提出的算法由于没有在输出时引入“递归结构”，从而更加适合于并行实现。
　　 (2)对于二维MDCT，提出了两种新的快速算法:向量基-(2×2)直接型MDCT算法和基于二维DCT-Ⅱ的间接型MDCT算法。提出的两种算法比传统的行列算法需要更少的计算复杂度，其中基于二维DCT-Ⅱ的间接型MDCT算法比传统行列算法降低了大约50％的计算复杂度。
　　 (3)对于一维MCLT，提出了两种新的快速算法:基-2直接型MCLT算法和基于GDHT-Ⅱ的间接型MCLT算法。第一种算法比直接用定义计算MCLT需要更少的计算复杂度，但是与各种间接算法相比需要更多的计算复杂度。第二种算法与之前复杂度最低的基于DCT-Ⅱ的MCLT算法相比，降低了大约5％的计算复杂度。
　　 2.离散哈特雷变换(DHT)的快速算法及其应用研究
　　 (1)对于一维DHT，当一个长度为N的序列由三个相邻的长度为N/3的短序列构成且后者的DHT系数己知时，实现了快速计算原序列DHT系数的方法，比传统的处理方法需要更少的计算复杂度。
　　 (2)对于二维DHT，提出了两种新的（分裂）向量基快速算法:奇因子分裂向量基-(2×2)/(8×8)频域抽取算法和向量基-(3×3)频域抽取算法。第一种算法与之前国际上复杂度最低的奇因子分裂向量基-(2×2)/(4×4)算法相比，不但需要更少的计算复杂度，还具有更少的实现复杂度（数据传送、旋转因子、计算机运行时间等），同时将这种算法应用于医学图像压缩编解码领域。第二种算法与之前国际上复杂度最低的奇因子分裂向量基-(2×2)/(4×4)算法相比计算复杂度相当，但是提出的方法解决了一些传统的方法所不能直接处理（需要补零才能处理）的序列长度。
　　 (3)对于三维GDHT，提出了一种新的向量基-(2×2×2)的三维频域抽取GDHT-Ⅲ算法，比传统的行列方法需要更少的计算复杂度。将新提出的算法应用于计算斜循环卷积。
　　 3.滑动窗(Sliding)复数哈达玛变换的快速算法及其应用研究
　　 (1)对于一维SCHT，提出了两种新的滑动窗快速算法:基-2列率抽取算法和基-4列率抽取算法。提出的算法比固定窗SCHT算法，滑动窗FFT算法和滑动窗DFT算法需要更低的计算复杂度。
　　 (2)对于一维CS-SCHT，提出了三种新的滑动窗快速算法:基-2列率抽取算法、基-4列率抽取算法和格雷码核(GCK)算法。提出的算法比固定窗CS-SCHT算法，滑动窗FFT算法和滑动窗DFT算法需要更低的计算复杂度。
　　 (3)验证了提出的滑动窗SCHT和CS-SCHT可以代替滑动窗FFT算法和滑动窗DFT算法，进行信号的频谱分析和变换域自适应滤波。

目录

声明

摘要

第一章 绪论

1．1 离散酉(正交)变换的定义及快速算法简介

1．1．1 离散酉(正交)变换相关的定义简介

1．1．2 离散酉(正交)变换的快速算法简介

1．2 常用的离散酉(正交)变换的分类及其主要应用领域举例

1．3 傅里叶分析相关变换国内外研究现状

1．3．1 离散傅里叶变换(DFT)及其快速算法研究简介

1．3．2 离散余弦变换(DCT)及其快速算法研究简介

1．3．3 离散哈特雷变换(DHT)及其快速算法研究简介

1．3．4 哈达玛变换系列及其快速算法研究简介

1．4 傅里叶分析相关变换理论与应用面临的新课题

1．5 论文的主要工作

参考文献

第二章 重叠正交变换的快速算法研究

2．1 引言

2．2 一维MDCT快速算法研究

2．2．1 一维MDCT快速算法综述

2．2．2 一维MDCT研究工作简介

2．2．3 一维MDCT的定义及其性质

2．2．4 基于DCT的一维MDCT快速算法

2．2．5 基于MDCT的一维MDCT快速算法

2．3 二维MDCT快速算法研究

2．3．1 二维MDCT及其相关的二维DCT-Ⅱ快速算法综述

2．3．2 二维MDCT研究工作简介

2．3．3 向量基-(2x2)直接型MDCT算法

2．3．4 基于二维DCT-Ⅱ的间接型MDCT算法

2．4 一维MCLT快速算法研究

2．4．1 一维MCLT快速算法综述

2．4．2 一维MCLT研究工作简介

2．4．3 一维MCLT的定义及矩阵表示

2．4．4 基-2直接型MCLT快速算法

2．4．5 基于GDHT-Ⅱ的间接型MCLT快速算法

2．5 本章小结

2．6 本章创新点

参考文献

第三章 离散哈特雷变换的快速算法及其应用研究

3．1 引言

3．2 一维DHT及其扩展GDHT(DWT)快速算法研究

3．2．1 一维DFT及GDFT快速算法简述

3．2．2 一维DHT及GDHT(DWT)快速算法综述

3．2．3 变换域快速解码算法综述

3．2．4 一维DHT研究工作简介

3．2．5 几种常用的基于“基分解’’的DHT快速算法简介

3．2．6 GDHT-Ⅱ域快速解码算法简介

3．2．7 DHT域快速解码算法

3．3 二维DHT及其扩展GDHT(DWT)快速算法及其应用研究

3．3．1 二维DHT(GDHT或DWT)及其相应的DFT快速算法综述

3．3．2 二维DHT研究工作简介

3．3．3 二维DHT的定义及性质

3．3．4 行列算法

3．3．5 向量基-(2x2)频域抽取DHT快速算法

3．3．6 奇因子分裂向量基-(2x2)／(4x4)频域抽取DHT快速算法

3．3．7 奇因子分裂向量基-(2x2)／(8x8)频域抽取DHT快速算法

3．3．8 向量基-(3x3)频域抽取DHT快速算法

3．4 三维(多维)DHT及其扩展GDHT(DWT)快速算法及应用研究

3．4．1 三维(多维)DHT(GDHT)及其相应的DFT快速算法综述

3．4．2 三维GDHT研究工作简介

3．4．3 二维DHT的定义及性质

3．4．4 行列算法

3．4．5 向量基-(2x2x2)频域抽取DHT算法

3．4．6 分裂向量基-(2x2x2)／(4x4x4)频域抽取DHT算法

3．4．7 向量基-(2x2x2)频域抽取GDHT-Ⅲ算法

3．4．8 奇因子分裂向量基-(2×2×2)／(4x4x4)频域抽取DHT算法

3．4．9 向量基-(3x3x3)时域抽取DHT算法

3．5 本章小结

3．6 本章创新点

参考文献

第四章 滑动窗复数啥达玛变换的快速算法及其应用研究

4．1 引言

4．2 滑动窗复数哈达玛变换研究工作简介

4．3 滑动窗FFT算法和滑动窗DFT算法

4．3．1 滑动窗DFT的定义及其性质

4．3．2 滑动窗FFT算法

4．3．3 滑动窗DFT算法

4．4 滑动窗WHT算法

4．4．1 滑动窗WHT的定义及性质

4．4．2 基-2时域抽取滑动窗WHT快速算法

4．4．3 基-2列率抽取滑动窗WHT快速算法

4．4．4 基-4列率抽取滑动窗WHT快速算法

4．4．5 格雷码核(GCK)WHT快速算法

4．5 滑动窗列率复数哈达玛变换的快速算法研究

4．5．1 滑动窗SCHT的定义及相关性质

4．5．2 滑动窗SCHT快速算法

4．6 滑动窗共轭对称列率复数哈达玛变换的快速算法研究

4．6．1 滑动窗CS-SCHT的定义

4．6．2 N阶CS-SCHT矩阵HN的分解

4．6．3 提出的滑动窗CS-SCHT快速算法

4．7 滑动窗SCHT和CS-SCHT的应用举例

4．7．1 频谱分析

4．7．2 变换域最小均方误差自适应滤波

4．7．3 提出的三种滑动窗复数哈达玛变换运行时间比较

4．8 本章小结

4．9 本章创新点

参考文献

第五章 其他离散变换简介

5．1 引言

5．2 傅里叶分析相关变换

5．2．1 希尔伯特变换及希尔伯特-黄变换

5．2．2 傅里叶变换及其扩展变换

5．3 小波分析相关变换

5．3．1 小波变换

5．3．2 后小波变换

5．4 矩函数

5．5 本章小结

参考文献

第六章 总结与展望

6．1 全文工作总结

6．1．1 重叠正交变换(包括MDCT和MCLT等)的快速算法理论研究

6．1．2 离散哈特雷变换(DHT)的快速算法及其应用研究

6．1．3 滑动窗复数哈达玛变换的快速算法及其应用研究

6．2 未来工作展望

6．2．1 新的重叠正交变换的构造理论及其应用研究

6．2．2 新的滑动窗变换的快速算法理论及其应用研究

6．2．3 新的分数阶变换的构造理论及其应用研究

6．2．4 四元数框架下离散酉变换的理论及其应用研究

6．2．5 小波及后小波框架下离散酉(正交)变换的理论及其应用研究

6．2．6 压缩感知框架下离散酉(正交)变换的研究

6．2．7 量子计算机框架下离散酉(正交)变换的研究

参考文献

致谢

附录A：计算6点MDCT

附录B：计算6点IMDCT

附录C：计算10点MDCT

附录D：计算10点IMDCT

附录E：计算18点MDCT

附录F：计算18点IMDCT

附录G：证明式(4．5．27)

附录H：证明式(4．6．11)

附录I：证明式(4．6．15)-(4．6．17)

附录J：证明式(4．6．20)

附录K：证明式(4．6．22)

附录L：证明式(4．6．24)

附录M：证明式(4．6．42)

附录N：证明式(4．6．64)

附录O：证明式(4．6．65)

附录P：证明式(4．6．66)

个人简历

研究成果概述

攻读博士学位期间发表论文清单

已投(或在准备)的论文

攻读博士学位期间的其他成果