第10章-圖像編碼-無損編碼

第十章圖像編碼10.1圖像編碼概述10.2無損編碼10.3有損編碼10.4JPEG編碼實例10.1圖像編碼概述10.1.1圖像編碼的必要性和可行性

1.必要性圖像的數(shù)據(jù)量非常大。

2.可行性圖像數(shù)據(jù)是高度相關(guān)的，即存在冗余（Redundancy）信息。數(shù)字圖像的冗余主要表現(xiàn)為以下幾種形式：空間冗余、時間冗余、視覺冗余、信息熵冗余、結(jié)構(gòu)冗余和知識冗余。10.1.2圖像編碼方法的分類

有損壓縮和無損壓縮；熵編碼、預(yù)測編碼、變換編碼和混合編碼等。10.2無損壓縮編碼10.2.1Huffman編碼(略)10.2.2香農(nóng)-范諾(Shannon-Fannon)編碼(略)10.2.3行程長度編碼(RunLengthEncoding,RLE)(略)10.2.4LZW編碼1.詞典編碼的兩種思想

（1）尋找正在壓縮的字符序列是否在以前輸入的數(shù)據(jù)中出現(xiàn)過，用已出現(xiàn)過的字符串替代重復(fù)的過程，它的輸出為指針。（2）從輸入的數(shù)據(jù)中創(chuàng)建一個“短語詞典（Dictionaryofthephrases）”，它可以是任意字符的組合。在編碼過程中，當(dāng)遇到詞典中已出現(xiàn)的“短語”，則輸出“短語”的索引號。

LZW編碼屬于第二種編碼思想。LZW編碼（1）相關(guān)術(shù)語字符流（charstream）：被編碼的數(shù)據(jù)序列；字符（character）：字符流中的基本數(shù)據(jù)單元；前綴（prefix）：在一個字符之前的字符序列；綴-符串（string）：前綴＋字符；碼字（codeword）：碼字流中基本數(shù)據(jù)單元，代表詞典中的一串字符；碼字流（codestream）：編碼器輸出的數(shù)據(jù)序列；

詞典（dictionary）：綴-符串表；當(dāng)前前綴（currentprefix）：當(dāng)前正在處理的前綴，用P表示；當(dāng)前字符（currentcharacter）：當(dāng)前前綴之后的字符，用C表示；當(dāng)前碼字（currentcodeword）：譯碼過程中當(dāng)前正在處理的碼字；前綴根（root）：字符流中的所有單個字符串。（2）LZW的編碼算法具體步驟：詞典初始化過程；當(dāng)前字符（C）:=碼字流中第一個字符；判斷綴-符串P+C是否在詞典中；若是，P:=P+C（用C擴展P）；若否：把代表當(dāng)前前綴P的碼字輸出到碼字流；把綴-符串P+C添加到詞典；令P:=C（現(xiàn)在的P僅包含一個字符C）;判斷字符流中是否還有字符要編碼；若是，返回2)；若否：把代表當(dāng)前前綴P的碼字輸出到碼字流；結(jié)束。（3）LZW的編碼實例輸入字符流：ababcbababaaaaaaa…………輸出碼字流：(1)(2)(4)(3)(5)(8)(1)(10)(11)(1)…LZW編碼流程圖初始化詞典P=NULLC:=下一個字符P+C是否在詞典中輸出P的碼字P+C添入詞典P:=C是否結(jié)束結(jié)束P:=P+C是否是否3.LZW譯碼（1）相關(guān)術(shù)語當(dāng)前碼字（currentcodeword）：譯碼過程中當(dāng)前正在處理的碼字，用cw表示；當(dāng)前綴-符串：用string.cw表示；先前碼字（previouscodeword）：用pw表示；先前綴-符串：用string.pw表示。（2）LZW的譯碼算法具體步驟：詞典初始化過程（使之包含所有前綴根）；當(dāng)前前綴P為空；當(dāng)前字符（C）:=字符流中下一個字符；輸出當(dāng)前綴-符串string.cw到字符流；先前碼字pw:=當(dāng)前碼字cw；當(dāng)前碼字cw:=碼字流中下一個碼字；判斷當(dāng)前綴-符串string.cw是否在詞典中；若是：把string.cw輸出到字符流；P:=pw；C:=cw中的第一個字符；P+C添加到詞典中；若否：P:=pw；C:=pw中的第一個字符；P+C輸出到字符流，然后添加到詞典中；判斷解碼是否結(jié)束；若否，返回步驟4)；若是，結(jié)束程序。（3）LZW的譯碼實例輸出碼字流：(1)(2)(4)(3)(5)(8)(1)(10)(11)(1)…輸入字符流：ababcbababaaaaaaa…………10.2.5算術(shù)編碼算術(shù)編碼在圖像數(shù)據(jù)壓縮標準中扮演了重要的角色。在算術(shù)編碼中，消息用0到1之間的實數(shù)進行編碼，算術(shù)編碼用到兩個基本的參數(shù)：符號的概率和它的編碼間隔。符號00011011概率0.10.40.20.3初始編碼間隔[0,0.1)[0.1,0.5)[0.5,0.7)[0.7,1)假設(shè)信源符號為{00,01,10,11}，這些符號的概率分別為{0.1,0.4,0.2,0.3}上面的信息可綜合在下表中。假設(shè)二進制消息序列的輸入為：10001100101101。算術(shù)編碼示意圖StartN=StartB+LeftC×L

EndN=StartB+RightC×L

步驟輸入

符號編碼間隔編碼判決110[0.5,0.7)符號的間隔范圍[0.5,0.7)200[0.5,0.52)[0.5,0.7)間隔的第一個1/10311[0.514,0.52)[0.5,0.52)間隔的最后一個1/10400[0.514,0.5146)[0.514,0.52)間隔的第一個1/10510[0.5143,0.51442)[0.514,0.5146)間隔的第五個1/10開始，二個1/10611[0.514384,0.51442)[0.5143,0.51442)間隔的最后3個1/10701[0.5143836,0.514402)[0.514384,0.51442)間隔的4個1/10，從第1個1/10開始8從[0.5143876,0.514402中選擇一個數(shù)作為輸出：0.5143876步驟間隔譯碼符號譯碼判決1[0.5,0.7)100.51439在間隔[0.5,0.7)2[0.5,0.52)000.51439在間隔[0.5,0.7)的第1個1/103[0.514,0.52)110.51439在間隔[0.5,0.52)的第7個1/104[0.514,0.5146)000.51439在間隔[0.514,0.52)的第1個1/105[0.5143,0.51442)100.51439在間隔[0.514,0.5146)的第5個