楊 超，董世錕

（1.海軍航空工程學(xué)院電子信息工程系，山東 煙臺(tái) 264001；2.海軍大連艦艇學(xué)院學(xué)員旅，遼寧 大連 116018）

0 引言

圖像的數(shù)據(jù)量非常大。為了有效地傳輸和存儲(chǔ)圖像，常有壓縮圖像數(shù)據(jù)的必要。圖像壓縮就是在沒(méi)有明顯失真的前提下，將圖像的位圖信息轉(zhuǎn)變成另外一種能將數(shù)據(jù)量縮減的表達(dá)形式。這樣做是有理論基礎(chǔ)的。首先，盡管圖像中數(shù)據(jù)量很大，但數(shù)據(jù)之間不是完全獨(dú)立的，圖像中存在著各種各樣的相關(guān)性或冗余信息。即一部分?jǐn)?shù)據(jù)可以由另一部分?jǐn)?shù)據(jù)完全推算出來(lái)。其次，大部分圖像視頻信號(hào)的最終接收者是人眼，而人類(lèi)的視覺(jué)系統(tǒng)是一種高度復(fù)雜的系統(tǒng)，它能從極為雜亂的圖像中抽象出有意義的信息，并以非常精練的形式反映給大腦。人眼對(duì)圖像中的不同部分的敏感程度是不同的，如果去除圖像中對(duì)人眼不敏感或意義不大的部分，對(duì)圖像的主觀質(zhì)量是不會(huì)有很大影響的。

正由于圖像壓縮的必要性和可行性，圖像壓縮編碼研究成為一個(gè)越來(lái)越活躍的領(lǐng)域。在諸如基于Internet的多媒體通信、可視電話(huà)、數(shù)字電視、多媒體計(jì)算機(jī)等領(lǐng)域得到了廣泛的應(yīng)用。

圖像編碼技術(shù)包括三個(gè)主要方面：①圖像壓縮的新算法的研究；② 基于VLSI技術(shù)的壓縮算法的硬件實(shí)現(xiàn)；③面向不同應(yīng)用場(chǎng)合的壓縮編碼標(biāo)準(zhǔn)的制定。其中，壓縮算法的研究是圖像編碼技術(shù)的關(guān)鍵。

本文介紹的基于矢量量化（Vector Quantization，VQ）的圖像壓縮方法是20世紀(jì)70年代后期發(fā)展起來(lái)的一種數(shù)據(jù)壓縮技術(shù)，是在圖像編碼技術(shù)中研究得較多的新型量化編碼方法。其基本思想是[1]：矢量量化編碼優(yōu)于標(biāo)量量化，將若干個(gè)標(biāo)量數(shù)據(jù)組構(gòu)成一個(gè)矢量，然后在矢量空間給以整體量化，從而壓縮了數(shù)據(jù)而不損失多少信息。

LBG算法[1]是Y.Linde，A.Buzo與R.M.Gray在1980年給出的矢量量化算法，以后有許多人進(jìn)行了改進(jìn)。其思想是：對(duì)于一個(gè)訓(xùn)練序列，先找出其中心，再用分裂法產(chǎn)生一個(gè)初始碼書(shū)，再把訓(xùn)練序列按碼書(shū)中的元素分組，對(duì)這一分組再找每組的中心得到新的碼書(shū)，轉(zhuǎn)而把新碼書(shū)作為初始碼書(shū)再進(jìn)行上述過(guò)程直至滿(mǎn)意為止。

本文在介紹基于矢量量化的圖像壓縮方法基礎(chǔ)上，將按照LBG算法以均方誤差法計(jì)算兩向量之間的距離，以分裂法產(chǎn)生初始碼書(shū)（以4×4塊圖像組成的256 碼書(shū)），通過(guò)全搜索算法進(jìn)行碼字搜索，對(duì)64×64的Lena 灰度圖像進(jìn)行矢量壓縮編碼，計(jì)算還原結(jié)果；LBG算法的缺陷是運(yùn)行時(shí)間長(zhǎng)，圖像質(zhì)量有較大的提升空間，對(duì)此許多論文都進(jìn)行了探討[2-14]，但是，文章大多在討論算法，對(duì)影響運(yùn)行速度的重要因素——訓(xùn)練樣本數(shù)目的討論卻鮮見(jiàn)文章發(fā)表。有鑒于此，本文就選擇合適數(shù)目的圖像樣本與運(yùn)算速度的關(guān)系進(jìn)行討論，試圖找到提高LBG算法運(yùn)算速度的有效途徑。

1 基于矢量量化的圖像壓縮法及LBG算法

1）基于矢量量化的圖像壓縮方法。

在數(shù)據(jù)與圖像的壓縮中，無(wú)論是數(shù)據(jù)還是圖像，都可以看成是一串?dāng)?shù)據(jù)。設(shè)這段數(shù)據(jù)是m個(gè)數(shù)據(jù)，把它截成M段（一般是相等的，例如每段k個(gè)數(shù)據(jù)），即把m個(gè)數(shù)據(jù)變成M個(gè)數(shù)據(jù)向量，再把M個(gè)向量分成N個(gè)組，對(duì)每個(gè)組挑選一個(gè)數(shù)據(jù)向量，作為這個(gè)組的代表，例如，第j個(gè)組中的代表為yj，j=0,1,…,N?1。所謂壓縮，就是圖像上的數(shù)據(jù)向量，如果屬于第j個(gè)組，則這個(gè)數(shù)據(jù)向量就用這個(gè)組的代表向量 yj代替，這時(shí)的編碼就是在碼書(shū)的相應(yīng)位置上記下編號(hào)j，而不必記下yj本身。而記錄{yj}的文件稱(chēng)為碼書(shū)。如上N為量化向量yj的個(gè)數(shù)，即碼書(shū)長(zhǎng)度為N，這時(shí)傳輸或存儲(chǔ)下標(biāo)所需比特?cái)?shù)為log2N。因此，平均傳輸一個(gè)像素所需的比特?cái)?shù)為(log2N)/k。例如一個(gè)圖像的每個(gè)像素用256級(jí)灰度，則每個(gè)像素點(diǎn)占用8 比特。如果壓縮后平均每個(gè)像素點(diǎn)占R 比特，則有 R=(log2N)/k，即N應(yīng)滿(mǎn)足關(guān)系 N=2kR。實(shí)用中，一般總令kR為正整數(shù)以便用于計(jì)算。這樣，向量量化方法的壓縮比是可以控制的。

2）LBG算法是典型的矢量量化算法。

a.初始化：給定級(jí)數(shù)N，失真閾值ε，一個(gè)訓(xùn)練序列，某個(gè)初始N級(jí)碼本令

其中，si={xj:d(xj?yi)≤d(xj?yl)}，l=1,2,…,N。

計(jì)算總平均失真

c.如果（Dn?1?Dn）/Dn≤ε，停止；為最終碼本；否則繼續(xù)。

2 方案設(shè)計(jì)

1）中心向量。

在矢量量化編碼中，關(guān)鍵是碼本的建立和碼字搜索算法。如上所述，在數(shù)據(jù)和圖像的壓縮中，當(dāng)k 確定后，問(wèn)題就變成了如何分組及如何對(duì)每個(gè)組挑選代表的問(wèn)題。當(dāng)然，這個(gè)代表可以是組中的向量，也可以不是組中的向量，這個(gè)理想的代表當(dāng)然應(yīng)當(dāng)是組中各向量的中心向量。為求中心，需要引入兩向量x與yj之間距離 d (x,yj)）的概念。當(dāng)然，兩向量之間的距離多種多樣，最常用的幾個(gè)如下：

d.加權(quán)均方誤差

本設(shè)計(jì)的碼本的生成算法是在未知信源分布，但已知信源的一列具有代表性且足夠長(zhǎng)的樣點(diǎn)集合（即訓(xùn)練序列）的設(shè)計(jì)算法，具體采用的是LBG算法，兩向量之間的距離采用均方誤差法。

選擇有許多方法，不同初始碼書(shū)對(duì)最終碼書(shū)往往有較大的影響。本文采用分裂法產(chǎn)生初始碼書(shū)。設(shè)kR=l，得到2lN=級(jí)量化器，具體步驟如下：

3）搜索過(guò)程。

碼字搜索是矢量量化中的一個(gè)最基本問(wèn)題，矢量量化過(guò)程本身實(shí)際上就是一個(gè)搜索過(guò)程，即搜索出與輸入最為匹配的碼本。矢量量化中最常用的搜索方法是全搜索算法和樹(shù)搜索算法。全搜索算法與碼本生成算法是基本相同的，在給定速率下其復(fù)雜度隨矢量維數(shù)K以指數(shù)形式增長(zhǎng)，全搜索矢量量化器性能好但設(shè)備較復(fù)雜。樹(shù)搜索算法又有二叉樹(shù)和多叉樹(shù)之分，它們的原理是相同的，但后者的計(jì)算量和存儲(chǔ)量都比前者大，性能比前者好。樹(shù)搜索的過(guò)程是逐步求近似的過(guò)程，中間的碼字是起指引路線(xiàn)的作用，其復(fù)雜度比全搜索算法顯著減少，搜索速度較快。由于樹(shù)搜索并不是從整個(gè)碼本中尋找最小失真的碼字，因而它的量化器并不是最佳的，其量化信噪比低于全搜索。本文采用全搜索算法。

為了討論選擇合適訓(xùn)練樣本數(shù)以減少運(yùn)算時(shí)間方法的有效性，本文首先討論訓(xùn)練樣本圖像數(shù)與壓縮結(jié)果的關(guān)系，在圖像解壓質(zhì)量較好的前提下，計(jì)算、比較不同訓(xùn)練樣本數(shù)對(duì)應(yīng)的圖像編碼時(shí)間。

3 仿真實(shí)驗(yàn)

用數(shù)碼相機(jī)拍攝10幅圖像，經(jīng)過(guò)photoshop 軟件的處理，使其變換成大小為64×64的灰度圖像，并分別以JPG形式存儲(chǔ)。將這些訓(xùn)練圖像分劃成4×4 并且不相交的小塊，通過(guò)LBG算法計(jì)算256個(gè)碼本構(gòu)成的碼書(shū)。按照LBG算法以均方誤差法計(jì)算兩向量之間的距離，通過(guò)全搜索算法進(jìn)行碼字搜索，得到的壓縮Lena圖像還原結(jié)果如圖1所示，其中，a）為原始圖像；b）為經(jīng)過(guò)VQ 編碼后解碼出來(lái)的圖像，壓縮信噪比SNRrms為21.554 8 dB，碼本維數(shù)k=16，碼書(shū)長(zhǎng)度N=256，壓縮后平均每個(gè)像素點(diǎn)占比特?cái)?shù)R=0.5 bpp，壓縮率為1/16。

為了研究訓(xùn)練樣本圖像數(shù)與圖像壓縮編碼效果的關(guān)系，本文由仿真試驗(yàn)給出了圖2曲線(xiàn)。

圖2是用LBG算法對(duì)64×64的Lena 灰度圖像進(jìn)行矢量編碼時(shí)，訓(xùn)練樣本個(gè)數(shù)與量化信噪比PSNR的關(guān)系，k=16，R=0.5 bpp。

圖1 Lena數(shù)字圖像壓縮編碼結(jié)果

圖2 訓(xùn)練樣本個(gè)數(shù)與量化信噪比PSNR的關(guān)系

圖3是當(dāng)訓(xùn)練樣本數(shù)分別為10、20、30、50和100時(shí)，用本文的矢量量化壓縮編碼方法對(duì)64×64的Lena 灰度圖像進(jìn)行壓縮編碼后得到的解碼圖像，k=16，R=0.5 bpp。

圖3 圖像還原效果

由圖2和圖3可見(jiàn)，訓(xùn)練樣本數(shù)為10幅圖像以上時(shí)，用LBG算法對(duì)64×64的Lena 灰度圖像進(jìn)行矢量編碼圖像質(zhì)量較好。

圖4是用LBG算法對(duì)64×64的Lena 灰度圖像進(jìn)行矢量編碼時(shí)，訓(xùn)練樣本個(gè)數(shù)與編碼運(yùn)算時(shí)間的關(guān)系，k=16，R=0.5 bpp。

由圖4可見(jiàn)，圖像訓(xùn)練樣本數(shù)為10幅、20幅和100幅圖像時(shí)，LBG圖像壓縮算法運(yùn)行時(shí)間分別是50 min、90 min和360 min。

用100幅圖像作為訓(xùn)練樣本圖像進(jìn)行運(yùn)算需要的時(shí)間大約是以10幅圖像為訓(xùn)練樣本圖像的5 倍。

圖4 訓(xùn)練樣本個(gè)數(shù)與運(yùn)算時(shí)間的關(guān)系

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

本文按照LBG算法以均方誤差法計(jì)算兩向量之間的距離，通過(guò)全搜索算法進(jìn)行碼字搜索，以分裂法產(chǎn)生初始碼書(shū)（以4×4塊圖像組成的256 碼書(shū)），得到壓縮Lena圖像還原結(jié)果。仿真實(shí)驗(yàn)表明，以100個(gè)圖像為訓(xùn)練樣本，對(duì)64×64的灰度圖像，以4×4塊圖像組成的256 碼書(shū)進(jìn)行恢復(fù)，按照LBG算法以均方誤差法計(jì)算兩向量之間的距離，通過(guò)全搜索算法進(jìn)行碼字搜索，可以得到較高的數(shù)字圖像壓縮比（壓縮率為1/16）；另外，圖像訓(xùn)練樣本數(shù)在10個(gè)以上時(shí)，用本文的矢量量化壓縮編碼方法對(duì)圖像進(jìn)行壓縮編碼，都可以得到較高的數(shù)字圖像壓縮比，但用100幅圖像作為訓(xùn)練樣本圖像進(jìn)行運(yùn)算需要的時(shí)間是以10幅圖像為訓(xùn)練樣本圖像的5 倍。由此可見(jiàn)，尋找合適的訓(xùn)練樣本圖像數(shù)，可以大大縮短圖像壓縮編碼時(shí)間。

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

[2]張濤,于鳳萍,要強(qiáng),等.高效的模糊聚類(lèi)初始碼書(shū)生成算法[J].紅外與激光,2010,39(1):179-183.

[3]陳善學(xué).矢量量化的初始碼書(shū)算法[J].計(jì)算機(jī)工程與應(yīng)用,2010,11:26-28.

[4]鄧宏貴,郭晟偉.采用分量均值正交分割法設(shè)計(jì)矢量量化初始碼書(shū)[J].中南大學(xué)學(xué)報(bào):自然科學(xué)版,2010,41(2):628-631.

[5]胡光波,周勇,徐騫.改進(jìn)向量量化算法的圖像壓縮研究[J].科學(xué)技術(shù)與工程,2010,10(14):3517-3519.

[6]榮秋生,潘梅森,顏君彪.基于Hopfiled神經(jīng)網(wǎng)絡(luò)的圖像矢量量化[J].微計(jì)算機(jī)信息:管理一體化,2007,23(2-3):301-302.

[7]李霆,王東進(jìn),劉發(fā)林.基于混合遺傳算法的碼書(shū)設(shè)計(jì)方法[J].電訊技術(shù),2007,47(1):151-153.

[8]胡俊.基于小波變換的多級(jí)矢量量化圖像編碼算法[J].現(xiàn)代電子技術(shù),2007,241(2):56-58.

[9]華宇寧,楊潔.基于遺傳算法的碼本設(shè)計(jì)及其在說(shuō)話(huà)人識(shí)別中的應(yīng)用[J].沈陽(yáng)理工大學(xué)學(xué)報(bào),2007,26(5):62-64.

[10]紀(jì)震,廖惠連,許文煥,等.粒子對(duì)算法在圖像矢量量化中的應(yīng)用[J].電子學(xué)報(bào),2007,35(10):1916-1920.

[11]王冬芳,廖裕民,余寧梅.矢量量化碼書(shū)旋轉(zhuǎn)壓縮的研究[J].計(jì)算機(jī)工程與應(yīng)用,2008,44(24):53-58.

[12]劉剛,劉晶,王泉.一種基于覆蓋域密度的LBG算法[J].計(jì)算機(jī)應(yīng)用,2008,28(12):319-325.

[13]郭瑩,董吉文.一種快速的碼本設(shè)計(jì)算法[J].山東科學(xué),2008,21(1):57-60.

[14]李碧,林土勝,姜靈敏.應(yīng)用協(xié)同進(jìn)化的圖像矢量量化碼書(shū)設(shè)計(jì)方法[J].計(jì)算機(jī)應(yīng)用,2008,44(36):29-31.