论文部分内容阅读
离散酉（正交）变换是数字信号与图像处理等领域重要的工具。目前，具有良好的表征信号的能力，在相关领域有着广泛应用的离散酉（正交）变换主要包括三大类:傅里叶分析相关变换、小波分析相关变换以及矩函数。第一类变换是利用正弦曲线或者方波构造相应的基函数，主要包括:离散傅里叶变换(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算法，进行信号的频谱分析和变换域自适应滤波。