基于矢量量化編碼的數(shù)據(jù)壓縮算法的研究與實(shí)現(xiàn)二-在線瀏覽
2025-07-10 19:49本頁(yè)面
【正文】 ) 若采用平方誤差測(cè)度，則式 ()可以化簡(jiǎn)為式 ()： 或 () 式中，分別為的元素個(gè)數(shù)。 從式 ()中可以看出，若胞腔、非空，則失真下降函數(shù)滿足。MD算法先計(jì)算出所有胞腔的最大失真下降值，然后找出最大的最大失真下降值，即，最后將胞腔 Sp分割成兩 個(gè)新胞腔。值得注意的是，每次分裂包腔時(shí)，并不需要重新計(jì)算所有包腔的失真函數(shù)，而只需找到新增加的兩個(gè)包腔的最優(yōu)分割超平面，計(jì)算它們各自的失真函數(shù)，再與其它包腔的失真函數(shù)值進(jìn)行比較即可找出新的滿足失真下降最大準(zhǔn)則的包腔。 碼書設(shè)計(jì)算法比較 LBG 算法是一種迭代算法，其迭代操作是標(biāo)量量化勞埃德迭代操作的直接推廣。因此，一旦選定初始碼書，該算法只能得到局部最優(yōu)的碼書，即 LBG 算法一般不能得到全局最優(yōu)的碼書。另一方面，MD算法傾向于分割元素較多的胞腔，而不會(huì)去分割只有一個(gè)元素的胞腔，而這種情況在 LBG 算法中卻常常出現(xiàn)。為減少計(jì)算量，這些算法的搜索范圍被限制在與矢量空間的基本矢量正交的超平面上，這個(gè)矢量空間可由離散余弦變換(DCT)得到。 碼字搜索算法 基于不等式的快速碼字搜索算法 部分失真搜索 (Partial Distortion Search， PDS)算法【 12】是一種較簡(jiǎn)單有效的最近鄰搜索算法。 PDS 常被用來(lái)與其他快速搜索算法結(jié)合起來(lái)運(yùn)用，來(lái)排除其它快速算法最 后無(wú)法排除的碼字。 據(jù)如下 ()所示的柯西一許瓦爾茲不等式【 14】： () 可得一個(gè)不等式判據(jù)若，則能保證， yi 可被排除。首先判斷是否成立，若成立，則排除碼字 Yi否則，再判斷是否滿足，若滿足， yi也可被排除。雙測(cè)試法的缺陷在于要求矢量的所有分量都為正值，而圖像變換域編碼中產(chǎn)生的變換系數(shù)有正有負(fù)，必須對(duì)這些系數(shù)進(jìn)行正補(bǔ)償，使所有矢量分量均大于零。他們?yōu)槊總€(gè)m m 圖像塊，定義三種整數(shù)投影【 14】，如下公式 ()()()所示： 塊狀投影： () 垂直投影： () 水平投影： () 在這三種投影的基礎(chǔ)上定義了三個(gè)不等式條件，公式 ()()()所示： () () () 可以證明，只要不滿足上述任何一個(gè)條件，可排除 yi 是最匹配碼字。第一種算法先計(jì)算碼書中每?jī)蓚€(gè)碼字之間的距離，以當(dāng)前匹配碼字 yi為中心，2hi(h i 為輸入矢量與當(dāng)前匹配碼字之 間的歐氏距離 )為半徑劃定搜索范圍，即只搜索滿足 d(yj,yi)2hi 的碼字 yj,j=1,2,… ,N； 第二種算法是將搜索范圍定為滿足： xhi rk rx+hi， 其中 rx 為輸入矢量的范數(shù)， rk為碼字的范數(shù)， hi為輸入矢量與當(dāng)前匹配碼字之間的歐氏距離，此種算法不同于第一種算法，無(wú)須計(jì)算碼字之間的距離； 第三種算法取前兩種算法搜索區(qū)域的交集作為搜索區(qū)域。第一、三種算法比第二種算法要多耗費(fèi)存儲(chǔ)空間來(lái)存儲(chǔ)碼字之間的距離。編碼時(shí)，從最小的 ri開始，排除對(duì)任意，滿足 .的碼字；那些對(duì)所有 j，滿足的碼字，則采用部分失真排除判定法，確定此碼字為最佳匹配碼字或者在以該碼字為開始的剩余碼字中搜索最佳匹配碼字。 k維輸入矢量 x的方差定義公式 ()【 9】為 () 其中： Mx為輸入矢量 x的均值。對(duì)式 ()作適當(dāng)變形，可得公式 ()和 () () () 即碼字 Yi的方差滿足以上兩式時(shí)，碼字 Yi可以被排除是輸入矢量 x的最近鄰碼字。由式 ()和 ()可知，等方差判別準(zhǔn)則將碼字搜索范圍限制在方差分別為 Vmax 和 V min 的兩個(gè)超圓柱面內(nèi)。 圖 等均值等方差最近鄰搜索算法搜索范圍二維示意圖 圖 所示是 EENNS 算法搜索范圍的二維示意圖，圖中以中心線 L為軸心的超圓柱面分別是方差為 Vmin 和 Vmax的等方差超圓柱面，與中心線 L垂直的超平面分別是均值為 Mmax 和 Mmin 的等均值超圓柱面。 EENNS 算法減少了碼字搜索范圍，從而可以提高碼字搜索速度。 (B)在線處理： Step l：計(jì)算輸入矢量 x的均值 Mx和方差 Vx，在已排序碼書中找到均值與 Mx 最接近的碼字作為輸入矢量 X的初始匹配碼字。使集合 Step 2：如果集合 G 為空，轉(zhuǎn) Step 7； Step 3：往返搜索法搜索初始匹配碼字 yp兩側(cè)的碼字 yj； Step 4：如果碼字滿足或者，則執(zhí)行 下列步驟的 (a)或者 (b)。 (D)否則，則從集合 G中刪除所有碼字 yi ij，轉(zhuǎn) Step2。 碼字索引分配算法 BSA 算法 BSA 算法是在 1990年提出基于二元對(duì)稱信道模型的碼字索引分配算法【 16】。 基于這個(gè)事實(shí)，很自然地想到一種最簡(jiǎn)單的碼字索引分 配方法：首先在給定碼書基礎(chǔ)上隨機(jī)產(chǎn)生一個(gè)初始碼字排列，然后將所有碼字的排列位置以特定方式進(jìn)行交換，使信道失真不斷減少。這帶來(lái)一個(gè)附加優(yōu)點(diǎn)：除了存儲(chǔ)碼書所需的空間以外，不需要任何額外信息來(lái)詳細(xì)描述索引映射函數(shù) n，從而不需要信道編碼和信道解碼。在每次迭代中，碼字的交換對(duì)是按一定的順序選擇的 。擁有最大函數(shù)值的碼字被選為首先交換的候選對(duì)象。選擇能使出現(xiàn)最大下降的那一個(gè)碼字與進(jìn)行真正地交換，然后進(jìn)入下一次迭代。如果每一個(gè)碼字按這種方法與其他碼字進(jìn)行交換后。算法的具體步驟如下： Step 1：初始化。根據(jù)從大到小的順序?qū)Υa字 yi 進(jìn)行排序。令 n=n+1 從 j=n+1 到 N 一 1，分別計(jì)算索引 n和索弓！ j 交換后所能引起的失真減少量，比較這些失真減少量，獲得最大的失真下降量； Step 4：如果 0，則交換索引 n和引起最大失真下降的索引 j，并轉(zhuǎn) Step 2； Step 5：終止算法。 可以看出， BSA 算法根據(jù)函數(shù)值將碼字進(jìn)行排列而選擇出哪一個(gè)碼字最先進(jìn)行交換，從而在運(yùn)算上給出了一個(gè)方向性引導(dǎo)。每一次成功交換的完成，代表一次迭代的結(jié)束。實(shí)驗(yàn)證明，該算法獲得的碼字索引分配方案的失 真比隨機(jī)碼字索引分配方案的失真有較大改進(jìn)。由當(dāng)前解到其鄰域解的移動(dòng)被部分地或完全地記錄在禁止表中，目的是為了禁止以后迭代中的重復(fù)操作。中碼字 Yj 的索引， Sb(j)仍表示分配給解 Sb中碼字Yi的索引。初始的當(dāng)前解是隨機(jī)產(chǎn)生的，通過(guò)隨機(jī)交換當(dāng)前解中的兩個(gè)索引來(lái)產(chǎn)生測(cè)試解。如果從當(dāng)前解中產(chǎn)生測(cè)試解的交換索引與禁止表中任何記錄相同，則稱該測(cè)試解為禁止解。令迭代計(jì)數(shù)器 i=1，禁止表插入點(diǎn) t=1。令 Sb=Sc 以及
高考資料相關(guān)推薦
鄂ICP備17016276號(hào)-1