基于矢量量化編碼的數(shù)據(jù)壓縮算法的研究與實現(xiàn)二

《基于矢量量化編碼的數(shù)據(jù)壓縮算法的研究與實現(xiàn)二》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在應(yīng)用文檔-天天文庫。

1、基于矢量量化編碼的數(shù)據(jù)壓縮算法的研究與實現(xiàn)二轉(zhuǎn)自：.4矢量量化的關(guān)鍵技術(shù)及技術(shù)指標(biāo)2.4.1矢量量化的關(guān)鍵技術(shù)矢量量化的三大關(guān)鍵技術(shù)是【8】：碼書設(shè)計、碼字搜索和碼字索引分配。其中前兩項最關(guān)鍵。1.碼書設(shè)計矢量量化的首要問題是設(shè)計出性能好的碼書。如果沒有碼書，那么編碼將成為無米之炊。假設(shè)采用平方誤差測度作為失真測度，訓(xùn)練矢量數(shù)為M，目的是生成含N(NM)個碼字的碼書，則碼書設(shè)計過程就是尋求把M個訓(xùn)練矢量分成N類的一種最佳方案(如：使得均方誤差最小)，而把各類的質(zhì)心矢量作為碼書的碼字?？梢宰C明在這種條件下各種可能的碼書個數(shù)為NumC，NumC滿足公式2.13：(2.13)

2、其中C為組合數(shù)。通過測試所有碼書的性能可以得到全局最優(yōu)碼書。然而，在N和M比較大的情況下，搜索全部碼書是根本不可能的。為了克服這個困難，文獻(xiàn)中各種碼書設(shè)計方法都采取搜索部分碼書的方法得到局部最優(yōu)或接近全局最優(yōu)的碼書。所以研究碼書設(shè)計算法的目的就是尋求有效的算法盡可能找到全局最優(yōu)或接近全局最優(yōu)的碼書以提高碼書的性能，并且盡可能減少計算復(fù)雜度。2.碼字搜索矢量量化碼字搜索算法是指在碼書已經(jīng)存在的情況下，對于給定的輸入矢量，在碼書中搜索與輸入矢量之間失真最小的碼字。給定大小為N的碼書C，如果矢量x與碼字A之間的失真測度為d(x,y)，則碼字搜索算法的目的就是找到碼字Y，使得失

3、真測度滿足公式2.14：(2.14)如果采用平方誤差測度，對于k維矢量，每次失真計算需要k次乘法，2k一1次加法，從而為了對矢量x進(jìn)行窮盡搜索編碼需要Nk次乘法，N(2k-1)次加法和N-1次比較。可以看出，計算復(fù)雜度由碼書尺寸和矢量維數(shù)決定。對于大尺寸碼書和高維矢量，計算復(fù)雜程度將很大。研究碼字搜索算法的主要目的就是尋求快速有效的算法以減少計算復(fù)雜程度，并且盡量使得算法易于用硬件實現(xiàn)。3.碼字索引分配在圖示的矢量量化編碼和解碼系統(tǒng)中，如果信道有噪聲，則信道左端的索引i經(jīng)過信道傳輸可能輸出索引J而不是索引i，從而將在解碼端引入額外失真。為了減少這種失真，可以對碼字的索引

4、進(jìn)行重新分配。如果書大小為N，則碼字索引分配方案一共有N！種。碼字索引分配算法就是在N！種碼字索引分配方案中尋求一種最佳的碼字索引分配使由信道噪聲引起的失真最小。然而，當(dāng)N較大時，測試N！種碼字索引分配方案是不可能的。為了克服這個困難，各種碼字索引分配方法都采用局部搜索算法，往往只能得到局部最優(yōu)解。所以研究碼字索引分配算法的目的就是尋求有效的算法盡可能找到全局最優(yōu)或接近全局最優(yōu)的碼字索引分配方案以減少由信道噪聲引起的失真，并盡可能減少計算復(fù)雜度和搜索時間。2.4.2矢量量化技術(shù)指標(biāo)1.矢量量化壓縮率從矢量量化器的工作原理我們看出，碼書確定之后，傳輸或者存儲的壓縮數(shù)據(jù)只是

5、一系列碼字的索引，這些索引本身并不包含原始數(shù)據(jù)的任何信息。因此矢量量化的壓縮率很大，其比特率bit/采樣，也就是說壓縮倍數(shù)為B為原始采樣數(shù)據(jù)所用比特(bit)數(shù)。舉例來說，當(dāng)E=8,M=256,K=64時，壓縮率r=0.015625bits/采樣。壓縮倍數(shù)為64。這樣的壓縮倍數(shù)顯然很可觀了從壓縮率與壓縮倍數(shù)的計算公式我們看出，M一般是2的冪次。再例如，碼書大小為150,碼字索引要用8bits碼書大小為256，碼字索引也要用8bits.兩種碼書大小得到的數(shù)據(jù)壓縮率相同，但后者壓縮性能顯然更好，所以一般我們用256而非150個碼字，大小為2a的碼書又稱為q比特碼書。2.信號

6、恢復(fù)性能指標(biāo)通常信號質(zhì)量有均方誤差(MSE)，信噪比(SNR)，峰值信噪比(PSNR)【11】等。在本文的討論中，我們主要是灰度圖像作為測試數(shù)據(jù)來源。我們的矢量量化技術(shù)的應(yīng)用也主要是針對灰度圖像的，因此以L級灰度圖像為例，我們給出個指標(biāo)的定義：設(shè)一副L級灰度圖像有WXH個像親，Xij為原始圖像像素值，Yij為恢復(fù)圖像像素值，那么結(jié)過如下公式所示：(2.15)(2.16)(2.17)第三章矢量量化的算法研究3.1矢量量化碼書設(shè)計算法的研究3.1.1經(jīng)典的LBG算法如前所述，在矢量量化器的構(gòu)造過程中，碼本設(shè)計是最初的也是最重要的部分，根據(jù)各種碼本設(shè)計算法的思想和迭代過程，我

7、們可以將碼本設(shè)計問題歸結(jié)為Lloyd算法的兩條基本準(zhǔn)則【12】：1.最佳劃分準(zhǔn)則(OptimalPartition)對于給定的碼本利用最近鄰條件對訓(xùn)練矢量集進(jìn)行重新劃分。將每個訓(xùn)練矢量映射到與它之間失真最小的碼字，最后形成一組以現(xiàn)有碼本中的碼字為中心的最佳劃分。設(shè)訓(xùn)練矢量集為：則訓(xùn)練矢量集的最佳分類滿足公式(3.1)：式中，i,j=1,2,…,N(3.1)如果存在D(x,yi)=D(x,yj),則將訓(xùn)練矢量歸入碼字yi的集合。通常把這種最佳劃分稱為Voronoi劃分，對應(yīng)的子集凡稱為Voronoi胞腔。設(shè)訓(xùn)練矢量x為k維的，如果用平方誤差