【正文】 home 數(shù)據(jù)壓縮方法的分類 1 .無損壓縮 （ Lossless Compression） : ? Huffman編碼 和 Shannon編碼根據(jù)概率分布特性確定碼長(zhǎng)。 ? 游程編碼：根據(jù)連續(xù)灰度的行程來確定編碼。 ? 算術(shù)編碼：隨信源數(shù)據(jù)不斷縮小實(shí)數(shù)區(qū)間，然后用一個(gè)與實(shí)數(shù)對(duì)應(yīng)的二進(jìn)制碼代表被編碼的信息。 ? 輪廓編碼：根據(jù)相同灰度的區(qū)域邊界線進(jìn)行編碼。 上 一 頁 下 一 頁 home 有損壓縮（ Lossy Compression） ? 預(yù)測(cè)編碼 ：根據(jù)相鄰像素的相關(guān)性來確定后續(xù)像素的預(yù)測(cè)值，若用差值進(jìn)行編碼。 ? 變換編碼 ：對(duì)于原始圖像進(jìn)行正交變換，在變換域進(jìn)行抽樣達(dá)到壓縮目的。 ? 混合編碼 現(xiàn)代壓縮編碼方法： ? 分形編碼 ? 模型基（ Modelbased）編碼 上 一 頁 下 一 頁 home 統(tǒng)計(jì)編碼（ statistic coding) ? 統(tǒng)計(jì)編碼 – 根據(jù)信源的概率分布特性，分配具有惟一可譯性的可變長(zhǎng)碼字，降低平均碼字長(zhǎng)度，以提高信息的傳輸速度，節(jié)省存儲(chǔ)空間。 ? 基本原理 – 在信號(hào)概率分布情況已知的基礎(chǔ)上，概率大的信號(hào)對(duì)應(yīng)的碼字短，概率小的信號(hào)對(duì)應(yīng)的碼字長(zhǎng)，這樣就降低了平均碼字長(zhǎng)度。 – 各種統(tǒng)計(jì)編碼的差異在于信號(hào)與編碼對(duì)應(yīng)的規(guī)則不同，性能也不同。 上 一 頁 下 一 頁 home ? 變長(zhǎng)最佳編碼定理 【 定理 】 在變長(zhǎng)編碼中 ， 對(duì)出現(xiàn)概率大的信息符號(hào)賦予短碼字 ， 而對(duì)于出現(xiàn)概率小的信息符號(hào)賦予長(zhǎng)碼字 。 如果碼字長(zhǎng)度嚴(yán)格按照所對(duì)應(yīng)符號(hào)出現(xiàn)概率大小逆序排列 ， 則編碼結(jié)果平均碼字長(zhǎng)度一定小于任何其他排列方式 。 1952年根據(jù)上述定理 ， 提出了依據(jù)信源集中符號(hào)出現(xiàn)的概率分配不同長(zhǎng)度的唯一可譯碼的算法 。 Huffman編碼 上 一 頁 下 一 頁 home ? 1．前綴碼（ Prefix Code） ? 一組唯一可譯碼中任意一個(gè)碼字都只與一個(gè)信號(hào)存在對(duì)應(yīng)關(guān)系。為了譯碼需要，在唯一可譯碼中的前綴碼保證任意一個(gè)碼字都不是其他碼字的前綴。 ? 舉例：有一維圖像的符號(hào)集合f(i)={f(1),f(2),f(3),f(4)} ? 設(shè)定的碼字集合 c(i)={0,10,110,111} ? 若一前綴碼為 0101111100， 譯碼輸出信號(hào)？ 上 一 頁 下 一 頁 home 4層樹形結(jié)構(gòu)的編碼情況 上 一 頁 下 一 頁 home 2． Huffman編碼 算法： ? ① 將圖像的灰度等級(jí)按概率大小進(jìn)行升序排序。 ? ② 在灰度級(jí)集合中取兩個(gè)最小概率相加，合成一個(gè)概率。 ? ③ 新合成的概率與其他的概率成員組成新的概率集合。 ? ④ 在新的概率集合中，仍然按照步驟②～③的規(guī)則，直至新的概率集合中只有一個(gè)概率為 1的成員。這樣的歸并過程可以用二叉樹描述。 ? ⑤ 從根節(jié)點(diǎn)按前綴碼的編碼規(guī)則進(jìn)行二進(jìn)制編碼。 上 一 頁 下 一 頁 home Huffman編碼示意圖 ? 左圖所示為建立碼的過程 ? 右圖所示為從根開始，經(jīng)各中間節(jié)點(diǎn)到葉節(jié)點(diǎn)的路徑采用二進(jìn)制編碼的情況 上 一 頁 下 一 頁 home 編碼過程舉例 ? 第 1行和第 2行列舉了一個(gè)信源的統(tǒng)計(jì)特性 ? 結(jié)果如第三行所示 符號(hào)集 {xi} x1 x2 x3 x4 x5 x6 概率分布 {pi} Huffman編碼 1 010 000 001 0110 0111 上 一 頁 下 一 頁 home ? 信源的熵 H(x)= ? 哈夫曼編碼的平均碼字長(zhǎng)度 R(x)= 上 一 頁 下 一 頁 home 3． Huffman編碼的性能 ? 優(yōu)點(diǎn)： – 實(shí)現(xiàn) Huffman編碼的基礎(chǔ)是統(tǒng)計(jì)源數(shù)據(jù)集中各信號(hào)的概率分布。 – Huffman編碼在無失真的編碼方法中效率優(yōu)于其他編碼方法，是一種最佳變長(zhǎng)碼，其平均碼長(zhǎng)接近于熵值。 ? 缺點(diǎn)： – 當(dāng)信源數(shù)據(jù)成分復(fù)雜時(shí)，龐大的信源集致使 Huffman碼表較大，碼表生成的計(jì)算量增加，編譯碼速度相應(yīng)變慢 – 不等長(zhǎng)編碼致使硬件譯碼電路實(shí)現(xiàn)困難。上述原因致使Huffman編碼的實(shí)際應(yīng)用受到限制。 上 一 頁 下 一 頁 home 4．圖像的 Huffman編譯碼系統(tǒng) 上 一 頁 下 一 頁 home Shannon編碼與 Fano編碼 ? 1. 1948年 ,Shannon提出了將信源符號(hào)依其概率降序排列，用符號(hào)序列累積概率的二進(jìn)制表示作為對(duì)信源的唯一可譯編碼。 ? 其應(yīng)用于圖像編碼的步驟如下： ? （ 1）將 N個(gè)灰度級(jí) xi按其概率遞減進(jìn)行排列。 ? （ 2）求概率分布 pi的第 i個(gè)灰度級(jí)的二進(jìn)制位數(shù) ni。 ? () ? （ 3）計(jì)算與 pi相對(duì)應(yīng)的累積概率 Pi, 把與 Pi相對(duì)應(yīng)的二進(jìn)碼和接下去與pk（ ki）相應(yīng)的碼相比較，前面的 ni位至少有一位以上的數(shù)字是不同的。 1l o gl o g 22 ????? iii pnp上 一 頁 下 一 頁 home 【 例 】 由表 Shannon編碼 ? 平均碼字長(zhǎng)度為 ，較 Huffman編碼為長(zhǎng)。 上 一 頁 下 一 頁 home ? （ 1）將圖像灰度級(jí) xi其概率大小按遞減順序進(jìn)行排序。 ? （ 2）將 xi分成兩組，使每組的概率和盡量接近。 – 給第一組灰度級(jí)分配代碼“ 0”，第二組分配代碼“ 1”。 ? （ 3）若每組還是由兩個(gè)或以上的灰度級(jí)組成，重復(fù)上述步驟，直至每組只有一個(gè)灰度級(jí)為止。 上 一 頁 下 一 頁 home 【 例 】 圖 Fano編碼。 上 一 頁 下 一 頁 home 算術(shù)編碼 ? 在信源各符號(hào)概率接近的條件下，算術(shù)編碼是一種優(yōu)于Huffman編碼的方法。 ? 20世紀(jì) 60年代， 與分組碼有本質(zhì)差別的編碼方法：算術(shù)編碼（ arithmetic coding）的概念 ,直到 20世紀(jì) 80年代才得以實(shí)現(xiàn)。 ? 基本思想：按照符號(hào)序列的出現(xiàn)概率對(duì)概率區(qū)間分割，用一個(gè)實(shí)數(shù)代表一個(gè)數(shù)據(jù)流的輸入符號(hào)，再將這個(gè)實(shí)數(shù)轉(zhuǎn)化為一定位數(shù)的二進(jìn)制代碼。 上 一 頁 下 一 頁 home ? 主要步驟： ? （ 1）首先把當(dāng)前區(qū)間定義為 【 0,1）； ? （ 2）對(duì)輸入流中的每個(gè)符號(hào) s，重復(fù)下面的兩步： ? 把當(dāng)前區(qū)間分割為長(zhǎng)度正比于符號(hào)概率的子區(qū)間； ? 為 s選擇一個(gè)子區(qū)間，并將其定義為新的當(dāng)前區(qū)間； ? （ 3）當(dāng)把整個(gè)輸入流處理完后，輸出的即為能唯一確定當(dāng)前區(qū)間的數(shù)字。 上 一 頁 下 一 頁 home ? 【 例 61】 根據(jù)信源的概率分布進(jìn)行算術(shù)編碼 。 已知信源的概率分布為 ? 求二進(jìn)制序列 01011的編碼 。 ?????????535210X上 一 頁 下 一 頁 home 舉例 ? 解：步驟如下： ? （ 1） 二進(jìn)制信源只有 x1 = 0和 x2 = 1兩種符號(hào) ， 相應(yīng)的概率為 pc = 2/5, pe = 1 pc =3/5 ? （ 2） 設(shè) s為區(qū)域左端起始位置 ， e為區(qū)域右端終止位置 ， l為子區(qū)的長(zhǎng)度 ， 則 – 符號(hào) “ 0”的子區(qū)為 [0， 2/5） ， 子區(qū)長(zhǎng)度為 2/5 。 – 符號(hào) “ 1”的子區(qū)為 [2/5 ， 1]， 子區(qū)長(zhǎng)度為 3/5 。 上 一 頁 下 一 頁 home （ 3） 隨著序列符號(hào)的出現(xiàn) ， 子區(qū)按下列公式減少長(zhǎng)度 : ? 新子區(qū)左端 = 前子區(qū)左端 + 當(dāng)前子區(qū)左端 前子區(qū)長(zhǎng)度 ? 新子區(qū)長(zhǎng)度 = 前子區(qū)長(zhǎng)度 當(dāng)前子區(qū)長(zhǎng)度 ? 設(shè)初始子區(qū)為 [0， 1]， 步序?yàn)?step， 則編碼過程參見 實(shí)例 。 ? 可見 ， 最后子區(qū)左端起始位置 二進(jìn)十進(jìn) （）（ )00 11 2569 2 ??s上 一 頁 下 一 頁 home ? 最后子區(qū)長(zhǎng)度 ? 最后子區(qū)右端終止位置 ? 編碼結(jié)果為子區(qū)起始位置與終止位