基于改进K均值的Context量化模型

彭淑燕 刘思聪

摘要：为了提高图形编码系统压缩性能，可以通过使用Context模型来得到当前所要编码符号的概率。但是事实证明由于高阶Context模型很难在统计中有效收敛于信号的真实分布，结果使得编码效果降低，这就是所谓的“模型代价”问题。为了解决这一问题，一种有效的方法就是对高阶Context模型进行量化。由于Context量化问题与一般矢量量化问题相似，可以在设定合适的失真度量准则的条件下，使用聚类算法来实现Context量化。目前，K均值是使用比较广泛的一种聚类算法，但K均值算法必须具有确定的类数和选定的初始聚类中心。但在实际中，K均值往往难以准确界定，从而导致了聚类效果不佳。基于此，为了找到最佳的聚类数，本文提出采用聚类有效性函数来改进K均值聚类算法。

【关键词】 Context模型 Context量化 聚类有效性 最佳聚类数目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.

一、引言

熵编码在图形编码中占有非常重要的地位，它通过利用信源符号的统计特性[2，4，5]来获得图像的压缩编码。近十几年来随着算术编码技术以及高速计算机的广泛运用，使得复杂的高阶熵编码实现成为可能。近几年来，图像编码研究者的注意力逐渐集中在了高阶熵编码上。但是高阶熵编码的实现却面临着一个很严重的问题—模型代价问题。

为了解决模型代价[1]问题，一种有效的方法是对Context模型进行量化。通过Context量化可以使经过训练后得到的Context模型的条件分布经过聚类后更易于统计、更好的收敛于信源的真实概率分布，而且在最小相对熵的准则下，使得量化后增加的熵在最优情况下最小并且可得到最小码长。

本文采用改进K均值的Context量化方法。其中选择K均值算法作为Context量化的聚类算法。K均值聚类算法是目前最常使用的聚类算法之一。该算法对大型数据集的处理效率较高，可以达到较好的聚类效果。但K均值的聚类数目开始是确定的，而在实际处理中最佳聚类数目往往很难确定，而这导致了K均值的聚类效果不佳。

本文提出了一些检验聚类有效性的函数指标，主要有Davies-Bouldin（DB）指标、Dunn指标、Between-WithinProportion（BWP）指标[6]等。使用这些有效性指标可以得到最佳的聚类数目Kopt 。这使得Context量化能够得到更短的熵编码码长。

二、基于聚类有效性函数的K均值Context量化器设计

2.1 Context模型量化原理

设有一随机变量C，在给定条件变量E的前提下对C编码所需的最小比特率为条件熵H（C|E）。其中当E被量化为M=Q（E），条件熵H（C|E）变为H（C|M），

则可得到：

由上式可知Context量化在增加熵的同时也减低了模型代价。

Context量化器的设计就是要找到一种最小的I（C；E|M）。为此可以定义相对熵公式如下：

而qk（c）=p（c|mk）可视作相应的p（c|ei）的量化值，其中ei∈mk。这里选择p（ei）D（p（c|ei）‖qk（c））作为量化的失真度标准。这里的相对熵是非对称的，它并不是两个失真度标准概率之间的真实距离。

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

此时Context量化的最优目标就变为：找到最佳的量化级数K，使对所有的ei∈E都找到一个最优的划分，然后为所有的K个划分分别计算最优量化值p（ei）D（p（c|ei）‖qk（c）），

在给定的量化级数K的条件，并且使量化失真最小。只有使量化值对于每一个划分都有以下形式：

2.2聚类有效性指标函数

2.2.1聚类算法的指标

由上文可以，尽管K均值聚类是一种常用的聚类方法，但是却有诸多条件的限制，为了突破这些条件的限制，学界提出了多种聚类有效性函数[3]。常见的聚类有效性函数有以下几种：

（1）Dunn指标

该指标定义如下：

d（ci，cj）表示类ci和类cj样本之间的相异性， diam（ck）表示同类中样本的相似性。

当该指标越大时表示聚类效果越好，但聚类数对指标并没有明显的指示性。

（2） Daivies-Bouldin（DB）指标

该指标定义如下：

k 和j表示类标，xi（j）表示第j类的第i个样本，xp（k）表示第k类的第p个样本，nk表示第k类中的样本数目。

其中：xq（j）表示第j类中的第q个样本，nj表示第j类样本数。

2.3基于聚类有效性函数的K均值Context量化器算法

算法步骤如下：

步骤1：用图像来训练条件概率分布p=（c|ej），i=1…N。由此得到对p=（c|ej）和p=（ej）的准确估计；

步骤2：从kmin循环至kmax；

（1）构造一个初始化的Context模型量化器，Qcn=Qc1=p（c|mk），k=1…K这里K是量化划分的数量。设n=1；

（2）为每一个集合中的p（c|ej）设定Context模型量化器Qcn=p（c|mk），k=1…K，对所有的集合mk，k=1…K，计算p（ej）D（p（c|ej）‖p（c|mk）），并找到其最小值。当l≠c，将je从所属集合ml移到另一集合mc，直到所有ml，l=1…K均被处理；

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

计算量化值p（c|mk）从而获得新的Context量化器Qcn+1；

（4）计算失真度D。如果它与上一步的迭代相比只是改变很小的数值，就停止，否则就将n+1赋值给n，然后转至（2）；

（5）利用公式（1）、（2）、（3）分别计算Dunn、DB、BWP的指标值。在这里将公式中的欧式距离全部改为散度值；

步骤3：输出最佳聚类数、有效性指标值和聚类结果。

步骤4：从kmin循环至kmax计算基于K均值聚类的Context量化的算术编码长度，找到最小码长的聚类数；

步骤5：比较上述几种聚类有效性得到的最佳聚类数计算出的算术码长与步骤4的到的最小码长和聚类数进行比较；

三、实验结果与分析

本文选择了3幅512阶灰度的图形，将其均匀量化为8阶灰度图形来作为测试的信源数据。选择以下的Context模型：

该模型共有83=512个条件分布，实验中聚类数K搜索范围为[2，25]。得到了基于K均值算法的DB、Dunn、BWP有效性指标值，结果如下表1。

由DB、Dunn、BWP指标确定的最佳聚类数目曲线其中由DB指标确定的最佳聚类数为9，由Dunn指标确定的最佳聚类数为16，由BWP指标确定的最佳聚类数为10。

在聚类数目为2～25的条件下，由K均值算法计算得到的Context模型的算术编码长度，如表2所示。

由表2可知，在聚类数目为10时，得到了最小的算术编码，其长度为174705。

通过对由几种有效性评价指标计算出的信源数据的最佳聚类数目与遍历K均值找到的最佳聚类数目比较，从表3中可以看出，BWP指标找到最佳聚类数为10，与遍历K均值找到的最小码长所对应的聚类数相一致。即基于K均值的BWP聚类指标评价能够设计最优的Context量化器。

四、结论

熵编码是利用信源符号之间的相关性来进行图像的，但是由于高阶熵编码的复杂计算，因而Context模型被广泛应用熵编码中，存在一个严重的问题就是模型代价问题。解决模型代价的最好方法就是利用模型量化，许多实验已经证明Context模型量化的类似一般的矢量量化。目前最常用的矢量量化方法就K均值聚类算法，但是K均值聚类算法存在聚类数需先确定的缺点。这样得到的聚类效果不是最佳，就量化器的设计不是最优。为了得到最佳聚类数，本文提出了一种基于聚类有效性指标的K均值聚类算法。通过比较上述几种聚类指标找到最佳的聚类数，设计了

一种最优的Context量化器。

参 考 文 献

[1] 陈建华.于Context量化的Context模型[J].云南大学学报，2002，24（5）：345-349.

[2] 杨亚彪.基于贝叶斯估计的Context量化器设计方法[J].昆明学报，2013，35（2）：79-82.

[3] 孙秀娟.基于新聚类有效性函数的改进K-mean算法[J]计算机应用，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 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.