基于矢量量化編碼的數(shù)據(jù)壓縮算法的研究與實(shí)現(xiàn)二-文庫吧資料
2025-05-15 19:49本頁面
【正文】 。所有的碼字y，都對應(yīng)一個(gè)函數(shù)，用來描述當(dāng)該碼字的索引 (在當(dāng)前碼書中 )在噪聲信道中傳輸時(shí)可能產(chǎn)生的失真，其定義為公式 ()： () BSA 算法每次按從大到小的順序?qū)Υa字進(jìn)行排序。 BSA 算法的主要思想是通過不斷交換碼字的位置，使得信道噪聲失真的目標(biāo)函數(shù)場獲得局部最優(yōu)值 .隨著交換的進(jìn)行不斷下降，而且索引映射函數(shù)也跟著不斷變化。因此，這種算法的輸入是一個(gè)碼書，輸出仍是一個(gè)碼書，只不過碼字存放在不同的位置。該算法對于任何索引映射函數(shù)，選擇碼字 y，作為輸入矢量 x的最近碼字后將產(chǎn)生索引的傳輸，該過程與首先將碼書中的碼字進(jìn)行位置交換等價(jià)，即對每一索 i，碼字 y最終移動(dòng)到碼書中索引為的位置。 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。否則，轉(zhuǎn)步驟 5； (C)如果 Myj Mx，則從集合 G中刪除所有碼字 yi， i j，轉(zhuǎn) Step2。計(jì) 算當(dāng)前最小失真 d min=d(x,yp)。 EENNS 算法具體步驟如下： (A)預(yù)處理：計(jì)算并存儲(chǔ)碼書 C中的均值和方差，按均值的大小對碼書進(jìn)行排序。等均值等方差最近鄰搜索算法將碼字的搜索范圍限制在超圓柱面 V1,V2 和超平面 Ll， L2所夾的范圍內(nèi)，即圖中的陰影區(qū)域。則等均值判別準(zhǔn)則與等方差判別準(zhǔn)則相結(jié)合的等均值等方差最近鄰搜索算法將碼字的搜索范圍限制在了如圖 。 由幾何知識(shí)可知，在歐幾里得空間中以空間中心線 L 為軸心的超圓柱面上，各點(diǎn)的方差相等，該超圓柱面稱為等方差超圓柱面。 等均值等方差最近鄰搜索算法所用到的方差判別準(zhǔn)則為： 設(shè)碼字為輸入矢量 x 的當(dāng)前最近鄰碼字，輸入矢量 x和碼字 Y，的方差分別為 Vx和 Vyi，如果公式 ()成立， () 則有 d(x,yi)d(x,yp)，碼字 yi，可以被排除是輸入矢量 x 的最近鄰碼字。 等均值等方差最近鄰搜索算法 均值等方差最近鄰碼字搜索算法是將均值不等式判據(jù)和用方差不等式判據(jù)相結(jié)合，進(jìn)一步縮小了碼字搜索范圍。最小均方誤 差編碼算法，取一長訓(xùn)練矢量序列，計(jì)算每個(gè)Voronoi 區(qū)域內(nèi)的訓(xùn)練矢量與該區(qū)域質(zhì)心矢量 (碼字 )的最大距離 di，求平方根后得 ri，按其升序排列。 這三種算法都涉及如何確定初始匹配碼字的問題，一般取范數(shù)與輸入矢量范數(shù)最相近的碼字。 基于三角不等式 d(Y i,yj)d(x,Yi)+d(x,yj)提出三種改進(jìn)算法【 14】。 整數(shù)投影法是一種適用于圖像矢量量化的快速碼字搜索算法。這縮小了搜索范圍，他們還融入部分距離失真法節(jié)省計(jì)算量。因?yàn)?|yi|可離線計(jì)算，所以節(jié)省了計(jì)算量。 在編碼過程中計(jì)算前面部分維數(shù)的失真距離，若其超出當(dāng)前最小距離，則排除此碼字為最匹配碼字，否則繼續(xù)搜索其它碼字。它的基本思想是：在計(jì)算某個(gè)碼字與輸入矢量之間失真測度的過程中，始終判斷累加的部分失真是否已經(jīng)超過目前的最小失真，如果一旦超出則終止該碼字與輸入矢量之間的失真計(jì)算，轉(zhuǎn)而開始計(jì)算另一個(gè)碼字與輸入矢量的失真測度。但是，在這種限制條件 下，算法常常搜索不到最優(yōu)超平面。然而，在 MD算法中，多維胞腔的最優(yōu)分割超平面的搜索是一個(gè)非常困難的問題。 與 LBG 算法相比， MD 算法的計(jì)算量少且所產(chǎn)生的碼書性能好。 LBG算法他具有如下的優(yōu)點(diǎn)： 計(jì)算，可大大減少計(jì)算時(shí)間 ，無空胞腔問題 LBG 算法在具有如上的優(yōu)點(diǎn)的同時(shí)也有一些缺點(diǎn)和不足： ，從碼書中搜索訓(xùn)練矢量的最近碼字需要大量的存儲(chǔ)空間和繁瑣的計(jì)算； ； 碼書設(shè)計(jì)的第一個(gè)缺點(diǎn)可采用各種快速碼字搜索算法來解決，但這些算法無法改善碼書的性能，第 2個(gè)缺點(diǎn)產(chǎn)生的原因是： LBG算法是一種下降算法，每次迭代總能減少 (至少保持不變 )平均失真，而且每次迭代通常只能產(chǎn)生碼書的局部變化，即每次迭代后，與舊碼書 相比，新碼書不可能有非常大的變化。產(chǎn)生最后的 N個(gè)胞腔，一共需計(jì)算 (2N3)次最大失真下降函數(shù)。所以， L+l個(gè)胞腔是通過劃分 L 個(gè)胞腔中具有最大失真下降的胞腔并保持其余胞腔不變而得到的。 我們將胞腔 Si 的最優(yōu)分割超平面定義為使胞腔具有最大失真下降的超平面。分別為的質(zhì)心。從 L 個(gè)包腔生成 (L+1)個(gè)包腔的具體實(shí)現(xiàn)描述如下： 設(shè)超平面將某胞腔分成兩個(gè)非空胞腔如式 ()所示： () 式中， T表示轉(zhuǎn) 置。這在 k維空間里是比較困難的事，需要大量的計(jì)算和比較。另一方面， MD算法傾向于分割元素較多的胞腔，而不會(huì)去分割只有一個(gè)元素的胞腔，避免了非典型碼字的形成，提高了碼本的整體性 能。依此類推，每次分裂產(chǎn)生一個(gè)包腔，直到生成最后的 N個(gè)包腔，計(jì)算它們的質(zhì)心，就可以得到設(shè)計(jì)的碼本 C={y}i=1,2,… ,N)。 MD 算法 最大下降 (MD)【 13】碼本設(shè)計(jì)算法與經(jīng)典的 LBG 算法不同，它是一種分裂算法，而沒有初始碼本。另外，有可能把某些空間分得過疏。因此在LBG算法中要對初始碼本的選擇作一定的處理。 1980 年 Linde， Buzo 和 Gray 將 Lloyd 算法推廣到矢量空間【 8】，算法的步驟簡單描述如下： Step 1：給定初始碼本，令迭代次數(shù) m=0，平均失真初始值為，給定失真下降閾值； Step 2：用碼本中的碼字作為質(zhì)心，根據(jù)最佳劃分原則將訓(xùn)練矢量集 x 劃分為對應(yīng)于每個(gè)碼字的 N 個(gè)聚類， 滿足：； Step 3：計(jì)算本次迭代的平均失真判斷相對誤差是否滿足，若滿足，則停止算法，碼本 C(m)就是所求的碼本； 否則，轉(zhuǎn) Step 4； Step 4：根據(jù)質(zhì)心條件，計(jì)算各聚類的質(zhì)心，即公式 ()： () 產(chǎn)生新碼本并 置 m=m+1，轉(zhuǎn) Step 2 END：算法結(jié)束。不難看出，碼本生成過程中的計(jì)算量是隨著碼本矢量的維數(shù) k和碼本尺寸 N的增大而急劇增長的，對于需要高維大碼本的矢量量化器來說，測試所有可能的碼本來尋求全局最優(yōu)碼本將是十分困難的。設(shè)訓(xùn)練矢量 x為 k 維的，如果用平方誤差測度用來表征訓(xùn)練矢量 x和碼字 yi 之間的失真，即： () (CentroidC ondition) 利用由上面步驟得到的訓(xùn)練矢
高考資料相關(guān)推薦
鄂ICP備17016276號(hào)-1