基于矢量量化編碼的數(shù)據(jù)壓縮算法的研究與實現(xiàn)二-展示頁
2025-05-19 19:49本頁面
【正文】 量劃分集重新計算它們各自的質(zhì)心，得到新的碼本： () () 式中，代表子集 Si中訓(xùn)練矢量的個數(shù)。設(shè)訓(xùn)練矢量集為： 則訓(xùn)練矢量集的最佳分類滿足公式 ()： 式中， i,j=1,2,… ,N() 如果存在 D(x,yi)=D(x,yj),則將訓(xùn)練矢量歸入碼字 yi的集合。我們的矢量量化技術(shù)的應(yīng)用也主要是針對灰度圖像的，因此以 L 級灰度圖像為例，我們給出個指標的定義：設(shè)一副 L 級灰度圖像有 WXH 個像親， Xij 為原始圖像像素值，Yij為恢復(fù)圖像像素值，那么結(jié)過如下公式所示： () () () 第三章矢量量化的算法研究 矢量量化碼書設(shè)計算法的研究 經(jīng)典的 LBG算法 如前所述，在矢量量化器的構(gòu)造過程中，碼本設(shè)計是最初的也是最重要的部分，根據(jù)各種碼本設(shè)計算法的思想和迭代過程，我們可以將碼本設(shè)計問題歸結(jié)為 Lloyd 算法的兩條基本準則【 12】： (Optimal Partition) 對于給定的碼本利用最近鄰條件對訓(xùn)練矢量集進行重新劃分。 通常信號質(zhì)量有均方誤差 (MSE)，信噪比 (SNR)，峰值信噪比 (PSNR)【 11】等。這樣的壓縮倍數(shù)顯然很可觀了從壓縮率與壓縮倍數(shù)的計算公式我們看出， M一般是 2的冪次。 舉例來說，當 E=8,M=256,K=64 時，壓縮率 r= bits/采樣。 矢量量化技術(shù)指標 壓縮率 從矢量量化器的工作原理我們看出，碼書確定之后，傳輸或者存儲的壓縮數(shù)據(jù)只是一系列碼字的索引，這些索引本身并不包含原始數(shù)據(jù)的任何信息。為了克服這個困難，各種碼字索引分配方法都采用局部搜索算法，往往只能得到局部最優(yōu)解。碼字索引分配算法就是在 N！種碼字索引分配方案中尋求一種最佳的碼字索引分配使由信道噪聲引起的失真最小。為了減少這種失真，可以對 碼字的索引進行重新分配。研究碼字搜索算法的主要目的就是尋求快速有效的算法以減少計算復(fù)雜程度，并且盡量使得算法易于用硬件實現(xiàn)。可以看出，計算復(fù)雜度由碼書尺寸和矢量維數(shù)決定。 矢量量化碼字搜索算法是指在碼書已經(jīng)存在的情況下，對于給定的輸入矢量，在碼書中搜索與輸入矢量之間失真最小的碼字。為了克服這個 困難，文獻中各種碼書設(shè)計方法都采取搜索部分碼書的方法得到局部最優(yōu)或接近全局最優(yōu)的碼書。通過測試所有碼書的性能可以得到全局最優(yōu)碼書。假設(shè)采用平方誤差測度作為失真測度，訓(xùn)練矢量數(shù)為 M，目的是生成含 N(N M)個碼字的碼書，則碼書設(shè)計過程就是尋求把 M 個訓(xùn)練矢量分成N類的一種最佳方案 (如：使得均方誤差最小 )，而把各類的質(zhì)心矢量作為碼書的碼字。 矢量量化的首要問題是設(shè)計出性能好的碼書。基于矢量量化編碼的數(shù)據(jù)壓縮算法的研究與實現(xiàn) 二 轉(zhuǎn)自： .4矢量量化的關(guān)鍵技術(shù)及技術(shù)指標 矢量量化的關(guān)鍵技術(shù) 矢量量化的三大關(guān)鍵技術(shù)是【 8】：碼書設(shè)計、碼字搜索和碼字索引分配。其中前兩項最關(guān)鍵。如果沒有碼書，那么編碼將成為無米之炊。可以證明在這種條件下各種可能的碼書個數(shù)為 Num C， Num C 滿足公式： () 其中 C 為組合數(shù)。 然而，在 N和 M比較大的情況下，搜索全部碼書是根本不可能的。所以研究碼書設(shè)計算法的目的就是尋求有效的算法盡可能找到全局最優(yōu)或接近全局最優(yōu)的碼書以提高碼書的性能，并且盡可能減少計算復(fù)雜度。給定大小為 N的碼書 C，如果矢量 x 與碼字 A之間的失真測度為 d(x,y)，則碼字搜索算法的目的就是找到碼字 Y，使得失真測度滿足公式 ： () 如果采用平方誤差測度， 對于 k維矢量，每次失真計算需要 k次乘法， 2k一 1次加法，從而為了對矢量 x 進行窮盡搜索編碼需要 Nk 次乘法， N(2k1)次加法和 N1 次比較。對于大尺寸碼書和高維矢量，計算復(fù)雜程度將很大。 在圖示的矢量量化編碼和解碼系統(tǒng)中，如果信道有噪聲，則信道左端的索引 i經(jīng)過信道傳輸可能輸出索引 J而不是索引 i，從而將在解碼端引入額外失真。如果書大小為 N，則碼字索引分配方案一共有 N！種。然而，當 N較大時，測試 N！種碼字索引分配方案是不可能的。所以研究碼字索引分配算法的目的就是尋求有效的算法盡可能找到全局最優(yōu)或接近全局最優(yōu)的碼字索引分配方案以減少由信道噪聲引起的失真，并盡可能減少計算復(fù)雜度和搜索時間。因此矢量量化的壓縮率很大，其比特率 bit/采樣，也就是說壓縮倍數(shù)為 B為原始采樣數(shù)據(jù)所用比特 (bit)數(shù)。壓縮倍數(shù)為 64。再例如，碼書大小為 150,碼字索引要用 8bits 碼書大小為 256，碼字索引也要用 ，但后者壓縮性能顯然更好，所以一般我們用 256 而非 150個碼字，大小為 2a的碼書又稱為 q 比特碼書。在本文的討論中，我們主要是灰度圖像作為測試數(shù)據(jù)來源。將每個訓(xùn)練矢量映射到與它之間失真最小的碼字，最后形成一組以現(xiàn)有碼本中的碼字為中心的最佳劃分。 通常把這種最佳劃分稱為 Voronoi 劃分，對應(yīng)的子集凡稱為 Voronoi 胞腔。 各種矢量量化碼本設(shè)計算法基本都是上面兩個步驟的交替迭代的基礎(chǔ)上得到最后的碼本。為了克服這個困難， 和 Gray 提出了經(jīng)典的 LBG 算法。 對于 LBG 算法來說，初始碼本選擇的好壞將直接影響到后面的迭代計算結(jié)果，一個不好的初始碼本會降低算法的收斂速度和最終碼本的性能。如果初始碼本隨機產(chǎn)生，即直接從訓(xùn)練序列中隨機選擇 N個訓(xùn)練矢量作為初始碼字，構(gòu)成初始碼本，可能會選到一些非典型的訓(xùn)練矢量作碼字，因而該胞腔可能含有少數(shù)幾個矢量甚至只有 1個。這可能會導(dǎo)致碼本中的有些碼字得不到充分利用，設(shè)計出來的碼本性能就可能較差。在 MD 算法中，首先將訓(xùn)練矢量集作為一個原始包腔，然后該包腔被它的最優(yōu)分割超平面分成兩個子包腔。與 LBG算法相比， MD 算法的計算量少并且所產(chǎn)生的碼本性能好。在 MD算法中，從 L個包腔向 (L+l)個包腔擴展時，先要找出每個現(xiàn)有包腔的最優(yōu)分割超平面，并計算它們各自帶來的失真下降幅度，然后依據(jù)失真下降最大準則來選擇究竟對哪一個包腔進行分裂。圖 所示為 MD算法的分裂過程示意圖，圖中每一步驟中有陰影的包腔是當前符合失真下降最大準則的包腔，它被最優(yōu)分割超平面分成下面的兩個子包腔和。 當中的矢量被質(zhì)心量化時，胞腔的失真 D(Si)定義為公式 ()： () 則由分割超平面 H,劃分胞腔 S,所引起的失真下降可表示為式 ()： (
高考資料相關(guān)推薦
鄂ICP備17016276號-1