第4章多媒體數(shù)據(jù)壓縮與編碼技術(shù)-文庫吧
2025-02-12 01:03 本頁面
【正文】 空間中每 —事件的概率不相等時的平均信息量為信息熵，則信息熵 H可采用如下公式計算： （ 44） ( ) log ( )k a kI x p??11{ ( ) } ( ) l ognnk k k k a kkkH E I x p I x p p??? ? ? ??? 哈夫曼（ Huffman）編碼 【例 】信息熵的計算。 設(shè) 8個隨機變量具有同等概率為 1/8，則熵： 即計算出 H=3比特。 ? 2. Huffman編碼 Huffman編碼是 1952年由 Huffman提出的一種編碼方法。它在變長編碼方法中是最佳的。 82111( ) l og 388jH X bit?? ? ?? 哈夫曼（ Huffman）編碼 設(shè)信源 A的信源空間為： 其中 ， 現(xiàn)用 r個碼符號的碼符號集 對信源 A中的每個符號 （ i＝ 1，2， … ， N）進行編碼。具體編碼的方法是： (1)把信源符號按其出現(xiàn)概率的大小順序排列起來； (2)把最末兩個具有最小概率的元素之概率加起來； ? ? 1212:( ) : ( ) ( ) ( )NNA a a aAPP A P a P a P a???? ????1 ( ) 1Nii Pa? ?? ? ?12: , , , rX x x xia 哈夫曼（ Huffman）編碼 (3)把該概率之和同其余概率由大到小排隊，然 后再把兩個最小概率加起來，再重新排隊； 重復(fù)步驟 ,直到最后只剩下兩個概率為止。 在上述工作完畢之后，從最后兩個概率開始逐步向前進行編碼。對于概率大的賦予 0，小的賦予 1。 哈夫曼（ Huffman）編碼 哈夫曼（ Huffman）編碼 經(jīng)霍夫曼編碼后，平均碼長為： = 1＋ 2＋ 4+ 5+ 5 =（ bit） 61()iiiB P w n?? ? 哈夫曼（ Huffman）編碼 ? 3. Huffman編碼的幾點說明 （ 1） Huffman編碼是最佳的，雖然構(gòu)造出來的碼不唯一，但其平均碼長卻相同，所以不影響編碼效率和數(shù)據(jù)壓縮性能。 （ 2）由于 Huffman碼的碼長參差不齊，因此，存在一個輸入、輸出速率匹配問題。解決的辦法是設(shè)置一定容量的緩沖存儲器。 （ 3） Huffman碼在存儲或傳輸過程中，如果出現(xiàn)誤碼，可能會引起誤碼的連續(xù)傳播，1bit的誤碼可能把一大串碼字全部破壞，因此，限制了 Huffman碼的使用。 哈夫曼（ Huffman）編碼 （ 4） Huffman編碼對不同信源其編碼效率也不盡相同。當(dāng)信源概率是 2的負(fù)次冪時，Huffman碼的編碼效率達(dá)到 100％；當(dāng)信源概率相等時，其編碼效率最低。這表明在使用Huffman方法編碼時，只有當(dāng)信源概率分布很不均勻時， Huffman碼才會收到顯著的效果。 （ 5） Huffman編碼應(yīng)用時，均需要與其他編碼結(jié)合起來使用，才能進一步提高數(shù)據(jù)壓縮比。例如，在靜態(tài)圖像處理標(biāo)準(zhǔn) JPEG中，先對圖像像素進行 DCT變換、量化、 Z形掃描、游程編碼后，再進行霍夫曼編碼。 費諾編碼 具體編碼方法如下： （ 1）把 按概率由大到小、從上到下排成一列，然后把 分成兩組 ， ，并使這兩組符號概率和相等或幾乎相等，即： （ 2）把兩組分別按 0， 1賦值 ,例如將第一組賦值為 0，則第二組賦值為 1。然后分組、賦值，不斷反復(fù)，直到每組只有一種輸入為止。將每個所賦的值依次排列起來就是 香農(nóng) 費諾編碼。 1,..., nxx1,..., n1,..., kxxnk xx ,...,1?11( ) ( )kniji j kP x P x? ? ???? 費諾編碼 以前面的數(shù)據(jù)為例，香農(nóng) 編碼費諾如圖 示。 算術(shù)編碼 理論上，用 Huffman方法對源數(shù)據(jù)流進行編碼可達(dá)到最佳編碼效果。但由于計算機中存儲、處理的最小單位是“位”，因此，在一些情況下，實際壓縮比與理論壓縮比的極限相去甚遠(yuǎn)。 算術(shù)編碼把要壓縮處理的整段數(shù)據(jù)映射到 — 段實數(shù)半開區(qū)間 [0， 1]內(nèi)的某一區(qū)段，構(gòu)造出小于 1且大于或等于 0的數(shù)值。這個數(shù)值是輸入數(shù)據(jù)流的唯 — 可譯代碼。 算術(shù)編碼 下面通過一個例子來說明算術(shù)編碼的方法。 對一個 5符號信源 A＝ {a1， a2， a3， a2， a4}，各字符出現(xiàn)的概率和設(shè)定的取值范圍如下表： 算術(shù)編碼 為討論方便起見，假定有 式中 Ns為新子區(qū)間的起始位置； Fs為前子區(qū)間的起始位置， Cl當(dāng)前符號的區(qū)間左端； Ne為新子區(qū)間的結(jié)束位置； Fe為前子區(qū)間的結(jié)束位置； Cr當(dāng)前符號的區(qū)間右端； L為前子區(qū)間的長度。 按上述區(qū)間的定義，最終結(jié)果如表 ： LCFN lss *?? *e e rN F C L?? 算術(shù)編碼 給定事件序列的算術(shù)編碼步驟如下： （ 1）編碼器在開始時將“當(dāng)前間隔” [ L， H] 設(shè)置為 [0， 1）。 （ 2）對每一事件，編碼器按步驟（ a）和（ b）進行處理 算術(shù)編碼 （ a）編碼器將“當(dāng)前間隔”分為子間隔，每一個事件一個。 （ b）一個子間隔的大小與下一個將出現(xiàn)的事件的概率成比例，編碼器選擇子間隔對應(yīng)于下一個確切發(fā)生的事件相對應(yīng)，并使它成為新的“當(dāng)前間隔”。 最后輸出的“當(dāng)前間隔”的下邊界就是該給定事件序列的算術(shù)編碼。 算術(shù)編碼 在算術(shù)編碼中有幾個問題需要注意： ? 由于實際的計算機的精度不可能無限長，一個明顯的問題是運算中出現(xiàn)溢出，但多數(shù)機器都有 1 32或者 64位的精度，因此這個問題可使用比例縮放方法解決。 ? 算術(shù)編碼器對整個消息只產(chǎn)生一個碼字，這個碼字是在間隔 [0， 1]中的一個實數(shù)，因此譯碼器在接收到表示這個實數(shù)的所有位之前不能進行譯碼。 ? 算術(shù)編碼也是一種對錯誤很敏感的編碼方法，如果有一位發(fā)生錯誤就會導(dǎo)致整個消息譯錯。 游程編碼（ RLC） 游程編碼是一種利用空間冗余度壓縮圖像的方法，相對比較簡單，也屬于統(tǒng)計編碼類。 設(shè)圖像中的某一行或某一塊像素經(jīng)采樣或經(jīng)某種方法變換后的系數(shù)為 ，如圖。某一行或某一塊內(nèi)像素值 可分為 k段，長度 為的連續(xù)串，每個串具有相同的值，那么，該圖像的某一行或某一塊可由下面偶對 來表示： ，其中 為每個串內(nèi)的代表值， 為串的長度。 12( , , , )Mx x xixil( , )i
研究報告相關(guān)推薦
鄂ICP備17016276號-1