1、第第3章章 數據壓縮的基本技術數據壓縮的基本技術 數據壓縮處理一般由兩個過程組成：數據壓縮處理一般由兩個過程組成： 編碼過程：對原始數據進行編碼壓縮，以便存儲和傳輸；編碼過程：對原始數據進行編碼壓縮，以便存儲和傳輸； 解碼過程：對壓縮的數據進行解壓，恢復成可用的數據。解碼過程：對壓縮的數據進行解壓，恢復成可用的數據。根據解壓后數據的保真度，數據壓縮技術可分為根據解壓后數據的保真度，數據壓縮技術可分為無損壓縮編碼無損壓縮編碼：解碼后的數據與原始數據完全相同，無任：解碼后的數據與原始數據完全相同，無任何偏差。這種編碼通常基于信息熵原理，常用的編碼有何偏差。這種編碼通常基于信息熵原理，常用的編碼有哈

2、夫曼編碼、算術編碼、行程編碼等。壓縮比比較低，哈夫曼編碼、算術編碼、行程編碼等。壓縮比比較低，一般在一般在2:1-5:1。主要用于要求數據無損壓縮存儲和傳輸。主要用于要求數據無損壓縮存儲和傳輸的場合，如傳真機的場合，如傳真機有損壓縮編碼有損壓縮編碼：解碼后的數據與原始數據相比有一定的偏：解碼后的數據與原始數據相比有一定的偏差，但仍可保持一定的視聽質量和效果。它主要是在保差，但仍可保持一定的視聽質量和效果。它主要是在保持一定保真度下對數據進行壓縮，其壓縮比可達持一定保真度下對數據進行壓縮，其壓縮比可達100:1。壓縮比越高，其解壓縮后的視、音頻質量就越壓縮比越高，其解壓縮后的視、音頻質量就越低。

3、低。 分類：分類： a 第一代圖像壓縮編碼方法第一代圖像壓縮編碼方法基于香農理論，基于香農理論，80年代初趨于成熟，主要降低數據之間的相關性，年代初趨于成熟，主要降低數據之間的相關性，去除冗余。去除冗余。 b 第二代圖像壓縮編碼方法第二代圖像壓縮編碼方法基于人類視覺特性的壓縮方法，其核心思想是力圖發現人眼是根據基于人類視覺特性的壓縮方法，其核心思想是力圖發現人眼是根據哪些關鍵特征來識別圖像、或圖像序列的，然后根據這些特征來哪些關鍵特征來識別圖像、或圖像序列的，然后根據這些特征來構造圖像模型。構造圖像模型。 例如，根據人眼對物體的輪廓比對物體內部細節更為敏例如，根據人眼對物體的輪廓比對物體內部細

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

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

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

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

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

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

10、誤差意義下，預測若上式最小時，表示在最小均方誤差意義下，預測最準確，此時色預測器稱為在最小均方誤差意義下最準確，此時色預測器稱為在最小均方誤差意義下的最佳預測器。的最佳預測器。 最佳預測器的系數最佳預測器的系數 ai可以通過求極小值的方法求得。可以通過求極小值的方法求得。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 用輸入序列的自相關函數 表示： 如果對所需要壓縮的某類圖像的自相關函數已經作如果對所需要壓縮的某類圖像的自相關函數已經作過測量的話，則可通過求解上式所表示的方程組，獲過測量的話，則可通過求解上式所表示的方程組，獲得最佳預測器的系數值。得最佳預測器的系數值。 另一個事實另一個事實2m in12m in111()()()() ()()()()0()()()() ()()()() ()( 0 )()NkkiNkkNkkNkkenenxnaxnkenxnienenaenenxnaxnkenxnxnaxnkxnRaRk 而 由 （ 3 . 4 2 ）所 以 預測

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

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

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

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

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

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

18、一化的二維互相關函數（NCCF） 當當NCCF為為最大值時最大值時2個子塊匹配，對應的個子塊匹配，對應的 i，j 值即構值即構成位移矢量成位移矢量D。11121 221 211111( , )(,)( , )( , ) (,)MNkkmnMNMNkkmnmnb m n bm i njNCCF i jbm nbm i nj 準則準則b 求求2幀子塊亮度的均方差值幀子塊亮度的均方差值MSE： 當當MSE最小時表示最小時表示2個子塊匹配個子塊匹配。21111( , )( , )(,)(,)MNkkmnmmMSE i jb m nbmi njMNdi jd c. MAD準則準則 求幀間子塊亮度差的絕對

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

20、搜索方法：為了節省計算量，在k-1幀中的匹配搜幀中的匹配搜索只在一定范圍內進行。假設在索只在一定范圍內進行。假設在時間間隔內時間間隔內最大可能最大可能的水平和垂直位移量為的水平和垂直位移量為dm個像素，則搜索范圍個像素，則搜索范圍SR為為 SR（M+2 dm ）*（N+ 2dm ）1)全搜索全搜索:尋找最佳的匹配塊，需要將尋找最佳的匹配塊，需要將k-1幀中對應的子塊在整個幀中對應的子塊在整個搜索區內沿水平和垂直方向逐個像素移動，每移動一次計算一搜索區內沿水平和垂直方向逐個像素移動，每移動一次計算一次判決函數。總的移動次數次判決函數。總的移動次數Q為為 Q（2dm+1）2 此種搜索方法運算量非常

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

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

23、，這些算法的搜索策略概括如下：策略概括如下：1）運動矢量預測：）運動矢量預測：根據圖像內容的連續性，相鄰塊的運動矢量一般是相近的。根據圖像內容的連續性，相鄰塊的運動矢量一般是相近的。2）搜索提前中止：預先設定匹配誤差閾值）搜索提前中止：預先設定匹配誤差閾值3）緊湊的搜索圖形）緊湊的搜索圖形 3.5.3具有運動補償的幀間預測具有運動補償的幀間預測 1.前向預測前向預測 概念：不直接傳送當前幀的像素值，而傳送當前幀（即概念：不直接傳送當前幀的像素值，而傳送當前幀（即第第k幀）中像素幀）中像素x和前和前1幀幀(即即k-1幀幀)的同位像素的同位像素x之間的之間的差值，稱為幀間預測。差值，稱為幀間預測。

24、 對隔行掃描的電視信號，也可以用前一場來預測當前場對隔行掃描的電視信號，也可以用前一場來預測當前場的像素的像素(場間預測場間預測)。當圖像中存在著運動物體時簡單的預測不能收到好的效果。當圖像中存在著運動物體時簡單的預測不能收到好的效果。考慮了物體移動的幀間預測方法稱為具有運動補償的幀間預測。考慮了物體移動的幀間預測方法稱為具有運動補償的幀間預測。 基本步驟：基本步驟： (1)將圖像分割成靜止的背景和若干運動的物體，各個將圖像分割成靜止的背景和若干運動的物體，各個物體可能有不同的位移。但構成同一物體的所有像素的物體可能有不同的位移。但構成同一物體的所有像素的位移相同。通過運動估值得到每個物體的位

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

26、塊看成是一個物體，按塊匹配的方法估計每個子塊的位移矢量，將經過位移補償的幀間方法估計每個子塊的位移矢量，將經過位移補償的幀間預測誤差預測誤差DFD和位移矢量和位移矢量D傳送給收端，收端就可以按傳送給收端，收端就可以按下式從已經收到的前下式從已經收到的前1幀信息中恢復出該子塊：幀信息中恢復出該子塊： bk(z)=bk-1(z-D)+DFD(z,D)下圖表示了下圖表示了K幀各塊及它們在幀各塊及它們在k-1幀中對應的匹配塊之間的關系幀中對應的匹配塊之間的關系從該塊的預測誤差和它的位移矢量所指向的從該塊的預測誤差和它的位移矢量所指向的k-1幀中的匹配塊，幀中的匹配塊，可以恢復出可以恢復出k幀中的對應子

27、塊。幀中的對應子塊。 注意：注意： 當子塊中的像素實際上屬于位移量不同的物體時，當子塊中的像素實際上屬于位移量不同的物體時，這種對整個子塊用同一位移量的預測就不夠準這種對整個子塊用同一位移量的預測就不夠準確會使預測誤差增加，從而影響到數據壓縮比確會使預測誤差增加，從而影響到數據壓縮比的提高。的提高。 2.后向預測和雙向預測后向預測和雙向預測 概念：概念： 前向預測：前向預測： 后向預測后向預測:從后續的從后續的k+1幀圖像預測前面的幀圖像預測前面的k幀圖像幀圖像 雙向預測雙向預測:采用前、后兩幀來預測中間幀采用前、后兩幀來預測中間幀 討論：討論： 預測誤差越小，傳輸的數據量就越低。預測誤差越小

28、，傳輸的數據量就越低。 雙向預測所付出的代價是，對每一個子塊需要傳送雙向預測所付出的代價是，對每一個子塊需要傳送2個位個位移矢量給收端，而且移矢量給收端，而且k幀的恢復必須等到接收到幀的恢復必須等到接收到k+1幀之幀之后才能進行。后才能進行。 即：編碼、解碼運算的幀順序是即：編碼、解碼運算的幀順序是k-1、k+1、k，而圖像顯，而圖像顯示的順序是示的順序是k-1、k、k+l。 要保持處理和顯示的連續性，編碼端和解碼端就分別需要保持處理和顯示的連續性，編碼端和解碼端就分別需要多引入要多引入1幀的延時。幀的延時。3.6 3.6 正交變換正交變換編碼編碼 例例1：單一頻率的正弦波：單一頻率的正弦波

29、在時域中：采樣、量化、編碼在時域中：采樣、量化、編碼 在頻域中：頻率、波幅、初相角在頻域中：頻率、波幅、初相角 時域上采樣值之間存在非常強的相關性，數據冗余度時域上采樣值之間存在非常強的相關性，數據冗余度大，而在變換域上三個參數相互獨立，沒有相關性，大，而在變換域上三個參數相互獨立，沒有相關性，描述信號的數據量大大減少。描述信號的數據量大大減少。將空域圖像信號映射變換到另一個正交矢量空間及變換域，將圖將空域圖像信號映射變換到另一個正交矢量空間及變換域，將圖像像素值轉變成一組非相關的系數，然后對這些系數進行量化和像像素值轉變成一組非相關的系數，然后對這些系數進行量化和編碼。編碼。目的：去除相關，

30、壓縮數據。為信號找到一種最有效的表示方式。目的：去除相關，壓縮數據。為信號找到一種最有效的表示方式。 例例2：由相鄰兩個像素組成的：由相鄰兩個像素組成的12子圖像中，設每個子圖像中，設每個像素取像素取8個灰度級（個灰度級（3bit量化），下圖中量化），下圖中x1軸表示第一軸表示第一個像素可能取的個像素可能取的8個灰度值，個灰度值，x2軸表示第二個像素可軸表示第二個像素可能取的能取的8個灰度值，由個灰度值，由x1,x2組成的二維坐標空間中不組成的二維坐標空間中不同坐標點對應于不同的同坐標點對應于不同的12子圖像。子圖像。 變換后的坐標系中，圖像子塊的兩個像素之間的相關變換后的坐標系中，圖像子塊的

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

32、經上式變換得到的，將經上式變換得到的Y用一個由用一個由M(MN)個分量構成的子集來近似。當刪去個分量構成的子集來近似。當刪去Y中剩下的中剩下的(N-M)個分量，僅用含個分量，僅用含M個分量的子集來恢復個分量的子集來恢復X時，不時，不會引起明顯的誤差。會引起明顯的誤差。或者說：用或者說：用Y的只有的只有M個分量的子集來代表有個分量的子集來代表有N個分量的個分量的信號信號X，從而達到數據壓縮的目的。，從而達到數據壓縮的目的。 關鍵是：尋找變換矩陣關鍵是：尋找變換矩陣T，即：找到最佳正交變換。，即：找到最佳正交變換。最佳的判斷標準：最佳的判斷標準：使得在恢復使得在恢復X時所產生的均方誤差最小。時所產

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

34、）當當T為實數矩陣，且為實數矩陣，且T-1TH時，稱時，稱T為正交矩陣，對應的為正交矩陣，對應的變換為正交變換。變換為正交變換。 由由Y=TX和和(3-56)式，得到式，得到 XTHYy1 1+y2 2+.+yN N上式表明將上式表明將X轉換到由基向量轉換到由基向量i(i1，2，N)生成的生成的N維空間維空間(通常稱為變換域通常稱為變換域)中。中。yi代表代表X在在i上投影的大小，上投影的大小，稱為變換系數。稱為變換系數。因此，因此，由變換系數所構成的向量由變換系數所構成的向量Y是信號是信號X在變換域中的在變換域中的表示。表示。 假設信號假設信號X是一個均值為零的隨機向量，即是一個均值為零的隨

35、機向量，即=0。 若只保留若只保留M(MN)個變換系數個變換系數,將其余將其余(N-M)個系數個系數置為零，則所得到的置為零，則所得到的X的近似值的近似值XM與原信號的差值與原信號的差值X為為 XX-XM 其均方誤差其均方誤差MSE為為 MSE= =1Niii My*1121.(3 71)NNHik iki Mk MNii Myyy 359）由由Y=TX可知：可知： 標量的轉置為其自身標量的轉置為其自身，（3-59）可改寫為：）可改寫為：當當=0時，時，即為即為X的協方差矩陣的協方差矩陣 。可以證明得：可以證明得：iH i1的條件下，使的條件下，使MSE為最小的條件為最小的條件是是.HiiyX

36、11NNHHHiiiii Mi MMSEy yXX XXiii 上式看出上式看出i和和i分別是矩陣分別是矩陣 的本征向量和本征值。的本征向量和本征值。也就是說，以信號的協方差矩陣也就是說，以信號的協方差矩陣 的本征向量的本征向量i(il，2，N)組成的變換矩陣是均方誤差準則下的最組成的變換矩陣是均方誤差準則下的最佳變換矩陣，用此矩陣構成的最佳變換佳變換矩陣，用此矩陣構成的最佳變換YTX稱為稱為卡南洛伊夫變換卡南洛伊夫變換KLT。 XX 經經KL變換后，變換后，Y的協方差矩陣的協方差矩陣 為為 （根據根據YTX）Y12.0.0HHYXNY YTTKL變換解除了隨機向量變換解除了隨機向量X的分量之

37、間的相關性，的分量之間的相關性，在變換域中在變換域中Y的各分量之間是互不相關的的各分量之間是互不相關的應用的先修知識：應用的先修知識：A為為n階實對稱矩陣，則有正交矩陣階實對稱矩陣，則有正交矩陣P,使使P-1AP=min1Nii MMSE上式說明最小均方誤差等于上式說明最小均方誤差等于Y向量中被丟棄的分量的方向量中被丟棄的分量的方差之和。差之和。由此可知，應該選擇具有較大方差的由此可知，應該選擇具有較大方差的M個個Y分量所構成分量所構成的子集來恢復的子集來恢復X，以使得恢復后所產生的誤差最小。，以使得恢復后所產生的誤差最小。缺點：缺點：KL變換的基向量與信號的統計特性有關，變換變換的基向量與信

38、號的統計特性有關，變換矩陣不是恒定的，需要臨時計算，同時也缺乏相應的快矩陣不是恒定的，需要臨時計算，同時也缺乏相應的快速算法速算法 3.6.2離散余弦變換離散余弦變換 選擇不同的正交基向量，可以得到不同的正交變換。選擇不同的正交基向量，可以得到不同的正交變換。 從數學上可以證明，各種正交變換都能在不同程度上從數學上可以證明，各種正交變換都能在不同程度上減小隨機向量的相關性。減小隨機向量的相關性。 信號經過大多數正交變換后，能量會相對集中在少數信號經過大多數正交變換后，能量會相對集中在少數變換系數上，刪去對信號貢獻較小變換系數上，刪去對信號貢獻較小(方差小方差小)的系數，的系數，只利用保留下來的

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

40、。余弦變換的數時，傅立葉級數中只包含余弦項。余弦變換的名字由來，或稱之為離散余弦變換。名字由來，或稱之為離散余弦變換。 離散余弦變換在數字圖像數據壓縮編碼技術中，離散余弦變換在數字圖像數據壓縮編碼技術中，可與最佳變換可與最佳變換K-L變換媲美。因為變換媲美。因為DCT與與K-L變變換壓縮性能和誤差相接近，而換壓縮性能和誤差相接近，而DCT計算復雜度適計算復雜度適中又具有可分離特性還有快速算法等特點，中又具有可分離特性還有快速算法等特點，所以近年來在圖像數據壓縮中，采用離散余弦變所以近年來在圖像數據壓縮中，采用離散余弦變換編碼的方案很多，特別是換編碼的方案很多，特別是20世紀世紀90年代迅速崛年

41、代迅速崛起的計算機多媒體技術當中起的計算機多媒體技術當中JPEG、MPEG、R.261等壓縮標準。都用到離散余弦變換編碼進等壓縮標準。都用到離散余弦變換編碼進行數據壓縮。行數據壓縮。112011202(21)( ) ( )( )( )cos(0,1,2,1)22(21)( ) ( )( ) ( )cos(0,1,2,1)2( )( )010NkNnknS nCns knNNNkns kCnS nkNNNs kS nnn 其 中為 信 號 樣 值 ，為 變 換 系 數 且1C(n)=2一維的一維的DCT正變換和反變換正變換和反變換DCT變換的核函數變換的核函數一維一維8個像素時對應的基函數數據個

42、像素時對應的基函數數據 由一維由一維DCT可以直接擴展到二維，即可以直接擴展到二維，即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 其中為信號樣值， ( )01010S nuuvv為變換系數且1C(u)=21C(v)=2u由此可以看出：由此可以看出：DCT將能量將能量集中于頻率平

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

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

45、2點為偶對稱的序列,即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則整個點序列的可表示為F(n)=2N-k-1設2N-k-1,并注意到因為上式變為F(n)=用 代替 并在等式兩邊同乘得1F(n)=2N-1N-1n/2Kk=0k=0N-1k=0W/2(2k+1)ns(k)cos(3 87)2N (3-75) 為了進一步簡化上述關系，注意到，由于上式右端是為了進一

46、步簡化上述關系，注意到，由于上式右端是實數，因此左端也應為實數。用實數，因此左端也應為實數。用An和和Bn分別表示分別表示F(n)的實數和虛數部分，則有的實數和虛數部分，則有 令上式的虛部為零則令上式的虛部為零則 將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、結論；一個函數的結論；一個函數的DCT系數可以由該函數對應的偶函數的系數可以由該函數對應的偶函數的DFT系數的實部得到。系數的實部得到。 (3-78) 討論討論: (1)先前知識，二維信號的傅氏變換的系數代表它所對先前知識，二維信號的傅氏變換的系數代表它所對應的空間頻率分量的復振幅。應的空間頻率分量的復振幅。 (3-79)式表明，雖然式表明，雖然DCT系數并不與空間頻率分量的復系數并不與空間頻率分量的復振幅嚴格相等，但有一定的對應關系。振幅嚴格相等，但有一定的對應關系。 特別是特別是n0時的時的DCT系數與系數與DFT的零頻分量一樣，代的零頻分量一樣，代表空間域內信號的均值；表空間域內信號的均

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

49、的數值的技術 b 內插（上取樣）內插（上取樣） 由低取樣率的樣值去估計在原來較高頻率的取樣點上的由低取樣率的樣值去估計在原來較高頻率的取樣點上的樣值，這種技術稱為內插。樣值，這種技術稱為內插。應用：應用：1）通過取樣頻率的轉換，可以使傳送數據量增多）通過取樣頻率的轉換，可以使傳送數據量增多或減少，實現傳送圖像高低分辨率的轉換。或減少，實現傳送圖像高低分辨率的轉換。2）當需要將數字信號與一些特殊系統的時鐘同步時，可）當需要將數字信號與一些特殊系統的時鐘同步時，可能需要進行采樣率的轉換；能需要進行采樣率的轉換；3）一個數字電話系統，通過該系統傳輸的既有語音信號，）一個數字電話系統，通過該系統傳輸的

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

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

52、利用周期序列的離散傅里葉級數利用周期序列的離散傅里葉級數DFS反變換：反變換：kMnknMjMkknMjkMnnpenpkPekPMnp為一脈沖串數為離散傅里葉級數的系其中)()(1)()()(1)(102102 102102102102102)(1)(1)(1)(11)()()()()()()()(MkMkwjMknMnknMjMknnMkwjMknMnknMjMnnMkknMjnMnmmmmeXMzenxMenxMzenxMzeMnxznxzMmxzmyZYMmxMmxmy3.4.2 3.4.2 上取樣上取樣 線性內插線性內插 是一種廣泛的內插方法，它利用兩相鄰是一種廣泛的內插方法，它利用

53、兩相鄰樣值得加權和內插出二者之間任意位置樣值得加權和內插出二者之間任意位置上的數值，每個樣值與該值到內插位置上的數值，每個樣值與該值到內插位置的距離成反比。的距離成反比。 3.7 3.7 子帶編碼子帶編碼 3.7.13.7.1子帶編碼工作原理子帶編碼工作原理 在子帶編碼中，如圖在子帶編碼中，如圖3-243-24所示所示. . 首先用一組帶通濾波器將輸入信號分成若干個在不同頻首先用一組帶通濾波器將輸入信號分成若干個在不同頻段上的子帶信號段上的子帶信號; ; 然后將這些子帶信號經過頻率搬移轉變成基帶信號，再然后將這些子帶信號經過頻率搬移轉變成基帶信號，再對它們在奈氏頻率上分別取樣。取樣后的信號經過

54、量化、對它們在奈氏頻率上分別取樣。取樣后的信號經過量化、編碼，并合成成一個總的碼流傳送給接收端。編碼，并合成成一個總的碼流傳送給接收端。 在接收端，首先把碼流分成與原來的各子帶信號相對應在接收端，首先把碼流分成與原來的各子帶信號相對應的子帶碼流，然后解碼、將頻譜搬移至原來的位置，最的子帶碼流，然后解碼、將頻譜搬移至原來的位置，最后經帶通濾波、相加得到重建的信號。后經帶通濾波、相加得到重建的信號。 在子帶編碼中，若各子帶的帶寬在子帶編碼中，若各子帶的帶寬Wk是相同的，是相同的，則稱為則稱為等帶寬子帶編碼等帶寬子帶編碼；若；若Wk是互不相同的，是互不相同的，則稱為則稱為變帶寬子帶編碼變帶寬子帶編碼

55、。 子帶編碼的壓縮數據的原因和優點：子帶編碼的壓縮數據的原因和優點： (1)可以利用人耳可以利用人耳(或人眼或人眼)對不同頻率信號的對不同頻率信號的感知靈敏度不同的特性，在人的聽覺感知靈敏度不同的特性，在人的聽覺(或視覺或視覺)不敏感的頻段采用較租糙的量化，從而達到數不敏感的頻段采用較租糙的量化，從而達到數據壓縮的目的；據壓縮的目的； (2)各子帶的量化噪聲都束縛在本子帶內，這各子帶的量化噪聲都束縛在本子帶內，這就可以避免能量較小的頻帶內的信號被其它頻就可以避免能量較小的頻帶內的信號被其它頻段中的量化噪聲所掩蓋。段中的量化噪聲所掩蓋。 子帶編碼的關鍵部件討論：子帶編碼的關鍵部件討論： 帶通濾波

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

57、為整數子帶濾波器組。滿足上式條件的子帶濾波器組稱為整數子帶濾波器組。 以以M4的變帶寬子帶為例：的變帶寬子帶為例： 圖圖3-25給出了第給出了第3個子帶的取樣過程。圖中個子帶的取樣過程。圖中(a)是輸入信號是輸入信號的頻譜；的頻譜；(b)是第是第3個子帶信號的頻譜，其下截止頻率個子帶信號的頻譜，其下截止頻率f132W3 ；(c)是以是以fs32W3 的頻率對的頻率對(b)取樣后，所得到取樣后，所得到的信號的頻譜。的信號的頻譜。 采用整數子帶濾波器組的優點：采用整數子帶濾波器組的優點： 采用整數于帶濾波器組省去了進行頻譜搬移所需要的調采用整數于帶濾波器組省去了進行頻譜搬移所需要的調制器和解調器，

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

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

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