【文章內容簡介】 。如果輸入序列為S=a2a1a3a2a4…… 。根據以上編碼過程，得如下結果： 43 從以上的編碼過程可以看出以下幾個問題： 1）算術編碼器對整個消息只產生一個碼字，這個碼字是在間隔 [0, 1)中的一個實數(shù)，因此譯碼器在接受到表示這個實數(shù)的所有位之前不能進行譯碼。 ２）運算中出現(xiàn)溢出是一個明顯的問題，但多數(shù)機器都有16位、 32位或者 64位的精度，因此該問題可使用比例縮放方法解決。 3）算術編碼也是一種對錯誤很敏感的編碼方法，如果有一位發(fā)生錯誤就會導致整個消息譯錯。 44 行程編碼 行程編碼（ RLE）通過統(tǒng)計信源符號中的重復個數(shù)，并以重復個數(shù) 重復符號 格式來編碼。適用于壓縮包含大量重復信息的信源。其基本思想是：按行存儲一個顏色值和相同色值的像素個數(shù)。如下圖。 (a) 圖像示例（ 16 8像素） 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 (b) 示例圖像的像素值（ 16 8像素） 連續(xù)相同色塊圖像與像素值示例 16 0 2 0 11 1 3 0 2 0 1 1 13 0 2 0 1 1 13 0 2 0 1 1 13 0 2 0 11 1 3 0 16 0 16 0 (c) RLE編碼 45 說明： RLE壓縮編碼尤其適用于計算機生成的圖像，對減少圖像文件的存儲空間非常有效。然而，RLE對顏色豐富的自然圖像就顯得力不從心，如果使用 RLE編碼方法，不僅不能壓縮圖像數(shù)據，反而可能使原來的圖像數(shù)據變得更大。 46 詞典編碼 詞典編碼主要是利用編碼數(shù)據本身存在字符串重復特性來實現(xiàn)數(shù)據壓縮的。算法的核心就是如何動態(tài)地形成詞典，以及如何選擇輸出格式以減小冗余。詞典編碼又可分為兩類： 第一類詞典編碼的思想 是：查找正在壓縮的字符序列是否在以前輸入的數(shù)據中出現(xiàn)過，然后用已經出現(xiàn)過的字符串替代重復的部分，并將指向重復字符串的指針作為輸出編碼。 指針 P指向了重復字符串 “ abc”，所以，當再次出現(xiàn)相同字符串時，則輸出指針 P。 47 第二類詞典編碼的思想 是：從輸入的數(shù)據中創(chuàng)建一個由短語組成的 “ 編碼詞典 ” ，編碼數(shù)據過程中當遇到已經在詞典中出現(xiàn)的 “ 短語 ” 時，編碼器就輸出這個詞典中短語的 “ 索引號 ” ，而不是短語本身，如下圖。 48 有損壓縮編碼介紹 有損數(shù)據壓縮編碼方法通常用于對靜態(tài)圖像、音頻以及視頻等多媒體信息的編碼壓縮，這些多媒體信息大多數(shù)是通過對模擬信息的數(shù)字化（采樣與量化）而得到的。 預測編碼 1） 預測編碼的基本概念 預測編碼是數(shù)據壓縮的重要技術原理之一，它是根據離散信號之間的空間或時間相關性，利用前面的一個或多個信號對下一信號進行預測，然后對實際值和預測值的差進行編碼。常用的預測編碼方法有 DPCM（差分脈沖編碼調制）和ADPCM（自適應差分脈沖編碼調制）等。 49 2） DPCM—— 差分脈沖編碼 DPCM ： Differential Pulse Code Modulation，差分脈沖編碼調制， 用采樣量化后的樣本值與預測值之間的差值來編碼 。原理如下圖所示。 s(k)是 PCM樣本值， se(k1)是 s(k)的預測值， d(k)是差分信號，即d(k)= s(k) se(k1)。 I(k)是差分信號 d(k)的量化值， st(k)是重構信號，是由逆量化器產生的量化差分信號與對過去樣本信號的估算值 se(k1)求和得到，以作為預測器確定下一個信號估算值的輸入信號。原理 P205 50 3） ADPCM——自適應差分脈沖編碼 ADPCM是自適應量化和自適應預測方法的總稱，是對 DPCM方法的進一步改進，通過調整量化步長，對不同頻段設置不同的量化字長，使數(shù)據得到進一步的壓縮。 自適應量化就是使量化間隔大小的變化自動地去適應輸入信號大小的變化。 根據信號分布不均勻的特點，使系統(tǒng)具有隨輸入信號的變化而改變量化區(qū)間的大小，以保持輸入量化器的信號基本均勻的能力。 51 下圖給出了反饋自適應的基本原理 。 52 變換編碼 先對信號進行域變換，以尋求更大的信號獨立性，減少相關性。然后再對變換后的信號進行采樣和量化編碼。數(shù)據編碼過程分為三步，即 變換、變換域采樣和量化編碼 。如下圖所示。 常用的變換有 KLT、 DCT、 WHT以及 WLT 。 53 1） KLT KLT（ KarhunenLoeve Transform）通常稱為 KL變換，亦稱主要成分變換，是一個離散變換。用一組不相關的系數(shù)來表示連續(xù)信號，實現(xiàn)正交變換。是失真最小的一種變換，故稱作最佳變換。 2） DCT DCT（ Discrete Cosine Transform）是離散余弦變換的簡稱。對于圖像編碼來說， DCT先將整體圖像分成若干個 N x N的像素塊，然后每個 N x N像素塊逐一進行 DCT變換。 54 DCT變換公式如下： ? ? ? ? ? ? ? ?? ??????????? ???????? ???1010 212cos212cos 2 NxNyv πNyu πNxx,yfNvEuEvuC ，其中： N為所劃分圖像方陣的行列數(shù)，一般 N=8； x、 y：原圖像方陣內某個數(shù)據的坐標位置，取值為 0～ N1； f(x,y)代表原圖像數(shù)據方陣內的某個數(shù)值； u、 v： DCT后矩陣內某個數(shù)值的坐標位置，取值為 0～ N1； C(u,v) 代表 DCT變換后矩陣內的某個數(shù)值； 當 u=0且 v=0時， E(u) = E(v) = 1/； 當 u0或 V0時， E(u) = E(v) = l 。 DCT逆變換公式： ? ? ? ? ? ? ? ?? ??????????? ???????? ???1010 212cos212cos 2 NxNyv πNyu πNxvuCvEuENx,yf ，55 3） WHT WHT（ WalshHadamard Transform）又稱哈達瑪特變換，這是一種有效地去除噪波的方法。 基本思想為： 對于圖像壓縮，首先將輸入值按 4 x 2分成小塊，分別進行實時快速哈達瑪特變換。圖像經變換后，轉換成相應成分的系數(shù)，這些系數(shù)分別代表直流分量、水平方向細節(jié)和色度分量、垂直方向細節(jié)、斜方向細節(jié)及色度分量等，而噪波變換后均勻散在各系數(shù)中。這樣就能更有效地區(qū)分出信號和噪波，從而達到更有效地進行自適應降噪的目的。 56 4） WLT WLT（ WaveLet Transform）又稱小波變換，是近年來新興的一種變換方法，解決了較好地解決突變信號與非平穩(wěn)信號的問題。是空間（時間）和頻率的局部變換。 小波變換的 基本思想 是將信號展開成一族基函數(shù)的加權和，即用一族函數(shù)來表示或逼近信號 (或函數(shù) )，這一族函數(shù)是通過基本函數(shù)的平移和伸縮構成的。 57 混合編碼 混合編碼不是一類原理性編碼方案，是兩種或兩種以上相關編碼方法優(yōu)點與特長的混合應用。 比如在 MPEG和 JPEG標準中，都混合應用了不同的編碼方法，從而實現(xiàn)較為理想的編碼壓縮效果。 58 其它編碼 主要包括分形編碼、矢量量化編碼、子帶編碼等獨具特色編碼方法。 1）分形編碼 分形的概念 ：分形指某種形狀（或結構）的一個局部或片斷，它可以有許多種大小、尺寸的相似形。 分形編碼 是一種以分形幾何學為理論基礎的編碼方法，它利用分形幾何中自相似的原理來實現(xiàn)數(shù)據壓縮的。首先對把一幅數(shù)字圖像，通過一些圖像處理技術，然后在分形集中尋找各子圖像之間的相似性，其壓縮比超出經典編碼方法近 3個數(shù)量級。 59 2）矢量量化編碼 矢量量化編碼利用相鄰圖像數(shù)據間的高度相關性，將輸入圖像數(shù)據序列分組，每一組由 n個數(shù)據構成一個 N維矢量，一起進行編碼，即一次量化多個點。 3）子帶編碼 子帶編碼