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

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

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

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

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

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

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

7、輸出到碼字流；結束。結束。第十章 圖像編碼 （3）LZW的編碼實例的編碼實例 輸 入 字 符 流 ：輸 入 字 符 流 ： 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:=下一個字符下一個字符P+C是否在詞典中是否在詞典中輸出輸出P的碼字的碼字P+C添入詞典添入詞典P:=C是否結束是否結束結束結束P:=P+C是是否否是是否否第十章 圖像編碼 3. LZW譯碼譯碼（1）相關術語）相關術語

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

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

10、結束；若否，返回步驟若否，返回步驟4)；若是，結束程序。若是，結束程序。第十章 圖像編碼 （3）LZW的譯碼實例的譯碼實例輸 出 碼 字 流 ：輸 出 碼 字 流 ： ( 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ù)據壓縮標準中扮演了重要的角色。在算術編碼中，消息用色。在算術編碼中，消息用0 0到到1 1

11、之間的實數(shù)進行編碼，之間的實數(shù)進行編碼，算術編碼用到兩個基本的參數(shù)：符號的概率和它的編算術編碼用到兩個基本的參數(shù)：符號的概率和它的編碼間隔。碼間隔。第十章 圖像編碼 符號符號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) 假設信源符號為假設信源符號為00, 01, 10, 1100, 01, 10, 11，這些符號的概率分，這些符號的概率分別為別為 0.1, 0.4, 0.2, 0.3 0.1

12、, 0.4, 0.2, 0.3 上面的信息可綜合在下表中。上面的信息可綜合在下表中。假設二進制消息序列的輸入為：假設二進制消息序列的輸入為：10 00 11 00 10 11 0110 00 11 00 10 11 01。第十章 圖像編碼 算術編碼示意圖算術編碼示意圖StartN=StartB+LeftCL EndN=StartB+RightCL 第十章 圖像編碼 步驟步驟 輸入輸入符號符號編碼間隔編碼間隔 編碼判決編碼判決1 110100.5, 0.7)0.5, 0.7)符號的間隔范圍符號的間隔范圍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)間隔的第一個間隔的第一個1/101/103 311110.514, 0.52)0.514, 0.52)0.5, 0.52)0.5, 0.52)間隔的最后一個間隔的最后一個1/101/104 400000.514, 0.5146)0.514, 0.5146)0.514, 0.52)0.514, 0.52)間隔的第一個間隔的第一個1/101/105 510100.5143, 0.5143, 0.51442)0.51442)0.514, 0.5146)0.514, 0.5146)間隔的第五個間隔的第五個1/101/10開始，二開始，二個個1/101/106 611

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

15、6第十章 圖像編碼 步步驟驟 間隔間隔譯碼符譯碼符號號 譯碼判決譯碼判決 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個個1/101/103 30.514, 0.52)0.514, 0.52)11110.514390.51439在間隔在間隔0.5, 0.52)0.5, 0.52)的第的第7 7個個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個個1/101/105 50.5143, 0.51442)0.5143, 0.51442)10100.514390.51439在間隔在間隔0.514, 0.5146)0.514, 0.5146)的第的第5 5個個1/101/106 60.514384, 0.514384, 0.51442)0.51442)11110.514390.51439在間隔在間隔0.5143, 0.51442)0.5143, 0.51442)的第的第7 7個個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個個1/101/107 7譯碼的消息：譯碼的消息：10 00 11 00 10 11 0110 00 11 00 10 11 01第十章 圖像編碼 10.2.6 無損預測編碼無損預測編碼（1）編碼思想）編碼思想 a. 去除像素冗余。去除像素冗余。 b. 認為相鄰像素的信息有冗余。當前像素值可以用以認為相鄰像素的信息有冗余。當前像素值可以用以前的像素值來獲得。前的像素值來獲得。 c. 用當前像素值用當前像素值f

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

19、-i) i=1round為取最近整數(shù)，為取最近整數(shù)， i為預測系數(shù)為預測系數(shù)(可為可為1/m)，y是是行變量。行變量。d. 前前m個像素不能用此法編碼，可用哈夫曼編碼個像素不能用此法編碼，可用哈夫曼編碼第十章 圖像編碼 舉例：舉例： m fn = roundifn-i i=1F = 154,159,151,149,139,121,112,109,129m = 2 = 1/2預測值預測值 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 = -