《數(shù)字圖象處理第七章.ppt》由會員分享，可在線閱讀，更多相關《數(shù)字圖象處理第七章.ppt（92頁珍藏版）》請在裝配圖網(wǎng)上搜索。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

23、連著的白像素段組成，分別稱為“黑長”和“白長”。黑長和白長總是交替發(fā)生。對于不同長度按其發(fā)生概率分配以不同長度的碼字，這就是游程長度編碼(RLC)。 設二值圖像中有長度為1, 2, ，N等不同長度的黑長和白長，N為一個掃描行的像素數(shù)。 步驟： 對每一掃描行從左到右按游程長度編碼，且每行都由白色游程開始(其長度可以是0) 。 用最優(yōu)變長編碼或亞最優(yōu)變長編碼對游程長度進行編碼。,一維游程長度(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)計按大小排列：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 共計：1319271170 (直接編碼為128位),2)、二維游程長度編碼(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)、預測差值量化編碼(PDQ),游程長度編碼只利用了沿掃描線方向的像素間的相關性。如果進一步利用行間

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

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

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

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

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

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

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

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

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

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

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

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

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

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

39、圍的編碼(使用自然碼，負數(shù)用反碼),6)、解碼時，對接收到的數(shù)據(jù)流查Huffman表進行解碼，得到和編碼器輸出相同的量化系數(shù)，對其進行反量化恢復出DCT系數(shù)。最后，經(jīng)IDCT恢復圖像。,亮度量化表S(u,v),系數(shù)量化后圖像,,JPEG編碼過程回顧,數(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ù)字圖像,壓縮比與圖象質量的關系,,8、彩色JPEG編碼原理,,,YIQ顏色空間來源于國家電視標準委員會(NTSC)制彩色電視信號的傳輸。從RGB轉換到YIQ顏色空間,9、JPEG文件結構,,,八、圖像文件.GIF文件編碼思想,1、字典編碼的思想 詞典編碼(dictionary encoding)的根據(jù)是數(shù)據(jù)本身包含有重復代碼這個特性。例如文本文件和光柵圖像就具有這種特性。字典編碼法的種類很多，歸納起來大致有兩類。 第一類詞典法的想法是企圖查找正在壓縮

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

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

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