基于描述長度和層次聚類的Context模型量化

陳慧+++陳建華

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

關鍵詞：Context量化；層次聚類；描述長度

中圖分類號：TN919.81

文獻標識碼：A

DOI：10.3969/j.issn.1003-6970.2015.12.009

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

l 引言

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

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

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

2 層次聚類算法

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

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

Stepl：將每一個對象看作一類，計算兩兩之間的距離；

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

Step3：重新計算新類和與其他類的距離；

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

層次聚類最大的優點就是一次性地得到了整個聚類的過程，類數都可以直接根據樹結構來得到，改變類數不需要再次計算數據對象的歸屬。由于層次聚類需要計算兩兩類間相似度，其運算量較劃分聚類的運算量大。

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

3 描述長度

根據吳進提出可定義上述條件概率分布的描述長度為：

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

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

利用凝聚型層次聚類和上述描述長度差值作為聚類終止判別準則而實現的Context量化算法的具體步驟如下：

第一步：建立初始統計條件概率分布的Context模型；

第二部：計算所有兩兩概率分布的描述長度差值AL_mn；

第三步：若描述長度差值AL_mn<0，此兩類作為層次聚類合并的備選對；

第四步：在所有備選對中找到描述長度差值最小的兩個類m、n，即AL_mn<0且最小，此兩類合并，總類數減l；

第五步：若沒有任何備選對，則算法停止；否則轉到第二步。

5 仿真實驗

實驗數據來白于對標準測試庫中256x256每像素8bit的灰度圖像進行8級量化得到的簡化圖像，本文先用Girl和Barb這兩幅圖像對2個條件下的條件概率分布函數p（x_i|x_i-1x_i-2）進行訓練，分別采用本文算法和MCECQ算法對這些條件概率分布聚類后得到相應的Context量化器；然后將上述Context量化器分別應用于Lena、Woman、Baby三幅簡化圖像進行白適應算術編碼。算法在MATLAB 7.0中實現。

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

6 結論

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