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

第六章

圖像數(shù)據(jù)的壓縮編碼6.1圖像壓縮編碼概述一、圖像編碼的目的和應(yīng)用：目的：在可能的情況下盡量減少圖像數(shù)據(jù)的尺寸，以便于傳輸、存儲、管理、處理和應(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計算機放射成像2048×2048×12216MB數(shù)字化X線攝影2048×2048×12216MB數(shù)字化X線乳腺攝影4096×4096×124128MBPACS系統(tǒng)的需求習(xí)題：試問:(1)對一個具有三個符號的信源，有多少個唯一的Huffman碼

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

(1)計算圖像的熵

(2)對信源符號構(gòu)造Huffman編碼

(3)對信源符號構(gòu)造S-F編碼

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

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

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

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

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

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

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

因此，當(dāng)M

等于8時，H

的范圍從0到3，即H＝0～log2M，其中H＝3說明信號的隨機程度最大。2.圖像的平均碼字長度

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

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

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

在R≧H

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

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

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

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

97.3%平均碼長：R＝2.2bit3.采用B1

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

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

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

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

＝82.3%③采用Huffman

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

＝98.8%④先用差分映射進行變換，再用Huffman

編碼差分映射:差分映射可以按行或按列進行，按行映射公式為：

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

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

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

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

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

個像素分別由這n

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

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

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

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