方块编码算法之改进

[摘要]利用传统方块编码算法编码压缩灰度图像，算法简单、失真率不大，却因为其方法比较固定而导致了其压缩比较小，伸缩度往往不大，在一些情况下不适合被利用来压缩图像。为了改变传统方块编码算法编码压缩灰度图像压缩比之不足，对传统方块编码算法作出改进以提高压缩比。实验证明在对一般图像进行方块编码的时候，改进以后所获得的算法有效。

[关键词]方块编码 编码 像素 图像 方块

中图分类号：TP3文献标识码：A文章编号：1671－7597（2009）0510034－02

一、引言

方块编码算法是一种传统的编码压缩算法，它简单、有效，失真率较小，其基本思想是将图像分成n×n的子块（通常是4×4的子块），并为每个子块设计两个电平量化器，量化门限和两个重建电平随子块局部统计特征而变化，量化后用一个n×n位的映像矩阵表示，这n×n位代表了有关各个像素的重建电平和确定两个重建电平的附加信息（分辨力分量）。译码时在各个像素点的映像位置选择一个合适的重建电平完成译码。

传统方块编码算法利用分辨力分量和两个重建电平来进行编码压缩，当子块的大小和原图像大小确定以后，压缩比就已经确定了，由于传统方块编码算法两个重建电平的编码没有充分考虑到相邻子块之间的关系和视觉冗余，因此其所需的编码就较多，方块编码所实现的压缩比也因此受到了限制，往往不大。

二、改进的方块编码算法

（一）传统方块编码算法的改进思路

使用传统方块编码算法编码时所选的方块区域的大小固定，利用固定的位数来记录重建电平和分辨力分量，丝毫没有考虑到相邻方块区域的联系，丝毫没有考虑到灰度值相差不多而且分布极其不均匀的现象，一切都导致了传统方块编码算法所实现的压缩比小而且固定，虽然我们不容易找到更好的记录方式来记录分辨力分量从而增大压缩比，但是如果能够充分考虑到相邻方块的相关性利用可变位数的方式记录重建电平使记录时使用的代码更少则必然可以提高压缩比。同时通过对经过传统方块编码算法编码压缩后的数据进行分析和研究，我们可以发现即使经过传统方块编码算法编码压缩以后图像数据依然存在一定程度的像素间冗余和心理视觉冗余，那么我们完全可以利用灰度值序列编码压缩灰度值信息，也可以使用相邻方块重建电平替代相应子块重建电平的方式来编码灰度值从而减少编码时所需要的数据量，只要失真率不大不至于影响视觉感受即可。

我们按照图1所示设A、B、C、D、E、F、G、H、I为一副图像中将要进行方块编码的相邻区域局部各子块，因为方块编码算法的子块往往不大（一般情况下小于4×4），其各子块之间的重建电平往往存在一定的相关性。则在很多情况下我们可以利用A、B、D三个子块的重建电平来推测E子块的重建电平，可以用A、B、D三个子块的重建电平来替代E子块的重建电平，同理其余子块的重建电平也可以用其周围的三个相邻子块的重建电平来替代。鉴于每个子块的编码要记录两个重建电平而且图像本身也有自身的规律，相应子块的重建电平可能与周围三个相邻子块的六个重建电平（每个子块都有两个重建电平）中的一个重建电平相关，也可能与这六个重建电平都不相关，另外对应子块的两个重建电平都要与周围三个子块的六个重建电平依次对比，并且按照灰度值高和灰度值低的顺序依次对子块的重建电平进行编码。考虑到在图像中普遍存在的像素间冗余和心理视觉冗余以及方块编码的特点，可以在编码端与解码端事前规定好一组灰度值序列，当编码端遇到重建电平的灰度值的时候如果不能利用相邻子块的重建电平替代则可以利用灰度序列中的值替代，解码时再在解码端解码灰度值即可。

使用灰度值序列编码灰度值的算法可以按照如下的思路进行：

假设通过图像获得的灰度值序列为COlOR,COLOR为一个256位的二进制数序列，每一位对应一个灰度值，例如第一位对应的灰度值为0，如果图像中存在灰度值为0的像素，则第一位编码为1否则编码为0；第二位对应的灰度值为1，如果存在灰度值为1的像素则该位编码为1否则为0，……以此类推。编码的时候不按照实际的灰度值进行编码而是按照灰度值在图像中存在像素的灰度值的位置进行编码，例如假设COLOR=000001111100000111110 0000111110000011111000001111100000111110000011111000001111100000111110000011111 000001111100000111110000011111000001111100000111110000011111000001111 10000011111000001111100000111110000011111000001111100000111110000011 1110000011111111111，灰度值为6则首先找到代表灰度值为6的数据位上的“1”是灰度值序列COLOR中的第几个“1”，因为是第2个“1”，所以该灰度值按照2进行编码。同理假设解码端获得的对应于灰度值的数据是6，则需要按照灰度值序列COLOR查找第6个“1”在灰度值序列COLOR中的相应位置，因为第6个“1”在第16个位置上，因此其实际灰度值是15。

在具体操作上，按照灰度值序列编码灰度值的编码算法可以按照如下方法进行操作：

1．首先获得灰度值序列；

2．根据灰度值找到灰度值在灰度值序列中的实际存在像素的相对位置；

3．按照灰度值在灰度值序列中的实际存在像素的相对位置编码灰度值。

在具体操作上，按照灰度值序列编码灰度值的解码算法可以按照如下方法进行操作：

1．首先获得灰度值序列；

2．按照灰度值在灰度值序列中的实际存在像素的相对位置找到相应的灰度值位置；

3．按照绝对的灰度值位置-1解码灰度值。

按照图像获得灰度值序列的方法要求在编码端与解码端之间有一个长达256位的编码头来表达图像中存在的灰度值。而使用相邻区域方块重建电平替代相应方块重建电平的方法编码重建电平以后再用灰度值序列替代的方法来记录灰度值所获得的压缩比往往不会大幅度提高却会提高解码算法的复杂度，因此利用灰度值序列编码灰度值的算法只是在一些特定情况下使用，本文主要探讨使用相邻方块重建电平替代的方式，灰度值序列编码只是作为补充和辅助。

因为改进的方块编码算法只是对记录方法进行了改进，同时即使应该记录的灰度值有了改变也是在灰度值相差不大的前提下进行的，其失真率实际上不大，也不至于影响视觉效果，所以传统方块编码算法原有的优点得以保留，同时由于减少了重建电平平均占有的位数则必然可以提高压缩比。

（二）改进的方块编码算法算法描述

改进的方块编码算法可以描述如下：

SC={Ci|i=0~n}

Ci=(Pi,Li)

Pi=(Ai,Bi,Ci,Di)

其中SC为某个数据流的所有编码集合，Ci为第i个编码，对应于图像中第i个子块的编码数据。Pi为表示第i个子块重建电平的数据，位宽根据实际的需要而定。Ai为表示图像中第i个子块的重建电平中灰度值较高的重建电平与第i个子块周围的三个子块的重建电平的替代关系，Bi为表示第i个子块的重建电平中灰度值较低的重建电平与第i个子块周围的三个子块的重建电平的替代关系，Ci为当第i个子块的重建电平中灰度值较高的重建电平不能从周围子块的重建电平推测时记录的灰度值较高的重建电平数据，Di为当第i个子块的重建电平中灰度值较低的重建电平不能从周围子块的重建电平推测时记录的灰度值较低的重建电平数据。每个Pi都有一个Ai 和一个Bi与之对应，当第i个子块的重建电平中灰度值较高的重建电平可以从周围子块的重建电平推测时没有Ci，当第i个子块的重建电平中灰度值较低的重建电平可以从周围子块的重建电平推测时没有Di。Li为表示第i个子块分辨力分量的数据，位宽固定。

在不考虑灰度级深度压缩和灰度值序列编码灰度值的编码过程中，记录改进方块编码算法的重建电平的数据量由表示替代的信息总量和不能替代时所需要记录的重建电平的数据总量决定，记录传统方块编码算法重建电平的数据量由实际记录重建电平的数据量决定，则设L改进为改进的方块编码算法记录重建电平所需要的总数据量，L传统为传统的方块编码算法记录重建电平所需要的总数据量，A改进和B改进为表示子块重建电平与周围子块重建电平关系的总数据量，C改进和D改进为表示无法通过相邻子块重建电平推测子块重建电平时所需要记录的数据量，C传统和D传统为传统方块编码算法记录重建电平的总数据量，则

L改进=A改进+B改进+C改进+D改进

L传统=C传统+D传统

鉴于方块编码算法记录分辨力分量的数据量是固定的，通过L改进和L传统的对比可以知道A改进+B改进>C传统+D传统-C改进-D改进时改进方块编码算法必然忧于传统方块编码算法。

（三）改进的方块编码算法的编码过程

对图像利用改进的方块编码算法进行编码与利用传统方块编码算法编码图像非常类似，区别主要是在重建电平的编码上，改进的方块编码可以事前约定采用的灰度值，需要参考各相邻子块的重建电平编码重建电平。设有将要进行改进的方块编码算法编码的二进制流SC，SC={Bi|i=0～n},SC为图像中各个像素点的数据集合，Bi对应于单个像素点的灰度值，SR={Wi,Ci,Di| i=0～n }/{Wi,Ci,Di,Ei| i=0～n },SR为一个子块进行改进的方块编码算法编码后获得的对应于单个子块的编码集合，Wi为对应子块的分辨力分量的数据，Ci为对应子块重建电平中灰度值高的重建电平与相邻子块重建电平的对比结果编码，Di为对应子块重建电平中灰度值低的重建电平与相邻子块重建电平的对比结果编码，Ei为对比不符时所需要记录的重建电平的编码，一个对应子块只对应SR中的一个元素。

改进的方块编码算法的编码过程如下：

1．按照传统方块编码算法的方式获得子块的两个重建电平和分辨力分量；

2．将非边缘子块的两个重建电平与其各紧邻子块的两个重建电平进行比较，并按照表1相邻方块区域重建电平关系表所表示的各种情况得出Ci、Di（以图1中的E块为例，具体请参考图1）；

3．如果对应于Ci或Di的编码为000即E子块的重建电平与各子块的重建电平均不相同则将需要编码的重建电平灰度值编码；

4．将Wi、Ci、Di（或者Wi、Ci、Di、Ei）进行编码，当需要对Ei进行编码的时候需要按照特定的编码方式编码Ei；

5．重复1～4；

6．最后添加000作为码流结束标志；

7．对二进制位流按照8位宽度进行切割，形成编码数据流。

（四）改进的方块编码算法的解码过程

对经过改进的方块编码算法编码压缩以后的数据进行解码，首先要解码重建电平和分辨力分量，然后按照子块对应的位置来进行解码，如果事前约定了灰度值序列还需要解码成真正的灰度值。

改进的方块编码算法的解码过程如下：

1．首先进行码流分解，获得SR、Wi、Ci、Di（或者SR、Wi、Ci、Di、Ei）；

2．根据Ci、Di（或Ci、Di、Ei）的值和表1求对应子块的两个重建电平，当需要使用Ei的时候需；

要按照特定的解码方法，结合Ci、Di的值和表1来获取两个重建电平；

3．按照对应的两个重建电平和Wi进行解码，得到解压图像对应子块各个像素点的灰度值；

4．重复进行1～3直到数据流结束。

三、编码试验

为了检验改进的方块编码算法的效果，对国际标准图LENA图基于4×4子块进行了试验，其压缩比为4.2（大于传统方块编码算法的压缩比4），其效果图像对比如图2改进的方块编码算法实验图所示：

四、结论

实验证明改进的方块编码算法所获得的压缩比大于传统方块编码算法所获得的压缩比，保留了传统方块编码算法的优点，算法简单、有效，失真率较小。

参考文献：

[1](美)Rafael C.Gonzalez和Richard E.Woods著，阮秋琦、阮宇智等译，数字图像处理（第二版）[M].北京:电子工业出版社，2002:15-18.

[2](美)David Salomon（编著），吴乐南等（译），数据压缩原理与应用[M].北京:电子工业出版社，2003:15-18.

[3]刘国强、钱建生、曹国清编著，多媒体图像技术及应用[M].北京:人民邮电出版社，2000:15-18.

[4]霍宏涛，数字图像处理[M].北京：北京理工大学出版社，2002:117.

作者简介：

王晓明，男，辽宁省锦州市人，硕士研究生，研究方向为图形图像。