基于矢量量化編碼技術(shù)的數(shù)據(jù)壓縮方法

【摘 要】本文以矢量量化在靜止圖像方面的應(yīng)用為研究目標(biāo)，介紹了矢量量化的發(fā)展現(xiàn)狀以及基本原理，重點(diǎn)討論研究了矢量量化的三大關(guān)鍵技術(shù)：碼書生成和碼字搜索和碼字索引分配。最后給出基于LBG的矢量量化圖像壓縮算法的，取得了較好的效果。

【關(guān)鍵詞】數(shù)據(jù)壓縮；矢量量化；LBG

引言

隨著現(xiàn)代通信業(yè)務(wù)的發(fā)展，我們?cè)絹?lái)越需要大量地存貯、記錄各類動(dòng)態(tài)圖像。在保證質(zhì)量的前提下，人們往往希望能夠以較小的空間存儲(chǔ)圖像，這就需要采用各種圖像壓縮編碼技術(shù)來(lái)實(shí)現(xiàn)。矢量量化[1](VQ)是在數(shù)字編碼技術(shù)中研究得較多的新型量化編碼方法。矢量量化壓縮技術(shù)的應(yīng)用領(lǐng)域非常廣闊，如衛(wèi)星遙感圖片的壓縮傳輸、數(shù)字電視視頻的壓縮、網(wǎng)絡(luò)上的語(yǔ)音編碼等。由此可見對(duì)矢量量化的研究是非常有意義的。

1、矢量量化技術(shù)現(xiàn)狀

矢量量化基本理論早在二十世紀(jì)六七十年代己有人關(guān)注，然后在八十年代開始逐步發(fā)展完善起來(lái)。1956年Steinhaus第一次系統(tǒng)闡述了最佳矢量量化問題；1978年Buzo第一個(gè)提出實(shí)際的矢量量化器。1980年Linde，Buzo和Gray[2]將Loyd-Max算法推廣，提出了一種有效的矢量量化碼書設(shè)計(jì)算法一一LBG算法[1]，將矢量量化技術(shù)的研究和推廣應(yīng)用推向了新的臺(tái)階。

矢量量化理論的研究歷程中，主要是從以下幾方面得到了發(fā)展[3]：

對(duì)基本矢量量化器復(fù)雜度大和比特率固定的缺點(diǎn)，開發(fā)其它類型的矢量量化器；

針對(duì)矢量量化器的LBG碼書設(shè)計(jì)算法，容易陷入局部極小、初始碼書影響優(yōu)化結(jié)果和計(jì)算量大的缺點(diǎn)，學(xué)者們引入神經(jīng)網(wǎng)絡(luò)[3]、優(yōu)化理論、模糊集合等技術(shù)，提出了各種各樣的碼書設(shè)計(jì)算法；

在矢量量化編碼場(chǎng)合中，針對(duì)基木矢量量化器的窮盡搜索編碼算法的計(jì)算量大和比特率固定的缺點(diǎn)提出各種各樣的快速碼字搜索算法和變化特率碼字搜索算法；

考慮到信道噪聲將會(huì)在矢量量化解碼端引入額外失真，學(xué)者們開始研究碼字索引分配算法以減少信道引起的失真。

2、矢量量化的三大關(guān)鍵技術(shù)

矢量量化的三大關(guān)鍵技術(shù)中，對(duì)碼書設(shè)計(jì)和碼字搜索研究比較多，而碼字索引分配則是比較新的研究方向。

2.1碼書設(shè)計(jì)

性能好的碼書，能使編碼時(shí)的總體量化誤差盡可能小。假設(shè)采用平方誤差測(cè)度作為失真測(cè)度，訓(xùn)練矢量數(shù)目為M(M>N)，則碼書設(shè)計(jì)的過(guò)程可看作對(duì)這M個(gè)訓(xùn)練矢量進(jìn)行N數(shù)目最優(yōu)分類的過(guò)程，并把各類的質(zhì)心矢量作為碼書的碼字?？梢宰C明在這種條件下各種可能的碼書個(gè)數(shù)為：

(1)

其中心CiN為組合數(shù)。由于碼字搜索的計(jì)算復(fù)雜度隨著碼書尺寸N的增大呈指數(shù)增加，使得大尺寸碼書的應(yīng)用受到實(shí)際編碼設(shè)備的限制而難以實(shí)現(xiàn)。

經(jīng)典的LBG算法是基于最佳矢量量化器設(shè)計(jì)的，基于最近鄰條件和質(zhì)心條件這兩個(gè)必要條件，其特點(diǎn)是概念清晰算法理論嚴(yán)謹(jǐn)且算法實(shí)現(xiàn)方便。

除了LBG算法之外，學(xué)者們還提出了眾多基于計(jì)算復(fù)雜度、全局優(yōu)化性、并行處理、自適應(yīng)等不同考慮因素的矢量量化碼書設(shè)計(jì)方法。

2.2碼字搜索

快速碼字搜索算法[4]可提高矢量量化編碼效率，然而一種有效的碼字搜索算法往往需要附加計(jì)算量和額外存儲(chǔ)空間。一方面如何盡可能減少附加計(jì)算量和額外存儲(chǔ)空間，另一方面與窮盡搜索編碼算法相比編碼質(zhì)量降低與否以及降低的程度，都是快速算法必須考慮的問題。目前文獻(xiàn)中提出了各種各樣的快速算法，這些算法大致可分為基于不等式判據(jù)和基于金字塔結(jié)構(gòu)及基于變換域的和自適應(yīng)搜索范圍及順序的四大類。

2.3碼字索引分配

研究碼字索引分配算法的目的就是尋求有效的算法盡可能找到全局最優(yōu)或接近全局最優(yōu)的碼字索引分配方案以減少由信道噪聲引起的失真，并盡可能減少計(jì)算復(fù)雜度和搜索時(shí)間。

矢量量化編碼器在碼書C中搜索與輸入矢量x最匹配的碼字yi

(2)

如果信道沒有噪聲，則接收端將收到索引i。如果信道有噪聲，則索引i經(jīng)過(guò)信道傳輸可能輸出索引j而不是索引i，這樣矢量量化解碼器將從碼書C中獲得碼字yi作為輸入矢量的重構(gòu)矢量，從而將在解碼過(guò)程中引入額外失真。為了克服這個(gè)困難，各種優(yōu)化技術(shù)被運(yùn)用到索引分配方案中，如BSA算法(Binary Switching Algorithm)、模擬退火算法、并行遺傳算法(Parallel Genetic Algorithm，PGA)等。

3、基于LBG的圖像壓縮算法

設(shè)計(jì)矢量量化器的主要任務(wù)是設(shè)計(jì)碼書，在給定碼書大小N的情況下由最佳劃分和最佳碼書兩個(gè)必要條件得到矢量量化器的設(shè)計(jì)算法，算法流程描述如下：

（1）給定碼書大小，初始碼書訓(xùn)練序列停止計(jì)算門限S起始平均失真。

（2）用碼書為已知形心把訓(xùn)練序列劃分為N個(gè)包腔；

（3)計(jì)算平均失真：

(3)

和相對(duì)失真:

(4)

（4）若條件≤g成立則，算法結(jié)束，若不成立計(jì)算此時(shí)劃分的各個(gè)包腔的形心，構(gòu)成新碼書，并置n=n+1，返回到（2）重新計(jì)算，直到條件滿足；算法結(jié)束。

該算法在Matlab實(shí)驗(yàn)環(huán)境下對(duì)512×512的圖像壓縮與解壓，得到PSNR=28.2315dB。具有對(duì)初始碼書依賴性小、不會(huì)陷入局部極小、收斂速度快、碼書性能佳的優(yōu)點(diǎn)，極大地改善了碼書的性能和加快了算法。

4、結(jié)束語(yǔ)

通過(guò)對(duì)矢量量化的現(xiàn)狀以及基本原理的分析，以及對(duì)矢量量化關(guān)鍵技術(shù)的分析；給出了一種基于LGB的矢量量化圖像壓縮算法的算法。矢量量化技術(shù)領(lǐng)域雖然已經(jīng)取得了長(zhǎng)足的進(jìn)步，但總體上來(lái)說(shuō)還有許多問題需要進(jìn)一步研究。

參考文獻(xiàn)

[1]張春田，蘇育挺，張靜.數(shù)字圖像壓縮編碼[M].北京:清華大學(xué)出版社，2006:284～291.

[2] Y.Linde， A.Buzo， R.M.Gray .An Algorithm for Vector Quantizer Design [J].IEEETransactions on Communications. 1980， 28 (1):84～95.

[3]郭晟偉.矢量量化技術(shù)及其在圖像壓縮中的應(yīng)用研究[D].長(zhǎng)沙:中南大學(xué)電路與系統(tǒng)專業(yè).

[4]耿國(guó)章，尹立敏，雷凱，王延杰.基于樹結(jié)構(gòu)矢量量化碼書的快速搜索算法[J].電子器件，2007，30(3):1061～1063.