第六章圖像數(shù)據(jù)壓縮編碼

第六章

圖像數(shù)據(jù)的壓縮編碼6.1圖像壓縮編碼概述一、圖像編碼的目的和應(yīng)用：目的：在可能的情況下盡量減少圖像數(shù)據(jù)的尺寸，以便于傳輸、存儲(chǔ)、管理、處理和應(yīng)用。圖像數(shù)據(jù)量舉例：視頻圖像：512×512×8×25bits/s≈150Mbit/s≈19MByte/s≈70,000MB/hr VCD：650M，74Min,約需要壓縮100倍！傳輸帶寬：CableATMMobilcommunication1.5～10Mbs播放速度：Upto34Mbs10Kbs～1Mbs醫(yī)學(xué)圖像：圖像種類圖像特征圖像數(shù)/檢查數(shù)據(jù)量/檢查核醫(yī)學(xué)128×128×1230～601～2MBMRI256×256×12608MB超聲512×521×820～2305～60MB數(shù)字減影血管造影DSA512×512×815～404～10MBCT512×512×124020MB計(jì)算機(jī)放射成像2048×2048×12216MB數(shù)字化X線攝影2048×2048×12216MB數(shù)字化X線乳腺攝影4096×4096×124128MBPACS系統(tǒng)的需求習(xí)題：試問(wèn):(1)對(duì)一個(gè)具有三個(gè)符號(hào)的信源，有多少個(gè)唯一的Huffman碼

(2)構(gòu)造這些碼字給出一幅8灰度級(jí)圖像的灰度值分布情況如下表示，

(1)計(jì)算圖像的熵

(2)對(duì)信源符號(hào)構(gòu)造Huffman編碼

(3)對(duì)信源符號(hào)構(gòu)造S-F編碼

(4)構(gòu)造最優(yōu)的B1碼

(5)構(gòu)造最優(yōu)的S2碼

(6)對(duì)每種編碼計(jì)算平均碼字長(zhǎng)度和編碼效率原始圖像灰度級(jí)01/72/73/74/75/76/77/7原始圖像各灰度級(jí)的像素790102385065632924512281二、壓縮的可能性與圖像保真度

1.圖像中的數(shù)據(jù)冗余冗余空間冗余時(shí)間冗余結(jié)構(gòu)冗余知識(shí)冗余視覺(jué)冗余信息熵冗余(編碼冗余)其它冗余 2.圖像在一些情況下允許一定程度的失真主觀保真度客觀保真度可能不完全統(tǒng)一保真度編碼信息保持編碼平均信息方法變換方法三、分類1.從圖像信息角度對(duì)編碼分類特征抽取2.從圖像編碼方法對(duì)編碼分類預(yù)測(cè)方法其它利用圖像的統(tǒng)計(jì)特征分配碼字長(zhǎng)度，達(dá)到壓縮目的，如Huffman,S-F

等調(diào)制，1D-DPCM，2D-DPCM,幀間預(yù)測(cè)，自適應(yīng)編碼等頻帶編碼，閾值編碼，多維技術(shù)，自適應(yīng)方法像素編碼行程編碼，等值線編碼，位平面編碼等混合編碼，二值/圖形編碼，彩色圖像編碼，矢量量化，金字塔編碼，基于知識(shí)的編碼等1.等長(zhǎng)碼與不等長(zhǎng)碼四、圖像編碼的一般過(guò)程五、常用編碼類型與舉例映射變換量化器編碼器解碼器反映射原始圖像信源碼字恢復(fù)的圖像等長(zhǎng)碼的碼位長(zhǎng)度都相等，即每一個(gè)碼字均有相同的比特?cái)?shù)，而不等長(zhǎng)碼則相反2.瞬時(shí)可譯碼與非瞬時(shí)可譯碼瞬時(shí)可譯碼：接收到一個(gè)碼位即可譯碼非瞬時(shí)可譯碼：接收到下一碼位才能譯碼3.唯一可譯碼非唯一可譯碼4.常用編碼舉例例如，某種代碼，c1=0,c2=1,c3=01,c4=10,則序列0011具有多意性：0011c1c3c2c1c1c2c2輸入數(shù)據(jù)W0W1W2W3W4W5W6W7自然碼000001010011100101110111格雷碼000001011010110111101100B1碼c0c1c0c0c0c1c1c0c1c1c0c0c0c0c0c1B2碼c00c01c10c11c00c00c00c01c00c10c00c11S2碼000110110011011110111100111101不等長(zhǎng)碼B碼中的c位稱為延續(xù)位，實(shí)際傳輸時(shí)用0或1代替B1碼和B2碼為非瞬時(shí)可譯碼選用等長(zhǎng)碼或不等長(zhǎng)碼的原則：輸入數(shù)據(jù)等概率分布時(shí)用等長(zhǎng)碼，否則，出現(xiàn)概率大的用短碼，出現(xiàn)概率小的用長(zhǎng)碼說(shuō)明：六、圖像的熵與平均碼字長(zhǎng)度1.圖像的熵(Entropy)

設(shè)數(shù)字圖像像素的灰度集合為｛w1,w2,……,wM｝，其對(duì)應(yīng)的概率分別為p1,p2,……,pM,按信息論中信源熵的定義，可以定義圖像的熵H

為：(bit)由上述定義可以看到，圖像的熵H是表示其各個(gè)灰度級(jí)比特?cái)?shù)的統(tǒng)計(jì)平均值，例如：①設(shè)隨機(jī)序列M由8個(gè)變量組成，等概率出現(xiàn)，即p1=p2=……,=p8，則：(bit)②設(shè)隨機(jī)序列M由8個(gè)變量組成，p1=1,p2=……,=p8=0，則：(bit)

因此，當(dāng)M

等于8時(shí)，H

的范圍從0到3，即H＝0～log2M，其中H＝3說(shuō)明信號(hào)的隨機(jī)程度最大。2.圖像的平均碼字長(zhǎng)度

設(shè)bk為數(shù)字圖像第k

個(gè)碼字ck的長(zhǎng)度(二進(jìn)制數(shù)的位數(shù))，其對(duì)應(yīng)出現(xiàn)的概率為pk,則該數(shù)字圖像的碼字平均長(zhǎng)度R

定義為：(bit)3.圖像的編碼效率：定義數(shù)字圖像編碼的效率為：

在R≧H

情況下總可以設(shè)計(jì)出某種無(wú)失真編碼方法，若R接近于H，則說(shuō)明碼編的較好，稱為最佳編碼。若要求編碼結(jié)果R<H,則必然要丟失信息而引起圖像失真。同時(shí)定義圖像編碼的冗余度為：4.圖像的變長(zhǎng)最佳編碼定理定理：在變長(zhǎng)編碼中，若對(duì)出現(xiàn)概率大的信息賦予短碼字，而對(duì)于出現(xiàn)概率小的信息賦予長(zhǎng)碼字，如果碼字長(zhǎng)度嚴(yán)格按照所對(duì)應(yīng)符號(hào)出現(xiàn)的概率大小而逆序排列，則此種編碼結(jié)果的平均碼字長(zhǎng)度一定小于其它任何排列形式得到的編碼。例如：圖像的熵(bit)采用等長(zhǎng)編碼：平均碼長(zhǎng)R＝2(bit)，編碼效率h＝87.5％，Rd=12.5%輸入數(shù)據(jù)W1W2W3W4概率1/21/41/81/8W1W2W3W400011011W1W2W3W4010110111采用不等長(zhǎng)編碼：平均碼長(zhǎng)R＝7/4(bit)，編碼效率h＝

100％，Rd=0%6.2常用編碼方法§6.2.1統(tǒng)計(jì)編碼1.Huffman編碼（Huffman

，1952）Huffman編碼是根據(jù)可變長(zhǎng)度最佳編碼定理，應(yīng)用Huffman編碼算法而產(chǎn)生的一種編碼方法它的平均碼字長(zhǎng)度在系統(tǒng)的輸入概率集合下，比其它唯一可譯碼都小。因此也稱為緊湊碼。Huffman編碼的原則是概率大的信息用短碼，而概率小的信息用長(zhǎng)碼，即：若：p1(w1)>p2(w2)>……>pM(wM)則?。篵1(c1)<b2(c2)<……<bM(cM)Huffman編碼的編碼步驟：①將信源符號(hào)按概率由大到小排列，概率相同的可以任意放②將兩個(gè)最小概率相加，形成新的概率集合，并按①的原則重新排隊(duì)③重復(fù)②的過(guò)程，直到僅剩下兩個(gè)概率為止④分配碼字進(jìn)行編碼，原則是從后到前，上0下1(或上1下0)Huffman編碼舉例：第一次重排編碼結(jié)果輸入數(shù)據(jù)對(duì)應(yīng)概率W10.4W20.3W30.1W40.1W50.06W60.040.40.30.10.10.10.40.30.20.10.40.30.30.60.4第二次重排第三次重排第四次重排0111111000100000000010011011010001010100010100101101011010100110110100熵計(jì)算編碼效率：編碼效率：h=2.14/2.2=97.3%為在接收端對(duì)上述編碼進(jìn)行解碼，可以采用樹(shù)形解碼方法唯一地解碼，每輸入一位即可確定分支情況，并自動(dòng)確定碼字的起止位。為此需要建立右圖的解碼樹(shù)。平均碼長(zhǎng)：R＝0.4＋0.3×2＋0.1×3＋0.1×4＋0.06×5＋0.04×5＝2.2bit說(shuō)明：wi1011110000w1w3w6w2w4w5在解碼時(shí)將輸入的數(shù)碼按樹(shù)去分配，得到碼字的切分和代碼符號(hào)，例如，輸入序列1011100010101從上述解碼過(guò)程可以看到，雖然Huffman碼不是等長(zhǎng)碼，但解碼中能自動(dòng)確定起止位。解碼結(jié)果是唯一的。2.Shannon－Fano編碼編碼步驟：①將信源符號(hào)按概率由大到小排列，概率相同的可以任意放②將概率分為近似相等的兩部分③進(jìn)行編碼，上半部分賦予0，下半部分賦予1④重復(fù)②

③直至編碼完成S－F編碼舉例：編碼結(jié)果輸入數(shù)據(jù)對(duì)應(yīng)概率W10.4W20.3W30.1W40.1W50.06W60.0401101111011111001101111011111111111011011100100編碼效率：h＝

97.3%平均碼長(zhǎng)：R＝2.2bit3.采用B1

編碼B類編碼適用于灰度級(jí)概率按指數(shù)規(guī)律分布的圖像，如打字圖像。而S碼適用于具有單調(diào)減少概率的輸入信號(hào)。為說(shuō)明B碼的使用方法，對(duì)上述例題采用B1編碼：編碼結(jié)果輸入數(shù)據(jù)對(duì)應(yīng)概率W10.4W20.3W30.1W40.1W50.06W60.04C0C1C0C0C0C1C1C0C1C1編碼效率：h＝

82.3%平均碼長(zhǎng)：R＝2.6bit而采用等長(zhǎng)碼時(shí)R＝3，h=71.3％解碼問(wèn)題：編碼中的C稱為延續(xù)位，在傳輸時(shí)用1或0代替，并交替進(jìn)行。例如發(fā)送了三個(gè)符號(hào)W2W5W6，傳輸時(shí)為：0111100101

在解碼時(shí)可以逐位判斷是否應(yīng)截?cái)?，在隔位比特變化時(shí)應(yīng)截?cái)?，而連續(xù)比特不變則延續(xù)。因此B碼不是瞬時(shí)可譯碼。例：有圖像f(x,y)，如右圖所示，灰階為3bit，即0～7，比較幾種不同編碼的效果4.通過(guò)映射變換達(dá)到壓縮編碼0011111122333333444444445555555566667777777777777777777777777777①直接將圖像傳輸：②采用S2碼輸入數(shù)據(jù)對(duì)應(yīng)概率728/6458/6448/6436/6416/6464/6422/6402/64編碼結(jié)果000110110011011110111100111101總碼長(zhǎng)為176bit平均碼長(zhǎng)為R＝176/64＝2.75bit編碼效率：h

＝89.8%圖像的熵：H＝2.47bit總碼長(zhǎng)為3×64＝192bit平均碼長(zhǎng)為R＝3bit編碼效率：h

＝82.3%③采用Huffman

編碼編碼灰度概率重排1重排2重排3重排4重排5重排6728/6428282828283658/64881216202848/64888121636/64688816/6466864/644622/64302/6410010100000000101100111001111總碼長(zhǎng)為160bit平均碼長(zhǎng)：R＝160/64＝2.5bit編碼效率：h

＝98.8%④先用差分映射進(jìn)行變換，再用Huffman

編碼差分映射:差分映射可以按行或按列進(jìn)行，按行映射公式為：

y0=x0 y1=x0-x1 y2=x1-x2 …… yi=xi－1-xi00-10000020-10000040000000500000006000-1000700000007000000070000000映射得到的差分圖像如右上圖所示輸入數(shù)據(jù)對(duì)應(yīng)概率054/6473/64－13/6461/6451/6441/6421/64差分圖像的灰度概率如右下表所示編碼灰度概率重排1重排2重排3重排4重排5054/64545454545473/64334610－13/64333461/6422351/641241/64121/64對(duì)差分圖像采用Huffman

編碼的結(jié)果如下：01001011110111111001101總碼長(zhǎng)為88bit平均碼長(zhǎng)：R＝88/64＝1.375bit可見(jiàn)，經(jīng)過(guò)差分映射后再進(jìn)行編碼，可以有效壓縮編碼數(shù)據(jù)。1.RLE編碼的效率§6.2.2行程編碼(RunLengthEncoding,RLE)

適用于有較多灰度相同對(duì)象的圖像，例如海洋、湖泊的衛(wèi)星圖像，醫(yī)學(xué)圖像中的細(xì)胞，染色體，材料的顯微圖像等。計(jì)算機(jī)中的PCX和BMP格式的圖像都采用行程編碼進(jìn)行壓縮。RLE的原理相當(dāng)簡(jiǎn)單，計(jì)算效率高。RLE編碼采用整數(shù)對(duì)進(jìn)行編碼，例如右側(cè)圖像可以編碼為(4,4)(4,1)(5,3)(4,1)(5,1)(7,2)(5,4)4444455545775555下面具體討論RLE編碼的效率和實(shí)現(xiàn)中的具體問(wèn)題。

設(shè)圖像的灰度級(jí)為M，一行的長(zhǎng)度為N，則對(duì)每一行來(lái)說(shuō)，行程數(shù)最少為1，最大為N。若將數(shù)對(duì)表示為(gk,lk)的序列，用普通二進(jìn)制碼存放(gk,lk)序列，并設(shè)一行中的行程數(shù)為m，則描述一行像素需要的碼字長(zhǎng)度為：m(log2M+log2N)bit而直接存儲(chǔ)原圖像一行所需的位數(shù)為：Nlog2Mbit顯然，只有當(dāng)m<<N

時(shí)，RLE的描述才是可取的。2.碼的截?cái)啵瓝Q行問(wèn)題方法1：預(yù)先存儲(chǔ)行的長(zhǎng)度，通過(guò)長(zhǎng)度控制截?cái)啵秉c(diǎn)是長(zhǎng)度不允許有誤碼例：BMP圖像文件的編碼BMP：文件頭 位圖信息 位圖陣列方法2：將行的結(jié)束作為一個(gè)碼對(duì)排入碼流，其缺點(diǎn)是加長(zhǎng)了序列長(zhǎng)度，降低了效率。 Windows的BMP格式中支持BI-RLE8和BI-RLE4兩種壓縮類型的存儲(chǔ)格式。由于使用了顏色索引表，因此可以用4位/像素存儲(chǔ)16色的圖像，用8位/像素存儲(chǔ)256色的圖像。下面介紹BI-RLE8的壓縮格式： BI-RLE8的壓縮格式由兩字節(jié)的數(shù)據(jù)對(duì)序列組成，第一個(gè)字節(jié)給出對(duì)應(yīng)畫(huà)出的連續(xù)像素的數(shù)目，而所用的顏色索引在第二字節(jié)中。如果第1個(gè)字節(jié)為0，則第個(gè)字節(jié)的含意如下：0: 行結(jié)束例如下面的序列：0304050600031234560002780002030202780000061E0001解壓縮為：行結(jié)束圖像結(jié)束04040406060606061234567878------------78781E1E1E1E1E1E1： 圖像結(jié)束2： 轉(zhuǎn)義后面的兩個(gè)字節(jié)，用這兩個(gè)字節(jié)分別表示下一像素從當(dāng)前位置水平和垂直位移的距離。n(0x03<n<0xff):轉(zhuǎn)義后面的n個(gè)字節(jié)，其后的n

個(gè)像素分別由這n

個(gè)字節(jié)所指定的顏色畫(huà)出。必須保證這種截?cái)嗍?的整數(shù)倍，不足的位數(shù)補(bǔ)03.對(duì)于二值圖像，由于只有兩個(gè)可能的灰度取值，在一行中相鄰兩個(gè)行程的值一定交替出現(xiàn)，因此只需要在第一個(gè)行程中標(biāo)出灰度值，于是一行的行程編碼為：g1l1l2……lm其中g(shù)1只有兩個(gè)值，只需要1bit存儲(chǔ)，因此描述一行的行程編碼的長(zhǎng)度為：1+m?log2Nbit而用直接編碼表示則需要Nbit4.為壓縮圖像，可以根據(jù)各種行程長(zhǎng)度在圖像中出現(xiàn)的概率，用不同長(zhǎng)度的碼字表示其編碼，以提高圖像數(shù)據(jù)的壓縮率。適用于少細(xì)節(jié)的圖像，如工程圖紙，文字，指紋等。基本思路：對(duì)圖像中灰度相同的區(qū)域，可以通過(guò)確定以下特征來(lái)表示：算法：§6.2.3等值線編碼(1)包圍這個(gè)區(qū)域的外圍邊界，即輪廓的方向序列(2)輪廓的起始位置(行數(shù)和列數(shù))(3)輪廓所包圍區(qū)域的灰度值若區(qū)域有一定面積，則對(duì)上述三個(gè)特征編碼，可能比對(duì)區(qū)域內(nèi)每個(gè)象素都分配碼字節(jié)約，且圖像細(xì)節(jié)越少，節(jié)省的比特?cái)?shù)越多。尋找輪廓的算法計(jì)算輪廓方向序列的算法：T算法計(jì)算輪廓起始點(diǎn)的算法：IP算法先找到第一個(gè)起始點(diǎn)，并進(jìn)行第一個(gè)輪廓方向序列的計(jì)算，再找到第二個(gè)起始點(diǎn)，進(jìn)行第二個(gè)輪廓方向序列的計(jì)算，依次交叉進(jìn)行，直到找到所有輪廓。1.輪廓方向序列的計(jì)算－T算法采用LML(LeftMostLooking)規(guī)則，沿輪廓前進(jìn)。例：LML規(guī)則：①先向左看②向前看③向右看④向后看利用LML規(guī)則，判斷所看的點(diǎn)是否灰度相等，若相等則前進(jìn)，若所有方向都不等，則為孤立點(diǎn)。共有四種象素灰度：代碼 灰度值表示為

00 a01 b10c11d選左上角的象素作為第一個(gè)輪廓的起始點(diǎn)！若等值線上的點(diǎn)走了兩次，則按下列規(guī)則合并指示符：2.等值線上的點(diǎn)賦“指示符”第一次、第二次通過(guò)的方向標(biāo)志DAADRRDRRDDDAR

RAAA合并后RDAIP1ARRRRRRDDDDDDRRRARRRRRAAAAADR或RA或或或輸出輸入指示符號(hào)分為I，A，R，D四種，初始化時(shí)各點(diǎn)賦指示符號(hào)I，然后根據(jù)等值線輸入和輸出的方向按下列規(guī)則更改：3.用IP算法尋找新起始點(diǎn)4.輪廓起始點(diǎn)判別規(guī)則5.在維護(hù)CPL表過(guò)程中，對(duì)新找到的起始點(diǎn)，確定其等值線，并重新掃描通過(guò)建立CPL表，并順序掃描搜索，利用判別規(guī)則確定掃描過(guò)的點(diǎn)是否為新的起始點(diǎn)。CPL表的建立：(1)每掃描一行制一個(gè)表，掃描前表為空(2)對(duì)每一行掃描，從左到右逐象素進(jìn)行判別，若遇到標(biāo)記為A的點(diǎn)，將該點(diǎn)灰度值填入表中；若遇到標(biāo)記為D，則將表中最后一個(gè)記錄劃去；若遇到標(biāo)記為I，表的內(nèi)容不變，但需要判別是否起始點(diǎn)；若標(biāo)記為R，則表的內(nèi)容不變。(3)每行掃描完畢，表一定是空的。(為什么？)在生成CPL表時(shí)，可利用下面的規(guī)則找到起始點(diǎn)：(1)掃描點(diǎn)指示符為I(2)灰度值與CPL表中標(biāo)記的點(diǎn)的灰度不等DDDDDIP1ARRRRRRDRRRARRRRRAAAAA行號(hào)CPL說(shuō)明0行1行1行1行2行3行4行5行aaADADabaRRRDDRAADARacAD做完上述建表和掃描、畫(huà)等值線工作后，確定該圖像有4條等值線！結(jié)果為空，表示該行無(wú)新起始點(diǎn)第1行第1列點(diǎn)作為IP2，利用T算法畫(huà)等值線重新掃描，對(duì)輪廓2，遇到A，又遇到D，故填上b又消去b第1行第4列點(diǎn)作為IP3，但標(biāo)記R不增加CPL項(xiàng)，遇D消去a無(wú)新起始點(diǎn)無(wú)新起始點(diǎn)無(wú)新起始點(diǎn)第1列為IP4，……同上同上空發(fā)送時(shí)將等值線的灰度值，IP點(diǎn)坐標(biāo)和方向序列一一逐個(gè)發(fā)送，即可描述圖像。6.做出編碼表00011011等值線號(hào)灰度值IP行坐標(biāo)IP列坐標(biāo)IP點(diǎn)后各象素方向000000000001,01,01,01,01,01,01,10,10,10,10,10,11,11,11,11,……(共26個(gè))010100100101,10,11,00101000110010,10,01,01,10,11,11,00,00,00111110100101,11上述采用三位自然碼，亦可用Huffman編碼進(jìn)行優(yōu)化。方向代碼：§6.2.4預(yù)測(cè)方法編碼(自學(xué))一、預(yù)測(cè)方法編碼的類型二、DPCM的基本原理三、DPCM方法中最佳系數(shù)的確定四、DPCM方法中圖像降質(zhì)的類型和原因要點(diǎn)§6.2.5LZW壓縮算法(自學(xué))一、LZW壓縮算法說(shuō)明，王廣志編二、lzwcompression，ByBobMontgomery三、lzwandgifexplained，BySteveBlackstock補(bǔ)充材料：

上述編碼均在圖像空間進(jìn)行操作，稱為空域方法。而基于圖像變換的方法稱頻域方法?！?.2.6變換方法壓縮編碼頻域方法的基礎(chǔ)：頻域方法一般為非信息保持編碼！頻域方法的處理流程：構(gòu)造子圖像正變換重新量化符號(hào)編碼合并子圖像符號(hào)解碼反變換輸入圖像壓縮圖像壓縮圖像解壓圖像通過(guò)可逆的線性變換將圖像映射為一組變換系數(shù)，達(dá)到能量集中的目的，從而舍棄能量很小的系數(shù)，達(dá)到壓縮的目的。頻域方法的優(yōu)點(diǎn)：壓縮比高，視覺(jué)效果好1.子圖像尺寸的選擇原則變換編碼中的主要問(wèn)題：子圖像尺寸的選擇變換方法的選擇比特分配方法子圖像尺寸的選擇影響到編碼誤差和計(jì)算的復(fù)雜度，實(shí)際中