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

1、第十章 圖像編碼 第十章 圖像編碼 10.1 圖像編碼概述圖像編碼概述 10.2 無損編碼無損編碼10.3 有損編碼有損編碼 10.4 JPEG編碼實(shí)例編碼實(shí)例第十章 圖像編碼 10.1 10.1 圖像編碼概述圖像編碼概述 10.1.1 圖像編碼的必要性和可行性圖像編碼的必要性和可行性 1. 必要性必要性 圖像的數(shù)據(jù)量非常大。圖像的數(shù)據(jù)量非常大。 2. 可行性可行性 圖像數(shù)據(jù)是高度相關(guān)的，即存在冗余（圖像數(shù)據(jù)是高度相關(guān)的，即存在冗余（Redundancy）信息。）信息。數(shù)字圖像的冗余主要表現(xiàn)為以下幾種形式：空間冗余、時(shí)間冗余、數(shù)字圖像的冗余主要表現(xiàn)為以下幾種形式：空間冗余、時(shí)間冗余、視覺冗余、

2、視覺冗余、 信息熵冗余、結(jié)構(gòu)冗余和知識(shí)冗余。信息熵冗余、結(jié)構(gòu)冗余和知識(shí)冗余。第十章 圖像編碼 10.1.2 圖像編碼方法的分類圖像編碼方法的分類 有損壓縮和無損壓縮；有損壓縮和無損壓縮； 熵編碼、預(yù)測編碼、熵編碼、預(yù)測編碼、 變換編碼和混合編碼等。變換編碼和混合編碼等。第十章 圖像編碼 10.2 10.2 無損壓縮編碼無損壓縮編碼 10.2.1 Huffman編碼編碼 (略略)10.2.2 香農(nóng)香農(nóng)-范諾范諾(Shannon-Fannon)編碼編碼 (略略)10.2.3 行程長度編碼行程長度編碼(Run Length Encoding,RLE) (略略)第十章 圖像編碼 10.2.4 LZW編

3、碼編碼 1. 詞典編碼的兩種思想詞典編碼的兩種思想（1）尋找正在壓縮的字符序列是否在以前輸入的數(shù)據(jù)中出現(xiàn)）尋找正在壓縮的字符序列是否在以前輸入的數(shù)據(jù)中出現(xiàn)過，用已出現(xiàn)過的字符串替代重復(fù)的過程，它的輸出為指針。過，用已出現(xiàn)過的字符串替代重復(fù)的過程，它的輸出為指針。（2）從輸入的數(shù)據(jù)中創(chuàng)建一個(gè)）從輸入的數(shù)據(jù)中創(chuàng)建一個(gè)“短語詞典（短語詞典（Dictionary of the phrases）”，它可以是任意字符的組合。在編碼過程中，當(dāng)，它可以是任意字符的組合。在編碼過程中，當(dāng)遇到詞典中已出現(xiàn)的遇到詞典中已出現(xiàn)的“短語短語”，則輸出，則輸出“短語短語”的索引號(hào)。的索引號(hào)。 LZW編碼屬于第二種編碼思想

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

5、器輸出的數(shù)據(jù)序列；第十章 圖像編碼 詞典（詞典（dictionary）：綴）：綴-符串表；符串表； 當(dāng)前前綴（當(dāng)前前綴（current prefix）：當(dāng)前正在處理的前綴，用）：當(dāng)前正在處理的前綴，用P表表示；示； 當(dāng)前字符（當(dāng)前字符（current character）：當(dāng)前前綴之后的字符，用）：當(dāng)前前綴之后的字符，用C表示；表示； 當(dāng)前碼字（當(dāng)前碼字（current code word）：譯碼過程中當(dāng)前正在處理）：譯碼過程中當(dāng)前正在處理的碼字；的碼字； 前綴根（前綴根（root）：字符流中的所有單個(gè)字符串。）：字符流中的所有單個(gè)字符串。第十章 圖像編碼 （2）LZW的編碼算法的編碼算法具體

6、步驟：具體步驟：詞典初始化過程；詞典初始化過程；當(dāng)前字符（當(dāng)前字符（C）:=碼字流中第一個(gè)字符；碼字流中第一個(gè)字符；判斷綴判斷綴-符串符串P+C是否在詞典中；是否在詞典中；若是，若是，P:=P+C（用（用C擴(kuò)展擴(kuò)展P）；）；若否：若否：把代表當(dāng)前前綴把代表當(dāng)前前綴P的碼字輸出到碼字流；的碼字輸出到碼字流；把綴把綴-符串符串P+C添加到詞典；添加到詞典；1) 令令P:=C（現(xiàn)在的（現(xiàn)在的P僅包含一個(gè)字符僅包含一個(gè)字符C）;第十章 圖像編碼 判斷字符流中是否還有字符要編碼；判斷字符流中是否還有字符要編碼；若是，返回若是，返回2)；若否：若否：把代表當(dāng)前前綴把代表當(dāng)前前綴P的碼字輸出到碼字流；的碼字

7、輸出到碼字流；結(jié)束。結(jié)束。第十章 圖像編碼 （3）LZW的編碼實(shí)例的編碼實(shí)例 輸 入 字 符 流 ：輸 入 字 符 流 ： a b a b c b a b a b a a a a a a a 輸出碼字流：輸出碼字流：(1) (2) (4) (3) (5) (8) (1) (10) (11) (1) 第十章 圖像編碼 LZW編編碼碼流流程程圖圖初始化詞典初始化詞典P=NULLC:=下一個(gè)字符下一個(gè)字符P+C是否在詞典中是否在詞典中輸出輸出P的碼字的碼字P+C添入詞典添入詞典P:=C是否結(jié)束是否結(jié)束結(jié)束結(jié)束P:=P+C是是否否是是否否第十章 圖像編碼 3. LZW譯碼譯碼（1）相關(guān)術(shù)語）相關(guān)術(shù)語

8、當(dāng)前碼字（當(dāng)前碼字（current code word）：譯碼過程中當(dāng)前正在處理）：譯碼過程中當(dāng)前正在處理的碼字，用的碼字，用cw表示；表示； 當(dāng)前綴當(dāng)前綴-符串：用符串：用string.cw表示；表示； 先前碼字（先前碼字（previous code word） ：用：用pw表示；表示； 先前綴先前綴-符串：用符串：用string.pw表示。表示。第十章 圖像編碼 （2）LZW的譯碼算法的譯碼算法具體步驟：具體步驟：詞典初始化過程（使之包含所有前綴根）；當(dāng)前前綴詞典初始化過程（使之包含所有前綴根）；當(dāng)前前綴P為空；為空；當(dāng)前字符（當(dāng)前字符（C）:=字符流中下一個(gè)字符；字符流中下一個(gè)字符；輸出

9、當(dāng)前綴輸出當(dāng)前綴-符串符串string.cw到字符流；到字符流；先前碼字先前碼字pw:=當(dāng)前碼字當(dāng)前碼字cw；當(dāng)前碼字當(dāng)前碼字cw :=碼字流中下一個(gè)碼字；碼字流中下一個(gè)碼字；1) 判斷當(dāng)前綴判斷當(dāng)前綴-符串符串string.cw是否在詞典中；是否在詞典中；第十章 圖像編碼 若是：若是：把把string.cw輸出到字符流；輸出到字符流；P :=pw； C:=cw中的第一個(gè)字符；中的第一個(gè)字符；P+C添加到詞典中；添加到詞典中；若否：若否：P :=pw； C:=pw中的第一個(gè)字符；中的第一個(gè)字符；P+C輸出到字符流，然后添加到詞典中；輸出到字符流，然后添加到詞典中；判斷解碼是否結(jié)束；判斷解碼是否

10、結(jié)束；若否，返回步驟若否，返回步驟4)；若是，結(jié)束程序。若是，結(jié)束程序。第十章 圖像編碼 （3）LZW的譯碼實(shí)例的譯碼實(shí)例輸 出 碼 字 流 ：輸 出 碼 字 流 ： ( 1 ) ( 2) ( 4) ( 3) ( 5) ( 8 ) ( 1 ) ( 1 0 ) ( 11 ) (1) 輸 入 字 符 流 ：輸 入 字 符 流 ： a b a b c b a b a b a a a a a a a 第十章 圖像編碼 10.2.5 算算 術(shù)術(shù) 編編 碼碼 算術(shù)編碼在圖像數(shù)據(jù)壓縮標(biāo)準(zhǔn)中扮演了重要的角算術(shù)編碼在圖像數(shù)據(jù)壓縮標(biāo)準(zhǔn)中扮演了重要的角色。在算術(shù)編碼中，消息用色。在算術(shù)編碼中，消息用0 0到到1 1

11、之間的實(shí)數(shù)進(jìn)行編碼，之間的實(shí)數(shù)進(jìn)行編碼，算術(shù)編碼用到兩個(gè)基本的參數(shù)：符號(hào)的概率和它的編算術(shù)編碼用到兩個(gè)基本的參數(shù)：符號(hào)的概率和它的編碼間隔。碼間隔。第十章 圖像編碼 符號(hào)符號(hào)00000101101011 11 概率概率0.10.10.40.40.20.20.3 0.3 初始編碼間隔初始編碼間隔0, 0.1)0, 0.1)0.1, 0.5)0.1, 0.5)0.5, 0.7)0.5, 0.7)0.7, 1) 0.7, 1) 假設(shè)信源符號(hào)為假設(shè)信源符號(hào)為00, 01, 10, 1100, 01, 10, 11，這些符號(hào)的概率分，這些符號(hào)的概率分別為別為 0.1, 0.4, 0.2, 0.3 0.1

12、, 0.4, 0.2, 0.3 上面的信息可綜合在下表中。上面的信息可綜合在下表中。假設(shè)二進(jìn)制消息序列的輸入為：假設(shè)二進(jìn)制消息序列的輸入為：10 00 11 00 10 11 0110 00 11 00 10 11 01。第十章 圖像編碼 算術(shù)編碼示意圖算術(shù)編碼示意圖StartN=StartB+LeftCL EndN=StartB+RightCL 第十章 圖像編碼 步驟步驟 輸入輸入符號(hào)符號(hào)編碼間隔編碼間隔 編碼判決編碼判決1 110100.5, 0.7)0.5, 0.7)符號(hào)的間隔范圍符號(hào)的間隔范圍0.5, 0.7) 0.5, 0.7) 2 200000.5, 0.52)0.5, 0.52)

13、0.5, 0.7)0.5, 0.7)間隔的第一個(gè)間隔的第一個(gè)1/101/103 311110.514, 0.52)0.514, 0.52)0.5, 0.52)0.5, 0.52)間隔的最后一個(gè)間隔的最后一個(gè)1/101/104 400000.514, 0.5146)0.514, 0.5146)0.514, 0.52)0.514, 0.52)間隔的第一個(gè)間隔的第一個(gè)1/101/105 510100.5143, 0.5143, 0.51442)0.51442)0.514, 0.5146)0.514, 0.5146)間隔的第五個(gè)間隔的第五個(gè)1/101/10開始，二開始，二個(gè)個(gè)1/101/106 611

14、110.514384, 0.514384, 0.51442)0.51442)0.5143, 0.51442)0.5143, 0.51442)間隔的最后間隔的最后3 3個(gè)個(gè)1/101/107 701010.5143836, 0.5143836, 0.514402)0.514402)0.514384, 0.51442)0.514384, 0.51442)間隔的間隔的4 4個(gè)個(gè)1/101/10，從第，從第1 1個(gè)個(gè)1/101/10開始開始8 8從從0.5143876, 0.5144020.5143876, 0.514402中選擇一個(gè)數(shù)作為輸出：中選擇一個(gè)數(shù)作為輸出：0.51438760.514387

15、6第十章 圖像編碼 步步驟驟 間隔間隔譯碼符譯碼符號(hào)號(hào) 譯碼判決譯碼判決 1 10.5, 0.7)0.5, 0.7)10100.514390.51439在間隔在間隔 0.5, 0.7)0.5, 0.7)2 20.5, 0.52)0.5, 0.52)00000.514390.51439在間隔在間隔 0.5, 0.7)0.5, 0.7)的第的第1 1個(gè)個(gè)1/101/103 30.514, 0.52)0.514, 0.52)11110.514390.51439在間隔在間隔0.5, 0.52)0.5, 0.52)的第的第7 7個(gè)個(gè)1/101/104 40.514, 0.5146)0.514, 0.51

16、46)00000.514390.51439在間隔在間隔0.514, 0.52)0.514, 0.52)的第的第1 1個(gè)個(gè)1/101/105 50.5143, 0.51442)0.5143, 0.51442)10100.514390.51439在間隔在間隔0.514, 0.5146)0.514, 0.5146)的第的第5 5個(gè)個(gè)1/101/106 60.514384, 0.514384, 0.51442)0.51442)11110.514390.51439在間隔在間隔0.5143, 0.51442)0.5143, 0.51442)的第的第7 7個(gè)個(gè)1/101/107 70.51439, 0.51

17、439, 0.5143948)0.5143948)01010.514390.51439在間隔在間隔0.51439, 0.5143948)0.51439, 0.5143948)的第的第1 1個(gè)個(gè)1/101/107 7譯碼的消息：譯碼的消息：10 00 11 00 10 11 0110 00 11 00 10 11 01第十章 圖像編碼 10.2.6 無損預(yù)測編碼無損預(yù)測編碼（1）編碼思想）編碼思想 a. 去除像素冗余。去除像素冗余。 b. 認(rèn)為相鄰像素的信息有冗余。當(dāng)前像素值可以用以認(rèn)為相鄰像素的信息有冗余。當(dāng)前像素值可以用以前的像素值來獲得。前的像素值來獲得。 c. 用當(dāng)前像素值用當(dāng)前像素值f

18、n ，通過預(yù)測器得到一個(gè)預(yù)測值，通過預(yù)測器得到一個(gè)預(yù)測值 fn，對(duì)當(dāng)前值和預(yù)測值求差，對(duì)差編碼，作為壓縮數(shù)據(jù)流對(duì)當(dāng)前值和預(yù)測值求差，對(duì)差編碼，作為壓縮數(shù)據(jù)流中的下一個(gè)元素。由于差比原數(shù)據(jù)要小，因而編碼要中的下一個(gè)元素。由于差比原數(shù)據(jù)要小，因而編碼要小，可用變長編碼。大多數(shù)情況下，小，可用變長編碼。大多數(shù)情況下， fn的預(yù)測是通過的預(yù)測是通過m個(gè)以前像素的線性組合來生成的。個(gè)以前像素的線性組合來生成的。第十章 圖像編碼 即：即：m fn = roundifn-ii=1在一維線性在一維線性(行預(yù)測行預(yù)測)預(yù)測編碼中，預(yù)測器為：預(yù)測編碼中，預(yù)測器為： m fn(x,y) = roundif(x, y

19、-i) i=1round為取最近整數(shù)，為取最近整數(shù)， i為預(yù)測系數(shù)為預(yù)測系數(shù)(可為可為1/m)，y是是行變量。行變量。d. 前前m個(gè)像素不能用此法編碼，可用哈夫曼編碼個(gè)像素不能用此法編碼，可用哈夫曼編碼第十章 圖像編碼 舉例：舉例： m fn = roundifn-i i=1F = 154,159,151,149,139,121,112,109,129m = 2 = 1/2預(yù)測值預(yù)測值 f2 = 1/2 * (154 + 159) 156 e2 = 151 156 = -5 f3 = 1/2 * (159 + 151) = 155 e3 = 149 155 = -6 f4 = 1/2 * (151 + 149) = 150 e4 = 139 150 = -11 f5 = 1/2 * (149 + 139) = 144 e5 = 121 144 = -23 f6 = 1/2 * (139 + 121) = 130 e6 = 112 130 = -18 f7 = 1/2 * (121 + 112) 116 e6 = 109 116 = -