陳慧+++陳建華

摘要：熵編碼被廣泛應(yīng)用于數(shù)據(jù)壓縮中，Context建?？梢杂行У睦眯旁葱蛄兄蟹?hào)間的相關(guān)性使信源編碼碼長(zhǎng)縮短，但是過大的Context模型會(huì)加大對(duì)信源符號(hào)的統(tǒng)計(jì)難度從而使編碼效率降低。為了使Context模型中的條件概率分布更加方便統(tǒng)計(jì)并且收斂于信源的實(shí)際概率分布，本文使用層次聚類算法對(duì)已經(jīng)建立的Context模型中的條件概率分布按照描述長(zhǎng)度最短的原則進(jìn)行聚類合并。實(shí)驗(yàn)證明此方法可以解決基于K-mean聚類的Context量化器設(shè)計(jì)算法中類數(shù)和初始聚類中心需要提前設(shè)定而造成設(shè)計(jì)困難的問題，還能使熵編碼的效率提高。

關(guān)鍵詞：Context量化；層次聚類；描述長(zhǎng)度

中圖分類號(hào)：TN919.81

文獻(xiàn)標(biāo)識(shí)碼：A

DOI：10.3969/j.issn.1003-6970.2015.12.009

本文著錄格式：陳慧，陳建華.基于描述長(zhǎng)度和層次聚類的Context模型量化[J].軟件，2015，36（12）：38-41

l 引言

熵編碼是以信息出現(xiàn)的概率分布特性作為編碼的依據(jù)，在信源壓縮過程中不產(chǎn)生失真，是一種無損的壓縮編碼。用Context模型可對(duì)有記憶的信源可以進(jìn)行有效編碼，它利用之前符號(hào)的統(tǒng)計(jì)量來預(yù)測(cè)當(dāng)前符號(hào)的概率分布情況，這樣當(dāng)前符號(hào)的概率分布就變成了條件概率分布。根據(jù)信息論中條件熵必不大于無條件熵這一結(jié)論，即H（Z|Z₁Z₂）≤H（Z|Z₁）≤H（z），條件越多條件熵可能越小。因信源的平均碼長(zhǎng)下限是熵，減少信源的熵，就有可能減少編碼的碼長(zhǎng)。然而條件越多可能出現(xiàn)的條件概率分布的個(gè)數(shù)就越多，從而導(dǎo)致利用已知信源符號(hào)對(duì)這些條件概率分布進(jìn)行估計(jì)時(shí)出現(xiàn)統(tǒng)計(jì)不充分的問題，即面臨“模型稀釋”的問題，反而使實(shí)際編碼時(shí)的碼長(zhǎng)增加。解決這個(gè)問題的辦法之一是對(duì)Context模型進(jìn)行量化，實(shí)際上就是利用聚類的思想來減少條件概率分布的總數(shù)，從而可以有效的緩解“模型稀釋”。在論文中Chen基于最小化條件熵的原則，對(duì)Context模型進(jìn)行量化（MCECQ），利用K-mean聚類算法對(duì)條件概率分布進(jìn)行合并；另一種相似的方法是Cagnazzo等在論文提出了基于最大互信息（MMI）的原則對(duì)Context模型進(jìn)行量化，也是利用類似K-mean聚類算法來實(shí)現(xiàn)條件概率分布的合并。但是K-mean聚類算法的類數(shù)和初始聚類中心需要提前設(shè)定、并且容易陷入局部最優(yōu)。論文中Forchhammer提出了最小白適應(yīng)碼長(zhǎng)的Context量化（MCICQ），利用白適應(yīng)碼長(zhǎng)為模型量化的判別準(zhǔn)則，并利用動(dòng)態(tài)規(guī)劃算法實(shí)現(xiàn)量化；論文中則利用最短路徑算法和上述自適應(yīng)碼長(zhǎng)準(zhǔn)則來實(shí)現(xiàn)Context量化，但這類方法只能用于二值信源，不能用于對(duì)多值信源的Context量化。

根據(jù)以上分析，我們要尋找一種不需要提前設(shè)定類數(shù)和初始聚類中心的聚類方法。實(shí)際上，聚類算法主要分為基于劃分的和基于層次的方法：基于劃分的方法最常見的是K-mean聚類算法，它隨機(jī)選取類中的K個(gè)對(duì)象作為初始聚類中心，計(jì)算類中其他對(duì)象和K個(gè)中心的距離，將每個(gè)對(duì)象分到最類似的類中，然后重復(fù)迭代直到滿足給定的判別準(zhǔn)則。此算法運(yùn)算效率高，類間相似度低?；趯哟蔚姆椒煞譃槟坌秃头至研?，其中最常見的是凝聚型。凝聚型層次聚類先將每個(gè)對(duì)象作為一個(gè)類，然后合并一個(gè)一個(gè)原子類為越來越大的類，直到所有對(duì)象都在一個(gè)類中，或按照終止條件停止。凝聚型層次聚類最初主要用于大數(shù)據(jù)樣本的統(tǒng)計(jì)歸類中，在論文中胡學(xué)坤將像素點(diǎn)的層次聚類結(jié)果用在圖像分割中；Jain等在論文中把基于特征的層次聚類算法在指紋識(shí)別中加以應(yīng)用。

如上分析所述，層次聚類不需要提前規(guī)定最佳的類數(shù)，也不需要給定初始的聚類中心，因而成為本文聚類方法的基礎(chǔ)。

2 層次聚類算法

絕大多數(shù)層次聚類屬于凝聚型層次聚類，只是類間相似度定義有所不同，四種可能的類間距離度量方法如下：

基于最小距離的凝聚型層次聚類的過程如下：

Stepl：將每一個(gè)對(duì)象看作一類，計(jì)算兩兩之間的距離；

Step2：將距離最小的兩類合并為一個(gè)新類；

Step3：重新計(jì)算新類和與其他類的距離；

Step4：重復(fù)Step2和Step3，直到滿足終止條件或所有類合并為一類。

層次聚類最大的優(yōu)點(diǎn)就是一次性地得到了整個(gè)聚類的過程，類數(shù)都可以直接根據(jù)樹結(jié)構(gòu)來得到，改變類數(shù)不需要再次計(jì)算數(shù)據(jù)對(duì)象的歸屬。由于層次聚類需要計(jì)算兩兩類間相似度，其運(yùn)算量較劃分聚類的運(yùn)算量大。

基本的凝聚型層次聚類算法最終會(huì)將所有類合并為一類，為獲得最佳的聚類類數(shù)，我們需要一個(gè)合理的判別準(zhǔn)則來終止層次聚類過程。Rissanen在論文中提出了描述長(zhǎng)度的概念，它不僅反映了一個(gè)統(tǒng)計(jì)模型的復(fù)雜程度，還體現(xiàn)了利用該模型對(duì)信源進(jìn)行編碼時(shí)的平均碼長(zhǎng)。本論文引入描述長(zhǎng)度作為層次聚類終止的判別條件，并且將其應(yīng)用到多值信源的Context量化中，實(shí)現(xiàn)對(duì)條件概率分布的聚類和最佳類數(shù)的確定。

3 描述長(zhǎng)度

根據(jù)吳進(jìn)提出可定義上述條件概率分布的描述長(zhǎng)度為：

聚類過程中，所有的類均兩兩分別進(jìn)行比較，將AL_mn為負(fù)數(shù)且最小的兩類合并。聚類直到剩下的任意兩類合并都不能使△L_mn，為負(fù)數(shù)為止，即合并不能再降低合并后的描述長(zhǎng)度，此時(shí)聚類的類數(shù)和聚類方案為最終的結(jié)果。

4 基于描述長(zhǎng)度和層次聚類的Context模型量化算法

利用凝聚型層次聚類和上述描述長(zhǎng)度差值作為聚類終止判別準(zhǔn)則而實(shí)現(xiàn)的Context量化算法的具體步驟如下：

第一步：建立初始統(tǒng)計(jì)條件概率分布的Context模型；

第二部：計(jì)算所有兩兩概率分布的描述長(zhǎng)度差值A(chǔ)L_mn；

第三步：若描述長(zhǎng)度差值A(chǔ)L_mn<0，此兩類作為層次聚類合并的備選對(duì)；

第四步：在所有備選對(duì)中找到描述長(zhǎng)度差值最小的兩個(gè)類m、n，即AL_mn<0且最小，此兩類合并，總類數(shù)減l；

第五步：若沒有任何備選對(duì)，則算法停止；否則轉(zhuǎn)到第二步。

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

實(shí)驗(yàn)數(shù)據(jù)來白于對(duì)標(biāo)準(zhǔn)測(cè)試庫(kù)中256x256每像素8bit的灰度圖像進(jìn)行8級(jí)量化得到的簡(jiǎn)化圖像，本文先用Girl和Barb這兩幅圖像對(duì)2個(gè)條件下的條件概率分布函數(shù)p（x_i|x_i-1x_i-2）進(jìn)行訓(xùn)練，分別采用本文算法和MCECQ算法對(duì)這些條件概率分布聚類后得到相應(yīng)的Context量化器；然后將上述Context量化器分別應(yīng)用于Lena、Woman、Baby三幅簡(jiǎn)化圖像進(jìn)行白適應(yīng)算術(shù)編碼。算法在MATLAB 7.0中實(shí)現(xiàn)。

表1中結(jié)果為本文算法自動(dòng)找到的Context量化器的聚類數(shù)為27類，用于對(duì)簡(jiǎn)化圖像進(jìn)行編碼時(shí)碼長(zhǎng)較短；而表2中結(jié)果為MCECQ算法設(shè)計(jì)的Context量化器用于編碼時(shí)的結(jié)果。具體來說，是在每種不同的給定類數(shù)情況下，通過不斷更新初始聚類中心后，得到一個(gè)較好的量化器，再最終用于編碼。由表2中結(jié)果可見，實(shí)際編碼的碼長(zhǎng)隨著聚類數(shù)目的增加，有先長(zhǎng)后短再變長(zhǎng)的規(guī)律，表明Context量化器確實(shí)存在最佳類數(shù)選擇的問題。而根據(jù)表1層次聚類的類數(shù)27，作為MCECQ算法的類數(shù)，將聚類得到的Context量化器用于三幅圖像編碼時(shí)，碼長(zhǎng)也最短，表明本文算法找到的最佳類數(shù)是可靠的。而且MCECQ算法實(shí)現(xiàn)時(shí)需要反復(fù)嘗試初始聚類中心和類數(shù)，實(shí)際通過聚類來設(shè)計(jì)Context量化器的時(shí)間很長(zhǎng)。因此利用本文算法可以大大縮短通過聚類來設(shè)計(jì)Context量化器的時(shí)間，提高設(shè)計(jì)效率。

6 結(jié)論

目前Context模型量化在高階熵編碼中的應(yīng)用越來越廣泛，本文提出的基于層次聚類和描述長(zhǎng)度的Context量化器設(shè)計(jì)算法，能夠解決以往基于K-mean聚類的Context量化器設(shè)計(jì)算法中，最佳聚類數(shù)未知和初始聚類中心需事先設(shè)定的問題，在算法計(jì)算過程中自動(dòng)迭代找到了最佳的聚類數(shù)目。實(shí)驗(yàn)證明，本文所提出的算法有助于提高Context量化器設(shè)計(jì)效率以及熵編碼效率。