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