全相位沃尔什双正交变换及其对JPEG的改进方法

摘要

全相位沃尔什双正交变换及其对JPEG的改进方法。本发明将二维全相位沃尔什双正交变换定义为[F]＝[V][f][VT]，反变换定义为[f]＝[V－1][F][(V－1) T]，其中[V]是全相位沃尔什双正交变换矩阵。改进方法是：输入原始图像及比特率；分成8×8像素块，分别进行全相位沃尔什双正交变换；根据比特率确定量化间隔，对变换系数进行均一量化；直流系数(DC)的预测编码和交流系数(AC)的“之”字形(Zig－Zag)扫描、可变长编码；哈夫曼(Huffman)熵编码；输出压缩图像的比特序列。在接收端，经过哈夫曼(Huffman)熵解码、直流系数(DC)和交流系数(AC)可变长解码、反量化后，再进行反全相位沃尔什双正交变换得到重建图像。本发明对变换系数进行均一量化，去掉了量化表，节省了内存，简化了计算，提高了编解码速度，大大缩短了运算时间。

说明书

【技术领域】：本发明属于计算机图像处理技术领域。

【背景技术】：目前，多媒体和互联网的发展要求采用合适的方法对图像进行压缩编码，以便于图像的存储和传输。JPEG是静止图像压缩的国际标准(见文献ISO/IEC10918-1|ITU-T Rec.T.81，Digital compression and coding of continuous-tone stillimages)。JPEG图像压缩编码算法的主要步骤为：图像的8×8方块化、二维离散余弦变换(Discrete Cosine Transform，DCT)、根据量化表量化、“之”字形(Zig-Zag)扫描游程编码、哈夫曼(Huffman)熵编码等。接收端解压缩是编码的逆过程，经过反量化和反DCT变换，得到重建图像。8×8像块[f]的二维DCT变换公式为[F]＝[C][f][C^T]，其中，[C]为8×8的DCT变换矩阵，[C^T]为[C]的转置。DCT变换是正交变换，[C]的转置即为[C]的逆，即[C^T]＝[C^-1]。因此，由[f]＝[C^T][F][C]重建图像。[C]的行向量是分解基矢量，[C^T]的列向量是合成基矢量，DCT变换和反变换中的分解基矢量和合成基矢量是相同的。

JPEG中采用DCT变换是因为DCT的基矢量接近理想正交变换(K-L变换)的基矢量。然而我们发现，对于图像压缩编码来说，正交变换并不是最优的选择。其缺点之一是量化表比较复杂，对不同的DCT系数采用不同的量化间隔，量化特别是改变压缩率时的量化需要较复杂的计算，量化表也需要占一定的内存空间。

【发明内容】：本发明的目的是解决现有技术中需要量化表，且量化表复杂，需要进行大量计算的问题，提供一种全相位沃尔什双正交变换法，及采用该变换对JPEG存储和传输的改进方法。

该方法最大的优点是无需量化表，对变换系数进行均一量化，从而可大大缩短运算时间，硬件实现也比较简单，并且能达到与DCT变换基本相同的图像压缩效果。

本发明提供的全相位沃尔什双正交变换法，是将二维全相位沃尔什双正交变换定义为[F]＝[V][f][V^T]，反变换定义为[f]＝[V^-1][F][(V^-1)^T]，其中[V]是全相位沃尔什双正交变换矩阵。

本发明定义的全相位沃尔什双正交变换矩阵[V]是由沃尔什正交变换矩阵用如下的迭代公式得到的：

$>>>V>m>>>(>j>,>l>)>>=>>\Sigma >>i>=>0>>>7>->j>\; >>>V>>m>->1>>>>->1>\; >>(>i>+>j>,>l>)>>>V>>m>->1>>>>(>l>,>i>)>>->->->>(>1>)>>>s>$

[V]＝[V_m]                                    (2)

其中，m为自然数，[V₀]为沃尔什正交变换矩阵：

$>>[>>V>0>>]>=>>1>>8>>>\begin{array}{}>>1>>1>>1>>1>>1>>1>>1>>1>\; >>1>>1>>1>>1>>->1>>->1>>->1>>->1>\; >>1>>1>>->1>>->1>>->1>>->1>>1>>1>\; >>1>>1>>->1>>->1>>1>>1>>->1>>->1>\; >>1>>->1>>->1>>1>>1>>->1>>->1>>1>\; >>1>>->1>>->1>>1>>->1>>1>>->1>>1>\; >>1>>->1>>1>>->1>>->1>>1>>->1>>1>\; >>1>>->1>>1>>->1>>1>>->1>>1>>->1>\; >\; >.>>s>\end{array}$

本发明用公式(1)迭代5次后得到的[V₅]作为全相位沃尔什双正交变换矩阵[V]，即m取5，则：

$>>[>V>]>=>[>>V>5>>]>=>>1>8>>\begin{array}{}>>8.0000>>8.0000>>8.0000>>8.0000>>8.0000>>8>.>0000>>8>.>0000>>8.0000>\; >>7.0000>>5.1833>>3>.>6220>>2.0186>>0.7104>>->4.8184>>->4.5786>>->9.1372>\; >>6>.>0000>>2.4593>>->0.9738>>->4.5986>>->6.2573>>->3.1366>>->2.0455>>8.5525>\; >>5.0000>>->1.0781>>->4.1499>>->3.4166>>->0.9594>>4.8113>>6.1078>>->6.3152>\; >>4>.>0000>>->1.8218>>->3.9411>>->0.3862>>4.2072>>0.2307>>->5.3196>>3.0309>\; >>3.0000>>->3.3642>>->1.1966>>2.2302>>0.4331>>->3.5140>>3.5731>>->1.1616>\; >>2.0000>>->3.1933>>0.9833>>1.7602>>->2.6011>>2.1770>>->1.3342>>0.2080>\; >>1.0000>>->2.2280>>1.8363>>->1.3542>>1.0357>>->0.3971>>->0.0758>>0.1831>\; >\; >.>>s>\end{array}$

一种采用上述全相位沃尔什双正交变换法对JPEG存储和传输的改进方法是，用全相位沃尔什双正交变换代替二维离散余弦变换，对所有变换系数采用均一量化，具体过程如下：

——输入原始图像及比特率；

——分成8×8像素块，分别进行全相位沃尔什双正交变换；

——根据比特率确定量化间隔，对变换系数进行均一量化；

——直流系数(DC)的预测编码和交流系数(AC)的“之”字形(Zig-Zag)扫描、可变长编码；

——哈夫曼(Huffman)熵编码；

——输出压缩图像的比特序列。

对JPEG存储和传输的改进方法，其接收端解压缩过程如下：

——接收输入的经变换后的压缩图像比特序列；

——哈夫曼(Huffman)熵解码；

——对直流系数(DC)和交流系数(AC)可变长解码；

——反量化；

——反全相位沃尔什双正交变换；

——得到重建图像。

本发明的优点和积极效果：1、本发明基于全相位数字滤波理论和传统的沃尔什正交变换提出了一种新型变换即全相位沃尔什双正交变换，并将其成功应用于图像压缩领域。2、全相位沃尔什双正交变换矩阵[V]与DCT正交变换矩阵[C]的相似之处是基矢量的列率随行序号的增加而增加，不同之处是[C]的各个基矢量是等模的，而[V]的基矢量的模随列率的增高而衰减。这就使得全相位沃尔什双正交变换系数具有高频衰减的性质。当对各变换系数采用均一的量化间隔量化时，就相当于DCT变换低频系数细量化、高频系数粗量化的效果。因此可以去掉基于DCT变换的JPEG算法中的复杂的量化表。3、本发明对JPEG的改进之处是，用全相位沃尔什双正交变换代替DCT变换，对所有变换系数采用均一量化。图像压缩编码的其他部分与JPEG相同。在接收端，经过哈夫曼(Huffman)熵解码、直流系数(DC)和交流系数(AC)可变长解码、反量化后，再进行反全相位沃尔什双正交变换得到重建图像。本发明提出的改进JPEG方法与标准JPEG方法相比的最大优点是，对变换系数进行均一量化，去掉了量化表，节省了内存，简化了计算，提高了编解码速度，从而可大大缩短运算时间，硬件实现也比较简单，并且能达到与DCT变换基本相同的图像压缩效果。比如，在Celeron(R)CPU 2.80GHz、256M内存计算机环境下，在编码时间上，对九幅512×512大小的图像，在标准压缩率下，全相位沃尔什双正交变换方案比DCT方案平均少用2.3924秒；对一幅512×512大小的图像，在不同的压缩率下，全相位沃尔什双正交变换方案比DCT方案平均少用2.8072秒。在内存使用上，因为DCT方案需要存储复杂的量化表，存储量化表所用内存为全相位沃尔什双正交变换方案的64倍。当调整编码比特率时，因DCT方案需要计算量化矩阵而要做大量的乘法运算，这一计算量大约为全相位沃尔什双正交变换方案的64倍。

【附图说明】：

图1是两种变换和量化方案下图像“announcer”的率失真曲线；

图2是用本发明方法对图像进行压缩与重建的方框图。

【具体实施方式】：

实施例1

本发明定义的全相位沃尔什双正交变换矩阵[V]是由沃尔什正交变换矩阵用如下的迭代公式得到的：

$>>>V>m>>>(>j>,>l>)>>=>>\Sigma >>i>=>0>>>7>->j>\; >>>V>>m>->1>>>>->1>\; >>(>i>+>j>,>l>)>>>V>>m>->1>>>>(>l>,>i>)>>->->->>(>1>)>>>s>$

[V]＝[V_m]                                      (2)

其中，m为自然数，[V₀]为沃尔什正交变换矩阵：

$>>[>>V>0>>]>=>>1>>8>>>\begin{array}{}>>1>>1>>1>>1>>1>>1>>1>>1>\; >>1>>1>>1>>1>>->1>>->1>>->1>>->1>\; >>1>>1>>->1>>->1>>->1>>->1>>1>>1>\; >>1>>1>>->1>>->1>>1>>1>>->1>>->1>\; >>1>>->1>>->1>>1>>1>>->1>>->1>>1>\; >>1>>->1>>->1>>1>>->1>>1>>1>>->1>\; >>1>>->1>>1>>->1>>->1>>1>>->1>>1>\; >>1>>->1>>1>>->1>>1>>->1>>1>>->1>\; >\; >>s>\end{array}$

本发明用公式(1)迭代5次后得到的[V₅]作为全相位沃尔什双正交变换矩阵[V]，即m取5，则：

$>>[>V>]>=>[>>V>5>>]>=>>1>8>>\begin{array}{}>>8.0000>>8.0000>>8.0000>>8.0000>>8.0000>>8.0000>>8.0000>>8.0000>\; >>7.0000>>5.1833>>3.6220>>2.0186>>0.7104>>->4.8184>>->4.5786>>->9.1372>\; >>6>.>0000>>2.4593>>->0.9738>>->4.5986>>->6.2573>>->3.1366>>->2.0455>>8.5525>\; >>5>.>0000>>->1.0781>>->4.1499>>->3.4166>>->0.9594>>4.8113>>6.1078>>->6.3152>\; >>4.0000>>->1.8218>>->3.9411>>->0.3862>>4.2072>>0.2307>>->5.3196>>3.0309>\; >>3.0000>>->3.3642>>->1.1966>>2.2302>>0.4331>>->3.5140>>3.5731>>->101616>\; >>2.0000>>->3.1933>>0.9833>>1.7602>>->2.6011>>2.1770>>->1.3342>>0.2080>\; >>1.0000>>->2.2280>>1.8363>>->1.3542>>1.0357>>->0.3971>>->0.0758>>0.1831>\; >\; >.>>s>\end{array}$

全相位沃尔什双正交变换矩阵[V]与DCT正交变换矩阵[C]的相似之处是基矢量的列率随行序号的增加而增加，不同之处是[C]的各个基矢量是等模的，而[V]的基矢量的模随列率的增高而衰减。这就使得全相位沃尔什双正交变换系数具有高频衰减的性质。当对各变换系数采用均一的量化间隔量化时，就相当于DCT变换低频系数细量化、高频系数粗量化的效果。因此可以去掉基于DCT变换的JPEG算法中的复杂的量化表。

实施例2

在本发明中，区别现有技术的必要技术特征是：首先提出了一种新型变换即全相位沃尔什双正交变换，并且用全相位沃尔什双正交变换代替JPEG压缩算法中的DCT变换，应用于图像压缩。本发明基于软件实现。

如图2所示，首先，输入原始图像和比特率，把图像分成8×8的像素块，分块进行全相位沃尔什双正交变换，根据输入比特率选定量化间隔，将变换系数进行均一量化，再对直流系数(DC)进行预测编码，对交流系数(AC)进行“之”字形(Zig-Zag)扫描和可变长编码，然后根据标准的哈夫曼(Huffman)码表进行熵编码，输出压缩图像的比特序列，实现了图像压缩。在接收端，经过哈夫曼(Huffman)熵解码、直流系数(DC)和交流系数(AC)可变长解码、反量化后，再进行反全相位沃尔什双正交变换得到重建图像。

需要注意的是，在图2的程序流程图中，进行哈夫曼(Huffman)编码时，对于直流系数(DC)，因为是对相邻图像块之间的差值进行编码的，所以在量化后扫描之前要先对直流系数(DC)进行预处理。将量化后直流系数(DC)的原始值替换成相邻图像块之间的差值。在对交流系数(AC)进行编码时，又要考虑63个系数全是零和连续出现16个连零这两种特殊情况等等。

本发明对JPEG的改进之处是，用全相位沃尔什双正交变换代替DCT变换，对所有变换系数采用均一量化。图像压缩编码的其他部分与JPEG相同。

在Matlab 6.5环境下对本发明提出的技术方案进行了计算机仿真实验。实验得到以下结论：

1.当采用均一量化时，用[V₅]作为全相位沃尔什双正交变换矩阵可以达到比其他[V_m]更好的图像压缩效果。

2.采用全相位沃尔什双正交变换、均一量化间隔取为60时的图像压缩率和重建图像信噪比指标，与采用DCT变换、用JPEG标准中的量化表进行量化时的指标近似。但全相位沃尔什双正交变换方案所用编码时间比DCT方案少。

3.在其他编码比特率下，本发明提出的技术方案与标准JPEG方案在重建图像的主观效果和峰值信噪比方面也大致相同。但全相位沃尔什双正交变换方案所用编码时间比DCT方案少。

表1给出了对512×512的九幅图像采用DCT变换、用JPEG标准中的量化表进行量化和采用全相位沃尔什双正交变换、均一量化间隔取为60进行图像编码和重建的实验结果。表1标准压缩率下两种方案性能比较

  测试图像      DCT  编码  比特  率  (bpp)  DCT  压缩比     DCT  编码时  间(s)    DCT  PSNR  (db)    全相位沃  尔什双正  交变换编  码比特率  (bpp)  全相位  沃尔什  双正交  变换  压缩比  全相位沃  尔什双正  交变换编  码时间(s)   全相位沃  尔什双正  交变换  PSNR  (db)  1.lena  0.6251  12.7973  43.5470  35.8050  0.6399  12.5014  40.7190  35.3745  2.mill  1.1984  6.6757  55.4380  29.7873  1.2890  6.2065  54.4690  29.8913  3.bridge  1.2403  6.4499  55.6250  29.5394  1.3348  5.9934  55.0940  29.5454  4.announcer  0.5029  15.9082  41.4530  38.2685  0.4972  16.0916  38.7500  38.0069  5.mandrill  1.3756  5.8157  57.5620  28.2313  1.4796  5.4070  56.5620  28.4004  6.einstein  0.6188  12.9276  44.4530  36.8386  0.6015  13.2994  40.4220  36.2204  7.model  0.4198  19.0555  39.9680  40.6479  0.4159  19.2336  37.3590  40.1664  8.milkdrop  0.4922  16.2530  41.2500  38.0828  0.4871  16.4244  37.7970  37.7871  9.cablecar  0.7408  10.7989  45.4220  36.5154  0.7277  10.9940  42.5310  35.9386

表2给出了对图像“announcer”，这两种变换和量化方案在不同的压缩比、编码比特率和重建图像峰值信噪比下的实验结果。

                  表2 不同压缩率下两种方案性能比较

  DCT  量化矩  阵Q  倍乘    DCT  比特率  (bpp)     DCT  压缩比      DCT  编码时间  (s)     DCT  PSNR  (db)     全相位  沃尔什  双正交  变换量  化间隔  Q  全相位  沃尔什  双正交  变换  比特率  (bpp)  全相位  沃尔什  双正交  变换  压缩比   全相位  沃尔什  双正交  变换  编码时  间(s)  全相位  沃尔什  双正交  变换  PSNR  (db)  Q*8  0.1724  46.4002  36.0930  29.4499  600  0.1623  49.2937  33.0470  29.4567  Q*5  0.2113  37.8684  36.5940  31.7091  300  0.2093  38.2141  33.6100  32.2414  Q*2.5  0.2970  26.9318  37.6100  34.7716  150  0.2947  27.1430  34.9530  34.9329  Q*2  0.3378  23.6819  38.2970  35.6659  120  0.3318  24.1102  35.7500  35.7336  Q*1.5  0.3960  20.2034  39.1720  36.8419  90  0.3898  20.5217  36.7350  36.7030  Q*1  0.5029  15.9082  41.4530  38.2685  60  0.4972  16.0916  38.7500  38.0069  Q*0.5  0.7887  10.1434  45.9380  40.5094  30  0.7887  10.1429  42.8750  40.2188  Q*0.35  0.9915  8.0689  49.3130  41.7222  20  1.0422  7.6762  46.4530  41.7238  Q*0.24  1.2448  6.4268  53.6090  43.0437  15  1.2687  6.3058  50.6410  42.8003

由表1和表2可以看出，二者的压缩效果基本相同。但全相位沃尔什双正交变换方案与DCT方案相比，对九幅512×512大小的图像，在标准压缩率下，全相位沃尔什双正交变换方案的编码时间平均少用2.3924秒；对一幅512×512大小的图像，在不同的压缩率下，全相位沃尔什双正交变换方案的编码时间平均少用2.8072秒。由表2数据绘制的两种变换和量化方案下图像“announcer”的率失真曲线如图1所示。

由图1可以看出，在编码比特率比较小时，本发明提出的改进JPEG方法优于标准JPEG方法。而在编码比特率比较大时，改进的JPEG方法效果略差一些，但二者基本接近。

本发明提出的改进JPEG方法与标准JPEG方法相比的最大优点是，去掉了量化表，节省了内存，简化了计算，提高了编解码速度。