離散酉(正交)變換的快速算法及其在信號與圖像處理中的應(yīng)用研究.pdf

1、離散酉（正交）變換是數(shù)字信號與圖像處理等領(lǐng)域重要的工具。目前，具有良好的表征信號的能力，在相關(guān)領(lǐng)域有著廣泛應(yīng)用的離散酉（正交）變換主要包括三大類:傅里葉分析相關(guān)變換、小波分析相關(guān)變換以及矩函數(shù)。第一類變換是利用正弦曲線或者方波構(gòu)造相應(yīng)的基函數(shù)，主要包括:離散傅里葉變換(DFT)、離散余弦變換(DCT)、改進(jìn)的離散余弦變換(MDCT)、復(fù)數(shù)調(diào)制重疊變換(MCLT)、離散哈特雷變換(DHT)、列率復(fù)數(shù)哈達(dá)碼變換(SCHT)、共軛對稱列率復(fù)數(shù)

2、哈達(dá)碼變換(CS-SCHT)等;第二類變換利用小波或者后小波構(gòu)造相應(yīng)的基函數(shù)，主要包括小波變換(WT)和后小波變換(Beyond Wavelets)。第三類變換利用多項式構(gòu)造相應(yīng)的基函數(shù)，主要包括:Tchebichef矩（TM)、Krawtchouk矩(KM）等。
　　 上述變換具有如下特性:具有較少的信息冗余度以及簡單的反變換形式，從而可以方便地恢復(fù)原信號（圖像）。但無論是正變換還是反變換，均涉及大量的算術(shù)運(yùn)算。因此，相關(guān)的快

3、速算法研究成為一項非常有意義的研究課題，長期以來吸引了眾多學(xué)者的關(guān)注，并取得了許多令人矚目的成果，比如:1965年，Cooley與Tukey提出了著名的快速傅里葉變換算法(FFT)，該算法入選了20世紀(jì)十大算法，被公認(rèn)為是信號處理領(lǐng)域的一次大飛躍，使得DFT被廣泛應(yīng)用于信息處理領(lǐng)域。1989年，Mallat創(chuàng)造性地將計算機(jī)視覺里面的多分辨分析思想引入小波領(lǐng)域，提出了著名的“金字塔算法(Pyramid Algorithm)”，從而使得小波

4、變換從理論研究迅速走向廣泛的工程實踐。
　　 本文主要致力于傅里葉分析相關(guān)的一些較新提出的離散酉（正交）變換（即:MDCT、MCLT、DHT、SCHT、CS-SCHT等）的快速算法研究，降低其算術(shù)復(fù)雜度以便實際應(yīng)用中能夠?qū)崟r實現(xiàn)。比較這些新交換與其它已提出的離散酉（正交）變換的性能，探索其在數(shù)字信號與圖像處理領(lǐng)域潛在的應(yīng)用。概括全文的研究成果和貢獻(xiàn)，主要有如下幾個方面:
　　 1.重疊正交變換（包括MDCT和MCLT等）

5、的快速算法理論研究
　　 (1)對于一維MDCT，建立了整個混合基直接型MDCT快速算法體系。該算法體系由基-2頻域抽取MDCT算法和統(tǒng)一的基-q MDCT快速算法體系構(gòu)成，其中q為任意大于0的奇數(shù)。后者還包括如下算法:基-3頻域抽取算法，基-3時域抽取算法以及任意的基-q時域抽取算法等。對于在MPEG-1以及MPEG-2第Ⅲ層采用序列長度為N=12和N=36的MDCT的場合，提出的混合基MDCT快速算法與目前最有效的Brita

6、nak算法計算復(fù)雜度一樣，但是提出的算法由于沒有在輸出時引入“遞歸結(jié)構(gòu)”，從而更加適合于并行實現(xiàn)。
　　 (2)對于二維MDCT，提出了兩種新的快速算法:向量基-(2×2)直接型MDCT算法和基于二維DCT-Ⅱ的間接型MDCT算法。提出的兩種算法比傳統(tǒng)的行列算法需要更少的計算復(fù)雜度，其中基于二維DCT-Ⅱ的間接型MDCT算法比傳統(tǒng)行列算法降低了大約50％的計算復(fù)雜度。
　　 (3)對于一維MCLT，提出了兩種新的快速算法

7、:基-2直接型MCLT算法和基于GDHT-Ⅱ的間接型MCLT算法。第一種算法比直接用定義計算MCLT需要更少的計算復(fù)雜度，但是與各種間接算法相比需要更多的計算復(fù)雜度。第二種算法與之前復(fù)雜度最低的基于DCT-Ⅱ的MCLT算法相比，降低了大約5％的計算復(fù)雜度。
　　 2.離散哈特雷變換(DHT)的快速算法及其應(yīng)用研究
　　 (1)對于一維DHT，當(dāng)一個長度為N的序列由三個相鄰的長度為N/3的短序列構(gòu)成且后者的DHT系數(shù)己知時

8、，實現(xiàn)了快速計算原序列DHT系數(shù)的方法，比傳統(tǒng)的處理方法需要更少的計算復(fù)雜度。
　　 (2)對于二維DHT，提出了兩種新的（分裂）向量基快速算法:奇因子分裂向量基-(2×2)/(8×8)頻域抽取算法和向量基-(3×3)頻域抽取算法。第一種算法與之前國際上復(fù)雜度最低的奇因子分裂向量基-(2×2)/(4×4)算法相比，不但需要更少的計算復(fù)雜度，還具有更少的實現(xiàn)復(fù)雜度（數(shù)據(jù)傳送、旋轉(zhuǎn)因子、計算機(jī)運(yùn)行時間等），同時將這種算法應(yīng)用于醫(yī)學(xué)圖

9、像壓縮編解碼領(lǐng)域。第二種算法與之前國際上復(fù)雜度最低的奇因子分裂向量基-(2×2)/(4×4)算法相比計算復(fù)雜度相當(dāng)，但是提出的方法解決了一些傳統(tǒng)的方法所不能直接處理（需要補(bǔ)零才能處理）的序列長度。
　　 (3)對于三維GDHT，提出了一種新的向量基-(2×2×2)的三維頻域抽取GDHT-Ⅲ算法，比傳統(tǒng)的行列方法需要更少的計算復(fù)雜度。將新提出的算法應(yīng)用于計算斜循環(huán)卷積。
　　 3.滑動窗(Sliding)復(fù)數(shù)哈達(dá)瑪變換的快

10、速算法及其應(yīng)用研究
　　 (1)對于一維SCHT，提出了兩種新的滑動窗快速算法:基-2列率抽取算法和基-4列率抽取算法。提出的算法比固定窗SCHT算法，滑動窗FFT算法和滑動窗DFT算法需要更低的計算復(fù)雜度。
　　 (2)對于一維CS-SCHT，提出了三種新的滑動窗快速算法:基-2列率抽取算法、基-4列率抽取算法和格雷碼核(GCK)算法。提出的算法比固定窗CS-SCHT算法，滑動窗FFT算法和滑動窗DFT算法需要更低的計