[科普中國(guó)]-矢量量化

矢量量化( Vector Quantization，VQ) 是 20 世紀(jì)70 年代后期新發(fā)展起來(lái)的一種有效的有損壓縮技術(shù)，其理論基礎(chǔ)是香農(nóng)的速率失真理論。矢量量化的基本原理是用碼書(shū)中與輸入矢量最匹配的碼字的索引代替輸入矢量進(jìn)行傳輸與存儲(chǔ)，而解碼時(shí)僅需要簡(jiǎn)單地查表操作。其突出優(yōu)點(diǎn)是壓縮比大、解碼簡(jiǎn)單且能夠很好地保留信號(hào)的細(xì)節(jié)。矢量量化在圖像壓縮領(lǐng)域中的應(yīng)用非常廣闊，如衛(wèi)星遙感照片的壓縮與實(shí)時(shí)傳輸、數(shù)字電視與DVD 的視頻壓縮、醫(yī)學(xué)圖像的壓縮與存儲(chǔ)以及圖像識(shí)別等。因此矢量量化已經(jīng) 成為圖像壓縮編碼的重要技術(shù)之一。1

基本概念矢量量化是七十年代發(fā)展起來(lái)的一種數(shù)據(jù)壓縮技術(shù), 其理論基礎(chǔ)是信息論中的“速率—失真理論”。對(duì)一定的碼率R, 最小量化失真D (用量化信號(hào)與原始信號(hào)之間的誤差均方值和原信號(hào)均方值之比來(lái)衡量) 是一定的,即D可表示為R的函數(shù)D (R) 。無(wú)論對(duì)于何種信源, 矢量量化總優(yōu)于標(biāo)量量化, 且矢量維數(shù)越大, 優(yōu)越性越高。由此可知, 對(duì)于一個(gè)特定的信息源, 若給定碼率R, 那么任何量化器都不可能獲得低于“速率—失真理論”給出的下限D(zhuǎn) (R) 的量化失真。矢量量化的研究目的, 在于針對(duì)特定的信息源和矢量維數(shù), 找到一種最優(yōu)的矢量量化器, 能夠在R一定時(shí)給出最小的失真。3

基本原理矢量量化是標(biāo)量量化的拓廣和延伸?？梢赃@樣描述矢量量化的基本原理。4設(shè)有N個(gè)K維矢量{X1, X2, …, XN}, 其中第i個(gè)矢量可記為Xi={xi1, xi2, …, xik}, i=1, 2…, N。把K維空間RK無(wú)遺漏的劃分為J個(gè)互補(bǔ)相交的子空間R1, R2, …RJ, 即滿足:R1∪R2∪…∪RJ=RK;Ri∩Rj=!, i≠j。這些子空間R1, R2, …RJ稱為胞腔 (cell) 。在每一個(gè)子空間中找出一個(gè)代表矢量Yi={yi1, yi2, …, yik}, i=1, 2…, N。令矢量集Y=[Y1, Y2, …, YJ], Y叫作碼書(shū)或碼本, Yi叫碼字 (code word) 或碼矢 (code vector) , 碼書(shū)Y中的矢量個(gè)數(shù)J叫作碼書(shū)長(zhǎng)度。矢量量化的過(guò)程就是對(duì)任意輸入矢量X∈RK, 在Y中找到一個(gè)與X最接近的Yi代替X, Yi就是X的量化值。矢量量化的過(guò)程可以看成是從K維歐氏空間RK到其中一個(gè)有限子集Y的映射。這個(gè)映射可以記為:Q:RK→Y={Y1, Y2, …, YJ}。5

特點(diǎn)矢量量化是標(biāo)量量化思想的一種自然推廣。標(biāo)量量化利用了數(shù)據(jù)間的線性依賴性和概率密度函數(shù)的形狀來(lái)消除冗余度。香農(nóng)的速率-失真理論表明，即使信源是無(wú)記憶的，利用矢量編碼代替標(biāo)量編碼總能在理論上得到更好的性能。實(shí)際上，是兩種各分量間存在4種相互關(guān)聯(lián)的性質(zhì)：線性依賴性、非線性依賴性、概率密度函數(shù)的形狀以及矢量維度。為了去掉數(shù)據(jù)之間的這些冗余，作為標(biāo)量量化的一種推廣，矢量量化就能夠更好地壓縮數(shù)據(jù)。6

關(guān)鍵技術(shù)矢量量化的三大關(guān)鍵技術(shù),即碼書(shū)設(shè)計(jì)、碼字搜索和碼字索引分配。7

碼書(shū)設(shè)計(jì)矢量量化設(shè)計(jì)的首要問(wèn)題和核心問(wèn)題是碼書(shū)的設(shè)計(jì)。如果沒(méi)有碼書(shū)的設(shè)計(jì), 那么整個(gè)矢量量化系統(tǒng)就無(wú)法實(shí)現(xiàn)。碼書(shū)的質(zhì)量直接影響到壓縮效率和復(fù)原信號(hào)的質(zhì)量。7

1980年, Linde, Buzo和Gray提出了一種有效的矢量量化碼書(shū)設(shè)計(jì)算法, 也就是在矢量量化技術(shù)的發(fā)展中具有里程碑意義的LBG算法。LBG算法是碼書(shū)設(shè)計(jì)的一種經(jīng)典算法, 其優(yōu)點(diǎn)為物理概念清晰、算法理論嚴(yán)密及算法容易實(shí)現(xiàn)。但是, LBG算法并不完美, 它的主要缺點(diǎn)是:對(duì)初始碼書(shū)的依賴性強(qiáng), 易收斂于局部最優(yōu)。學(xué)者們主要針對(duì)LBG算法易陷入局部最小失真和對(duì)初始碼書(shū)的依賴性強(qiáng)這兩個(gè)方面對(duì)其進(jìn)行改進(jìn), 提出了多種改進(jìn)算法。a.基于神經(jīng)網(wǎng)絡(luò)的碼書(shū)設(shè)計(jì), 如自組織特征映射算法 (SOFM)，8它的收斂特性受初始碼書(shū)的影響較小, 對(duì)初始碼書(shū)和訓(xùn)練矢量的要求較低, 且可以很方便的修改已有的碼書(shū)。它的缺點(diǎn)是計(jì)算量大。b.遺傳算法。針對(duì)LBG易陷入局部最優(yōu)的問(wèn)題進(jìn)行的改進(jìn), 能得到全局最優(yōu)解。7

碼字搜索碼字搜索是矢量量化的一項(xiàng)關(guān)鍵技術(shù)。碼字搜索是指在碼書(shū)已經(jīng)存在的情況下, 對(duì)于給定的輸入矢量, 在碼書(shū)中搜索與輸入矢量之間失真最小的碼字。研究碼字搜索算法的主要目的就是尋求快速有效的算法以減少計(jì)算復(fù)雜程度, 且盡量使算法易于硬件實(shí)現(xiàn)。7

針對(duì)窮盡搜索算法的缺點(diǎn), 許多文獻(xiàn)提出了各種各樣的快速算法, 這些碼字搜索算法可以分為兩大類:一類是基于特殊碼書(shū)結(jié)構(gòu)的快速算法, 這類算法依賴于碼書(shū)結(jié)構(gòu)而在編碼時(shí)只搜索較小的子碼書(shū), 如分類矢量量化和基于樹(shù)結(jié)構(gòu)的矢量量化9等, 第二類算法不依賴于碼書(shū), 這類算法通常采用一些碼字排除準(zhǔn)則以減少計(jì)算量。這些算法有:a.部分失真搜索算法 (Partial Distortion Search, PDS) 。部分失真搜索算法的思想是:在計(jì)算某個(gè)碼字與輸入矢量之間的失真測(cè)度的過(guò)程中始終判斷累計(jì)的部分失真是否已經(jīng)超過(guò)目前的最小失真, 一旦超出則終止該碼字與輸入矢量間的失真計(jì)算。部分失真搜索算法是一種簡(jiǎn)單有效的算法, 但是其效率是有限的。b.基于Hadamard變換的搜索算法10。這類算法利用了變換域的特點(diǎn), 一是在變換域內(nèi)搜索最匹配碼字和在空間域內(nèi)搜索最匹配碼字是等價(jià)的, 另一個(gè)是變換域具有能量集中的特點(diǎn)。利用變換域的特點(diǎn)和其他搜索算法相結(jié)合能夠產(chǎn)生的較高效率的算法。7

碼字索引分配在矢量量化編碼和解碼系統(tǒng)中，如果信道有噪聲，則信道輸入端的索引i經(jīng)過(guò)信道傳輸可能輸出索引j而不是索引i，從而在解碼端引入額外失真。為了減少這種失真，可對(duì)碼字索引進(jìn)行重新分配。碼字索引分配就是在N！種分配方案中尋求一種最佳方法使得由信道噪聲引起的失真最小。然而當(dāng)N！較大時(shí)，測(cè)試所有方案是不可能的。因此，研究碼字索引分配算法的目的就是尋求有效的算法盡可能找到全局最優(yōu)或接近全局最優(yōu)的方案以減少由信道噪聲引起的失真，并盡可能減少計(jì)算復(fù)雜度和搜索時(shí)間。7

應(yīng)用矢量量化(VQ)作為一種有效的有損壓縮技術(shù),其突出優(yōu)點(diǎn)是壓縮比大以及解碼算法簡(jiǎn)單,因此它已經(jīng)成為圖像壓縮編碼的重要技術(shù)之一。矢量量化壓縮技術(shù)的應(yīng)用領(lǐng)域非常廣闊,如軍事部門和氣象部門的衛(wèi)星(或航天飛機(jī))遙感照片的壓縮編碼和實(shí)時(shí)傳輸、雷達(dá)圖像和軍用地圖的存儲(chǔ)與傳輸、數(shù)字電視和DVD的視頻壓縮、醫(yī)學(xué)圖像的壓縮與存儲(chǔ)、網(wǎng)絡(luò)化測(cè)試數(shù)據(jù)的壓縮和傳輸、語(yǔ)音編碼、圖像識(shí)別和語(yǔ)音識(shí)別等等。矢量量化技術(shù)的研究涉及多學(xué)科領(lǐng)域的理論和技術(shù),無(wú)論從理論角度還是從應(yīng)用角度來(lái)看,開(kāi)展對(duì)矢量量化技術(shù)的研究,不但具有重要的學(xué)術(shù)意義,還有極為重要的國(guó)防意義和經(jīng)濟(jì)意義。11

本詞條內(nèi)容貢獻(xiàn)者為:

尚軼倫 - 副教授 - 同濟(jì)大學(xué)數(shù)學(xué)科學(xué)學(xué)院