基于改進(jìn)K均值的Context量化模型

彭淑燕 劉思聰

摘要：為了提高圖形編碼系統(tǒng)壓縮性能，可以通過使用Context模型來得到當(dāng)前所要編碼符號的概率。但是事實(shí)證明由于高階Context模型很難在統(tǒng)計(jì)中有效收斂于信號的真實(shí)分布，結(jié)果使得編碼效果降低，這就是所謂的“模型代價”問題。為了解決這一問題，一種有效的方法就是對高階Context模型進(jìn)行量化。由于Context量化問題與一般矢量量化問題相似，可以在設(shè)定合適的失真度量準(zhǔn)則的條件下，使用聚類算法來實(shí)現(xiàn)Context量化。目前，K均值是使用比較廣泛的一種聚類算法，但K均值算法必須具有確定的類數(shù)和選定的初始聚類中心。但在實(shí)際中，K均值往往難以準(zhǔn)確界定，從而導(dǎo)致了聚類效果不佳?；诖耍瑸榱苏业阶罴训木垲悢?shù)，本文提出采用聚類有效性函數(shù)來改進(jìn)K均值聚類算法。

【關(guān)鍵詞】 Context模型 Context量化 聚類有效性 最佳聚類數(shù)目Kopt K均值

Context quantization model based on improved K mean

Abstract： In order to improve the compression performance of the image coding system，the context model can be used to get the probability of the current coded symbol. However， it is proved that high-level context model is difficult to achieve the true distribution of the signal， as a result the effect of coding is reduced， which is the so-called “model cost” problem. Context quantization is an efficient method to deal with this problem. As the context quantification is similar to the general vector quantization problem， context quantization can be achieved by the clustering algorithm under the condition that a suitable distortion measure is defined. Currently， K-means is widely used as a clustering algorithm， but K-means algorithm is determined by the premise that the number of classes and the initial cluster centers are given. However， in fact， K-means is often difficult to be defined precisely， resulting in poor clustering effects. To obtain the best number of clustersin this paper， using cluster validity to improve K-means clustering.

一、引言

熵編碼在圖形編碼中占有非常重要的地位，它通過利用信源符號的統(tǒng)計(jì)特性[2，4，5]來獲得圖像的壓縮編碼。近十幾年來隨著算術(shù)編碼技術(shù)以及高速計(jì)算機(jī)的廣泛運(yùn)用，使得復(fù)雜的高階熵編碼實(shí)現(xiàn)成為可能。近幾年來，圖像編碼研究者的注意力逐漸集中在了高階熵編碼上。但是高階熵編碼的實(shí)現(xiàn)卻面臨著一個很嚴(yán)重的問題—模型代價問題。

為了解決模型代價[1]問題，一種有效的方法是對Context模型進(jìn)行量化。通過Context量化可以使經(jīng)過訓(xùn)練后得到的Context模型的條件分布經(jīng)過聚類后更易于統(tǒng)計(jì)、更好的收斂于信源的真實(shí)概率分布，而且在最小相對熵的準(zhǔn)則下，使得量化后增加的熵在最優(yōu)情況下最小并且可得到最小碼長。

本文采用改進(jìn)K均值的Context量化方法。其中選擇K均值算法作為Context量化的聚類算法。K均值聚類算法是目前最常使用的聚類算法之一。該算法對大型數(shù)據(jù)集的處理效率較高，可以達(dá)到較好的聚類效果。但K均值的聚類數(shù)目開始是確定的，而在實(shí)際處理中最佳聚類數(shù)目往往很難確定，而這導(dǎo)致了K均值的聚類效果不佳。

本文提出了一些檢驗(yàn)聚類有效性的函數(shù)指標(biāo)，主要有Davies-Bouldin（DB）指標(biāo)、Dunn指標(biāo)、Between-WithinProportion（BWP）指標(biāo)[6]等。使用這些有效性指標(biāo)可以得到最佳的聚類數(shù)目Kopt 。這使得Context量化能夠得到更短的熵編碼碼長。

二、基于聚類有效性函數(shù)的K均值Context量化器設(shè)計(jì)

2.1 Context模型量化原理

設(shè)有一隨機(jī)變量C，在給定條件變量E的前提下對C編碼所需的最小比特率為條件熵H（C|E）。其中當(dāng)E被量化為M=Q（E），條件熵H（C|E）變?yōu)镠（C|M），

則可得到：

由上式可知Context量化在增加熵的同時也減低了模型代價。

Context量化器的設(shè)計(jì)就是要找到一種最小的I（C；E|M）。為此可以定義相對熵公式如下：

而qk（c）=p（c|mk）可視作相應(yīng)的p（c|ei）的量化值，其中ei∈mk。這里選擇p（ei）D（p（c|ei）‖qk（c））作為量化的失真度標(biāo)準(zhǔn)。這里的相對熵是非對稱的，它并不是兩個失真度標(biāo)準(zhǔn)概率之間的真實(shí)距離。

定義Context量化的量化失真如下：

此時Context量化的最優(yōu)目標(biāo)就變?yōu)椋赫业阶罴训牧炕墧?shù)K，使對所有的ei∈E都找到一個最優(yōu)的劃分，然后為所有的K個劃分分別計(jì)算最優(yōu)量化值p（ei）D（p（c|ei）‖qk（c）），

在給定的量化級數(shù)K的條件，并且使量化失真最小。只有使量化值對于每一個劃分都有以下形式：

2.2聚類有效性指標(biāo)函數(shù)

2.2.1聚類算法的指標(biāo)

由上文可以，盡管K均值聚類是一種常用的聚類方法，但是卻有諸多條件的限制，為了突破這些條件的限制，學(xué)界提出了多種聚類有效性函數(shù)[3]。常見的聚類有效性函數(shù)有以下幾種：

（1）Dunn指標(biāo)

該指標(biāo)定義如下：

d（ci，cj）表示類ci和類cj樣本之間的相異性， diam（ck）表示同類中樣本的相似性。

當(dāng)該指標(biāo)越大時表示聚類效果越好，但聚類數(shù)對指標(biāo)并沒有明顯的指示性。

（2） Daivies-Bouldin（DB）指標(biāo)

該指標(biāo)定義如下：

k 和j表示類標(biāo)，xi（j）表示第j類的第i個樣本，xp（k）表示第k類的第p個樣本，nk表示第k類中的樣本數(shù)目。

其中：xq（j）表示第j類中的第q個樣本，nj表示第j類樣本數(shù)。

2.3基于聚類有效性函數(shù)的K均值Context量化器算法

算法步驟如下：

步驟1：用圖像來訓(xùn)練條件概率分布p=（c|ej），i=1…N。由此得到對p=（c|ej）和p=（ej）的準(zhǔn)確估計(jì)；

步驟2：從kmin循環(huán)至kmax；

（1）構(gòu)造一個初始化的Context模型量化器，Qcn=Qc1=p（c|mk），k=1…K這里K是量化劃分的數(shù)量。設(shè)n=1；

（2）為每一個集合中的p（c|ej）設(shè)定Context模型量化器Qcn=p（c|mk），k=1…K，對所有的集合mk，k=1…K，計(jì)算p（ej）D（p（c|ej）‖p（c|mk）），并找到其最小值。當(dāng)l≠c，將je從所屬集合ml移到另一集合mc，直到所有ml，l=1…K均被處理；

（3）對所有的集合[1，2]mk，用公式

計(jì)算量化值p（c|mk）從而獲得新的Context量化器Qcn+1；

（4）計(jì)算失真度D。如果它與上一步的迭代相比只是改變很小的數(shù)值，就停止，否則就將n+1賦值給n，然后轉(zhuǎn)至（2）；

（5）利用公式（1）、（2）、（3）分別計(jì)算Dunn、DB、BWP的指標(biāo)值。在這里將公式中的歐式距離全部改為散度值；

步驟3：輸出最佳聚類數(shù)、有效性指標(biāo)值和聚類結(jié)果。

步驟4：從kmin循環(huán)至kmax計(jì)算基于K均值聚類的Context量化的算術(shù)編碼長度，找到最小碼長的聚類數(shù)；

步驟5：比較上述幾種聚類有效性得到的最佳聚類數(shù)計(jì)算出的算術(shù)碼長與步驟4的到的最小碼長和聚類數(shù)進(jìn)行比較；

三、實(shí)驗(yàn)結(jié)果與分析

本文選擇了3幅512階灰度的圖形，將其均勻量化為8階灰度圖形來作為測試的信源數(shù)據(jù)。選擇以下的Context模型：

該模型共有83=512個條件分布，實(shí)驗(yàn)中聚類數(shù)K搜索范圍為[2，25]。得到了基于K均值算法的DB、Dunn、BWP有效性指標(biāo)值，結(jié)果如下表1。

由DB、Dunn、BWP指標(biāo)確定的最佳聚類數(shù)目曲線其中由DB指標(biāo)確定的最佳聚類數(shù)為9，由Dunn指標(biāo)確定的最佳聚類數(shù)為16，由BWP指標(biāo)確定的最佳聚類數(shù)為10。

在聚類數(shù)目為2～25的條件下，由K均值算法計(jì)算得到的Context模型的算術(shù)編碼長度，如表2所示。

由表2可知，在聚類數(shù)目為10時，得到了最小的算術(shù)編碼，其長度為174705。

通過對由幾種有效性評價指標(biāo)計(jì)算出的信源數(shù)據(jù)的最佳聚類數(shù)目與遍歷K均值找到的最佳聚類數(shù)目比較，從表3中可以看出，BWP指標(biāo)找到最佳聚類數(shù)為10，與遍歷K均值找到的最小碼長所對應(yīng)的聚類數(shù)相一致。即基于K均值的BWP聚類指標(biāo)評價能夠設(shè)計(jì)最優(yōu)的Context量化器。

四、結(jié)論

熵編碼是利用信源符號之間的相關(guān)性來進(jìn)行圖像的，但是由于高階熵編碼的復(fù)雜計(jì)算，因而Context模型被廣泛應(yīng)用熵編碼中，存在一個嚴(yán)重的問題就是模型代價問題。解決模型代價的最好方法就是利用模型量化，許多實(shí)驗(yàn)已經(jīng)證明Context模型量化的類似一般的矢量量化。目前最常用的矢量量化方法就K均值聚類算法，但是K均值聚類算法存在聚類數(shù)需先確定的缺點(diǎn)。這樣得到的聚類效果不是最佳，就量化器的設(shè)計(jì)不是最優(yōu)。為了得到最佳聚類數(shù)，本文提出了一種基于聚類有效性指標(biāo)的K均值聚類算法。通過比較上述幾種聚類指標(biāo)找到最佳的聚類數(shù)，設(shè)計(jì)了

一種最優(yōu)的Context量化器。

參 考 文 獻(xiàn)

[1] 陳建華.于Context量化的Context模型[J].云南大學(xué)學(xué)報，2002，24（5）：345-349.

[2] 楊亞彪.基于貝葉斯估計(jì)的Context量化器設(shè)計(jì)方法[J].昆明學(xué)報，2013，35（2）：79-82.

[3] 孫秀娟.基于新聚類有效性函數(shù)的改進(jìn)K-mean算法[J]計(jì)算機(jī)應(yīng)用，2008，28（12）：3244-3247.

[4] M. J. Weinberger， J.J. Rissanen， R. B. Arps.Applications of universal context modeling to lossless compression of gray-scale images[J]. IEEE Transactions on Image Processing，1996，5（4） ：575-586.

[5] D.Marpe， H. Schwarz， T. Wiegand，.Context-base dadaptive binary arithmetic coding in the H.264/AVC video compression standard[J].IEEE Transactions on Circuits and Systems for Video Technology，2003，13（7） 620-636.

[6] LF Lago-Fernández，F(xiàn) Corbacho. Normality-based validation for crisp clustering[J]. Pattern Recognition 2010， 43（3）：782-795.

[7] S. Forchhammer， X. Wu， Context quantization by minimum adaptive code length， in： Proceedings of IEEE International Symposium on Information Theory，Nice， France， June2007，246-250.