數(shù)字圖像與視頻壓縮編碼原理2

1、 1數(shù)字圖像與視頻壓縮編碼原理張亞飛信息工程教研室2012-2013學(xué)年第2學(xué)期幀間預(yù)測編碼¾幀間預(yù)測編碼的依據(jù):視頻序列相鄰幀之間的相關(guān)性¾視頻圖像的預(yù)測編碼方法的基本思想第一幀關(guān)鍵幀采用幀內(nèi)編碼方法(即靜態(tài)圖像的編碼方法進(jìn)行壓縮后續(xù)幀只傳輸相鄰幀之間的變化信息(幀差,幀差的傳送是采用運(yùn)動(dòng)估計(jì)和補(bǔ)償?shù)姆椒ㄟM(jìn)行編碼。 幀間預(yù)測編碼¾視頻序列圖像在時(shí)間上的冗余分為幾種9對于靜止不同的場景,當(dāng)前幀和前一幀的圖像內(nèi)容是完全相同的9對于運(yùn)動(dòng)的物體,只要知道其運(yùn)動(dòng)規(guī)律,就可以從前一幀圖像推算它在當(dāng)前幀中的位置9攝像頭對著場景的橫向移動(dòng)、焦距變化等操作會(huì)引起整個(gè)圖像的平移、放

2、大或縮小。對于這種情況,只要攝像機(jī)的運(yùn)動(dòng)規(guī)律和鏡頭改變的參數(shù)已知,圖像隨時(shí)間所產(chǎn)生的變化也是可以推算出來的 幀間預(yù)測編碼-運(yùn)動(dòng)補(bǔ)償預(yù)測¾當(dāng)圖像中存在著運(yùn)動(dòng)物體時(shí),簡單的預(yù)測不能收到好的效果¾如果能夠跟蹤場景中物體的運(yùn)動(dòng),采用運(yùn)動(dòng)補(bǔ)償技術(shù),再做幀間預(yù)測,則會(huì)充分地發(fā)掘序列圖像的幀間相關(guān)性,預(yù)測的準(zhǔn)確性將大大提高 幀間預(yù)測編碼-運(yùn)動(dòng)補(bǔ)償預(yù)測¾如果簡單地以第k-1幀像素值作為k幀的預(yù)測值,則在實(shí)線和虛線所示的圓內(nèi)的預(yù)測誤差都不為零¾如果已經(jīng)知道了小球運(yùn)動(dòng)的方向和速度,可以從小球在k-1幀的位置推算出它在k幀中的位置來,這種考慮了小球位移的k-1幀圖像作為k幀的

3、預(yù)測值,就比簡單的預(yù)測準(zhǔn)確得多,從而可以達(dá)到更高的數(shù)據(jù)壓縮比。這種預(yù)測方法稱為具有運(yùn)動(dòng)補(bǔ)償?shù)膸g預(yù)測 幀間預(yù)測編碼-運(yùn)動(dòng)補(bǔ)償預(yù)測¾運(yùn)動(dòng)估計(jì):就是對運(yùn)動(dòng)物體的位移作出估計(jì),即對運(yùn)動(dòng)物體從前一幀到當(dāng)前幀位移的大小和方向作出估計(jì),也就是求出運(yùn)動(dòng)矢量¾運(yùn)動(dòng)補(bǔ)償預(yù)測就是根據(jù)求出的運(yùn)動(dòng)矢量,找到當(dāng)前幀中的像素(或像素塊是從前一幀的哪個(gè)位置移動(dòng)過來的,從而得到當(dāng)前幀像素(或像素塊的預(yù)測值¾獲得好的運(yùn)動(dòng)補(bǔ)償?shù)年P(guān)鍵是運(yùn)動(dòng)估計(jì)的精度 運(yùn)動(dòng)估計(jì)后向運(yùn)動(dòng)估計(jì)用的較多 運(yùn)動(dòng)估計(jì)-塊匹配算法¾塊匹配算法是目前最常用的運(yùn)動(dòng)估計(jì)算法¾在塊匹配算法中,先將當(dāng)前幀(第k幀分割成若

4、干個(gè)M*N的圖像子塊,并假設(shè)位于同一圖像子塊內(nèi)的所有像素都作相同的運(yùn)動(dòng),且只作平移運(yùn)動(dòng)¾實(shí)際上塊內(nèi)各像素的運(yùn)動(dòng)并不一定相同,也不一定只做平移運(yùn)動(dòng),但當(dāng)M*N較小時(shí),上述假設(shè)可近似成立 運(yùn)動(dòng)估計(jì)-塊匹配算法¾塊匹配算法是對當(dāng)前幀的每一個(gè)圖像子塊,在參考幀(如第k-1幀的一定范圍內(nèi),根據(jù)一定的匹配準(zhǔn)則找出與當(dāng)前塊最相似的塊,即最佳匹配塊,并認(rèn)為本圖像子塊就是從參考幀最佳匹配塊位置平移過來的,從而求得運(yùn)動(dòng)矢量。運(yùn)動(dòng)估計(jì)-塊匹配算法幀k-1運(yùn)動(dòng)矢量搜索窗被搜索的塊最佳匹配的塊塊幀k限失真編碼 運(yùn)動(dòng)估計(jì)-塊匹配算法 11 限失真編碼 運(yùn)動(dòng)估計(jì)-塊匹配算法 a b c d refere

5、nce frame a: (-2,-2 b: (-2,-1 c: (0,0 d: (2,2 inquiry block in current frame 12 限失真編碼 運(yùn)動(dòng)估計(jì)-塊匹配算法 ¾ 匹配塊的劃分 9 塊尺寸的選擇非常重要 9 較小尺寸的塊可以很好地和物體邊界吻合，得到更真 實(shí)的運(yùn)動(dòng)，但較小的尺寸會(huì)產(chǎn)生較多的運(yùn)動(dòng)信息，不 利于數(shù)據(jù)壓縮，同時(shí)，小尺寸塊對噪聲更敏感，會(huì)產(chǎn) 生運(yùn)動(dòng)多義性問題 9 較大尺寸的塊可以得到較少的運(yùn)動(dòng)信息，但由于可能 包含多個(gè)不同的運(yùn)動(dòng)物體而導(dǎo)致運(yùn)動(dòng)估計(jì)精度較低 13 限失真編碼 運(yùn)動(dòng)估計(jì)-塊匹配算法 ¾ 匹配塊的劃分 9 H.261,MP

6、EG-1使用16*16的塊 9 MPEG-2使用16*16和16*8的塊 9 H.263使用16*16和8*8的塊 16-by-16 8-by-16 16-by-8 8-by-8 14 限失真編碼 運(yùn)動(dòng)估計(jì)-塊匹配算法 ¾ 匹配準(zhǔn)則 9 絕對誤差和（SAD）最小準(zhǔn)則 SAD(i, j = f k (m, n f k 1 (m + i, n + j m =1 n =1 M N dxmax i dxmax , dymax j dymax = arg min SAD d d 15 限失真編碼 運(yùn)動(dòng)估計(jì)-塊匹配算法 ¾ 匹配準(zhǔn)則 9 均方誤差（MSE）最小準(zhǔn)則 1 MSE (i,

7、j = MN f k (m, n f k 1 (m + i, n + j m =1 n =1 M N 2 dxmax i dxmax , dymax j dymax = arg min MSE d d 16 限失真編碼 運(yùn)動(dòng)估計(jì)-塊匹配算法 ¾ 匹配準(zhǔn)則 9 歸一化互相關(guān)函數(shù)（NCCF）最大準(zhǔn)則 NCCF (i, j = f m =1 n =1 N M N k (m, n f k 1 (m + i, n + j m =1 n =1 M f k2 (m, n m =1 n =1 M N f k21 (m + i, n + j dxmax i dxmax , dymax j dymax

8、= arg max NCCF d d 17 限失真編碼 運(yùn)動(dòng)估計(jì)-塊匹配算法 ¾ 搜索策略-窮盡搜索（FS）法 9 窮盡搜索（FS）法，也稱為全搜索法 9 當(dāng)前幀中當(dāng)前塊大小M*N 9 搜索窗大小(M+2dxmax*(N+2dymax 9 搜索窗內(nèi)候選窗個(gè)數(shù)(2dxmax+1*(2dymax+1 9 位移矢量的范圍dx:-dxmax, dxmax ,dy:-dymax, dymax 9 全搜索就是逐一計(jì)算當(dāng)前塊和搜索窗內(nèi)所有候選塊之 間的匹配函數(shù) 9 如匹配準(zhǔn)則為SAD，則找出SAD最小時(shí)，所對應(yīng)的位 移量即為所求的運(yùn)動(dòng)矢量 18 限失真編碼 運(yùn)動(dòng)估計(jì)-塊匹配算法 a b c d r

9、eference frame a: (-2,-2 b: (-2,-1 c: (0,0 d: (2,2 inquiry block in current frame 19 限失真編碼 運(yùn)動(dòng)估計(jì)-塊匹配算法 ¾ 搜索策略-窮盡搜索（FS）法 9 全搜索的計(jì)算量非常大 9 使用SAD匹配準(zhǔn)則，全搜索一個(gè)塊需要計(jì)算加、減 和絕對值各M*N* (2dxmax+1*(2dymax+1次 9 此方法計(jì)算量大，但最簡單、可靠，找到的匹配點(diǎn) 肯定是全局點(diǎn)，而且易于硬件實(shí)現(xiàn) 20 運(yùn)動(dòng)估計(jì)-塊匹配算法¾搜索策略-快速搜索算法9通過減小候選塊的數(shù)目來降低計(jì)算復(fù)雜度,因此估計(jì)精度會(huì)降低9三步搜索法

10、9新三步搜索法9二維對數(shù)搜索法9交叉搜索法9菱形搜索法9四步搜索法Fast BMA: 3-Step-Searchsearch 9+8+8=25 points02468-2-4-6-82468-2-4-6-8 運(yùn)動(dòng)估計(jì)-塊匹配算法¾搜索策略-快速搜索算法9三步搜索法第一步,從原點(diǎn)開始,選取最大搜索長度的一半為步長,在周圍距離步長的8 個(gè)點(diǎn)處進(jìn)行塊匹配計(jì)算并比較,選取匹配函數(shù)最小點(diǎn)。第二步,將步長減半,中心點(diǎn)移到上一步的匹配函數(shù)最小點(diǎn),重新在周圍距離步長的8 個(gè)點(diǎn)處進(jìn)行塊匹配計(jì)算并比較,選取匹配函數(shù)最小點(diǎn)。第三步,在中心及周圍8個(gè)點(diǎn)處找出價(jià)值函數(shù)最小點(diǎn),若步長為1,該點(diǎn)價(jià)值函數(shù)最小,搜索

11、結(jié)束,否則重復(fù)第二步 運(yùn)動(dòng)估計(jì)-塊匹配算法¾搜索策略-分級搜索9快速搜索算法可以減少運(yùn)算量,但但不容易找到全局最優(yōu)解,估計(jì)精度降低9分級搜索算法現(xiàn)在低分辨率圖像中進(jìn)行全搜索(粗搜索,然后以粗搜索的結(jié)果作為下一步搜索的起始點(diǎn),再在高分辨率圖像中進(jìn)行快速搜索。 運(yùn)動(dòng)估計(jì)-塊匹配算法¾搜索策略-分級搜索 運(yùn)動(dòng)估計(jì)-塊匹配算法¾搜索策略-分級搜索(a(c(e(b (d (f運(yùn)用運(yùn)動(dòng)補(bǔ)償技術(shù)進(jìn)行預(yù)測編碼的過程 在緩存中重構(gòu)一個(gè)經(jīng)過編解碼處理的前一幀的圖像,該圖像稱為運(yùn)動(dòng)估計(jì)的“參考幀”,編碼端和解碼端采用同樣的參考幀;運(yùn)用運(yùn)動(dòng)補(bǔ)償技術(shù)進(jìn)行預(yù)測編碼的過程 計(jì)算當(dāng)前幀中的每一個(gè)

12、方塊(一般為16*16像素的宏塊和緩存中的參考幀中宏塊的最佳匹配塊,即進(jìn)行運(yùn)動(dòng)估計(jì)計(jì)算。用運(yùn)動(dòng)矢量表明兩個(gè)宏塊之間的位移。例如,運(yùn)動(dòng)矢量=(-4,5,則在當(dāng)前幀的宏塊向左移動(dòng)4個(gè)像素,向下移動(dòng)5個(gè)像素,就可以在參考幀中找到最匹配的宏塊。運(yùn)用運(yùn)動(dòng)補(bǔ)償技術(shù)進(jìn)行預(yù)測編碼的過程 通過參考幀的最佳匹配塊進(jìn)行運(yùn)動(dòng)補(bǔ)償計(jì)算,得到當(dāng)前幀的最相似圖像(運(yùn)動(dòng)補(bǔ)償參考幀。運(yùn)用運(yùn)動(dòng)補(bǔ)償技術(shù)進(jìn)行預(yù)測編碼的過程幀差圖像然后當(dāng)前幀和運(yùn)動(dòng)補(bǔ)償參考幀進(jìn)行差值運(yùn)算(相對應(yīng)的像素進(jìn)行減法運(yùn)算,得到運(yùn)動(dòng)補(bǔ)償?shù)膸顖D像。運(yùn)用運(yùn)動(dòng)補(bǔ)償技術(shù)進(jìn)行預(yù)測編碼的過程 對幀差圖像進(jìn)行DCT變換和量化;運(yùn)用運(yùn)動(dòng)補(bǔ)償技術(shù)進(jìn)行預(yù)測編碼的過程 量化后的系數(shù)

13、和運(yùn)動(dòng)矢量進(jìn)行熵編碼和傳輸;運(yùn)用運(yùn)動(dòng)補(bǔ)償技術(shù)進(jìn)行預(yù)測編碼的過程 量化后的系數(shù)同時(shí)被解碼,得到的幀差圖像和運(yùn)動(dòng)補(bǔ)償參考幀進(jìn)行加法運(yùn)算,從而得到一個(gè)新的放在緩存中的參考幀。在解碼端重構(gòu)當(dāng)前幀的過程 在解碼端對運(yùn)動(dòng)矢量和系數(shù)進(jìn)行解碼;在解碼端重構(gòu)當(dāng)前幀的過程幀差圖像對系數(shù)進(jìn)行反量化和反變換,得到幀差圖像;在解碼端重構(gòu)當(dāng)前幀的過程 對緩存中的參考幀(重構(gòu)的前一幀圖像通過運(yùn)動(dòng)矢量進(jìn)行運(yùn)動(dòng)補(bǔ)償計(jì)算,得到運(yùn)動(dòng)補(bǔ)償參考幀;在解碼端重構(gòu)當(dāng)前幀的過程幀差圖像幀差圖像和運(yùn)動(dòng)補(bǔ)償參考幀進(jìn)行加法運(yùn)算,得到當(dāng)前幀圖像;在解碼端重構(gòu)當(dāng)前幀的過程和編碼器的緩存中存放的是相同的參考幀當(dāng)前幀圖像放入緩存中,作為新的參考幀。 塊匹

14、配算法作業(yè)¾請分別編程實(shí)現(xiàn)絕對誤差和(SAD和均方誤差(MSE函數(shù)的一個(gè)搜索點(diǎn)的匹配函數(shù),其中塊大小為16*16,當(dāng)前點(diǎn)為(curr_x, curr_y,搜索點(diǎn)為(cand_x, cand_y。以上描述中均使用塊的左上角像素點(diǎn)的坐標(biāo)標(biāo)示該塊,當(dāng)前幀和參考幀分別采用二維數(shù)組img和imgr存儲(chǔ)。¾函數(shù)原型:9int OneMatchSAD(int curr_x, int curr_y, int cand_x, intcand_y;9int OneMatchMSE(int curr_x, int curr_y, int cand_x, int cand_y;限失真編碼變換編碼&

15、#190;基于圖像變換域的編碼方式¾用一個(gè)可逆的、正交變換(如傅立葉變換,把圖像映射到變換空間,將圖像像素集合轉(zhuǎn)化為變換系數(shù)的集合¾對系數(shù)集合進(jìn)行量化和編碼¾對于大多數(shù)自然圖像,重要系數(shù)的數(shù)量總是比較少的,因而可僅以較小的圖像失真為代價(jià),刪除接近于零的系數(shù),并且對較小的系數(shù)進(jìn)行粗量化,而保留包含圖像主要信息的系數(shù),以此進(jìn)行壓縮編碼。¾在重建圖像進(jìn)行解碼時(shí),所損失的將是一些不重要的信息,引起圖像的失真是可以接受的限失真編碼變換編碼¾正交變換的選擇9離散傅立葉變換(DFT、離散余弦變換(DCT、K-L變換、Walsh-Hadamard變換(WHT9

16、最優(yōu)變換:K-L變換,均方差準(zhǔn)則下的最佳變換,但其沒有快速算法,計(jì)算量大9次優(yōu)變換:DCT變換,對于通常的圖像信號,有和K-L變換幾乎一樣好的去相關(guān)性,并且有快速算法、易于硬件實(shí)現(xiàn),在圖像和視頻壓縮中應(yīng)用最廣泛限失真編碼變換編碼-DCT¾一維離散余弦變換設(shè)一維實(shí)數(shù)離散序列f (x ,x =0,1,N -1。將f (x 延拓為偶對稱序列f s (x 。1(21(2s f x f f x =111,1,(1222111,1,(1222x N x N =+=""限失真編碼變換編碼-DCT¾一維離散余弦變換(11/2(11/2(11/21/2(11/21/2(1

17、1/2(11/21/21/212(exp(221212(exp(exp(22221212(exp(exp(2222N s s x N N s s x N x N N s s x x F u f x j ux N Nf x j ux f x j ux N N NN f x j ux f x j ux N N NN +=+=+=+=+=(11/21/2(11/21/2102(cos(21(cos(22(cos (212N s x N x N x ux f x N N ux f x N N f x x u N N +=+=+限失真編碼變換編碼-DCT¾一維離散余弦變換=+=1012(2co

18、s (2(N x u x N x f N u C u F 一維DCT 定義如下:設(shè)f (x |x =0, 1, , N -1為離散的信號序列。=其他1021(u u C 式中,u =0, 1, 2, , N -1。限失真編碼變換編碼-DCT¾一維離散余弦變換將變換式展開整理后,可以寫成矩陣的形式,即其中=N N N N N N N N N N N N G 21(12(cos 21(3cos 21(cos 212(cos 23cos 2cos 2121212"#%#""F=Gf限失真編碼變換編碼-DCT例:當(dāng)N=4時(shí)余弦變換核矩陣G 為11110.50.50.50.271N N N NN N N N N N N N G N N N N N N N N N NN NN NN N =0.6530.6530.271限失真編碼變換編碼-DCT¾一維離散余弦變換=+=1012(2cos (2(N u