數(shù)據(jù)壓縮的基本技術(shù)

1、數(shù)據(jù)壓縮的基本技術(shù)北京郵電大學(xué)多媒體通信技術(shù)課程2離散無記憶信源的熵與概率分布的關(guān)系).,2,1(0)1()(nippxHiii)., 2, 1(1ninpi時nnH22maxlog1logbits/symbol1)(max1niiptosubjectXH條件極值)(.)()(2211nnspsspsspsXniisp11)(離散信源熵iiippXH2log)(bits/symbol3離散無記憶信源的熵與概率分布的關(guān)系 一個符號攜帶的信息量最大，同樣信息量需要使用的符號數(shù)最少ppX1012n當(dāng)當(dāng)21psymbolbitH/1max00.51p1H,:pAX4信源的相關(guān)性與序列熵的關(guān)系)(.)(

2、)(2211nnspsspsspsXniisp11)()(.)()(2211mmtqttqttqtYmjjtq11)(ijijijrrYXH2log)( )/()()/()()(YXHYHXYHXHYXH給定 X 的條件下 條件熵22( /)loglog / ( )jiijijiijH Y XPrrp s假設(shè)離散信源是有記憶的：5信源的相關(guān)性與序列熵的關(guān)系)(XH)/(XYH)(YH)/()();(XYHYHYXI互信息假設(shè)離散信源是無記憶的：)()()(YHXHYXH)/()()(XYHXHYXH)()()/()(YHXHXYHXH)()()(maxYHXHYXH 信源符號之間無相關(guān)性時，聯(lián)

3、合熵最大6通信系統(tǒng)的一般模型csTKTNcsTTNK11 Noiseless channel DecoderSink SourceA, p EncoderE, jSymbol rate 1/TsNAu Symbol rate 1/TcllppssA.11. aajjttE.1.1Nl# of source codes =Ka# of encoder codes = 1/Ts1/TcNmBv # of source codes =Ka率失真函數(shù)長度為 N 的碼字的失真函數(shù) NrrrrNVUdNd1),(1對于給定信源 A, p：Auup )(是確定的信宿的概率分布為)/()()(uvPupvqA

4、u UN 和 VN 間的互信息為)()/(log)/()()/()();(vquvPuvPupUVHVHVUINNBvAuNNNNN 問題問題： 當(dāng)DdN 時，);(NNVUI至少要多大？或 至少需要傳遞多少信息，失真才足夠??？率失真函數(shù) );(min1)()/(NNPuvPVUINDRD 率失真函數(shù) R(D) 是對信源信息率進行有損壓縮的極限 對應(yīng)于不同類型的信源、不同類型的編解碼器（互 信息）和不同類型的失真度量函數(shù)，R(D)不同H(p)Dmax0R(D)D離散信源離散信源PD：所有滿足 DdN （所有滿足失真條件的編解碼器)的條件概率的集合限失真信源編碼定理 給定任意 和 ，可以找到正整

5、數(shù)N（N 充分大），以使一個長度為N 的（ ）容許碼存在，且其信息率 。 換句話說，失真接近于D、而信息率接近于R(D) 的碼是存在的。 對于 ， 前述離散無記憶信源可以在容量 的任何離散無記憶信道的輸出端還原，而失真為 。00D ()RR D0()CR DDD壓縮的途徑和極限 無損壓縮 解相關(guān) （符號間互信息為零） 等概率 （信源熵） 有損壓縮 率失真函數(shù)決定限失真壓縮的極限 利用視覺特性的限制基本的壓縮技術(shù) Down-sampling (sub-sampling) Predictive coding (DPCM) Motion compensated predictive coding T

6、ransform coding Quantization Entropy coding 取樣頻率的轉(zhuǎn)換下采樣2 ：1 下采樣？取樣頻率的轉(zhuǎn)換下采樣ffs2fs2424ffs2fsfs = 0.5 fs取樣頻率的轉(zhuǎn)換下采樣Antiaiasing fitr抗混疊濾波器 10)()()(NiinxihnwW(n)(nx)(nw)(my內(nèi)插（上采樣）Introation fitrIntroation fitr內(nèi)插濾波器b = round(G + H)/2 10)()()(NiimwihmyW(m)？預(yù)測編碼DPCMX12345 消除空間冗余（亮度、彩色） 1D 線性預(yù)測、2D 線性預(yù)測)()( 1in

7、xanxNii )( )()(nxnxne Z-1Z-Na1aN)(ne)(nx.預(yù)測器QDQ預(yù)測器)( nx)(nxPrediction error (residual)最佳預(yù)測器最小均方誤差（最小均方誤差（MMSE）意義下的最佳預(yù)測器）意義下的最佳預(yù)測器 min)., 2, 1(0)()(0)()()()(11NikiRaiRinxknxainxnxNkkNkk NkkkRaRne1min2)()0()(N階預(yù)測器的設(shè)計：階預(yù)測器的設(shè)計： 求 ai (I=1,2,N)最佳的準(zhǔn)則：最佳的準(zhǔn)則：最小均方誤差（最小均方誤差（minimum mean square error）)., 2, 1(0

8、)(2Nineai Niiinxanxne1)()()(量化誤差的傳播)()( 1inxanxNii)()(1inxanxNiiZ-1Z-Na1aN)(ne)(nx.預(yù)測器QDQ預(yù)測器)( nx)(nx)(ne)( nx收、發(fā)端的不匹配（Mismatch）DQ預(yù)測器)(nx)(nx)(neQDQ預(yù)測器)(nx閉環(huán)（Close Loop）預(yù)測器模仿接收環(huán)路序列圖像中的冗余 靜止物體在前后幀中完全相同 已知運動物體速度可以推算物體在下一幀中的位置 已知攝像機的運動參數(shù)(zoom, pan, tilt, rotation)可以推算下一幀的部分內(nèi)容運動估值 編碼：編碼：比較 bk 和 bk-1 得到

9、(motion estimation) 解碼解碼：從 bk-1 和 得到 bkDD 假設(shè) 物體是剛體，且只在與攝 像機軸垂直的平面內(nèi)平移 物體在任何位置上的照明 不變 不考慮 uncovered & covered backgroundDkk-1)()(1Dzbzbkk 運動矢量(Displacement vector)Motion Estimation Block matching Pel recursive Optical flow塊匹配方法 在前一幀中找找到相似塊到相似塊k 幀k-1 幀搜索范圍 SR（M+2dm)(N+2dm)MxN 什么是相似 如何搜索 “物體”： 不重疊的塊

10、相似準(zhǔn)則全搜索：全搜索：總移動次數(shù)為（2dm+1)2 (m,n)(m+i,n+j)（M+2dm)(N+2dm) MmNnkkjnimbnmbMNjiMAD111),(),(1),(mean absolute difference： ),(),(),(1),(2111mmMmNnkkdjidjnimbnmbMNjiMSE mean squared error：sum of absolute difference: MmNnkkjnimbnmbjiSAD111),(),(),(經(jīng)典的搜索方法 全搜索 (2dm+1)2 三步法搜索點數(shù)：25搜索步驟 ：3正交搜索法搜索點數(shù)：13搜索步驟：6 搜索圖形

11、搜索圖形搜索算法的基本思想 沿判決函數(shù)減小 的方向搜索 判決函數(shù)非凸時， 容易搜索到局部極 值點D判決函數(shù)optD搜索方法的改進MV預(yù)測A組：median3 neighbors B組： C組： , MVk-1+(MVk-1-MVk-2) k-1 幀k 幀k-2 幀搜索方法的改進早期終止如果滿足 A組： SAD T1 B組： SAD T2 C組： SAD 2, go to (1) then go to (4)(4) Assign codes1/31/41/51/61/2013/605/127/121.001000111x1x2x3x4x5X1: 00X2: 01X3: 11X4: 100X5:

12、101 給定符號集和概率模型， 找不到其他整數(shù)碼比霍夫 曼碼有更短的平均碼長 概率大的符號用短碼 概率小的符號用長碼霍夫曼碼的前綴特性 接收端必須已知碼表 短碼永遠不是長碼的開端X2 X5 X5 X2 X2 X3 .如果發(fā)生傳輸誤差：0 1 0 0 1 1 0 1 0 1 0 1 1 1 .X2 X1 X3 X2 X2 X2 X3 . Prefix property:0 1 1 0 1 1 0 1 0 1 0 1 1 1 .Variable length codingX1: 00X2: 01X3: 11X4: 100X5: 101Error propogation算術(shù)編碼的原理符號S1S2S3

13、S4概率（10 進制）0.1250.250.50.125概率（2 進制）p0.0010.010.10.001累積概率 P00.0010.0110.111S3: C=0+1x0.011 =0.011 A=1x0.1=0.1S3: C=0.011+0.1x0.011 =0.1001 A=0.1x0.1=0.01S2: C=0.1001+0.01x0.001 =0.10011 A=0.01x0.01=0.0001新編碼點C 原編碼點C原區(qū)間A x P新區(qū)間A 原區(qū)間A x pS3S2S1S4S1S2S3S41/83/87/8000.0010.0110.1111.01.0S3S2S1S40.0110.

14、01110.10010.11010.111S3S3S2算術(shù)編碼的譯碼輸入符號：輸入符號： S3 S3 S2 .輸出碼字：輸出碼字： 0.10011 .新譯碼點C (原譯碼點C P）/ pS1S2S3S41/83/87/8000.0010.0110.1111.01.0S3(0.10011 0.011) / 0.1 = 0.01111S3(0.011110.011) / 0.1 = 0.0011S2算術(shù)編碼的效率 編碼點 C C + A x Pi 編碼區(qū)間 A A x pi 表示最后編碼點（即最后一個區(qū)間）所需要的比特數(shù) 熵21221222log (.)loglog.lognnTpppppp 1()logNiiiHXpp 二進制算術(shù)編碼符號S1S2S3S4概率（10 進制）0.1250.250.50.125概率（2 進制） 0.0010.010.10.001累積概率00.0010.0110.111S1S4S2S3010101輸入序列：輸入序列： S3 S3 S2 . 0 0 10 1.001QeQeMPS： C C A A（1Qe）LPS： C C A（1Qe） A A Qe算術(shù)編碼實現(xiàn)中的問題