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

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

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

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