一种基于自适应分块八叉树颜色量化的图像压缩技术*

吴振华,沈虎峻,2,公佐权,冯平,龚彤艳,3,邓明森

(1.贵州财经大学信息学院，贵州 贵阳 550025; 2.贵州师范学院贵州省纳米材料模拟与计算重点实验室，贵州 贵阳 550018; 3.中国科学院计算研究所计算机体系结构国家重点实验室，北京 100180)

1 引言

随着信息时代逐渐演变为数字时代，基于计算机的多媒体技术的发展引起了许多研究者的极大关注。数字图像信息作为最重要的信息之一，在我们的日常生活中越来越广泛和频繁地被使用。因为高分辨率的图像需要占用大量的存储空间，因此改进图像数据的压缩技术对于多媒体行业来说变得非常迫切和必要[1 - 3]。

众所周知，图像中的任何颜色都可以通过几种特定的原色组合生成，例如红色、绿色和蓝色(RGB)。对于常见的图像，每个颜色分量由0～255的数字表示，对应于1个字节。因此，RGB图像的文件大小(分辨率为M×N)至少为M×N×3个字节，而带Alpha通道的RGB(ARGB)图像文件大小至少为M×N×4个字节。图像压缩技术的关键问题是，如何在保证图像质量的前提下有效地压缩图像数据，以及如何在颜色损失最低的前提下有效地恢复原始图像。

在图像压缩技术中，由于颜色量化CQ(Color Quantization)技术可以很容易地实现图像压缩，有效地减少图像存储空间，已经被广泛使用。为了重建具有最小色彩损失的压缩图像并减少人眼可以检测到的视觉差异，人们已经提出了各种基于CQ的算法。这些算法包括神经网络[4]、中值切割算法[5,6]、RWM切割算法[7]、k-均值算法[8 - 12]、中位分割算法[13]、模糊C均值算法[14 - 16]、基于DWT的聚类算法[17]等。然而，由于色彩空间的选择、图像内容的差异等方面的影响，目前还没有一种万能的方法适应所有的颜色量化，都或多或少地存在一些缺陷。八叉树颜色量化OCQ(Octree Color Quantization)算法最初由Gervautz等人[18]提出。与其他CQ算法相比，该算法量化后的图像效果层次丰富，并且时间和空间上的消耗很低。此外，OCQ算法使用了调色板技术，可以在常数时间内通过调色板直接访问每个像素数据，而这种特征是其他图像压缩算法如离散余弦变换(典型代表是JPEG文件[19])、小波变换(典型代表是JPEG2000文件[20])、字典压缩(典型代表是PNG文件使用的LZ77[21]派生算法压缩)等所不具备的，因为这些算法需要经过复杂的解码恢复所有原始数据后，才能随机访问任意像素。因此，OCQ使用的调色板技术可以在图像压缩状态下随机访问图像中的数据，该特性能让应用程序在有限的内存资源下容纳更多的压缩图像数据，也保证应用程序能高效率地对压缩图像数据做随机访问。实际上，有很多的场合需要这种特性，譬如绘制带有大量图片的Web页面、画面丰富绚丽的电脑游戏软件等等。然而，由于传统OCQ算法的限制，处理后的图像细节已经不能满足多媒体行业日益增长的需求。

因此，本文提出了一种自适应分块八叉树颜色量化AB-OCQ(Adaptive Block Octree Color Quantization)算法来提高图像质量。其中，自适应分块量化用于提高图像的局部细节质量，在保留OCQ优势的前提下，有效地解决了OCQ算法所面临的问题。

2 AB-OCQ算法介绍

传统的OCQ算法仅支持RGB 3个颜色通道，由于每个颜色通道的每1位有0或1 2种状态，因此传统的OCQ算法需要23=8个分支来存储每个节点上的颜色状态。为了支持带Alpha通道图像的颜色量化，我们把八叉树扩展为24=16分支树，如图1所示。

Figure 1 Tree representation for sixteen branches employed by AB-OCQ algorithm图1 AB-OCQ算法使用的16分支树表示

例如，对于半透明橙色，其ARGB值的分量分别用128,255,168,76表示，二进制表示分别为10000000,1111111,10101000,01001100。根据每个颜色位从高到低的优先级划分，第1层子节点的位值为14(二进制值为1110)，接下来的子节点的位值分别为5(0101)，6(0110)，4(0100)，7 (0111)，5(0101)，4(0100)和4(0100)。通过插入图像中所有的颜色值，形成1个称为颜色树的结构。在该颜色树中(如图2所示)，最高层(Level 1)具有最高优先级，而最低层(Level 8)具有最低优先级。

Figure 2 Process of prioritizing hierarchies in translucent orange图2 半透明橙色按优先级划分层次结构的过程

Figure 4 Process of inserting node in AB-OCQ algorithm图4 AB-OCQ算法插入节点的过程

从图1和图2中可以看出，这个结构下最大颜色数量是168，是1个巨大的数字。为了充分压缩存储空间，需要合并和裁剪颜色树上那些不重要的颜色。如果最终留下的颜色数量不超过256，我们就可以使用1个字节来表示在这个颜色树上每个原始ARGB颜色的位置，从而可以显著减少存储空间占用。对每个节点，我们定义它的结构如图3所示。

Figure 3 Node structure in the color tree图3 颜色树的节点结构

初始化节点时，节点结构中的每个分量都被赋值为0。颜色插入过程按照以下步骤进行(参见图4)：

(1)从Root层开始，当前处理的节点指针指向Root。

(2)按照颜色的bit位从高到低的优先级进行如下循环处理。

①根据ARGB的bit值生成索引值。

②判断索引位置的childNode是否为空。如果为空，则在此位置创建新的子节点，并记录当前层次。如果处理到最低位，则将该节点标记为叶节点，并将其添加到叶节点列表中。

③将颜色的A,R,G,B值添加到该子节点的A,R,G,B值，然后将访问次数加1。

④如果该子节点是叶节点则跳出循环，否则，将当前处理的指针指向该子节点。

通过上述过程不断插入颜色数据，就可以构造出1棵颜色树：这棵树上的每个父节点都有其所有子节点的统计信息。根据这个特征，当颜色树中的叶节点数超过256时，进行如下的合并处理(参见图5)：

(1)从叶节点链表中，找到最低层和最低访问次数的叶节点，它是当前最不重要的，应该首先被合并。

(2)合并该叶节点到父节点下，并将父节点标记为新的叶节点，添加到叶节点列表中。

Figure 5 Process of merging node in AB-OCQ algorithm图5 AB-OCQ算法合并节点的过程

按照上面插入和合并的过程处理完所有颜色数据之后，即得到1棵颜色树。树中的每个叶节点都包含重要的颜色信息。把这些叶节点的颜色数据提取出来，得到1个颜色集合(称为调色板)，可用于映射原始的颜色数据。

传统的OCQ由于仅仅使用了1个至多256种颜色的全局调色板，在处理色彩丰富的图像时不可避免地会导致颜色失真，如图6所示。

Figure 6 Details of the image are seriously distorted in the traditional octree color quantization algorithm图6 传统八叉树颜色量化算法造成图像细节部分失真

因此，改进的OCQ算法(即自适应分块OCQ或AB-OCQ)的基本思想是对图像中那些细节丰富的部分执行分块的OCQ处理。首先，使用1个大小为16×16的滑动窗口来分析图像中的透明区域和单一颜色区域，这些透明区域和单一颜色区域是可以用更简单的方式表达的。如果图像中没有这些区域，则将整个图像视为1个子区域。然后，对子区域(或分块)执行OCQ处理，计算子区域内得到的调色板颜色数量和原始图像的颜色数量，把这2个数量的比率记为α：如果α=1，则表示这个子区域内没有任何颜色被合并，此时通过OCQ算法处理这个区域，不会造成颜色数据损失；如果α接近0，则表示这个子区域中的大多数颜色都会被合并，如果用OCQ处理将会产生严重的失真。因此，在AB-OCQ算法中设置了1个阈值。计算过程中，如果计算出来的α值小于该阈值，则需要继续把这个子区域划分为更小的子区域，重复执行AB-OCQ过程。特别地，如果把这个阈值设置为1，则表示不允许合并任何颜色，处理完整个图像后将获得1个完全无损图像。如果此阈值设置为0，则表示每个子区域的处理过程都退化为传统的OCQ算法。

图7显示了AB-OCQ算法的过程。

AB-OCQ中定义了4种类型的子区域。

(1)完全透明的块(不占用任何空间);

(2)相同的颜色块(只需要1个像素空间);

(3)普通颜色块(包含1个局部调色板数据和颜色索引数据);

(4)子区域块(包含这4种类型的子区域)。

OCQ使用的调色板技术具有直接随机访问每个像素的颜色数据的特性，图像通过AB-OCQ算法处理后，可获得各种子区域的数据块，图像中的每个像素都有相应的数据块映射，因此不难看出AB-OCQ依然保留了这一特性，使图像中的像素数据在保持压缩状态下依然能够高效率地被随机访问。

Figure 7 Process of AB-OCQ algorithm图7 AB-OCQ算法的处理过程

3 AB-OCQ 算法的实验与讨论

为了验证AB-OCQ算法的性能，我们在量化大小、压缩比和图像质量方面对AB-OCQ和OCQ算法进行了比较；同时，对AB-OCQ算法处理后的图像与JPEG、PNG等典型的主流图像格式在文件大小、压缩比和图像质量等方面进行了比较。

本文用峰值信噪比PSNR评估图像质量：

(1)

其中，MAX代表图像颜色的最大值，对于常用的每个颜色分量使用8位表示时，该值为255，MSE为式(2)定义的均方误差：

(2)

其中,I(i,j)表示像素点(i,j)处理后的数据，K(i,j)表示像素点(i,j)的原始数据，M和N表示图像的宽和高，根据方程式中的定义，图像质量的改善需要增加PSNR值。

压缩比Rc定义为未压缩图像数据大小Sunc和压缩图像数据大小Sc之间的比率：

(3)

3.1 不同算法处理不带Alpha通道的图像比较

图8和表1显示了在处理不带Alpha通道的无损图像(大小为1960×1960)时，OCQ和AB-OCQ算法之间的比较(图8a)。当采用传统的OCQ算法处理该图像时，能看到图像上的脸部明显出现了严重的失真(如图8b所示)。图8c是无损图像到JPEG图像高质量的转换，转换后的JPEG图像PSNR值是40 dB。从表1可以看出，与传统的OCQ算法相比，AB-OCQ算法在图像质量方面得到了显著改善，并且改善的程度取决于阈值的设定。我们发现当阈值设置为0.05时，采用AB-OCQ算法可以在图像质量和图像量化尺寸之间实现最佳平衡。比如，与OCQ算法相比，AB-OCQ算法将图像量化大小仅仅增加了1.05倍，但将图像质量提高了1.25倍。令人兴奋的是，当阈值设置为0.05时，AB-OCQ算法的图像质量(40 dB)已经与JPEG图像的质量相当了。

Figure 8 Comparison of RGB images processed by different algorithms图8 不同算法处理后的RGB图像比较

为了进一步评估AB-OCQ的性能，从各种互联网站点随机选择了1 000幅不带Alpha通道的图像,然后分别用OCQ和AB-OCQ算法来处理。表2显示了OCQ和不同阈值的AB-OCQ算法获得的结果之间的比较。类似地，当阈值设置为0.03时，采用AB-OCQ算法可以在图像质量和图像量化尺寸之间实现最佳平衡。比如，与OCQ算法相比，AB-OCQ算法将平均量化大小增加了1.07倍，但图像质量提高了1.15倍。

Table 1 Comparison between OCQ and AB-OCQ algorithms with different thresholds on a RAW image from quantization size,compression ratio, and image quality表1 在量化大小、压缩比和图像质量方面，用OCQ和不同阈值的AB-OCQ算法处理无损图像的比较

3.2 不同算法处理带Alpha通道的半透明图像比较

带Alpha通道的半透明图像通常用于Web页面和电脑游戏的图像合成等。为了说明AB-OCQ算法在处理带Alpha通道的半透明图像的性能，从互联网上随机选择了1幅半透明的PNG图像(大小为1698×1131)。图9和表3显示了OCQ和AB-OCQ算法性能之间的比较。图9a是1幅无损的PNG图像，图9b是图9a的局部放大。由于AB-OCQ算法不需要大量空间来存储同色或透明子区域，因此AB-OCQ算法在处理这类图像时的表现优于OCQ。比如，当阈值设置为0.3或更低时，AB-OCQ算法显著提高了图像质量和压缩比，如图9c、图9d和表3所示。

Table 2 Comparison between OCQ and AB-OCQ algorithms with different thresholds on 1 000 images without Alpha channel表2 OCQ和不同阈值的AB-OCQ算法处理1 000幅不带Alpha通道图像的比较

Figure 9 Comparison of ARGB images processed by different algorithms图9 不同算法处理后的ARGB图像比较

同样地，从各种互联网站点随机选择了1 000幅带Alpha通道的半透明PNG图像并分别对这些图像用OCQ和AB-OCQ算法进行处理，结果如表4所示。与OCQ算法相比，AB-OCQ算法显著提高了图像质量。同时，当阈值小于0.3(表4中所示)时，AB-OCQ算法实现了更高的压缩比，与表3中给出的结果一致。

Table 3 Comparison between OCQ and AB-OCQ algorithms with different thresholds on a half-transparent lossless PNG image from quantization size,compression ratio, and image quality表3 在量化大小、压缩比和图像质量方面，用OCQ和不同阈值的AB-OCQ算法处理带Alpha通道的半透明PNG图像时的比较

Table 4 Comparison between OCQ and AB-OCQ with different thresholds on 1 000 PNG images with different sizes表4 OCQ和不同阈值的AB-OCQ处理1 000幅不同尺寸的带Alpha通道的半透明PNG图像的比较

3.3 AB-OCQ算法和主流图片格式使用的压缩算法的对比

为了和主流图像格式使用的压缩算法进行对比，随机选择了1 000幅原始图像，其中有一半是带有Alpha通道的半透明图像。用Adobe Photoshop将这些图像转换为常见的JPEG和PNG格式，其中JPEG文件的核心算法使用的是离散余弦变换(DCT)，而PNG文件使用的主要是基于LZ77派生的字典压缩算法；同时也用AB-OCQ算法对原始图像进行处理。对于带Alpha通道的半透明图像，根据实验取阈值为0.2，其他图像根据实验取阈值为0.05，并把AB-OCQ处理后的数据直接保存为文件，然后和原始的像素矩阵、JPEG、PNG文件做对比，得到的结果如表5所示。

Table 5 Comparison of AB-OCQ algorithm and the algorithm used by JPEG, PNG files表5 AB-OCQ算法和JPEG，PNG文件使用的算法比较

从表5可以看出，在压缩比上，AB-OCQ算法和JPEG使用的DCT算法相比虽然不占优势，但好于PNG文件使用的LZ77派生算法；在图像质量上，AB-OCQ算法虽然比不上PNG文件使用的算法，但却优于JPEG文件使用的算法； AB-OCQ算法不仅能支持带Alpha通道的图像，更重要的，它还拥有着随机访问任意像素的特性，该特性是JPEG文件和PNG文件使用的压缩算法所没有的——DCT和LZ77派生算法都需要经过解码变成原始像素矩阵才能支持随机访问像素。因此，和JPEG、PNG文件所用的算法相比，AB-OCQ算法虽然不是在所有方面都是最优的，但却是综合性能最平衡的1个算法。

4 结束语

本文提出了一种改进的OCQ算法，即AB-OCQ算法。用OCQ和AB-OCQ算法进行了比较：在处理不带Alpha通道的图像时，尽管通过AB-OCQ算法获得的压缩比与OCQ算法的压缩比相当，但AB-OCQ算法图像质量比OCQ算法提高了很多;而在处理带Alpha通道的图像时，AB-OCQ算法不仅具有更好的图像质量，而且还具有更好的压缩比；和常见的主流图像格式所使用的压缩算法比较，AB-OCQ算法虽然不是在各方面都最优，但却是综合性能最平衡的1个算法。更为重要的是，通过AB-OCQ算法处理后的图像数据可直接随机访问图像上的像素，该特性是其他图像压缩算法如离散余弦变换、小波变换和字典压缩等方法所不具备的。因此，从这个特性出发，如果应用程序使用AB-OCQ算法对图像进行存储、绘制，就能在保证图像质量的前提下大大减少内存消耗。未来，将继续从这个特性出发做进一步研究。