【文章內(nèi)容簡介】 PSNR=10lg?????????????? ?????10102^2m a x)],(),([MNMiNjjiajiaa （ 26） 要是信息是視頻或者用于商業(yè)圖片的話，常用 K=8，直接將 amax =256代入到上式。 圖像質(zhì)量評價的主觀準(zhǔn)則 主觀準(zhǔn)則也常常被用于圖像的評價當(dāng)中去。由于每個人的審美還有觀感不一樣，所以就利用多數(shù)人的態(tài)度，讓很多人去看同一張圖片，讓其打分。如表 所示的兩種經(jīng)典的評分標(biāo)準(zhǔn)。 表 對圖像質(zhì)量的主觀評價標(biāo)準(zhǔn) 得分 第一種評價標(biāo)準(zhǔn) 第二種評價標(biāo)準(zhǔn) 5 非常好 完全沒有失真 4 好 稍微失真，但是看著幾乎沒變化 3 一般 看上去有了一點(diǎn)變化 2 較差 變化 挺大 1 差 變化非常大沒法看 假設(shè)每個人的打記為 Ci ,每一種得分的評分人數(shù)為 ni ，那么我么就可以規(guī)定感覺分MOS(mean opinion score)的主觀評價得分就是： ?????KiiKiiinnCM OS01 （ 27） 例如，一幅圖像的評分為 ，這說明圖像質(zhì)量相當(dāng)好。 壓縮比 C 也是判別圖像編碼質(zhì)量的一項(xiàng)重要參數(shù)，它的概念是編碼前圖像每像素的比特?cái)?shù)與編碼指后平均每個像素的比特?cái)?shù)的比值，也常用每像素比特值（ bpp）來代表壓縮效果。 本文就采用客觀準(zhǔn)則和主觀準(zhǔn)則這兩種準(zhǔn)則來評價編碼圖像前后的質(zhì)量。 陜西理工學(xué)院畢業(yè)設(shè)計(jì) 第 6 頁 共 56 頁 霍夫曼編碼 霍夫曼于 1952 年提出一種編碼方法，該方法完全依據(jù)字符出現(xiàn)概率來構(gòu)造異字頭的平均長度最短的碼字，有時稱 之為最佳編碼，一般就叫作霍夫曼編碼 [12]。 霍夫曼編碼的基本原理 將使用次數(shù)多的代碼用長度較短的代碼代替，而使用次數(shù)少的則使用較長的編碼，并且確保編碼的唯一可解性。其最根本的原則是：累計(jì)的（字符的統(tǒng)計(jì)數(shù)字字符的編碼長度）最小，也就是權(quán)值的和最小。 ①霍夫曼編碼的基本步驟 霍夫曼編碼是一種無損編碼方法，其一般算法如下： （ 1）首先統(tǒng)計(jì)信源中各信息出現(xiàn)的概率，按信息出現(xiàn)的概率從大到小排序； （ 2）將兩個最小的概率相加成新的概率，于是剩余的概率就組成新的概率集合； （ 3）對這 個新組成的概率集合又重新排序，再次把其中兩個最小的概率相加，組成了新的概率集合。重復(fù)進(jìn)行上面的步驟，直至只剩下了兩個概率的并且和為 l； （ 4）分配碼字：碼字分配從最后一步開始進(jìn)行，對于每次相加的兩個概率，給大的賦 1，小的賦 0(同樣可以全部相反，如果兩個概率相等，則從中任選一個賦 1，另外的賦 0 就行 )，讀編碼的時侯由符號開始一直走到最后的概率和 1，將路線上所遇到的 1 和 0按最低位到最高位的順序排好，霍夫曼編碼就此形成。 ②霍夫曼編碼的特點(diǎn) 霍夫曼編碼具有不唯一性。 霍夫曼編碼對不同信源具有不同的編碼效率 。 霍夫曼編碼的結(jié)果不等長，硬件實(shí)現(xiàn)有相當(dāng)大的困難，而且誤碼傳播嚴(yán)重。 一般情況下，霍夫曼編碼的效率要比其他編碼算法的效率高一些，是最佳變長碼。但霍夫曼編碼依賴于信源的統(tǒng)計(jì)特性，必須先統(tǒng)計(jì)出信源的概率特性才能編碼，這就限制了霍夫曼編碼的實(shí)際應(yīng)用。 如圖 所示是一個霍夫曼編碼的例子。從圖中可以看到，符號只能出現(xiàn)在樹葉上，且任何一個字符的路徑都不允許是另一個字符路徑的前綴路徑，這樣，前綴編碼就構(gòu)造成功了。這樣一顆二叉樹在數(shù)據(jù)結(jié)構(gòu)中被稱為霍夫曼樹，經(jīng)常用于最佳判定，它是最優(yōu)二叉樹，是一種帶權(quán)路徑長 度最短的二叉樹。所謂樹的帶權(quán)路徑長度，就是樹中所有的葉節(jié)點(diǎn)的權(quán)值乘上其到根節(jié)點(diǎn)的路徑長度（假如根節(jié)點(diǎn)為 0 層，葉節(jié)點(diǎn)到根節(jié)點(diǎn)的路徑長度則為葉節(jié)點(diǎn)的層數(shù)）。樹的帶權(quán)路徑長度記作： WPL=(+ +?? )， N個權(quán)值 W(i=1,2，?， n)構(gòu)成一棵有N 個節(jié)點(diǎn)的二叉樹，相應(yīng)的樹節(jié)點(diǎn)的路徑長度為 L（ i=1,2，?， n），霍夫曼得出的 WPL值最小。 陜西理工學(xué)院畢業(yè)設(shè)計(jì) 第 7 頁 共 56 頁 圖 霍夫曼編碼實(shí)例 在實(shí)際應(yīng)用中，由于在霍夫曼編碼之前需要知道信源數(shù)據(jù)符號（葉節(jié)點(diǎn)）的概率，給那些要求做實(shí)時編碼的任務(wù) 帶來了麻煩。因此，在目前的實(shí)時編碼作業(yè)中，大多采用所謂的準(zhǔn)可變字長碼，例如，采用雙字長編碼，并且從短碼集合中選出一個碼子，作為長碼字頭，以保證碼字的非續(xù)長特性。另外，在數(shù)字圖像通信中采用的三類傳真機(jī)中的 MH碼，則采用了多字長 VLC技術(shù)，它是根據(jù)一系列標(biāo)準(zhǔn)圖像的統(tǒng)計(jì)分析出結(jié)果，預(yù)先在其 IC 芯片中做號碼表，使得實(shí)際的編碼解碼作業(yè)簡化為一個查表過程，從而確保了高速實(shí)時處理的需要。 霍夫曼編碼的實(shí)現(xiàn)過程 本文霍夫曼編碼壓縮圖像的步驟如下： ① 讀入圖像，并把它用矩陣表 示。 ② 統(tǒng)計(jì)圖像顏色的種數(shù)。 ③ 統(tǒng)計(jì)各種顏色值出現(xiàn)的概率，并把它們按從大到小的順序排列。 ④ 進(jìn)行霍夫曼編碼的計(jì)算： 定義一個矩陣 M， M 矩陣的第一行，存放的是需要編碼的各個顏色值出現(xiàn)的概率，并且按照從大到小排列順序，然后再將第一行從后往前兩兩相加（即概率最小的兩個數(shù)相加）， 把相加得到的結(jié)果放到第二行，然后再將第二行重新進(jìn)行排序，依此類推，一直到最后一行，這時最后一行只有兩個概率，并且相加肯定為 1 。 ⑤ 對 M 矩陣的數(shù)值進(jìn)行霍夫曼編碼： 首先建立 N 矩陣，用來存放編碼的碼字。然后將字符 0，賦給最后一行的第一小段，再將字符 1，賦給最后一行的第二小段，在 M 矩陣中，由于每一行的最后兩個數(shù)，都是這一行中概率最小的兩個數(shù)，所以將倒數(shù)第二行的最后兩個數(shù)進(jìn)行相加，然后用相加的結(jié)果到倒數(shù)第一行中去尋找，肯定會在倒數(shù)第一行中找到一樣的值，然后記錄下來在倒數(shù)第一行中這個值的位置，再將這個在 M 矩陣中的位置對應(yīng)到 N 矩陣中，將 N 矩陣中的該位置的字符賦給倒數(shù)第二行的第二小段和第三小段，最后在給 第二小段的后面賦字符 0，給第三小段后面賦字符 1，然后將在最后一行找到的那個數(shù)的左邊的數(shù)，一一對應(yīng)到上一行去，右邊的數(shù)，向左串一位，再對應(yīng)到上一行去，這樣依此類推，那么在 N 矩陣的第一行，可以得到最后陜西理工學(xué)院畢業(yè)設(shè)計(jì) 第 8 頁 共 56 頁 的編碼。 霍夫曼編碼的實(shí)現(xiàn)及評價 編碼結(jié)果 實(shí)驗(yàn)程序見附錄 C 實(shí)驗(yàn)結(jié)果如下： 原始圖像大小 Name Size Bytes Class f0 256x256 66560 uint8 array Elapsed time is seconds. 壓縮圖像大小 Name Size Bytes Class f 256x256 66560 uint8 array Elapsed time is seconds. 圖 原始圖像 圖 編碼圖像 陜西理工學(xué)院畢業(yè)設(shè)計(jì) 第 9 頁 共 56 頁 圖 解碼圖像 霍夫曼編碼的客觀評價 客觀準(zhǔn)則評價霍夫曼編碼壓縮圖像質(zhì)量 由前文 圖像編碼質(zhì)量的評價可知，客觀準(zhǔn)則評價霍夫曼編碼壓縮圖像的質(zhì)量即求壓縮圖像與原始圖像的峰值信噪比（ PSNR）。 求 PSNR 的程序見附錄 C 求得結(jié)果為： mse = psnr = entropy = 霍夫曼編碼的主觀評價 主觀準(zhǔn)則評價霍夫曼編碼壓縮圖像質(zhì)量 根據(jù)前文 圖像編碼質(zhì)量的評價的主觀評價準(zhǔn)則，我收集了 30 分主觀評價的 樣本； 運(yùn)用公式（ 27） ?????KiiKiiinnCM OS01 可得，霍夫曼編碼壓縮圖像的主觀評價得分為： MOS= 255 25*55*4 ?? = 實(shí)驗(yàn)結(jié)果分析 從本次實(shí)驗(yàn)結(jié)果看熵為 ，均值誤差（ MSE）為 而峰值信噪比（ PSNR）達(dá)到 ，主觀得分也高達(dá) ，說明本次壓縮圖片編碼理論上的最少傳輸量為 ,測量數(shù)據(jù)可信度非常之高，無論從主觀還是客觀方面來看，圖像的壓縮質(zhì)量都是非常好的，只 是程序的編碼時間為 ，而程序的解碼時間更是達(dá)到了 ，整個編解陜西理工學(xué)院畢業(yè)設(shè)計(jì) 第 10 頁 共 56 頁 碼的過程共花了 4分多鐘，僅僅是一幅圖片就花了 4 分多鐘，這在圖像壓縮的編碼算法中是比較慢的了，若只考慮圖像壓縮的質(zhì)量，可以用這種編碼，如有數(shù)量的要求則不建議使用這種編碼算法。 從本次試驗(yàn)來看霍夫曼編碼的特點(diǎn)為： （ 1）進(jìn)行無損編碼需要知道數(shù)據(jù)的概率； （ 2）發(fā)信者與受信者需要使用同一張定制的編碼 /解碼表，在音頻中即是編碼器和解碼器要共用一張表； （ 3）無損編碼的效率會因概率表的不同而不同，這就是為什么 各種無損音頻編碼的壓縮率不一樣； （ 4）無損編碼不會造成信息的損失，不用擔(dān)心圖像進(jìn)行無損編碼之后會劣化。 與實(shí)現(xiàn)及其性能對比 算術(shù)編碼 算術(shù)編碼 是一種無失真的編碼方法，能有效地壓縮信源冗余度，使編成的碼率趨于信源的熵 ，它是無損壓縮的一種 [13]。 算術(shù)編碼的基本原理 算術(shù)編碼的基本原理是：根據(jù)信源可能發(fā)現(xiàn)的不同符號序列的概率，把 [0， 1)區(qū)間劃分為互不重疊的子區(qū)間，子區(qū)間的寬度恰好是各符號序列的概率。這樣信源發(fā)出的不同符號序列將與各子區(qū)間一一對應(yīng)，因此每個 子區(qū)間內(nèi)的任意一個實(shí)數(shù)都可以用來表示對應(yīng)的符號序列，這個數(shù)就是該符號序列所對應(yīng)的碼字。顯然，一串符號序列發(fā)生的概率越大，對應(yīng)的子區(qū)間就越寬，要表達(dá)它所用的比特?cái)?shù)就減少，因而相應(yīng)的碼字就越短。 算術(shù)編碼可以是靜態(tài)的或者自適應(yīng)的。在靜態(tài)算術(shù)編碼中，信源符號的概率是固定的。本文主要是以靜態(tài)算術(shù)編碼算法為例。 在自適應(yīng)算術(shù)編碼中， 自適應(yīng)算術(shù)編碼在對符號序列進(jìn)行掃描的過程中，可一次完成兩個過程，即根據(jù)恰當(dāng)?shù)母怕使烙?jì)模型和當(dāng)前符號序列中各符號出現(xiàn)的頻率，自適應(yīng)地調(diào)整各符號的概率估計(jì)值，同時完成編碼。 信源符號的概率根據(jù)編碼 時符號出現(xiàn)的頻繁程度動態(tài)地進(jìn)行修改，在編碼期間估算信源符號概率的過程叫做建模。需要開發(fā)態(tài)算術(shù)編碼的原因是因?yàn)槭孪戎谰_的信源概率是很難的，而且是不切實(shí)際的。當(dāng)壓縮消息時，我們不能期待一個算術(shù)編碼器獲得最大的效率，所能做的最有效的方法是在編碼過程中估算概率。 盡管從編碼效率上看不如已知概率表的情況，但正是由于算術(shù)編碼自適應(yīng)的調(diào)整對個符號概率的估計(jì)值，這點(diǎn)比哈弗曼編碼相比，具有實(shí)時性好、靈活性高、適應(yīng)性強(qiáng)等特點(diǎn)，在圖像壓縮、視頻圖像編碼等領(lǐng)域都得到了廣泛的應(yīng)用 [14]。 算術(shù)編碼的優(yōu)點(diǎn)： （ 1） 不必 預(yù)先定義概率模型 ， 自適應(yīng)模式具有獨(dú)特的優(yōu)點(diǎn) ； （ 2） 信源符號概率接近時 ， 建議使用算術(shù)編碼 ， 這種情況下其效率高于 霍夫曼 編碼 ； （ 3） 算術(shù)編碼繞過了用一個特定的代碼替代一個輸入符號的想法 ， 用一個浮點(diǎn)輸出數(shù)值代替一個流的輸入符號 ， 較長的復(fù)雜的消息輸出的數(shù)值中就需要更多的位數(shù) ； （ 4） 算術(shù)編碼實(shí)現(xiàn)方法復(fù)雜一些 ， 但 JPEG 成員對多幅圖像的測試結(jié)果 表 明 ， 算術(shù)編碼比 霍夫曼 編碼提高了 10%左右的效率 ， 因此在 JPEG擴(kuò)展系統(tǒng)中用算術(shù)編碼取代 霍夫曼 編碼。 算術(shù)編碼雖然具有其獨(dú)特的優(yōu)點(diǎn)，但我們?nèi)孕枰⒁庀?面幾個問題： （ 1）由于實(shí)際的計(jì)算機(jī)的精度不可能無限長，運(yùn)算中出現(xiàn)溢出是一個明顯的問題，但多數(shù)機(jī)器都有 16 位、 32 位或者 64 位的精度，因此這個問題可使用比例縮放方法解決。 （ 2）算術(shù)編碼器對整個消息只產(chǎn)生一個碼字，這個碼字是在間隔 [0,1)中的一個實(shí)數(shù)，因此譯碼器在接受到表示這個實(shí)數(shù)的所有位之前不能進(jìn)行譯碼。 陜西理工學(xué)院畢業(yè)設(shè)計(jì) 第 11 頁 共 56 頁 （ 3）算術(shù)編碼也是一種對錯誤很敏感的編碼方法，如果有一位發(fā)生錯