基于矩形NAM和偏微分方程的灰度图像压缩方法

1、基于矩形NAM和偏微分方程的灰度图像压缩方法摘要：借助于矩形NAM图像表示和偏微分方程技术，提出一种新的灰度图像压缩方法。该方法在编码端把原始图像逆布局为若干的矩形子块，并采用坐标压缩的方法存储每个子块的位置、大小。在解码端，采用偏微分方程进行图像修复，有效地消除解码图像中的方块效应。该方法的时间复杂度为，其中为灰度图像的像素数。实验表明：在保持图像质量的前提下，本文给出的方法具有更高的压缩比和更少的块数，具有较高的实用价值。关键词：偏微分方程（PDE） 非对称逆布局模式表示模型（NAM） 图像压缩 Gray Image compression based on Rectangle NAM a

2、nd PDEAbstract: based on Rectangle NAM and PDE，a new compression method for gray image is proposed.On the encoder, the original image is segmented into a number of rectangular sub-block,and the method of coordinate compression is used for storaging location and size of sub-block.On the decoder,a PDE

3、 method is applied to reconstruct the image ,which is effective to reduce block-effect.The time complexity is,n is the number of Gray-scale image pixels. Experiments show that the proposed approach can reduce the number of rectangular sub-block and has a higher compression ratio on the premise of re

4、maining the image quality，which has a potential in application.Keywords: Partial Differential Equation（PDE）Non-Symmetry and Anti-Packing Pattern Representation Model（NAM）Image compression1引言图像的压缩方法很多，有效的图像压缩方法能够减少表示一幅图像所需要的存储空间并且可以提高图像处理的速度。图像压缩包含两个过程：其一是编码过程。其二是图像重构过程，即解码过程。如预测编码、变换编码、矢量量化、子带编码、小波变

5、换、分形编码和模型编码等，已经发展得很成熟，并制定了国际标准。但是目前流行的图像编码如JPEG、小波变换和分形编码等计算过于复杂，很多研究者提出基于分层数据结构的图像压缩方法，等1提出了一种基于S-树的图像压缩方法，简称STC方法。李宏贵、李兴国等2提出一种基于四叉树的灰度图像压缩方法，简称QTC方法。STC方法和QTC方法在重建图像质量上取得了满意的结果，并且在执行时间上是远远优于JPEG和分形计算。借助于QTC灰度图像压缩方法的思想，本文结合PDE的图像修复技术和矩形NAM的思想，从灰度图像的局部统计特征出发，用矩形子块取代QTC方法中的标准方块，提出了一种新的灰度图像压缩方法，简称为NA

6、MRP方法。2 基于矩形NAM和偏微分方程的灰度图像压缩方法2.1 矩形NAM的思想非对称逆布局模式表示模型3（Non-Symmetry and Anti-Packing Pattern Representation Model，NAM）是Packing问题的一个反问题，具体可以描述为：给定一个模式（容器）和N个预先定义的子模式（N个不同形状的物体），现在要从这个给定的模式（已经摆放好物体的容器）中抽出这些子模式（物体），用这些子模式的组合来表示给定的模式（已经布局好的容器）。矩形NAM4是一种基于矩形子模式的非对称逆布局模式表示模型。其基本思想是：给定一个已经布局好了的模式和一个预先定义的不

7、同形状的矩形子模式，然后从这个给定的模式中抽取这些矩形子模式，用这些矩形子模式的组合来表示给定的模式。2.2 灰度图像的NAMRP方法 为了减少矩形NAM编码的规模，首先把图像按照像素点划分为若干等大小且不相交叠的正方形的小图像块，称为原子块，原子块大小为，原子块的灰度值为该原子块所覆盖的4个像素的灰度平均值。这样就将一个大小为图像矩阵转化为大小为原子块矩阵，然后对于大小为原子块矩阵采用逆布局算法得到一系列矩形子块。下面给出矩形子块的定义。 定义2-1(矩形子块)：给定一个误差容许量，若一个矩形区域内，像素灰度的最大值和最小值之差小于，该区域称为一个矩形子块。设一幅大小为的图像矩阵为，其对应的

8、原子块矩阵为，有，使用NAMRP方法，可以把矩原子块阵分割为互不重叠的矩形子块，定义一个大小为的标签矩阵R，在R中用单独的标签来标记矩形子块的顶点类型。在R中，符号“1”和“2”分别用来标识矩形子块的左上角和右下角，符号“-1”仅用来表示一个孤立的原子块，其它元素为0。这些互不重叠的矩形子块具有如下特点：以光栅扫描的方式扫描R矩阵，每一个矩形的左上角和右下角顶点在列的方向上是最近的。所以，只要原始图像被分割后的矩形子块互不重叠，矩阵R就是可以解码的。以下分别给出NAMRP方法的编解码的具体步骤。NAMRP方法的编码步骤如下：/*给定一幅大小为的灰度图像和误差容许量,将编码结果存储到一个队列和坐

9、标表Q中。*/Step1：从图像矩阵，计算其原子块矩阵为，定义一个大小为的标签矩阵R，将R的所有元素初始化为0，同时将矩形子块的计数num初始化为0，清空队列和坐标表Q，将待编码图像全部设为未标记状态；Step2：对于图像的原子块矩阵，按照光栅扫描顺序从左至右，从上至下搜索下一个起始点（未标记点的原子块），再根据矩形子模式的匹配（逆布局）算法和误差容许量来追踪相应的矩形子块。Step3：根据矩形子块的面积，来确定一个面积最大的矩形子模式，确定该矩形子模式的终点，并将这个矩形子模式从中作标记，以便下一个子模式起点的寻找；Step4：根据矩形的起点和终点确定矩形子模式的类型，并在标签矩阵R中标记出

10、这个矩形子模式，同时进行如下操作：num=num+1，Snum=，S中存储矩形子块左上角的灰度值；Step5：重复Step2到Step4，直到没有新的起始点为止；Step6：根据2.3节介绍的坐标压缩方法，对R矩阵中所有非零元素的坐标进行编码，并将编码结果存储到一个坐标表Q中；Step67：形成编码数据流。编码数据由原始图像大小N、Q、S组成，Q是根据R矩阵得到二进制0、1序列。NQS在NAMRP方法中，编码后的数据量分为两部分，一部分是坐标压缩后的数据，另一部分是矩形子块左上角的灰度值，其数据量由矩形子块的个数决定。存储原始图像所需的比特数为：，存储矩形子块的灰度所需的比特数=，假设存储坐标

11、系Q所需要的比特数为，则压缩比为 NAMRP方法的解码步骤如下：/*给定一幅的灰度图像模式，一个坐标表Q，一个队列S，输出解码图像，并计算该重建图像的PSNR*/Step1：将一个大小为的灰度图像矩阵所有元素赋值为0，同时将矩形子模式计数变量num赋值为0；Step2：根据坐标表Q，解码出大小为的R矩阵；Step3：根据队列S，算出矩形子模式的总数sum；Step4：按照光栅顺序从左至右，从上至下遍历R矩阵，若搜寻到一个矩形子模式进行如下操作：num=num+1,根据Snum，将该矩形子模式中覆盖解码图像的所有像素都赋值为Snum，R矩阵中一个元素表示一个原子子块，表示中的四个像素点；Step

12、5：若num1）和时间间隔，并令k=0。（2）根据迭代公式计算。根据矩形子块左上角坐标集，用修正，即：。把修正后的作为下一个时刻的初始迭代图像矩阵；（3）重复步骤（2）直到N结束。2.5 NAMRP方法的复杂度对NAMRP方法的编码部分来说，编码所需要的时间取决于像素点的规模，正比于/4，其中为灰度图像的像素数，=（为灰度图像宽和高），表示图像中每个原子块被访问的次数，由于每次进行矩形逆布局计算，都要从行优先和列优先两种矩形去追踪局部最优的矩形，而且在每一次的逆布局计算中，前一次的运算结果可以直接为后一次所使用，故平均每个原子块被访问的次数为2，=2。所以编码部分的时间复杂度为。对NAMRP方

13、法的解码部分来说，解码所需要的时间比编码少得多，解码所需要的时间正比于k，k为进行PDE图像修复时的迭代次数，是一个常量。所以解码算法的时间复杂度为。在空间开销方面，整个NAMRP方法只增加为数不多的中间变量，因而其空间复杂度与图像的大小成正比，即。3实验结果分析选择图像处理领域中Lena、Girl图像作为典型的测试对象，如图2-1，图像大小均为，考察5种不同的误差容许量=5、10、15、20、25，表2-3给出了NAMRP方法和QTC方法的性能比较，这两种压缩方法的灰度图压缩性能用以下3个参数进行评价，即：子块的块数、压缩比以及图像的峰值信噪比PSNR。 (a ) Lena图像 (b) Gi

14、rl图像图2-1 实验测试图像表2-3中的、分别表示NAMRP方法相对于QTC方法在、PSNR上减少或者下降的程度，分别用如下的3个公式来进行计算：= =表2-3 NAMRP表示方法和QTC方法的性能比较Image%QTC NAMRPQTC NAMRPQTC NAMRPLena5 1015202514935 6314 12064 420110195 31798998 25497948 211957.5265.1768.8171.6773.334.3880 4.83335.4323 7.02276.4282 9.05567.2833 11.09468.2455 13.173010.1429.32

15、40.8752.3259.7528.5074 28.156428.4749 27.690628.1052 27.086127.5254 26.316227.0764 25.57821.234.263.624.395.53Girl51015202514689 582311875 35889580 25677882 19706571 161060.3569.7873.6375.0075.494.4615 5.19015.5188 8.03436.8409 10.95008.3146 14.06059.9735 17.119616.3345.5859.9469.1171.6531.7805 31.2

16、22931.7059 30.656431.5295 29.688230.5039 28.689629.8473 27.84291.753.315.845.946.71从表2-3中不难看出，在相同的误差容许量下，比如：当=10，对于Lena图像，NAMRP（QTC）的块数为4201（12064），NAMRP（QTC）的压缩比7.0227（5.4323），NAMRP（QTC）的峰值信噪比为27.6906（28.4749），显然NAMRP在块数和压缩比上是远远优于QTC的，块数减少了65.17%，压缩比增加29.32%，尽管图像的质量下降了4.26%。与QTC方法相比，在不同的误差容许（），尽管NA

17、MRP方法在重建图像的PSNR方面比QTC方法下降1.23%10.16%，但在压缩比方面比QTC方法增加了7.74%75.22%，块数上减少了54.75%77.44%。对于同一幅图像，越大，则越大，解码图像的PSNR越小，解码图像丢失的细节越多。这是因为一个子块中灰度差小于的细节都可能被丢失。对于不同的图像，当相同时，Girl的解码图像的压缩比和PSNR都要远远优于Lena的解码图像。这是因为Lena图像的细节比Girl图像的细节都要多，Lena图像的细节变化比Girl图像的细节变化要剧烈。图2-2给出分别取5、10、15和20时，NAMRP方法的解码图像。=5 =10 =15 =20 =5

18、=10 =15 =20 图2-2 解码图像4结论本文给出的NAMRP方法具有更高的压缩比和更少的块数，从而具有更快的处理速度，与目前流行的JPEG方法和小波变换方法相比，由于JPEG方法和小波变换方法要涉及到复杂度数学计算，故NAMRP方法具有计算简单、处理速度快等特点。所以NAMRP方法在降低图像存储空间、加快传输速度等方面具有良好的理论参考意义和实际应用价值。参考文献：1K.Chung,J.Wu.Improved image compression using S-tree and shading approach.IEEE Trancations on Communications,2000,48(5):748-7512李宏贵，李兴国，罗正发. 基于四叉树的灰度图压缩方法J.系统工程与电子技术，2004,26(7)3陈传波. 非对称逆布局模式表示方法研究: 博士学位论文. 武汉: 华中科技大学图书馆, 2005 4陈传波，