【正文】 ② 把兩組分別按 0， 1賦值。 ? 然后分組、賦值，不斷反復(fù)，直到每組只有一種輸入為止。將每個所賦的值依次排列起來就是費諾 —香農(nóng)編碼。 nxx ,...,1nxx ,...,1 kxx ,...,1 nk xx ,...,1?11( ) ( )kniji j kP x P x? ? ????? 以前面哈夫曼編碼的例子進(jìn)行香農(nóng)－費諾編碼 ： 輸入 概率 x1 o 0 x2 1 0 10 x3 1 0 0 1100 x7 1 1101 x5 1 0 1110 x6 1 1111 算術(shù)編碼 ? 理論上 ， 用 Huffman方法對源數(shù)據(jù)流進(jìn)行編碼可達(dá)到最佳編碼效果 。 但 由于計算機(jī)中存儲 、 處理的最小單位是 “ 位 ” ， 因此 ， 在一些情況下 ， 實際壓縮比與理論壓縮比的極限相去甚遠(yuǎn) 。 ? 算術(shù)編碼沒有延用數(shù)據(jù)編碼技術(shù)中用一個特定的代碼代替一個輸入符號的一般做法 ， 它 把要壓縮處理的整段數(shù)據(jù)映射到一段實數(shù)半開區(qū)間 [0， 1]內(nèi)的某一區(qū)段 ， 構(gòu)造出小于 1且大于或等于 0的數(shù)值 。 這個數(shù)值是輸人數(shù)據(jù)流的唯 —可譯代碼 。 ? 對一個 5符號信源 A＝ {a1,a2,a3,a2,a7}，各字符出現(xiàn)的概率和設(shè)定的取值范圍如下： 字符 概率 范圍 a3 [， ） a1 [， ） a2 [， ) a7 [， ) “范圍 ” 給出了字符的賦值區(qū)間。這個區(qū)間是根據(jù)字符發(fā)生的概率劃分的。具體把 a a aa7分配在哪個區(qū)間范圍，對編碼本身沒有影響，只要保證編碼器和解碼器對字符的概率區(qū)間有相同的定義即可。為討論方便起見，假定有 LCFN lse *?? LCFN ree *??? 式中 Ns為新于區(qū)間的起始位置； Fl為前于區(qū)間的起始位置，當(dāng)前符號的區(qū)間左端； Ne為新于區(qū)間的結(jié)束位置； Fe為前子區(qū)間的結(jié)束位置；當(dāng)前符號的區(qū)間右端； L為前子區(qū)間的長度。 ? 按上述區(qū)間的定義，若數(shù)據(jù)流的第一個字符為 a1，由字符概率取值區(qū)間的定義可知，代碼的實際取值范圍在 [， ]之間，即輸入數(shù)據(jù)流的第一個字符決定了代碼最高有效位取值的范圍。 ? 繼續(xù)對源數(shù)據(jù)流中的后續(xù)字符進(jìn)行編碼。每讀入一個新的符號，輸出數(shù)值范圍就進(jìn)一步縮小。讀入第二個符號 a2取值范圍在區(qū)間的 [， ]內(nèi)。由于第一個字符 a1已將取值區(qū)間限制在 [， ]的范圍中，因此 a2的實際取值是在前符號范圍 [， ]的 [，]處，從而字符 a2的編碼取值范圍在 [， ]，而不是在 [0， 1]整個概率分布區(qū)間上。 ? 每輸入一個符號，都將按事先對概率范圍的定義，在逐步縮小的當(dāng)前取值區(qū)間上確定新的范圍上、下限。繼續(xù)讀入第三個符號 a3受到前面巳編碼的兩個字符的限制，它的編碼取值應(yīng)在 [， ]中的[， ]內(nèi)，即 [， ]。重復(fù)上述編碼過程，直到輸入數(shù)據(jù)流結(jié)束。最終結(jié)果如下： 輸入字符 區(qū)間長度 范圍 a1 [， ） a2 [， ） a3 [， ) a2 [， ) a1 [， ] ? 隨著字符的輸入，代碼的取值范圍越來越小?？梢杂靡粋€浮點數(shù)表示一個字符串，達(dá)到減少所需存儲空間的目的。 ? 游程編碼 (RLC)是一種利用空間冗余度壓縮圖像的方法 ， 屬于統(tǒng)計編碼類 。 ? 設(shè)圖像中的某一行或某一塊像素經(jīng)采樣或經(jīng)某種變換后的系數(shù)為 ： 某一行或某一塊內(nèi)像素值可分為 k段，長度為 的連續(xù)串，每個串具有相同的值，那么，該圖像的某一行或某一塊可由下面偶對 來表示： 其中 為每個串內(nèi)的代表值 ， 為串的長度 。 串長就是游程長度 (Run—length)， 簡寫為 RL， 即由灰度值構(gòu)成的數(shù)據(jù)流中各灰度值重復(fù)出現(xiàn)而形成的長度 。如果給出了灰度值 、 對應(yīng)長度及位置 ， 就能很容易地恢復(fù)出原來的數(shù)據(jù)流 。 12( , , )Mx x x1 2 1 1 2 2( , , ) ( , ) , ( , ) , , ( , )M k kx x x g l g l g l?igil( , ) , 1iig l i k??ilRL的基本結(jié)構(gòu) 游程編碼分為定長游程編碼和變長游程編碼兩類 。 定長游程編碼是指編碼的游程所使用位數(shù)是固定的 ， 即 RL位數(shù)是固定的 。 如果灰度連續(xù)相同的個數(shù)超過了固定位數(shù)所能表示的最大值 ， 則進(jìn)入下一輪游程編碼 。 變長游程編碼是指對不同范圍的游程使用不同位數(shù)的編碼 ， 即表示 RL位數(shù)是不固定的 。 X SC RL 串字符 串位置 串長 游程編碼一般不直接應(yīng)用于多灰度圖像 ， 但比較適合于二值圖像的編碼 。 為了達(dá)到較好的壓縮效果 ， 有時游程編碼和其他一些編碼方法混合使用 。 RLC比較適合二值圖像數(shù)據(jù)序列 ， 其原因是在二值序列中 ， 只有 “ 0”和 “ 1”兩種符號；這些符號的連續(xù)出現(xiàn) ， 就形成了 “ 0”游程：L(0)， “ 1”游程： L(1)。 定義了游程和游程長度之后 ， 就可以把任何二元序列變換成游程長度的序列 ， 簡稱游程序列 。 這一變換是可逆的 ， 一一對應(yīng)的 。 無損預(yù)測編碼 ? 一幅二維靜止圖像 ， 設(shè)空間坐標(biāo) (i， j)像素點的實際灰度為 f(i,j)， 是根據(jù)以前已出現(xiàn)的像素點的灰度對該點的預(yù)測灰度 ， 也稱預(yù)測值或估計值 ，計算預(yù)測值的像素 ， 可以是同一掃描行的前幾個像素 ， 或者是前幾行上的像素 ， 甚至是前幾幀的鄰近像素 。 實際值和預(yù)測值之間的差值 ， 以下式表示： ),( jif?),(),(),( jifjifjie ???（ 713） ? 由圖像的統(tǒng)計特性可知 ， 相鄰像素之間有著較強(qiáng)的相關(guān)性 。 因此 ， 其像素的值可根據(jù)以前已知的幾個像素來估計 ， 即預(yù)測 。 ? 預(yù)測編碼是根據(jù)某一模型 ， 利用以往的樣本值對于新樣本值進(jìn)行預(yù)測 ， 然后將樣本的實際值與其預(yù)測值相減得到一個誤差值 ， 對于這一誤差值進(jìn)行編碼 。 ? 如果模型足夠好且樣本序列在時間上相關(guān)性較強(qiáng) ，那么誤差信號的幅度將遠(yuǎn)遠(yuǎn)小于原始信號 。 ? 對差值信號不進(jìn)行量化而直接編碼就稱之為無損預(yù)測編碼 。 ? 無損預(yù)測編碼器的工作原理圖 如下： 預(yù)測器 源圖像 熵編碼器 編碼表 壓縮源圖像 ? 由先前三點預(yù)測可以定義為： ? 其中 a1， a2, a3稱預(yù)測系數(shù)，都是待定參數(shù)。如果預(yù)測器中預(yù)測系數(shù)是固定不變的常數(shù)，稱之為線性預(yù)測。 ? 預(yù)測誤差： ),( jif?),1()1,1()1,(),( 321^ jifajifajifajif ???????),(),(),( ^ jifjifjie ??)],1()1,1()1,([),( 321 jifajifajifajif ????????（ 714） （ 715） ? 設(shè) a=f(i,j1)， b=f(i1,j), c=f(i1,j1)， ? 的預(yù)測方法如右圖所示 ， 可有 8種選擇方法： ),( jif?選擇方法 預(yù)測值 0 非預(yù)測 1 a c b 2 b a x 3 c 4 a+bc 5 a+(bc)/2 6 B+(ac)/2 7 (a+b)/2 例：設(shè)有一幅圖像 ， f(i1,j1),f(i1,j), f(i,j1), f(i,j)的灰度值分別為 253,252,253,255， 用圖 78第四種選擇方法預(yù)測 f(i,j)的灰度值 ， 并計算預(yù)測誤差 。 解： =a+bc= f(i,j1)+ f(i1,j) f(i1,j1)=252+253253=252 預(yù)測誤差 =255252=3 顯然，預(yù)測誤差 e(i,j)=2比像素的實際值 f(i,j)=255小的多，對 2進(jìn)行編碼比對 255直接編碼將占用更少的比特位。 ),( jif?),(),(),( jifjifjie ??? 字典壓縮算法 ? 字典編碼方法是以類似查字典的方式進(jìn)行編碼。它的 基本原理是以較長的字符串或經(jīng)常出現(xiàn)的字母組合構(gòu)成字典中的各個詞條 ，并用相對較短的數(shù)字或符號來表示的方法。 ? ? 字典編碼按其構(gòu)成的方式可分為 靜態(tài)字典方法和動態(tài)字典方法 。 ? 算法 ? LZ77 是 Jacob Ziv 和 Abraham Lempel 在1977 年發(fā)表的一篇論文中提出的。利用該算法進(jìn)行數(shù)據(jù)壓縮、解壓縮的過程，就像一個窗口在原始數(shù)據(jù)中滑動過程，故也常稱為基于滑動窗口的自適應(yīng)的字典壓縮方法。 ? 2 LZ78 算法 ? LZ78 是 Jacob Ziv 和 Abraham Lempel 在1978 年發(fā)表的另一篇論文中提出的。 LZ78 算法不同于 LZ77 算法，它放棄了窗口概念，采用樹形結(jié)構(gòu)構(gòu)造字典和保存短語，從而確保文件中的內(nèi)容均能反映到字典中。 ? 3 LZW 算法 ? 1987 年， Terry A. Welch 在 LZ78 的基礎(chǔ)上進(jìn)行了改進(jìn)，這就是著名的 LZW 壓縮算法。 ? LZW壓縮算法是一種基于字典算法的編碼方法 . 他的基本思想是建立一個編碼表 (轉(zhuǎn)換表 ) 也稱串表 ,將輸入字符串映射成定長的碼子輸出 ,通常碼長設(shè)為 12bit . ? 12 位可以有 7 096個不同的 12 位代碼 ,這就是說 ,轉(zhuǎn)換表有 7 096個表項 ,其中 256 個表項用來存放已定義的字符 ,剩下 3 870個表項用來存放前綴 ? LZW編碼算法的具體執(zhí)行步驟如下 : ? 步驟 1 : 開始時的詞典包含所有可能的根 (Root) ,而當(dāng)前前綴 P 是空的 。 ? 步驟 2 :當(dāng)前字符 (C) : = 字符流中的下一個字符 。 ? 步驟 3 :判斷綴 2符串 P + C 是否在詞典中 ? (1) 如果 “ 是 ” :P : = P + CPP(用 C 擴(kuò)展 P) 。 ? (2) 如果 “ 否 ” ? ①把代表當(dāng)前前綴 P 的碼字輸出到碼字流 。 ? ②把綴 2符串 P + C 添加到詞典 。 ? ③令 P : = CPP(現(xiàn)在的 P 僅包含一個字符 C) 。 ? 步驟 7 :判斷碼字流中是否還有碼字要譯 ? (1) 如果 “ 是 ” ,就返回到步驟 2 。 ? (2) 如果 “ 否 ” ? ①把代表當(dāng)前前綴 P 的碼字輸出到碼字流 。 ? ②結(jié)束 . 壓縮算法流程圖 ? 舉例： ? 原始碼流 35 76 67 35 76 78 90 33 35 76 78 37 ? 原理 ? (1). 準(zhǔn)備一個數(shù)據(jù)字典 (可以看做一個數(shù)組 ). 數(shù)組的前 256項初始化為 0,1,2,...,2