【導(dǎo)讀】基于信源模型圖像編碼的數(shù)據(jù)壓縮

　　

【正文】 很高外，模型基編碼的碼率與圖像分辨率無關(guān)，不會(huì)因 收端計(jì)算機(jī)合成的圖像大小變了，就要求模型參數(shù)及運(yùn)動(dòng)參數(shù)的數(shù)目也相應(yīng)變化。而在其他 視頻編碼方法如 MPEG2 標(biāo)準(zhǔn)中，如果提高圖像分辨率，則所需傳輸?shù)拇a率也會(huì)大幅增加。 當(dāng)然，模型基編碼也存在不足的地方，主要問題是，計(jì)算機(jī)根據(jù) 3D 模型和信息合成的圖像缺乏足夠的自然度和真實(shí)度 。原因在于，攝像機(jī)拍攝自然景物的過程是三維景物投影到攝像平面的過程，其間丟失了三維景物的深度信息，而要重建這些深度信息是非常困難的。其進(jìn)一步的研究方向是把物體基編碼和語義基編碼結(jié)合起來，取長(zhǎng)補(bǔ)短；或者在語義基編碼器中加入波形編碼器，對(duì)不能建模的物體進(jìn)行混合編碼，以擴(kuò)大前者的適用范圍。 基于信源模型圖像編碼的數(shù)據(jù)壓縮算法的研究與實(shí)現(xiàn) 第 三 章 矢量量化圖像編碼 的研究 18 第三 章 矢量量化圖 像編碼 的研 究 矢量量化 [3](Vector Quantization， VQ)利用了相鄰采樣之間的相關(guān)性，基本思想是在量化時(shí)用輸出組集合 (碼書 )中最匹配的一組輸出值 (碼字 )代替輸入的一組采樣值 (輸入矢量 )。矢量量化的歷史可追溯到 1956 年由 Steinhaus 第一次系統(tǒng)地闡述了最佳矢量量化問題。 1978 年， Buzo 第一個(gè)提出實(shí)際的矢量量化器。 1980 年，Linde,， Buzo 和 Gray 將 LloydMax 算法 推廣，發(fā)表了第一個(gè)實(shí)用的矢量量化器設(shè)計(jì)算法 —— LBG 算法，從此矢量量化在有損數(shù)據(jù) 壓縮上得到了廣泛的應(yīng)用。 基本的矢量量化器可以定義為從 k 維歐幾里德空間 KR 到一個(gè)有限子集 C 的一個(gè)映射，即 Q： KR ?C，其中 C={ K0 1 1 i, , ..., | RNy y y y? ?}稱為碼書， N為碼書大小。該映射滿足 ： Q(x|x KR? )= py ， 其中 x=( 0 1 1, ,..., kx x x ? )為 KR 中的 k 維矢量，0 1 ( 1 )( , , .. ., )p p p p ky y y y ?? 為碼書 C中的碼字并滿足 ： 0 j N 1( , ) m in ( , )pjd x y d x y? ? ?? （ 31） 其中 ， ( , )jdxy 為輸入矢量 x與碼字 jy 之間的失真 測(cè)度。每一個(gè)矢量 x=( 0 1 1, ,..., kx x x ? )都能在碼書 C={ 0 1 1 i, ,..., |Ny y y y? }中找到最匹配碼字 py =Q(x|x KR? )。 輸入矢量空間通過量化器 Q 量化后，可以用劃分 S= 0 1 1{ , ,..., }Ns s s ? 來 描述，其中 iS 是所有映射成碼字 iy 的輸入矢量集合，即 ( | ( ) )iis x Q x y??。這 N個(gè)子空間 0 1 1, ,..., Ns s s ? 滿 足 ： 10 ()Ni i i js s s s i j?? ? ? ? ?且 （ 32） 矢量量化編碼與解碼過程如圖 。矢量量化編碼器根據(jù)一定的失真測(cè)度在碼書中搜索出與輸入矢量之間失真最小的碼字。傳輸時(shí)僅傳輸該碼字的索引。矢量量化解碼過程很簡(jiǎn)單，只要根據(jù)接收到的碼字索引在碼書中查找該碼字，并將它作為輸入矢量的重 構(gòu)矢量 。 用數(shù)學(xué)的觀點(diǎn)來描述，可以將矢量 S= 0 1 1{ , ,..., }Ns s s ? 看作是在 N 維空間中的一個(gè)點(diǎn)。把 N 維空間劃分為 L 個(gè)區(qū)域 iR ， i=1,2,...,L，人們稱之為 Voronoi 區(qū)域。落在區(qū)域 iR 上的所有矢量都用同一個(gè)矢量 11[ , ,..., ]i i i iNr r r r? 來表示，這里矢量稱為碼字(Codeword)， 由所有 L個(gè)碼字組成的集合稱為碼書 (Codebook)。由上可知， 矢量量化的編碼首先要將原始的數(shù)據(jù)劃分為一系列矢量，然后在特定碼書中搜索誤差最小基于信源模型圖像編碼的數(shù)據(jù)壓縮算法的研究與實(shí)現(xiàn) 第 三 章 矢量量化圖像編碼 的研究 19 的碼字作為量化值。矢量量化的編碼結(jié)果并不是碼字，而是碼字在碼書中的索引值。如果這個(gè)索引值記錄所需要的存儲(chǔ)空間小于原始矢量的存儲(chǔ)空間，就達(dá)到了壓縮數(shù)據(jù)的目的。而量化質(zhì)量則體現(xiàn)為原始矢量同其碼字之間的誤差。由此可見矢量量化技術(shù)包括矢量構(gòu)成、碼書設(shè)計(jì)、碼字搜索等多個(gè)方面。 圖 書 設(shè)計(jì) 矢 量量化的首要問題是設(shè)計(jì)出性能好的碼書。在矢量維數(shù) k與碼書尺寸 N已經(jīng)確定的情況下，好的碼書訓(xùn)練方法可以使訓(xùn)練得到的碼書性能大大提高，使得編碼時(shí)的總體量化誤差 (通常采用均方誤差 )盡可能小。假設(shè)采用平方誤差測(cè)度作為失真測(cè)度，訓(xùn)練矢量數(shù)目為 M(M N)，則碼書設(shè)計(jì)的過程可看作對(duì)這 M 個(gè)訓(xùn)練矢量進(jìn)行N 數(shù)目最優(yōu)分類的過程，并把各類的質(zhì)心 矢量作為碼書的碼字。可以證明在這種條件下各種可能的碼書個(gè)數(shù)為 : 01 ( 1) *N N i i MNi CiN?? ?? (33) 其中心 iNC 為組合數(shù)。然而，在 N 和 M 比較大的情況下，建立這樣一個(gè)大尺寸的碼索引 P 索引 P 輸出碼字 py 輸入矢量 X 搜索最匹配碼字 py 信 道 查找索引P 對(duì)應(yīng)的碼字 py 0y 1y …… N1y? 0y 1y …… N1y? 碼書C 碼書C 基于信源模型圖像編碼的數(shù)據(jù)壓縮算法的研究與實(shí)現(xiàn) 第 三 章 矢量量化圖像編碼 的研究 20 書會(huì)帶來存儲(chǔ)上的問題，更嚴(yán)重的是由于碼書設(shè)計(jì)和編碼時(shí)碼字搜索的計(jì)算復(fù)雜度隨著碼書尺寸 N 的增大呈指數(shù)增加，使得大尺寸碼書的應(yīng)用受到實(shí)際編碼設(shè)備的限制而難以實(shí)現(xiàn)。 從實(shí)用角度講，碼書設(shè)計(jì)算法應(yīng)保證所得到的碼書具有高的性能，同時(shí)算法的復(fù)雜度也要在可以接受的范圍之內(nèi)。對(duì)于灰度、色度和紋理信息豐富的圖像信源而言，要在碼書設(shè)計(jì)算法的性能和計(jì)算量之間的取得平衡并不容易。 1980 年 Linde、 Buzo 和 Gray 將勞埃德最佳標(biāo)量量 化算法在多維空間上進(jìn)行推廣提出一種有效的矢量量化碼書設(shè)計(jì)方法 —— 經(jīng)典的 LBG 算法 [3]，也稱作GLA(General Lloyd Algorithm)算法。該算法基于最佳矢量量化器設(shè)計(jì)的最近鄰條件和質(zhì)心條件這兩個(gè)必要條件，其特點(diǎn)是概念清晰、算法理論嚴(yán)謹(jǐn)且算法實(shí)現(xiàn)方便。質(zhì)心條件是指在量化區(qū)間預(yù)先知道的情況下，使噪聲最小的各量化值應(yīng)是各量化區(qū)間的質(zhì)心 ； 最佳劃分條件是指在給定一組量化值的條件下，相應(yīng)的最佳量化區(qū)間的諸端點(diǎn)值應(yīng)為相鄰兩個(gè)量化值的中點(diǎn)。推廣到矢量量化編碼中， 最近鄰條件和質(zhì)心條件可以分別定義為 ： (1) 最近鄰條件 對(duì)已給定的輸出電平 (碼字 )集合 (碼書 )C，最優(yōu)劃分單元應(yīng)滿足 ： { : ( , )。 }ijR x d x y i j?? (34) 這種 劃 分也被稱為 Voronoi 劃分。 (2) 質(zhì)心條件 對(duì)已給定的劃分 { 。 1, 2,..., }iR i N? ，最優(yōu)碼字應(yīng)滿足 ： ()iiy cent R? (35) LBG 采用迭代的方法輪流滿足 (34)和 (35)以致達(dá)到矢量量化器設(shè)計(jì)的最優(yōu)(盡管是局部最優(yōu) )。設(shè)訓(xùn)練矢量集為 0 1 1{ , , ..., ,}MX x x x ?? ，則算法的具體步驟如下 ： （ 1）給定的初始碼書 ( 0 ) ( 0 ) ( 0 ) ( 0 )0 1 1{ , , ..., }NC y y y ?? ，令迭代次數(shù) n=0，平均失真( 1)D? ?? ，給定相對(duì)誤差門限 (0 1)???? 。 （ 2） 用碼書 ()nC 中的 各碼字作為質(zhì)心，根據(jù)最佳劃分原則把訓(xùn)練矢量集 X劃分為 N個(gè)胞腔 ( ) ( ) ( ) ( ) ( )0 1 1( , , .. ., ) ,n n n n nNiS S S S S?? 滿足 ( ) ( ) ( )01{ | ( , ) m in ( , ) , }n n ni i ijNS v d v y d v y V X? ? ?? ? ? (36) (3)計(jì)算平均失真 1( ) ( )0011 m in ( , )MnnijijND d x yM??? ? ?? ? (37) 判斷相對(duì)誤差是否滿足 ： ( 1) ( )()||nnnDDD ?? ? ? （ 38） 基于信源模型圖像編碼的數(shù)據(jù)壓縮算法的研究與實(shí)現(xiàn) 第 三 章 矢量量化圖像編碼 的研究 21 若滿足， 則停止算法，碼書 ()nC 就是所求的碼書。 否則，轉(zhuǎn)步驟（ 4）。 (4)根據(jù)最佳碼書條件，計(jì)算各胞腔的質(zhì)心， 即： ()( 1 ) ()1|| nini n vSiyvS? ?? ? （ 39） 由這 N 個(gè)新質(zhì)心 ( 1)niy? ， i=1， 2， ? ， N1形成新的碼書 ( 1)nC? ，置 n=n+1，轉(zhuǎn)步驟（ 2）。 由最佳量化器的兩個(gè)必要條件可以看出，量化失真是單調(diào)遞減的，因而上面的迭代算法必然是收斂的。由于上面的算法是概率密度相關(guān)的，所以設(shè)計(jì)時(shí)也要考慮輸入矢量的概率分布。所謂概率密度相關(guān)是指該量化器 (碼書 )生成之后，對(duì)目標(biāo)數(shù)據(jù)量化性能的好壞同目標(biāo)數(shù)據(jù)與訓(xùn)練數(shù)據(jù)的概率分布相似程度密切相關(guān)。一般來說，作為信源的圖像像素序列的幅值分布可以用足夠多的訓(xùn)練樣本的幅值分布情況來近似。對(duì)于一個(gè)固定的信源和訓(xùn)練方法而言，通常參與訓(xùn)練的信源矢量越多，得到的碼書越能在對(duì)大量此信源輸出的矢量進(jìn)行量化編碼時(shí)體現(xiàn)出優(yōu)良的編碼質(zhì)量。 另一方面， LBG 算法也存在訓(xùn)練計(jì)算量較大、訓(xùn)練結(jié)果受初始碼字影響較大以及自適應(yīng)不強(qiáng)等缺點(diǎn)，但是作為矢量量化碼書設(shè)計(jì)的經(jīng)典算法，它成為實(shí)現(xiàn)矢量量化器設(shè)計(jì)的一個(gè)基本模型和性能參照。除了 LBG 算法之外，學(xué)者們還提出了眾多基于計(jì)算復(fù)雜度、全局優(yōu)化性、并行處理、自適應(yīng)等不同考慮因素的矢量量化碼書設(shè)計(jì)方法。由于 LBG 算法具有平均失真單調(diào)不增特性，從這個(gè)角度看，其它碼書設(shè)計(jì)技術(shù)的有效性體現(xiàn)在所得到的碼書能用 LBG 算法改進(jìn)的余地很少。 碼 字 搜索 編碼時(shí)間是影響編碼系統(tǒng)實(shí)時(shí)性的一個(gè)重要因素，數(shù)據(jù)存儲(chǔ)量以及傳 輸效率也是壓縮編碼系統(tǒng)中的重要問題。編碼時(shí)間的降低主要通過減少編碼計(jì)算復(fù)雜度來完成，而傳輸時(shí)間和存儲(chǔ)量的降低往往通過降低比特率 (比特 1采樣 )來解決。矢量量化編碼過程最終歸結(jié)為在給定碼書中搜索與輸入矢量最匹配碼字的過程。假定碼書C={ K0 1 1 i, , ..., | RNy y y y? ?}，其中 N 為碼字個(gè)數(shù)，而 k 維輸入矢量 x=( 0 1 1, ,..., kx x x ? )與碼字 0 1 ( 1 )( , , ..., )i i i i ky y y y ?? }之間的失真測(cè)度， 采用平方誤差測(cè)度來描述，即 1 20( , ) ( )ki i ijid x y x y????? （ 310） 則矢量量化碼字搜索問題就是在碼書 C 中搜索出與輸入矢量 x 最匹配的碼字 jy ，使得 jy 與 x 之間的失真是所有碼字中最小的，即 01( , ) ( , )m inpjjNd x y d x y? ? ?? (311) 窮盡搜索 (Full Search， FS)算法是一種最原始最直觀的最近鄰碼字搜索算法，它需要計(jì)算 輸入矢量與所有碼字之間的失真并通過比較找出失真最小的碼字。由于FS 算法的計(jì)算復(fù)雜度由碼書尺寸和矢量維數(shù)決定，高效率矢量量化編碼系統(tǒng)往往采基于信源模型圖像編碼的數(shù)據(jù)壓縮算法的研究與實(shí)現(xiàn) 第 三 章 矢量量化圖像編碼 的研究 22 用大碼書和高維矢量，這種情況下采用 FS 算法計(jì)算復(fù)雜度將非常大，故減少碼字搜索的計(jì)算負(fù)擔(dān)是非常必要的。 快速碼字搜索算法可提高矢量量化編碼效率，也可運(yùn)用到 LBG 碼書設(shè)計(jì)算法的最優(yōu)化分步驟中以加快設(shè)計(jì)速度，而且還可推廣運(yùn)用到非編碼場(chǎng)合如數(shù)據(jù)檢索中。一種快速有效的碼字搜索算法必須具備良好的初始匹配碼字、合理的碼字搜索順序和強(qiáng)有力的碼字刪除準(zhǔn)則。顯然，如果碼字搜索開始于一個(gè)跟輸入矢 量比較接近的碼字，隨后的候選碼字將很容易檢驗(yàn)和排除，從而最大限度地節(jié)省計(jì)算量。另一方面，搜索范圍和順序決定了需要檢測(cè)碼字的最少數(shù)目，它在碼字搜索算法中是至關(guān)重要的。然而一種有效的碼字搜索算法往往需要附加計(jì)算量和額外存儲(chǔ)空間。附加計(jì)算量分為在線計(jì)算量 (占用編碼時(shí)間 )