3）哈夫曼編碼方法（huffman）

1、數(shù)字圖像處理,第十五章圖像壓縮和編碼,CH15 圖像壓縮和編碼,一、序言二、無損壓縮技術(shù)三、圖像的無失真編碼方法四、預(yù)測壓縮技術(shù)五、變換壓縮技術(shù)六、活動圖像壓縮技術(shù)七、圖像壓縮編碼的新進展要點總結(jié)上機實習,1 序言,1）圖像壓縮編碼的目的,1 序言,目的：節(jié)省圖像存儲容量；減少傳輸信道容量；縮短圖像加工處理時間。原因：圖像像素之間、行之間、幀之間有較強的相關(guān)性。從統(tǒng)計的觀點，某點像素的灰度與其鄰域灰度有密切關(guān)系；

2、從信息論關(guān)系，減少圖像信息中冗余信息。,1 序言,2）圖像壓縮編碼的分類（1）無損編碼又稱為信息保持編碼。要求編碼—解碼過程中能夠無誤差的重建圖像。如在醫(yī)學圖像應(yīng)用中。（2）有損編碼常被稱為保真度編碼。常用在圖像的信宿為人眼的應(yīng)用中，如數(shù)字電視、可視電話等。（3）特征抽取編碼是另一種有損編碼。常用在圖像的信宿為計算機的應(yīng)用中，這是只需要保留計算機處理的信息特征。如圖像識別。,1 序言,3）圖像壓縮編碼的具體方法（1）熵編

3、碼：信息保持編碼；（2）預(yù)測法：信息保持編碼、保真度編碼（更常用）；（3）變換法：特征保持編碼；（4）其他編碼法,2 無損壓縮技術(shù),1）基本概念,,,,2 無損壓縮技術(shù),2）變長最佳編碼定理和唯一可譯代碼,,,2 無損壓縮技術(shù),2 無損壓縮技術(shù),3）哈夫曼編碼方法（Huffman）,2 無損壓縮技術(shù),2 無損壓縮技術(shù),Huffman編碼討論（1） Huffman編碼是唯一可譯碼。短的碼不會成為更長碼的啟始部分；（2） Huff

4、man編碼的平均碼長接近于熵；（3）缺點：與計算機的數(shù)據(jù)結(jié)構(gòu)不匹配；（4）缺點：需要多次排序，耗費時間。,2 無損壓縮技術(shù),Huffman編碼Huffman編碼最優(yōu)性擴展Huffman編碼自適應(yīng)Huffman編碼Will be learnt in Multimedia Technology (請課后自學……),2 無損壓縮技術(shù),4）香農(nóng)編碼法（Fano-Shannon）,2 無損壓縮技術(shù),,2 無損壓縮技術(shù),F

5、ano-Shannon編碼討論（1） Fano-Shannon編碼是唯一可譯碼。短的碼不會成為更長碼的啟始部分；（2） Fano-Shannon編碼的平均碼長接近于熵；編碼效率略低于Huffman編碼。,3 圖像的無失真編碼方法,1）白塊跳過編碼WBS2）行程長度編碼3）比特平面編碼4）二值圖像編碼的國際標準G3和G4,3 圖像的無失真編碼方法,0）壓縮比直接編碼一幅圖像所需比特數(shù)取決于幅面大小及分辨率。設(shè)C為采用某種方法

6、編碼前后的 壓縮比,,3 圖像的無失真編碼方法,1）白塊跳過編碼WBS原理對于一般白紙黑字的文件，總是白的面積大。因此跳過白的行程，只對黑行程編碼就可以壓縮數(shù)據(jù)。一維WBS編碼將每一掃描行分成若干段，每段包含n個像素。對于全白段，給最短碼字如0；而對于黑白相間或全黑段，不進行壓縮。為區(qū)別全白段和有黑段，在編碼前加1作為標志位。,3 圖像的無失真編碼方法,一維WBS編碼平均碼長例,3 圖像的無失真編碼方法,常用圖像WB

7、S編碼平均碼長,3 圖像的無失真編碼方法,二維WBS編碼將圖像分成M*N大小的塊，全白塊以0編碼，其他同一維WBS編碼。,為什么?,3 圖像的無失真編碼方法,自適應(yīng)WBS編碼根據(jù)圖像局部結(jié)構(gòu)或統(tǒng)計特性，改變像素塊尺寸大??；一維情況下，首先判斷該行是否有1024個連續(xù)白像素；否則判斷是否有64，16，4個連續(xù)白像素；否則直接編碼；在每一行編碼前要加上N為多少的代碼。自適應(yīng)WBS編碼可以有效增加圖像的 壓縮比，但增加了編碼設(shè)備

8、的復(fù)雜性。,3 圖像的無失真編碼方法,2）行程長度編碼（RLC，Run-Length Coding）原理：二值圖像從左到右掃描圖像時，連續(xù)白點和連續(xù)黑點總是交替出現(xiàn)。將連續(xù)像素的數(shù)目稱為行程長度（Run-Length），分別為白長和黑長。方法：統(tǒng)計所有行程長度出現(xiàn)的概率，然后采用Huffman編碼。在每一行的行首加標志位，確定是白長還是黑長。以后黑長和白長交替出現(xiàn)。,3 圖像的無失真編碼方法,3）比特平面編碼思想：對于灰度或彩色

9、圖像，如果每個像素用k位表示，將相同位上的0，1取出，就可以形成k個N*N的二值圖像。將每一個二值圖像稱為一個比特平面。方法：對于比特平面采用前述的無失真二值圖像壓縮技術(shù)。,希望連續(xù)的0/1出現(xiàn)的概率增大.,Lena圖像的比特平面,3 圖像的無失真編碼方法,問題：采樣自然二進制碼，將導致數(shù)據(jù)相關(guān)性減小。如灰度127和128，對應(yīng)自然二進制碼分別為01111111和10000000。較小的灰度變化導致比特平面的突變。解決方法：采用格雷

10、碼（Gray）。,3 圖像的無失真編碼方法,,,,3 圖像的無失真編碼方法,4）傳真國際標準G3和G4（1）G3采用一維行程長度編碼；（2）行程采用Huffman編碼；（3）0－63之間的行程，用單個碼字即終止碼表示；（4）大于63的游長用一個形成碼和一個終止碼組合表示。形成碼表示實際行程對64的倍數(shù)；（5）G3能達到15：1的壓縮比；（6）G4采用二維行程程度編碼，壓縮比比G3提高30％。,4 預(yù)測壓縮技術(shù),1）基本思想

11、2）預(yù)測誤差的熵編碼3）DPCM預(yù)測編碼4）最佳線性預(yù)測5）有失真預(yù)測編碼6）最佳量化,4 預(yù)測壓縮技術(shù),1）基本思想圖像相鄰像素間存在很強的相關(guān)性，通過觀察其相鄰像素取值，可以預(yù)測一個像素的大概情況。預(yù)測值和實際值存在誤差，稱為預(yù)測誤差。預(yù)測誤差的方差必然比原圖像像素的方差小，因此對預(yù)測誤差進行編碼必然壓縮其平均碼長。對預(yù)測誤差進行編碼的技術(shù)稱為DPCM（差分脈沖編碼調(diào)制）。,請結(jié)合熵的定義思考這個結(jié)論,4 預(yù)測壓縮技

12、術(shù),2）預(yù)測誤差的熵編碼對比一幅圖像和其差分圖像的標準差和熵。從Lenna和Bob的差分圖像的直方圖看：不同圖像的差分圖像直方圖分布形態(tài)大致相同，只是方差有所不同。,4 預(yù)測壓縮技術(shù),Lenna差分圖象,4 預(yù)測壓縮技術(shù),Bob差分圖象,4 預(yù)測壓縮技術(shù),3）DPCM預(yù)測編碼預(yù)測器的階數(shù)對當前像素進行預(yù)測的像素集合中的像素個數(shù)，稱為預(yù)測器的階數(shù)。理論上預(yù)測器的階數(shù)越大越好，當階數(shù)大于3時其性能的改變非常有限。

13、預(yù)測器的系數(shù)如一個3階預(yù)測器中，各像素的權(quán)重稱為預(yù)測器的系數(shù)。其既可以固定不變，也可以變化。,如何預(yù)測?,4 預(yù)測壓縮技術(shù),4）最佳線性預(yù)測目的：尋找使預(yù)測器的某種誤差函數(shù)為最小的線性預(yù)測器；準則：均方預(yù)測誤差最小化。,,,4 預(yù)測壓縮技術(shù),最常用的一階DPCM編碼器在實際中最常用的是一階DPCM編碼器，此時有唯一的一個預(yù)測系數(shù)1。,4 預(yù)測壓縮技術(shù),為實現(xiàn)無失真編碼，通常對差分圖像進行熵編碼（通常是Huffman編碼）；預(yù)測

14、誤差熵編碼的步驟：建立碼表和編碼。通常采用一個通用碼表，節(jié)省建立專用碼表時間，由此帶來壓縮比損失較?。痪幋a：若對差分圖像所有灰度建立碼表，則項數(shù)較多。通常對－16~16采用Huffman編碼，其他直接用前綴＋實際灰度值。,4 預(yù)測壓縮技術(shù),采用同一掃描行中前幾個像素值進行預(yù)測，稱為一維預(yù)測；采用同一行或前幾行像素值進行預(yù)測，稱為二維預(yù)測；采用前幾行和前幾幀像素值進行預(yù)測，稱為三維預(yù)測。,4 預(yù)測壓縮技術(shù),5）有失真預(yù)測編碼由于預(yù)

15、測誤差的方差遠比像素取樣值小，因此需要對預(yù)測誤差重新量化。,減少需編碼信息符號的數(shù)目,4 預(yù)測壓縮技術(shù),由于量化器存在量化誤差，因此帶量化器的DPCM系統(tǒng)是有失真預(yù)測編碼。,,4 預(yù)測壓縮技術(shù),6）最佳量化由于預(yù)測誤差滿足拉普拉思分布，在量化比特數(shù)b確定情況下，根據(jù)量化誤差的均方值最小原則設(shè)計。（參見CH2），從而使判決電平和量化電平滿足于其中量化比特數(shù)b確定取決于信噪比。,4 預(yù)測壓縮技術(shù),自適應(yīng)量化：將圖像分割為圖像方塊

16、，按各自標準差進行量化。但需要將各塊的方差編碼發(fā)送給接收端。另一種方法：將圖像方塊方差大小分為4類：平坦區(qū)域，紋理區(qū)域，緩變區(qū)域和陡峭區(qū)域。每一類方塊采用不同的量化器。,5 變換壓縮技術(shù),1）基本概念將在空域上描述的圖像，經(jīng)過某種變換（通常采用傅立葉變換，沃爾什變換等），在某種變換域里進行描述。在變換域里，首先降低了圖像的相關(guān)性；其次通過某種圖像處理（如頻域的二維濾波）以及熵編碼，則可進一步壓縮圖像的編碼比特率。,5 變換壓縮技術(shù)

17、,2）變換壓縮原理框圖,5 變換壓縮技術(shù),3）常用圖像變換技術(shù)討論傅立葉變換和余弦變換傅立葉變換及頻譜移中后，其能量集中在中心附近。中心數(shù)據(jù)又稱為直流分量，代表全圖數(shù)值的算術(shù)平均值。其編碼誤差來源有：變換系數(shù)經(jīng)過量化器而引起的量化誤差。常使高頻分量為0，導致圖像模糊。,6 靜止圖像編碼國際標準JPEG,1）JPEG基本系統(tǒng)2）FDCT和IDCT3）量化與反量化4）對量化系數(shù)的處理和組織5）熵編碼6）應(yīng)用舉例,6 靜止圖像

18、編碼國際標準JPEG,1）JPEG基本系統(tǒng)以8*8的圖像塊為基本單位進行編碼；將RGB轉(zhuǎn)換為亮度-色差顏色系統(tǒng)，并重新采樣；,6 靜止圖像編碼國際標準JPEG,YIQ（NTSC制）與YUV（PAL制）Y：指顏色的明視度、亮度、灰度值；I或U：指色調(diào)；Q或V：指飽和度。Y=0.299R+0.587G+0.114BI=0.596R-0.247G-0.322BQ=0.211R-0.523G+0.312BU=0.148R-

19、0.289G+0.473BV=0.615R-0.515G-0.1B,,6 靜止圖像編碼國際標準JPEG,思想：人對亮度比對色彩敏感，在光線不足的情況下，所觀察物體都是黑白的。因此可以對色調(diào)和飽和度做粗略處理。方法：對8*8圖像塊矩陣，Y成分數(shù)據(jù)不變，U每2*2個數(shù)據(jù)求平均，V每2*1個數(shù)據(jù)求平均。稱為YUV421系統(tǒng)。除此,還有YUV422, 411, 420等系統(tǒng).,6 靜止圖像編碼國際標準JPEG,2）FDCT與IDCT思

20、想：人眼對低頻數(shù)據(jù)比對高頻數(shù)據(jù)敏感。根據(jù)8*8的二維DCT定義,6 靜止圖像編碼國際標準JPEG,稱F（0,0）為直流系數(shù)，其他為交流系數(shù)。JPEG標準不規(guī)定FDCT和IDCT的算法。,6 靜止圖像編碼國際標準JPEG,3）量化與反量化思想：將每個DCT系數(shù)除以各自量化步長并四舍五入后取整，得到量化系數(shù)。JPEG系統(tǒng)分別規(guī)定了亮度分量和色度分量的量化表，顯然色度分量相應(yīng)的量化步長比亮度分量大。,6 靜止圖像編碼國際標準J

21、PEG,4）對量化系數(shù)的處理和組織思想：JPEG采用定長和變長相結(jié)合的編碼方法。直流系數(shù)：通常相鄰8*8圖像塊的DC分量很接近，因此JPEG對量化后的直流分量采用無失真DPCM編碼。通常JPEG要保存所需比特數(shù)和實際差值。交流系數(shù)：經(jīng)過量化后，AC分量出現(xiàn)較多的0。JPEG采用對0系數(shù)的行程長度編碼。而對非0值，則要保存所需位數(shù)和實際值。,6 靜止圖像編碼國際標準JPEG,ZIG-ZAG排序：為使連續(xù)的0個數(shù)增多，采用Z形編碼

22、。,6 靜止圖像編碼國際標準JPEG,5）熵編碼對于直流系數(shù)的差值，采用Huffman編碼。JPEG標準為亮度和色度分量分別擬定了Huffman碼表。對于交流0系數(shù)的行長，采用Huffman編碼。同樣JPEG標準為亮度和色度分量分別擬定了Huffman碼表。計算每像素的平均比特稱為碼率。0.25 — 0.50圖像質(zhì)量中等，滿足某些應(yīng)用0.50 — 0.75質(zhì)量好，滿足多數(shù)應(yīng)用0.75 — 1.50極好，滿足大多數(shù)應(yīng)用

23、1.50 — 2.0與原始圖像質(zhì)量一樣,6 靜止圖像編碼國際標準JPEG,6）應(yīng)用舉例Lenna圖像的一個8*8方塊,只舉亮度塊為例.,6 靜止圖像編碼國際標準JPEG,經(jīng)過FDCT后的變換系數(shù)矩陣,6 靜止圖像編碼國際標準JPEG,根據(jù)亮度量化表量化后得到的量化系數(shù)矩陣,6 靜止圖像編碼國際標準JPEG,假設(shè)上一編碼塊的直流量化系數(shù)為77，則直流差值為2。則該圖像塊編碼為,6 靜止圖像編碼國際標準JPEG,反量化,6 靜止圖像編

24、碼國際標準JPEG,反變換,6 靜止圖像編碼國際標準JPEG,編碼比特率與質(zhì)量因子通常在圖像傳輸時要求固定比特率，JPEG通過設(shè)定一個質(zhì)量控制因子Q，在量化時用該因子與量化表中的量化步長相乘作為實際的量化步長。則要求較高比特率時，Q取較小值如0.1；否則取大值。Q與比特流一起傳送給解碼端。,6 靜止圖像編碼國際標準JPEG,,壓縮率9.2,6 靜止圖像編碼國際標準JPEG,,壓縮率18.4,6 靜止圖像編碼國際標準JPEG,,壓縮率

25、51.6,7 圖像壓縮編碼新進展,H.261：用于電視電話和電視會議；碼率128kbps——384kbps；MPEG1：用于數(shù)字存儲媒體（如VCD），碼率為1——1.5Mbps，適合通訊網(wǎng)絡(luò)；MPEG2：用于數(shù)字電視和高清晰度電視（如CCTV Ch 5），碼率為1.5——30Mbps；MPEG4：用于64Kbps以下帶寬的音視編碼，實現(xiàn)基于內(nèi)容的編碼；其他編碼方法：子帶編碼、小波編碼JPEG2000、分形編碼和基于模型的編碼等。

26、,要點總結(jié),掌握基本壓縮技術(shù)的分類和他們各自的基本原理；掌握熵編碼的Huffman和香農(nóng)編碼方法；掌握白塊跳過編碼和行程長度編碼；掌握預(yù)測編碼技術(shù)，及無失真和有失真預(yù)測編碼的區(qū)別；掌握變換編碼技術(shù)；了解JPEG標準的基本步驟，并能解釋之。,上機實習,閱讀有關(guān)Jpeg壓縮標準的相關(guān)文獻，利用Jpeg的源碼實現(xiàn)圖像的壓縮存儲（將bmp格式圖像轉(zhuǎn)成jpeg文件格式）。,習題,1）設(shè)某一幅圖像共有8個灰度級，各灰度級出現(xiàn)概率分別為：