基于矢量量化編碼的數(shù)據(jù)壓縮算法的研究與實(shí)現(xiàn)二(編輯修改稿)
2025-06-12 19:49 本頁面
【文章內(nèi)容簡介】 為碼字的范數(shù)， hi為輸入矢量與當(dāng)前匹配碼字之間的歐氏距離，此種算法不同于第一種算法，無須計(jì)算碼字之間的距離； 第三種算法取前兩種算法搜索區(qū)域的交集作為搜索區(qū)域。 這三種算法都涉及如何確定初始匹配碼字的問題，一般取范數(shù)與輸入矢量范數(shù)最相近的碼字。第一、三種算法比第二種算法要多耗費(fèi)存儲空間來存儲碼字之間的距離。最小均方誤 差編碼算法，取一長訓(xùn)練矢量序列，計(jì)算每個Voronoi 區(qū)域內(nèi)的訓(xùn)練矢量與該區(qū)域質(zhì)心矢量 (碼字 )的最大距離 di，求平方根后得 ri，按其升序排列。編碼時，從最小的 ri開始，排除對任意，滿足 .的碼字；那些對所有 j，滿足的碼字，則采用部分失真排除判定法，確定此碼字為最佳匹配碼字或者在以該碼字為開始的剩余碼字中搜索最佳匹配碼字。 等均值等方差最近鄰搜索算法 均值等方差最近鄰碼字搜索算法是將均值不等式判據(jù)和用方差不等式判據(jù)相結(jié)合，進(jìn)一步縮小了碼字搜索范圍。 k維輸入矢量 x的方差定義公式 ()【 9】為 () 其中： Mx為輸入矢量 x的均值。 等均值等方差最近鄰搜索算法所用到的方差判別準(zhǔn)則為： 設(shè)碼字為輸入矢量 x 的當(dāng)前最近鄰碼字，輸入矢量 x和碼字 Y，的方差分別為 Vx和 Vyi，如果公式 ()成立， () 則有 d(x,yi)d(x,yp)，碼字 yi，可以被排除是輸入矢量 x 的最近鄰碼字。對式 ()作適當(dāng)變形，可得公式 ()和 () () () 即碼字 Yi的方差滿足以上兩式時，碼字 Yi可以被排除是輸入矢量 x的最近鄰碼字。 由幾何知識可知，在歐幾里得空間中以空間中心線 L 為軸心的超圓柱面上，各點(diǎn)的方差相等，該超圓柱面稱為等方差超圓柱面。由式 ()和 ()可知，等方差判別準(zhǔn)則將碼字搜索范圍限制在方差分別為 Vmax 和 V min 的兩個超圓柱面內(nèi)。則等均值判別準(zhǔn)則與等方差判別準(zhǔn)則相結(jié)合的等均值等方差最近鄰搜索算法將碼字的搜索范圍限制在了如圖 。 圖 等均值等方差最近鄰搜索算法搜索范圍二維示意圖 圖 所示是 EENNS 算法搜索范圍的二維示意圖，圖中以中心線 L為軸心的超圓柱面分別是方差為 Vmin 和 Vmax的等方差超圓柱面，與中心線 L垂直的超平面分別是均值為 Mmax 和 Mmin 的等均值超圓柱面。等均值等方差最近鄰搜索算法將碼字的搜索范圍限制在超圓柱面 V1,V2 和超平面 Ll， L2所夾的范圍內(nèi)，即圖中的陰影區(qū)域。 EENNS 算法減少了碼字搜索范圍，從而可以提高碼字搜索速度。 EENNS 算法具體步驟如下： (A)預(yù)處理：計(jì)算并存儲碼書 C中的均值和方差，按均值的大小對碼書進(jìn)行排序。 (B)在線處理： Step l：計(jì)算輸入矢量 x的均值 Mx和方差 Vx，在已排序碼書中找到均值與 Mx 最接近的碼字作為輸入矢量 X的初始匹配碼字。計(jì) 算當(dāng)前最小失真 d min=d(x,yp)。使集合 Step 2：如果集合 G 為空，轉(zhuǎn) Step 7； Step 3：往返搜索法搜索初始匹配碼字 yp兩側(cè)的碼字 yj； Step 4：如果碼字滿足或者，則執(zhí)行 下列步驟的 (a)或者 (b)。否則，轉(zhuǎn)步驟 5； (C)如果 Myj Mx，則從集合 G中刪除所有碼字 yi， i j，轉(zhuǎn) Step2。 (D)否則，則從集合 G中刪除所有碼字 yi ij，轉(zhuǎn) Step2。 Step 5：判斷碼字 Yi 的方差是否滿足或者如果滿足，則從刪除集合 G中刪除碼字 Yi，否則，轉(zhuǎn) Step6； Step 6：用部 分失真排除算法搜索碼字 Yi，如果 d(x,Yi)dmin,.則更新p=J，從集合 G中刪除碼字 Yi轉(zhuǎn) Step 2； Step7：確定輸入矢量 x的最匹配碼字為 Yp。 碼字索引分配算法 BSA 算法 BSA 算法是在 1990年提出基于二元對稱信道模型的碼字索引分配算法【 16】。該算法對于任何索引映射函數(shù)，選擇碼字 y，作為輸入矢量 x的最近碼字后將產(chǎn)生索引的傳輸，該過程與首先將碼書中的碼字進(jìn)行位置交換等價，即對每一索 i，碼字 y最終移動到碼書中索引為的位置。 基于這個事實(shí)，很自然地想到一種最簡單的碼字索引分 配方法：首先在給定碼書基礎(chǔ)上隨機(jī)產(chǎn)生一個初始碼字排列，然后將所有碼字的排列位置以特定方式進(jìn)行交換，使信道失真不斷減少。因此，這種算法的輸入是一個碼書，輸出仍是一個碼書，只不過碼字存放在不同的位置。這帶來一個附加優(yōu)點(diǎn)：除了存儲碼書所需的空間以外，不需要任何額外信息來詳細(xì)描述索引映射函數(shù) n，從而不需要信道編碼和信道解碼。 BSA 算法的主要思想是通過不斷交換碼字的位置，使得信道噪聲失真的目標(biāo)函數(shù)場獲得局部最優(yōu)值 .隨著交換的進(jìn)行不斷下降，而且索引映射函數(shù)也跟著不斷變化。在每次迭代中，碼字的交換對是按一定的順序選擇的 。所有的碼字y，都對應(yīng)一個函數(shù)，用來描述當(dāng)該碼字的索引 (在當(dāng)前碼書中 )在噪聲信道中傳輸時可能產(chǎn)生的失真，其定義為公式 ()： () BSA 算法每次按從大到小的順序?qū)Υa字進(jìn)行排序。擁有最大函數(shù)值的碼字被選為首先交換的候選對象。首先進(jìn)行試驗(yàn)性的交換，與其他每一個碼字分別進(jìn)行交換，并計(jì)算每次交換后的下降值。選擇能使出現(xiàn)最大下降的那一個碼字與進(jìn)行真正地交換，然后進(jìn)入下一次迭代。如果不存在這樣的碼字，則對 yi 作相同的交換試驗(yàn)。如果每一個碼字按這種方法與其他碼字進(jìn)行交換后。不再下降，則終止算法，從而獲得一 個局部最優(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 交換后所能引起的失真減少量，比較這些失真減少量，獲得最大的失真下降量； Step 4：如果 0，則交換索引 n和引起最大失真下降的索引 j，并轉(zhuǎn) Step 2； Step 5：終止算法。如果 n=N 一 1，則終止算法，否則，轉(zhuǎn) Step 3。 可以看出， BSA 算法根據(jù)函數(shù)值將碼字進(jìn)行排列而選擇出哪一個碼字最先進(jìn)行交換，從而在運(yùn)算上給出了一個方向性引導(dǎo)。如果由于程序運(yùn)行時間的限制而使算法的迭代次數(shù)有限，則這種方向性引導(dǎo)將顯得尤為重要。每一次成功交換的完成，代表一次迭代的結(jié)束。若一次迭代中的所有試驗(yàn)性交換產(chǎn)生的失真下降都不大于
高考資料相關(guān)推薦
鄂ICP備17016276號-1