基于矢量量化編碼的數(shù)據(jù)壓縮算法的研究分析

2. 質(zhì)心條件 (CentroidC ondition)
利用由上面步驟得到的訓(xùn)練矢量劃分集 重新計(jì)算它們各自的質(zhì)心，得到新的碼本：
（3.3）
（3.4）
式中， 代表子集Si中訓(xùn)練矢量的個(gè)數(shù)。
各種矢量量化碼本設(shè)計(jì)算法基本都是上面兩個(gè)步驟的交替迭代的基礎(chǔ)上得到最后的碼本。不難看出，碼本生成過(guò)程中的計(jì)算量是隨著碼本矢量的維數(shù)k和碼本尺寸N的增大而急劇增長(zhǎng)的，對(duì)于需要高維大碼本的矢量量化器來(lái)說(shuō)，測(cè)試所有可能的碼本來(lái)尋求全局最優(yōu)碼本將是十分困難的。為了克服這個(gè)困難，Linde . Buzo和Gray提出了經(jīng)典的LBG算法。
1980年Linde，Buzo和Gray將Lloyd算法推廣到矢量空間【8】， 算法的步驟簡(jiǎn)單描述如下：
Step 1 ：給定初始碼本 ，令迭代次數(shù)m=0，平均失真初始值為 ，給定失真下降閾值 ；
Step 2：用碼本 中的碼字作為質(zhì)心，根據(jù)最佳劃分原則將訓(xùn)練矢量集x劃分為對(duì)應(yīng)于每個(gè)碼字的N個(gè)聚類(lèi)，
滿(mǎn)足： ；
Step 3：計(jì)算本次迭代的平均失真 判斷相對(duì)誤差是否滿(mǎn)足 ，若滿(mǎn)足，則停止算法，碼本C(m)就是所求的碼本;
否則，轉(zhuǎn)Step 4；
Step 4：根據(jù)質(zhì)心條件，計(jì)算各聚類(lèi)的質(zhì)心，即公式（3.5）：
（3.5）
產(chǎn)生新碼本 并置m=m+1，轉(zhuǎn)Step 2
END：算法結(jié)束。

對(duì)于 LBG算法來(lái)說(shuō)，初始碼本選擇的好壞將直接影響到后面的迭代計(jì)算結(jié)果，一個(gè)不好的初始碼本會(huì)降低算法的收斂速度和最終碼本的性能。因此在LBG算法中要對(duì)初始碼本的選擇作一定的處理。如果初始碼本隨機(jī)產(chǎn)生，即直接從訓(xùn)練序列中隨機(jī)選擇N個(gè)訓(xùn)練矢量作為初始碼字，構(gòu)成初始碼本，可能會(huì)選到一些非典型的訓(xùn)練矢量作碼字，因而該胞腔可能含有少數(shù)幾個(gè)矢量甚至只有1個(gè)。另外，有可能把某些空間分得過(guò)疏。這可能會(huì)導(dǎo)致碼本中的有些碼字得不到充分利用，設(shè)計(jì)出來(lái)的碼本性能就可能較差。
3．1．2 MD算法
最大下降（MD）【13】碼本設(shè)計(jì)算法與經(jīng)典的LBG算法不同，它是一種分裂算法，而沒(méi)有初始碼本。在MD算法中，首先將訓(xùn)練矢量集 作為一個(gè)原始包腔，然后該包腔被它的最優(yōu)分割超平面分成兩個(gè)子包腔。依此類(lèi)推，每次分裂產(chǎn)生一個(gè)包腔，直到生成最后的N個(gè)包腔，計(jì)算它們的質(zhì)心，就可以得到設(shè)計(jì)的碼本C={y}i=1,2,…,N)。與LBG算法相比，MD算法的計(jì)算量少并且所產(chǎn)生的碼本性能好。另一方面，MD算法傾向于分割元素較多的胞腔，而不會(huì)去分割只有一個(gè)元素的胞腔，避免了非典型碼字的形成，提高了碼本的整體性能。在MD算法中，從L個(gè)包腔向(L+ l )個(gè)包腔擴(kuò)展時(shí)，先要找出每個(gè)現(xiàn)有包腔的最優(yōu)分割超平面，并計(jì)算它們各自帶來(lái)的失真下降幅度，然后依據(jù)失真下降最大準(zhǔn)則來(lái)選擇究竟對(duì)哪一個(gè)包腔進(jìn)行分裂。這在k維空間里是比較困難的事，需要大量的計(jì)算和比較。圖3.2所示為MD算法的分裂過(guò)程示意圖，圖中每一步驟中有陰影的包腔 是當(dāng)前符合失真下降最大準(zhǔn)則的包腔，它被最優(yōu)分割超平面分成下面的兩個(gè)子包腔 和 。從L個(gè)包腔生成(L+ 1)個(gè)包腔的具體實(shí)現(xiàn)描述如下：
設(shè)超平面 將某胞腔 分成兩個(gè)非空胞腔如式（3.6）所示：

（3.6）
式中 ， ， ， T表示轉(zhuǎn)置。
當(dāng) 中的矢量被質(zhì)心 量化時(shí)，胞腔的失真D(Si)定義為公式（3.7）： （3.7）
則由分割超平面H,劃分胞腔S,所引起的失真下降可表示為式（3.8）：
（3.8）
若采用平方誤差測(cè)度，則式(3.8)可以化簡(jiǎn)為式（3.9）：
或 （3.9）
式中， 分別為 的元素個(gè)數(shù)， 。分別為 的質(zhì)心。
從式(3.9)中可以看出，若胞腔 、 非空，則失真下降函數(shù)滿(mǎn)足 。
我們將胞腔Si的最優(yōu)分割超平面 定義為使胞腔 具有最大失真下降 的超平面。MD算法先計(jì)算出所有胞腔的最大失真下降值 ， ，然后找出最大的最大失真下降值 ，即 ，最后將胞腔Sp分割成兩個(gè)新胞腔。所以，L+l個(gè)胞腔是通過(guò)劃分L個(gè)胞腔中具有最大失真下降的胞腔并保持其余胞腔不變而得到的。值得注意的是，每次分裂包腔時(shí)，并不需要重新計(jì)算所有包腔的失真函數(shù)，而只需找到新增加的兩個(gè)包腔的最優(yōu)分割超平面，計(jì)算它們各自的失真函數(shù)，再與其它包腔的失真函數(shù)值進(jìn)行比較即可找出新的滿(mǎn)足失真下降最大準(zhǔn)則的包腔。產(chǎn)生最后的N個(gè)胞腔，一共需計(jì)算(2N-3)次最大失真下降函數(shù)。
3．1．3 碼書(shū)設(shè)計(jì)算法比較
LBG算法是一種迭代算法，其迭代操作是標(biāo)量量化勞埃德迭代操作的直接推廣。LBG算法他具有如下的優(yōu)點(diǎn)：
1. 不用初始化計(jì)算，可大大減少計(jì)算時(shí)間
2. 初始碼字選自訓(xùn)練序列，無(wú)空胞腔問(wèn)題
LBG算法在具有如上的優(yōu)點(diǎn)的同時(shí)也有一些缺點(diǎn)和不足:
1. 在每次迭代的最佳劃分階段，從碼書(shū)中搜索訓(xùn)練矢量的最近碼字需要大量的存儲(chǔ)空間和繁瑣的計(jì)算；
2. 初始碼書(shū)的選擇影響碼書(shū)訓(xùn)練的收斂速度和最終碼書(shū)的性能；
碼書(shū)設(shè)計(jì)的第一個(gè)缺點(diǎn)可采用各種快速碼字搜索算法來(lái)解決，但這些算法無(wú)法改善碼書(shū)的性能，第2個(gè)缺點(diǎn)產(chǎn)生的原因是:LBG算法是一種下降算法，每次迭代總能減少(至少保持不變)平均失真，而且每次迭代通常只能產(chǎn)生碼書(shū)的局部變化，即每次迭代后，與舊碼書(shū)相比，新碼書(shū)不可能有非常大的變化。因此，一旦選定初始碼書(shū)，該算法只能得到局部最優(yōu)的碼書(shū)，即LBG算法一般不能得到全局最優(yōu)的碼書(shū)。
與LBG算法相比，MD算法的計(jì)算量少且所產(chǎn)生的碼書(shū)性能好。另一方面， MD算法傾向于分割元素較多的胞腔，而不會(huì)去分割只有一個(gè)元素的胞腔，而這種情況在LBG算法中卻常常出現(xiàn)。然而，在MD算法中，多維胞腔的最優(yōu)分割超平面的搜索是一個(gè)非常困難的問(wèn)題。為減少計(jì)算量，這些算法的搜索范圍被限制在與矢量空間的基本矢量正交的超平面上，這個(gè)矢量空間可由離散余弦變換(DCT)得到。但是，在這種限制條件下，算法常常搜索不到最優(yōu)超平面。
3．2 碼字搜索算法
3．2．1 基于不等式的快速碼字搜索算法
1. 部分失真不等式排除法
部分失真搜索(Partial Distortion Search，PDS)算法【12】是一種較簡(jiǎn)單有效的最近鄰搜索算法。它的基本思想是：在計(jì)算某個(gè)碼字與輸入矢量之間失真測(cè)度的過(guò)程中，始終判斷累加的部分失真是否已經(jīng)超過(guò)目前的最小失真，如果一旦超出則終止該碼字與輸入矢量之間的失真計(jì)算，轉(zhuǎn)而開(kāi)始計(jì)算另一個(gè)碼字與輸入矢量的失真測(cè)度。PDS常被用來(lái)與其他快速搜索算法結(jié)合起來(lái)運(yùn)用，來(lái)排除其它快速算法最后無(wú)法排除的碼字。
在編碼過(guò)程中計(jì)算前面部分維數(shù)的失真距離，若其超出當(dāng)前最小距離，則排除此碼字為最匹配碼字，否則繼續(xù)搜索其它碼字。
據(jù)如下（3.10）所示的柯西一許瓦爾茲不等式【14】：
（3.10）
可得一個(gè)不等式判據(jù) 若 ，則能保證 ，yi可被排除。因?yàn)閨yi|可離線計(jì)算，所以節(jié)省了計(jì)算量。
首先判斷 是否成立，若成立，則排除碼字Yi否則，再判斷是否滿(mǎn)足 ，若滿(mǎn)足，yi也可被排除。這縮小了搜索范圍，他們還融入部分距離失真法節(jié)省計(jì)算量。雙測(cè)試法的缺陷在于要求矢量的所有分量都為正值，而圖像變換域編碼中產(chǎn)生的變換系數(shù)有正有負(fù)，必須對(duì)這些系數(shù)進(jìn)行正補(bǔ)償，使所有矢量分量均大于零。
2. 整數(shù)投影法
整數(shù)投影法是一種適用于圖像矢量量化的快速碼字搜索算法。他們?yōu)槊總€(gè)m×m圖像塊 ，定義三種整數(shù)投影【14】，如下公式（3.11）（3.12）（3.13）所示：
塊狀投影： （3.11）
垂直投影： （3.12）
水平投影： （3.13）
在這三種投影的基礎(chǔ)上定義了三個(gè)不等式條件，公式（3.14）（3.15）（3.16）所示：
（3.14）
（3.15）
（3.16）
可以證明，只要不滿(mǎn)足上述任何一個(gè)條件，可排除yi是最匹配碼字。
3. 三角不等式法
基于三角不等式d(Y i,yj) d (x ,Yi)+ d (x ,yj)提出三種改進(jìn)算法【14】。第一種算法先計(jì)算碼書(shū)中每?jī)蓚€(gè)碼字之間的距離，以當(dāng)前匹配碼字yi為中心，2hi(h i為輸入矢量與當(dāng)前匹配碼字之間的歐氏距離)為半徑劃定搜索范圍，即只搜索滿(mǎn)足d(yj,yi) 2hi的碼字yj,j= 1,2,…,N；
第二種算法是將搜索范圍定為滿(mǎn)足：x-hirkrx+hi，
其中rx為輸入矢量的范數(shù)，rk為碼字的范數(shù)，hi為輸入矢量與當(dāng)前匹配碼字之間的歐氏距離，此種算法不同于第一種算法，無(wú)須計(jì)算碼字之間的距離；
第三種算法取前兩種算法搜索區(qū)域的交集作為搜索區(qū)域。
這三種算法都涉及如何確定初始匹配碼字的問(wèn)題，一般取范數(shù)與輸入矢量范數(shù)最相近的碼字。第一、三種算法比第二種算法要多耗費(fèi)存儲(chǔ)空間來(lái)存儲(chǔ)碼字之間的距離。最小均方誤差編碼算法，取一長(zhǎng)訓(xùn)練矢量序列，計(jì)算每個(gè)Voronoi區(qū)域內(nèi)的訓(xùn)練矢量與該區(qū)域質(zhì)心矢量(碼字) 的最大距離di，求平方根后得ri，按其升序排列。編碼時(shí)，從最小的ri開(kāi)始，排除對(duì)任意 ，滿(mǎn)足 .的碼字；那些對(duì)所有j，滿(mǎn)足 的碼字，則采用部分失真排除判定法，確定此碼字為最佳匹配碼字或者在以該碼字為開(kāi)始的剩余碼字中搜索最佳匹配碼字。
3．2．2 等均值等方差最近鄰搜索算法
均值等方差最近鄰碼字搜索算法是將均值不等式判據(jù)和用方差不等式判據(jù)相結(jié)合，進(jìn)一步縮小了碼字搜索范圍。k維輸入矢量x的方差定義公式（3.17）【9】為
（3.17）
其中：Mx為輸入矢量x的均值。
等均值等方差最近鄰搜索算法所用到的方差判別準(zhǔn)則為：
設(shè)碼字 為輸入矢量x的當(dāng)前最近鄰碼字， ，輸入矢量x和碼字Y，的方差分別為Vx和Vyi，如果公式（3.18）成立，
（3.18）
則有d(x,yi) >d( x,yp)，碼字yi，可以被排除是輸入矢量x的最近鄰碼字。對(duì)式(3.12)作適當(dāng)變形，可得公式（3.19）和（3.20）
(3.19)
(3.20)
即碼字Yi的方差滿(mǎn)足以上兩式時(shí)，碼字Yi可以被排除是輸入矢量x的最近鄰碼字。
由幾何知識(shí)可知，在歐幾里得空間 中以空間中心線L為軸心的超圓柱面上，各點(diǎn)的方差相等，該超圓柱面稱(chēng)為等方差超圓柱面。由式(3.13)和(3.14)可知，等方差判別準(zhǔn)則將碼字搜索范圍限制在方差分別為Vmax和V min的兩個(gè)超圓柱面內(nèi)。則等均值判別準(zhǔn)則與等方差判別準(zhǔn)則相結(jié)合的等均值等方差最近鄰搜索算法將碼字的搜索范圍限制在了如圖3.2所示的陰影部分內(nèi)。
圖3.1 等均值等方差最近鄰搜索算法搜索范圍二維示意圖

圖3.1 所示是EENNS算法搜索范圍的二維示意圖，圖中以中心線L為軸心的超圓柱面分別是方差為Vmin和Vmax的等方差超圓柱面，與中心線L垂直的超平面分別是均值為Mmax和Mmin的等均值超圓柱面。等均值等方差最近鄰搜索算法將碼字的搜索范圍限制在超圓柱面V1, V2和超平面Ll，L2所夾的范圍內(nèi)，即圖中的陰影區(qū)域。EENNS算法減少了碼字搜索范圍，從而可以提高碼字搜索速度。EENNS算法具體步驟如下：
(A)預(yù)處理：計(jì)算并存儲(chǔ)碼書(shū)C中的均值和方差，按均值的大小對(duì)碼書(shū)進(jìn)行排序。
(B)在線處理：
Step l：計(jì)算輸入矢量x的均值Mx和方差Vx，在已排序碼書(shū)中找到均值與Mx 最 接近的碼字 作為輸入矢量X的初始匹配碼字。計(jì)算當(dāng)前最小失真 d min = d (x ,yp )。使集合
Step 2：如果集合G為空，轉(zhuǎn)Step 7；
Step 3：往返搜索法搜索初始匹配碼字yp兩側(cè)的碼字yj；
Step 4：如果碼字滿(mǎn)足 或者 ，則執(zhí)行
下列步驟的(a)或者(b)。否則，轉(zhuǎn)步驟5；
(C)如果Myj> Mx，則從集合G中刪除所有碼字yi，ij，轉(zhuǎn)Step2。
(D)否則，則從集合G中刪除所有碼字yi i>j，轉(zhuǎn)Step2。
Step 5：判斷碼字Yi的方差是否滿(mǎn)足 或者 如果 滿(mǎn)足， 則從刪除集合G中刪除碼字Yi，否則，轉(zhuǎn)Step6；
Step 6：用部分失真排除算法搜索碼字Yi，如果d(x, Yi)dmin,. 則更新 p = J，從集合G中刪除碼字Yi轉(zhuǎn)Step 2；
Step7：確定輸入矢量x的最匹配碼字為Yp。
3．3 碼字索引分配算法
3．3．1 BSA算法
BSA算法是在1990年提出基于二元對(duì)稱(chēng)信道模型的碼字索引分配算法【16】。該算法對(duì)于任何索引映射函數(shù) ，選擇碼字y，作為輸入矢量x的最近碼字后將產(chǎn)生索引 的傳輸，該過(guò)程與首先將碼書(shū)中的碼字進(jìn)行位置交換等價(jià)，即對(duì)每一索i，碼字y最終移動(dòng)到碼書(shū)中索引為 的位置。
基于這個(gè)事實(shí)，很自然地想到一種最簡(jiǎn)單的碼字索引分配方法：首先在給定碼書(shū)基礎(chǔ)上隨機(jī)產(chǎn)生一個(gè)初始碼字排列，然后將所有碼字的排列位置以特定方式進(jìn)行交換，使信道失真不斷減少。因此，這種算法的輸入是一個(gè)碼書(shū)，輸出仍是一個(gè)碼書(shū)，只不過(guò)碼字存放在不同的位置。這帶來(lái)一個(gè)附加優(yōu)點(diǎn):除了存儲(chǔ)碼書(shū)所需的空間以外，不需要任何額外信息來(lái)詳細(xì)描述索引映射函數(shù)n，從而不需要信道編碼和信道解碼。
BSA算法的主要思想是通過(guò)不斷交換碼字的位置，使得信道噪聲失真的目標(biāo)函數(shù)場(chǎng)獲得局部最優(yōu)值.隨著交換的進(jìn)行 不斷下降，而且索引映射函數(shù) 也跟著不斷變化。在每次迭代中，碼字的交換對(duì)是按一定的順序選擇的。所有的碼字y，都對(duì)應(yīng)一個(gè)函數(shù) ，用來(lái)描述當(dāng)該碼字的索引(在當(dāng)前碼書(shū)中)在噪聲信道中傳輸時(shí)可能產(chǎn)生的失真，其定義為公式（3.21）：
（3.21）
BSA算法每次按 從大到小的順序?qū)Υa字進(jìn)行排序。擁有最大函數(shù)值 的碼字被選為首先交換的候選對(duì)象。首先進(jìn)行試驗(yàn)性的交換， 與其他每一個(gè)碼字分別進(jìn)行交換，并計(jì)算每次交換后 的下降值。選擇能使 出現(xiàn)最大下降的那一個(gè)碼字與 進(jìn)行真正地交換，然后進(jìn)入下一次迭代。如果不存在這樣的碼字，則對(duì)yi作相同的交換試驗(yàn)。如果每一個(gè)碼字按這種方法與其他碼字進(jìn)行交換后。不再下降，則終止算法，從而獲得一個(gè)局部最優(yōu)的碼字索引分配方案。算法的具體步驟如下：
Step 1：初始化。隨機(jī)打亂碼字的排序；
Step 2：整理排序。根據(jù) 從大到小的順序?qū)Υa字yi進(jìn)行排序。令n=－1；
Step 3：試驗(yàn)性交換。令n＝n＋1從j＝n＋1到N一1，分別計(jì)算索引n和索弓!j交換后所能引起的失真減少量，比較這些失真減少量，獲得最大的失真下降量 ；