【正文】 (b)定義域塊 jD 圖 分形編碼分塊表示圖 圖像分塊 對(duì)每一塊尋找近似不變集 保留 IFS 碼 編碼 恢復(fù) IFS 碼 IFS 代碼迭代生成不變集 圖像合并 恢復(fù)圖像 解碼 原始圖像 基于信源模型圖像編碼的數(shù)據(jù)壓縮算法的研究與實(shí)現(xiàn) 第 二 章 基于信源模型圖像壓縮的綜述 10 (2)找到合適的迭代函數(shù)系統(tǒng)。因此，分形圖像編碼的關(guān)鍵是如何找到最佳的仿射變換以和定義域塊 jD 。用 ),( LjiD ddj ??? 來(lái)表示經(jīng)過(guò)抽樣后，起始位置為 dd ji ??,( ） ，大小為 LL?的定義域塊 jD? 。這里的 LK ??2 。經(jīng)過(guò)同構(gòu)變換后，產(chǎn)生 jD? 。 灰度 變換 iG :灰度 變化包括比例因子 s 和補(bǔ)償因子 o ， 對(duì) jD? 做 灰度 變換oDsDG jji ???????)( ，產(chǎn)生 jD? 。對(duì)值域塊 iR 的分形編碼就是尋找最佳 i? ， i? ， iG 以及在定義域池里找到最佳的定義域塊 jD ，我們選擇 MSE 來(lái)度量塊之間的距離，使得下式最小 : 2,2 ))((),( odsrDRE jijiNji ???? ? （ 23） jir, 和 jid, 分別為值域塊 R 和經(jīng)過(guò)前兩種變換后的定義域塊 )()( jiijij DDD ??? ??????的像素值。 當(dāng)最佳仿射變換 i? ， i? ， iG 及定義域塊 jD 找到以后，經(jīng)過(guò)量化，然后存儲(chǔ)其參數(shù)。分形圖像編碼三個(gè)步驟如圖 。再做 16 16 的小方塊 DDi? ，它們是可以互為交迭的，這樣的 iD 總共達(dá) 58081)15256( 2 ?? 個(gè)。又有 8 種方法映射 iD 到 iR ，這意味著對(duì) 1024 個(gè) iR 中的任意一個(gè)要有 8 58081個(gè)比較。 為了縮短編碼時(shí)間，提高壓縮比， 1992 年， 發(fā)表一篇文章 ，提出改進(jìn)。 中等復(fù)雜子塊 :即灰度有一定的變化，但是不含有邊緣，對(duì)這類(lèi)子塊，旋轉(zhuǎn)和對(duì)折的意義不大，因此，為了提高壓縮比，省略旋轉(zhuǎn)和對(duì)折。 對(duì)于給定的值域塊，首先確定它的類(lèi)別。如果此值域塊為中等復(fù)雜子塊，由于 8 種變換的意義不大，因此減少了要搜索的定義域塊數(shù)目 。由以上分析可知，這種分類(lèi)方案可以加快編碼速度，而圖像的質(zhì)量基本不變。從嚴(yán)格的數(shù)基于信源模型圖像編碼的數(shù)據(jù)壓縮算法的研究與實(shí)現(xiàn) 第 二 章 基于信源模型圖像壓縮的綜述 12 學(xué)角度來(lái)說(shuō)，需要迭代無(wú)數(shù)多次才能得到吸引子。一般情況下， N=8。 分形圖像壓縮的特點(diǎn) 自從 1990 年 應(yīng)用局部迭代函數(shù)系統(tǒng)實(shí)現(xiàn)了分形圖像的自動(dòng)壓縮以來(lái)，人們對(duì)分形編碼進(jìn)行了不懈地研究，提出了許多改進(jìn)方法，這些方法主要針對(duì) Jacquin 方法中的兩大缺點(diǎn)，一是編碼計(jì)算量大和編碼時(shí)間較長(zhǎng) ； 二是壓縮比不夠理想進(jìn)行改進(jìn)。 現(xiàn)將分形圖像壓縮的優(yōu)點(diǎn)歸納如下 : 壓縮原理新穎 ：在分形圖像編碼中，利用原始圖像局部和局部的自相似性構(gòu)造一個(gè)迭代函數(shù)系統(tǒng)，并使該系統(tǒng)的吸引子盡可能逼近原圖像；在解碼過(guò)程中，只需要該迭代函數(shù)系統(tǒng)對(duì)任意初始圖像不斷迭代就可以重建圖像。 壓縮比高 ：由于自然界的景物圖像中都存在著確定的或統(tǒng)計(jì)的自相似性，而分形圖像編碼算法恰恰利用了原始圖像的自相似性，因此分形圖像編碼通常都能獲得較高的壓縮比和信噪比。 發(fā)展速度快 ：分形圖像編碼技術(shù)從提出到現(xiàn)在才僅僅十幾年的時(shí)間，但其發(fā)展速度之快令人驚訝 —— 國(guó)際上發(fā)表的文獻(xiàn)逐年增加，商業(yè)化的軟件、硬件己在市場(chǎng)上出售。但是，隨著計(jì)算機(jī)各方面技術(shù)特別是人工智能技術(shù)的不斷發(fā)展并取得突破后，分形圖像編碼克服時(shí)間長(zhǎng)的不足，達(dá)到極高倍的壓縮比并不是不可能的事。主要有兩種模型基方法 ： 一種為將待建模對(duì)象的表面采用一些表面幾何模型來(lái)建模，如平面或光滑曲面 ； 另外一種就是采用對(duì)象參數(shù)模型的方法建模。而后一種方法則先給定參數(shù)模型，然后估計(jì)模型的運(yùn)動(dòng)參數(shù)。當(dāng)然對(duì)一個(gè)普通場(chǎng)景欲獲得其詳細(xì)的模型是很困難的。比如在會(huì)議電視、可視電話中，一個(gè) 3D 的頭肩模型就足以描述序列中的大多數(shù)圖像前景。首先需要建立的是 3D模型，主要通過(guò)三種方法得到 :三維掃描設(shè)備、解剖學(xué)的方法和采用多幅立體圖像的方法。 等在 1970 年代提出了FACS(Facial Action Coding System)[3],是第一個(gè)將面部表情量化成數(shù)字來(lái)表征其強(qiáng)度的系統(tǒng)。 到 1987 年， 和 將紋理映射的概念引入到此方案中，這對(duì)模型基圖像編碼來(lái)講是一個(gè)里程碑，紋理映射 (Texture Mapping)[3]技術(shù)為相片現(xiàn)實(shí)化模型基編碼 (photo realistic modelbased coding)成為可能，迅速成為一個(gè)基于信源模型圖像編碼的數(shù)據(jù)壓縮算法的研究與實(shí)現(xiàn) 第 二 章 基于信源模型圖像壓縮的綜述 14 研究熱點(diǎn)，包括東京大學(xué)、 UIUC、 MIT 媒體實(shí)驗(yàn)室等一些著名的研究機(jī)構(gòu)都開(kāi)展了這項(xiàng)研究，他們各自對(duì)人臉作出了自己 的 3D 參數(shù)模型，用于視頻壓縮。必須承認(rèn)的一點(diǎn)，基于三維模型圖像編碼的研究還很不成熟。 模型基圖像壓縮的基本思想 模型基編碼根據(jù)所采用模型的不同類(lèi)型分為物體基圖像編碼和語(yǔ)義基圖像編碼兩種。由于模型中物體的不確實(shí)性增大 ,可利用的先驗(yàn)知識(shí)減少 ,壓縮比要小于語(yǔ)義基編碼。 圖 語(yǔ)義基圖像編碼框圖 建模是合成圖像的關(guān)鍵步驟。根據(jù)線框模型的形變不同 ，現(xiàn)有的模型可分為幾何模型和生理模型。另外，在對(duì)待全局參數(shù)和局部參數(shù)上 ,也有兩種方案：一種方案是將兩者分開(kāi)來(lái)測(cè)，另一種方案是將全局參數(shù)和局部參數(shù)同時(shí)測(cè)。但是我們可以采用一組“表情基本活動(dòng)單元”來(lái)表示各種臉部表情。任何臉部表情都可由不同的表情基本活動(dòng)單元 (AU) 來(lái)線性組合。 語(yǔ)義基編碼和傳統(tǒng)的波形編碼不同 ， 它利用圖像的宏觀特點(diǎn) ， 運(yùn)用了計(jì)算機(jī)視覺(jué)、計(jì)算機(jī)圖形學(xué)、圖像處理、模式識(shí)別等技術(shù) ， 為圖像編碼開(kāi)辟了新途徑。不過(guò) ， 它面臨以下 3 個(gè)實(shí)際問(wèn)題： (1) 如何將線框模型自動(dòng)匹配到具體人臉上 ； (2) 實(shí)時(shí)進(jìn)行運(yùn)動(dòng)跟蹤 ,即不斷提供全局和局部運(yùn)動(dòng)參數(shù) ； (3) 盡快完成戴眼鏡的人臉模型。 人臉模型化 模型基編碼的前提是人臉對(duì)象的模型化 [3]表示，通常，采用網(wǎng)格化的三維圖形來(lái)表示。三角形網(wǎng)格結(jié)構(gòu)用編碼信息隱含說(shuō)明。預(yù)測(cè)編碼網(wǎng)格的三角形結(jié)構(gòu)與參考網(wǎng)格相同，只是接點(diǎn)位置有所變化，接點(diǎn)的位移表明了網(wǎng)格的運(yùn)動(dòng)，可以用當(dāng)前網(wǎng)格對(duì)象平面與參考網(wǎng)格對(duì)象平面的接點(diǎn)運(yùn)動(dòng)向量來(lái)描述。人臉的形狀、紋理和表示由包含人臉定義參數(shù)集（ FDP）和人臉動(dòng)畫(huà)參數(shù)集 （ FAP）的碼流來(lái)控制。這個(gè)臉一旦被展現(xiàn)，就可以馬上從碼流中接 受 FAP 來(lái)生成人臉的活動(dòng)，例如表情和語(yǔ)言等。一個(gè)完整的人臉模型通過(guò)FDP 集用類(lèi)似向場(chǎng)景圖中插入人臉結(jié)點(diǎn)的方法生成。他們描述了基本人臉活動(dòng)的一個(gè)完全集，因此可以表示絕大部分自然人臉。 這些單元是為了用統(tǒng)一的方式描述人臉模型而定義的， 以便對(duì)表情語(yǔ)言生成合理的結(jié)果。 所有 FAP 表示了人臉特征位置的移動(dòng)。FDP 參數(shù)通常是每一個(gè)鏡頭傳輸一遍，然后才是壓縮的 FAP 參數(shù)。 在對(duì)人臉網(wǎng)格化之后，就可以著手建立模型基編碼系統(tǒng)了。只有這樣，發(fā)端才能獲得與收端相同的綜合后的重構(gòu)圖像，并將后則與原始圖像進(jìn)行補(bǔ)交。由此可以注意到模型基圖像編碼與經(jīng)典的圖像編碼有兩點(diǎn)顯著的不同： 一是編碼失真。這些失真同量化誤差相比， 將更難以為人眼所察覺(jué)。 二是如何評(píng)價(jià)重建圖像質(zhì)量。究竟采用什么函數(shù)才能定量地計(jì)算重建圖像的“失真度”，正是模型法需要研究和解決的一個(gè)關(guān)鍵問(wèn)題。而在其他 視頻編碼方法如 MPEG2 標(biāo)準(zhǔn)中，如果提高圖像分辨率，則所需傳輸?shù)拇a率也會(huì)大幅增加。原因在于，攝像機(jī)拍攝自然景物的過(guò)程是三維景物投影到攝像平面的過(guò)程，其間丟失了三維景物的深度信息，而要重建這些深度信息是非常困難的。 基于信源模型圖像編碼的數(shù)據(jù)壓縮算法的研究與實(shí)現(xiàn) 第 三 章 矢量量化圖像編碼 的研究 18 第三 章 矢量量化圖 像編碼 的研 究 矢量量化 [3](Vector Quantization， VQ)利用了相鄰采樣之間的相關(guān)性，基本思想是在量化時(shí)用輸出組集合 (碼書(shū) )中最匹配的一組輸出值 (碼字 )代替輸入的一組采樣值 (輸入矢量 )。 1978 年， Buzo 第一個(gè)提出實(shí)際的矢量量化器。 基本的矢量量化器可以定義為從 k 維歐幾里德空間 KR 到一個(gè)有限子集 C 的一個(gè)映射，即 Q： KR ?C，其中 C={ K0 1 1 i, , ..., | RNy y y y? ?}稱為碼書(shū)， N為碼書(shū)大小。每一個(gè)矢量 x=( 0 1 1, ,..., kx x x ? )都能在碼書(shū) C={ 0 1 1 i, ,..., |Ny y y y? }中找到最匹配碼字 py =Q(x|x KR? )。這 N個(gè)子空間 0 1 1, ,..., Ns s s ? 滿 足 ： 10 ()Ni i i js s s s i j?? ? ? ? ?且 （ 32） 矢量量化編碼與解碼過(guò)程如圖 。傳輸時(shí)僅傳輸該碼字的索引。 用數(shù)學(xué)的觀點(diǎn)來(lái)描述，可以將矢量 S= 0 1 1{ , ,..., }Ns s s ? 看作是在 N 維空間中的一個(gè)點(diǎn)。落在區(qū)域 iR 上的所有矢量都用同一個(gè)矢量 11[ , ,..., ]i i i iNr r r r? 來(lái)表示，這里矢量稱為碼字(Codeword)， 由所有 L個(gè)碼字組成的集合稱為碼書(shū) (Codebook)。矢量量化的編碼結(jié)果并不是碼字，而是碼字在碼書(shū)中的索引值。而量化質(zhì)量則體現(xiàn)為原始矢量同其碼字之間的誤差。 圖 書(shū) 設(shè)計(jì) 矢 量量化的首要問(wèn)題是設(shè)計(jì)出性能好的碼書(shū)。假設(shè)采用平方誤差測(cè)度作為失真測(cè)度，訓(xùn)練矢量數(shù)目為 M(M N)，則碼書(shū)設(shè)計(jì)的過(guò)程可看作對(duì)這 M 個(gè)訓(xùn)練矢量進(jìn)行N 數(shù)目最優(yōu)分類(lèi)的過(guò)程，并把各類(lèi)的質(zhì)心 矢量作為碼書(shū)的碼字。然而，在 N 和 M 比較大的情況下，建立這樣一個(gè)大尺寸的碼索引 P 索引 P 輸出碼字 py 輸入矢量 X 搜索最匹配碼字 py 信 道 查找索引P 對(duì)應(yīng)的碼字 py 0y 1y …… N1y? 0y 1y …… N1y? 碼書(shū)C 碼書(shū)C 基于信源模型圖像編碼的數(shù)據(jù)壓縮算法的研究與實(shí)現(xiàn) 第 三 章 矢量量化圖像編碼 的研究 20 書(shū)會(huì)帶來(lái)存儲(chǔ)上的問(wèn)題，更嚴(yán)重的是由于碼書(shū)設(shè)計(jì)和編碼時(shí)碼字搜索的計(jì)算復(fù)雜度隨著碼書(shū)尺寸 N 的增大呈指數(shù)增加，使得大尺寸碼書(shū)的應(yīng)用受到實(shí)際編碼設(shè)備的限制而難以實(shí)現(xiàn)。對(duì)于灰度、色度和紋理信息豐富的圖像信源而言，要在碼書(shū)設(shè)計(jì)算法的性能和計(jì)算量之間的取得平衡并不容易。該算法基于最佳矢量量化器設(shè)計(jì)的最近鄰條件和質(zhì)心條件這兩個(gè)必要條件，其特點(diǎn)是概念清晰、算法理論嚴(yán)謹(jǐn)且算法實(shí)現(xiàn)方便。推廣到矢量量化編碼中， 最近鄰條件和質(zhì)心條件可以分別定義為 ： (1) 最近鄰條件 對(duì)已給定的輸出電平 (碼字 )集合 (碼書(shū) )C，最優(yōu)劃分單元應(yīng)滿足 ： { : ( , )。 (2) 質(zhì)心條件 對(duì)已給定的劃分 { 。設(shè)訓(xùn)練矢量集為 0 1 1{ , , ..., ,}MX x x x ?? ，則算法的具體步驟如下 ： （ 1）給定的初始碼書(shū) ( 0 ) ( 0 ) ( 0 ) ( 0 )0 1 1{ , , ..., }NC y y y ?? ，令迭代次數(shù) n=0，平均失真( 1)D? ?? ，給定相對(duì)誤差門(mén)限 (0 1)???? 。 否則，轉(zhuǎn)步驟（ 4）。 由最佳量化器的兩個(gè)必要條件可以看出，量化失真是單調(diào)遞減的，因而上面的迭代算法必然是收斂的。所謂概率密度相關(guān)是指該量化器 (碼書(shū) )生成之后，對(duì)目標(biāo)數(shù)據(jù)量化性能的好壞同目標(biāo)數(shù)據(jù)與訓(xùn)練數(shù)據(jù)的概率分布相似程度密切相關(guān)。對(duì)于一個(gè)固定的信源和訓(xùn)練方法而言，通常參與訓(xùn)練的信源矢量越多，得到的碼書(shū)越能在對(duì)大量此信源輸出的矢量進(jìn)行量化編碼時(shí)體現(xiàn)出優(yōu)良的編碼質(zhì)量。除了 LBG 算法之外，學(xué)者們還提出了眾多基于計(jì)算復(fù)雜度、全局優(yōu)化性、并行處理、自適應(yīng)等不同考慮因素的矢量量化碼書(shū)設(shè)計(jì)方法。 碼 字 搜索 編碼時(shí)間是影響編碼系統(tǒng)實(shí)時(shí)性的一個(gè)重要因素，數(shù)據(jù)存儲(chǔ)量以及傳 輸效率也是壓縮編碼系統(tǒng)中的重要問(wèn)題。矢量量化編碼過(guò)程最終歸結(jié)為在給定碼書(shū)中搜索與輸入矢量最匹配碼字的過(guò)程。由于FS 算法的計(jì)算復(fù)雜度由碼書(shū)尺寸和矢量維數(shù)決定，高效率矢量量化編碼系統(tǒng)往往采基于信源模型圖像編碼的數(shù)據(jù)壓縮算法的研究與實(shí)現(xiàn) 第 三 章 矢量量化圖像編碼 的研究 22 用大碼書(shū)和高維矢量，這種情況下采用 FS 算法計(jì)算復(fù)雜度將非常大，故減少碼字搜索的計(jì)算負(fù)擔(dān)是非常必要的。一種快速有效的碼字搜索算法必須具備良好的初始匹配碼字、合理的碼字搜索順序和強(qiáng)有力的碼字刪除準(zhǔn)則。另一方面，搜索范圍和順序決定了需要檢測(cè)碼字的最少數(shù)目，它在碼字搜索算法中是至關(guān)重要的。附加計(jì)算量分為在線計(jì)算量 (占用編碼時(shí)間