圖像的編碼技術(shù)

1、第九章第九章 圖像編碼與圖像通信圖像編碼與圖像通信數(shù)字圖像處理數(shù)字圖像處理安徽建筑安徽建筑 大大 學(xué)學(xué)圖像編碼的研究背景圖像編碼的研究背景 通信方式改變帶來的需求通信方式改變帶來的需求n信息傳輸方式發(fā)生了很大的改變信息傳輸方式發(fā)生了很大的改變n通信方式的改變通信方式的改變文字文字+ +語音語音圖像圖像+ +文字文字+ +語音語音n通信對(duì)象的改變通信對(duì)象的改變?nèi)伺c人人與人人與機(jī)器，機(jī)器與機(jī)器人與機(jī)器，機(jī)器與機(jī)器n由通信方式和通信對(duì)象的改變帶來的最大問由通信方式和通信對(duì)象的改變帶來的最大問題是：題是：傳輸帶寬、速度、存儲(chǔ)器容量的限制。傳輸帶寬、速度、存儲(chǔ)器容量的限制。n帶來的難題，也創(chuàng)造了機(jī)會(huì)：帶

2、來的難題，也創(chuàng)造了機(jī)會(huì)：如何用軟件的手段來解決硬件上的物理極限。如何用軟件的手段來解決硬件上的物理極限。圖像編碼的研究背景圖像編碼的研究背景 通信方式改變帶來的需求通信方式改變帶來的需求圖像編碼的研究背景圖像編碼的研究背景 海量數(shù)據(jù)帶來的需求海量數(shù)據(jù)帶來的需求n數(shù)字圖像數(shù)據(jù)量的龐大。數(shù)字圖像數(shù)據(jù)量的龐大。n圖像的傳輸與存儲(chǔ)，必須解決圖像數(shù)圖像的傳輸與存儲(chǔ)，必須解決圖像數(shù)據(jù)的壓縮問題。據(jù)的壓縮問題。彩色視頻數(shù)據(jù)量分析彩色視頻數(shù)據(jù)量分析n對(duì)于電視畫面的分辨率對(duì)于電視畫面的分辨率640480的彩色圖的彩色圖像像(像素分辨率為像素分辨率為24bit)，每秒，每秒30幀，則一幀，則一秒鐘的數(shù)據(jù)量為：秒鐘

3、的數(shù)據(jù)量為： 6404802430=221.12M n播放時(shí)，需要播放時(shí)，需要221Mbps的通信回路。的通信回路。 彩色視頻數(shù)據(jù)量分析彩色視頻數(shù)據(jù)量分析n實(shí)時(shí)傳輸：實(shí)時(shí)傳輸： 在在10M帶寬網(wǎng)上實(shí)時(shí)傳輸?shù)脑?，需要壓縮到原來數(shù)帶寬網(wǎng)上實(shí)時(shí)傳輸?shù)脑?，需要壓縮到原來數(shù)據(jù)量的據(jù)量的0.045， 即即0.36bit/pixel。n存儲(chǔ)：存儲(chǔ)： （按（按1張光盤可存張光盤可存640M計(jì)算）計(jì)算） 如果不進(jìn)行壓縮，如果不進(jìn)行壓縮，1張張CD則僅可以存放則僅可以存放2.89秒的數(shù)秒的數(shù)據(jù)。存據(jù)。存2小時(shí)的信息則需要壓縮到原來數(shù)據(jù)量的小時(shí)的信息則需要壓縮到原來數(shù)據(jù)量的0.0004，即：，即：0.003bit/

4、pixel。傳真數(shù)據(jù)量分析傳真數(shù)據(jù)量分析n如果只傳送如果只傳送2值圖像，以值圖像，以200dpi的分辨率傳的分辨率傳輸，一張輸，一張A4稿紙的數(shù)據(jù)量為：稿紙的數(shù)據(jù)量為： 165423371=3888768bit =3900Kn按按14.4K的電話線傳輸速率，需要傳送的時(shí)的電話線傳輸速率，需要傳送的時(shí)間是：間是：270秒（秒（4.5分）分）圖像通信系統(tǒng)模型圖像通信系統(tǒng)模型圖像信息源圖像信息源圖像預(yù)處理圖像預(yù)處理圖像信源圖像信源編碼編碼信道編信道編碼碼調(diào)制調(diào)制信道傳輸信道傳輸解調(diào)解調(diào)信道解碼信道解碼圖像信源圖像信源解碼解碼顯示圖像顯示圖像9.1基本概念基本概念9.2圖像壓縮原理圖像壓縮原理9.3圖

5、像的壓縮編碼圖像的壓縮編碼第九章第九章 圖像編碼與圖像通信圖像編碼與圖像通信一、圖像編碼壓縮的必要性一、圖像編碼壓縮的必要性 海量圖像數(shù)據(jù)的存儲(chǔ)和處理、通信的是現(xiàn)代信海量圖像數(shù)據(jù)的存儲(chǔ)和處理、通信的是現(xiàn)代信 息傳輸?shù)碾y點(diǎn)。息傳輸?shù)碾y點(diǎn)。二、圖像編碼壓縮的可能性二、圖像編碼壓縮的可能性 組成圖像的各像素之間，在行列方向存在一定的組成圖像的各像素之間，在行列方向存在一定的相關(guān)性。從信息論角度來看，描述圖像信源數(shù)據(jù)相關(guān)性。從信息論角度來看，描述圖像信源數(shù)據(jù)是由有效信息量和冗余量?jī)蓚€(gè)部分組成，可以在是由有效信息量和冗余量?jī)蓚€(gè)部分組成，可以在保持圖像原有信息量的同時(shí)，去除冗余量能夠節(jié)保持圖像原有信息量的

6、同時(shí)，去除冗余量能夠節(jié)省存儲(chǔ)和傳輸中的開銷，同時(shí)又不損害圖像信源省存儲(chǔ)和傳輸中的開銷，同時(shí)又不損害圖像信源的有效信息。的有效信息。 9.1基本概念基本概念數(shù)據(jù)的冗余數(shù)據(jù)的冗余l(xiāng)你的大學(xué)同學(xué)，李某某，將于明天晚上你的大學(xué)同學(xué)，李某某，將于明天晚上6點(diǎn)零點(diǎn)零5分在合肥的安徽分在合肥的安徽建筑大學(xué)北區(qū)大門口等你。建筑大學(xué)北區(qū)大門口等你。 (362+5=77個(gè)半角字符個(gè)半角字符)l你的同學(xué)將于明天晚上你的同學(xué)將于明天晚上6點(diǎn)零點(diǎn)零5分在安徽建筑大學(xué)北區(qū)大門口等分在安徽建筑大學(xué)北區(qū)大門口等你你 (292+2=60個(gè)半角字符）個(gè)半角字符）l李某某將于明晚李某某將于明晚6點(diǎn)在安建大北區(qū)大門口等你點(diǎn)在安建大北

7、區(qū)大門口等你 (182+1=37個(gè)半角字符）個(gè)半角字符）結(jié)論：只要接收端不會(huì)產(chǎn)生誤解，就可以減少承載信息結(jié)論：只要接收端不會(huì)產(chǎn)生誤解，就可以減少承載信息的數(shù)據(jù)量。的數(shù)據(jù)量。數(shù)據(jù)冗余數(shù)據(jù)冗余 描述上的冗余描述上的冗余n描述方式：描述方式： 1）這是一幅）這是一幅22的圖像，圖像的第一個(gè)像素是的圖像，圖像的第一個(gè)像素是綠的，第二個(gè)像素是綠的，第三個(gè)像素是綠的，綠的，第二個(gè)像素是綠的，第三個(gè)像素是綠的，第四個(gè)像素是綠的。第四個(gè)像素是綠的。 2）這是一幅）這是一幅22的圖像，整幅圖都是綠色的。的圖像，整幅圖都是綠色的。 3）一幅綠色）一幅綠色22的圖像。的圖像。整理圖像的描述方法可以達(dá)到壓縮的目的。整

8、理圖像的描述方法可以達(dá)到壓縮的目的。 1 2 3 4圖像冗余圖像冗余 數(shù)據(jù)冗余的壓縮數(shù)據(jù)冗余的壓縮 n圖像冗余無損壓縮的原理圖像冗余無損壓縮的原理RGBRGBRGBRGBRGBRGBRGBRGBRGBRGBRGBRGBRGBRGBRGBRGB16RGB從從1638=284bits壓縮為：壓縮為：(1+3) 8=32bits壓縮比為：壓縮比為：12：1圖像冗余圖像冗余 數(shù)據(jù)冗余的壓縮數(shù)據(jù)冗余的壓縮n圖像冗余有損壓縮的原理圖像冗余有損壓縮的原理363534 3434343432 3434333730 3434343434 3434343534 343134 34 34 34 3434 34 34

9、34 3434 34 34 34 3434 34 34 34 3434 34 34 34 342534圖像冗余圖像冗余 實(shí)際圖像中的數(shù)據(jù)冗余實(shí)際圖像中的數(shù)據(jù)冗余 實(shí)際圖像中冗余信息的表現(xiàn)實(shí)際圖像中冗余信息的表現(xiàn)圖像冗余圖像冗余 視覺冗余的壓縮視覺冗余的壓縮n圖像的視覺冗余圖像的視覺冗余 （彩色）（彩色） R G B248882222=242 =16,777,216(248,27,4)(251,32,15)(248,27,4)(248,27,4)9.2圖像壓縮原理圖像壓縮原理n由于一幅圖像存在數(shù)據(jù)冗余和主觀視覺冗余，由于一幅圖像存在數(shù)據(jù)冗余和主觀視覺冗余，所以壓縮方式可以從這兩方面著手開展。所以

10、壓縮方式可以從這兩方面著手開展。n改變圖像信息的描述方式，以壓縮掉圖像中改變圖像信息的描述方式，以壓縮掉圖像中的數(shù)據(jù)冗余。的數(shù)據(jù)冗余。n忽略一些視覺不太明顯的微小差異，以壓縮忽略一些視覺不太明顯的微小差異，以壓縮掉圖像中的視覺冗余。掉圖像中的視覺冗余。9.3圖像的壓縮編碼圖像的壓縮編碼n第一代壓縮編碼第一代壓縮編碼八十年代以前，主要是根據(jù)傳統(tǒng)的信源編碼方法。八十年代以前，主要是根據(jù)傳統(tǒng)的信源編碼方法。n第二代壓縮編碼第二代壓縮編碼 八十年代以后，突破信源編碼理論，結(jié)合分形、八十年代以后，突破信源編碼理論，結(jié)合分形、模型基、神經(jīng)網(wǎng)絡(luò)、小波變換等數(shù)學(xué)工具，充分模型基、神經(jīng)網(wǎng)絡(luò)、小波變換等數(shù)學(xué)工具，

11、充分利用視覺系統(tǒng)生理心理特性和圖像信源的各種特利用視覺系統(tǒng)生理心理特性和圖像信源的各種特性。性。9.3圖像的壓縮編碼圖像的壓縮編碼像素編碼像素編碼變換編碼變換編碼預(yù)測(cè)編碼預(yù)測(cè)編碼位平面編碼位平面編碼增量調(diào)制增量調(diào)制熵編碼熵編碼算術(shù)編碼算術(shù)編碼DCT變換變換DPCM調(diào)制調(diào)制第一代壓縮編碼第一代壓縮編碼其他編碼其他編碼行程編碼行程編碼9.3圖像的壓縮編碼圖像的壓縮編碼子帶編碼子帶編碼模型編碼模型編碼分層編碼分層編碼分形編碼分形編碼第二代壓縮編碼第二代壓縮編碼H.261標(biāo)準(zhǔn)標(biāo)準(zhǔn)(ITU-T,可視電話可視電話 ,視頻會(huì)議視頻會(huì)議)H.263、 H.26L標(biāo)準(zhǔn)標(biāo)準(zhǔn)H.264MPEG-1標(biāo)準(zhǔn)標(biāo)準(zhǔn)(視頻會(huì)議

12、、視頻會(huì)議、VCD)MPEG-2標(biāo)準(zhǔn)標(biāo)準(zhǔn)(通用活動(dòng)圖像及其編碼通用活動(dòng)圖像及其編碼)MPEG-4標(biāo)準(zhǔn)標(biāo)準(zhǔn)(通用活動(dòng)圖像及其編碼通用活動(dòng)圖像及其編碼)AVS(audio video coding standard)一、行程編碼一、行程編碼(RLE編碼編碼)n行程編碼是一種最簡(jiǎn)單的，在某些場(chǎng)合是非行程編碼是一種最簡(jiǎn)單的，在某些場(chǎng)合是非常有效的一種無損壓縮編碼方法。常有效的一種無損壓縮編碼方法。n雖然這種編碼方式的應(yīng)用范圍非常有限，但雖然這種編碼方式的應(yīng)用范圍非常有限，但是因?yàn)檫@種方法中所體現(xiàn)出的編碼設(shè)計(jì)思想是因?yàn)檫@種方法中所體現(xiàn)出的編碼設(shè)計(jì)思想非常明確，所以在圖像編碼方法中都會(huì)將其非常明確，所以在

13、圖像編碼方法中都會(huì)將其作為一種典型的方法來介紹。作為一種典型的方法來介紹。 一、行程編碼一、行程編碼n通過改變圖像的描述方式，來實(shí)現(xiàn)圖像的壓通過改變圖像的描述方式，來實(shí)現(xiàn)圖像的壓縮?？s。n將一行中灰度值相同的相鄰像素，用一個(gè)計(jì)將一行中灰度值相同的相鄰像素，用一個(gè)計(jì)數(shù)值和該灰度值來代替。數(shù)值和該灰度值來代替。一、行程編碼一、行程編碼n 例：例： aaaa bbb cc d eeeee fffffff 4 3 2 1 5 7 (共共228=176 bits) 4a 3b 2c 1d 5e 7f (共共12 8=96 bits)壓縮比為：壓縮比為：176：96=1.83:1一、行程編碼一、行程編碼傳

14、真中的應(yīng)用方法傳真中的應(yīng)用方法o傳真圖像中一般都是白色比較多，而黑傳真圖像中一般都是白色比較多，而黑色相對(duì)比較少。常常會(huì)出現(xiàn)如下的情況：色相對(duì)比較少。常常會(huì)出現(xiàn)如下的情況： 500W 3b 470w 12b 4w 3b 3000w 上面行程編碼所需用的字節(jié)數(shù)上面行程編碼所需用的字節(jié)數(shù)(最高最高)為：為： 204830004096 所以計(jì)數(shù)值須用所以計(jì)數(shù)值須用12 bit來表示來表示 采用行程編碼采用行程編碼對(duì)于：對(duì)于： 500W 3b 470w 12b 4w 3b 3000w 編碼為：編碼為： 500, 3, 570, 12, 4, 3, 3000 編碼位數(shù)為編碼位數(shù)為:12, 12, 12,

15、 12, 12,12,12需要的數(shù)據(jù)量為：需要的數(shù)據(jù)量為： 127=84 bit 一般情況下，只傳輸計(jì)數(shù)值即可。一般情況下，只傳輸計(jì)數(shù)值即可。壓縮比為：壓縮比為： 176：84=2.1：1行程編碼行程編碼傳真中的應(yīng)用方法傳真中的應(yīng)用方法n根據(jù)傳真件的特點(diǎn)，對(duì)其進(jìn)行改進(jìn)。根據(jù)傳真件的特點(diǎn)，對(duì)其進(jìn)行改進(jìn)。n已知白色多黑色少，可對(duì)白色和黑色的已知白色多黑色少，可對(duì)白色和黑色的計(jì)數(shù)值采用不同的位數(shù)。計(jì)數(shù)值采用不同的位數(shù)。n上例，重新定義：上例，重新定義： 白色：白色：12 bit，黑色：黑色：4 bit 行程編碼行程編碼傳真中的應(yīng)用方法傳真中的應(yīng)用方法編碼為：編碼為： 500,3,570,12,4,3

16、,3000 編碼位數(shù)為編碼位數(shù)為: 12,4,12, 4,12,4,12所需字節(jié)數(shù)為：所需字節(jié)數(shù)為：4 12+3 4=60bit比原來的比原來的RLE方式方式84bit減少了減少了60bit,相當(dāng)于又提高了壓縮比為相當(dāng)于又提高了壓縮比為 84/60=1.4：1 。壓縮比為：壓縮比為： 176：60=2.93：1 二維行程編碼二維行程編碼 基本概念基本概念二維行程編碼要解決的核心問題是二維行程編碼要解決的核心問題是: : 將二維排列的像素，采用某種方式轉(zhuǎn)化成一將二維排列的像素，采用某種方式轉(zhuǎn)化成一維排列的方式。之后按照一維行程編碼方式進(jìn)行維排列的方式。之后按照一維行程編碼方式進(jìn)行編碼。編碼。二維

17、行程編碼二維行程編碼 數(shù)據(jù)排序數(shù)據(jù)排序如下圖所示，是兩種典型的二維行程編碼的排列如下圖所示，是兩種典型的二維行程編碼的排列方式：方式：(a) (b) 二維行程編碼二維行程編碼例題例題例：例：130130130129134133129130130130130129134133130130130130130129132132130130129130130129130130129129127128127129131 129131 130127128127128127128132132125126129129127129133132127125128128126130131131f=數(shù)據(jù)量：數(shù)據(jù)量：6

18、4 8=512(bit)n 如果按照行掃描的順序排列的話，數(shù)據(jù)分布為：如果按照行掃描的順序排列的話，數(shù)據(jù)分布為：130，130，130，129，134，133，129，130；130，130，130，129，134，133，130，130； 130，130，130，129，132，132，130，130；129，130，130，129，130，130，129，129；127，128，127，129，131，129，131，130；127，128，127，128，127，128，132，132；125，126，129，129，127，129，133，132；127，125，128，128，126

19、，130，131，131二維行程編碼二維行程編碼例題例題二維行程編碼二維行程編碼例題例題一維行程編碼后為一維行程編碼后為: :（3，130），（），（1，129），（），（1，134），（），（1，133），（），（1，129），（），（4，130），（），（1，129），（），（1，134），（），（1，133），（），（5，130），（），（1，129），（），（2，132），（），（2，130），（），（1，129），（），（2，130），（），（1，129），（），（2，130），（），（2，129），（），（1，127），（），（1，128），（），（1，127），（），（1，129

20、），（），（1，131），（），（1，129），（），（1，131），（），（1，130），（），（1，127），（），（1，128），（），（1，127），（），（1，128），（），（1，127），（），（1，128），（），（2，132），（），（1，125），（），（1，126），（），（2，129），（），（1，127），（），（1，129），（），（1，133），（），（1，132），（），（1，127），（），（1，125），（），（2，128），（），（1，126），（），（1，130），（），（2，131）壓縮比為：壓縮比為：512：506=1.01:1數(shù)據(jù)量為數(shù)據(jù)量為:46

21、 （3+8）=506(bit)二維行程編碼二維行程編碼例題例題如果按照列掃描的順序排列的話，數(shù)據(jù)分布為：如果按照列掃描的順序排列的話，數(shù)據(jù)分布為：130，130，130，129，127，127，125，127；130，130，130，130，128，128，126，125；130，130，130，130，127，127，129，128；129，129，129，129，129，128，129，128；134，134，132，130，131，127，127，126；133，133，132，130，129，128，129，130； 129，130，130，129，131，132，133，131；13

22、0，130，130，129，130，132，132，131二維行程編碼二維行程編碼 例題例題一維行程編碼為一維行程編碼為: :壓縮比為：壓縮比為：512：462=1.11:1（3，130），（），（1，129），（），（2，127），（），（1，125），（），（1，127），（），（4， 130），（），（2，128），（），（1，126），（），（1，125），（），（4，130），（），（2，127），（），（1，129），（），（1，128），（），（5，129），（），（1，128），（），（1，129），（），（1，128），（），（2， 134），（），（1，132），（），（1

23、，130），（），（1，131），（），（2，127），（），（1，126），（），（2，133），（），（1，132），（），（1，130），（），（1，129），（），（1，128），（），（1，129），（），（1，130），）， （1，129），（），（2，130），（），（1，129），（），（1，131），（），（1，132），（），（1，133），（），（1，131），（），（3，130），（），（1，129），（），（1，130），（），（2，132），（），（1，131）數(shù)據(jù)量為數(shù)據(jù)量為:42 （3+8）=462(bit)二維行程編碼二維行程編碼例題例題如果如果按照按照Z字掃

24、描字掃描的順序排列的話，數(shù)據(jù)分布為：的順序排列的話，數(shù)據(jù)分布為：130，130，130，129，127，127，125，127；130，130，130，130，128，128，126，125；130，130，130，130，127，127，129，128；129，129，129，129，129，128，129，128；134，134，132，130，131，127，127，126；133，133，132，130，129，128，129，130； 129，130，130，129，131，132，133，131；130，130，130，129，130，132，132，131二維行程編碼二維行程編碼

25、 例題例題一維行程編碼為一維行程編碼為: :壓縮比為：壓縮比為：512：462=1.11:1（9，130），（），（1，129），（），（2，130），（），（4，129），（），（2，134），（），（1， 132），（），（1，130），（），（1，131），（），（1，129），（），（1，127），（），（1，128），（），（2，127），（），（1，128），（），（1，127），（），（1，128），（），（1，127），（），（1，128），（），（1， 129），（），（1，130），（），（1，132），（），（2，133），（），（1，129），（），（2，130），（）

26、，（1，129），（），（1，131），（），（1，132），（），（1，133），（），（1，129），（），（1，127），（），（2，129），）， （1，126），（），（1，125），（），（1，127），（），（1，125），（），（2，128），（），（1，126），（），（1，130），（），（2，131），（），（2，132），（），（1，130），（），（1，129），（），（3，130）數(shù)據(jù)量為數(shù)據(jù)量為:42 （3+8）=462(bit)二、二、Huffman 編碼（熵編碼）編碼（熵編碼）n行程編碼要獲得好的壓縮率的前提，有比較長(zhǎng)行程編碼要獲得好的壓縮率的前提，有比較長(zhǎng)的

27、相鄰像素的值是相同的。的相鄰像素的值是相同的。n熵是指數(shù)據(jù)中承載的信息量。熵是指數(shù)據(jù)中承載的信息量。n熵編碼是指在完全不損失信息量前提下最小數(shù)熵編碼是指在完全不損失信息量前提下最小數(shù)據(jù)量的編碼。據(jù)量的編碼。二、二、Huffman編碼編碼n為了達(dá)到大的壓縮率，將在圖像中出現(xiàn)頻為了達(dá)到大的壓縮率，將在圖像中出現(xiàn)頻度大的像素值，給一個(gè)比較短的編碼，將度大的像素值，給一個(gè)比較短的編碼，將出現(xiàn)頻度小的像素值，給一個(gè)比較長(zhǎng)的編出現(xiàn)頻度小的像素值，給一個(gè)比較長(zhǎng)的編碼。碼。二、二、Huffman編碼編碼n例：例： aaaa bbb cc d eeeee fffffff 4 3 2 1 5 7n如果不進(jìn)行特殊的

28、編碼，按照?qǐng)D像像素的描述，如果不進(jìn)行特殊的編碼，按照?qǐng)D像像素的描述，需要的數(shù)據(jù)量為：需要的數(shù)據(jù)量為： 22 8=176 bits 二、二、Huffman編碼編碼 基本原理基本原理 aaaa bbb cc d eeeee fffffff 4 3 2 1 5 7n按照熵編碼的原理進(jìn)行編碼：按照熵編碼的原理進(jìn)行編碼： f=0 e=10 a=101 b=1111 c=11100 d=11101n編碼規(guī)則是長(zhǎng)短不一的異字頭碼，具有碼字編碼規(guī)則是長(zhǎng)短不一的異字頭碼，具有碼字唯一可譯性，能實(shí)時(shí)進(jìn)行解碼。唯一可譯性，能實(shí)時(shí)進(jìn)行解碼。(一一) 基本原理基本原理 由：由：f=0 e=10 a=101 b=1111

29、 c=11100 d=11101 aaaa bbb cc d eeeee fffffff 10110110110111111111111111100111001110110101010100000000 數(shù)據(jù)量數(shù)據(jù)量：7 1+5 2+4 3+3 4+2 5+1 5=56 bit 壓縮比為：壓縮比為：176：56=3.14：1(二二)編碼基本步驟編碼基本步驟 n首先求出圖像中灰度分布的灰度直方圖；首先求出圖像中灰度分布的灰度直方圖；n根據(jù)該直方圖，對(duì)其按照分布概率從小到大根據(jù)該直方圖，對(duì)其按照分布概率從小到大的順序進(jìn)行排列；的順序進(jìn)行排列；n每一次從中選擇出兩個(gè)概率為最小的節(jié)點(diǎn)相每一次從中選擇出

30、兩個(gè)概率為最小的節(jié)點(diǎn)相加，形成一個(gè)新的節(jié)點(diǎn)，構(gòu)造一個(gè)稱為加，形成一個(gè)新的節(jié)點(diǎn)，構(gòu)造一個(gè)稱為“Huffman樹樹”的二叉樹；的二叉樹；n對(duì)此二叉樹進(jìn)行編碼，得到對(duì)此二叉樹進(jìn)行編碼，得到Huffman編碼碼字。編碼碼字。( (三三) )實(shí)例實(shí)例 數(shù)據(jù)序列數(shù)據(jù)序列 aaaa bbb cc d eeeee fffffff 其概率分布為：其概率分布為： a:4/22 b:3/22 c:2/22 d:1/22 e:5/22 f:7/22 概率大小的排序?yàn)椋焊怕蚀笮〉呐判驗(yàn)椋?d c b a e f 1/22 2/22 3/22 4/22 5/22 7/22例例cbafe7/225/224/222/2210

31、f=11 e=01 a=00 b=101 c=1001 d=1000d1/223/226/2222/2213/229/223/2210101010 f=11 e=01 a=00 b=101 c=1001 d=1000經(jīng)經(jīng)Huffman編碼后的數(shù)據(jù)為：編碼后的數(shù)據(jù)為：1010101010001001001000100010000111111111101010101010101共共 7 2+5 2+4 2+3 3+2 4+1 4=53 bit壓縮比為壓縮比為176：53=3.32:1(四四)Huffman編碼在圖像壓縮中的實(shí)際應(yīng)用編碼在圖像壓縮中的實(shí)際應(yīng)用n對(duì)一幅圖像進(jìn)行編碼時(shí)，如果圖像的大小大對(duì)

32、一幅圖像進(jìn)行編碼時(shí)，如果圖像的大小大于于256時(shí)，這幅圖像的不同的碼字就有可能時(shí)，這幅圖像的不同的碼字就有可能是很大，例如極限為是很大，例如極限為256個(gè)不同的碼字。個(gè)不同的碼字。 n如果采用全局如果采用全局Huffman編碼則壓縮效率不高。編碼則壓縮效率不高。甚至有可能與原來的等長(zhǎng)編碼的數(shù)據(jù)量相同。甚至有可能與原來的等長(zhǎng)編碼的數(shù)據(jù)量相同。 (四四) Huffman編碼在圖像壓縮中的實(shí)際應(yīng)用編碼在圖像壓縮中的實(shí)際應(yīng)用 常用的且有效的方法是：常用的且有效的方法是：o將圖像分割成若干的小塊，對(duì)每塊進(jìn)行獨(dú)立將圖像分割成若干的小塊，對(duì)每塊進(jìn)行獨(dú)立的的Huffman編碼。例如：分成編碼。例如：分成88

33、的子塊，的子塊，可以大大降低不同灰度值的個(gè)數(shù)（最多是可以大大降低不同灰度值的個(gè)數(shù)（最多是64而不是而不是256）。）。(四四) Huffman編碼在圖像壓縮中的實(shí)際應(yīng)用編碼在圖像壓縮中的實(shí)際應(yīng)用8 8分塊的編分塊的編碼壓縮比為碼壓縮比為2.12:116 16分塊的編分塊的編碼壓縮比為碼壓縮比為1.64:1全圖的編碼壓全圖的編碼壓縮比為縮比為1.09:1三、預(yù)測(cè)編碼三、預(yù)測(cè)編碼 (DPCM)o利用圖像信號(hào)的空間或時(shí)間相關(guān)性，用已利用圖像信號(hào)的空間或時(shí)間相關(guān)性，用已傳輸?shù)南袼貙?duì)當(dāng)前的像素進(jìn)行預(yù)測(cè)，然后傳輸?shù)南袼貙?duì)當(dāng)前的像素進(jìn)行預(yù)測(cè)，然后對(duì)預(yù)測(cè)值與真實(shí)值的差對(duì)預(yù)測(cè)值與真實(shí)值的差( (預(yù)測(cè)誤差預(yù)測(cè)誤差

34、) )進(jìn)行編進(jìn)行編碼處理和傳輸。碼處理和傳輸。三、預(yù)測(cè)編碼三、預(yù)測(cè)編碼-+f (m,n)e(m,n)e(m,n)輸入輸入 f (m,n)量化器量化器Q預(yù)測(cè)器預(yù)測(cè)器),(nmf輸出輸出 f (m,n)反量化器反量化器IQ預(yù)測(cè)器預(yù)測(cè)器e(m,n),(nmf編碼器輸出預(yù)測(cè)編碼器輸出預(yù)測(cè)誤差的量化值誤差的量化值三、預(yù)測(cè)編碼三、預(yù)測(cè)編碼o預(yù)測(cè)器的設(shè)計(jì)主要是確定預(yù)測(cè)器的階數(shù)預(yù)測(cè)器的設(shè)計(jì)主要是確定預(yù)測(cè)器的階數(shù)N，以及各個(gè)預(yù)測(cè)系數(shù)。以及各個(gè)預(yù)測(cè)系數(shù)。 o階數(shù)階數(shù)N是指預(yù)測(cè)器的輸出是由是指預(yù)測(cè)器的輸出是由N個(gè)輸入數(shù)據(jù)個(gè)輸入數(shù)據(jù)的線性組合而成。的線性組合而成。 三、預(yù)測(cè)編碼三、預(yù)測(cè)編碼X0X4X2X3X1a0a1

35、a2a34XX0X1X2X3根據(jù)圖像信號(hào)的統(tǒng)計(jì)特性，可以通過一組合適的預(yù)測(cè)系數(shù)，使根據(jù)圖像信號(hào)的統(tǒng)計(jì)特性，可以通過一組合適的預(yù)測(cè)系數(shù)，使得預(yù)測(cè)誤差得預(yù)測(cè)誤差e(m,n)的分布大部分集中在的分布大部分集中在0附近，經(jīng)過非均勻量附近，經(jīng)過非均勻量化，減少量化層，壓縮圖像數(shù)據(jù)。化，減少量化層，壓縮圖像數(shù)據(jù)。 安徽建筑工業(yè)學(xué)院安徽建筑工業(yè)學(xué)院最優(yōu)線性預(yù)測(cè)最優(yōu)線性預(yù)測(cè)o假定當(dāng)前待編碼的像素為假定當(dāng)前待編碼的像素為XN，其前面，其前面N個(gè)個(gè)已編像素分別為已編像素分別為X0，X1，.，XN-1，若用，若用它們對(duì)它們對(duì)XN進(jìn)行預(yù)測(cè)，進(jìn)行預(yù)測(cè)，ai /i=0,1,.N-1表表示預(yù)測(cè)系數(shù)，則可以寫成示預(yù)測(cè)系數(shù)，則

36、可以寫成 111100.=NNNXaXaXaX預(yù)測(cè)誤差為：預(yù)測(cè)誤差為： =10NiiiNNNXaXXXe=22NNeXXE預(yù)測(cè)誤差的均方值為預(yù)測(cè)誤差的均方值為 極小值極小值 0222=jNNjNNNjeXXXEaXXXEa1,.,1 , 00=NjXXXEjNN由此解出由此解出N個(gè)預(yù)測(cè)系數(shù)個(gè)預(yù)測(cè)系數(shù)ai /i=0,1,.N-1，由于，由于本方法求解時(shí)使預(yù)測(cè)誤差的均方值極小，因此稱本方法求解時(shí)使預(yù)測(cè)誤差的均方值極小，因此稱為最佳預(yù)測(cè)系數(shù)。為最佳預(yù)測(cè)系數(shù)。四、算術(shù)編碼四、算術(shù)編碼 o算術(shù)編碼方法：算術(shù)編碼方法： 將被編碼的信源消息表示成實(shí)數(shù)軸上將被編碼的信源消息表示成實(shí)數(shù)軸上01之間的一個(gè)間隔，消

37、息越長(zhǎng)，編碼表示它之間的一個(gè)間隔，消息越長(zhǎng)，編碼表示它的間隔就越小，表示這一間隔所需的二進(jìn)的間隔就越小，表示這一間隔所需的二進(jìn)制位數(shù)就越多，碼字就越長(zhǎng)，反之，編碼制位數(shù)就越多，碼字就越長(zhǎng)，反之，編碼所需的二進(jìn)制位數(shù)就越少，碼字就越短。所需的二進(jìn)制位數(shù)就越少，碼字就越短。例：例： 設(shè)圖像信源編碼用設(shè)圖像信源編碼用a、b、c、d表示，出表示，出現(xiàn)的概率分別為現(xiàn)的概率分別為1/2、1/4、1/8、1/8。則信。則信源編碼符號(hào)集的所有符號(hào)的概率之和組成源編碼符號(hào)集的所有符號(hào)的概率之和組成了一個(gè)完整的概率空間，用單位長(zhǎng)度的矩了一個(gè)完整的概率空間，用單位長(zhǎng)度的矩形來表示。形來表示。1/2、1/4、1/8、

38、1/8(一一)、編碼過程、編碼過程對(duì)對(duì)aabc進(jìn)行算術(shù)編碼進(jìn)行算術(shù)編碼1、編碼前，指針指向碼點(diǎn)、編碼前，指針指向碼點(diǎn)0，指針活動(dòng)寬度為，指針活動(dòng)寬度為1，即從，即從0到到1；2、編碼、編碼a，指針指向新的碼點(diǎn)，指針指向新的碼點(diǎn)0+10.011=0.011(前面的碼點(diǎn)前面的碼點(diǎn)+前面指針活動(dòng)寬度前面指針活動(dòng)寬度a的碼點(diǎn)的碼點(diǎn))，指針有效活動(dòng)寬度，指針有效活動(dòng)寬度10.1=0.1(前面的單位長(zhǎng)度前面的單位長(zhǎng)度a的概率的概率)；3、編碼、編碼a，指針指向新的碼點(diǎn)，指針指向新的碼點(diǎn)0.011+0.10.011=0. 1001，指針，指針有效活動(dòng)寬度有效活動(dòng)寬度0.10.1=0.01；4、編碼、編碼b，

39、指針指向新的碼點(diǎn)，指針指向新的碼點(diǎn)0.1001+0.010.001=0.10011，指針有效活動(dòng)寬度指針有效活動(dòng)寬度0.010.01=0.0001；5、編碼、編碼c，指針指向新的碼點(diǎn)，指針指向新的碼點(diǎn)0.10011+0.00010.111=0.1010011，指針有效活動(dòng)寬度，指針有效活動(dòng)寬度0.00010.001=0.0000001。最后的碼點(diǎn)值最后的碼點(diǎn)值1010011就是對(duì)就是對(duì)aabc進(jìn)行算術(shù)編碼的結(jié)果。進(jìn)行算術(shù)編碼的結(jié)果。1/2、1/4、1/8、1/8a0.0110.1、0.01、0.001、 0.0010.011+0.10.011=0. 1001 (0.10.1=0.01)0.10

40、01+0.010.001=0.10011 (0.010.01=0.0001)0.10011+0.00010.111=0.1010011o隨著碼字的增加，指針活動(dòng)范圍越來越小，隨著碼字的增加，指針活動(dòng)范圍越來越小，也就越來越精確，編碼的碼字位數(shù)就越多，也就越來越精確，編碼的碼字位數(shù)就越多，算法中只含有加法和移位運(yùn)算，因此稱為算法中只含有加法和移位運(yùn)算，因此稱為算術(shù)編碼。算術(shù)編碼。(二二)、解碼過程、解碼過程 在在01區(qū)間里定位，由于區(qū)間里定位，由于0.0110.10100110.111，解得第一，解得第一個(gè)碼字為個(gè)碼字為a；碼字序列減去前面的碼點(diǎn)值，碼字序列減去前面的碼點(diǎn)值，0.1010011-

41、0.011=0.0100011，再乘以再乘以2，0.01000112=0.100011，因?yàn)樵诰幋a過程中子，因?yàn)樵诰幋a過程中子區(qū)間寬度乘以區(qū)間寬度乘以a的概率的概率(0.1=1/2)，0.0110. 01000110.111，解得第二個(gè)碼字為解得第二個(gè)碼字為a；碼字序列減去前面的碼點(diǎn)值，碼字序列減去前面的碼點(diǎn)值，0.100011-0.011=0.001011，再，再乘以乘以2，0.0010112=0. 01011，因?yàn)樵诰幋a過程中子區(qū)間，因?yàn)樵诰幋a過程中子區(qū)間寬度乘以寬度乘以a的概率的概率(0.1=1/2)，0.0010. 010110.011，解得第，解得第二個(gè)碼字為二個(gè)碼字為b；01011

42、-0.001=0.00111，再乘以，再乘以4，0.001114=0. 111，因?yàn)椋驗(yàn)樵诰幋a過程中子區(qū)間寬度乘以在編碼過程中子區(qū)間寬度乘以b的概率的概率(0.01=1/4)，正好是，正好是c。o算術(shù)編碼效率比霍夫曼編碼效率高，在算術(shù)編碼效率比霍夫曼編碼效率高，在H.263、H.264/AVC和和AVS編碼標(biāo)準(zhǔn)中用算編碼標(biāo)準(zhǔn)中用算術(shù)編碼術(shù)編碼(基于內(nèi)容的自適應(yīng)算術(shù)編碼基于內(nèi)容的自適應(yīng)算術(shù)編碼)代替代替霍夫曼編碼，提高編碼效率?；舴蚵幋a，提高編碼效率。五、變換編碼五、變換編碼n行程編碼與行程編碼與Huffman編碼的設(shè)計(jì)思想都是基編碼的設(shè)計(jì)思想都是基于對(duì)于對(duì)信息表述方法的改變信息表述方法的改

43、變，屬于無損壓縮方，屬于無損壓縮方式。式。n雖然無損壓縮可以保證接收方獲得的信息與雖然無損壓縮可以保證接收方獲得的信息與發(fā)送方相同，但是其壓縮率一定有極限。發(fā)送方相同，但是其壓縮率一定有極限。n因此，采用忽略視覺不敏感的部分進(jìn)行有損因此，采用忽略視覺不敏感的部分進(jìn)行有損壓縮是提高壓縮率的一條好的途徑。壓縮是提高壓縮率的一條好的途徑。 (一一) 設(shè)計(jì)思想設(shè)計(jì)思想n基于基于DCT變換編碼是希望在接收方不產(chǎn)生變換編碼是希望在接收方不產(chǎn)生誤解的前提下進(jìn)行一定的信息丟失。誤解的前提下進(jìn)行一定的信息丟失。n由前面所講到的頻域變換得到的啟示，就由前面所講到的頻域變換得到的啟示，就是將低頻與高頻部分的信息，分

44、別按照不是將低頻與高頻部分的信息，分別按照不同的數(shù)據(jù)承載方式進(jìn)行表述。同的數(shù)據(jù)承載方式進(jìn)行表述。(二二)基本概念基本概念將空域描述的圖像經(jīng)過某種變換，在變換域中進(jìn)行將空域描述的圖像經(jīng)過某種變換，在變換域中進(jìn)行描述，達(dá)到改變能量分布的目的，將圖像能量在空描述，達(dá)到改變能量分布的目的，將圖像能量在空域的域的分散分布分散分布變?yōu)樵谧儞Q域的能量的相對(duì)變?yōu)樵谧儞Q域的能量的相對(duì)集中分布集中分布，利于進(jìn)一步處理，獲得對(duì)圖像信息量有效壓縮。利于進(jìn)一步處理，獲得對(duì)圖像信息量有效壓縮。DCT變換：變換：=1010222) 12(cos) 12(cos),()()(),(MxNyMNMNcyxyxfccF正變換：正

45、變換：=1010222) 12(cos) 12(cos),()()(),(MNMNcMNyxFccyxf=1)(21xc0=x1,.,2 , 1=Nx逆變換：逆變換：其中：其中：(三三)DCT變換編碼變換編碼DCT變換變換DCT逆變換逆變換原圖像原圖像量化量化取整取整1）編碼過程：）編碼過程：2）解碼過程：）解碼過程：壓縮圖像壓縮圖像反量化反量化取整取整壓縮壓縮圖像圖像解壓解壓圖像圖像例：例：原圖像為：原圖像為：DCT變換變換3753696267828785395771646984888741597366718683894361756873888591456377707590879347657

46、972779289954967817479949197506882758095929800000000000000010000000000000001000000030000000100000003531814342818106591變換編碼把統(tǒng)計(jì)上彼此密切相關(guān)的像素所變換編碼把統(tǒng)計(jì)上彼此密切相關(guān)的像素所構(gòu)成的矩陣通過線性變換正交變換，變成構(gòu)成的矩陣通過線性變換正交變換，變成統(tǒng)計(jì)上彼此較為相互獨(dú)立，甚至達(dá)到完全統(tǒng)計(jì)上彼此較為相互獨(dú)立，甚至達(dá)到完全獨(dú)立的變換系數(shù)所構(gòu)成的矩陣。獨(dú)立的變換系數(shù)所構(gòu)成的矩陣。 由信息論可知，由信息論可知，正交變換不改變信源的正交變換不改變信源的熵值熵值，變換前后的圖像的信息量并無損失，變換前后的圖像的信息量并無損失，完全可以通過反變換得到原來的圖像值。但完全可以通過反變換得到原來的圖像值。但經(jīng)正交變換后的數(shù)據(jù)分布發(fā)生了很大的改變，經(jīng)正交變換后的數(shù)據(jù)分布發(fā)生了很大的改變，系數(shù)向新坐標(biāo)點(diǎn)集中。系數(shù)向新坐標(biāo)點(diǎn)集中。o正交變換本身并不