2023年全國碩士研究生考試考研英語一試題真題(含答案詳解+作文范文)_第1頁
已閱讀1頁,還剩28頁未讀, 繼續(xù)免費(fèi)閱讀

下載本文檔

版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)

文檔簡介

1、<p><b>  引言</b></p><p>  數(shù)字信號(hào)處理(digital signal processing,DSP)是利用計(jì)算機(jī)或?qū)S锰幚碓O(shè)備,用數(shù)值計(jì)算的方法對(duì)信號(hào)進(jìn)行采集,交換,綜合,估值與識(shí)別等加工處理,借以達(dá)到提取信息和便于應(yīng)用的目的。數(shù)字信號(hào)處理系統(tǒng)具有靈活,精確,抗干擾強(qiáng),設(shè)備尺寸小,造價(jià)低,速度快等突出優(yōu)點(diǎn)[1,2],這些都是模擬信號(hào)處理系統(tǒng)無法比擬的。

2、</p><p>  數(shù)字信號(hào)處理的起源可追溯到17世紀(jì),當(dāng)時(shí)已提出了有限差分,數(shù)值積分和數(shù)值插值得方法。自20世紀(jì)60年代以來,隨著計(jì)算機(jī)和信息學(xué)科的飛速發(fā)展,數(shù)字信號(hào)處理技術(shù)應(yīng)運(yùn)而生并迅速發(fā)展,現(xiàn)已形成一門獨(dú)立的學(xué)科體系[3]。數(shù)字信號(hào)處理就是研究用數(shù)字的方法,正確快速地處理信號(hào),提取各類信息的一門科學(xué)。在國際上,一般把1965年快速傅里葉變換(FFT ,Fast Fourier Transform)的問世,

3、作為數(shù)字信號(hào)信號(hào)處理這一新興學(xué)科的開端[3,4]。目前,伴隨著通信技術(shù)、電子技術(shù)計(jì)算機(jī)的飛速發(fā)展,數(shù)字信號(hào)處理的理論也在不斷地豐富的豐富和完善,各種新算法、新理論正在不斷地推出。在這近四十多年的發(fā)展中,數(shù)字信號(hào)處理自身已基本形成一套較完整的理論體系[4]。</p><p>  傅立葉變換在數(shù)字信號(hào)處理中扮演著重要的角色[4]。在數(shù)字信號(hào)處理中,最重要也是最基本的表達(dá)信號(hào)的兩個(gè)變量是時(shí)間和頻率。通過傅立葉變換或反變

4、換,可以把時(shí)間域信號(hào)轉(zhuǎn)到頻率域或把頻率域信號(hào)轉(zhuǎn)到時(shí)間域,但又由于我們所要測(cè)量的信號(hào)大都是連續(xù)周期信號(hào),不能直接在計(jì)算機(jī)上計(jì)算它的傅里葉變換,而DFT及其快速算FFT是一種時(shí)域和頻域都離散化的變換,能在計(jì)算機(jī)上實(shí)現(xiàn)信號(hào)的頻譜分析及其他方面的處理,因此DFT在數(shù)字信號(hào)處理和數(shù)字圖像處理中得到了廣泛的應(yīng)用,它建立了離散時(shí)域與離散頻域之間的關(guān)系[5]。如果信號(hào)或圖像處理直接在時(shí)域或空域上處理,計(jì)算就會(huì)隨著離散采樣點(diǎn)數(shù)的增加而激劇增加。使得計(jì)算機(jī)

5、計(jì)算量大,費(fèi)時(shí),難以達(dá)到實(shí)時(shí)的要求[6]。因此,一般采用DFT方法,將輸入的數(shù)字信號(hào)首先進(jìn)行DFT變換,把時(shí)域中的卷積和相關(guān)運(yùn)算簡化為在頻域上的相成處理,然后進(jìn)行DFT反變換,恢復(fù)為時(shí)域信號(hào)。這樣大大減少計(jì)算量,提高處理速度。最重要的是DFT有多種快速算法,統(tǒng)稱為快速傅立葉變換,從而使信號(hào)的實(shí)時(shí)處理和設(shè)備的簡化得以實(shí)現(xiàn)。所以說,DFT不僅在理論上有重要意義,而且在各種信號(hào)的處理中也起核心作用。</p><p> 

6、 離散傅立葉變換(DFT)是復(fù)數(shù)域的運(yùn)算,盡管借助于FFT可以提高運(yùn)算速度,但在實(shí)際應(yīng)用,特別是實(shí)時(shí)處理中帶來了不便。由于實(shí)偶函數(shù)的傅立葉變換只含有實(shí)的余弦項(xiàng),因此構(gòu)造了一種實(shí)域的變換---離散余弦變換(DCT)。</p><p>  離散余弦變換(DCT)是N Ahmed等人在1974年提出的正交變換方法[5]。它是一種正交變換,它類似于離散傅里葉變換(DFT),但是只使用實(shí)數(shù)。離散余弦變換相當(dāng)于一個(gè)長度大概是

7、它兩倍的離散傅里葉變換,這個(gè)離散傅里葉變換是對(duì)一個(gè)實(shí)偶函數(shù)進(jìn)行的。它的思想是將一個(gè)實(shí)函數(shù)對(duì)稱延拓成一個(gè)實(shí)偶函數(shù),實(shí)偶函數(shù)的傅立葉變換也必然是實(shí)偶函數(shù),連續(xù)函數(shù)和離散函數(shù)(CFT)都是基于這一原理。</p><p>  在20世紀(jì)80年代至90年代初期,人們對(duì)DCT快速算法的研究較多,并且取得了巨大的成功。早在1977年,Chen?根據(jù)變換矩陣具有對(duì)稱性,利用稀疏矩陣分解法第一次提出DCT的快速算法。l984年B.

8、G.Led 提出了一種使用余割因子的DCT矩陣分解方法,得到Cooley-Tukey式的簡單結(jié)構(gòu),受到廣泛重視。后來Duhamel將DCT看成是一種基于循環(huán)卷積的算法,并證明。對(duì)于一維的8點(diǎn)DCT,其乘法的理論下限值是l1次,C.Loeffler 具體實(shí)現(xiàn)了這種ll步乘法的算法。從此以后,一維DCT快速算法的研究進(jìn)展緩慢。2000年Trac.D.Trar提出了一種DCT的近似快速算法,在算法中也沒有用到乘法,但使用了移位運(yùn)算。在國內(nèi),趙

9、耀等人也提出了一種“基于矩陣分解的DCT-I算法”[16] ,該方法也用到了l2次乘法。</p><p>  離散余弦變換的提出雖然比快速傅立葉變換(FFT)晚,但其性能更接近于理想的KLT變換,并且由于KLT 到目前為止沒有發(fā)現(xiàn)有效的快速速算法,所以DCT在信號(hào)處理中得到了廣泛應(yīng)用[6]。離散余弦變換(DCT)域是數(shù)字信號(hào)處理技術(shù)中最常用的線性變換之一,和離散傅里葉變換一樣,也存在著快速算法。它的快速算法也是在

10、繼承完善DFT的基礎(chǔ)上不斷進(jìn)步的。但由于離散余弦變換(DCT)的變換核為實(shí)數(shù)的余弦函數(shù),因此它的計(jì)算速度比變換核為復(fù)數(shù)指數(shù)的DFT要快。所以高效快速的離散余弦變換(DCT)得到了廣泛應(yīng)用,并且不斷激發(fā)人們對(duì)其快速算法的研究[7,8,9]。</p><p>  基于以上研究現(xiàn)狀,如何改進(jìn)DCT的快速算法是本文的研究重點(diǎn)。本文首先系統(tǒng)闡述了離散傅立葉變換(DFT)的基礎(chǔ)理論及其快速算法FFT,然后詳細(xì)論述了離散余弦變

11、換的基本概念及其二維DCT快速算法的基本理論和實(shí)現(xiàn)方法,重點(diǎn)研究了一種改進(jìn)的離散余弦變換的快速算法,并推導(dǎo)了算法的進(jìn)行過程。本文著眼于如何改進(jìn)離散余弦變換的快速算法,分析了一維8點(diǎn)DCT快速算法的原理和二維8乘8DCT快速算法的理論,推導(dǎo)出了改進(jìn)的DCT快速算法的基本思路,并將此算法與其它算法做了比較,最后舉出具體實(shí)例,演繹了算法的進(jìn)行過程,結(jié)果表明該算法的運(yùn)算量明顯減少。</p><p>  2 離散傅立葉變換

12、(DFT)及其快速算法(FFT)</p><p>  DFT是先將信號(hào)在時(shí)域離散化,求其連續(xù)傅里葉變換后,再在頻域離散化的結(jié)果。它通常用于頻譜分析和濾波,它提供了使用計(jì)算機(jī)來分析信號(hào)和系統(tǒng)的一種方法,尤其是DFT的快速算FFT,在許多科學(xué)技術(shù)領(lǐng)域中得到了廣泛的應(yīng)用,并推動(dòng)了數(shù)字信號(hào)處理技術(shù)的迅速發(fā)展[10]。</p><p>  2.1 離散傅立葉變換(DFT)的定義和DFT性質(zhì)<

13、/p><p>  在計(jì)算機(jī)上實(shí)現(xiàn)信號(hào)的頻譜分析及其他方面的處理工作時(shí),對(duì)信號(hào)的要求是:在時(shí)域和頻域都是離散的,且都應(yīng)是有限長。離散傅立葉變換不是一個(gè)新的傅立葉變換形式,它實(shí)際上來自于DFS,只不過僅在時(shí)域,頻域各取一個(gè)周期,其實(shí)質(zhì)是有限長序列傅立葉變換的有限點(diǎn)離散采樣,從而開辟了頻域離散化的道路,使數(shù)字信號(hào)處理可以在頻域采用數(shù)字運(yùn)算的方法進(jìn)行,大大增加了數(shù)字信號(hào)處理的靈活性。</p><p>

14、 ?。?) 正變換: (2.1.1)</p><p> ?。?) 反變換: (2.1.2)</p><p>  離散傅立葉變換適用于有限長序列,和只有N個(gè) 值,但隱含周期性。是Z變換在單位圓上等距離的抽樣值,,是序列頻譜的采樣值,。 </p><p>  假定與是長度為N的有限長序列,其各自的離散傅立葉變換分別為

15、 , 。則DFT具有以下性質(zhì):</p><p>  (1) 線性 ,,為任意常數(shù) </p><p><b>  (2) 循環(huán)移位</b></p><p>  有限長序列的循環(huán)移位定義為:</p><p>  表示的周期延拓序列的移位:</p><p>  表示對(duì)移位的周期序列取主值序列。所

16、以仍然是一個(gè)長度為N的有限長序列。實(shí)際上可看作序列排列在一個(gè)N等分圓周上,并向左旋轉(zhuǎn)m位。 </p><p>  序列循環(huán)移位后的DFT為:。實(shí)際上,利用的周期性,將代入DFT定義式,同樣很容易證明。 </p><p>  同樣,對(duì)于頻域有限長序列X(k)的循環(huán)移位,有如下反變換特性:</p><p><b>  (3) 循環(huán)卷積</b><

17、;/p><p><b>  若 </b></p><p><b>  則 </b></p><p><b>  或 </b></p><p><b>  同樣,若 </b></p><p><b>

18、;  則 </b></p><p>  所以,離散時(shí)間序列(或離散傅立葉變換)的循環(huán)卷積與離散傅立葉變換(或離散時(shí)間序列)的乘積相對(duì)應(yīng)。這就說明循環(huán)卷積的運(yùn)算可利用離散傅立葉變換轉(zhuǎn)換成乘積實(shí)現(xiàn)。</p><p>  (4) 有限長序列的線性卷積與循環(huán)卷積(循環(huán)卷積的應(yīng)用)</p><p>  有限長序列的線性卷積等于循環(huán)卷積,而不產(chǎn)生混淆的必要

19、條件是延拓周期 L≥N+M-1,其中N、M為兩個(gè)有限長序列的長度。 </p><p>  (5) 奇偶對(duì)稱特性</p><p>  時(shí)域序列奇對(duì)稱時(shí),其也奇對(duì)稱,即若 ,則。</p><p>  時(shí)域序列偶對(duì)稱時(shí),其也偶對(duì)稱,即若 ,</p><p><b>  則。</b></p><p>&l

20、t;b>  (6) 虛實(shí)特性</b></p><p><b>  若 ,則 。</b></p><p>  當(dāng)為純實(shí)數(shù)序列時(shí),=→共軛偶對(duì)稱。 </p><p>  當(dāng)為純虛數(shù)序列時(shí),=→共軛奇對(duì)稱。</p><p>  2.2 快速傅立葉變換定義和算法思路</p><p> 

21、 自從1965年土基和庫利在《計(jì)算機(jī)數(shù)學(xué)》(Math.Computation,Vol.19,1965)雜志上發(fā)表了著名的《機(jī)器計(jì)算傅立葉變換的一種算法》論文后,桑德--圖基等快速算法相繼出現(xiàn),又經(jīng)人們改進(jìn),很快形成一套高效的運(yùn)算方法,這就是現(xiàn)在的快速傅立葉變換,簡稱FFT(Fast Fourier Transform)。這種算法使DFT的運(yùn)算效率提高1~2個(gè)數(shù)量級(jí),為數(shù)字信號(hào)處理技術(shù)應(yīng)用于各種信號(hào)的實(shí)時(shí)處理創(chuàng)造了良好的條件,大大推動(dòng)了數(shù)

22、字信號(hào)處理的發(fā)展[11]。</p><p>  快速傅立葉變換(FFT)是離散傅立葉變換DFT (Discrete Fourier Transform)的快速算法,它就是利用的特性,逐步地將N點(diǎn)序列分解成較短的序列,計(jì)算短序列的DFT,然后組合成原序列的DFT,使運(yùn)算量顯著減少。FFT是DFT的快速計(jì)算方法,DFT是連續(xù)傅立葉變換的離散形式。 </p><p>  =,=0,1,…N-1

23、 (2.2.1)</p><p>  式中, =,稱為蝶形因子。此式實(shí)際上就是N點(diǎn)的DFT。由(2.2.1)式可以看出,計(jì)算所有的的運(yùn)算量很大。FFT算法利用了蝶形因子內(nèi)在的性質(zhì),從而加快了運(yùn)算的速度。的以下三種性質(zhì)在FFT運(yùn)算中得到了應(yīng)用:</p><p>  性質(zhì) 1: 的周期性 =</p><p&g

24、t;  性質(zhì) 2: 的對(duì)稱性 =</p><p>  性質(zhì) 3: 的可約性 =,=</p><p>  FFT算法將長序列的DFT分解為短序列的DFT。N點(diǎn)的DFT先分解為2個(gè)點(diǎn)的DFT,每個(gè)點(diǎn)的DFT又分解為點(diǎn)的DFT,等等。最小變換的點(diǎn)數(shù)即所謂的“基數(shù)(Radix)",因此,基數(shù)為2的算法的最小變換(或稱蝶形)是2點(diǎn)DFT。一般的,對(duì)N點(diǎn)FFT,對(duì)應(yīng)于N個(gè)輸入樣值

25、,有N個(gè)頻域樣值與之對(duì)應(yīng)。</p><p>  一般而言 ,F(xiàn)FT算法可以分為時(shí)間抽取(DIT)FFT和頻率抽取(DIF)FFT兩大類。</p><p>  2.2.1 時(shí)間抽取(DIT)FFT</p><p>  時(shí)間抽取算法是將N點(diǎn)的輸入序列按照偶數(shù)和奇數(shù)分解為偶序列和奇序列兩個(gè)序列: 偶序列:x(0), x(2), x(4),…,x(N-2)</p>

26、;<p>  奇序列:x(1), x(3) ,x(5),…,x(N-1)</p><p>  因此,的N點(diǎn)FFT可以表示 =+ (2.2.1.1)</p><p>  因?yàn)?===</p><p>  所以 =+,</p><p><b>  令,&

27、lt;/b></p><p>  則有 =+ (2.2.1.2)</p><p>  由于和的周期為,因此 k=0,1,…,。</p><p>  由 =- 可知 =- (2.2.1.3)</p><p>  用(2.2.1.

28、2),(2.2.1.3)兩式分別用來計(jì)算和的。以同樣的方式進(jìn)一步抽取,就可以得到N/4的DFT,重復(fù)這個(gè)抽取過程,就可以使N點(diǎn)的DFT用一組2點(diǎn)的DFT來計(jì)算。在基數(shù)為2的FFT中,設(shè)N=,則總共有M級(jí)運(yùn)算,每級(jí)中有N/2個(gè)2點(diǎn)FFT蝶形運(yùn)算,因此,N點(diǎn)FFT總共有個(gè)蝶形運(yùn)算。</p><p>  圖2.1 時(shí)間抽取算法碟形運(yùn)算圖</p><p>  基2DIT的蝶形如圖2.1所示。設(shè)蝶形

29、的輸入分別為A和B ,輸出分別為C和D,則有 ,</p><p>  圖2.2 N=8點(diǎn)DIT-FFT算法流圖</p><p>  2.2.2 頻率抽取(DIF)FFT</p><p>  頻率抽取FFT算法是在頻域里把序列分解為奇、偶的形式來進(jìn)行計(jì)算,頻率抽取FFT算法首先將輸入序列按照自然順序分為前半部分和后半部分:&l

30、t;/p><p>  偶序列:x(0),x(2),x(4),…,x()</p><p>  奇序列:x(1),x(3),x(5),…,x()</p><p>  因此,的N點(diǎn)FFT可以表示為:=+= (2.2.1.4)</p><p>  k為偶數(shù)時(shí): =,k=0,1,…()</p><p>  k為奇數(shù)時(shí):= ,k

31、=0,1,…()</p><p>  因?yàn)?</p><p><b>  令 =,</b></p><p><b>  則有: </b></p><p><b> ?。?lt;/b></p><p><b&g

32、t;  =</b></p><p>  以同樣的方式,就可以得到N/4點(diǎn)的DFT,重復(fù)這個(gè)過程, N點(diǎn)的DFT用一組2點(diǎn)的DFT來計(jì)算。設(shè)N=,則共有M級(jí)運(yùn)算。DIF的基2蝶形運(yùn)算如圖3所示。</p><p>  圖2.3 基2的DIF-FFT蝶形運(yùn)算</p><p>  圖2.4 8點(diǎn)DIF-FFT的信號(hào)流程圖</p><p>

33、  設(shè)蝶形的輸入分別為A和B,輸出分別為C和D, 則有</p><p><b>  ,</b></p><p>  則一個(gè)8點(diǎn)DIF-FFT的信號(hào)流程圖如圖2.4。</p><p>  從圖2.1和圖2.3可以看出,DIT和DIF兩種FFT算法的區(qū)別是旋轉(zhuǎn)因子出現(xiàn)的位置不同,DIT中在輸入端而DIF中在輸出端。除此之外,兩種方法是一樣的。<

34、;/p><p>  3 離散余弦變換的基本理論</p><p>  離散余弦變換(DCT for Discrete Cosine Transform)是一種正交變換,它類似于離散傅立葉變換 (DFT),但它只使用實(shí)數(shù)。離散余弦變換相當(dāng)于一個(gè)長度大概是它兩倍的離散傅里葉變換,這個(gè)離散傅里葉變換是對(duì)一個(gè)實(shí)偶函數(shù)進(jìn)行的(因?yàn)橐粋€(gè)實(shí)偶函數(shù)的傅里葉變換仍然是一個(gè)實(shí)偶函數(shù)),在有些變形里面需要將輸入或者

35、輸出的位置移動(dòng)半個(gè)單位(DCT有8種標(biāo)準(zhǔn)類型,其中4種是常見的)。</p><p>  最常用的一種離散余弦變換的類型是下面給出的第二種類型,通常我們所說的離散余弦變換指的就是這種。它的逆,也就是下面給出的第三種類型,通常相應(yīng)的被稱為"反離散余弦變換","逆離散余弦變換"或者"IDCT"。有兩個(gè)相關(guān)的變換,一個(gè)是離散正弦變換 (DST for Discr

36、ete Sine Transform),它相當(dāng)于一個(gè)長度大概是它兩倍的實(shí)奇函數(shù)的離散傅立葉變換;另一個(gè)是改進(jìn)的離散余弦變換 (MDCT for Modified Discrete Cosine Transform),它相當(dāng)于對(duì)交疊的數(shù)據(jù)進(jìn)行離散余弦變換[13]。</p><p>  3.1 一維離散余弦變換的各種定義</p><p>  余弦變換是傅里葉變換的一種特殊情況。在傅里葉級(jí)數(shù)展開

37、式中,如果被展開的函數(shù)是實(shí)偶函數(shù),那么,其傅里葉級(jí)數(shù)中只包含余弦項(xiàng),再將其離散化由此可導(dǎo)出余弦變換,或稱之為離散余弦變換(DCT)。下圖(3.1),(3.2)分別給出偶對(duì)稱和奇對(duì)稱的。   </p><p>  圖3.1 偶對(duì)稱的 </p><p><b>  圖3.2 奇對(duì)稱的</b></p><p>  設(shè)一維離散函數(shù)f(x),x=0

38、,1,…,N-1,把f(x)擴(kuò)展成為偶函數(shù)的方法有兩種,以N=4為例,可得出如圖3.1和圖3.2所示的兩種情況。圖3.1稱偶對(duì)稱,圖3.2稱奇對(duì)稱,從而有偶離散余弦變換(EDCT)和奇離散余弦變換(ODCT)。由圖1和2看出,對(duì)于偶對(duì)稱擴(kuò)展,對(duì)稱軸在x=處。</p><p>  = (3.1.1)  采樣點(diǎn)數(shù)增到2N。  </p><p

39、>  對(duì)于奇對(duì)稱擴(kuò)展,對(duì)稱軸在x=0處。</p><p>  =  (3.1.2)  采樣點(diǎn)數(shù)增到2N-1。由離散傅里葉變換定義出發(fā),對(duì)公式(3.1.1)作傅里葉變換,以表示,則得=      

40、 </p><p><b>  (3.1.3)</b></p><p><b>  式中,  </b></p><p>  當(dāng) u=0, =</p><p><b>  當(dāng)  </b></p><p>  當(dāng) ,,且=2[] 考慮正交變換公式與逆變換

41、公式的對(duì)稱性,令 (3.1.4)       式中 (3.1.5)</p><p><b>  (3.1.6)  </b></p><p> 

42、 (3.1.7) </p><p>  定義式(3.1.4)和式(3.1.5)為離散偶余弦正變換公式;式(3.1.6)和式(3.1.7)為離散偶余弦變換核公式。  離散偶余弦逆變換公式為C(0)+C(u)    (3.1.8)</p><p>  x = 0,1,…,N-1  將公式(3.1.4)和公式(3.1

43、.5)合并、化簡,可得到一維離散偶余弦正變換公式</p><p>  即C(u)=E(u)    式中  </p><p>  當(dāng)u=0時(shí),E(u)= ; 當(dāng)時(shí), </p><p>  總上述可歸納:若給定序列,則其離散有限傅里葉變換為:</p><p><b> ?。?.1.9)</b></p>&

44、lt;p>  當(dāng)時(shí),為實(shí)數(shù),則其離散余弦變換定義為</p><p><b> ?。?.1.10)</b></p><p><b> ?。?.1.11)</b></p><p>  顯然,其變換的核函數(shù) (3.1.12) </p><p>  是實(shí)數(shù),式中系數(shù)

45、 (3.1.13)</p><p>  這樣,若是實(shí)數(shù),那么它的DCT變換也是實(shí)數(shù)。對(duì)傅里葉變換,若是實(shí)數(shù),其DFT一般為復(fù)數(shù)。由此可以看出,DCT避免了復(fù)數(shù)運(yùn)算。將(3.1.9)式寫成矩陣,有 (3.1.14)</p><p>  式中,都是的向量,是的變換矩陣,其元素

46、由(3.1.12)式給出。當(dāng)時(shí),有</p><p>  (3.1.13) </p><p>  可以證明,的行、列向量均有如下的正交關(guān)系:</p><p>  可見變換矩陣是歸一化的正交陣,DCT是正交變換,由此立即得到DCT的反變換關(guān)系:</p><p><

47、;b> ?。?.1.14)</b></p><p><b>  即 </b></p><p><b>  (3.1.15)</b></p><p>  當(dāng)k 為其他值時(shí),為了實(shí)現(xiàn)實(shí)數(shù)域運(yùn)算,對(duì)其進(jìn)行改造,將信號(hào)以原點(diǎn)為中心對(duì)稱增加一倍,從N個(gè)擴(kuò)展到 2N個(gè),并對(duì)相位也進(jìn)行修改,除了N 改2N 外,還要加

48、上0+ 與0- 的相位,他們分別為與,則式(3.1.1)應(yīng)該為式(3.1.2),即:</p><p>  由于信號(hào)的安排為,并且,故式(3.1.1)展開相加之后,所有項(xiàng)都抵消,而可化簡為:</p><p><b>  (3.1.16)</b></p><p><b> ?。?.1.17)</b></p>&l

49、t;p>  這就是離散余弦變換的關(guān)系式。</p><p>  從形式上來看,離散余弦變換一個(gè)線性的可逆的函數(shù): (其中R是實(shí)數(shù)集, 或者等價(jià)的說一個(gè)的方陣。離散余弦變換有幾種變形的形式,它們都是根據(jù)下面的某一個(gè)公式把 n 個(gè)實(shí)數(shù)變換到另外n個(gè)實(shí)數(shù)的操作。下面給出離散余弦變換的四種類型:</p><p>  DCT-I =(+)+ []</p><p>

50、  DCT-II =[]</p><p>  DCT-III =+[]</p><p>  DCT-IV =[]</p><p>  3.2 二維離散余弦變換的定義及反變換</p><p>  DCT變換被認(rèn)為是一種準(zhǔn)最佳變換,具有壓縮比高、誤碼率小,信息集中能力和計(jì)算復(fù)雜

51、性綜合效果好等優(yōu)點(diǎn)[10]。一個(gè)M×N矩陣A 的二維DCT定義如下:</p><p><b> ?。?.2.1)</b></p><p>  其中: </p><p>  式中, F( u ,v )為空間域圖像在( x, y )處的灰度值,x ,y=0,1,2, ,N-1, f(x ,y)為變換系數(shù)矩陣,u ,v =

52、0,1,2, ,N-1,N為數(shù)字圖像的寬度和高度。</p><p>  二維離散余弦反變換公式如下:</p><p> ?。?.2.2) </p><p>  其中:為空間域采樣值;為頻率域采樣值。通常,數(shù)字圖像用象素方陣表示,即,在這種情況下,二維離散余弦的正反變換可簡化為:</p><p><b>  (3.2.3)<

53、/b></p><p><b>  (3.2.4)</b></p><p><b>  其中:</b></p><p>  4 離散余弦變換(DCT)的快速算法</p><p>  離散余弦變換也象DFT一樣具有快速實(shí)現(xiàn)的算法。對(duì)于n個(gè)點(diǎn)的DCT變換,其算法復(fù)雜度為O()。</p>

54、;<p>  4.1 一維離散余弦變換的快速算法</p><p>  DCT首先由N.Ahmad等人于1974年提出的[13],設(shè)數(shù)據(jù)序列x(n),n=0,1 ,N-1,則X(n)的DCT定義為:</p><p>  ,k=0,1, ,N-1</p><p><b>  (4.1.1)</b></p><p&g

55、t;  在這里,Y(k)是第K個(gè)DCT系數(shù)。</p><p>  若寫成矩陣形式,則有:其中表示DCT變換矩陣,離散余弦逆變換(IDCT)定義為: (4.1.2)</p><p>  4.2 二維88快速DCT的基本原理及其實(shí)現(xiàn)方法</p><p>  離散余弦變換(Discrete Cos

56、ine Transform ,DCT)是一種最接近統(tǒng)計(jì)最優(yōu)變換K--L變換的正交變換,已有的各種成熟的壓縮標(biāo)準(zhǔn)如JPEG,MPEG1/2/4,H.26X以及HDTV等都無一例外地采用基于DCT/IDCT的壓縮編碼。但通常的DCT運(yùn)算量比較大,為了降低DCT算法的運(yùn)算量,提高運(yùn)算速度,人們提出了多種快速計(jì)算DCT的方法。例如在2D-DCT快速算法中,Duhame和Guillemot提出了一種直接多項(xiàng)式變換法;Vetterli提出了一種間接

57、算法,用附加一些旋轉(zhuǎn)方法將2D-DCT映射為2D-DFT,再用多項(xiàng)式計(jì)算2D-DFT;Wu和Paoloni提出了一種矩陣分解法,利用Kronecker積將N乘N的DCT轉(zhuǎn)化為N的平方點(diǎn)的一維變換,然后對(duì)此一維變換矩陣進(jìn)行分解,減少矩陣中所包含的乘法次數(shù)等等。后來提出的快速算法幾乎都是在上面提出的集中快速算法的基礎(chǔ)上的改進(jìn),以及針對(duì)一些特殊情況的快速算法。在DCT的快速算法中,Loeffer,Ligtenberg和Moschytz在198

58、9年提出的算法最有代表性。在圖像和視頻壓縮中,二維8乘8快速DCT變換是使用最普遍</p><p>  在此主要介紹二維88快速DCT的基本原理及其實(shí)現(xiàn)方法。由于二維8乘8快速DCT的算法是通過計(jì)算行方向的一維DCT和列方向的一維DCT來實(shí)現(xiàn)的,因此首先介紹一維8點(diǎn)快速DCT算法。</p><p>  4.2.1 一維8點(diǎn)快速算法DCT</p><p>  在20世

59、紀(jì)80年代,DCT算法受到了人們的關(guān)注,人們提出了多種針對(duì)一維8點(diǎn)DCT的算法。下表4.1給出七種不同的快速算法的比較,這些算法都是針對(duì)8點(diǎn)的一維DCT,各算法以其作者進(jìn)行標(biāo)志。</p><p>  表4.1 各種快速DCT快速算法的比較</p><p>  若把DCT看做一種循環(huán)旋轉(zhuǎn)運(yùn)算,則對(duì)于8點(diǎn)的一維DCT算法,理論上最少需要11次乘法和29次加法。Loeffler的算法是達(dá)到這一

60、極限的算法。直接計(jì)算DCT需要64次乘法和56次加法,而用Loeffler的快速算法來計(jì)算以維DCT只需要11次乘法和29次加法,可見Loeffler 快速算法在很大程度上減少了計(jì)算量。</p><p>  Loeffler快速算法是一種極具有代表性的一維8點(diǎn)快速DCT算法,下面詳細(xì)介紹Loeffler快速算法。</p><p>  Loeffler快速算法的基本原理??焖貲CT算法把一維

61、DCT算法分為4級(jí),由于各級(jí)之間的輸入輸出具有依存關(guān)系,4級(jí)操作必須串進(jìn)行,而各級(jí)內(nèi)部的運(yùn)算可采用并聯(lián)方式來進(jìn)行處理。它有三種運(yùn)算因子:蝶形因子,旋轉(zhuǎn)因子和倍乘因子。下圖是Lo </p><p>  圖4.1 Loeffler算法流程圖 </p><p>  (a)蝶形因子 (b)旋轉(zhuǎn)因子 (c)倍乘因子</p>&

62、lt;p>  圖4.2 Loeffler快速DCT算法中的三種因子</p><p>  上圖中表示Loeffler快速DCT算法中的三種,其中,或表示輸入,,或表示輸出。幾種運(yùn)算因子之間的關(guān)系介紹如下。</p><p> ?、〉我蜃拥妮斎胼敵鲫P(guān)系是: </p><p>  由上式可見,完成一個(gè)蝶形因子需要2次加法運(yùn)算。</p><p>

63、; ?、⑿D(zhuǎn)因子的輸入輸出關(guān)系是:</p><p>  根據(jù)上面的公式,直接計(jì)算旋轉(zhuǎn)因子需要4次乘法和2次加法。為了減少運(yùn)算量,對(duì)上面描述旋轉(zhuǎn)因子輸入輸出關(guān)系的等式做變換,變形為:</p><p>  采用上面變形后的等式,只需要3次乘法和3次加法就可以完成一個(gè)旋轉(zhuǎn)因子的運(yùn)算。等式變換后使旋轉(zhuǎn)因子的計(jì)算量減少。</p><p> ?、?倍乘因子的輸入輸出關(guān)系是:&l

64、t;/p><p>  倍乘因子只需要一次乘法。</p><p>  以上分析可得出結(jié)論:計(jì)算蝶形因子需要2次加法操作,計(jì)算旋轉(zhuǎn)因子需要3次乘法因子和3次加法操作,計(jì)算倍乘因子需要1次乘法操作。而 Loeffler的快速算法流程圖中共存在10個(gè)蝶形因子,3個(gè)旋轉(zhuǎn)因子和2個(gè)倍乘因子,因此,總的乘法次數(shù)是33+2=11,總的加法次數(shù)是102+33=29。</p><p>  

65、(2) Loeffler 快速算法DCT算法的計(jì)算 前面介紹了Loeffler快速算算法的運(yùn)算流程,并且對(duì)其在運(yùn)算過程中所需要的乘法和加法操作的次數(shù),也就是運(yùn)算量進(jìn)行了分析。下面來推導(dǎo)一維DCT快速算法的8個(gè)系數(shù)。進(jìn)一步驗(yàn)證Loeffler快速算法的正確性。按DCT系數(shù)y(0),y(4),y(2)y(6),y(7),y(3),y(5),y(1)的順序來排列。偶系數(shù)y(0) ,y(4),y(2).y(6), 按照位序增序排序,而奇系數(shù)

66、y(7),y(3),y(5),y(1) 按倒位序降序排列。按這種順序?qū)⒚總€(gè)DCT系數(shù)的表達(dá)式化為流程圖中三種因子的組合。</p><p>  給出一維8點(diǎn)DCT的公式為:</p><p><b>  F(u)=</b></p><p><b>  式中 </b></p><p>  對(duì)于一維D

67、CT的系數(shù)F(0),F(4),根據(jù)一維8點(diǎn)DCT的公式,有</p><p><b>  F(0)= =</b></p><p><b>  F(4)= </b></p><p>  ={[]+[]}-{[]+[]}</p><p>  y(0)和y(4)都可以表示為3級(jí)蝶形因子的級(jí)聯(lián)。</p&

68、gt;<p>  同理,其余的6個(gè)系數(shù)也可以得出:</p><p><b>  F(2)= </b></p><p>  ={[]-[]}+{[]-]}</p><p><b>  F(6)= </b></p><p>  ={[]-[]}-{[]-]}</p><

69、p><b>  F(7)= </b></p><p>  ={[]+[]}+{-]+[]}-{-[]+[]-[-]+[]}</p><p><b>  F(3)= </b></p><p>  ={-[]+[]}-{[]+[]}</p><p><b>  F(5)= </b&

70、gt;</p><p>  ={[]+[]}-{-[]+[]}</p><p><b>  F(1)= </b></p><p>  ={[]+[]}+{-]+[</p><p>  ]}-{-[]+[]-[-]+[]}</p><p>  由上面的DCT系數(shù)的表示公式可以看出,y(0)和y(4)

71、都可以表示為3級(jí)蝶形因子的級(jí)聯(lián);y(2)和y(6)表示為2級(jí)蝶形因子與一級(jí)旋轉(zhuǎn)因子的級(jí)聯(lián);y(7)和y(1) 表示為1級(jí)蝶形運(yùn)算與1級(jí)旋轉(zhuǎn)運(yùn)算級(jí)聯(lián)后,再級(jí)聯(lián)2級(jí)蝶形運(yùn)算;y(5)和y(3)表示為1級(jí)蝶形,1級(jí)旋轉(zhuǎn),1級(jí)蝶形和一級(jí)倍乘運(yùn)算的依次順序級(jí)聯(lián)。</p><p>  綜上所述,一維8點(diǎn)DCT的8個(gè)系數(shù)利用一維8點(diǎn)DCT的公式來計(jì)算,其結(jié)果可以轉(zhuǎn)化為三種因子的級(jí)聯(lián)形式,從而證明一維8點(diǎn)DCT算法的流程圖是正確

72、的。</p><p>  4.2.2 二維 8乘8 DCT 快速算法</p><p>  為了減弱或消除圖像數(shù)據(jù)的空間相關(guān)性,可以運(yùn)用二維DCT變換,將圖像 f( x ,y )從空間域轉(zhuǎn)換到DCT變換域。</p><p>  二維8乘8快速DCT算法及其逆變換IDCT的計(jì)算公式定義如下:</p><p>  F(u,v)=C(u)C(v)&

73、lt;/p><p>  F(x ,y)= F( u ,v ) </p><p><b>  式中</b></p><p>  f( x ,y )表示像素的值,F(xiàn)( u ,v )表示DCT系數(shù)。對(duì)于二維DCT的計(jì)算方法很多或進(jìn)行行--列方法運(yùn)算。直接方法是二維的數(shù)據(jù);而行--列方法是根據(jù)DCT/IDCT的正交可分解性,通過對(duì)輸入矩陣先行行方向的一維D

74、CT,再作列方向的一維 DCT 。即將 N乘N 數(shù)據(jù)按行(或列)方向進(jìn)行N 個(gè)一維DCT計(jì)算,產(chǎn)生中間數(shù)據(jù)矩陣再按列(行)方向進(jìn)行N 個(gè)一維DCT計(jì)算,最后得到二維DCT的結(jié)果。</p><p>  下圖(4.3)所描述的是二維離散余弦變換(2D-DCT)和二維離散余弦逆變(2D-IDCT)的處理流程。在圖中有兩個(gè)一維DCT/IDCT 的處理模塊和一個(gè)轉(zhuǎn)置RAM模塊。輸入數(shù)據(jù)首先要經(jīng)過串-并轉(zhuǎn)換模塊,把串行輸入的

75、數(shù)據(jù)轉(zhuǎn)換為并行的形式;再經(jīng)過第一個(gè)DCT/IDCT處理模塊,按行方向進(jìn)行一維DCT/IDCT;然后產(chǎn)生的中間數(shù)據(jù)輸入到轉(zhuǎn)置RAM中;將轉(zhuǎn)置后的數(shù)據(jù)輸入到第二個(gè)DCT/IDCT處理模塊,按列方向進(jìn)行一維DCT/IDCT;最后數(shù)據(jù)再經(jīng)過并-串轉(zhuǎn)換模塊,把并行的數(shù)據(jù)變?yōu)榇械臄?shù)據(jù)。</p><p>  圖4.3 二維DCT/IDCT處理流程圖</p><p>  上圖描述的二維DCT快速算法的處

76、理流程中有三種模塊:DCT/IDCT處理模塊,轉(zhuǎn)置RAM模塊,串-并(并-串)轉(zhuǎn)換模塊。串-并模塊是實(shí)現(xiàn)數(shù)據(jù)的串-并轉(zhuǎn)換模塊的功能與串-并轉(zhuǎn)換模塊的功能正好相反,即把沒收到的一組8個(gè)并行數(shù)據(jù)轉(zhuǎn)換成8個(gè)串行數(shù)據(jù)輸出。轉(zhuǎn)置RAM模塊對(duì)兩個(gè)一維DCT處理模塊之間的中間數(shù)據(jù)進(jìn)行轉(zhuǎn)置處理。DCT/IDCT模塊用來對(duì)輸入的數(shù)據(jù)做DCT/IDCT處理。針對(duì)二維8乘8快速DCT的計(jì)算,DCT模塊完成一維8點(diǎn)DCT計(jì)算,采用Loeffler的一維快速DC

77、T算法。</p><p>  5 一種新的改進(jìn)型離散余弦快速算法</p><p>  改進(jìn)型的離散余弦變換(Modified discrete cosine transform)作為良好的時(shí)頻分析工具,在信號(hào)處理的實(shí)時(shí)性上顯得至關(guān)重要,為此需要研究其快速算法。下面論述基于快速DCT變換的MDCT快速算法的原理。</p><p><b>  5.1 算法原理

78、</b></p><p>  改進(jìn)型離散余弦變換(MDCT :Modified Discrete Cosine Transform)的定義為: (5.1.1)</p><p>  式中,。式(5.1.1)與DCT相比多了一個(gè)常數(shù)為此首先簡化該式,分離余弦函數(shù)中包含的信息。利用三角公式中的余弦和積關(guān)系:2cosAcosB=cos(A+B)+cos(A-B)

79、。</p><p><b>  令 </b></p><p>  對(duì)大括號(hào)進(jìn)一步調(diào)整 </p><p>  其中(推導(dǎo)見附錄1)所以式(5.1.1)可改寫為如下形式:</p><p><b> ?。?.1.2)</b></p><p><b>  其中, <

80、/b></p><p>  由此,對(duì)X(k)的計(jì)算轉(zhuǎn)化為系數(shù)Z(k)的計(jì)算,明顯地,Z(k)具有對(duì)稱性,Z(n-1-k)=Z(k),所以只需計(jì)算一半系數(shù),即 對(duì)Z(k)分離其奇偶序號(hào)項(xiàng)</p><p>  對(duì)后半部分進(jìn)一步解析,令</p><p><b>  (推導(dǎo)見附錄2)</b></p><p><b&g

81、t;  其中 </b></p><p>  再令 于是Z(k)可重寫為:</p><p><b>  (5.1.3)</b></p><p>  至此,本文將N點(diǎn)的轉(zhuǎn)化為兩個(gè)點(diǎn)的的計(jì)算,其遞推公式(5.1.3),這樣的遞推形式與傳統(tǒng)將N點(diǎn)DCT分解為一個(gè)點(diǎn)DCT和一個(gè)點(diǎn)DST的線性組合不同,其子變換仍為的形式,便于編程;這與FFT相

82、似,但所有運(yùn)算皆為實(shí)數(shù)運(yùn)算。</p><p><b>  5.2 舉例</b></p><p>  以N=8為例,具體演繹算法的進(jìn)行過程。依據(jù)下面的過程可以類推N=(n為大于3的自然數(shù))。</p><p><b>  預(yù)處理</b></p><p>  z(0)=x(0)-x(3)</p>

83、;<p>  z(1)=x(1)-x(2)-x(4) </p><p>  z(2)=x(2)-x(1)-x(5)</p><p>  z(3)=x(3)-x(0)-x(6) </p><p>  z(4)=x(4)-x(7)</p><p><b>  z(5)=x(5)</b&g

84、t;</p><p>  z(6)=x(6) </p><p><b>  z(7)=x(7)</b></p><p>  圖5.1 奇偶分序數(shù)組示意圖</p><p>  構(gòu)造奇偶分序組(見圖5.1)</p><p><b>  遞推(見圖5.2)</b></

85、p><p>  圖5.2 遞推示意圖</p><p><b>  后處理</b></p><p><b>  結(jié)論 </b></p><p>  除預(yù)處理操作復(fù)雜外,本算法的結(jié)構(gòu)簡單,遞推中半蝶形運(yùn)算的所有操作皆為實(shí)數(shù),再加上系數(shù)具有對(duì)稱性,因此其該乘法加法次數(shù)都較基于FFT的算法少。由上述分析可知,

86、其實(shí)數(shù)加法和乘法次數(shù)分別為和,與文獻(xiàn)[ 14,15]相比,具體數(shù)據(jù)見表5.1。</p><p>  表5.1算法實(shí)數(shù)操作比較</p><p>  由表5.1可知基于DCT變換的快速算法的運(yùn)算量明顯減少。并將此算法的結(jié)果與其它算法的結(jié)果作了比較,結(jié)果表明:算法速度提高了,雖然算法的結(jié)果仍是正確的。</p><p><b>  6 結(jié)束語</b>&

87、lt;/p><p>  DCT的快速算法有多種,基于多項(xiàng)式變換的DCT快速算法,基于查表的無乘法DCT快速算法,利用循環(huán)卷積實(shí)現(xiàn)的DCT快速算法等,本文以離散余弦變換的快速算法的基本理論為基礎(chǔ),提出了改進(jìn)型離散余弦變換的快速算法,并用具體實(shí)例進(jìn)行驗(yàn)證,結(jié)果表明此算法可行,說明此算法在一定程度上減少了運(yùn)算量,尤其是減少了將近三分之一的乘法的運(yùn)算次數(shù)。但是,該算法過程中的預(yù)處理操作比較復(fù)雜,所以在運(yùn)算簡便方面不是太理想。

88、由于改進(jìn)型的DCT是良好的時(shí)頻分析工具,其快速算法也顯得至關(guān)重要。在以后的時(shí)間里,我將繼續(xù)研究,完善基于快速DCT變換的MDCT快速算法。</p><p><b>  [參考文獻(xiàn)]</b></p><p>  [1] 胡廣書, 數(shù)字信號(hào)處理導(dǎo)論[M]. 北京: 清華大學(xué)出版社, 2005.</p><p>  [2] 丁玉美, 高西全. 數(shù)字信

89、號(hào)處理[M]. 西安: 西安電子科技大學(xué)出版社,1994.[3] 奧本海姆著. 劉樹棠,黃建國譯. 離散時(shí)間信號(hào)處理[M]. 西安: 西安交通大學(xué)出版社 </p><p><b>  2001.</b></p><p>  [4] 朱秀昌, 劉峰, 胡棟. 數(shù)字圖像處理與圖像通信[M]. 北京: 北京郵電大學(xué)出版社,2002.</p><

90、;p>  [5] Kenneth R.Castleman 著, 朱志剛, 石定機(jī)等譯. 數(shù)字圖像處理[M]. 北京: 電子工業(yè)出版社,2002.</p><p>  [6] 李在銘. 數(shù)字圖像處理壓縮與識(shí)別技術(shù)[M]. 成都: 電子科技大學(xué)出版社, 2000.</p><p>  [7] 谷獲隆嗣(日本). 快速算法與并行信號(hào)處理[M]. 北京: 科學(xué)出版社, 2003.</p

91、><p>  [8] K.R. Rao and P. Yip, 離散余弦變換 : 算法、優(yōu)點(diǎn)和應(yīng)用 (Discrete Cosine Transform: Algorithms, Advantages, Applications) (Academic Press, Boston, 1990). </p><p>  [9] Syed Ali Khayam , Department of Ele

92、ctrical & Computer Engineeri . Michigan State University . The Discrete Cosine Transform(DCT):Theory and , Application March 10th 2003.</p><p>  [10] Gilbert Strang Massachusetters Institute of Tec

93、hnology . Discrete Cosine Transform(DCT).</p><p>  [11] 何小敏, 王正勇. 數(shù)字圖像通信及其應(yīng)用[M]. 成都: 四川大學(xué)出版社, 2006.</p><p>  [12] 陳禾, 毛志剛, 葉以正. DCT快速算法及其VLSI實(shí)現(xiàn)[J]. 哈爾濱工業(yè)大學(xué)學(xué)報(bào), 1998.</p><p>  [13] 徐盛

94、, 胡劍凌, 陳 健. 一種新的MDCT快速算法[J]. 上海交通大學(xué),200030, 2000. 12.</p><p>  [14] 杜相文, 陳賀毒, 趙巖. 基于查表的無乘法DCT快速算法[J].吉林大學(xué)南嶺校區(qū)通信工程學(xué)院測(cè)控技術(shù)與儀器系,長春130025 ;2.吉林大學(xué)通信工程學(xué)院通信工程系,長春130012 2004 10.</p><p>  [15] 殷瑞祥. 基于多

95、項(xiàng)式變換的2D—DCT快速算法[J]. 華南理工大學(xué)電子與信息工程學(xué)院,廣東廣州510640, 2001 9.</p><p><b>  附 錄</b></p><p><b>  附錄1</b></p><p><b>  =</b></p><p><b> 

96、 =</b></p><p><b>  =</b></p><p><b>  =</b></p><p><b>  =</b></p><p><b>  =</b></p><p><b>  =<

97、;/b></p><p><b>  附錄2</b></p><p><b>  =</b></p><p><b>  =</b></p><p><b>  =+</b></p><p><b>  +</

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 眾賞文庫僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。

評(píng)論

0/150

提交評(píng)論