數(shù)字圖象處理第七章.ppt

《數(shù)字圖象處理第七章.ppt》由會(huì)員分享，可在線閱讀，更多相關(guān)《數(shù)字圖象處理第七章.ppt（92頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、第七講 圖像編碼,一、引言 因?yàn)閿?shù)字圖像的數(shù)據(jù)量特別大，從而對(duì)存儲(chǔ)、處理和傳輸都帶來(lái)了問(wèn)題。如何才能有效的減少數(shù)字圖像的數(shù)據(jù)量而又不丟失或少丟失圖像的信息，就是圖像編碼問(wèn)題減少表達(dá)信息的數(shù)據(jù)量。,引言,圖像信息之所以可被減少或稱被壓縮，是由于圖像信息中有大量的冗余信息。圖像壓縮就是利用了圖像信號(hào)中的冗余度，如數(shù)據(jù)編碼冗余度、心理冗余度(利用人眼視覺(jué)系統(tǒng)的一些特性忽略掉一些不被人眼所察覺(jué)的信號(hào)成分)等，進(jìn)行壓縮。,1、數(shù)據(jù)冗余,如果用n1和n2分別代表相同信息的2個(gè)數(shù)據(jù)集合中的信息載體單位的個(gè)數(shù)，那么第一個(gè)數(shù)據(jù)集合的相對(duì)數(shù)據(jù)冗余RD(相對(duì)于第二個(gè)數(shù)據(jù)集合)定義為： RD=1-1/CR

2、 其中CR稱為壓縮率： CR=n1/n2 例如，對(duì)同一幅512512點(diǎn)的全白圖像，以兩種方式表達(dá)這幅圖像： 每點(diǎn)用8位信息表示 n1=5125128 每點(diǎn)用1位信息表示 n2=5125121 則 RD=1-1/CR11/8=88% CR=n1/n28,,2、冗余的形式,編碼冗余：沒(méi)有充分利用編碼對(duì)像的概率特性而產(chǎn)生的冗余。 設(shè)定義在0,1區(qū)間的離散隨機(jī)變量sk代表圖像的灰度值，每個(gè)sk以概率ps(sk)出現(xiàn)： ps(sk)nk/n k=0,1,,L-1 其中L為灰度級(jí)數(shù)，nk是第k個(gè)灰度級(jí)出現(xiàn)的次數(shù)，n是圖像中像素總個(gè)數(shù)。,若用于表示信息sk的位數(shù)是l(sk)，那么為表示每個(gè)像素所需

3、的平均位數(shù)(碼長(zhǎng))為：,自然碼和變長(zhǎng)碼的例子,RD=1-1/CR1-0.91=9% CR=n1/n23/2.7=1.11 說(shuō)明該圖像有9%的冗余。,自然碼和變長(zhǎng)碼的例子,像素間的冗余 圖像的重要特點(diǎn)之一就是像素間具有某種相關(guān)性。換言之，就是如果相鄰像素值可由本像素值得出，那么像素值原來(lái)的表達(dá)是多余的。 心理視覺(jué)冗余 如果隨著圖像信息表達(dá)位數(shù)的增加，主觀視覺(jué)效果不在增加，那么多于的信息表達(dá)位數(shù)就是心理視覺(jué)冗余。,3、圖像保真度和質(zhì)量,1)客觀保真度原則 均方根誤差 均方信噪比 峰值信噪比 2)主觀保真度原則 優(yōu)秀很好 良好較好 可用稍好 剛可看相同 差較差 不能用很差,Lena.bmp(原圖

4、),Lenna.jpg (壓縮率9.2),Lenna.jpg (壓縮率18.4),Lenna.jpg (壓縮率51.6),二、編碼模型,漢明碼一種糾錯(cuò)碼。漢明指出：如果將3位的冗余加到4位碼字上，則所有單個(gè)位出現(xiàn)的錯(cuò)誤都可以發(fā)現(xiàn)和校正。 編碼： 例如：01011 0 1 0 0 1 0 解碼：對(duì)漢明碼進(jìn)行校驗(yàn)，錯(cuò)誤位置由非 零校驗(yàn)字c4c2c1指出；對(duì)該位求反即可糾 正錯(cuò)誤。如果校驗(yàn)字為零，則解碼結(jié)果為h3h5h6h7。,,信道編碼、解碼器以漢明碼為例,一個(gè)典型的信源壓縮(編碼)系統(tǒng)如圖所示。,通過(guò)時(shí)間軸上采樣和幅度量化將連續(xù)信號(hào)變成離散數(shù)字信號(hào)并對(duì)其進(jìn)行量化。,將信號(hào)中絕大部分能量集中在少數(shù)

5、幾個(gè)變換系數(shù)上，去除信號(hào)中的相關(guān)性,信號(hào)壓縮真正體現(xiàn)在量化階段 。,一般先是游程編碼，然后Huffman編碼或算術(shù)編碼進(jìn)一步提高壓縮比,如果信號(hào)已經(jīng)數(shù)字化,,最終的“無(wú)損”與“有損”編碼的區(qū)別在于： 在編碼過(guò)程中是否是對(duì)全部的“數(shù)據(jù)”進(jìn)行編碼。,,1、設(shè)計(jì)一個(gè)好的圖像編碼器的步驟 要為圖像信號(hào)選擇一個(gè)正確合適的模型；在這個(gè)給定模型框架中優(yōu)化編碼器。 壓縮算法的選擇；數(shù)據(jù)壓縮率、失真度和算法的復(fù)雜度。 2、圖像編碼算法的分類(lèi)： 1)、一類(lèi)是無(wú)損編碼 即在編碼過(guò)程中信息沒(méi)有丟失。 2)、另一類(lèi)是有損編碼 即在編碼過(guò)程中沒(méi)有對(duì)所有信息編碼。,三、編碼器的設(shè)計(jì)原則,3、圖像信息率及編碼效率,一般靜

6、止灰度圖像中每個(gè)像素用8比特來(lái)表示，那么一幅圖像的平均信息率可以用下面的熵值來(lái)表示：,其中pini/n i=0,1,,L-1 表示像素取i級(jí)灰度的概率，i的取值范圍為0（28-1）。H表示該圖像在不失真情況下，每像素編碼所需的最小碼長(zhǎng)；如果對(duì)每像素編碼的碼長(zhǎng)小于H，則解 碼后的圖像會(huì)產(chǎn)生失真。,4、最佳編碼定理,主要內(nèi)容：若對(duì)一幅圖像進(jìn)行編碼，將出現(xiàn)概率較高的信息(出現(xiàn)概率較高的像素值)賦予較短的碼字；反之，將出現(xiàn)概率較低的信息(出現(xiàn)概率較低的像素值)賦予較長(zhǎng)的碼字；如果碼字長(zhǎng)度嚴(yán)格按照所對(duì)應(yīng)信息出現(xiàn)的概率大小逆序排列，則這樣編碼結(jié)果的平均碼字長(zhǎng)度一定是小于任何其它排列方式。,衡量編碼優(yōu)劣可

7、用編碼效率作為一個(gè)重要指標(biāo)。,對(duì)最佳編碼定理的簡(jiǎn)單說(shuō)明,設(shè)圖像灰度級(jí)為w1,w2 ,wN； 各級(jí)灰度出現(xiàn)的概率分別為p1,p2 ,pN(由大到小)； 編碼器賦予各級(jí)灰度對(duì)應(yīng)的碼字長(zhǎng)度分別為t1,t2 ,tN (由小到大) ；則編碼后圖像平均碼字長(zhǎng)度R應(yīng)為： 令：R1為嚴(yán)格按最優(yōu)編碼定理規(guī)定的原則編碼的平均碼字長(zhǎng)度；R2為在編碼過(guò)程中將任意兩個(gè)灰度級(jí)不按最優(yōu)編碼定理規(guī)定的原則編碼的平均碼字長(zhǎng)度。 依最優(yōu)編碼定理的結(jié)論應(yīng)有R2R1R。 只要證明R0即可,令第m和n個(gè)灰度級(jí)出現(xiàn)的概率分別為pm，pn，且 pmpn；對(duì)應(yīng)的碼字長(zhǎng)度分別為tm，tn，且 tmtn(不符合嚴(yán)格逆序的原則)。構(gòu)造下列運(yùn)算：,

8、注意：概率和字長(zhǎng)均為正數(shù)。,不按定理的碼長(zhǎng),按定理的碼長(zhǎng),說(shuō)明不按定理編碼的平均碼長(zhǎng)一定大于按定理編碼的平均碼長(zhǎng),,說(shuō)明運(yùn)算構(gòu)造的合理性,5、編碼的唯一可譯碼(單義碼)原則,一個(gè)能唯一的被譯出、不會(huì)產(chǎn)生歧義的編碼序列稱為唯一可譯碼編碼(單義碼) 。這樣的編碼序列應(yīng)滿足以下兩個(gè)條件： 編碼中的任何一個(gè)碼字都不是另一個(gè)碼字的簡(jiǎn)單續(xù)長(zhǎng)代碼由一個(gè)碼字簡(jiǎn)單添加一些碼元而構(gòu)成一個(gè)新的碼字。 注意：非續(xù)長(zhǎng)碼一定是單義碼；而單義碼不一定是非續(xù)長(zhǎng)碼。 編碼序列應(yīng)為單義代碼序列，即滿足Kraft不等式。,其中：n為編碼序列的編碼個(gè)數(shù)；D為編碼系統(tǒng)的進(jìn)制；ti為第i個(gè)碼字的長(zhǎng)度。,編碼的唯一可譯碼原則的解釋,某編碼

9、序列C=00, 10, 0(0)11, 101對(duì)應(yīng)信息a,b,c,d 編碼序列C滿足Kraft不等式，所以C是單義代碼。 例：某編碼序列C=101, 10, 00, 10 dbab 某編碼序列C=0, 01, 1,11對(duì)應(yīng)信息a,b,c,d 編碼序列C不滿足Kraft不等式，所以C不是單義代碼。 例：某編碼序列C=0, 1, 11, 0, 11 acdad bdbc ? 所有應(yīng)用于信號(hào)的編碼，都應(yīng)滿足編碼的唯一可譯碼原則。,四、簡(jiǎn)單編碼方法,哈夫曼編碼是一種利用信息符號(hào)概率分布特性的變字長(zhǎng)的編碼方法。對(duì)于出現(xiàn)概率大的信息符號(hào)編以短字長(zhǎng)的碼，對(duì)于出現(xiàn)概率小的信息符號(hào)編以長(zhǎng)字長(zhǎng)的碼。 具體步驟：

10、分配碼字長(zhǎng)度時(shí)，首先將出現(xiàn)概率最小的兩個(gè)符號(hào)的概率相加，合成一個(gè)概率； 第二步把這個(gè)合成概率看成是一個(gè)新組合符號(hào)的概率。 重復(fù)上述做法，直到最后只剩下兩個(gè)符號(hào)的概率為止。 完成以上概率相加順序排列后，再反過(guò)來(lái)逐步向前進(jìn)行編碼； 每一步有二個(gè)分支，各賦予一個(gè)二進(jìn)制碼，可以對(duì)概率大的編碼賦為0，概率小的編碼賦為1。,1、哈夫曼編碼最優(yōu)變長(zhǎng)編碼,哈夫曼編碼示例,某圖像中的一個(gè)子集如圖所示，其哈夫曼編碼為(逐行a2 a6 a2 a6 a4 a5 a2 a3 a1)： 1 00 1 00 0100 01011 1 01010 001 共24位 如果用每個(gè)符號(hào)3位自然碼編碼： 共需27位；,,,,,,,,

11、,,,,,,,設(shè)某一幅圖象共有8個(gè)灰度級(jí)，各灰度級(jí)出現(xiàn)概率分別為： 試對(duì)此圖象進(jìn)行Huffman編碼。,計(jì)算上例的編碼效率,圖像的熵、平均碼字長(zhǎng)度、編碼效率,若按自然碼編碼： H = 2.14 Lavg = 3 編碼效率 = 71.3%,之所以沒(méi)有達(dá)到H=2.14的水平，是因?yàn)樽珠L(zhǎng)是整數(shù)。,哈夫曼編碼在使用中出現(xiàn)的問(wèn)題,1、編碼過(guò)程太復(fù)雜 2、對(duì)每個(gè)文件的編碼是不一樣的 3、解碼器的構(gòu)造不一致 4、壓縮文件中必須包含解碼信息 針對(duì)上述問(wèn)題，常常采用一些亞最優(yōu)編碼 只要對(duì)文件信息的統(tǒng)計(jì)參數(shù)已知，可直接用亞最優(yōu)編碼對(duì)其進(jìn)行壓縮。,2、亞最優(yōu)可變長(zhǎng)編碼,哈夫曼編碼為最優(yōu)編碼。但在使用過(guò)程中有

12、不便之處：要對(duì)編碼對(duì)像進(jìn)行概率統(tǒng)計(jì)，不利于快速編碼。如果對(duì)某一類(lèi)編碼對(duì)像的統(tǒng)計(jì)統(tǒng)計(jì)規(guī)律有一定的了解，即可利用一些亞最優(yōu)變長(zhǎng)編碼技術(shù)得到近似最優(yōu)的編碼結(jié)果。,亞最優(yōu)可變長(zhǎng)編碼,常見(jiàn)的亞最優(yōu)變長(zhǎng)編碼有： 截?cái)喙蚵a對(duì)最有可能出現(xiàn)的M個(gè)符號(hào)進(jìn)行哈夫曼編碼；將其余的符號(hào)概率相加，查出對(duì)應(yīng)的哈夫曼編碼作為前綴，后跟由0開(kāi)始的自然碼對(duì)剩余的信息進(jìn)行編碼。 哈夫曼平移碼 重新排列信源符號(hào)使它們的概率單減； 將符號(hào)總數(shù)分成相同大小的符號(hào)塊； 對(duì)所有塊中的各個(gè)元素采用同樣方法編碼； 對(duì)每個(gè)塊加上專門(mén)的移上移下符號(hào)以區(qū)別它們。每當(dāng)解碼器認(rèn)出1個(gè)移上移下符號(hào)，它就相對(duì)事先定義的參考?jí)K移上移下1個(gè)塊。具體到平移哈夫

13、曼碼，則在用哈夫曼方法對(duì)參考?jí)K編碼前先將概率賦給平移符號(hào)。,編碼應(yīng)用舉例1圖像的差分編碼,某衛(wèi)星圖像f為23403240像素，灰度量化為128級(jí)。如果采用自然碼編碼，共需使用23403240750Mbit。若每天接收30幅，則共需使用約50301500Mbit。圖像的直方圖如圖所示。構(gòu)造差分變換矩陣A，對(duì)圖像f進(jìn)行變換。,A為(23403240) (23403240)方陣 f為 (23403240)1列向量； g為(23403240)1列向量,圖像以堆疊向量表示,直方圖的比較,可以看出： 由于圖像數(shù)據(jù)的相關(guān)性，差分?jǐn)?shù)據(jù)的方差(數(shù)據(jù)的離散程度小)遠(yuǎn)小于灰度數(shù)據(jù)的方差。 根據(jù)最佳編碼定理，對(duì)差分?jǐn)?shù)

14、據(jù)編碼所需的平均碼長(zhǎng)會(huì)遠(yuǎn)小于對(duì)灰度數(shù)據(jù)編碼所需的平均碼長(zhǎng)。,構(gòu)造編碼,構(gòu)造一種變形的A碼(移位碼)，共16個(gè)碼字c1 c2 c3c16 。 c10000， c20001， c30010， c161111 將其中的14個(gè)碼字c2 c3c15分配給差分?jǐn)?shù)據(jù)； c1 、c16 作為指示位。,圖像重構(gòu)：編碼圖像 解碼 逆變換 f = A-1g 壓縮后的平均碼長(zhǎng)為4.3，壓縮61；如果用哈夫曼編碼平均碼長(zhǎng)為3.5，壓縮50 。,對(duì)存在大面積等灰度塊的圖像(可能是直接得到，也可能是通過(guò)某種增強(qiáng)方法得到)可采用圖像輪廓編碼進(jìn)行壓縮。任何一個(gè)灰度區(qū)域，都可以按照某種規(guī)則勾畫(huà)成一個(gè)封閉的等值線。,編碼應(yīng)用舉例

15、2圖像的輪廓編碼,將所有像素標(biāo)記為I 從左上角開(kāi)始逐行尋找起始點(diǎn)并將該點(diǎn)標(biāo)記成IP；能夠成為起始點(diǎn)的條件為該點(diǎn)標(biāo)記為I，并且不在已勾畫(huà)過(guò)的輪廓當(dāng)中。 按“向左看”，“順時(shí)針轉(zhuǎn)”的原則，尋找等灰度I點(diǎn)，按標(biāo)記規(guī)則加注標(biāo)記。 完成一個(gè)封閉輪廓后，尋找新的輪廓起點(diǎn)。直至標(biāo)記完所有輪廓。,勾畫(huà)輪廓及標(biāo)記,新IP點(diǎn)的確定： 從左到右從上到下逐行搜索。 構(gòu)造棧區(qū)，搜索新的一行時(shí)，將棧區(qū)清空。 遇A進(jìn)棧，遇D出棧，遇R不管；如果空棧遇I則為一新的IP點(diǎn)；如果非空棧遇I且該像素的灰度值不同于先前進(jìn)棧A點(diǎn)的灰度值，則該點(diǎn)為一新的IP點(diǎn)，反之不是。,對(duì)于同一像素點(diǎn)上出現(xiàn)兩次標(biāo)記得處理,,A,編碼方案,輪廓號(hào)： 自

16、然碼 輪廓灰度：自然碼 坐標(biāo)起點(diǎn)：自然碼 輪廓碼：Flame方向碼,Flame方向碼,解碼：每完成一個(gè)輪廓的描繪，將該輪廓內(nèi)填充為對(duì)應(yīng)的輪廓灰度。該圖像如果用自然碼編碼共用788448bit；采用輪廓編碼共用31621692172bit。同灰度面積越大，效果越明顯。,可以是8位,,,,編碼應(yīng)用舉例3圖像的游程編碼,圖像的每一行可以看成是由i個(gè)長(zhǎng)度不等，灰度級(jí)為k個(gè)的像素組成。,灰度級(jí),對(duì)每一行像素用(li,gk)表達(dá)，選擇恰當(dāng)編碼方式對(duì)其進(jìn)行編碼(甚至直接保存) ，即可對(duì)圖像進(jìn)行壓縮。圖像中等灰度的面積越大，壓縮效果越好。 對(duì)上圖表示的某一行像素而言： (l1,g1)，(l2,g3)，(l3,

17、g2)，(l4,g5)，(l5,g4),g1,g2,g3,g4,g5,編碼應(yīng)用舉例4算術(shù)編碼,特點(diǎn)：遞推式編碼。 編碼條件：必須知道各符號(hào)信息的概率 例：已知符號(hào)源a1, a2, a3, a4，已知各符號(hào)出現(xiàn)的概率分別為p(a1)=0.2， p(a2) =0.2，p(a3) =0.4，p(a4) =0.2，現(xiàn)需對(duì)a1 a2 a3 a3 a4編碼。,在最后一個(gè)符號(hào)的區(qū)間內(nèi)0.06752,0.0688內(nèi)的任意的一個(gè)實(shí)數(shù)就可以表示整個(gè)序列(碼長(zhǎng)盡可能的短)。如0.068。,(0.04/10)4 +0.04=0.056 (0.04/10)8 +0.04=0.072,,算術(shù)編碼的解碼：條件同上，給定編碼

18、0.0676059,解碼方法：排列概率、選擇展開(kāi)區(qū)間去逼近被解碼字區(qū)間。,解碼結(jié)果： a1 a2 a3 a3 a4 a1 a2 a3 a3 a4 被編碼的信息長(zhǎng)度應(yīng)是已知的,,五、二值圖像編碼,1、二值圖像編碼跳過(guò)白塊編碼(WBS) 二值圖像是指只有兩個(gè)灰度級(jí)的圖像。例如文字組成的文件掃描圖、氣像圖、工程圖、指紋卡、軍用態(tài)勢(shì)圖。 分辨率越高，圖像細(xì)節(jié)越清晰，因而圖像質(zhì)量越高。但是其代價(jià)是表示一幅圖像的數(shù)據(jù)量也越大，這使得傳輸時(shí)間、存儲(chǔ)容量、處理計(jì)算時(shí)間都要付出更高的代價(jià)。 CCITT(國(guó)際電話與電報(bào)顧問(wèn)委員會(huì))建議采用兩種分辨率：1728像素/行(8取樣/mm)，3.5行/mm；1728像素/

19、行(8取樣/mm)，7.7行/mm。,在一般情況下，用主觀測(cè)試方法確定結(jié)果表明，對(duì)中等質(zhì)量要求，如我國(guó)常用的公文紙幅面190mm270mm，如果分辨率取5點(diǎn)/mm，直接編碼所需bit數(shù)： 19027052=1282500bit1.3Mbit 如果用常用的速率為2.4kbit/s的傳真機(jī)傳送，需要9分鐘。如要達(dá)到CCITT規(guī)定的三類(lèi)傳真機(jī)的傳輸標(biāo)準(zhǔn)，即傳輸一幀公文約需1分鐘，則需將數(shù)據(jù)壓縮9倍。,1)、一維跳過(guò)白塊編碼,基本原理： 大多數(shù)二值圖像中的黑像素只占整個(gè)圖像的一小部分，若能跳過(guò)白色像素，只對(duì)黑色像素編碼，則表示圖像的比特?cái)?shù)就能減少，平均比特?cái)?shù)就能大大降低。 步驟： 將圖像的每條掃描線分

20、成若干段，每一段的像素個(gè)數(shù)為n； 對(duì)全部是白色的像素用0表示； 對(duì)至少有一個(gè)黑像素的線段用n+1個(gè)比特表示，第一個(gè) 比特為1，其余n比特采用直接編碼。,舉例：黑白白黑 11001 白白白白 0 設(shè)長(zhǎng)度為n的像素段出現(xiàn)全白的概率為Pw，則一維 WBS編碼每一段的平均碼長(zhǎng)bn為：,例：某二值圖像行有40個(gè)黑白像素(40位)。 n=4時(shí) 0 0 11110 0 11111 0 0 0 共16位 n=8時(shí) 0 111100000 111110000 0 共20位 n=5時(shí) 0 100011 110000 101111 0 0 0 0 共23位 可見(jiàn)，分段大小的不同，編碼效率也不同。,

21、2)、二維跳過(guò)白塊編碼,將一維WBS的像素段推廣為像素塊。設(shè)像素塊大小為MN，全白像素塊用“0”表示，否則用MN個(gè)比特來(lái)直接編碼，并在編碼前加一個(gè)1作為標(biāo)識(shí)位。則每塊像素的平均碼長(zhǎng)R為,若按44分塊：5位05(16+1 )位190位編碼。,其中：Pw為像素塊出現(xiàn)全白的概率 例：某二值圖像4行有160個(gè)黑白像素。,如果此像素為白,3)、自適應(yīng)跳過(guò)白塊編碼,根據(jù)圖像的局部結(jié)構(gòu)或統(tǒng)計(jì)特性，改變像素塊的大小，進(jìn)一步提高壓縮效果，這就是所謂的自適應(yīng)WBS編碼。 改進(jìn)型的一維WBS編碼：對(duì)于一維的WBS編碼，如果一條掃描線全為白像素時(shí)，則用1比特“0”表示，否則用正常的一維WBS編碼。 自適應(yīng)的WBS編碼

22、可以使得表示圖像的bit數(shù)下降很多，但是增加了自適應(yīng)增加了譯碼的復(fù)雜性。,2、二值圖像編碼游程編碼,主要思路是將一個(gè)連續(xù)相同值的串用一個(gè)代表值和 串長(zhǎng)來(lái)代替。 對(duì)于圖像編碼，可以定義沿特定方向上具有相同灰度值的相鄰像元為一組，其延續(xù)長(zhǎng)度稱之為延續(xù)的行程，簡(jiǎn)稱為“游程”。游程終點(diǎn)位置由前一游程終點(diǎn)的相對(duì)距離確定，這樣就可以由游程長(zhǎng)度串來(lái)表示圖像數(shù)據(jù)。游程編碼一般不直接應(yīng)用于多灰度圖像，而比較適合于二值圖像的編碼，例如傳真圖像的編碼等。 為了達(dá)到較好的壓縮效果，有時(shí)游程編碼和其它一些編碼方法混合使用。,1)、一維游程長(zhǎng)度編碼(RLC),對(duì)二值圖像的每一掃描行來(lái)看，總是由若干段連著的 黑像素段和

23、連著的白像素段組成，分別稱為“黑長(zhǎng)”和“白長(zhǎng)”。黑長(zhǎng)和白長(zhǎng)總是交替發(fā)生。對(duì)于不同長(zhǎng)度按其發(fā)生概率分配以不同長(zhǎng)度的碼字，這就是游程長(zhǎng)度編碼(RLC)。 設(shè)二值圖像中有長(zhǎng)度為1, 2, ，N等不同長(zhǎng)度的黑長(zhǎng)和白長(zhǎng)，N為一個(gè)掃描行的像素?cái)?shù)。 步驟： 對(duì)每一掃描行從左到右按游程長(zhǎng)度編碼，且每行都由白色游程開(kāi)始(其長(zhǎng)度可以是0) 。 用最優(yōu)變長(zhǎng)編碼或亞最優(yōu)變長(zhǎng)編碼對(duì)游程長(zhǎng)度進(jìn)行編碼。,一維游程長(zhǎng)度(RLC)編碼舉例,各行編碼： 1，7，4，4，4，12 2，7，3，12，4，4 3，7，2，4，1，2，1，4，1，7 4，7，1，4，4，4，4，4 概率統(tǒng)計(jì)按大小排列：4，1，7，2，12 ，3 用哈夫

24、曼編碼方案編碼 00，011，1，1，1，01010 0100，011，01011，01010，1，1 01011，011，0100，1，00，0100，00，1，00，011 1，011，00，1，1，1，1，1 共計(jì)：1319271170 (直接編碼為128位),2)、二維游程長(zhǎng)度編碼(RAC),RAC編碼舉例 各行編碼： 第一行：1，7，4，4，4，12RLC編碼 第二行：1，1，3，4，4，4 第三行：2，1，2，4，1，2，1，4，1，3 第四行：3，1，1，4，3，4，3，4,3)、預(yù)測(cè)差值量化編碼(PDQ),游程長(zhǎng)度編碼只利用了沿掃描線方向的像素間的相關(guān)性。如果進(jìn)一步利用行間

25、像素相關(guān)性則可能達(dá)到更高的壓縮效率，這就是預(yù)測(cè)差值量化編碼。 PDQ實(shí)際是RLC基礎(chǔ)上改進(jìn)得到的二維游程編碼，它不是對(duì)游程長(zhǎng)度本身進(jìn)行編碼，而是對(duì)掃描線之間的代表兩個(gè)游程長(zhǎng)度變化的差值進(jìn)行編碼，但相應(yīng)的規(guī)則較多。,六、預(yù)測(cè)編碼,預(yù)測(cè)編碼是統(tǒng)計(jì)冗余數(shù)據(jù)壓縮理論的三個(gè)重要分支之一(直接編碼、預(yù)測(cè)編碼、變換編碼)。 預(yù)測(cè)編碼的理論基礎(chǔ)是現(xiàn)代統(tǒng)計(jì)學(xué)和控制論，它主要減少了數(shù)據(jù)在時(shí)間和空間上的相關(guān)性。 對(duì)于靜止圖像來(lái)說(shuō)，預(yù)測(cè)編碼將被圖像變換編碼所取代。 而預(yù)測(cè)編碼對(duì)于視頻信號(hào)來(lái)說(shuō)，它充分利用了連續(xù)幀之間的統(tǒng)計(jì)冗余性，是當(dāng)今主流技術(shù)并且還會(huì)流行于未來(lái)。,1、預(yù)測(cè)編碼的基本原理,預(yù)測(cè)編碼是根據(jù)圖像數(shù)學(xué)模型利用

26、以往的樣本值對(duì)于新樣本值進(jìn)行預(yù)測(cè)，然后將樣本的實(shí)際值與其預(yù)測(cè)值相減得到一個(gè)誤差值，對(duì)這一誤差值進(jìn)行編碼。 如果模型足夠好且樣本序列在時(shí)間上相關(guān)性較強(qiáng)，那么誤差信號(hào)的幅度將遠(yuǎn)遠(yuǎn)小于原始信號(hào)，從而可以用較少的碼字對(duì)其差值量化得到較大的數(shù)據(jù)壓縮效果。 如果能精確地預(yù)測(cè)數(shù)據(jù)源輸出，那就不存在關(guān)于 數(shù)據(jù)源的不確定性。,然而沒(méi)有一個(gè)實(shí)際的系統(tǒng)能找到其完整的數(shù)學(xué)模型，我們能找到的最好預(yù)測(cè)器是以某種最小化的誤差對(duì)下一個(gè)采樣進(jìn)行預(yù)測(cè)的預(yù)測(cè)器。 通常預(yù)測(cè)器的設(shè)計(jì)不是利用數(shù)據(jù)源的實(shí)際數(shù)學(xué)模型，因?yàn)閿?shù)據(jù)源的實(shí)際數(shù)學(xué)模型是非常復(fù)雜，而且是時(shí)變的。 實(shí)驗(yàn)結(jié)果表明以最小均方預(yù)測(cè)誤差設(shè)計(jì)的預(yù)測(cè)器不但能獲得最小均方預(yù)測(cè)誤差，同

27、時(shí)在視覺(jué)效果上也是比較好的。,預(yù)測(cè)編碼原理線性預(yù)測(cè),設(shè)時(shí)間序列像元如下,XM， XM-1， XM-2， ，X1， Xn， Xn+1， 則對(duì)Xn的線性估值可表述為：,為了得到最佳的預(yù)測(cè)系數(shù)，定義均方誤差準(zhǔn)則：,求使en2最小的ai：,被預(yù)測(cè)數(shù)據(jù),歷史數(shù)據(jù),,看成常數(shù),不可能=0,,有：,當(dāng)i=1,2,,M時(shí)若定義Xi、Xj的協(xié)方差為Rij=EXi,Xj則上式可寫(xiě)為： 且可以證明 |ai|<1。由于Rij是可以求出來(lái)的，因此ai也是可以求出來(lái)的。求取偏差的方差觀察其離散程度。,對(duì)稱方陣,若Rij=EXi,Xj，定義相關(guān)系數(shù)： ij= EXi,Xj / EXi2 0ij1 則

28、Rij等式可以寫(xiě)成,,如果預(yù)測(cè)的比較準(zhǔn)確則近似等于Xn,顯然，M=1時(shí)，有：,在前面公式推導(dǎo)時(shí)，前提條件是各點(diǎn)的均值為0。但在實(shí)際的圖像中，圖像點(diǎn)的均值不可能等于0，總有一個(gè)值m。因此，要保證上式成立應(yīng)有：,上式稱為最佳一維一階預(yù)測(cè)公式。其中：,使用預(yù)測(cè)編碼方式可以實(shí)現(xiàn)無(wú)損編碼在預(yù)測(cè)過(guò)程中不進(jìn)行各種舍入的量化；以及有損編碼在預(yù)測(cè)過(guò)程中進(jìn)行了適當(dāng)?shù)纳崛牒土炕?實(shí)際上，前面推導(dǎo)的公式是不好用的。因?yàn)槠谕蹬c自相關(guān)系數(shù)是不容易得到的。,2、無(wú)損編碼實(shí)例一階DPCM編碼,設(shè)預(yù)測(cè)器為一階預(yù)測(cè)器： 偏差為： 用其對(duì)給定圖像進(jìn)行編碼。,對(duì) 選擇恰當(dāng)?shù)木幋a方式進(jìn)行編碼(如前例中的變形移位碼)。,令a

29、1=1,3、有損編碼實(shí)例DM(差值調(diào)制)編碼,為了進(jìn)一步提高壓縮率，可使用DM編碼方案。 設(shè)預(yù)測(cè)器為一階預(yù)測(cè)器： ，其中a1=1；偏差為： 用其對(duì)給定圖像進(jìn)行編碼。,令+c=1， -c=0 對(duì) 進(jìn)行編碼，每像素僅一位(每行的第一個(gè)像素用自然碼編碼)。,DM(差值調(diào)制)編碼存在地問(wèn)題,造成顆粒噪聲形成亮暗噪聲點(diǎn)，噪聲的強(qiáng)弱取決于c的選擇。 當(dāng)圖像的灰度發(fā)生劇烈變化時(shí)，預(yù)測(cè)值跟不上變化，解碼后會(huì)造成邊緣的不清晰斜率過(guò)載現(xiàn)像。 4、最優(yōu)量化高階預(yù)測(cè)(有損編碼) 如果使用高階預(yù)測(cè)，M1，由于|ai|<1，則偏差會(huì)出現(xiàn)小數(shù)，且為各種可能值，如：0.312、0.1237、4.7856。 為了對(duì)其進(jìn)

30、行編碼，必須要進(jìn)行量化。最簡(jiǎn)單的方法是取整運(yùn)算： 當(dāng)像素間的相關(guān)性較 強(qiáng)時(shí)，誤差很大。,量化方案的選擇,如何對(duì)偏差信息進(jìn)行量化，需幾級(jí)量化才能使解碼圖像更接近原始圖像，量化時(shí)怎樣才能使量化誤差最小等問(wèn)題是我們關(guān)心的問(wèn)題。 所謂量化問(wèn)題，簡(jiǎn)言之就是為輸入按某種規(guī)律分配碼字的過(guò)程。常見(jiàn)的量化方式為均勻量化，如A/D。 即給定輸入s，如果s落在s0,s1)之間則賦予碼字t0；如果s落在s1,s2)之間則賦予碼字t1；如果s落在si-1,si)之間則賦予碼字ti-1；,,,均勻量化的最小量化誤差,設(shè)想si 、ti有同樣的量綱，問(wèn)如何量化si，量化誤差最小。設(shè)s在其可量化范圍內(nèi)的概率密度p(s)為常數(shù)各

31、可能出現(xiàn)值得概率相等。構(gòu)造均方誤差函數(shù)：,如果設(shè)si、ti都是變化的，問(wèn)： si、ti如何取值時(shí)均方誤差最小。,重建層是均勻的，A/D轉(zhuǎn)換恰是如此 。,概率密度p(s)不為常數(shù)時(shí)，有,可見(jiàn)，重建層是不均勻的每個(gè)titi+1的寬度取決于s在si,si+1)區(qū)間內(nèi)分布的概率密度 。 對(duì)預(yù)測(cè)偏差而言，其概率密度為L(zhǎng)aplace分布：,由此構(gòu)造出的量化器稱為L(zhǎng)loyd-Max量化器(P165)。,Lloyd-Max量化器,假設(shè)預(yù)測(cè)方程的預(yù)測(cè)結(jié)果足夠準(zhǔn)，用8級(jí)最優(yōu)量化已能滿足要求，也就是說(shuō)偏差范圍在-2.9942.994之間，既便是采用自然碼編碼，也可以將256級(jí)灰度的圖像壓縮近50。如果采用變長(zhǎng)碼壓縮

32、率會(huì)更高。,1100 1011 1010 1001 0000 0001 0010 0011 0100,00111 00011 00000 111 10 110 0101 00001 00110,,,,,,2級(jí)量化,4級(jí)量化,,表示決策區(qū)域,自然碼編碼,哈夫曼編碼,5、二維和三維預(yù)測(cè),對(duì)一幅圖像而言，被預(yù)測(cè)點(diǎn)的值不僅與本行的點(diǎn)相關(guān)，而且也與前一行的鄰近點(diǎn)相關(guān)，如果將其考慮進(jìn)來(lái)，預(yù)測(cè)會(huì)更加準(zhǔn)確?？紤]到行間相關(guān)性的預(yù)測(cè)稱為二維預(yù)測(cè)。一個(gè)常用的四階預(yù)測(cè)公式為：,同理，有時(shí)圖像幀之間也有相關(guān)性。如電視圖像的每幀之間具有較高的相關(guān)性。考慮到幀間相關(guān)性的預(yù)測(cè)稱為三維預(yù)測(cè)。應(yīng)用

33、領(lǐng)域：電視圖像、可視電話。,編碼器,解碼器,,,第1幀,預(yù)測(cè)幀2,第2幀,偏差幀2,,預(yù)測(cè)幀3,第3幀,偏差幀3,,預(yù)測(cè)幀4,第4幀,偏差幀4,,,,預(yù)測(cè)幀4,第4幀,偏差幀4,,,,第1幀,預(yù)測(cè)幀2,第2幀,偏差幀2,,預(yù)測(cè)幀3,第3幀,偏差幀3,預(yù)測(cè)幀4,第4幀,偏差幀4,,預(yù)測(cè)幀4,第4幀,偏差幀4,,,,,,,第一幀中使用一維或二維預(yù)測(cè)編碼,七、變換編碼,1、變換編碼中的有損與無(wú)損編碼 “無(wú)損”編碼：由于經(jīng)過(guò)正交變換后“圖像”，都具有能量集中的特點(diǎn)絕大部分“像素”為0或很小，它們占用的碼位相對(duì)較少，所以，直接對(duì)變換“圖像”進(jìn)行編碼，會(huì)比對(duì)原圖像進(jìn)行編碼需要的碼位少。 由于絕大多數(shù)圖像變

34、換都會(huì)產(chǎn)生帶有經(jīng)舍入的小數(shù)點(diǎn)的變換矩陣，一般而言，變換編碼不可能做到絕對(duì)“無(wú)損”。 有損編碼：將經(jīng)過(guò)正交變換后“圖像”中能量較集中的 “像素”依照某種準(zhǔn)則保留，而將其它“像素”置為0，然后對(duì)其進(jìn)行編碼，這樣會(huì)比對(duì)原圖像進(jìn)行編碼需要的碼位少的多。但解碼后，圖像不可能恢復(fù)原來(lái)狀態(tài)。,2、變換編碼的基本步驟,選擇變換形式；變換編碼的一個(gè)極其重要的作用是將信號(hào)中的能量盡可能集中在少數(shù)幾個(gè)系數(shù)上，選擇的準(zhǔn)則應(yīng)是集中度較高的變換。幾乎所有的圖像變換編碼器都采用基于分塊的DCT變換。 對(duì)給定圖像按某種方案(如分塊)進(jìn)行變換。 對(duì)這變換系數(shù)進(jìn)行按給定的規(guī)則進(jìn)行量化，這樣圖像壓縮率有明顯的提高(如：DCT變換之

35、后通常是均勻量化) 。 最后按指定編碼方式編碼(如：哈夫曼編碼)。,3、圖像壓縮為什么選中的余弦變換,實(shí)變換，且在給定條件下的重建誤差較小。 測(cè)試方法：對(duì)同一幅具有代表性的圖像，將其分成nn的子圖像，計(jì)算各子圖像的變換系數(shù)(求其變換“圖像”)，將變換系數(shù)由小到大截除75，求取截除系數(shù)后的變換“圖像”的反變換，計(jì)算均方根誤差后比較。,傅立葉,余弦,哈達(dá)瑪,1,3,16,64,4、國(guó)際標(biāo)準(zhǔn)簡(jiǎn)介JPEG標(biāo)準(zhǔn),JPEG的產(chǎn)生 JPEG是“聯(lián)合圖片專家組”(Joint Photograhic Coding Experts Group)的簡(jiǎn)稱。是由ISO (國(guó)際標(biāo)準(zhǔn)化組織)和CCITT(國(guó)際電話與電報(bào)顧問(wèn)

36、委員會(huì))于1986年聯(lián)合成立的一個(gè)標(biāo)準(zhǔn)起草小組，該小組于1991年提出ISO CD10918標(biāo)準(zhǔn)建議草案，1992年成為國(guó)際標(biāo)準(zhǔn)ISO/IEC。后來(lái)，通常將該標(biāo)準(zhǔn)稱為JPEG。 JPEG標(biāo)準(zhǔn)主要涉及連續(xù)色調(diào)(灰度和彩色)靜止圖像的壓縮編碼。它提供了一種適合大多數(shù)應(yīng)用場(chǎng)合的簡(jiǎn)單高效的圖像編碼方案。 下面，以灰度圖像為例介紹JPEG標(biāo)準(zhǔn)。,5、JPEG基本系統(tǒng),6、編碼、解碼過(guò)程 1)、將圖像分成88的圖像塊，以其為基本單位進(jìn)行編碼。 2)、對(duì)每個(gè)88的圖像塊進(jìn)行FDCT變換，得到變換系數(shù)矩陣。,3)、量化。將每個(gè)DCT系數(shù)除以各自的量化步長(zhǎng)并取整得到量化系數(shù)。,4)、將量化后的系數(shù)分成直流系數(shù)和

37、交流系數(shù)，查對(duì)應(yīng)表格對(duì)量化系數(shù)編碼。 5)、用Z型掃描的方法形成數(shù)據(jù)流，對(duì)數(shù)據(jù)流查Huffman表進(jìn)行編碼。,亮度量化表S(u,v),7、JPEG編碼應(yīng)用舉例,數(shù)據(jù)流： 79,0,-2,-1,-1,-1,0,0, -1,0,0,0,0,.,0,,直流分量,編碼示例,對(duì)直流分量而言，由于兩塊之間的直流分量非常接近所以JPEG對(duì)量化后的直流系數(shù)采用如下方法對(duì)F(0,0)編碼： F(0,0)=Fi(0,0)-Fi-1(0,0) 就本例而言，設(shè)F(0,0)2，查直流系數(shù)表，形成編碼： 類(lèi)型碼的編碼量化值范圍的編碼(使用自然碼，負(fù)數(shù)用反碼)。 有：2 2，2 011 10 對(duì)交流分量而言，采用

38、游程編碼。由若干個(gè)0(也可以沒(méi)有)和一個(gè)非0值組成一個(gè)編碼的基本單位。 就本例而言，在 0,-2,-1,-1,-1,0,0,-1,0,0,0,0,.,0中，0,-2為一個(gè)編碼單位； 有3個(gè)-1的編碼單位；最后為EOB編碼單位。每個(gè)編碼單位下式構(gòu)成： (游程/類(lèi)型碼)的編碼量化值范圍的編碼(使用自然碼，負(fù)數(shù)用反碼),,,類(lèi)型：由非0值查直流系數(shù)表得到。 游程：基本編碼單位中0的個(gè)數(shù)。,直流系數(shù)、交流系數(shù)量化表,亮度分量直流系數(shù)編碼表,亮度分量交流系數(shù)編碼表(負(fù)數(shù)用反碼表示),類(lèi)型碼的形成同亮度分量直流系數(shù)編碼表,最終編碼,對(duì)于本例而言，可求其編碼的壓縮比等參數(shù)為：,(游程/類(lèi)型碼)的編碼量化值范

39、圍的編碼(使用自然碼，負(fù)數(shù)用反碼),6)、解碼時(shí)，對(duì)接收到的數(shù)據(jù)流查Huffman表進(jìn)行解碼，得到和編碼器輸出相同的量化系數(shù)，對(duì)其進(jìn)行反量化恢復(fù)出DCT系數(shù)。最后，經(jīng)IDCT恢復(fù)圖像。,亮度量化表S(u,v),系數(shù)量化后圖像,,JPEG編碼過(guò)程回顧,數(shù)據(jù)流： 79,0,-2,-1,-1,-1,0,0,-1,0,0,0,0,.,0,最終編碼,亮度量化表S(u,v),解碼后的圖像,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,-13,-14,0,0,0,0,0,

40、0,-12,-24,0,0,0,0,0,-10,0,1264,,,,,,,,,,,,,,,,,,,反量化后的圖像,經(jīng)IDCT后的解壓縮圖像,原始數(shù)字圖像,壓縮比與圖象質(zhì)量的關(guān)系,,8、彩色JPEG編碼原理,,,YIQ顏色空間來(lái)源于國(guó)家電視標(biāo)準(zhǔn)委員會(huì)(NTSC)制彩色電視信號(hào)的傳輸。從RGB轉(zhuǎn)換到Y(jié)IQ顏色空間,9、JPEG文件結(jié)構(gòu),,,八、圖像文件.GIF文件編碼思想,1、字典編碼的思想 詞典編碼(dictionary encoding)的根據(jù)是數(shù)據(jù)本身包含有重復(fù)代碼這個(gè)特性。例如文本文件和光柵圖像就具有這種特性。字典編碼法的種類(lèi)很多，歸納起來(lái)大致有兩類(lèi)。 第一類(lèi)詞典法的想法是企圖查找正在壓縮

41、的字符序列是否在以前輸入的數(shù)據(jù)中出現(xiàn)過(guò)，然后用已經(jīng)出現(xiàn)過(guò)的字符串替代重復(fù)的部分，它的輸出僅僅是指向早期出現(xiàn)過(guò)的字符串的“指針”。 第二類(lèi)算法的想法是企圖從輸入的數(shù)據(jù)中創(chuàng)建一個(gè)“短語(yǔ)字典(dictionary of the phrases)”，編碼數(shù)據(jù)過(guò)程中當(dāng)遇到已經(jīng)在詞典中出現(xiàn)的“短語(yǔ)”時(shí)，編碼器就輸出這個(gè)詞典中的短語(yǔ)的“索引號(hào)”，而不是短語(yǔ)本身。,,,2、LZ78無(wú)損壓縮算法的基本思路,1.初始化字典，給定基本符號(hào)編碼；且將前綴串置為空串：P 空串。 2. C(字符串) 字符流的下一字符 3. P+C(綴-符串)在字典中嗎？ a. 是，則P P+C b. 否， 將當(dāng)前P和C的編碼加入到輸出碼

42、流 將P+C(綴符串)加入字典 P 空串 c. 字符流還有字符嗎？ 是，goto 2 否，i. 輸出P的編碼， ii. 結(jié)束,對(duì)給定符號(hào)序列編碼：,,,,,,,,,,,,基本符號(hào),3、LZ78解壓縮算法的基本思路,1. 初始化字典、P、C、cW、pW 2. cW= 碼流的第一個(gè)碼(cW表示正在處理的碼字) 3. 輸出string(cW)到字符流(string(cW)表示當(dāng)前綴符串) 4. pW = cW (pW表示先于當(dāng)前碼字的碼字) 5. cW = 碼流的下一個(gè)碼 6. string(cW)在字典中嗎？ a. 是。 輸出string(cW)到字符流； P=string(pW)

43、(string(pW)表示先前綴符串)；C=string(cW)的第一個(gè)字符； 將字符串P+C加入到字典中。 b. 否。 P=string(pW)； C=string(cW)的第一個(gè)字符； 將P+C輸出到字符流，并將它加入字典。 7. 碼流中還有編碼嗎？ a. 是，goto 4。b. 否，解碼過(guò)程結(jié)束,設(shè)對(duì)給定編碼序列解碼： ,輸出解碼序列： A B B A B A B A C,,,,,,,,,,,,編程作業(yè)：,1、編制一通用模板處理圖像的程序。模板的大小、系數(shù)可以更改；圖像的處理結(jié)果可以直接看到。 2、編制一個(gè)哈夫曼壓縮程序，對(duì)任意文件進(jìn)行壓縮，觀察結(jié)果；對(duì)壓縮文件進(jìn)行解壓縮，保持原文件的特征。,