用于图像压缩的提升结构二维离散小波变换交织扫描方法

摘要

该发明涉及用于图像压缩的提升结构二维离散小波变换交织扫描方法，特别是应用于符合联合图像专家组（JPEG）2000图像压缩标准的、具有高效率低存储特点的、基于5/3提升结构的二维离散小波变换交织扫描方法。该发明突破了传统的光栅扫描方法所采用的先行后列的数据读入方式，按照行列交织扫描方法读入图像数据，使得5/3提升结构离散小波变换过程中处理，水平方向一维离散小波变换输出的低频系数无需存储，仅需缓存

说明书

技术领域

本发明涉及用于图像压缩的提升结构二维离散小波变换交织扫描方法，特别是应用于符合联合图像专家组(JPEG)2000图像压缩标准的、低内存消耗的，基于5/3提升结构的二维离散小波变换交织扫描方法。 

背景技术

目前国际最新的图像压缩标准JPEG2000（参考文献[1]）具备帧内编码、压缩效果好、支持感兴趣区域编码和渐进式传输等品质，因而在高端数字图像应用中得到了推广。在图像压缩过程中，首先采用提升结构二维离散小波变换（DWT）原始图像，之后采用位平面编码器（BPC)处理小波系数子带生成上下文和码值(CX/D)，再送入算术编码器(AC)进行压缩编码。现有的DWT已经能够满足图像编码器的实时处理要求。但随着各类高清数字图像的应用普及，所消耗的内部存储器急剧增高。如何降低DWT在计算过程中所消耗的内部存储器已经成了该领域研究热点之一。 

提升结构离散小波变换由Mallat提出，极大减小了离散小波变换的计算复杂度。JPEG2000采用的提升结构二维离散小波变换有两种，一种是9/7提升结构离散小波变换，另一种是5/3提升结构离散小波变换。无损图像压缩采用基于5/3提升结构离散小波变换，即按照光栅扫描方法，自左向右自上而下的读入图像数据进行水平方向的一维离散小波变换，即用公式1计算高频系数，用公式2计算低频系数，公式中X(m, n)表示一副 行列图像中第m行第n列像素，表示水平方向一维离散小波变换后生成的第m行第n列个高频系数，表示第m行第n列个高频系数；用公式3和公式4对高频系数进行垂直方向一维离散小波变换，产生甚高频系数和高低频系数；用公式5和公式6对低频系数进行垂直方向一维离散小波变换，生成低高频系数、甚低频系数。 

                 公式1 

                  公式2

               公式3

              公式4

      公式5

                公式6

提升结构二维离散小波变换的实质是采用光栅扫描方法读入图像数据，先进行水平方向一维小波离散变换，后进行垂直方向一维离散小波变换。在进行垂直方向一维离散小波变换之前，需要存储水平方向一维离散小波变换所生成的所有H(m, n)和L(m, n)。对于N行N列的图像，其完成5/3提升结构二维离散小波变换需要内部存储器Trans_Mem为:

                            公式7

根据公式7，随着高清高分辨率数字图像的广泛应用，5/3提升结构二维离散小波变换所需的内部存储器会随之急剧增高。如何降低5/3提升结构离散小波变换的内部存储器成为该领域的研究热点之一。

具有代表性的研究成果有：参考文献[2]提出了一种对称折叠流水线方法；参考文献[3]提出了一种双模结构，通过复用5/3提升结构离散小波变换与9/7提升结构离散小波变换来提高转换速率；参考文献[4]提出了递归金字塔结构；参考文献[5]采用了多相分解及系数折叠方法；等等。 

传统方法通过改进电路结构来降低内部存储器，但由于依然按照光栅扫描方法读入图像数据，本质上依旧是先进行水平方向的行变换，后进行垂直方向的列变换。所消耗的内部存储器并没有显著降低。传统方法对行列图像进行5/3提升结构离散小波变换时，所消耗的内部存储器最小为，最多为。 

参考文献： 

[1] JPEG2000 Part 1: Final Draft, document ISO/IEC JTCI/SC29/WGI N1855.doc, International Standard (ISO/IEC FDISF DIS15444-1), Aug.2000.

[2] K. Andra, C. Chakrabarti, and T. Acharya, “A VLSI architecture for lifting-based forward and inverse wavelet transform,” IEEE Trans. on Signal Processing, vol. 50, no.4, pp. 966-977, 2002.

[3] G.-C Jung and S.-M. Park, “VLSI implement of lifting wavelet transform of JPEG2000 with efficient RPA (recursive pyramid algorithm) realization,”  IEICE Trans. on Fundamentals, vol. E88-A, no. 12, pp. 3508-3515, 2005.

[4] C.-T. Huang, P.-C. Tseng, and L.-G. Chen, “Efficient VLSI architecture of lifting-based discrete wavelet transform by systematic design method,” IEEE Int. Symposium Circuits and Systems, vol. 5, pp. 26-29, 2002.

[5] P.-C. Wu and L.-G. Chen, “An efficient architecture for two-dimensional discrete wavelet transform,” IEEE Trans. on Circuits and Systems for Video Technology, vol. 11, no.4, pp. 536-545, 2001.

[5] P.-Y. Chen, “VLSI implementation of discrete wavelet transform using the 5/3 filter,” IEICE Trans. on Information and Systems,vol. E85-D, no.12, pp. 1893-1897, 2002.

发明内容

技术问题：本发明的目的是提供一种用于图像压缩的提升结构二维离散小波变换交织扫描方法，该方法按照行列交织的顺序读入图像数据，同时进行水平方向和垂直方向的5/3提升结构一维离散小波变换，从而完成整幅图像的5/3提升结构二维离散小波变换。本发明在变换过程中，水平方向一维离散小波变换后输出的低频系数无需存储，仅需缓存N个高频系数，便可同时进行垂直方向一维离散小波变换，输出四个频率子带的小波系数。相对于传统最优的设计方案，消耗的内部存储器降低了50％。 

技术方案：本发明的用于图像压缩的提升结构二维离散小波变换交织扫描方法，按照行列交织的顺序读入N行N列图像数据，同时进行水平方向和垂直方向的5/3提升结构一维离散小波变换，其处理完成N行N列大小的图像仅需N个存储单元，其中N是自然数。下面，用5/3提升结构离散小波变换交织扫描方法对N行N列图像进行变换实例来阐明本发明的技术方案。定义N行N列图像中的第m行第n列的图像像素点为X(m, n)；定义水平方向一维离散小波变换后，第m行第n列高频系数为H（m, n），第m行第n列低频系数L(m, n)；定义垂直方向一维离散小波变换后，第m行第n列甚高频小波系数为HH(m, n)，第m行第n列高低频子带小波系数为HL(m, n)，第m行第n列低高频子带小波系数为LH(m, n)，第m行第n列甚低频子带小波系数为LL(m, n)。 

所述的按照行列交织的顺序读入N行N列的图像数据，是指从第0行第0列开始，读取第0行第0列图像数据X(0,0)、第0行第1列图像数据X(0,1)、第0行第2列图像数据X(0,2)进行水平方向一维离散小波变换，采用公式1和公式2算得第0行第0列高频系数H(0,0)、第0行第0列低频系数L(0,0)；公式1和公式2中，m和n都是小于等于N的自然数： 

                 公式1

                  公式2

               公式3

              公式4

      公式5

                公式6

将H(0,0)存入内部存储器；换行读取第1行第0列图像数据X(1,0)、第1行第1列图像数据X(1,1)、第1行第2列图像数据X(1,2)进行水平方向一维离散小波变换，算得高频系数H(1,0)、低频系数L(1,0)并将H(1,0)存入内部存储器；按此方法逐行读入数据并进行转换直至第N行，并将相应的高频系数H(m, 0)存入内部存储器；

返回第0行，换列读取第0行第2列数据X(0,2)、第0行第3列数据X(0,3)、第0行第4列数据X(0,4)进行水平方向一维离散小波变换，计算出H(0,1)后，从内部存储器中读取H(0,0)用来计算L(0,1),之后将H(0,1)存入内部存储器并覆盖掉；然后跳转到第1行读取第1行第2列数据X(1,2)、第1行第3列数据X(1,3)、第1行第4列数据X(1,4) 进行水平方向一维离散小波变换，计算出H(1,1)后，从内部存储器中读取H(1,0)用来计算L(1,1),之后将H(1,1)存入内部存储器并覆盖掉H (1,0)；按此方法逐行读取数据并进行转换直至第N行，并将原内部存储器中的H(m,0)逐个更新为H(m,1)；

返回第0行，循环进行以上操作，按照这种行列交织的方法读取全部图像数据进行计算。

所述同时进行水平方向和垂直方向的5/3提升结构离散小波变换，是水平方向一维离散小波变换所产生的高频系数和低频系数是按照垂直方向逐列输出的；只需用三个寄存器缓存高频系数，便可用公式3和公式4进行垂直方向一维离散小波变换，生成甚高频子带小波系数HH(m,n)和高低频子带小波系数HL(m,n)；与此同时，用三个寄存器缓存高频系数，便可用公式5和6进行垂直方向一维离散小波变换，生成低高频子带小波系数LH(m,n)和甚低频子带小波系数LL(m,n)；即同时计算出四个频率子带的变换结果，从而完成5/3提升结构二维离散小波变换。 

所述的处理完成N行N列大小的图像仅需N个存储单元，是指从第0行第0列开始，读取第0行第0列图像数据X(0,0)、第0行第1列图像数据X(0,1)、第0行第2列图像数据X(0,2)进行水平方向一维离散小波变换，算得H(0,0)、L(0,0)并将H(0,0)存入内部存储器；换行读取第1行第0列图像数据X(1,0)、第1行第1列图像数据X(1,1)、第1行第2列图像数据X(1,2)进行水平方向一维离散小波变换，算得H(1,0)、L(1,0)并将H(1,0)存入内部存储器；按此方法逐行读入数据并进行转换直至第N行，并将N个高频系数H(m,0)存入内部存储器； 

返回第0行，换列读取第0行第2列数据X(0,2)、第0行第3列数据X(0,3)、第0行第4列数据X(0,4)进行水平方向一维离散小波变换，计算出H(0,1)后，从内部存储器中读取H(0,0)用来计算L(0,1),之后将H(0,1)存入内部存储器并覆盖掉；然后跳转到第1行读取第1行第2列数据X(1,2)、第1行第3列数据X(1,3)、第1行第4列数据X(1,4)进行水平方向一维离散小波变换，计算出H(1,1)后，从内部存储器中读取H(1,0)用来计算L(1,1),之后将H(1,1)存入内部存储器并覆盖掉    H (1,0)；按此方法逐行读取数据并进行转换直至第N行，并将原内部存储器中的N个H(m,0)逐个更新为N个H(m,1)；

返回第0行，循环进行以上操作，按照这种行列交织的方式读取全部图像数据进行完水平方向一维离散小波变换；水平方向一维离散小波变换所产生的高频系数和低频系数是按照垂直方向逐列输出的，只需用三个寄存器缓存高频系数，便可用公式3和公式4进行垂直方向一维离散小波变换，生成甚高频子带小波系数HH(m,n)和高低频子带小波系数HL(m,n)；与此同时，用三个寄存器缓存低频系数，便可用公式5和公式6进行垂直方向一维离散小波变换，生成低高频子带小波系数LH(m,n)和甚低频子带小波系数LL(m,n)；即同时计算出四个频率子带的二维离散小波变换结果；在整个变换过程中，仅需N个存储单元。

有益效果：该发明突破了传统的光栅扫描方法所采用的先行后列的数据读入方式，按照行列交织扫描方法读入图像数据，使得5/3提升结构离散小波变换过程中，水平方向一维离散小波变换输出的低频系数无需存储，仅需缓存N个高频系数，便可同时进行垂直方向一维离散小波变换，同时输出四个频率子带的小波系数。该发明将内部存储器的消耗降低至，相对于传统最优的设计方案降低了50%。 

  

附图说明

下面结合附图和实施例对本发明做进一步说明。 

图1 采用传统的5/3提升结构二维离散小波变换光栅扫描方法处理66图像的 

原理流程图 。                     

图2 用于图像压缩的提升结构二维离散小波变换交织扫描方法进行水平方向一

维离散小波变换时的数据读取和计算顺序。

图3用于图像压缩的提升结构二维离散小波变换交织扫描方法进行垂直方向一 

维离散小波变换时的数据读取和计算顺序。

图4用于图像压缩的提升结构二维离散小波变换交织扫描方法流程图。 

  

具体实施方式

用于图像压缩的提升结构二维离散小波变换交织扫描方法，按照行列交织的顺序读入图像数据，同时进行水平方向一维离散小波变换和垂直方向一维离散小波变换。其转换流程为： 

从第0行第0列开始，读取第0行第0列的X(0,0)、第0行第1列的X(0,1)、第0行第2列的X(0,2)进行水平方向一维离散小波变换，算得H(0,0)、L(0,0)并将H(0,0)存入内部存储器；换行读取X(1,0)、X(1,1)、X(1,2)进行水平方向一维离散小波变换，算得H(1,0)、L(1,0)并将H(1,0)存入内部存储器。按此方法逐行读入数据并进行转换直至第N行，并将相应的高频系数H(m,0)存入内部存储器。

返回第0行第2列，读取第0行第2列的X(0,2)、第0行第3列的X(0,3)、第0行第4列的X(0,4)进行水平方向一维离散小波变换，计算出H(0,1)后，从内部存储器中读取H(0,0)用来计算L(0,1),之后将H(0,1)存入内部存储器并覆盖掉。然后跳转到第1行读取X(1,2)、X(1,3)、X(1,4) 进行水平方向一维离散小波变换，计算出H(1,1)后，从内部存储器中读取H(1,0)用来计算L(1,1),之后将H(1,1)存入内部存储器并覆盖掉H (1,0)。按此方法逐行读取数据并进行转换直至第N行，并将原内部存储器中的H(m,0)逐个更新为H(m,1)。 

返回第0行，循环以上行列交织的读取操作和计算过程，直至全部图像数据进行完水平方向一维离散小波变换。在此过程中，水平方向一维离散小波变换所产生的高频系数和低频系数是按照垂直方向逐列输出的。只需用三个寄存器缓存高频系数，便可用公式3和公式4进行垂直方向一维离散小波变换，生成HH(m,n)和HL(m,n)；与此同时，用三个寄存器缓存高频系数，便可用公式5和公式6进行垂直方向一维离散小波变换，生成LH(m,n)和LL(m,n)。即同时计算出四个频率子带的二维离散小波变换结果。 

基于以上分析，具体的算法流程为： 

1）初始化m=0, n=0；

2) 读入原始图像数据X(m, 0)、X(m, 1)、X(m, 2)，由公式(1)、公式(2)分别计算出中间系数H(m, 0)、L(m, 0)，并将H(m, 0)存入内部存储器。将m加1；

3）重复步骤2)，至m=N，将m置零并将n加1；

4）读入原始图像数据X(m, 2n)、X(m, 2n+1)、X(m, 2n+2)，由公式(1)计算出H(m,n)从内部存储器中读入H(m, n-1)，由公式(2)计算出L(m, n)。将H(m, n)存入内部存储器，覆盖掉H(m, n-1)，将m加1；

5）重复步骤4)至m=N，将m置零并将n加1；

6）重复步骤4)和5)至n=N/2-1，计算结束；

水平方向一维离散小波变换和垂直方向一维离散小波变换是并行的计算过程。因为水平方向一维离散小波变换输出数据的顺序是垂直方向逐列输出，所以垂直方向一维离散小波变换不需要内部存储器，而只需3个寄存器缓存三个中间变换系数后，就直接计算并输出最终的变换结果。

 下面以图像进行提升结构二维小波变换的实例，来说明具体实施方式： 

1）读入原始图像第一行前三个数据X(0,0)、X(0,1)、X(0,2)，计算出中间系数H(0,0)、L(0,0)，并将H(0,0)存入内部存储器；

2）读入原始图像第二行前三个数据X(1,0)、X(1,1)、X(1,2)，计算出中间系数H(1,0)、L(1,0)，并将H(1,0)存入内部存储器；

3）读入原始图像第三行前三个数据X(2,0)、X(2,1)、X(2,2)，计算出中间系数H(2,0)、L(2,0)，并将H(2,0)存入内部存储器；

4）第二级变换单元由H(0,0)、L(0,0)， H(1,0)、L(1,0)， H(2,0)、L(2,0)，计算并输出HH(0,0)、HL(0,0)、LH(0,0) 、 LL(0,0)；

5）读入原始图像第四行前三个数据X(3,0)、X(3,1)、X(3,2)，计算出中间系数H(3,0)、L(3,0)，并将H(3,0)存入内部存储器；

6）读入原始图像第五行前三个数据X(4,0)、X(4,1)、X(4,2)，计算出中间系数H(4,0)、L(4,0)，并将H(4,0)存入内部存储器；

7）第二级变换单元由H(2,0)、L(2,0)， H(3,0)、L(3,0)， H(4,0)、L(4,0)，计算并输出HH(1,0)、HL(1,0)、LH(1,0)、LL(1,0)；

8）读入原始图像第一行后三个数据X(0,2)、X(0,3)、X(0,4)，计算出中间系数H(0,1)，从内部存储器中读入H(0,0)，计算出L(0,1)。将H(0,1)存入内部存储器，覆盖掉H(0,0)；

9）读入原始图像第二行后三个数据X(1,2)、X(1,3)、X(1,4)，计算出中间系数H(1,1)，从内部存储器中读入H(1,0)，计算出L(1,1)。将H(1,1)存入内部存储器，覆盖掉H(1,0)；

10）读入原始图像第三行后三个数据X(2,2)、X(2,3)、X(2,4)，计算出中间系数H(2,1)，从内部存储器中读入H(2,0)，计算出L(2,1)。将H(2,1)存入内部存储器，覆盖掉H(2,0)；

11）第二级变换单元由H(0,1)、L(0,1)， H(1,1)、L(1,1)， H(2,1)、L(2,1)，计算并输出HH(0,1)、HL(0,1)、LH(0,1)、LL(0,1)；

12）读入原始图像第四行后三个数据X(3,2)、X(3,3)、X(3,4)，计算出中间系数H(3,1)，从内部存储器中读入H(3,0)，计算出L(3,1)。将H(3,1)存入内部存储器，覆盖掉H(3,0)；

13）读入原始图像第四行后三个数据X(4,2)、X(4,3)、X(4,4)，计算出中间系数H(4,1)，从内部存储器中读入H(4,0)，计算出L(4,1)。将H(4,1)存入内部存储器，覆盖掉H(4,0)；

14）第二级变换单元由H(2,1)、L(2,1)， H(3,1)、L(3,1)， H(4,1)、L(4,1)，计算并输出HH(1,1)、HL(1,1)、LH(1,1)、LL(1,1)，计算结束。