第09章 圖象數(shù)據(jù)結(jié)構(gòu)與數(shù)據(jù)壓縮 數(shù)字圖像處理 北航

1、第七章第七章 圖象數(shù)據(jù)結(jié)構(gòu)與數(shù)據(jù)壓縮圖象數(shù)據(jù)結(jié)構(gòu)與數(shù)據(jù)壓縮7.1概述概述 1、圖象數(shù)據(jù)壓縮是為了檢索、存儲、傳輸?shù)男枰?圖象經(jīng)常用到搜索（查找分區(qū)、判別邊界都要搜索）如何搜索算法。為了提高搜索速度涉及兩個問題：存貯分式及存貯結(jié)構(gòu)（圖象的數(shù)據(jù)結(jié)構(gòu)）。 存貯方式有兩大類：一類為文件管理系統(tǒng)下數(shù)據(jù)結(jié)構(gòu)，即作為標(biāo)準(zhǔn)的數(shù)據(jù)文件；另一類為在系統(tǒng)的外部卷，即作為系統(tǒng)驅(qū)動程序下直接讀寫，其卷結(jié)構(gòu)由設(shè)計者自己規(guī)定，這種結(jié)構(gòu)有兩個好處：一是空間節(jié)?。筛浞掷么尜A介質(zhì)），二是讀寫速度快（由于節(jié)省了文件結(jié)構(gòu)的一些輔助空間及省去了一些不必要的檢查手續(xù)）。 文件結(jié)構(gòu)：提供一種能快速搜索到所需數(shù)據(jù)文件組織方式。逐點查

2、找先粗后細(xì)查找方式： * 四叉樹（地圖逐級放大，世界國省縣） * 二叉樹 2圖象一大特點是數(shù)據(jù)量大，為其存貯、傳輸帶來困難，需壓縮。 例：電話線傳輸速率一般為56Kbits/s（波特率） 一幅彩色圖像51251224bit = 6M bits大小。傳一幅圖象需2分鐘左右。實時傳送更難：51251224bits25幀/秒=150Mbits/S 如壓縮20倍，傳一幅圖6秒左右，可以接受，實用。 實時，要專用信道（衛(wèi)星、微波網(wǎng)、專線網(wǎng)等技術(shù)）。另外，大量資料需存貯遙感、故宮、醫(yī)學(xué)CT、MR。從統(tǒng)計觀點出發(fā)，簡單直觀地講，就是某一象素的灰度值，總是和周圍其他象素灰度值有某種關(guān)系，應(yīng)用某種編碼方法提取并

3、減少這些相關(guān)特性，便可實現(xiàn)圖象信息的數(shù)據(jù)壓縮。圖象數(shù)據(jù)壓縮的目的可以是節(jié)省圖象存貯器容量，也可以是減少傳輸信道容量，還可以是為了縮短圖象加工處理的時間。 （1）壓縮方法： 按時間分： 靜圖：靜止圖象（要求質(zhì)量高） 動圖：活動的序列圖象（相對質(zhì)量要求低，壓縮倍數(shù)要高） 壓縮比未壓縮的圖象的存貯字節(jié)數(shù)壓縮后圖象存貯字節(jié)數(shù) 失真與否分： 無失真壓縮：經(jīng)壓縮后再恢復(fù)圖象與原圖象無任何區(qū)別，一般 壓縮倍數(shù) 2 有限失真壓縮：單幀（靜）420倍。 圖象序列（x、y、t）50200倍 （2）壓縮失真度衡量標(biāo)準(zhǔn)：a客觀： 輸出與輸入之差：e(x,y) = g(x,y)f(x,y)整圖：均方差： 量綱：灰度級。

4、亦也將輸出與輸入之差看作噪聲。輸出圖象均方信噪比定義為： g2(x,y) / e2(x,y) 211010101022,msrmsNxNyNxNymsSNRSNRyxeyxgSNR 2121010222,1eeyxeNermsNxNy常用：峰值信噪比 RationoisetosignalpeakPSNR222552log10一般2，或PSNR40dB 人眼看不出來30 dB 的圖象不能用35dB 可接受 到目前為上，國際上沒有一個通用的評價圖象壓縮的客觀標(biāo)準(zhǔn) b主觀（人判別）專家投票的方法，實用方法。 人的視覺的主觀亮度是光強的對數(shù)函數(shù)。 人眼對黑暗區(qū)誤差比明亮區(qū)更敏感。 人眼對灰度突變邊緣比

5、較敏感。 （3）圖象壓縮的技術(shù)指標(biāo)：）圖象壓縮的技術(shù)指標(biāo)：a保真度與用途有關(guān)，例如偵察與體育比賽關(guān)心內(nèi)容不同b壓縮比：原圖象數(shù)據(jù)量壓縮后數(shù)據(jù)量或0.3bit/pixelc誤碼擴散程度d實時性與壓縮算法、系統(tǒng)速度有關(guān)e保密性傳輸中防止被盜，SPOT 是數(shù)據(jù)需解碼（高明壓縮方法，壓縮后仍是一幅圖） 數(shù)字水印技術(shù)watermarking 7.2 四叉樹與二叉樹四叉樹與二叉樹（金字塔pyramid或Quad tree） 適用于N = 2n 圖象 四叉樹：四叉樹： 0層 1層 2層 n層象素數(shù)： 40 41 42 4n四叉樹全部保留，總數(shù)據(jù)量為：nknnk014343144點數(shù)全分辨率圖： 4n點數(shù)，數(shù)

6、據(jù)量增加1/3，對搜索有好處，找到有關(guān)興趣區(qū)域后再提取感應(yīng)趣的下一層圖象。 二叉樹二叉樹（能解決余位問題）如右圖所示可作二叉樹表示其優(yōu)點是灰度變化平緩一些，且數(shù)據(jù)量相同，另一優(yōu)點數(shù)據(jù)位數(shù)不增加，計算方法如下： 其f0、f1與g0、g1關(guān)系由查表決定 若右側(cè)f=07,則g亦在07范圍的灰度為例定義g0、g1 1與f0、f1關(guān)系。 由查表關(guān)系，f0、f1、g0、g1之間是11對應(yīng)關(guān)系，所以不會丟失精度和誤差 3,210100ffgffg7.3 信息有關(guān)的基本概念信息有關(guān)的基本概念1信息的度量 7月份天氣報：“明天下雨”， 信息量小 10月份天氣報：“明天下雪”概率事件發(fā)生，信息量大概率低信息量大概

7、念高信息量小怎么定量？ 戈壁灘一年下雨概率1/128，睛概率127/128 。 對天氣預(yù)報的信息量多少 引入-log2p 代表信息量 如： -log21/128 = 7 有雨 -log2127/128 0 晴信息具有可加性： 一個99方陣，一個士兵在某一位置的概率1/81，信息 = -log21/81 = 6.34 在特定行上的概率1/9：信息 = -log21/9 = 3.17 在特定列上的概率1/9：信息 = -log21/9 = 3.17 行、列信息量和： 3.17+ 3.17 = 6.34引入一個信息度量 I(P)特點： 0 p P2，I(P2)I(P1) I(p q) = I(p)+

8、I(q) I(P)= -logbp 一般 b = 2 2信息熵信息熵（Entropy） 預(yù)期能得到的平均信息量，I(Pi)的數(shù)學(xué)期望值 。對于M個灰階： Pi i= 1,2,., mM1iM1i2log -)( HipiiippIp熵例1， 當(dāng)Pi = 1/4 , i= 1,2,3,4 H = 2 當(dāng)P1 = 1/2, P2 = 1/4, P3 = P4 = 1/8 H = 1.75 例2，二值圖象， xi = 0, 1 0值概率：p 1值概率：1-p)1(112log)1 (2log HppppH p 變化關(guān)系可以發(fā)現(xiàn)，當(dāng)p=0.5時熵最大。 0 0.5 1 pH1.0一般講，對M個灰值，

9、Miip11求H的條件極值，即： M)1,2,., (i 1MpiMMH2log2log1max M = 256時， Hmax = 8注意熵H的特點： H 0 Hmax = log2M H Hmax 3互信息量（信息損失的度量） 7.4 可逆保真編碼（無失真壓縮）可逆保真編碼（無失真壓縮）熵：平均信息量一般圖象壓縮模式： 孤立地考察每個象素點出現(xiàn)概率。去相關(guān)（去冗余）量化無失真編碼M1i2log - ipipS一階熵S=8大S小0 255 灰度 百分比注意：恰當(dāng)做變換熵可以減小。例：熵變小，把信息轉(zhuǎn)移到變換模型中（高階熵概念） 結(jié)論：結(jié)論： 不作變換時無失真編碼壓縮極限是熵一幅圖(3bits)

10、4 4 4 4 4 4 0 4 5 5 5 5 4 04 5 6 6 6 4 04 5 6 7 6 4 04 5 6 6 6 4 04 5 5 5 5 4 04 4 4 4 4 4 0 4 4 4 4 4 4 0 灰度 頻數(shù) 概率 熵0 8 0.125 0.3751 0 0 02 0 0 03 0 0 04 31 0.484 0.5075 16 0.25 0.506 8 0.125 0.375 7 1 0.016 0.096和 64 1.0 1.8531Huffman碼緊湊編碼碼緊湊編碼 n個由(m1mn)信息，概率為P1Pn， 基本思想基本思想：對概率大的信息分配短碼，小的分配長碼。步驟：步

11、驟：先作直方圖統(tǒng)計，按出現(xiàn)概率由大到小排隊。 而后反向編碼： 概率大的賦0， 概率小的賦1。實現(xiàn)：實現(xiàn)：可以按塊、按總體統(tǒng)計或自適應(yīng)邊統(tǒng)計邊修正。此碼變長，不易實現(xiàn)，當(dāng)概率變，則編碼方式亦變化。 nirp112B碼：碼：每個碼分成兩部分，即延續(xù)比特和信息比特。 分割碼字 代表有效信息CCCC(0或1表示)C相同的表示同一個碼字 C變號表示前一個碼字結(jié)束。 3移位碼移位碼 2位碼可有00，01，10，而11作為移位碼，超過3的倍數(shù)用11 的次數(shù)表之。 4行程編碼行程編碼(Run-Length Coding) 由灰度長度對組成，即(灰度，長度)，根據(jù)前圖按垂直方向掃描,可編為：(4,9) (5,5

12、) (4,3) (5,1) (6,3) (5,1) (4,3) (5,1) (6,1) (7,1)(6,1) (5,1) (4,3) (5,1) (6,3) (5,1) (4,3) (5,5) (4,10) (0,8) 結(jié)果：64個數(shù)據(jù)壓成到40個。通常掃描走向：另一種掃描方向線選取另一種掃描方向線選取，Helbert曲線行程編碼。遞歸算法： A: D A A B B: C B B A C: B C C D D: A D D CDDDAC1級2級對前圖用Helbert曲線掃描結(jié)果： 4 4 5 4 4 4 5 5 6 6 7 6 5 5 4 4 4 5 5 4 4 4 4 4 4 4 4 4

13、5 5 6 6 6 5 5 5 4 4 4 4 4 4 0 0 0 4 4 0 0 0 4 4 5 6 6 5 5 5 4 4 4 4 0 0得：(4,2) (5,1) (4,3) (5,2) (6,2) (7,1) (6,1) (5,2) (4,3) (5,2) (4,9) (5,2) (6,3) (5,3) (4,6) (0,3) (4,2) (0,3) (4,2) (5,1) (6,2) (5,3) (4,4) (0,2) 242=48目前算術(shù)編程碼效率最高,計算量大7.5 有限失真編碼有限失真編碼1插值編碼量化： 灰度分辨率采樣： 空間分辨率僅保留部分灰值其它部分值求得 2按塊取齊編碼

14、按塊取齊編碼 將NN圖像分成MM大小之塊，MN然后分別對每個MM塊內(nèi)之?dāng)?shù)據(jù)壓成一位長，按力矩不變原則選閾值并二值化而得到，同時還需保留恢復(fù)力矩必須的信息。步驟：由中值分割成二值圖， 由一、二次力矩計算出分別之A，B值， 保留二值圖像及f,。 例： 小范圍內(nèi)恢復(fù)后的灰度值近似取為一樣，看不出差別，主要特征保留。 優(yōu)點：按塊等長編碼，防誤碼擴散。 缺點：四行才能計算，需要行存貯。 3變換編碼變換編碼 概念概念：將空間域里的圖象，經(jīng)過某種變換（通常用正交變換，如付氏變換，沃爾什變換等），在某種變換域里描述，一般來說，在變換域里描述要比空間域里簡單，而且圖象相關(guān)性明顯下降，這樣變換本身就能實現(xiàn)編碼率的

15、壓縮。若再對變換域圖象進行某種處理（如頻域中的二維濾波）以及熵編碼，則可進一步壓縮圖象的編碼比特率。對變換處理后的圖像信號施以上述的反變換，即可獲得空間域圖象。 變換目的是去相關(guān)、相鄰象素相關(guān)性強，變換運算量與N2成正比。一般N取88塊或1616塊（塊小壓縮倍數(shù)少，沒意義；塊大，相關(guān)性弱）。 4預(yù)測編碼：預(yù)測編碼： 由前m點預(yù)測當(dāng)前點，存預(yù)測值與實際值的差值典型：典型：相鄰象素灰值相減，存差值。 預(yù)測結(jié)果：預(yù)測結(jié)果：多米諾骨牌，誤碼擴散嚴(yán)重。 分塊后邊緣損失。 5矢量編碼矢量編碼 簡化描述：全圖n個點，有A0 A1 A2 An，有m 個組，近似歸納為有限個模式，如k組，全圖有n/m組 ，n/m

16、k, 存k組 + n/m個組號。 7.6 圖象幀間編碼圖象幀間編碼 序列圖象（動圖）幀間相關(guān)性強1靜止運動部分的關(guān)系： Bell實驗室研究成果，人對靜止部分分辨率強，對運動部分分辨率弱要求不高。即：空間分辨率高，時間分辨率低一些。2傳送幀間差對幀間差壓縮傳輸，兩幅之間對應(yīng)象素的灰度差某一閾值，取為零。3運動檢測：圖象分成一定大小的塊（MN-1616）子塊，在(M+2L,N+2L)范圍內(nèi)到前一幀圖上搜索與某相關(guān)性最大的子塊。 相關(guān)函數(shù)： 7.7 JPEG與與MPEG（Joint Photographic Expert Group, Motion Picture Expert Group）90年代初期制定。1JPEG：8791年初制定的一系列標(biāo)準(zhǔn)?；痉桨福?DCT 量化編碼壓縮 DCT：88塊做DCT變換,統(tǒng)計分析表明，圖象局域相關(guān)性較強。 量化：人的感覺對低頻敏感，各系數(shù)對人眼的重要程度區(qū)別對待，即非均勻量化。 沿長編碼：（鋸齒形編碼）后半很多都是零有利編碼。 88塊，每塊做DCT直流分量，按塊作預(yù)測編碼，交流分量量化后作延長編碼。對沿長編碼結(jié)果作Huffman編碼。 多波段問題：多波段問題：地物波譜224波，彩色R、G、B三波段，各波段間存在相關(guān)性，如彩色，人眼對亮