基于GSOFM的分形图像压缩方法

1、基于 GSOFM 的分形图像压缩方法郭建威辽宁工程技术大学(125105E-mail :摘 要:本文针对分形图像压缩编码中编码时间长的特点, 给出了一种结合神经网络和多尺 度分析的分形编码方法。通过多尺度的逐次逼近和 KNN 网络自组织分类,可以极大地缩减 分形编码的时间。 这种新算法可通过高效的图像域分类算法来改善对图像扫描的速度, 减少 计算量,最终达到编码加速的目的。此外,本文在自组织特征映射网络(SOFM 基础上结 合灰关系分析, 使用一种新型网络 (GSOFM , 并作了计算机仿真实验。 实验仿真结果表明, 本文提出的方法与普通的全搜索方法相比, 可大大加速图像编码过程, 而压缩率和

2、图像质量 仅有微小变化。图像质量,压缩时间和压缩率这三个指标也优于 fisher 方法。关键词:图像压缩,分形,神经网络,自组织特征映射网络1. 引言图像压缩技术已经研究了几十年,并取得了一些成绩,但还有许多的不足值得我们进一 步探讨, 压缩速度和质量依然是图像压缩中的主要问题和主要矛盾。 为了在不损失或尽可能 少损失图像质量的前提下提高分形图像压缩的速度, 本文在基于分形理论的图像压缩算法基 础上,通过结合多尺度分析和神经网络的分形编码方法,以降低图像复杂度 1-3,利用 GSOFM 4充分发挥分形压缩的高压缩比性能和神经网络的提高压缩速度的性能,将分形中 遇到的某些近似相似的图像块归类,

3、以少数有代表性的图像小块来代替与其相似的, 减少分 形中的总计算次数,从而减少分形压缩的时间。在这个过程中,本文也使用了四叉树 5和多 尺度逼近 6-7的方法, 降低图像维数, 进一步减少计算负担, 大大提高分形方法的压缩速度。 在仿真实验中,我们用这种方法与全搜索方法及其 Fisher 方法 8相比较,对比这三种方法的 压缩图像时间, 所得图像的质量和压缩比。 此方法在速度上应该比全搜索方法 5有大的飞跃, 比 Fisher 方法也各个方面也应有一定优势。2. 一种基于神经网络的分形图像压缩的方法2.1神经网络和块图像编码自组织特征映射 SOFM(Selforganizing feature

4、 map9-11是一种无教师学习的神经网 络,其中,不同的神经元通过无监督学习 12过程匹配不同的输入信号模式(pattern 或模式 的分类。 自组织过程可视为从高维输入空间到低维空间的概率密度的映射, 该低维空间通常 是一维、二维或三维空间,相应于临近模式的输出节点是拓扑不变的。 SOFM 的目的是将输 入数据按照其相似性进行分类。本文中使用 KKN 网和 SOFM 在编码算法, 将图像分割成相同尺寸的像素块分别进行编 码。对于 256×256像素大小的图像,块的大小通常为 4×4, 8×8, 16×16和 32×32。在 SOFM 图像块

5、编码中,视每个块为一个高维输入模式(一个 8×8的块属于 R64,用 KNN 网的自 组织过程去映射各个图像类。采用 GSOFM 的映射特性将目标图像的图像类映射到一个低维神经元矩阵。 因为输入空 间(图像块的维数远大于输出空间(神经元空间的维数,用图像块的多尺度逼近来降低 向量空间的维数。自组织过程以后, KNN 网的神经元将会产生关联的权向量,其作为图像块的逼近或类的代表。 在编码过程中, 将图像块输入到输入层, 将具有最高响应的神经元在 输出空间中的位置作为该块的编码。这个编码与激活神经元的权向量结合,用于表示该块。2.2 GSOFM的学习算法GSOFM 的训练属于无人监督竞争

6、学习算法。Kohonen 神经网络包含一个输入层和一个通过权矩阵相联系的输出层,也叫 KNN 层。 这个输出层是竞争的,且通常是一维、二维或三维阵列。这里实用二维 KNN 层应用于图像 块编码算法。 图 1 SOFM的二维网络结构神经元 (和 是 KNN 网神经元的序列号可视为一个具有权矩阵 的简易处 理器,通过它可以把相似的输入神经元归类。 输入的图像块向量 (i 和 nm N m n nm w ij b j 为输入神经元序 列号,即图像块编号并行输入到所有神经元,并且每个神经元具有活跃因子:=Pk m,n i,j m,n k w k b u 12(1其中, P 是 的像素个数, k 为单个

7、输入结点的分量。当 i,j b k w k b m,n i,j 最小, 也就是 和 距离最近时, u 有极大值,为活跃因子。k b i,j k w m,n m,n 一般学习算法如下:1 用随机数初始化每个神经元的权值 w mn ,设置邻域半径为 NE (0,学习速率为 (0 (0<(0<1及总学习次数为 T2 将块 映射到输入层并获得每个神经元的活跃因子 ,即有极大值i,j b m,n u 3 有极大活跃因子选择胜出的神经元 j*4 定义输入模式分量 , , 2, 1(n k b nmk L =,和权值 间的灰关系系数 nmk w nmk 为 maxmax min +=nmk nm

8、k其中, 为输入块的序列号, 为其分量, m n , k 10(是判别系数,通常取 =0.5,并且nmk k M m N n p k w b =, , 2, 1, , 2, 1, , 2, 1min min min min L L Lnmk k M m N n p k w b =, , 2, 1, , 2, 1, , 2, 1max max max max L L L nmk k nmk w b =5 更改胜出的神经元及其临近神经元的权值如下:(*,(, , ( (, , 1, t NE j n m w b t w w t n m ij nmk t n m t nm 邻域 +=+更新学习速率

9、(t及邻域半径为 NE (t , (t是随次数 t 增加而减小的增益项, 它的值介 于 0和 1之间。/1( (0T t t =1(0(INTt/TNE NE(t=6 转向 2, 继续上述过程,直到 (t=0为止。2.3一种新的分形图像编码加速算法下面将阐述基于结合多尺度分析和 GSOFM 网络的逼近算法,以缩减分形编码的时间。 这种新算法可通过高效的图像域分类算法来改善最佳匹配的速度,进而加速编码过程。当采用四叉树方法进行图像分割时,可采用四种值域大小(例如 4×4, 8×8, 16×16,和 32×32,和定义域的大小(例如 8×8, 16

10、×16, 32×32和 64×64,这将导致一个高达 1024维的 KNN 输入空间,从而引起计算和存储问题。为了解决这个问题,用该块的 2j (j=0, -2 -4, -6, -8 尺度上的离散逼近使其大小降低到 4×4。例如,对于 8×8的值域块,我们采用该 块在 1/4尺度下的离散逼近;相应地对 16×16的定义域块,采用在 1/16尺度下的离散逼近, 等等。这里,假设 KNN 网的输入空间是 R16。结合多尺度分析和 KNN 网的分形图像编码的具体算法如下:1 对原始图像进行降采样来获得尺度 1/4 , 1/16, 1/64

11、和 1/256下的图像。 大小为 (b x , b y 像素的块在尺度 2j (j=0, -2 -4, -6, -8 下进行离散逼近,所获得的图像大小为 (2j b x , 2j b y 像素。这里最低尺度为 1/256.2 建立一个定义域池,用于训练 KNN 网。注意,用于训练 KNN 网的定义域池可从另 一个不同于将要编码的图像中获得。 这样只要通过学习得出分类权重, 便可以在不同图像上 进行分类,不必对每一幅图像分别进行学习。我们在尺度 2j (j=-2, -4, -6, -8 下使用大小为 4×4像素的图像块来训练 KNN. 这个过程可总结如下:a 在尺度 2j (j=-2,

12、-4, -6, -8 下选择每一个大小为 4×4像素的块。 例如, 对于 256×256的图像,在尺度 1/256下,块的数目是(16-4+1 ×(16-4+1 .b 将每个块 d i 进行规格化(min (max , ( , (' i i i i i d d d y x d y x d = (1 其中, i d 是定义域块 d i 的平均像素值, max(d i 和 min(d i 分别是 d i 的最大和最小像素值。c 产生每个规格化块 d i 的等距变换。定义域池中的块可重复出现。3 用在定义域池(即从步骤 2中获得的训练集中的规格化向量建立 KNN

13、 网的码本。 a 将 KNN 中的所有权值置成随机数。b 从定义域池中提取向量并用于训练 KNN 。c 重复 3中(b 步骤直到映射收敛。4 在编码图像的定义域池中的向量和 KNN 网中一个神经元间建立联系。 每一个神经元 保持一个最接近于在他们权中存储模式的关联向量序列, 每一个向量由定义域块和等距变换 操作指示产生。5 根据式 (1, 在较低尺度上通过活跃神经元 N kl , 在图像的定义域块和值域块间建立联 系。在这个尺度上,定义域块和值域块的大小为 4×4。a 在值域块和关联到活跃神经元 Nkl 的类中的块之间搜索最佳匹配 (满足误差限 E 。 如果类中的一个块匹配上了, 则

14、在较高尺度上, 采用相同的等距变换搜索这个块, 和它的右 邻块、下边邻块和右下方邻块(位置关系表明相邻的块具有相似的特性。重复本步骤直到 尺度 1。b 如果没有满足误差限 E 的匹配, 我们可搜索临近神经元 1(±=k m N mn ,关 联的类。1±=l n c 如果在临近神经元 N mn 关联的类中也没有满足误差限 E 的匹配,该值域块将被分解 成四个更小的同大小的块(采用四叉树分割,并对每个块进行编码(重复步骤 4和 5。d 如果找到达到最小品质标准要求的匹配,我们可对该块进行编码。e 重复 5(a到 5(d步骤,直到所有的块都编码为止。通过以上步骤,我们便完成了对数

15、字图像压缩的加速。应用这种方法,理论上是可以 在分形中减少寻找匹配块的次数,提高分形压缩的速度。我们在下面章节中将给出具体仿 真试验的结果,来证明此方法的有效性。3. 基于 GSOFM 分形编码方法仿真实验测试中采用大小为 8位 256×256像素的 LENNA 灰度图像。 从多个方面将该算法与无遗 漏最佳匹配搜索方法(全搜索法和 FISHER 方法进行比较:编码时间,压缩倍数和图像质 量(PSNR 。在本文提出的方法中,可使用四种值域块大小 (4 × 4, 8 × 8, 16× 16及 32 ×32 , 定义域块大小可采用 ( 8×

16、8, 16×16, 32×3及 64×64。 编码实现在 2000 MHz 的 Pentium 4处理器上进行。 KNN 的输入空间是 R16.PSNR 是两个大小为 m×n的图像 f 和 g 之间的失 真程度的度量,定义如下:×=MSE PSNR 225510log10 (2式中, n m j i g j i f MSE n j m i ×=10102, ( , (压缩倍数:压缩后图像数据大小 /原始图像数据大小。在对图像存储时,要对编码信息进行量化后再存储,这样可以减小文件的存储空间。 量化时,对于一个值域块的编码信息中的匹配块位

17、置坐标(x , y 使用 8位,对比度 使用 5s位,亮度 o 使用 6位进行存储, 3位存储旋转变换种类, 2位存储层次信息。如果一个图像 在编码后值域块的编码信息的数目为 ,则它所在的存储空间为:n8/ 236582(+××n 字节3.1 与无遗漏最佳匹配搜索方法的进行比较与无遗漏最佳匹配搜索方法对比结果如表 3-1所示。实验结果表明,本文提出的 方法可在很大程度上提高图像压缩速度,加速效果十分明显。表 3-1 比对表图像 方法 PSNR 时间(秒 压缩倍数全搜索方法 35.26 8600 8.16Lenna本文方法 35.10 17 8.07在图 3-1(a和 3-1

18、(b中,我们可以清楚的看出按照本文算法压缩后的图像与原始图像的 对比,效果还是可以让人满意的。 图 3-1(a 本文方法压缩的 Lenna 图像 图 3-1(b 原始的 Lenna 图像3.2 与 fisher 方法进行比较与 Fisher 方法对比如表 3-2所示。这组实验结果表明,本文提出的方法在图像质量,压 缩时间和压缩倍数这三个指标上均优于 fisher 方法的。表 3-2 比对表图像 方法 PSNR 时间(秒 压缩倍数Fisher 方法 34.41 58 7.97Lenna本文算法 34.66 17 8.07与 Fisher 方法压缩的图像 3-2(b相比,本文提到的压缩方法得到 L

19、enna 图像 3-2(a更加 细致, 压缩比率更高, 而且压缩时间缩短 3倍以上。 可见基于 GSOFM 网络的分形压缩方法 要比 Fisher 的分形压缩方法更好。 图 3-2（a）本文方法压缩的 Lenna 图像 图 3-2（b）Fisher 方法压缩的 Lenna 图像 4. 结论 本文提出一种结合神经网络和多尺度逼近的图像压缩方法。 凭借自组织神经网络的分类 功能，将组成图像的不同类型像素小块分类，结合多尺度逼近降低图像复杂度，进而减少分 形过程中选择匹配块过程中的总计算次数，缩短总的压缩时间。 在自组织神经网络 SOFM 的权值调整中，仅考虑了学习率及输入模式与获胜神经元及 其邻域

20、， 而忽略了输入模式分量与全体参与竞争的神经元权值向量间的某种相关关系。 因此， 本文将灰关系系数（Generalized Grey Relation Coefficient）引入自组织神经网络，形成新的 分类网络 GSOFM，从而能够更好的完成分类工作。 在实验仿真中，分别用本文提出的方法与无遗漏最佳匹配搜索方法（全搜索方法）以及 Fisher 方法对同一图像进行编码和解码实验，在压缩时间、压缩倍数和图像质量上进行了对 比。 通过 Lenna 图像的仿真结果显示， 本文提出的方法在压缩速度方面比无遗漏最佳匹配搜 索方法提高 500 倍以上， 而且在图像质量和压缩倍数方面相差很小。 与经典的

21、Fisher 方法相 比，此方法在编码时间，压缩率和图像质量这三项上，也不同程度的优于 Fisher 方法。 -6- 参考文献 1 Mas Ribés Joan Maria, Simon Benoît, Macq Benoit, “Combined Kohonen neural networks and discrete cosine transform method for iterated transformation theory”C, Signal Processing: Image Communication vol.16, pp.643-656, 2001. 2

22、 Bogdan, H.E. Meadows, Kohonen neural network for image coding based on iteration transformation theoryC, in Proc. SPIE Neural. Stochastic Methods Image Signal Processing, vol. 1766, 1992, pp. 425436. 3 J. Stark, Iterated function systems as neural networksJ, Neural Networks , vol.4, pp.679-690, 199

23、1. 4 Ming-Feng Yeh, Kuang-Chiung Chang, GraySOFM networkfor solving classification problemsJ, Neurocomputing 67 (2005. pp281287. 5 SaupeD. Accelerating fractal image compression by multi-dimensional nearest neighbor search A. Data Compression Conference, 1995.222-231. 6 H. Lin and A. N. Venetsanopou

24、los, A pyramid algorithm for fast fractal image compressionC, ICIP-95 IEEE Int. Conf. Image Processing, vol. 3. pp. 596599, Washington, DC, Oct. 1995. 7 F. M. Dekking, An Inequality for Pairs of martingales and Its Applications to fractal Image CodingZ, technical Report 95-10 Faculfy of Technicals a

25、nd Informatics Delft university of Technology, 1995. 8 Fisher, Y., Fractal image compression: theory and applicationsM, Springer-Verlag, 1994. 9 杜世培.分形图像压缩方法的改进与实现J.贵州工业大学学报,2000,29(4:5659. 10 张颖,余英林.一种基于去均值的加速收敛的分形压缩算法J.中国图像图形学报，1998,3(4:285289. 11 蔡芳.快速分形图像压缩算法J.西北工业大学学报.1999,17(3:355-359. 12 郭嗣琮,

26、陈刚编著.信息科学种的软计算方法M.沈阳.东北大学出版社,2001. Image Compression Method Of Fractal Based On Gsofm Network Guo Jianwei LiaoNing Technical University (125105 Abstract In this paper, we proposed a method which incorporated multi-scale analysis into neural nets to solve problem that fractal coding allows fast decoding but suffers from long encoding times. This method can reduce the computational load of fractal im