數(shù)字圖象處理第七章第一頁，共九十二頁，2022年，8月28日引言圖像信息之所以可被減少或稱被壓縮，是由于圖像信息中有大量的冗余信息。圖像壓縮就是利用了圖像信號中的冗余度，如數(shù)據(jù)編碼冗余度、心理冗余度(利用人眼視覺系統(tǒng)的一些特性忽略掉一些不被人眼所察覺的信號成分)等，進(jìn)行壓縮。第二頁，共九十二頁，2022年，8月28日1、數(shù)據(jù)冗余如果用n1和n2分別代表相同信息的2個數(shù)據(jù)集合中的信息載體單位的個數(shù)，那么第一個數(shù)據(jù)集合的相對數(shù)據(jù)冗余RD(相對于第二個數(shù)據(jù)集合)定義為：

RD=1-1/CR其中CR稱為壓縮率：CR=n1/n2例如，對同一幅512×512點(diǎn)的全白圖像，以兩種方式表達(dá)這幅圖像：每點(diǎn)用8位信息表示n1=512×512×8每點(diǎn)用1位信息表示n2=512×512×1則RD=1-1/CR＝1－1/8=88%

CR=n1/n2＝8第三頁，共九十二頁，2022年，8月28日2、冗余的形式編碼冗余：沒有充分利用編碼對像的概率特性而產(chǎn)生的冗余。設(shè)定義在[0,1]區(qū)間的離散隨機(jī)變量sk代表圖像的灰度值，每個sk以概率ps(sk)出現(xiàn)：

ps(sk)＝nk/nk=0,1,…,L-1

其中L為灰度級數(shù)，nk是第k個灰度級出現(xiàn)的次數(shù)，n是圖像中像素總個數(shù)。如果一個像素(事件、信息)用8位表示，該信息被賦予的碼符號序列稱為碼字；碼字里的符號個數(shù)稱為碼長。第四頁，共九十二頁，2022年，8月28日若用于表示信息sk的位數(shù)是l(sk)，那么為表示每個像素所需的平均位數(shù)(碼長)為：自然碼和變長碼的例子第五頁，共九十二頁，2022年，8月28日RD=1-1/CR＝1-0.91=9%CR=n1/n2＝3/2.7=1.11說明該圖像有9%的冗余。自然碼和變長碼的例子第六頁，共九十二頁，2022年，8月28日像素間的冗余圖像的重要特點(diǎn)之一就是像素間具有某種相關(guān)性。換言之，就是如果相鄰像素值可由本像素值得出，那么像素值原來的表達(dá)是多余的。心理視覺冗余如果隨著圖像信息表達(dá)位數(shù)的增加，主觀視覺效果不在增加，那么多于的信息表達(dá)位數(shù)就是心理視覺冗余。100→110→120第七頁，共九十二頁，2022年，8月28日3、圖像保真度和質(zhì)量1)客觀保真度原則均方根誤差均方信噪比峰值信噪比2)主觀保真度原則優(yōu)秀——很好良好——較好可用——稍好剛可看——相同差——較差不能用——很差第八頁，共九十二頁，2022年，8月28日Lena.bmp(原圖)第九頁，共九十二頁，2022年，8月28日Lenna.jpg(壓縮率9.2)第十頁，共九十二頁，2022年，8月28日Lenna.jpg(壓縮率18.4)第十一頁，共九十二頁，2022年，8月28日Lenna.jpg(壓縮率51.6)第十二頁，共九十二頁，2022年，8月28日二、編碼模型輸入圖像輸出圖像信源編碼器信道解碼器信道編碼器信源解碼器信道第十三頁，共九十二頁，2022年，8月28日漢明碼——一種糾錯碼。漢明指出：如果將3位的冗余加到4位碼字上，則所有單個位出現(xiàn)的錯誤都可以發(fā)現(xiàn)和校正。編碼：例如：0101→1010010解碼：對漢明碼進(jìn)行校驗，錯誤位置由非零校驗字c4c2c1指出；對該位求反即可糾正錯誤。如果校驗字為零，則解碼結(jié)果為h3h5h6h7。信道編碼、解碼器以漢明碼為例第十四頁，共九十二頁，2022年，8月28日一個典型的信源壓縮(編碼)系統(tǒng)如圖所示。通過時間軸上采樣和幅度量化將連續(xù)信號變成離散數(shù)字信號并對其進(jìn)行量化。將信號中絕大部分能量集中在少數(shù)幾個變換系數(shù)上，去除信號中的相關(guān)性信號壓縮真正體現(xiàn)在量化階段。一般先是游程編碼，然后Huffman編碼或算術(shù)編碼進(jìn)一步提高壓縮比如果信號已經(jīng)數(shù)字化最終的“無損”與“有損”編碼的區(qū)別在于：在編碼過程中是否是對全部的“數(shù)據(jù)”進(jìn)行編碼。第十五頁，共九十二頁，2022年，8月28日1、設(shè)計一個好的圖像編碼器的步驟要為圖像信號選擇一個正確合適的模型；在這個給定模型框架中優(yōu)化編碼器。壓縮算法的選擇；數(shù)據(jù)壓縮率、失真度和算法的復(fù)雜度。2、圖像編碼算法的分類：1)、一類是無損編碼即在編碼過程中信息沒有丟失。2)、另一類是有損編碼即在編碼過程中沒有對所有信息編碼。

三、編碼器的設(shè)計原則第十六頁，共九十二頁，2022年，8月28日3、圖像信息率及編碼效率

一般靜止灰度圖像中每個像素用8比特來表示，那么一幅圖像的平均信息率可以用下面的熵值來表示：其中pi＝ni/ni=0,1,…,L-1表示像素取i級灰度的概率，i的取值范圍為0~（28-1）。H表示該圖像在不失真情況下，每像素編碼所需的最小碼長；如果對每像素編碼的碼長小于H，則解碼后的圖像會產(chǎn)生失真。第十七頁，共九十二頁，2022年，8月28日4、最佳編碼定理主要內(nèi)容：若對一幅圖像進(jìn)行編碼，將出現(xiàn)概率較高的信息(出現(xiàn)概率較高的像素值)賦予較短的碼字；反之，將出現(xiàn)概率較低的信息(出現(xiàn)概率較低的像素值)賦予較長的碼字；如果碼字長度嚴(yán)格按照所對應(yīng)信息出現(xiàn)的概率大小逆序排列，則這樣編碼結(jié)果的平均碼字長度一定是小于任何其它排列方式。衡量編碼優(yōu)劣可用編碼效率作為一個重要指標(biāo)。第十八頁，共九十二頁，2022年，8月28日對最佳編碼定理的簡單說明設(shè)圖像灰度級為w1,w2,…wN；各級灰度出現(xiàn)的概率分別為p1,p2,…pN(由大到小)；編碼器賦予各級灰度對應(yīng)的碼字長度分別為t1,t2,…tN(由小到大)

；則編碼后圖像平均碼字長度R應(yīng)為：令：R1為嚴(yán)格按最優(yōu)編碼定理規(guī)定的原則編碼的平均碼字長度；R2為在編碼過程中將任意兩個灰度級不按最優(yōu)編碼定理規(guī)定的原則編碼的平均碼字長度。依最優(yōu)編碼定理的結(jié)論應(yīng)有R2＝R1＋△R。只要證明△R＞0即可第十九頁，共九十二頁，2022年，8月28日令第m和n個灰度級出現(xiàn)的概率分別為pm，pn，且pm>pn；對應(yīng)的碼字長度分別為tm，tn，且tm>tn(不符合嚴(yán)格逆序的原則)。構(gòu)造下列運(yùn)算：注意：概率和字長均為正數(shù)。不按定理的碼長按定理的碼長說明不按定理編碼的平均碼長一定大于按定理編碼的平均碼長說明運(yùn)算構(gòu)造的合理性第二十頁，共九十二頁，2022年，8月28日5、編碼的唯一可譯碼(單義碼)原則一個能唯一的被譯出、不會產(chǎn)生歧義的編碼序列稱為唯一可譯碼編碼(單義碼)

。這樣的編碼序列應(yīng)滿足以下兩個條件：編碼中的任何一個碼字都不是另一個碼字的簡單續(xù)長代碼——由一個碼字簡單添加一些碼元而構(gòu)成一個新的碼字。注意：非續(xù)長碼一定是單義碼；而單義碼不一定是非續(xù)長碼。編碼序列應(yīng)為單義代碼序列，即滿足Kraft不等式。其中：n為編碼序列的編碼個數(shù)；D為編碼系統(tǒng)的進(jìn)制；ti為第i個碼字的長度。第二十一頁，共九十二頁，2022年，8月28日編碼的唯一可譯碼原則的解釋某編碼序列C=[00,10,0(0)11,101]對應(yīng)信息[a,b,c,d]編碼序列C滿足Kraft不等式，所以C是單義代碼。例：某編碼序列C=[101,10,00,10]dbab某編碼序列C=[0,01,1,11]對應(yīng)信息[a,b,c,d]編碼序列C不滿足Kraft不等式，所以C不是單義代碼。例：某編碼序列C=[0,1,11,0,11]acdad→bdbc?所有應(yīng)用于信號的編碼，都應(yīng)滿足編碼的唯一可譯碼原則。第二十二頁，共九十二頁，2022年，8月28日四、簡單編碼方法哈夫曼編碼是一種利用信息符號概率分布特性的變字長的編碼方法。對于出現(xiàn)概率大的信息符號編以短字長的碼，對于出現(xiàn)概率小的信息符號編以長字長的碼。具體步驟：分配碼字長度時，首先將出現(xiàn)概率最小的兩個符號的概率相加，合成一個概率；第二步把這個合成概率看成是一個新組合符號的概率。重復(fù)上述做法，直到最后只剩下兩個符號的概率為止。完成以上概率相加順序排列后，再反過來逐步向前進(jìn)行編碼；每一步有二個分支，各賦予一個二進(jìn)制碼，可以對概率大的編碼賦為0，概率小的編碼賦為1。1、哈夫曼編碼——最優(yōu)變長編碼第二十三頁，共九十二頁，2022年，8月28日哈夫曼編碼示例某圖像中的一個子集如圖所示，其哈夫曼編碼為(逐行a2a6a2a6a4a5a2a3a1)：1

00

1

00

0100

01011

1

01010

001

共24位如果用每個符號3位自然碼編碼：共需27位；符號概率排序編碼過程①⑩②⑨③⑧④⑦⑤⑥a10.1a20.410.410.410.410.60a20.4a60.3000.3000.3000.3000.41a30.06a10.10110.10110.20100.301a40.1a40.101000.101000.1011a50.04a30.06010100.10101a60.3a50.0401011a2a2a2a6a6a4a3a1a5第二十四頁，共九十二頁，2022年，8月28日設(shè)某一幅圖象共有8個灰度級，各灰度級出現(xiàn)概率分別為：試對此圖象進(jìn)行Huffman編碼。第二十五頁，共九十二頁，2022年，8月28日計算上例的編碼效率圖像的熵、平均碼字長度、編碼效率若按自然碼編碼：H=2.14Lavg=3編碼效率=71.3%之所以沒有達(dá)到H=2.14的水平，是因為字長是整數(shù)。第二十六頁，共九十二頁，2022年，8月28日哈夫曼編碼在使用中出現(xiàn)的問題1、編碼過程太復(fù)雜2、對每個文件的編碼是不一樣的3、解碼器的構(gòu)造不一致4、壓縮文件中必須包含解碼信息針對上述問題，常常采用一些亞最優(yōu)編碼只要對文件信息的統(tǒng)計參數(shù)已知，可直接用亞最優(yōu)編碼對其進(jìn)行壓縮。第二十七頁，共九十二頁，2022年，8月28日2、亞最優(yōu)可變長編碼哈夫曼編碼為最優(yōu)編碼。但在使用過程中有不便之處：要對編碼對像進(jìn)行概率統(tǒng)計，不利于快速編碼。如果對某一類編碼對像的統(tǒng)計統(tǒng)計規(guī)律有一定的了解，即可利用一些亞最優(yōu)變長編碼技術(shù)得到近似最優(yōu)的編碼結(jié)果。第二十八頁，共九十二頁，2022年，8月28日亞最優(yōu)可變長編碼常見的亞最優(yōu)變長編碼有：截斷哈夫曼碼——對最有可能出現(xiàn)的M個符號進(jìn)行哈夫曼編碼；將其余的符號概率相加，查出對應(yīng)的哈夫曼編碼作為前綴，后跟由0開始的自然碼對剩余的信息進(jìn)行編碼。哈夫曼平移碼——①重新排列信源符號使它們的概率單減；②將符號總數(shù)分成相同大小的符號塊；③對所有塊中的各個元素采用同樣方法編碼；④對每個塊加上專門的移上移下符號以區(qū)別它們。每當(dāng)解碼器認(rèn)出1個移上移下符號，它就相對事先定義的參考塊移上移下1個塊。具體到平移哈夫曼碼，則在用哈夫曼方法對參考塊編碼前先將概率賦給平移符號。第二十九頁，共九十二頁，2022年，8月28日編碼應(yīng)用舉例1——圖像的差分編碼某衛(wèi)星圖像f為2340×3240像素，灰度量化為128級。如果采用自然碼編碼，共需使用2340×3240×7≈50Mbit。若每天接收30幅，則共需使用約50×30＝1500Mbit。圖像的直方圖如圖所示。構(gòu)造差分變換矩陣A，對圖像f進(jìn)行變換。A為(2340×3240)×(2340×3240)方陣f為(2340×3240)×1列向量；g為(2340×3240)×1列向量圖像以堆疊向量表示第三十頁，共九十二頁，2022年，8月28日直方圖的比較可以看出：由于圖像數(shù)據(jù)的相關(guān)性，差分?jǐn)?shù)據(jù)的方差(數(shù)據(jù)的離散程度小)遠(yuǎn)小于灰度數(shù)據(jù)的方差。根據(jù)最佳編碼定理，對差分?jǐn)?shù)據(jù)編碼所需的平均碼長會遠(yuǎn)小于對灰度數(shù)據(jù)編碼所需的平均碼長。skpk(sk)1690gipi(gi)-32032-88灰度直方圖差分?jǐn)?shù)據(jù)直方圖0.250.4第三十一頁，共九十二頁，2022年，8月28日構(gòu)造編碼構(gòu)造一種變形的A碼(移位碼)，共16個碼字c1c2c3…c16

。c1＝0000，c2＝0001，c3＝0010，……c16＝1111將其中的14個碼字c2c3…c15分配給差分?jǐn)?shù)據(jù)；c1

、c16

作為指示位。0…678…2021…35…c9…c15c16c2c16c3…c16c15c16c16c2…c16c16c16c2……-36-35…-23-22－21…－9－8-7……c1c1c1c15c1c1c2…c1c1c14c1c1c15c1c2c1c14c1c15c2…圖像重構(gòu)：編碼圖像→解碼→逆變換f=A-1g壓縮后的平均碼長為4.3，壓縮61％；如果用哈夫曼編碼平均碼長為3.5，壓縮50％。第三十二頁，共九十二頁，2022年，8月28日對存在大面積等灰度塊的圖像(可能是直接得到，也可能是通過某種增強(qiáng)方法得到)可采用圖像輪廓編碼進(jìn)行壓縮。——任何一個灰度區(qū)域，都可以按照某種規(guī)則勾畫成一個封閉的等值線。編碼應(yīng)用舉例2——圖像的輪廓編碼①將所有像素標(biāo)記為I②從左上角開始逐行尋找起始點(diǎn)并將該點(diǎn)標(biāo)記成IP；能夠成為起始點(diǎn)的條件為該點(diǎn)標(biāo)記為I，并且不在已勾畫過的輪廓當(dāng)中。③按“向左看”，“順時針轉(zhuǎn)”的原則，尋找等灰度I點(diǎn)，按標(biāo)記規(guī)則加注標(biāo)記。④完成一個封閉輪廓后，尋找新的輪廓起點(diǎn)。直至標(biāo)記完所有輪廓。標(biāo)記像元出的方向↑→↓←像元進(jìn)的方向↑←AR↓→RDIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII第三十三頁，共九十二頁，2022年，8月28日勾畫輪廓及標(biāo)記新IP點(diǎn)的確定：從左到右從上到下逐行搜索。①構(gòu)造棧區(qū)，搜索新的一行時，將棧區(qū)清空。②遇A進(jìn)棧，遇D出棧，遇R不管；如果空棧遇I則為一新的IP點(diǎn)；如果非空棧遇I且該像素的灰度值不同于先前進(jìn)棧A點(diǎn)的灰度值，則該點(diǎn)為一新的IP點(diǎn)，反之不是。IP1RRRRRRDARRRRRIDARIP2RDRARDRARAIDDAIP3DAARADDRRDADAARRRDADRDAARRRDADRR對于同一像素點(diǎn)上出現(xiàn)兩次標(biāo)記得處理兩次標(biāo)記DADRARADRDRARRDDAA最后標(biāo)記RDAA第三十四頁，共九十二頁，2022年，8月28日編碼方案輪廓號：自然碼輪廓灰度：自然碼坐標(biāo)起點(diǎn)：自然碼輪廓碼：Flame方向碼輪廓號輪廓灰度起點(diǎn)坐標(biāo)輪廓碼編碼0000000000010101010101011010101010100000000011111010……010101001001011010111100001010011111101010110001000000011011Flame方向碼解碼：每完成一個輪廓的描繪，將該輪廓內(nèi)填充為對應(yīng)的輪廓灰度。該圖像如果用自然碼編碼共用7×8×8＝448bit；采用輪廓編碼共用3×16＋2×16＋92＝172bit。同灰度面積越大，效果越明顯?？梢允?位第三十五頁，共九十二頁，2022年，8月28日編碼應(yīng)用舉例3——圖像的游程編碼圖像的每一行可以看成是由i個長度不等，灰度級為k個的像素組成。l1l2l3l4l5像素坐標(biāo)灰度級對每一行像素用(li,gk)表達(dá)，選擇恰當(dāng)編碼方式對其進(jìn)行編碼(甚至直接保存)，即可對圖像進(jìn)行壓縮。圖像中等灰度的面積越大，壓縮效果越好。對上圖表示的某一行像素而言：(l1,g1)，(l2,g3)，(l3,g2)，(l4,g5)，(l5,g4)g1g2g3g4g5第三十六頁，共九十二頁，2022年，8月28日編碼應(yīng)用舉例4——算術(shù)編碼特點(diǎn)：遞推式編碼。編碼條件：必須知道各符號信息的概率例：已知符號源{a1,a2,a3,a4}，已知各符號出現(xiàn)的概率分別為p(a1)=0.2，p(a2)=0.2，p(a3)=0.4，p(a4)=0.2，現(xiàn)需對a1a2a3a3a4編碼。01a1a2a3a400.2a1a2a3a40.06240.0688a1a2a3a40.0560.072a1a2a3a40.040.08a1a2a3a4a1a2a3a3a40.06752在最后一個符號的區(qū)間內(nèi)[0.06752,0.0688]內(nèi)的任意的一個實數(shù)就可以表示整個序列(碼長盡可能的短)。如0.068。(0.04/10)×4+0.04=0.056(0.04/10)×8+0.04=0.072第三十七頁，共九十二頁，2022年，8月28日算術(shù)編碼的解碼：條件同上，給定編碼0.0676059解碼方法：排列概率、選擇展開區(qū)間去逼近被解碼字區(qū)間。01a1a2a3a400.2a1a2a3a40.06240.0688a1a2a3a40.0560.072a1a2a3a40.040.08a1a2a3a4a1a2a3a3a40.067520.067520.0688a1a2a3a40.067520.067776a1a2a3a40.0675993680.067607426a1a2a3a40.067591320.06761144a1a2a3a40.06757120.0676224a1a2a3a4a1a2a3a3a40.0676058064解碼結(jié)果：a1a2a3a3a4a1a2a3a3a4被編碼的信息長度應(yīng)是已知的第三十八頁，共九十二頁，2022年，8月28日五、二值圖像編碼1、二值圖像編碼——跳過白塊編碼(WBS)二值圖像是指只有兩個灰度級的圖像。例如文字組成的文件掃描圖、氣像圖、工程圖、指紋卡、軍用態(tài)勢圖…。分辨率越高，圖像細(xì)節(jié)越清晰，因而圖像質(zhì)量越高。但是其代價是表示一幅圖像的數(shù)據(jù)量也越大，這使得傳輸時間、存儲容量、處理計算時間都要付出更高的代價。CCITT(國際電話與電報顧問委員會)建議采用兩種分辨率：1728像素/行(8取樣/mm)，3.5行/mm；1728像素/行(8取樣/mm)，7.7行/mm。第三十九頁，共九十二頁，2022年，8月28日在一般情況下，用主觀測試方法確定結(jié)果表明，對中等質(zhì)量要求，如我國常用的公文紙幅面190mm×270mm，如果分辨率取5點(diǎn)/mm，直接編碼所需bit數(shù)：190×270×52=1282500bit≈1.3Mbit如果用常用的速率為2.4kbit/s的傳真機(jī)傳送，需要9分鐘。如要達(dá)到CCITT規(guī)定的三類傳真機(jī)的傳輸標(biāo)準(zhǔn)，即傳輸一幀公文約需1分鐘，則需將數(shù)據(jù)壓縮9倍。第四十頁，共九十二頁，2022年，8月28日1)、一維跳過白塊編碼基本原理：大多數(shù)二值圖像中的黑像素只占整個圖像的一小部分，若能跳過白色像素，只對黑色像素編碼，則表示圖像的比特數(shù)就能減少，平均比特數(shù)就能大大降低。步驟：將圖像的每條掃描線分成若干段，每一段的像素個數(shù)為n；對全部是白色的像素用0表示；對至少有一個黑像素的線段用n+1個比特表示，第一個比特為1，其余n比特采用直接編碼。第四十一頁，共九十二頁，2022年，8月28日舉例：黑白白黑——11001

白白白白——0設(shè)長度為n的像素段出現(xiàn)全白的概率為Pw，則一維WBS編碼每一段的平均碼長bn為：例：某二值圖像行有40個黑白像素(40位)。n=4時0011110011111000共16位n=8時01111000001111100000共20位n=5時01000111100001011110000共23位可見，分段大小的不同，編碼效率也不同。第四十二頁，共九十二頁，2022年，8月28日2)、二維跳過白塊編碼將一維WBS的像素段推廣為像素塊。設(shè)像素塊大小為M×N，全白像素塊用“0”表示，否則用M×N個比特來直接編碼，并在編碼前加一個1作為標(biāo)識位。則每塊像素的平均碼長R為若按4×4分塊：5位0＋5×(16+1)位1＝90位編碼。其中：Pw為像素塊出現(xiàn)全白的概率例：某二值圖像4行有160個黑白像素。如果此像素為白第四十三頁，共九十二頁，2022年，8月28日3)、自適應(yīng)跳過白塊編碼根據(jù)圖像的局部結(jié)構(gòu)或統(tǒng)計特性，改變像素塊的大小，進(jìn)一步提高壓縮效果，這就是所謂的自適應(yīng)WBS編碼。改進(jìn)型的一維WBS編碼：對于一維的WBS編碼，如果一條掃描線全為白像素時，則用1比特“0”表示，否則用正常的一維WBS編碼。自適應(yīng)的WBS編碼可以使得表示圖像的bit數(shù)下降很多，但是增加了自適應(yīng)增加了譯碼的復(fù)雜性。第四十四頁，共九十二頁，2022年，8月28日2、二值圖像編碼——游程編碼

主要思路是將一個連續(xù)相同值的串用一個代表值和串長來代替。對于圖像編碼，可以定義沿特定方向上具有相同灰度值的相鄰像元為一組，其延續(xù)長度稱之為延續(xù)的行程，簡稱為“游程”。游程終點(diǎn)位置由前一游程終點(diǎn)的相對距離確定，這樣就可以由游程長度串來表示圖像數(shù)據(jù)。游程編碼一般不直接應(yīng)用于多灰度圖像，而比較適合于二值圖像的編碼，例如傳真圖像的編碼等。為了達(dá)到較好的壓縮效果，有時游程編碼和其它一些編碼方法混合使用。第四十五頁，共九十二頁，2022年，8月28日1)、一維游程長度編碼(RLC)對二值圖像的每一掃描行來看，總是由若干段連著的黑像素段和連著的白像素段組成，分別稱為“黑長”和“白長”。黑長和白長總是交替發(fā)生。對于不同長度按其發(fā)生概率分配以不同長度的碼字，這就是游程長度編碼(RLC)。設(shè)二值圖像中有長度為1,2,…，N等不同長度的黑長和白長，N為一個掃描行的像素數(shù)。步驟：對每一掃描行從左到右按游程長度編碼，且每行都由白色游程開始(其長度可以是0)。用最優(yōu)變長編碼或亞最優(yōu)變長編碼對游程長度進(jìn)行編碼。第四十六頁，共九十二頁，2022年，8月28日一維游程長度(RLC)編碼舉例各行編碼：1，7，4，4，4，122，7，3，12，4，43，7，2，4，1，2，1，4，1，74，7，1，4，4，4，4，4概率統(tǒng)計按大小排列：4，1，7，2，12，3用哈夫曼編碼方案編碼00，011，1，1，1，010100100，011，01011，01010，1，101011，011，0100，1，00，0100，00，1，00，0111，011，00，1，1，1，1，1

共計：13＋19＋27＋11＝70(直接編碼為128位)符號碼字411007011201001201010301011第四十七頁，共九十二頁，2022年，8月28日2)、二維游程長度編碼(RAC)RAC編碼舉例各行編碼：第一行：1，7，4，4，4，12——RLC編碼第二行：1，1，3，4，4，4第三行：2，1，2，4，1，2，1，4，1，3第四行：3，1，1，4，3，4，3，4第四十八頁，共九十二頁，2022年，8月28日3)、預(yù)測差值量化編碼(PDQ)游程長度編碼只利用了沿掃描線方向的像素間的相關(guān)性。如果進(jìn)一步利用行間像素相關(guān)性則可能達(dá)到更高的壓縮效率，這就是預(yù)測差值量化編碼。PDQ實際是RLC基礎(chǔ)上改進(jìn)得到的二維游程編碼，它不是對游程長度本身進(jìn)行編碼，而是對掃描線之間的代表兩個游程長度變化的差值進(jìn)行編碼，但相應(yīng)的規(guī)則較多。第四十九頁，共九十二頁，2022年，8月28日六、預(yù)測編碼預(yù)測編碼是統(tǒng)計冗余數(shù)據(jù)壓縮理論的三個重要分支之一(直接編碼、預(yù)測編碼、變換編碼)。預(yù)測編碼的理論基礎(chǔ)是現(xiàn)代統(tǒng)計學(xué)和控制論，它主要減少了數(shù)據(jù)在時間和空間上的相關(guān)性。對于靜止圖像來說，預(yù)測編碼將被圖像變換編碼所取代。而預(yù)測編碼對于視頻信號來說，它充分利用了連續(xù)幀之間的統(tǒng)計冗余性，是當(dāng)今主流技術(shù)并且還會流行于未來。第五十頁，共九十二頁，2022年，8月28日1、預(yù)測編碼的基本原理預(yù)測編碼是根據(jù)圖像數(shù)學(xué)模型利用以往的樣本值對于新樣本值進(jìn)行預(yù)測，然后將樣本的實際值與其預(yù)測值相減得到一個誤差值，對這一誤差值進(jìn)行編碼。如果模型足夠好且樣本序列在時間上相關(guān)性較強(qiáng)，那么誤差信號的幅度將遠(yuǎn)遠(yuǎn)小于原始信號，從而可以用較少的碼字對其差值量化得到較大的數(shù)據(jù)壓縮效果。如果能精確地預(yù)測數(shù)據(jù)源輸出，那就不存在關(guān)于數(shù)據(jù)源的不確定性。第五十一頁，共九十二頁，2022年，8月28日然而沒有一個實際的系統(tǒng)能找到其完整的數(shù)學(xué)模型，我們能找到的最好預(yù)測器是以某種最小化的誤差對下一個采樣進(jìn)行預(yù)測的預(yù)測器。通常預(yù)測器的設(shè)計不是利用數(shù)據(jù)源的實際數(shù)學(xué)模型，因為數(shù)據(jù)源的實際數(shù)學(xué)模型是非常復(fù)雜，而且是時變的。實驗結(jié)果表明以最小均方預(yù)測誤差設(shè)計的預(yù)測器不但能獲得最小均方預(yù)測誤差，同時在視覺效果上也是比較好的。第五十二頁，共九十二頁，2022年，8月28日預(yù)測編碼原理——線性預(yù)測設(shè)時間序列像元如下XM，XM-1，XM-2，……，X1，Xn，Xn+1，……則對Xn的線性估值可表述為：為了得到最佳的預(yù)測系數(shù)，定義均方誤差準(zhǔn)則：求使en2最小的ai：被預(yù)測數(shù)據(jù)歷史數(shù)據(jù)看成常數(shù)不可能=0第五十三頁，共九十二頁，2022年，8月28日有：當(dāng)i=1,2,…,M時若定義Xi、Xj的協(xié)方差為Rij=E[Xi,Xj]則上式可寫為：且可以證明|ai|<1。由于Rij是可以求出來的，因此ai也是可以求出來的。求取偏差的方差——觀察其離散程度。Xnp

(Xn)e2np

(e2n)對稱方陣第五十四頁，共九十二頁，2022年，8月28日若Rij=E[Xi,Xj]，定義相關(guān)系數(shù)：ρij=E[Xi,Xj]

/E[Xi2]0≤ρij≤1則Rij等式可以寫成如果預(yù)測的比較準(zhǔn)確則近似等于Xn第五十五頁，共九十二頁，2022年，8月28日顯然，M=1時，有：在前面公式推導(dǎo)時，前提條件是各點(diǎn)的均值為0。但在實際的圖像中，圖像點(diǎn)的均值不可能等于0，總有一個值m。因此，要保證上式成立應(yīng)有：上式稱為最佳一維一階預(yù)測公式。其中：使用預(yù)測編碼方式可以實現(xiàn)無損編碼——在預(yù)測過程中不進(jìn)行各種舍入的量化；以及有損編碼——在預(yù)測過程中進(jìn)行了適當(dāng)?shù)纳崛牒土炕?。實際上，前面推導(dǎo)的公式是不好用的。因為期望值與自相關(guān)系數(shù)是不容易得到的。第五十六頁，共九十二頁，2022年，8月28日2、無損編碼實例——一階DPCM編碼設(shè)預(yù)測器為一階預(yù)測器：偏差為：用其對給定圖像進(jìn)行編碼。對選擇恰當(dāng)?shù)木幋a方式進(jìn)行編碼(如前例中的變形移位碼)。編碼器解碼器令a1=1第五十七頁，共九十二頁，2022年，8月28日3、有損編碼實例——DM(差值調(diào)制)編碼為了進(jìn)一步提高壓縮率，可使用DM編碼方案。設(shè)預(yù)測器為一階預(yù)測器：，其中a1=1；偏差為：用其對給定圖像進(jìn)行編碼。令+c=1，-c=0對進(jìn)行編碼，每像素僅一位(每行的第一個像素用自然碼編碼)。編碼器解碼器第五十八頁，共九十二頁，2022年，8月28日DM(差值調(diào)制)編碼存在地問題造成顆粒噪聲形成亮暗噪聲點(diǎn)，噪聲的強(qiáng)弱取決于c的選擇。當(dāng)圖像的灰度發(fā)生劇烈變化時，預(yù)測值跟不上變化，解碼后會造成邊緣的不清晰——斜率過載現(xiàn)像。4、最優(yōu)量化——高階預(yù)測(有損編碼)如果使用高階預(yù)測，M>1，由于|ai|<1，則偏差會出現(xiàn)小數(shù)，且為各種可能值，如：0.312、0.1237、4.7856。為了對其進(jìn)行編碼，必須要進(jìn)行量化。最簡單的方法是取整運(yùn)算：當(dāng)像素間的相關(guān)性較強(qiáng)時，誤差很大。第五十九頁，共九十二頁，2022年，8月28日量化方案的選擇如何對偏差信息進(jìn)行量化，需幾級量化才能使解碼圖像更接近原始圖像，量化時怎樣才能使量化誤差最小等問題是我們關(guān)心的問題。所謂量化問題，簡言之就是為輸入按某種規(guī)律分配碼字的過程。常見的量化方式為均勻量化，如A/D。即給定輸入s，如果s落在[s0,s1)之間則賦予碼字t0；如果s落在[s1,s2)之間則賦予碼字t1；如果s落在[si-1,si)之間則賦予碼字ti-1；…………重建層決策層t0t1t2t3tk+1tk-1tk輸入s第六十頁，共九十二頁，2022年，8月28日均勻量化的最小量化誤差設(shè)想si、ti有同樣的量綱，問如何量化si，量化誤差最小。設(shè)s在其可量化范圍內(nèi)的概率密度p(s)為常數(shù)——各可能出現(xiàn)值得概率相等。構(gòu)造均方誤差函數(shù)：如果設(shè)si、ti都是變化的，問：si、ti如何取值時均方誤差最小。重建層是均勻的，A/D轉(zhuǎn)換恰是如此。第六十一頁，共九十二頁，2022年，8月28日概率密度p(s)不為常數(shù)時，有可見，重建層是不均勻的——每個titi+1的寬度取決于s在[si,si+1)區(qū)間內(nèi)分布的概率密度。對預(yù)測偏差而言，其概率密度為Laplace分布：由此構(gòu)造出的量化器稱為Lloyd-Max量化器(P165)。第六十二頁，共九十二頁，2022年，8月28日Lloyd-Max量化器假設(shè)預(yù)測方程的預(yù)測結(jié)果足夠準(zhǔn)，用8級最優(yōu)量化已能滿足要求，也就是說偏差范圍在-2.994~2.994之間，既便是采用自然碼編碼，也可以將256級灰度的圖像壓縮近50％。如果采用變長碼壓縮率會更高。0.707－0.70700.395－0.39501.810－1.8100.222－0.22200.785－0.7851.576-1.5762.994-2.994110010111010100100000001001000110100

00111000110000011110110010100001001102級量化4級量化表示決策區(qū)域自然碼編碼哈夫曼編碼第六十三頁，共九十二頁，2022年，8月28日5、二維和三維預(yù)測對一幅圖像而言，被預(yù)測點(diǎn)的值不僅與本行的點(diǎn)相關(guān)，而且也與前一行的鄰近點(diǎn)相關(guān)，如果將其考慮進(jìn)來，預(yù)測會更加準(zhǔn)確?？紤]到行間相關(guān)性的預(yù)測稱為二維預(yù)測。一個常用的四階預(yù)測公式為：X6X2X3X4X7X5X1X前一行當(dāng)前行同理，有時圖像幀之間也有相關(guān)性。如電視圖像的每幀之間具有較高的相關(guān)性?？紤]到幀間相關(guān)性的預(yù)測稱為三維預(yù)測。應(yīng)用領(lǐng)域：電視圖像、可視電話。第六十四頁，共九十二頁，2022年，8月28日編碼器解碼器第1幀預(yù)測幀2第2幀偏差幀2預(yù)測幀3第3幀偏差幀3預(yù)測幀4第4幀偏差幀4預(yù)測幀4第4幀偏差幀4第1幀預(yù)測幀2第2幀偏差幀2預(yù)測幀3第3幀偏差幀3預(yù)測幀4第4幀偏差幀4預(yù)測幀4第4幀偏差幀4

第一幀中使用一維或二維預(yù)測編碼第六十五頁，共九十二頁，2022年，8月28日七、變換編碼

1、變換編碼中的有損與無損編碼“無損”編碼：由于經(jīng)過正交變換后“圖像”，都具有能量集中的特點(diǎn)——絕大部分“像素”為0或很小，它們占用的碼位相對較少，所以，直接對變換“圖像”進(jìn)行編碼，會比對原圖像進(jìn)行編碼需要的碼位少。由于絕大多數(shù)圖像變換都會產(chǎn)生帶有經(jīng)舍入的小數(shù)點(diǎn)的變換矩陣，一般而言，變換編碼不可能做到絕對“無損”。有損編碼：將經(jīng)過正交變換后“圖像”中能量較集中的“像素”依照某種準(zhǔn)則保留，而將其它“像素”置為0，然后對其進(jìn)行編碼，這樣會比對原圖像進(jìn)行編碼需要的碼位少的多。但解碼后，圖像不可能恢復(fù)原來狀態(tài)。第六十六頁，共九十二頁，2022年，8月28日2、變換編碼的基本步驟選擇變換形式；變換編碼的一個極其重要的作用是將信號中的能量盡可能集中在少數(shù)幾個系數(shù)上，選擇的準(zhǔn)則應(yīng)是集中度較高的變換。幾乎所有的圖像變換編碼器都采用基于分塊的DCT變換。對給定圖像按某種方案(如分塊)進(jìn)行變換。對這變換系數(shù)進(jìn)行按給定的規(guī)則進(jìn)行量化，這樣圖像壓縮率有明顯的提高(如：DCT變換之后通常是均勻量化)。最后按指定編碼方式編碼(如：哈夫曼編碼)。第六十七頁，共九十二頁，2022年，8月28日3、圖像壓縮為什么選中的余弦變換實變換，且在給定條件下的重建誤差較小。測試方法：對同一幅具有代表性的圖像，將其分成n×n的子圖像，計算各子圖像的變換系數(shù)(求其變換“圖像”)，將變換系數(shù)由小到大截除75％，求取截除系數(shù)后的變換“圖像”的反變換，計算均方根誤差后比較。3.02.52.01.51.00.50.02×24×48×816×1632×32傅立葉余弦哈達(dá)瑪131664第六十八頁，共九十二頁，2022年，8月28日4、國際標(biāo)準(zhǔn)簡介——JPEG標(biāo)準(zhǔn)JPEG的產(chǎn)生JPEG是“聯(lián)合圖片專家組”(JointPhotograhicCodingExpertsGroup)的簡稱。是由ISO(國際標(biāo)準(zhǔn)化組織)和CCITT(國際電話與電報顧問委員會)于1986年聯(lián)合成立的一個標(biāo)準(zhǔn)起草小組，該小組于1991年提出ISOCD10918標(biāo)準(zhǔn)建議草案，1992年成為國際標(biāo)準(zhǔn)ISO/IEC。后來，通常將該標(biāo)準(zhǔn)稱為JPEG。

JPEG標(biāo)準(zhǔn)主要涉及連續(xù)色調(diào)(灰度和彩色)靜止圖像的壓縮編碼。它提供了一種適合大多數(shù)應(yīng)用場合的簡單高效的圖像編碼方案。下面，以灰度圖像為例介紹JPEG標(biāo)準(zhǔn)。第六十九頁，共九十二頁，2022年，8月28日5、JPEG基本系統(tǒng)圖像分割系數(shù)編碼量化FDCT量化表碼表編碼器系數(shù)解碼圖像接拼IDCT反量化量化表碼表解碼器6、編碼、解碼過程1)、將圖像分成8×8的圖像塊，以其為基本單位進(jìn)行編碼。2)、對每個8×8的圖像塊進(jìn)行FDCT變換，得到變換系數(shù)矩陣。第七十頁，共九十二頁，2022年，8月28日3)、量化。將每個DCT系數(shù)除以各自的量化步長并取整得到量化系數(shù)。4)、將量化后的系數(shù)分成直流系數(shù)和交流系數(shù)，查對應(yīng)表格對量化系數(shù)編碼。5)、用Z型掃描的方法形成數(shù)據(jù)流，對數(shù)據(jù)流查Huffman表進(jìn)行編碼。9910310011298959272101120121103877864499211310481645535247710310968563722186280875129221714566957402416131455605826191412126151402416101116亮度量化表S(u,v)第七十一頁，共九十二頁，2022年，8月28日7、JPEG編碼應(yīng)用舉例158158158163161161162162157157157162163161162162157157157160161161161161155155155162162161160159159159159160160162161159156156156158163160155150156156156159156153151144155155155155153149144139原始數(shù)字圖像0－112－2－42－3－1120－100－1－111－1020211－1021－1－1000110－2－70－1－102－2－9－11－100－3－3－6－17－231－3－22－5－12－11260DCT系數(shù)圖像0000000000000000000000000000000000000000000000－1－1000000－1－200000－1079系數(shù)量化后圖像數(shù)據(jù)流：79,0,-2,-1,-1,-1,0,0,-1,0,0,0,0,…….,0直流分量第七十二頁，共九十二頁，2022年，8月28日編碼示例對直流分量而言，由于兩塊之間的直流分量非常接近所以JPEG對量化后的直流系數(shù)采用如下方法對ΔF(0,0)編碼：ΔF(0,0)=Fi(0,0)-Fi-1(0,0)就本例而言，設(shè)ΔF(0,0)＝2，查直流系數(shù)表，形成編碼：類型碼的編碼＋量化值范圍的編碼(使用自然碼，負(fù)數(shù)用反碼)。有：22，201110對交流分量而言，采用游程編碼。由若干個0(也可以沒有)和一個非0值組成一個編碼的基本單位。就本例而言，在0,-2,-1,-1,-1,0,0,-1,0,0,0,0,…….,0中，0,-2為一個編碼單位；有3個-1的編碼單位；最后為EOB編碼單位。每個編碼單位下式構(gòu)成：(游程/類型碼)的編碼＋量化值范圍的編碼(使用自然碼，負(fù)數(shù)用反碼)類型：由非0值查直流系數(shù)表得到。游程：基本編碼單位中0的個數(shù)。第七十三頁，共九十二頁，2022年，8月28日直流系數(shù)、交流系數(shù)量化表亮度分量直流系數(shù)編碼表-2047~-1024,1024~2047-1023~-512,512~1023-511~-256,256~511-255~-128,-128~255-127~-64,64~127-63~-32,32~63-31~-16,16~31-15~-8,8~15-7~-4,4~7-1,-2,2,3-1,10量化值范圍(使用自然碼)11109876543210類型碼類型碼的Huffman碼字00111110010111001111110100101110111111110111111101111110第七十四頁，共九十二頁，2022年，8月28日亮度分量交流系數(shù)編碼表(負(fù)數(shù)用反碼表示)1111111110001110……111110011110011111111110001000……1101111001111111110000011……001010Huffman碼字游程/類型碼Huffman碼字游程/類型碼2/A……2/22/11/A……1/21/10/A……0/10/0(EOB)5/A……5/25/14/A……4/24/13/A……3/23/11111111110100101……11110101110011111111110011101……11111110001110111111111110010101……111110111111010類型碼的形成同亮度分量直流系數(shù)編碼表第七十五頁，共九十二頁，2022年，8月28日最終編碼1010111000000000000110110101110編碼EOB2/1，-10/1，-10/1，-10/1，-11/2，-22，2類型表示0…..00-1-1-1-10-279量化值對于本例而言，可求其編碼的壓縮比等參數(shù)為：(游程/類型碼)的編碼＋量化值范圍的編碼(使用自然碼，負(fù)數(shù)用反碼)第七十六頁，共九十二頁，2022年，8月28日0000000000000000000000000000000000000000000000－13－14000000－12－2400000－1001264解碼及反量化后的圖像158159161162161161159158158159161162162162161160157158160162164164163163156158160162163164163163155157159161162161161160155156157158158157156155156156156156154152150148156156156154152149146144經(jīng)IDCT后的圖像158158158163161161162162157157157162163161162162157157157160161161161161155155155162162161160159159159159160160162161159156156156158163160155150156156156159156153151144155155155155153149144139原始數(shù)字圖像6)、解碼時，對接收到的數(shù)據(jù)流查Huffman表進(jìn)行解碼，得到和編碼器輸出相同的量化系數(shù)，對其進(jìn)行反量化恢復(fù)出DCT系數(shù)。最后，經(jīng)IDCT恢復(fù)圖像。第七十七頁，共九十二頁，2022年，8月28日158158158163161161162162157157157162163161162162157157157160161161161161155155155162162161160159159159159160160162161159156156156158163160155150156156156159156153151144155155155155153149144139原始數(shù)字圖像0-112-2-42-3-1120-100-1-111-1020211-1021-1-1000110-2-70-1-102-2-9-11-100-3-3-6-17-231-3-22-5-12-11260DCT系數(shù)圖像9910310011298959272101120121103877864499211310481645535247710310968563722186280875129221714566957402416131455605826191412126151402416101116亮度量化表S(u,v)0000000000000000000000000000000000000000000000-1-1000000-1-200000-1079系數(shù)量化后圖像JPEG編碼過程回顧第七十八頁，共九十二頁，2022年，8月28日數(shù)據(jù)流：79,0,-2,-1,-1,-1,0,0,-1,0,0,0,0,…….,0最終編碼1010111000000000000110110101110編碼EOB2/1，-10/1，-10/1，-10/1，-11/2，-22，2類型表示0…..00-1-1-1-10-279量化值0000000000000000000000000000000000000000000000-1-1000000-1-200000-10799910310011298959272101120121103877864499211310481645535247710310968563722186280875129221714566957402416131455605826191412126151402416101116亮度量化表S(u,v)解碼后的圖像第七十九頁，共九十二頁，2022年，8月28日0000000000000000000000000000000000000000000000-13-14000000-12-2400000-1001264反量化后的圖像158159161162161161159158158159161162162162161160157158160162164164163163156158160162163164163163155157159161162161161160155156157158158157156155156156156156154152150148156156156154152149146144經(jīng)IDCT后的解壓縮圖像158158158