【正文】 那么就能在很大程度上減少后面碼書在迭代過程中所耗費的時間和空間占用。每個胞腔的質(zhì)心為：，從而獲得新的碼書Y，并另迭代次數(shù)t加1，重復(fù)步驟 (c)。(d)計算當(dāng)前胞腔劃分的平均失真，公式為：，若前后兩次平均失真的相對誤差滿足，或達到限制的迭代次數(shù)T，則停止算法，而當(dāng)前碼書就是所求的最終碼書，否則轉(zhuǎn)到下一個步驟，繼續(xù)執(zhí)行。根據(jù)某種生成算法，得到初始碼書，初始碼書的選取很關(guān)鍵，直接影響到收斂速度和最終碼書的質(zhì)量。給定最大迭代次數(shù)T的值，當(dāng)前迭代次數(shù)t=0，平均失真D趨于無窮大，并給定相對誤差值TermTh。而每次迭代總可以將平均失真降低一些，使碼書的性能逐漸提高。 LBG算法及其初始碼書生成算法LBG算法是基于最優(yōu)矢量量化器最近鄰條件和質(zhì)心條件的實現(xiàn)碼書設(shè)計的一種迭代算法。質(zhì)心條件為：當(dāng)給定了空間的劃分后，最優(yōu)碼字Yi是對應(yīng)胞腔Ri的質(zhì)心，Yi=cent(Ri) 。質(zhì)心條件：給定劃分的最優(yōu)碼書條件，即給定了編碼器的最優(yōu)解碼器條件。假如給定了碼書，那么輸入矢量空間的最優(yōu)劃分應(yīng)該滿足最近鄰條件，即每個輸入矢量應(yīng)該劃分到離它最近的碼字，或者是以離它最近的碼字來重構(gòu)該輸入矢量。假設(shè)有一個矢量量化器，其輸入矢量空間RK的N個劃分為Ri={R1,R2,…RN}，其碼書尺寸為N，碼書為Y={Y1,Y2,…YN}，則可以按照給定碼書的最優(yōu)劃分和給定劃分的最優(yōu)碼書條件，來刻畫最優(yōu)矢量量化器需要滿足的條件。 矢量量化碼書設(shè)計的最優(yōu)條件矢量量化器的設(shè)計目的就是為了尋求一個K維矢量量化器Q(X)，使得待編碼矢量序列的總體失真D最小，總體失真一般可以采用某種失真測度的統(tǒng)計平均值來描述，比如平方誤差測度的統(tǒng)計平均值。 矢量量化的碼書設(shè)計方法一般情況下，基于窮盡搜索方法的矢量量化碼書設(shè)計，能夠得到較好的量化質(zhì)量，因此很多改進的矢量量化器的設(shè)計都是以基于窮盡搜索方法矢量量化碼書設(shè)計算法為基礎(chǔ)，而該算法就是經(jīng)典的LBG算法。根據(jù)窮盡搜索算法的缺點，專家提出了許多改進的快速搜索算法，算法有：基于不等式判據(jù)的快速碼字搜索算法；基于變換域的快速碼字搜索算法；基于金字塔結(jié)構(gòu)的快速碼字搜索算法等。上文中已經(jīng)論述了，在采用平方誤差測度時，矢量量化的時間和空間復(fù)雜度，如果碼書較長，碼字的維數(shù)也大的話，計算的復(fù)雜度將會變得很大。碼字搜索，是指在已經(jīng)給定碼書的情況下，對于當(dāng)前輸入矢量，采用某種度量方法，在碼書中搜索出與輸入矢量之間失真最小的碼字。這些算法都旨在提高矢量量化碼書的質(zhì)量和降低計算復(fù)雜度。針對以上這些問題，專家學(xué)者們提出了許多改進算法。而且最終碼書只能收斂到基于訓(xùn)練矢量的局部最優(yōu)，碼書的生成速度也比較慢。其二由于LBG是基于聚類方法的，需要不斷迭代，而每次迭代，需要從碼書中查找到最近鄰碼字，這將耗費大量的存儲空間和繁瑣的計算時間。LBG算法是基于最佳矢量量化器的最佳劃分和最佳碼書的生成這兩個條件的，該算法物理概念清晰、算法理論嚴(yán)謹(jǐn)、實現(xiàn)容易。碼書設(shè)計的過程就是找到一種最佳方案，把M個訓(xùn)練矢量分成N類，并將各類的質(zhì)心矢量作為碼書的碼字。 碼書設(shè)計矢量量化設(shè)計的首要問題和核心問題就是設(shè)計出性能好的碼書。 矢量量化的關(guān)鍵技術(shù)介紹在上文中提過，矢量量化器的設(shè)計有幾個關(guān)鍵的環(huán)節(jié)，矢量量化器設(shè)計的成敗和好壞基本取決于這幾個關(guān)鍵環(huán)節(jié)的設(shè)計是否有效，這些環(huán)節(jié)也正是矢量量化技術(shù)研究的關(guān)鍵點。至于空間復(fù)雜度，基本的窮盡搜索矢量量化器的空間復(fù)雜度為kN。第一種，考慮到每個輸入矢量所用到的乘法、加法和比較次數(shù)，則其復(fù)雜度為kN次乘法加(2k1)N次加法再加(N1)次比較。(c)假設(shè)有一幅MN的L級灰度圖像，其原始圖像像素值為，而重構(gòu)圖像像素值為，則有： 均方誤差 （公式5） 信噪比 （公式6） 峰值信噪比 （公式 7） 矢量量化的實現(xiàn)復(fù)雜度矢量量化的復(fù)雜度分為時間復(fù)雜度和空間復(fù)雜度，且復(fù)雜度隨矢量維數(shù)的增加而呈指數(shù)形式增加，這成為了高維矢量量化的實現(xiàn)障礙之一。通過輸入矢量X與其對應(yīng)的重構(gòu)矢量Y=Q(X))的平方歐幾里德距離可導(dǎo)出為均方誤差，其公式為， （公式3）(b)Minkowshi測度矢量。以下是幾種常見的失真測度方法。在模式匹配問題中，一個關(guān)鍵的問題就是重構(gòu)矢量與輸入矢量之間的差異的度量。按照一樣的電平數(shù)，當(dāng)采用標(biāo)量量化時，每個采樣需要log2M比特，而矢量量化時，每個采樣僅需log2N/k比特。若系統(tǒng)的輸入信號是一個矢量序列，則每個輸入矢量所需的比特數(shù)為R=kr，并稱該比特數(shù)為比特率或傳輸率。編碼速率定義為每個輸入采樣所需要的平均比特數(shù)。矢量量化器的性能評價指標(biāo)具體有壓縮比、信噪比、編碼速率、實現(xiàn)復(fù)雜度和失真測度等客觀性評價標(biāo)準(zhǔn)以及主觀性評價標(biāo)準(zhǔn)。相比標(biāo)量量化，矢量量化的優(yōu)勢是顯然的，一個k維的最佳矢量量化器的性能總是優(yōu)于k個最佳標(biāo)量量化器。如果矢量量化的碼書長度越長，即碼字越多，則重構(gòu)矢量的失真就會越小，只要根據(jù)給定的失真閾值，選取適當(dāng)?shù)拇a字?jǐn)?shù)量，則該矢量量化可以達到很好的編碼效果，因此選取適當(dāng)?shù)拇a字?jǐn)?shù)量也是矢量量化的關(guān)鍵。矢量量化器模型如下： 最近鄰規(guī)則量化編碼碼書碼書 圖2圖中的最近鄰規(guī)則用來確定與輸入矢量對應(yīng)的碼字，用某種測度準(zhǔn)則計算出與該輸入矢量最近的碼字，來量化和重構(gòu)該輸入矢量，從而可以確定輸入矢量對應(yīng)的碼字。因此，在矢量量化器實際編碼時，只需要在發(fā)送端記錄下代表矢量的下標(biāo)索引i即可，并不需要發(fā)送整個代表矢量，所以矢量量化編碼就是按照一定的失真測度，在碼書中搜索出與輸入矢量最匹配的碼字，并記錄下該碼字的索引，而在傳輸時只需要傳輸該索引。并設(shè)子空間Ri的質(zhì)心，即代表矢量為，則所有子空間質(zhì)心構(gòu)成的向量集，就是矢量量化器的輸出空間，稱其為碼書，是碼字，J是碼書的長度。矢量量化在本質(zhì)上是一個聚類算法，其碼書的形成是一個不斷迭代的過程。其后，人們對矢量量化技術(shù)的關(guān)注和研究越來越深入，專家們以LBG算法為基礎(chǔ)，將神經(jīng)網(wǎng)絡(luò)、遺傳算法等結(jié)合到矢量量化技術(shù)的研究中，并取得一定的成效，使矢量量化器更加高效、快速。矢量量化技術(shù)憑借其壓縮比大、解碼簡單等優(yōu)點，引起了人們的極大關(guān)注，并在圖像壓縮等領(lǐng)域嶄露頭角。為了合理利用樣本之間的相關(guān)性，可以采用對多個樣本進行聯(lián)合量化的方法，用一個值代替一組相似的值，這樣一來不僅可以減少量化誤差，同時還提高了壓縮比，這種方法便是矢量量化。標(biāo)量量化又叫一維量化，是一個多對一映射過程，其每次僅量化一個樣本值。一般的量化過程是根據(jù)一組判決電平，每個判決電平覆蓋一定的區(qū)間，而所有的判決電平將覆蓋整個有效取值區(qū)間，量化便是將采樣值與判決電平進行比較，若采樣值的幅度落在某個判決電平的覆蓋區(qū)間上，則規(guī)定該采樣值取這個區(qū)間的代表值。而編碼的主要任務(wù)是利用圖像信號的統(tǒng)計特性以及人的視覺心理特性對圖像信號進行壓縮，從而減少數(shù)據(jù)的空間存儲量以方便處理與傳輸。由于采樣后的離散圖像還不是數(shù)值圖像，必須進行量化處理，量化就是將離散圖像的值表示為與其幅度成比例的整數(shù)。在通常情況下，圖像壓縮的一般流程可如下表示：采樣量化編碼圖1在采樣之前可以對圖像進行某種變換，將圖像信息集中分布到少數(shù)成分上，以便于圖像的后續(xù)處理，變換可以使圖像信息熵減少，因而圖像的壓縮率就能提高，變換是可逆的，常用的變換方法有離散余弦變換、離散傅里葉變換等。率失真理論則說明了，對于一個給定的信源分布與失真度量，在特定的碼率下能達到的最小失真；或為了滿足一定的失真限制，最小描述碼率是多少。設(shè)某個無記憶獨立信源xk，如果它出現(xiàn)的概率是pk，那么它包含的信息是： （公式1）其中I(xk)稱為自信息量，它表明一個概率小的符號出現(xiàn)將帶來更大的信息量，也就是說信息量與該符號的概率成反比。第二章 基于矢量量化的圖像壓縮編碼原理在深入探討矢量量化圖像編碼原理壓縮之前，先介紹下一般圖像壓縮技術(shù)方法的基本原理，從而更好地理解和區(qū)別矢量量化編碼與其它壓縮編碼算法。傳統(tǒng)編碼的編碼方法，一般是將信號經(jīng)過某種映射變換成為數(shù)的序列，然后進行標(biāo)量量化，再對其進行熵編碼，而矢量量化編碼則是把輸入的數(shù)據(jù)分成許多互不重疊的組，將每組看作一個k維矢量，再根據(jù)按照某種算法生成的碼書，查找與當(dāng)前輸入向量最相近的碼字，作為該輸入向量的量化結(jié)果，然后只要傳輸該碼字的在碼書中的索引即可，接收方根據(jù)碼字索引所在碼書中查找到對應(yīng)的碼字，重構(gòu)輸入向量。詞典編碼雖然處理過程較為復(fù)雜，但是完全可逆，有較高的壓縮比，對機器硬件要求也不高，且可以壓縮任何類型的數(shù)據(jù)。算術(shù)編碼實現(xiàn)比較復(fù)雜，但其效率比赫夫曼編碼好。赫夫曼編碼保證了碼的唯一可用性，但由于編碼長度可變而且不統(tǒng)一，導(dǎo)致譯碼時間長，硬件實現(xiàn)難度大。其實現(xiàn)簡單，容易理解。常用的圖像壓縮編碼有以下幾種。其他幾種冗余還有，時間冗余、知識冗余等。編碼冗余也叫信息熵冗余，是根據(jù)圖像的編碼冗余思想進行編碼