基于矢量量化編碼的數據壓縮算法的研究分析

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

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

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

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