基于描述长度和层次聚类的Context模型量化

陈慧+++陈建华

摘要：熵编码被广泛应用于数据压缩中，Context建模可以有效的利用信源序列中符号间的相关性使信源编码码长缩短，但是过大的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量化器设计效率以及熵编码效率。