河北科技大學(xué)多媒體通信技術(shù)基礎(chǔ) 第三章.ppt

1、第第3章章 數(shù)據(jù)壓縮的基本技術(shù)數(shù)據(jù)壓縮的基本技術(shù) 數(shù)據(jù)壓縮處理一般由兩個(gè)過(guò)程組成：數(shù)據(jù)壓縮處理一般由兩個(gè)過(guò)程組成： 編碼過(guò)程：對(duì)原始數(shù)據(jù)進(jìn)行編碼壓縮，以便存儲(chǔ)和傳輸；編碼過(guò)程：對(duì)原始數(shù)據(jù)進(jìn)行編碼壓縮，以便存儲(chǔ)和傳輸； 解碼過(guò)程：對(duì)壓縮的數(shù)據(jù)進(jìn)行解壓，恢復(fù)成可用的數(shù)據(jù)。解碼過(guò)程：對(duì)壓縮的數(shù)據(jù)進(jìn)行解壓，恢復(fù)成可用的數(shù)據(jù)。根據(jù)解壓后數(shù)據(jù)的保真度，數(shù)據(jù)壓縮技術(shù)可分為根據(jù)解壓后數(shù)據(jù)的保真度，數(shù)據(jù)壓縮技術(shù)可分為無(wú)損壓縮編碼無(wú)損壓縮編碼：解碼后的數(shù)據(jù)與原始數(shù)據(jù)完全相同，無(wú)任：解碼后的數(shù)據(jù)與原始數(shù)據(jù)完全相同，無(wú)任何偏差。這種編碼通?；谛畔㈧卦?，常用的編碼有何偏差。這種編碼通?；谛畔㈧卦?，常用的編碼有哈

2、夫曼編碼、算術(shù)編碼、行程編碼等。壓縮比比較低，哈夫曼編碼、算術(shù)編碼、行程編碼等。壓縮比比較低，一般在一般在2:1-5:1。主要用于要求數(shù)據(jù)無(wú)損壓縮存儲(chǔ)和傳輸。主要用于要求數(shù)據(jù)無(wú)損壓縮存儲(chǔ)和傳輸?shù)膱?chǎng)合，如傳真機(jī)的場(chǎng)合，如傳真機(jī)有損壓縮編碼有損壓縮編碼：解碼后的數(shù)據(jù)與原始數(shù)據(jù)相比有一定的偏：解碼后的數(shù)據(jù)與原始數(shù)據(jù)相比有一定的偏差，但仍可保持一定的視聽(tīng)質(zhì)量和效果。它主要是在保差，但仍可保持一定的視聽(tīng)質(zhì)量和效果。它主要是在保持一定保真度下對(duì)數(shù)據(jù)進(jìn)行壓縮，其壓縮比可達(dá)持一定保真度下對(duì)數(shù)據(jù)進(jìn)行壓縮，其壓縮比可達(dá)100:1。壓縮比越高，其解壓縮后的視、音頻質(zhì)量就越低。壓縮比越高，其解壓縮后的視、音頻質(zhì)量就越

3、低。 分類(lèi)：分類(lèi)： a 第一代圖像壓縮編碼方法第一代圖像壓縮編碼方法基于香農(nóng)理論，基于香農(nóng)理論，80年代初趨于成熟，主要降低數(shù)據(jù)之間的相關(guān)性，年代初趨于成熟，主要降低數(shù)據(jù)之間的相關(guān)性，去除冗余。去除冗余。 b 第二代圖像壓縮編碼方法第二代圖像壓縮編碼方法基于人類(lèi)視覺(jué)特性的壓縮方法，其核心思想是力圖發(fā)現(xiàn)人眼是根據(jù)基于人類(lèi)視覺(jué)特性的壓縮方法，其核心思想是力圖發(fā)現(xiàn)人眼是根據(jù)哪些關(guān)鍵特征來(lái)識(shí)別圖像、或圖像序列的，然后根據(jù)這些特征來(lái)哪些關(guān)鍵特征來(lái)識(shí)別圖像、或圖像序列的，然后根據(jù)這些特征來(lái)構(gòu)造圖像模型。構(gòu)造圖像模型。 例如，根據(jù)人眼對(duì)物體的輪廓比對(duì)物體內(nèi)部細(xì)節(jié)更為敏例如，根據(jù)人眼對(duì)物體的輪廓比對(duì)物體內(nèi)部細(xì)

4、節(jié)更為敏感的特點(diǎn)，可以利用物體感的特點(diǎn)，可以利用物體(而不是像素而不是像素)的集合來(lái)表示圖的集合來(lái)表示圖像。像。 3.2 數(shù)據(jù)壓縮的理論依據(jù)數(shù)據(jù)壓縮的理論依據(jù)3.2 數(shù)據(jù)壓縮的理論依據(jù)數(shù)據(jù)壓縮的理論依據(jù) 數(shù)據(jù)壓縮的理論基礎(chǔ)為數(shù)據(jù)壓縮的理論基礎(chǔ)為Shannon信息論。信息論。它一方面給出了數(shù)據(jù)壓縮的理論極限，另它一方面給出了數(shù)據(jù)壓縮的理論極限，另一方面又指明了數(shù)據(jù)壓縮的技術(shù)途徑。一方面又指明了數(shù)據(jù)壓縮的技術(shù)途徑。 Shannon理論認(rèn)為：信源中所含有的平均信息量理論認(rèn)為：信源中所含有的平均信息量（熵）是進(jìn)行無(wú)失真壓縮編碼的理論極限。（熵）是進(jìn)行無(wú)失真壓縮編碼的理論極限。 無(wú)記憶信源：如果設(shè)計(jì)的編

5、碼方法的碼字平均長(zhǎng)無(wú)記憶信源：如果設(shè)計(jì)的編碼方法的碼字平均長(zhǎng)度最接近熵，則說(shuō)明該編碼方法是最佳的。度最接近熵，則說(shuō)明該編碼方法是最佳的。的下限。熵值是平均碼長(zhǎng)。稍大于最佳編碼不可能；編碼；時(shí)，有冗余，不是最佳NXHNXHNXHNXHN)()()()(香農(nóng)三大定理是信息論的基礎(chǔ)理論。香農(nóng)三大定理是存在香農(nóng)三大定理是信息論的基礎(chǔ)理論。香農(nóng)三大定理是存在性定理，雖然并沒(méi)有提供具體的編碼實(shí)現(xiàn)方法，但為通信性定理，雖然并沒(méi)有提供具體的編碼實(shí)現(xiàn)方法，但為通信信息的研究指明了方向。信息的研究指明了方向。第一定理：可變長(zhǎng)無(wú)失真信源編碼定理第一定理：可變長(zhǎng)無(wú)失真信源編碼定理采用無(wú)失真最佳信源編碼可使得用于每個(gè)信

6、源符號(hào)的編碼采用無(wú)失真最佳信源編碼可使得用于每個(gè)信源符號(hào)的編碼位數(shù)盡可能的少，但它的極限是原始信號(hào)源的熵；超過(guò)了位數(shù)盡可能的少，但它的極限是原始信號(hào)源的熵；超過(guò)了這一極限就不可能實(shí)現(xiàn)無(wú)失真的譯碼。這一極限就不可能實(shí)現(xiàn)無(wú)失真的譯碼。第二定理：有噪信道編碼定理第二定理：有噪信道編碼定理若在信息傳輸率若在信息傳輸率R不大于信道容量不大于信道容量C時(shí)，則存在一種編碼，時(shí)，則存在一種編碼，當(dāng)碼長(zhǎng)當(dāng)碼長(zhǎng)n足夠大時(shí)，它可以使信道輸出端的錯(cuò)誤概率任意小，足夠大時(shí)，它可以使信道輸出端的錯(cuò)誤概率任意小，而信息傳輸率無(wú)限接近而信息傳輸率無(wú)限接近C；如果；如果RC，則不能找到一種編碼，則不能找到一種編碼，使輸出端錯(cuò)誤

7、概率任意小。使輸出端錯(cuò)誤概率任意小。第三定理：第三定理： 第三定理：保真度準(zhǔn)則下的信源編碼定理，或稱(chēng)有損信源第三定理：保真度準(zhǔn)則下的信源編碼定理，或稱(chēng)有損信源編碼定理編碼定理只要碼長(zhǎng)足夠長(zhǎng)，總可以找到一種信源編碼，使編碼后的只要碼長(zhǎng)足夠長(zhǎng)，總可以找到一種信源編碼，使編碼后的信息傳輸率信息傳輸率R（單位：（單位：bit/信源符號(hào)）略大于率失真函數(shù)信源符號(hào)）略大于率失真函數(shù)R(D)，而碼的平均失真度不大于給定的允許失真度，即，而碼的平均失真度不大于給定的允許失真度，即D0,一定存在一種碼一定存在一種碼字個(gè)數(shù)為字個(gè)數(shù)為M2NR(D)+的信源編碼，使編碼后的平均失真度的信源編碼，使編碼后的平均失真度D

8、R(D),只要信源序列長(zhǎng)只要信源序列長(zhǎng)度度L足夠長(zhǎng)，一定存在一種編碼方法其譯碼平均足夠長(zhǎng)，一定存在一種編碼方法其譯碼平均失真小于或等于失真小于或等于D+逆定理：當(dāng)逆定理：當(dāng)RDQn預(yù)測(cè)器預(yù)測(cè)器 xn+ +xn xn = n + xn 幾個(gè)概念：幾個(gè)概念： 一維預(yù)測(cè)：被預(yù)測(cè)的樣值與用作預(yù)測(cè)的樣值在同一維預(yù)測(cè)：被預(yù)測(cè)的樣值與用作預(yù)測(cè)的樣值在同一行內(nèi)一行內(nèi) 二維預(yù)測(cè)：用作預(yù)測(cè)的樣值位于相鄰的不同行上二維預(yù)測(cè)：用作預(yù)測(cè)的樣值位于相鄰的不同行上 一維預(yù)測(cè)利用像素之間在水平方向上的相關(guān)性。一維預(yù)測(cè)利用像素之間在水平方向上的相關(guān)性。在水平方向亮度變化緩慢的圖像，有較好的預(yù)測(cè)在水平方向亮度變化緩慢的圖像，有較

9、好的預(yù)測(cè)效果。效果。 如果水平方向上亮度有突變，那么一階的一維預(yù)如果水平方向上亮度有突變，那么一階的一維預(yù)測(cè)經(jīng)常會(huì)測(cè)經(jīng)常會(huì) 給出錯(cuò)誤的預(yù)測(cè)數(shù)值。給出錯(cuò)誤的預(yù)測(cè)數(shù)值。在這種情況下，采用下面的二維預(yù)測(cè)，會(huì)有較好在這種情況下，采用下面的二維預(yù)測(cè)，會(huì)有較好的預(yù)測(cè)值。的預(yù)測(cè)值。 10 ()xx黑電平451122xxxx圖圖3-14對(duì)應(yīng)于圖像黑對(duì)應(yīng)于圖像黑白邊界處的幾個(gè)像素白邊界處的幾個(gè)像素 N階預(yù)測(cè)器的設(shè)計(jì)問(wèn)題階預(yù)測(cè)器的設(shè)計(jì)問(wèn)題 在最小均方誤差下的最佳預(yù)測(cè)器。在最小均方誤差下的最佳預(yù)測(cè)器。 下式表示預(yù)測(cè)誤差信號(hào)下式表示預(yù)測(cè)誤差信號(hào)e(n)平方值的統(tǒng)計(jì)平均。平方值的統(tǒng)計(jì)平均。 若上式最小時(shí)，表示在最小均方

10、誤差意義下，預(yù)測(cè)若上式最小時(shí)，表示在最小均方誤差意義下，預(yù)測(cè)最準(zhǔn)確，此時(shí)色預(yù)測(cè)器稱(chēng)為在最小均方誤差意義下最準(zhǔn)確，此時(shí)色預(yù)測(cè)器稱(chēng)為在最小均方誤差意義下的最佳預(yù)測(cè)器。的最佳預(yù)測(cè)器。 最佳預(yù)測(cè)器的系數(shù)最佳預(yù)測(cè)器的系數(shù) ai可以通過(guò)求極小值的方法求得。可以通過(guò)求極小值的方法求得。2221( ) ( )( ) ( )()Niie nx nx nx nax n i211Nkk=1( )2( )( )0 (1,2,)( )( ) ( )()()( ) ()() ()0 (3.42)R( )-a()0(1,2,)iiNkkiNkke ne ne niNaae ne nx na x nkx niax n x n

11、iax nk x niR iR ikiN 用輸入序列的自相關(guān)函數(shù) 表示： 如果對(duì)所需要壓縮的某類(lèi)圖像的自相關(guān)函數(shù)已經(jīng)作如果對(duì)所需要壓縮的某類(lèi)圖像的自相關(guān)函數(shù)已經(jīng)作過(guò)測(cè)量的話(huà)，則可通過(guò)求解上式所表示的方程組，獲過(guò)測(cè)量的話(huà)，則可通過(guò)求解上式所表示的方程組，獲得最佳預(yù)測(cè)器的系數(shù)值。得最佳預(yù)測(cè)器的系數(shù)值。 另一個(gè)事實(shí)另一個(gè)事實(shí)2m in12m in111()()()() ()()()()0()()()() ()()()() ()( 0 )()NkkiNkkNkkNkkenenxnaxnkenxnienenaenenxnaxnkenxnxnaxnkxnRaRk 而 由 （ 3 . 4 2 ）所 以 預(yù)測(cè)

12、誤差的平均功率比原信號(hào)的功率預(yù)測(cè)誤差的平均功率比原信號(hào)的功率R(0)要要小。在相同的均方量化誤差下，小。在相同的均方量化誤差下，e(n)比比x(n)要要求較少的量化級(jí)數(shù)，因此，傳送求較少的量化級(jí)數(shù)，因此，傳送e(n)比傳送比傳送x(n)的數(shù)據(jù)率要低。的數(shù)據(jù)率要低。 3.5.2 序列圖像中運(yùn)動(dòng)矢量的估值序列圖像中運(yùn)動(dòng)矢量的估值 1.運(yùn)動(dòng)矢量估值的必要性運(yùn)動(dòng)矢量估值的必要性 序列圖像在時(shí)間上的冗余情況可分如下幾種：序列圖像在時(shí)間上的冗余情況可分如下幾種： (1)對(duì)于靜止不動(dòng)的場(chǎng)景，當(dāng)前幀和前一幀的圖像內(nèi)容對(duì)于靜止不動(dòng)的場(chǎng)景，當(dāng)前幀和前一幀的圖像內(nèi)容是完全相同的；是完全相同的； (2)對(duì)于運(yùn)動(dòng)的物體

13、，只要知道其運(yùn)動(dòng)規(guī)律，就可以從對(duì)于運(yùn)動(dòng)的物體，只要知道其運(yùn)動(dòng)規(guī)律，就可以從前一前一 幀圖像推算出它在當(dāng)前幀中的位置；幀圖像推算出它在當(dāng)前幀中的位置； (3)攝像鏡頭對(duì)著場(chǎng)景橫向移動(dòng)攝像鏡頭對(duì)著場(chǎng)景橫向移動(dòng)(稱(chēng)為滑鏡頭稱(chēng)為滑鏡頭)、焦距變、焦距變化等操作會(huì)引起整個(gè)圖像的平移、放大或縮小。對(duì)于化等操作會(huì)引起整個(gè)圖像的平移、放大或縮小。對(duì)于這種情況，只要攝像機(jī)的運(yùn)動(dòng)規(guī)律和鏡頭改變的參數(shù)這種情況，只要攝像機(jī)的運(yùn)動(dòng)規(guī)律和鏡頭改變的參數(shù)已知，圖像隨時(shí)間所產(chǎn)生的變化也是可以推算出來(lái)的。已知，圖像隨時(shí)間所產(chǎn)生的變化也是可以推算出來(lái)的。 由電視圖像的相關(guān)性特點(diǎn)，可知：由電視圖像的相關(guān)性特點(diǎn)，可知： 發(fā)送端不一定

14、必須把每幀圖像上所有的像素都傳給收端，發(fā)送端不一定必須把每幀圖像上所有的像素都傳給收端，而只要將物體而只要將物體(或攝像機(jī)或攝像機(jī))的運(yùn)動(dòng)信息告知接收端，收端的運(yùn)動(dòng)信息告知接收端，收端就可根據(jù)運(yùn)動(dòng)信息和前一幀圖像的內(nèi)容來(lái)更新當(dāng)前幀圖就可根據(jù)運(yùn)動(dòng)信息和前一幀圖像的內(nèi)容來(lái)更新當(dāng)前幀圖像，這比全部傳送每幀圖像的具體細(xì)節(jié)所需的數(shù)據(jù)量要像，這比全部傳送每幀圖像的具體細(xì)節(jié)所需的數(shù)據(jù)量要小得多。小得多。 首先要做的是從圖像序列中提取運(yùn)動(dòng)物體的信息運(yùn)首先要做的是從圖像序列中提取運(yùn)動(dòng)物體的信息運(yùn)動(dòng)估值。動(dòng)估值。 為了簡(jiǎn)單起見(jiàn)，做出如下假設(shè)：為了簡(jiǎn)單起見(jiàn)，做出如下假設(shè)： (1)物體是剛體只在與攝像機(jī)鏡頭的光軸垂直

15、的平面物體是剛體只在與攝像機(jī)鏡頭的光軸垂直的平面內(nèi)移動(dòng)。即：物體的形變、旋轉(zhuǎn)、鏡頭焦距的變更等因內(nèi)移動(dòng)。即：物體的形變、旋轉(zhuǎn)、鏡頭焦距的變更等因素不考慮在內(nèi)；素不考慮在內(nèi)； (2)無(wú)論物體移動(dòng)到任何位置，照明條件都不變，即：無(wú)論物體移動(dòng)到任何位置，照明條件都不變，即：同一物體在所有序列圖像中亮度沒(méi)有變化；同一物體在所有序列圖像中亮度沒(méi)有變化； (3)被物體遮擋的背景和由于物體移開(kāi)而新暴露出來(lái)的被物體遮擋的背景和由于物體移開(kāi)而新暴露出來(lái)的背景部分都未不作特殊考慮。背景部分都未不作特殊考慮。 t 時(shí)刻運(yùn)動(dòng)物體的象素值時(shí)刻運(yùn)動(dòng)物體的象素值 bt 可用它在時(shí)間以前的值可用它在時(shí)間以前的值b t-表示：

16、表示： 含義：含義：t時(shí)刻的圖像是時(shí)刻的圖像是t-時(shí)刻的圖像經(jīng)適當(dāng)位移時(shí)刻的圖像經(jīng)適當(dāng)位移D后的后的結(jié)果。結(jié)果。 運(yùn)動(dòng)估值的分類(lèi)：運(yùn)動(dòng)估值的分類(lèi)： a 塊匹配方法塊匹配方法 b 像素遞歸方法像素遞歸方法( )()ttb zbzD 2.塊匹配方法塊匹配方法 方法描述：方法描述： a.將圖像劃分為許多互不重疊的子塊，并認(rèn)為子塊內(nèi)所將圖像劃分為許多互不重疊的子塊，并認(rèn)為子塊內(nèi)所有像素的位移量都相同。（每個(gè)子塊視為一個(gè)有像素的位移量都相同。（每個(gè)子塊視為一個(gè)“運(yùn)動(dòng)物運(yùn)動(dòng)物體體”） b.尋找匹配塊尋找匹配塊假設(shè)在圖像序列中，假設(shè)在圖像序列中，t 時(shí)刻對(duì)應(yīng)于第時(shí)刻對(duì)應(yīng)于第k幀圖像，幀圖像，t-時(shí)刻對(duì)時(shí)刻對(duì)

17、應(yīng)于應(yīng)于k-1幀圖像。對(duì)于幀圖像。對(duì)于k幀中的一個(gè)子塊，在幀中的一個(gè)子塊，在k-1幀中尋幀中尋找與其找與其最相似的子塊最相似的子塊，稱(chēng)為，稱(chēng)為匹配塊匹配塊。K-1幀稱(chēng)為幀稱(chēng)為K幀的幀的參考幀參考幀 c.尋找位移矢量尋找位移矢量認(rèn)為匹配塊在認(rèn)為匹配塊在k-1幀中的位置就是幀中的位置就是k幀塊位移前的位置，根幀塊位移前的位置，根據(jù)據(jù) (3-44)式則可以得到該子塊的位移矢量式則可以得到該子塊的位移矢量D。 塊匹配方法中最重要的問(wèn)題：塊匹配方法中最重要的問(wèn)題：(1)判別兩個(gè)子塊匹配的準(zhǔn)則；判別兩個(gè)子塊匹配的準(zhǔn)則；(2)尋找匹配塊搜索的方法。尋找匹配塊搜索的方法。準(zhǔn)則準(zhǔn)則a:歸一化的二維互相關(guān)函數(shù)（歸

18、一化的二維互相關(guān)函數(shù)（NCCF） 當(dāng)當(dāng)NCCF為為最大值時(shí)最大值時(shí)2個(gè)子塊匹配，對(duì)應(yīng)的個(gè)子塊匹配，對(duì)應(yīng)的 i，j 值即構(gòu)值即構(gòu)成位移矢量成位移矢量D。11121221211111( , )(,)( , )( , ) (,)MNkkmnMNMNkkmnmnb m n bm i njNCCF i jbm nbm i nj 準(zhǔn)則準(zhǔn)則b 求求2幀子塊亮度的均方差值幀子塊亮度的均方差值MSE： 當(dāng)當(dāng)MSE最小時(shí)表示最小時(shí)表示2個(gè)子塊匹配個(gè)子塊匹配。21111( , )( , )(,)(,)MNkkmnmmMSE i jb m nbmi njMNdi jd c. MAD準(zhǔn)則準(zhǔn)則 求幀間子塊亮度差的絕對(duì)值的

19、均值求幀間子塊亮度差的絕對(duì)值的均值MAD： 當(dāng)當(dāng)MAD最小時(shí)表示最小時(shí)表示2個(gè)子塊匹配個(gè)子塊匹配。1111( , )( , )(,)(,)MNkkmnmmMAD i jb m nbm i njMNdi jd d.計(jì)算塊亮度差的絕對(duì)值和計(jì)算塊亮度差的絕對(duì)值和SAD： SAD(I,j)=MN*MAD(i,j) 當(dāng)當(dāng)SAD最小時(shí)表示最小時(shí)表示2個(gè)子塊匹配個(gè)子塊匹配。 此準(zhǔn)則較常使用。此準(zhǔn)則較常使用。 研究結(jié)果表明，匹配判別準(zhǔn)則的不同對(duì)匹配精度，也研究結(jié)果表明，匹配判別準(zhǔn)則的不同對(duì)匹配精度，也即是對(duì)位移適量估值的精度影響不大。即是對(duì)位移適量估值的精度影響不大。 （2）搜索方法：為了節(jié)省計(jì)算量，在）搜索

20、方法：為了節(jié)省計(jì)算量，在k-1幀中的匹配搜幀中的匹配搜索只在一定范圍內(nèi)進(jìn)行。假設(shè)在索只在一定范圍內(nèi)進(jìn)行。假設(shè)在時(shí)間間隔內(nèi)時(shí)間間隔內(nèi)最大可能最大可能的水平和垂直位移量為的水平和垂直位移量為dm個(gè)像素，則搜索范圍個(gè)像素，則搜索范圍SR為為 SR（M+2 dm ）*（N+ 2dm ）1)全搜索全搜索:尋找最佳的匹配塊，需要將尋找最佳的匹配塊，需要將k-1幀中對(duì)應(yīng)的子塊在整個(gè)幀中對(duì)應(yīng)的子塊在整個(gè)搜索區(qū)內(nèi)沿水平和垂直方向逐個(gè)像素移動(dòng)，每移動(dòng)一次計(jì)算一搜索區(qū)內(nèi)沿水平和垂直方向逐個(gè)像素移動(dòng)，每移動(dòng)一次計(jì)算一次判決函數(shù)?？偟囊苿?dòng)次數(shù)次判決函數(shù)?？偟囊苿?dòng)次數(shù)Q為為 Q（2dm+1）2 此種搜索方法運(yùn)算量非常大。

21、此種搜索方法運(yùn)算量非常大。2)塊匹配的快速搜索方法：塊匹配的快速搜索方法：舉例：三步法舉例：三步法搜索過(guò)程：搜索過(guò)程：1）以待匹配塊中心的同位像素為中心，在中心點(diǎn)和與其距離）以待匹配塊中心的同位像素為中心，在中心點(diǎn)和與其距離4個(gè)個(gè)像素的像素的8個(gè)鄰域上計(jì)算判決函數(shù)個(gè)鄰域上計(jì)算判決函數(shù)SAD,取取SAD最小的點(diǎn)作為下一最小的點(diǎn)作為下一步搜索的中心步搜索的中心2）以該點(diǎn)為中心，對(duì)于中心相距）以該點(diǎn)為中心，對(duì)于中心相距2個(gè)像素的未搜索過(guò)的鄰域點(diǎn)進(jìn)個(gè)像素的未搜索過(guò)的鄰域點(diǎn)進(jìn)行搜索行搜索3）以上一步中）以上一步中SAD最小的點(diǎn)為中心，對(duì)距離中心最小的點(diǎn)為中心，對(duì)距離中心1個(gè)像素的未搜個(gè)像素的未搜索過(guò)的鄰

22、域點(diǎn)進(jìn)行搜索，最終找到最佳匹配位置。索過(guò)的鄰域點(diǎn)進(jìn)行搜索，最終找到最佳匹配位置。幾乎所有的快速搜索算法都基于如下的假設(shè)：幾乎所有的快速搜索算法都基于如下的假設(shè)：當(dāng)偏離最佳匹配位置時(shí)，判決函數(shù)（匹配誤差）值是當(dāng)偏離最佳匹配位置時(shí)，判決函數(shù)（匹配誤差）值是單調(diào)上升的。因此無(wú)需搜索所有點(diǎn)，只要沿著誤差值單調(diào)上升的。因此無(wú)需搜索所有點(diǎn)，只要沿著誤差值減少的方向進(jìn)行搜索，就能找到最佳匹配位置。減少的方向進(jìn)行搜索，就能找到最佳匹配位置。保證任何情況下找到全局極值點(diǎn)是困難的。保證任何情況下找到全局極值點(diǎn)是困難的。近幾年來(lái)人們提出了許多新的快速搜索算法，這些算法的搜索近幾年來(lái)人們提出了許多新的快速搜索算法，這

23、些算法的搜索策略概括如下：策略概括如下：1）運(yùn)動(dòng)矢量預(yù)測(cè)：）運(yùn)動(dòng)矢量預(yù)測(cè)：根據(jù)圖像內(nèi)容的連續(xù)性，相鄰塊的運(yùn)動(dòng)矢量一般是相近的。根據(jù)圖像內(nèi)容的連續(xù)性，相鄰塊的運(yùn)動(dòng)矢量一般是相近的。2）搜索提前中止：預(yù)先設(shè)定匹配誤差閾值）搜索提前中止：預(yù)先設(shè)定匹配誤差閾值3）緊湊的搜索圖形）緊湊的搜索圖形 3.5.3具有運(yùn)動(dòng)補(bǔ)償?shù)膸g預(yù)測(cè)具有運(yùn)動(dòng)補(bǔ)償?shù)膸g預(yù)測(cè) 1.前向預(yù)測(cè)前向預(yù)測(cè) 概念：不直接傳送當(dāng)前幀的像素值，而傳送當(dāng)前幀（即概念：不直接傳送當(dāng)前幀的像素值，而傳送當(dāng)前幀（即第第k幀）中像素幀）中像素x和前和前1幀幀(即即k-1幀幀)的同位像素的同位像素x之間的之間的差值，稱(chēng)為幀間預(yù)測(cè)。差值，稱(chēng)為幀間預(yù)測(cè)。 對(duì)

24、隔行掃描的電視信號(hào)，也可以用前一場(chǎng)來(lái)預(yù)測(cè)當(dāng)前場(chǎng)對(duì)隔行掃描的電視信號(hào)，也可以用前一場(chǎng)來(lái)預(yù)測(cè)當(dāng)前場(chǎng)的像素的像素(場(chǎng)間預(yù)測(cè)場(chǎng)間預(yù)測(cè))。當(dāng)圖像中存在著運(yùn)動(dòng)物體時(shí)簡(jiǎn)單的預(yù)測(cè)不能收到好的效果。當(dāng)圖像中存在著運(yùn)動(dòng)物體時(shí)簡(jiǎn)單的預(yù)測(cè)不能收到好的效果。考慮了物體移動(dòng)的幀間預(yù)測(cè)方法稱(chēng)為具有運(yùn)動(dòng)補(bǔ)償?shù)膸g預(yù)測(cè)。考慮了物體移動(dòng)的幀間預(yù)測(cè)方法稱(chēng)為具有運(yùn)動(dòng)補(bǔ)償?shù)膸g預(yù)測(cè)。 基本步驟：基本步驟： (1)將圖像分割成靜止的背景和若干運(yùn)動(dòng)的物體，各個(gè)將圖像分割成靜止的背景和若干運(yùn)動(dòng)的物體，各個(gè)物體可能有不同的位移。但構(gòu)成同一物體的所有像素的物體可能有不同的位移。但構(gòu)成同一物體的所有像素的位移相同。通過(guò)運(yùn)動(dòng)估值得到每個(gè)物體的位移矢

25、量；位移相同。通過(guò)運(yùn)動(dòng)估值得到每個(gè)物體的位移矢量； (2)利用位移矢量計(jì)算經(jīng)運(yùn)動(dòng)補(bǔ)償后的預(yù)測(cè)值；利用位移矢量計(jì)算經(jīng)運(yùn)動(dòng)補(bǔ)償后的預(yù)測(cè)值； (3)除了對(duì)預(yù)測(cè)誤差進(jìn)行編碼、傳送以外，還需要傳送除了對(duì)預(yù)測(cè)誤差進(jìn)行編碼、傳送以外，還需要傳送位移矢量以及如何進(jìn)行運(yùn)動(dòng)物體和靜止背景的分割等方位移矢量以及如何進(jìn)行運(yùn)動(dòng)物體和靜止背景的分割等方面的附加信息。面的附加信息。 實(shí)際上，將圖像分割成靜止區(qū)域和不同的運(yùn)動(dòng)區(qū)域非常實(shí)際上，將圖像分割成靜止區(qū)域和不同的運(yùn)動(dòng)區(qū)域非常困難，當(dāng)實(shí)時(shí)地完成時(shí)就更加困難。困難，當(dāng)實(shí)時(shí)地完成時(shí)就更加困難。 方法方法 將圖像分割成子塊，每塊看成是一個(gè)物體，按塊匹配的將圖像分割成子塊，每塊看

26、成是一個(gè)物體，按塊匹配的方法估計(jì)每個(gè)子塊的位移矢量，將經(jīng)過(guò)位移補(bǔ)償?shù)膸g方法估計(jì)每個(gè)子塊的位移矢量，將經(jīng)過(guò)位移補(bǔ)償?shù)膸g預(yù)測(cè)誤差預(yù)測(cè)誤差DFD和位移矢量和位移矢量D傳送給收端，收端就可以按傳送給收端，收端就可以按下式從已經(jīng)收到的前下式從已經(jīng)收到的前1幀信息中恢復(fù)出該子塊：幀信息中恢復(fù)出該子塊： bk(z)=bk-1(z-D)+DFD(z,D)下圖表示了下圖表示了K幀各塊及它們?cè)趲鲏K及它們?cè)趉-1幀中對(duì)應(yīng)的匹配塊之間的關(guān)系幀中對(duì)應(yīng)的匹配塊之間的關(guān)系從該塊的預(yù)測(cè)誤差和它的位移矢量所指向的從該塊的預(yù)測(cè)誤差和它的位移矢量所指向的k-1幀中的匹配塊，幀中的匹配塊，可以恢復(fù)出可以恢復(fù)出k幀中的對(duì)應(yīng)子塊。

27、幀中的對(duì)應(yīng)子塊。 注意：注意： 當(dāng)子塊中的像素實(shí)際上屬于位移量不同的物體時(shí)，當(dāng)子塊中的像素實(shí)際上屬于位移量不同的物體時(shí)，這種對(duì)整個(gè)子塊用同一位移量的預(yù)測(cè)就不夠準(zhǔn)這種對(duì)整個(gè)子塊用同一位移量的預(yù)測(cè)就不夠準(zhǔn)確會(huì)使預(yù)測(cè)誤差增加，從而影響到數(shù)據(jù)壓縮比確會(huì)使預(yù)測(cè)誤差增加，從而影響到數(shù)據(jù)壓縮比的提高。的提高。 2.后向預(yù)測(cè)和雙向預(yù)測(cè)后向預(yù)測(cè)和雙向預(yù)測(cè) 概念：概念： 前向預(yù)測(cè)：前向預(yù)測(cè)： 后向預(yù)測(cè)后向預(yù)測(cè):從后續(xù)的從后續(xù)的k+1幀圖像預(yù)測(cè)前面的幀圖像預(yù)測(cè)前面的k幀圖像幀圖像 雙向預(yù)測(cè)雙向預(yù)測(cè):采用前、后兩幀來(lái)預(yù)測(cè)中間幀采用前、后兩幀來(lái)預(yù)測(cè)中間幀 討論：討論： 預(yù)測(cè)誤差越小，傳輸?shù)臄?shù)據(jù)量就越低。預(yù)測(cè)誤差越小，傳

28、輸?shù)臄?shù)據(jù)量就越低。 雙向預(yù)測(cè)所付出的代價(jià)是，對(duì)每一個(gè)子塊需要傳送雙向預(yù)測(cè)所付出的代價(jià)是，對(duì)每一個(gè)子塊需要傳送2個(gè)位個(gè)位移矢量給收端，而且移矢量給收端，而且k幀的恢復(fù)必須等到接收到幀的恢復(fù)必須等到接收到k+1幀之幀之后才能進(jìn)行。后才能進(jìn)行。 即：編碼、解碼運(yùn)算的幀順序是即：編碼、解碼運(yùn)算的幀順序是k-1、k+1、k，而圖像顯，而圖像顯示的順序是示的順序是k-1、k、k+l。 要保持處理和顯示的連續(xù)性，編碼端和解碼端就分別需要保持處理和顯示的連續(xù)性，編碼端和解碼端就分別需要多引入要多引入1幀的延時(shí)。幀的延時(shí)。3.6 3.6 正交變換正交變換編碼編碼 例例1：?jiǎn)我活l率的正弦波：?jiǎn)我活l率的正弦波 在時(shí)

29、域中：采樣、量化、編碼在時(shí)域中：采樣、量化、編碼 在頻域中：頻率、波幅、初相角在頻域中：頻率、波幅、初相角 時(shí)域上采樣值之間存在非常強(qiáng)的相關(guān)性，數(shù)據(jù)冗余度時(shí)域上采樣值之間存在非常強(qiáng)的相關(guān)性，數(shù)據(jù)冗余度大，而在變換域上三個(gè)參數(shù)相互獨(dú)立，沒(méi)有相關(guān)性，大，而在變換域上三個(gè)參數(shù)相互獨(dú)立，沒(méi)有相關(guān)性，描述信號(hào)的數(shù)據(jù)量大大減少。描述信號(hào)的數(shù)據(jù)量大大減少。將空域圖像信號(hào)映射變換到另一個(gè)正交矢量空間及變換域，將圖將空域圖像信號(hào)映射變換到另一個(gè)正交矢量空間及變換域，將圖像像素值轉(zhuǎn)變成一組非相關(guān)的系數(shù)，然后對(duì)這些系數(shù)進(jìn)行量化和像像素值轉(zhuǎn)變成一組非相關(guān)的系數(shù)，然后對(duì)這些系數(shù)進(jìn)行量化和編碼。編碼。目的：去除相關(guān)，壓縮

30、數(shù)據(jù)。為信號(hào)找到一種最有效的表示方式。目的：去除相關(guān)，壓縮數(shù)據(jù)。為信號(hào)找到一種最有效的表示方式。 例例2：由相鄰兩個(gè)像素組成的：由相鄰兩個(gè)像素組成的12子圖像中，設(shè)每個(gè)子圖像中，設(shè)每個(gè)像素取像素取8個(gè)灰度級(jí)（個(gè)灰度級(jí)（3bit量化），下圖中量化），下圖中x1軸表示第一軸表示第一個(gè)像素可能取的個(gè)像素可能取的8個(gè)灰度值，個(gè)灰度值，x2軸表示第二個(gè)像素可軸表示第二個(gè)像素可能取的能取的8個(gè)灰度值，由個(gè)灰度值，由x1,x2組成的二維坐標(biāo)空間中不組成的二維坐標(biāo)空間中不同坐標(biāo)點(diǎn)對(duì)應(yīng)于不同的同坐標(biāo)點(diǎn)對(duì)應(yīng)于不同的12子圖像。子圖像。 變換后的坐標(biāo)系中，圖像子塊的兩個(gè)像素之間的相關(guān)變換后的坐標(biāo)系中，圖像子塊的兩個(gè)

31、像素之間的相關(guān)性減弱，能量的分布向性減弱，能量的分布向x1集中。集中。3.6 3.6 正交變換正交變換編碼編碼3.6.1 3.6.1 最佳線(xiàn)性正交變換最佳線(xiàn)性正交變換 思路：思路： 假設(shè)：一個(gè)離散信號(hào)由假設(shè)：一個(gè)離散信號(hào)由N N個(gè)采樣值組成，則可以個(gè)采樣值組成，則可以認(rèn)為它是一個(gè)在認(rèn)為它是一個(gè)在N N維空間中的維空間中的一個(gè)列向量一個(gè)列向量XT=(x1,x2,xn)。 為了找到有效的表示方法，可以選取為了找到有效的表示方法，可以選取X X的一個(gè)正的一個(gè)正交變換，使交變換，使 YTX （3-53）YT=(y1,y2,yn)做變換的目的：做變換的目的：要尋找一個(gè)變換矩陣要尋找一個(gè)變換矩陣T，將經(jīng)上

32、式變換得到的，將經(jīng)上式變換得到的Y用一個(gè)由用一個(gè)由M(MN)個(gè)分量構(gòu)成的子集來(lái)近似。當(dāng)刪去個(gè)分量構(gòu)成的子集來(lái)近似。當(dāng)刪去Y中剩下的中剩下的(N-M)個(gè)分量，僅用含個(gè)分量，僅用含M個(gè)分量的子集來(lái)恢復(fù)個(gè)分量的子集來(lái)恢復(fù)X時(shí)，不時(shí)，不會(huì)引起明顯的誤差。會(huì)引起明顯的誤差?；蛘哒f(shuō)：用或者說(shuō)：用Y的只有的只有M個(gè)分量的子集來(lái)代表有個(gè)分量的子集來(lái)代表有N個(gè)分量的個(gè)分量的信號(hào)信號(hào)X，從而達(dá)到數(shù)據(jù)壓縮的目的。，從而達(dá)到數(shù)據(jù)壓縮的目的。 關(guān)鍵是：尋找變換矩陣關(guān)鍵是：尋找變換矩陣T，即：找到最佳正交變換。，即：找到最佳正交變換。最佳的判斷標(biāo)準(zhǔn)：最佳的判斷標(biāo)準(zhǔn)：使得在恢復(fù)使得在恢復(fù)X時(shí)所產(chǎn)生的均方誤差最小。時(shí)所產(chǎn)生的

33、均方誤差最小。 設(shè)變換矩陣具有下列形式設(shè)變換矩陣具有下列形式 TH1， 2，.， N (3-54) i是是N維列向量，并且歸一化正交，即：維列向量，并且歸一化正交，即： 1 （ik） iH . k (3-55) 0 （ik） i相互正交，故其線(xiàn)性獨(dú)立。相互正交，故其線(xiàn)性獨(dú)立。 以前的知識(shí)：以前的知識(shí)： N個(gè)線(xiàn)性獨(dú)立的向量可以生成一個(gè)個(gè)線(xiàn)性獨(dú)立的向量可以生成一個(gè)N維空間，這一組向維空間，這一組向量稱(chēng)為該空間的基，其中的每一個(gè)量稱(chēng)為該空間的基，其中的每一個(gè)i稱(chēng)為基向量。稱(chēng)為基向量。由（由（3-54）和（）和（3-55）知：）知： TTHI 所以所以 T的逆矩陣：的逆矩陣：T-1TH （3-56）當(dāng)

34、當(dāng)T為實(shí)數(shù)矩陣，且為實(shí)數(shù)矩陣，且T-1TH時(shí)，稱(chēng)時(shí)，稱(chēng)T為正交矩陣，對(duì)應(yīng)的為正交矩陣，對(duì)應(yīng)的變換為正交變換。變換為正交變換。 由由Y=TX和和(3-56)式，得到式，得到 XTHYy1 1+y2 2+.+yN N上式表明將上式表明將X轉(zhuǎn)換到由基向量轉(zhuǎn)換到由基向量i(i1，2，N)生成的生成的N維空間維空間(通常稱(chēng)為變換域通常稱(chēng)為變換域)中。中。yi代表代表X在在i上投影的大小，上投影的大小，稱(chēng)為變換系數(shù)。稱(chēng)為變換系數(shù)。因此，因此，由變換系數(shù)所構(gòu)成的向量由變換系數(shù)所構(gòu)成的向量Y是信號(hào)是信號(hào)X在變換域中的在變換域中的表示。表示。 假設(shè)信號(hào)假設(shè)信號(hào)X是一個(gè)均值為零的隨機(jī)向量，即是一個(gè)均值為零的隨機(jī)向

35、量，即=0。 若只保留若只保留M(MN)個(gè)變換系數(shù)個(gè)變換系數(shù),將其余將其余(N-M)個(gè)系數(shù)個(gè)系數(shù)置為零，則所得到的置為零，則所得到的X的近似值的近似值XM與原信號(hào)的差值與原信號(hào)的差值X為為 XX-XM 其均方誤差其均方誤差MSE為為 MSE= =1Niii My*1121.(3 71)NNHikiki Mk MNii Myyy 359）由由Y=TX可知：可知： 標(biāo)量的轉(zhuǎn)置為其自身標(biāo)量的轉(zhuǎn)置為其自身，（3-59）可改寫(xiě)為：）可改寫(xiě)為：當(dāng)當(dāng)=0時(shí)，時(shí)，即為即為X的協(xié)方差矩陣的協(xié)方差矩陣 。可以證明得：可以證明得：iH i1的條件下，使的條件下，使MSE為最小的條件為最小的條件是是.HiiyX11N

36、NHHHiiiii Mi MMSEy yXX XXiii 上式看出上式看出i和和i分別是矩陣分別是矩陣 的本征向量和本征值。的本征向量和本征值。也就是說(shuō)，以信號(hào)的協(xié)方差矩陣也就是說(shuō)，以信號(hào)的協(xié)方差矩陣 的本征向量的本征向量i(il，2，N)組成的變換矩陣是均方誤差準(zhǔn)則下的最組成的變換矩陣是均方誤差準(zhǔn)則下的最佳變換矩陣，用此矩陣構(gòu)成的最佳變換佳變換矩陣，用此矩陣構(gòu)成的最佳變換YTX稱(chēng)為稱(chēng)為卡南洛伊夫變換卡南洛伊夫變換KLT。 XX 經(jīng)經(jīng)KL變換后，變換后，Y的協(xié)方差矩陣的協(xié)方差矩陣 為為 （根據(jù)根據(jù)YTX）Y12.0.0HHYXNY YTTKL變換解除了隨機(jī)向量變換解除了隨機(jī)向量X的分量之間的相

37、關(guān)性，的分量之間的相關(guān)性，在變換域中在變換域中Y的各分量之間是互不相關(guān)的的各分量之間是互不相關(guān)的應(yīng)用的先修知識(shí)：應(yīng)用的先修知識(shí)：A為為n階實(shí)對(duì)稱(chēng)矩陣，則有正交矩陣階實(shí)對(duì)稱(chēng)矩陣，則有正交矩陣P,使使P-1AP=min1Nii MMSE上式說(shuō)明最小均方誤差等于上式說(shuō)明最小均方誤差等于Y向量中被丟棄的分量的方向量中被丟棄的分量的方差之和。差之和。由此可知，應(yīng)該選擇具有較大方差的由此可知，應(yīng)該選擇具有較大方差的M個(gè)個(gè)Y分量所構(gòu)成分量所構(gòu)成的子集來(lái)恢復(fù)的子集來(lái)恢復(fù)X，以使得恢復(fù)后所產(chǎn)生的誤差最小。，以使得恢復(fù)后所產(chǎn)生的誤差最小。缺點(diǎn)：缺點(diǎn)：KL變換的基向量與信號(hào)的統(tǒng)計(jì)特性有關(guān)，變換變換的基向量與信號(hào)的統(tǒng)

38、計(jì)特性有關(guān)，變換矩陣不是恒定的，需要臨時(shí)計(jì)算，同時(shí)也缺乏相應(yīng)的快矩陣不是恒定的，需要臨時(shí)計(jì)算，同時(shí)也缺乏相應(yīng)的快速算法速算法 3.6.2離散余弦變換離散余弦變換 選擇不同的正交基向量，可以得到不同的正交變換。選擇不同的正交基向量，可以得到不同的正交變換。 從數(shù)學(xué)上可以證明，各種正交變換都能在不同程度上從數(shù)學(xué)上可以證明，各種正交變換都能在不同程度上減小隨機(jī)向量的相關(guān)性。減小隨機(jī)向量的相關(guān)性。 信號(hào)經(jīng)過(guò)大多數(shù)正交變換后，能量會(huì)相對(duì)集中在少數(shù)信號(hào)經(jīng)過(guò)大多數(shù)正交變換后，能量會(huì)相對(duì)集中在少數(shù)變換系數(shù)上，刪去對(duì)信號(hào)貢獻(xiàn)較小變換系數(shù)上，刪去對(duì)信號(hào)貢獻(xiàn)較小(方差小方差小)的系數(shù)，的系數(shù)，只利用保留下來(lái)的系數(shù)恢

39、復(fù)信號(hào)時(shí)，不會(huì)引起明顯的只利用保留下來(lái)的系數(shù)恢復(fù)信號(hào)時(shí)，不會(huì)引起明顯的失真。失真。 因此，不同的正交變換，例如，離散傅氏變換因此，不同的正交變換，例如，離散傅氏變換(DFT)，離散余弦變換離散余弦變換(DCT)，沃爾什，沃爾什-哈達(dá)馬變換哈達(dá)馬變換(WHT)等均等均在數(shù)據(jù)壓縮中得到不同程度的應(yīng)用，只是在均方誤差在數(shù)據(jù)壓縮中得到不同程度的應(yīng)用，只是在均方誤差準(zhǔn)則下，性能不如準(zhǔn)則下，性能不如KLT好。好。 余弦變換是傅立葉變換的一種特殊情況。余弦變換是傅立葉變換的一種特殊情況。 當(dāng)傅立葉級(jí)數(shù)展開(kāi)式中，被展開(kāi)的函數(shù)是實(shí)偶函當(dāng)傅立葉級(jí)數(shù)展開(kāi)式中，被展開(kāi)的函數(shù)是實(shí)偶函數(shù)時(shí)，傅立葉級(jí)數(shù)中只包含余弦項(xiàng)。余弦

40、變換的數(shù)時(shí)，傅立葉級(jí)數(shù)中只包含余弦項(xiàng)。余弦變換的名字由來(lái)，或稱(chēng)之為離散余弦變換。名字由來(lái)，或稱(chēng)之為離散余弦變換。 離散余弦變換在數(shù)字圖像數(shù)據(jù)壓縮編碼技術(shù)中，離散余弦變換在數(shù)字圖像數(shù)據(jù)壓縮編碼技術(shù)中，可與最佳變換可與最佳變換K-L變換媲美。因?yàn)樽儞Q媲美。因?yàn)镈CT與與K-L變變換壓縮性能和誤差相接近，而換壓縮性能和誤差相接近，而DCT計(jì)算復(fù)雜度適計(jì)算復(fù)雜度適中又具有可分離特性還有快速算法等特點(diǎn)，中又具有可分離特性還有快速算法等特點(diǎn)，所以近年來(lái)在圖像數(shù)據(jù)壓縮中，采用離散余弦變所以近年來(lái)在圖像數(shù)據(jù)壓縮中，采用離散余弦變換編碼的方案很多，特別是換編碼的方案很多，特別是20世紀(jì)世紀(jì)90年代迅速崛年代迅速

41、崛起的計(jì)算機(jī)多媒體技術(shù)當(dāng)中起的計(jì)算機(jī)多媒體技術(shù)當(dāng)中JPEG、MPEG、R.261等壓縮標(biāo)準(zhǔn)。都用到離散余弦變換編碼進(jìn)等壓縮標(biāo)準(zhǔn)。都用到離散余弦變換編碼進(jìn)行數(shù)據(jù)壓縮。行數(shù)據(jù)壓縮。112011202(21)( ) ( )( )( )cos(0,1,2,1)22(21)( ) ( )( ) ( )cos(0,1,2,1)2( )( )010NkNnknS nC ns knNNNkns kC n S nkNNNs kS nnn 其 中為 信 號(hào) 樣 值 ，為 變 換 系 數(shù) 且1C(n)=2一維的一維的DCT正變換和反變換正變換和反變換DCT變換的核函數(shù)變換的核函數(shù)一維一維8個(gè)像素時(shí)對(duì)應(yīng)的基函數(shù)數(shù)據(jù)個(gè)

42、像素時(shí)對(duì)應(yīng)的基函數(shù)數(shù)據(jù) 由一維由一維DCT可以直接擴(kuò)展到二維，即可以直接擴(kuò)展到二維，即110011002(21)(21)( , )( ) ( )( , )coscos22(0,1,2,1;0,1,2,1)2(21)(21)( , )( ) ( ) ( , )coscos22(0,1,2,1;0,1,2,1)( )NNjkNNuvjukvS u vC n C vs j kNNNuNvNjnkvs j kC u C v S u vNNNjNkNs k 其中為信號(hào)樣值， ( )01010S nuuvv為變換系數(shù)且1C(u)=21C(v)=2u由此可以看出：由此可以看出：DCT將能量將能量集中于頻率平

43、面的左上角集中于頻率平面的左上角DCT變換后信號(hào)能量主要集中于左上角變換后信號(hào)能量主要集中于左上角44二維二維DCT的基圖像的基圖像N=8時(shí)的變換矩陣時(shí)的變換矩陣T課后課后14題題b圖對(duì)應(yīng)的圖像塊圖對(duì)應(yīng)的圖像塊A：以下代碼產(chǎn)生變換矩陣以下代碼產(chǎn)生變換矩陣jihanshujuzhen,并按矩陣運(yùn)算進(jìn)行并按矩陣運(yùn)算進(jìn)行DCT變變換，最后將變換結(jié)果與換，最后將變換結(jié)果與Matlab中的二維中的二維DCT變換函數(shù)變換函數(shù)DCT2（）進(jìn)（）進(jìn)行比較行比較1010101010101010),(),(2) 12(cos2) 12(cos),()()(2),( :IDCT),(),(2) 12(cos2) 1

44、2(cos),()()(2, :FDCTNuNvNuNvNiNjNiNjvujiqvuFNvjNuivuFvCuCNjifvujipjifNvjNuijifvCuCNv)F(u在以變換系數(shù)在以變換系數(shù)F(u,v)作加權(quán)的情況下，由正交變換的基作加權(quán)的情況下，由正交變換的基圖像的組合，可以重新得到原始圖像圖像的組合，可以重新得到原始圖像 基于基于DFT的快速的快速DCT算法算法K-1nkKk=0exp(2 / )KDFTF(n)=s(k)W(0,1,1)N( ),0,1,1,1,21,kWjknKs k kNkN NN令則 個(gè)點(diǎn)的可表示為若有一個(gè) 點(diǎn)的實(shí)數(shù)序列定義一與該序列相對(duì)應(yīng)于(2N-1)/

45、2點(diǎn)為偶對(duì)稱(chēng)的序列,即s(2N-k-1)=s(k),N-12N-1nknkKKk=0k=N2NKN-1N-1nk-n(i+1)KKk=0i=0n/2Kn/2nkn/2-n(k+1)KKKKK2NDFTs(k)Ws()WW1(K2N),s(k)Ws(i)Wki,W/2,Ws(k)W .W/2s(k)W.i則整個(gè)點(diǎn)序列的可表示為F(n)=2N-k-1設(shè)2N-k-1,并注意到因?yàn)樯鲜阶優(yōu)镕(n)=用 代替 并在等式兩邊同乘得1F(n)=2N-1N-1n/2Kk=0k=0N-1k=0W/2(2k+1)ns(k)cos(3 87)2N (3-75) 為了進(jìn)一步簡(jiǎn)化上述關(guān)系，注意到，由于上式右端是為了進(jìn)一

46、步簡(jiǎn)化上述關(guān)系，注意到，由于上式右端是實(shí)數(shù)，因此左端也應(yīng)為實(shí)數(shù)。用實(shí)數(shù)，因此左端也應(yīng)為實(shí)數(shù)。用An和和Bn分別表示分別表示F(n)的實(shí)數(shù)和虛數(shù)部分，則有的實(shí)數(shù)和虛數(shù)部分，則有 令上式的虛部為零則令上式的虛部為零則 將Bn代入(3-88)得到2( )()(cossin) (3 88)22nKnnF n WAnjBnjNN()2nBnAntgN (3-76)(3-76)2( )sec()Re( ) sec()(3 90)22nKnnF n WAnF nNN(3-78)代入代入(3-75)得得N-12k=01(2k+1)n1( )s(k)cosRe( ) sec()22N22nKnF n WF nN

47、結(jié)論；一個(gè)函數(shù)的結(jié)論；一個(gè)函數(shù)的DCT系數(shù)可以由該函數(shù)對(duì)應(yīng)的偶函數(shù)的系數(shù)可以由該函數(shù)對(duì)應(yīng)的偶函數(shù)的DFT系數(shù)的實(shí)部得到。系數(shù)的實(shí)部得到。 (3-78) 討論討論: (1)先前知識(shí)，二維信號(hào)的傅氏變換的系數(shù)代表它所對(duì)先前知識(shí)，二維信號(hào)的傅氏變換的系數(shù)代表它所對(duì)應(yīng)的空間頻率分量的復(fù)振幅。應(yīng)的空間頻率分量的復(fù)振幅。 (3-79)式表明，雖然式表明，雖然DCT系數(shù)并不與空間頻率分量的復(fù)系數(shù)并不與空間頻率分量的復(fù)振幅嚴(yán)格相等，但有一定的對(duì)應(yīng)關(guān)系。振幅嚴(yán)格相等，但有一定的對(duì)應(yīng)關(guān)系。 特別是特別是n0時(shí)的時(shí)的DCT系數(shù)與系數(shù)與DFT的零頻分量一樣，代的零頻分量一樣，代表空間域內(nèi)信號(hào)的均值；表空間域內(nèi)信號(hào)的均

48、值； (2)一個(gè)函數(shù)的一個(gè)函數(shù)的DCT系數(shù)可以通過(guò)與該函數(shù)對(duì)應(yīng)的偶函系數(shù)可以通過(guò)與該函數(shù)對(duì)應(yīng)的偶函數(shù)的數(shù)的DFT系數(shù)得到。系數(shù)得到。 由于偶函數(shù)的對(duì)稱(chēng)性減小了由于偶函數(shù)的對(duì)稱(chēng)性減小了DFT中由于周期延拓而產(chǎn)中由于周期延拓而產(chǎn)生的空間域中邊緣的不連續(xù)性，從而使能量在頻率域生的空間域中邊緣的不連續(xù)性，從而使能量在頻率域內(nèi)更為集中。內(nèi)更為集中。 因此在數(shù)據(jù)壓縮應(yīng)用中因此在數(shù)據(jù)壓縮應(yīng)用中DCT比比DFT具有更好的性能具有更好的性能. 3.4取樣頻率的轉(zhuǎn)換取樣頻率的轉(zhuǎn)換 幾個(gè)概念幾個(gè)概念 a 抽取抽取(下取樣）下取樣） 由高取樣率的樣值去推算低取樣率樣點(diǎn)上的數(shù)值的技術(shù)由高取樣率的樣值去推算低取樣率樣點(diǎn)上

49、的數(shù)值的技術(shù) b 內(nèi)插（上取樣）內(nèi)插（上取樣） 由低取樣率的樣值去估計(jì)在原來(lái)較高頻率的取樣點(diǎn)上的由低取樣率的樣值去估計(jì)在原來(lái)較高頻率的取樣點(diǎn)上的樣值，這種技術(shù)稱(chēng)為內(nèi)插。樣值，這種技術(shù)稱(chēng)為內(nèi)插。應(yīng)用：應(yīng)用：1）通過(guò)取樣頻率的轉(zhuǎn)換，可以使傳送數(shù)據(jù)量增多）通過(guò)取樣頻率的轉(zhuǎn)換，可以使傳送數(shù)據(jù)量增多或減少，實(shí)現(xiàn)傳送圖像高低分辨率的轉(zhuǎn)換?；驕p少，實(shí)現(xiàn)傳送圖像高低分辨率的轉(zhuǎn)換。2）當(dāng)需要將數(shù)字信號(hào)與一些特殊系統(tǒng)的時(shí)鐘同步時(shí)，可）當(dāng)需要將數(shù)字信號(hào)與一些特殊系統(tǒng)的時(shí)鐘同步時(shí)，可能需要進(jìn)行采樣率的轉(zhuǎn)換；能需要進(jìn)行采樣率的轉(zhuǎn)換；3）一個(gè)數(shù)字電話(huà)系統(tǒng)，通過(guò)該系統(tǒng)傳輸?shù)募扔姓Z(yǔ)音信號(hào)，）一個(gè)數(shù)字電話(huà)系統(tǒng)，通過(guò)該系統(tǒng)傳輸?shù)?/p>

50、既有語(yǔ)音信號(hào)，也有傳真（也有傳真（FAX）信號(hào)，甚至有視頻信號(hào)，這些信號(hào)的）信號(hào)，甚至有視頻信號(hào)，這些信號(hào)的頻率成分相差甚遠(yuǎn)。因此，該系統(tǒng)應(yīng)具有多種抽樣頻率頻率成分相差甚遠(yuǎn)。因此，該系統(tǒng)應(yīng)具有多種抽樣頻率并自動(dòng)地完成采樣率的轉(zhuǎn)換并自動(dòng)地完成采樣率的轉(zhuǎn)換3.4.1下取樣下取樣(亞取樣）亞取樣） 取樣頻率取樣頻率f1略高于奈氏頻率；略高于奈氏頻率； 用用f2 f1/n ( f2小于奈氏頻率小于奈氏頻率 )作為取樣頻率直接對(duì)源信號(hào)抽樣，作為取樣頻率直接對(duì)源信號(hào)抽樣，發(fā)生頻譜混疊情形。發(fā)生頻譜混疊情形。 取樣頻率為取樣頻率為f1/2時(shí)發(fā)生時(shí)發(fā)生頻譜混疊部分頻譜混疊部分 為避免混疊失真，可先用一個(gè)低通濾

51、波器將圖為避免混疊失真，可先用一個(gè)低通濾波器將圖(a)所示所示的頻譜的基帶部分取出，恢復(fù)出原來(lái)的模擬信號(hào)，然后的頻譜的基帶部分取出，恢復(fù)出原來(lái)的模擬信號(hào)，然后用另一低通濾波器將此模擬信號(hào)的頻帶限制到用另一低通濾波器將此模擬信號(hào)的頻帶限制到f22，再重新取樣，便可得到取樣頻率為再重新取樣，便可得到取樣頻率為f2的樣值。的樣值。含義：將信號(hào)含義：將信號(hào)x(n)作作M倍的抽取后得到的倍的抽取后得到的y(n)頻譜等于原信號(hào)的頻譜先做頻譜等于原信號(hào)的頻譜先做M倍的擴(kuò)展，再在倍的擴(kuò)展，再在w軸上作軸上作2k的移位，幅度降為原來(lái)的的移位，幅度降為原來(lái)的1/M后再后再疊加疊加以下以下2頁(yè)為證明過(guò)程頁(yè)為證明過(guò)程

52、利用周期序列的離散傅里葉級(jí)數(shù)利用周期序列的離散傅里葉級(jí)數(shù)DFS反變換：反變換：kMnknMjMkknMjkMnnpenpkPekPMnp為一脈沖串?dāng)?shù)為離散傅里葉級(jí)數(shù)的系其中)()(1)()()(1)(102102 102102102102102)(1)(1)(1)(11)()()()()()()()(MkMkwjMknMnknMjMknnMkwjMknMnknMjMnnMkknMjnMnmmmmeXMzenxMenxMzenxMzeMnxznxzMmxzmyZYMmxMmxmy3.4.2 3.4.2 上取樣上取樣 線(xiàn)性?xún)?nèi)插線(xiàn)性?xún)?nèi)插 是一種廣泛的內(nèi)插方法，它利用兩相鄰是一種廣泛的內(nèi)插方法，它利用

53、兩相鄰樣值得加權(quán)和內(nèi)插出二者之間任意位置樣值得加權(quán)和內(nèi)插出二者之間任意位置上的數(shù)值，每個(gè)樣值與該值到內(nèi)插位置上的數(shù)值，每個(gè)樣值與該值到內(nèi)插位置的距離成反比。的距離成反比。 3.7 3.7 子帶編碼子帶編碼 3.7.13.7.1子帶編碼工作原理子帶編碼工作原理 在子帶編碼中，如圖在子帶編碼中，如圖3-243-24所示所示. . 首先用一組帶通濾波器將輸入信號(hào)分成若干個(gè)在不同頻首先用一組帶通濾波器將輸入信號(hào)分成若干個(gè)在不同頻段上的子帶信號(hào)段上的子帶信號(hào); ; 然后將這些子帶信號(hào)經(jīng)過(guò)頻率搬移轉(zhuǎn)變成基帶信號(hào)，再然后將這些子帶信號(hào)經(jīng)過(guò)頻率搬移轉(zhuǎn)變成基帶信號(hào)，再對(duì)它們?cè)谀问项l率上分別取樣。取樣后的信號(hào)經(jīng)過(guò)

54、量化、對(duì)它們?cè)谀问项l率上分別取樣。取樣后的信號(hào)經(jīng)過(guò)量化、編碼，并合成成一個(gè)總的碼流傳送給接收端。編碼，并合成成一個(gè)總的碼流傳送給接收端。 在接收端，首先把碼流分成與原來(lái)的各子帶信號(hào)相對(duì)應(yīng)在接收端，首先把碼流分成與原來(lái)的各子帶信號(hào)相對(duì)應(yīng)的子帶碼流，然后解碼、將頻譜搬移至原來(lái)的位置，最的子帶碼流，然后解碼、將頻譜搬移至原來(lái)的位置，最后經(jīng)帶通濾波、相加得到重建的信號(hào)。后經(jīng)帶通濾波、相加得到重建的信號(hào)。 在子帶編碼中，若各子帶的帶寬在子帶編碼中，若各子帶的帶寬Wk是相同的，是相同的，則稱(chēng)為則稱(chēng)為等帶寬子帶編碼等帶寬子帶編碼；若；若Wk是互不相同的，是互不相同的，則稱(chēng)為則稱(chēng)為變帶寬子帶編碼變帶寬子帶編碼

55、。 子帶編碼的壓縮數(shù)據(jù)的原因和優(yōu)點(diǎn)：子帶編碼的壓縮數(shù)據(jù)的原因和優(yōu)點(diǎn)： (1)可以利用人耳可以利用人耳(或人眼或人眼)對(duì)不同頻率信號(hào)的對(duì)不同頻率信號(hào)的感知靈敏度不同的特性，在人的聽(tīng)覺(jué)感知靈敏度不同的特性，在人的聽(tīng)覺(jué)(或視覺(jué)或視覺(jué))不敏感的頻段采用較租糙的量化，從而達(dá)到數(shù)不敏感的頻段采用較租糙的量化，從而達(dá)到數(shù)據(jù)壓縮的目的；據(jù)壓縮的目的； (2)各子帶的量化噪聲都束縛在本子帶內(nèi)，這各子帶的量化噪聲都束縛在本子帶內(nèi)，這就可以避免能量較小的頻帶內(nèi)的信號(hào)被其它頻就可以避免能量較小的頻帶內(nèi)的信號(hào)被其它頻段中的量化噪聲所掩蓋。段中的量化噪聲所掩蓋。 子帶編碼的關(guān)鍵部件討論：子帶編碼的關(guān)鍵部件討論： 帶通濾波

56、器組是子帶編碼的重要部件，它影響到子帶帶通濾波器組是子帶編碼的重要部件，它影響到子帶編碼的復(fù)雜程度和性能。編碼的復(fù)雜程度和性能。 問(wèn)題問(wèn)題1，注意到，如果各子帶的下截止頻率，注意到，如果各子帶的下截止頻率f1k恰好是恰好是該子帶寬度的整數(shù)倍，即該子帶寬度的整數(shù)倍，即 f1knWk （k1，2，M） （3-92） (其中其中n是一非負(fù)整數(shù)，是一非負(fù)整數(shù)，M為子帶的個(gè)數(shù)為子帶的個(gè)數(shù))，則可以不必，則可以不必將帶通信號(hào)搬移到基帶上，就直接以取樣頻率將帶通信號(hào)搬移到基帶上，就直接以取樣頻率fsk2Wk對(duì)子帶信號(hào)取樣，而不會(huì)產(chǎn)生混疊失真。對(duì)子帶信號(hào)取樣，而不會(huì)產(chǎn)生混疊失真。 滿(mǎn)足上式條件的子帶濾波器組稱(chēng)

57、為整數(shù)子帶濾波器組。滿(mǎn)足上式條件的子帶濾波器組稱(chēng)為整數(shù)子帶濾波器組。 以以M4的變帶寬子帶為例：的變帶寬子帶為例： 圖圖3-25給出了第給出了第3個(gè)子帶的取樣過(guò)程。圖中個(gè)子帶的取樣過(guò)程。圖中(a)是輸入信號(hào)是輸入信號(hào)的頻譜；的頻譜；(b)是第是第3個(gè)子帶信號(hào)的頻譜，其下截止頻率個(gè)子帶信號(hào)的頻譜，其下截止頻率f132W3 ；(c)是以是以fs32W3 的頻率對(duì)的頻率對(duì)(b)取樣后，所得到取樣后，所得到的信號(hào)的頻譜。的信號(hào)的頻譜。 采用整數(shù)子帶濾波器組的優(yōu)點(diǎn)：采用整數(shù)子帶濾波器組的優(yōu)點(diǎn)： 采用整數(shù)于帶濾波器組省去了進(jìn)行頻譜搬移所需要的調(diào)采用整數(shù)于帶濾波器組省去了進(jìn)行頻譜搬移所需要的調(diào)制器和解調(diào)器，

58、使系統(tǒng)得以簡(jiǎn)化。制器和解調(diào)器，使系統(tǒng)得以簡(jiǎn)化。 輸入信號(hào)的總帶寬輸入信號(hào)的總帶寬W ，按下式計(jì)算：，按下式計(jì)算：1MkkWW 例子：下圖給出使用抽取和內(nèi)插的且例子：下圖給出使用抽取和內(nèi)插的且M2的子帶編碼的子帶編碼和解碼的原理方框圖。和解碼的原理方框圖。 此時(shí)，系統(tǒng)的輸入和輸出看成是已在奈氏頻率下取樣的此時(shí)，系統(tǒng)的輸入和輸出看成是已在奈氏頻率下取樣的離散信號(hào)，圖離散信號(hào)，圖(b)給出了它對(duì)應(yīng)的頻譜。假設(shè)用帶通濾給出了它對(duì)應(yīng)的頻譜。假設(shè)用帶通濾波器取出圖波器取出圖(b)中斜線(xiàn)所示的上子帶經(jīng)中斜線(xiàn)所示的上子帶經(jīng)2：1抽取后的抽取后的上子帶的頻譜如圖上子帶的頻譜如圖(c)所示。在接收端，再用所示。在

59、接收端，再用1：2的內(nèi)插的內(nèi)插器，將頻譜恢復(fù)到原來(lái)的位置。器，將頻譜恢復(fù)到原來(lái)的位置。 在采用整數(shù)子帶濾波器的系統(tǒng)中，總的傳輸速率在采用整數(shù)子帶濾波器的系統(tǒng)中，總的傳輸速率I為為 式中，式中，Rk為第為第K個(gè)子帶中每個(gè)樣值量化的比特?cái)?shù)。個(gè)子帶中每個(gè)樣值量化的比特?cái)?shù)。 問(wèn)題問(wèn)題2，濾波器的具體實(shí)現(xiàn)不可能是理想的帶通，其幅，濾波器的具體實(shí)現(xiàn)不可能是理想的帶通，其幅度響應(yīng)不可避免地帶有有限的滾降。因此在劃分子帶時(shí)，度響應(yīng)不可避免地帶有有限的滾降。因此在劃分子帶時(shí)，有兩種情況：有兩種情況： a子帶間有交疊，如圖所示；子帶間有交疊，如圖所示；112MMskkKkkkIf RW R b：子帶之間有一定的間

60、隙，如圖：子帶之間有一定的間隙，如圖 (b)所示。所示。 在在(a)的情況下按奈氏頻率取樣將會(huì)產(chǎn)生混疊失真；的情況下按奈氏頻率取樣將會(huì)產(chǎn)生混疊失真； 在在(b)的情況下，由于原有信號(hào)的部分頻帶經(jīng)濾波而損的情況下，由于原有信號(hào)的部分頻帶經(jīng)濾波而損 失掉了重建的信號(hào)會(huì)有失真，例如以話(huà)音為例，重建失掉了重建的信號(hào)會(huì)有失真，例如以話(huà)音為例，重建的語(yǔ)音會(huì)產(chǎn)生混響的主觀(guān)感覺(jué)。的語(yǔ)音會(huì)產(chǎn)生混響的主觀(guān)感覺(jué)。 解決方法：解決方法： 正交鏡像濾波器正交鏡像濾波器比較好地解決了混疊失真的問(wèn)比較好地解決了混疊失真的問(wèn)題，從而降低了對(duì)濾波器滾降特性的要求，簡(jiǎn)題，從而降低了對(duì)濾波器滾降特性的要求，簡(jiǎn)化了濾波器的復(fù)雜性，成