一种基于折叠流水线小波变换实现图像压缩的方法

摘要

本发明提供一种基于折叠流水线小波变换实现图像压缩的方法，尤其涉及一种基于折叠流水线技术，所述折叠流水线针对多种小波变换采用统一架构VLSI，通过构造小波变换最短迭代计算路径来减少计算资源消耗，并通过简化提升步骤，采用单射输入结构来提高硬件利用效率。实验结果表明，对于相同的图像，分别采用本结构与传统长流水线结构实验，本方法在资源消耗和硬件利用率方面更优。

说明书

技术领域

本发明涉及一种适用于多种小波变换的统一架构VLSI(Very Large Scale Integration，超大规模集成电路)实现方法，尤其涉及一种基于折叠流水线技术，通过构造小波变换最短迭代计算路径来减少计算资源消耗，并通过简化提升步骤，采用单射输入结构来提高硬件利用效率，属于数字图像处理技术领域。

背景技术

小波变换以其独特的时频局部化特性，在信号分析和数字图像处理等领域有着广泛的应用。上个世纪九十年代，Sweldens和Daubechies等学者提出了小波信号分解与重构的快速计算格式-提升格式(lifting scheme)。提升格式的基本思想是建立在双正交小波和完全可恢复滤波器组的理论基础上，在保持小波双正交特性的条件下，通过所谓提升和对偶提升过程来改善小波及其对偶的性能，以满足各种应用的需要。

基于提升格式的小波变换具有如下优点：小波基构造可以完全在时域内进行，无须傅立叶分析；涉及的工具较简单，主要为Laurent级数的Euclidean除法；可以构造出所有已有的小波变换，并且得到部分新的小波变换；运算量较小，可以实现即位(in-place)运算；正向变换与反变换的结构一致，仅有正负号的区别。

提升格式主要包括三个步骤：分裂、预测和更新，具体内容如下：

分裂：将原信号x(n)分裂为两个互不相交的子集，通常将原信号序列x(n)分解为偶数序列x_e(n)和奇数序列x_o(n)，即

x_e(n)＝x(2n)，x_o(n)＝x(2n+1)    (1)

预测：利用预测算子P计算新的奇数序列d(n)，即利用偶数序列x_e(n)预测邻近的奇数序列x_o(n)，预测产生误差d(n)可用来表示信号的高频信息，作为小波变换的高频系数。其表达式为

d(n)＝x_o(n)-P(x_e(n))    (2)

更新：通过更新算子U产生新的偶数序列s(n)，使之保持原有偶数序列x_e(n)的一些特性，s(n)即可用来表示信号的低频信息，作为小波变换的低频系数。更新过程的表达式为

s(n)＝x_e(n)+U(d(n))    (3)

目前，在静态图像压缩标准JPEG2000中采用基于提升格式9/7双正交小波变换做有损压缩，采用基于提升格式5/3双正交小波变换做无损压缩。其中，9/7小波变换方式的优点在于小波变换的能量集中性和恢复图像的PSNR(峰值信噪比，目前最常用的图像质量客观评价指标)较高，但其运算复杂度较高，VLSI实现时消耗资源较多。5/3双正交小波变换由于其小波基长度较短以及容易定点化的特点，其计算步骤少，功耗低，实时性强，但是能量集中性和恢复图像的PSNR较9/7小波变换表现差。对于内容较为简单的图像，采用5/3小波便可以达到较好的压缩效果，并且可以减少处理时间和计算功耗，内容复杂的图像则采用9/7小波取得的压缩效果较优。

在此背景下，研究一种能实现多种小波变换的统一架构VLSI对图像压缩质量、处理实时性以及运算功耗均有要求的图像处理平台显得尤为重要。

发明内容

本发明的目的在于提供一种采用折叠流水线的统一架构VLSI实现多种小波变换来实现图像处理的方法。该方法通过构造9/7和5/3小波变换最短迭代计算路径来减少计算资源消耗；通过复用移位寄存器实现数据延拓来减少存储资源消耗；并通过简化提升步骤，采用单射输入结构来提高硬件利用效率。

为实现上述的目的，本发明采用下述的技术方案：一种基于折叠流水线小波变换实现图像压缩的方法，所述折叠流水线针对多种小波变换采用统一架构VLSI，其包括步骤：

(1)图像数据读入：从单端口存储器按行串行读进像素数据；

(2)图像数据预处理：从读入的像素值减去直流分量，所述直流分量值取像素值最大值的一半；

(3)预处理后的数据送入基于折叠流水线的提升小波运算模块，进行小波变换；提升小波运算模块采用移位寄存器复用的边界对称延拓，免分裂步骤的单射输入结构；小波变换运算过程中采用推迟低频系数尺度变换的方法；

(4)在小波变换之后，对小波系数进行量化操作；

(5)对量化后的小波系数进行熵编码，得到最终码流。

其中，所述步骤(3)中，小波变换采用基于提升格式实现，包括一次或者多次迭代过程；一次迭代所需的运算电路包括预测和更新电路模块，数据输入通过寄存器D0和寄存器D1，得到输入的奇偶队列，送入预测电路的输入端口寄存器D2和端口寄存器D3，预测得到的低频系数作为更新电路的输入，与更新电路的寄存器D6相连；预测得到的高频系数作为更新电路的输入，与更新电路的寄存器D7相连；更新得到的结果保存到寄存器D11和D10中；D11同时与乘法器M3、路选器mux3和路选器mux1相连。

进一步的，在9/7小波变换的第一次迭代阶段，寄存器D11保存的数据通过mux1被选通到寄存器D2，寄存器D10保存的数据通过mux2被选通到寄存器D3，D2和D3中的数据进入第二次迭代阶段；在9/7小波变换的第二次迭代阶段，寄存器D11保存的数据通过乘法器M3，与K运算得到的结果送到寄存器D12，作为最终的低频系数输出；寄存器D10保存的数据通过乘法器M4，与K运算得到的结果送到寄存器D13，作为最终的高频系数输出。

进一步的，在做5/3小波变换时，只需要一次迭代运算，将寄存器D11的数据直接通过路选器mux3送到寄存器D12，作为最终的低频系数输出，寄存器D10的数据直接通过路选器mux4送到寄存器D13，作为最终的高频系数输出。

进一步的，所述步骤3中，小波变换模块采用折叠流水线技术的统一实现架构VLSI，构造9/7和5/3小波变换最短计算路径，动态配置不同小波基和不同迭代阶段乘法器的操作常数。

进一步的，在9/7小波变换第一次迭代阶段，乘法器M1的操作常数被配置为α，与寄存器D2和寄存器D5的加和相乘，乘法器M2的操作常数被配置为β，与寄存器D7和寄存器D9的加和相乘；在9/7小波变换第二次迭代阶段，乘法器M1的操作常数被配置为γ，与寄存器D2和寄存器D5的加和相乘；乘法器M2的操作常数被配置为δ，与寄存器D7和寄存器D9的加和相乘。

进一步的，在做5/3小波变换时，只需要进行一次迭代操作，乘法器M1的操作常数被配置为μ，与寄存器D2和寄存器D5的加和相乘，乘法器M2的操作常数被配置为v，与寄存器D7和寄存器D9的加和相乘。

进一步的，所述步骤3中，在图像数据进入小波变换迭代运算电路之前，要对图像数据进行边界延拓；小波变换的边界对称延拓采用移位寄存器复用的结构；该移位寄存器复用的结构由三部分组成：由寄存器D0-D8组成的移位寄存器链，数据选择器以及控制器；在寄存器使能信号en有效时，小波变换的输入样本逐周期依次通过寄存器D0到D8，将寄存器D0连接到数据选择器的5号端口，寄存器D1连接到数据选择器的4号端口、寄存器D2连接到数据选择器的3号端口、寄存器D4连接到数据选择器的2号端口、寄存器D6连接到数据选择器的1号端口、寄存器D8的数据输出端口连接到数据选择器连接到数据选择器的0号端口；控制器将数据有效信号连接到寄存器D0-D8的使能端口，同时根据采用9/7小波还是5/3小波进行数据选择器选通信号sel生成。

进一步的，所述步骤3中，在图像数据进入小波变换迭代运算电路之前，要对图像数据进行边界延拓；小波变换的边界对称延拓采用移位寄存器复用的结构；在做9/7小波变换时，输入样本数据有效后的前5个周期内不进行输出，在第6个周期输出寄存器D0里的数据，第7个周期输出寄存器D2里的数据，第8个周期输出寄存器D2里的数据，第9个周期输出寄存器D4里的数据，第10个周期输出寄存器D6里的数据，在此之后输入样本数据有效期间，一直输出寄存器D8里的数据；在输入样本数据无效后，控制器模块拉低移位寄存器链里D0-D8的使能控制信号，逐周期的将寄存器D8到寄存器D0中的数据导出，在此之后，再顺序导出寄存器D1、寄存器D2以及寄存器D3里的数据。

进一步的，所述步骤3中，在图像数据进入小波变换迭代运算电路之前，要对图像数据进行边界延拓；小波变换的边界对称延拓采用移位寄存器复用的结构；在做5/3小波变换时，输入样本数据有效后的前3个周期内不进行输出，在第4个周期输出寄存器D0里的数据，第5个周期输出寄存器D2里的数据，第6个周期输出寄存器D2里的数据，在此之后输入样本数据有效期间，一直输出寄存器D4的数据；在输入样本数据无效后，控制器模块拉低移位寄存器链里D0-D4的使能控制信号，逐周期的将寄存器D4到寄存器D0中的数据导出，在此之后，导出寄存器D1里的数据。

进一步的，所述步骤3中，在图像数据进入小波变换迭代运算电路之前，要对图像数据进行边界延拓；边界延拓后的图像数据被送入迭代运算电路；小波变换采用单射的输入结构；边界对称延拓后的小波变换输入样本数据与寄存器D0相连，寄存器D0的输出端与寄存器D1输入端相连；寄存器D0中的数据和寄存器D11通过选择器mux1进入提升运算电路的寄存器D2，寄存器D1中的数据和寄存器D11通过选择器mux2进入提升运算电路的寄存器D3。

进一步的，所述步骤3中，所述推迟低频系数尺度变换的方法为：进行尺度变换前的提升电路的低频输出结果保存在D11中，根据所在的变换级别决定是否对其进行尺度变换；在做第n级小波变换时，若n不是最后一级变换，得到的低频系数保持不变，高频系数中HL和LH子带与K^2(n-1)做一次乘法，高频系数中HH子带与K^2(n-2)做一次乘法；在做第n级小波变换时，若n是最后一级小波变换，高频系数中HL和LH子带与K^2(n-1)做一次乘法，高频系数中HH子带与K^2(n-2)做一次乘法，低频系数与K²ⁿ相乘，得到的结果最为最终的小波系数；K是个常数，将K²ⁿ的取值做成查找表的形式，便不需要进行额外的运算，用到时查表即可。

本发明具有如下的优点：通过设计适合在FPGA等高速计算平台上实现的多种小波变换统一实现架构，能够有效地减少实现多种小波变换所消耗的器件面积，进而改善功耗和实时处理能力；在此基础上采用寄存器复用的边界延拓算法和免分裂的单射输入结构，改善流水线负载均衡状况，减少消耗的寄存器数目。

附图说明

下面结合附图和具体实施方式对本发明进一步的详细说明。

图1是基于小波变换编码方法的一般实现流程，包括图像数据输入、数据预处理、小波变换、量化和熵编码步骤。

图2是小波变换提升实现的一般实现步骤，包括分裂、预测以及更新。

图3是常规的基于提升格式的9/7小波变换实现方法的流水处理示意图。其中：x(n)为原始数据，y(n)为小波逆变换后的数据，预测1、更新1、预测2和更新2为中间过程。

图4是基于提升格式的9/7小波变换所做的对称延拓示意图，图中实线处对应的数为原始的11个输入，虚线处为延拓的数据，其中左延拓数目为4，右延拓数目为3。

图5是本发明采用的基于移位寄存器复用的边界对称延拓结构图。

图6是本发明采用的折叠流水线的9/7小波变换提升实现硬件结构图。

图7是基于提升格式的9/7小波变换一次提升步骤对应的电路结构。

具体实施方式

本发明所提供的基于折叠流水线的多种小波变换统一架构VSLI实现方法主要是针对处理时间、变换性能以及计算功耗要求较多的多种小波变换如基于提升格式的9/7和5/3小波变换而专门提出的。下面，以图像压缩中的9/7和5/3小波变换为例对本发明的具体实施步骤进行详细的说明。但显然，本发明所提供的方法还可以用于对其它类型数据进行的基于提升格式的小波变换操作，所取得的有益效果也是相似的。

小波变换提升格式计算过程如2所示，一次迭代分为分裂、预测与更新三个步骤。9/7小波变换的提升格式由两次迭代组成，5/3小波变换的提升格式由一次迭代完成，9/7小波变换的提升步骤为：

(1)分裂，s₀[n]＝x[2n]，d₀[n]＝x[2n+1]

(2)预测1，d₁[n]＝d₀[n]+α(s₀[n]+s₀[n+1])，s₁[n]＝s₀[n]

(3)更新1，s₂[n]＝s₁[n]+β(d₁[n]+d₁[n-1])，d₂[n]＝d₁[n]

(4)预测2，d₃[n]＝d₂[n]+γ(s₂[n]+s₂[n+1])，s₃[n]＝s₂[n]

(5)更新2，s₄[n]＝s₃[n]+δ(d₃[n]+d₃[n-1])，d₄[n]＝d₃[n]

(6)尺度变换，s[n]＝(1/k)s₄[n]，d₅[n]＝kd₄[n]

其中，分裂步骤中s₀[n]和d₀[n]分别表示输入队列中偶数位置和奇数位置的数据；α、β、γ和δ为提升系数，参与提升步骤中的乘法运算，k为尺度变换系数。

5/3小波变换的提升步骤为：

(1)分裂，s₀[n]＝x[2n]，d₀＝x[2n+1]

(2)预测，d[n]＝d₀[n]-μ(s₀[n]+s₀[n+1])

(3)更新，s[n]＝s₀[n]+v(d[n]+d[n-1])

其中，分裂步骤中s₀[n]和d₀[n]分别表示输入队列中偶数位置和奇数位置的数据；μ和v为提升系数，参与提升步骤中的乘法运算。

分析基于提升格式的小波变换计算过程，如图3。预测1、更新1、预测2和更新2表示9/7小波变换的提升格式中二次迭代的计算过程，x(n)表示输入小波系数点序列。对于5/3小波变换提升格式只需要迭代一次，只进行预测1和更新1以及尺度变换，跳过预测2和更新2。

一般情况下，完成图3所示的数据流水处理过程，产生与原始数据量相同的高频与低频系数必须对输入进行边界延拓，最常用的方式是边界对称延拓。传统的边界延拓算法包括边界数据延拓、存储和读取三个操作，需要单独的数据存储单元和运算过程。压缩的图像数据量较大时，边界延拓运算将耗费较多的内存与运算单元。也有嵌入式延拓，即将延拓嵌入到提升算法中，但是要改变原有的数据依赖关系，控制变得复杂。9/7小波变换对称延拓示意图如图4所示。

延拓后的数据输入到提升结构进行迭代运算。小波变换在进入第一次迭代之前要经过分裂的步骤，即将输入分裂为奇偶两个数据序列再送到提升结构，则一个双输入的提升步骤如图7所示。一个奇数据和一个偶数据同时进入该提升结构，相隔一个周期的偶数据进行求和操作，再与提升因子相乘，将乘积结果与对应周期的奇数据求和得到预测或者更新的结果。对于大多数应用场合，比如从单端口存储器读出，或者从图像采集设备获取的数据大多数都是串行进入的，每个周期进入一个数据，这种情况下，提升流水线架构效率降低50％，只有一半时间为有效负载，另一半时间处于空置状态。

在提升计算过程中，有关尺度系数K的运算，实际上是一个归一化乘法操作，该操作将提升格式生成的低频和高频数据分别乘以一对互为倒数的尺度系数(K和K^-1)。二维图像的小波变换可拆分为两个独立的一维小波变换，即先对原数据行进行一维小波变换，再对数据列进行一维小波变换。若每次提升格式运算时都进行尺度系数K的乘法运算，则对应所有样本点均进行了两次乘法操作，若进行6级小波变换，则最低频子带的变换系数的归一化乘法运算次数最多可达到12次，其它子带也均有一定的重复运算。

本发明的基于折叠流水线实现结构如图6所示，9/7小波变换提升结构的后两个流水节拍的数据路径结构与前两个流水节拍相同，因此可以设计两个流水节拍的电路结构，通过适当的反馈策略，可以将某一次的运算结果重新导入该电路，进行第二次迭代运算。一次迭代所需的运算电路包括预测和更新电路模块。数据输入通过延迟寄存器D0和D1，得到输入的奇偶队列，送入预测电路的输入端口寄存器D2和D3。预测得到的低频系数作为更新电路的输入，与更新电路的寄存器D6相连；预测得到的高频系数作为更新电路的输入，与更新电路的寄存器D7相连。更新得到的结果保存到寄存器D11和D10中。D11同时与乘法器M3、路选器mux3和路选器mux1相连。

在9/7小波变换的第一次迭代阶段，寄存器D11保存的数据通过mux1被选通到寄存器D2，寄存器D10保存的数据通过mux2被选通到寄存器D3，D2和D3中的数据进入第二次迭代阶段；在9/7小波变换的第二次迭代阶段，寄存器D11保存的数据通过乘法器M3，与K运算得到的结果送到寄存器D12，作为最终的低频系数输出。寄存器D10保存的数据通过乘法器M4，与K运算得到的结果送到寄存器D13，作为最终的高频系数输出。

在做5/3小波变换时，只需要一次迭代运算，将寄存器D11的数据直接通过路选器mux3送到寄存器D12，作为最终的低频系数输出。寄存器D10的数据直接通过路选器mux4送到寄存器D13，作为最终的高频系数输出。

在9/7小波变换第一次迭代阶段，乘法器M1的操作常数被配置为α，与寄存器D2和寄存器D5的加和相乘。乘法器M2的操作常数被配置为β，与寄存器D7和寄存器D9的加和相乘；在9/7小波变换第二次迭代阶段，乘法器M1的操作常数被配置为γ，与寄存器D2和寄存器D5的加和相乘。乘法器M2的操作常数被配置为δ，与寄存器D7和寄存器D9的加和相乘；在做5/3小波变换时，只需要进行一次迭代操作，乘法器M1的操作常数被配置为μ，与寄存器D2和寄存器D5的加和相乘。乘法器M2的操作常数被配置为v，与寄存器D7和寄存器D9的加和相乘。

在做边界对称延拓时，本发明利用FPGA内部寄存器的使能信号，使得寄存器链合理地工作在移位与锁存状态，实现寄存器复用，达到减少寄存器消耗数量的目的。具体操作如下所述。

在边界对称延拓过程中，对于9/7小波，移位寄存器链工作分为以下几个状态：

(1)流水线填充：在输入使能控制信号有效后的头5个周期，将输入数据送入移位寄存器链，不输出。

(2)左延拓数据输出：移位寄存器正常移位，在第六个周期，输出D0寄存器数据，后几个周期依次输出D2、D4、D6和D8寄存器数据，之后进入中间数据输出状态。

(3)中间数据输出：输入使能有效期间，移位寄存器正常移位，输出D8寄存器数据。输入使能无效，进入右延拓数据输出状态。

(4)右延拓数据输出：输入使能无效，则流水线里保存了尚未输出的中间数据以及待右延拓的数据，此时将寄存器的使能端拉低，依次输出D8到D0的数据，最后输出需要延拓的D3、D2和D1寄存器里的数据。

对于5/3小波，输出分为几个状态：

(1)流水线填充：在输入使能控制信号有效的头3个周期，将输入数据送入移位寄存器链，不输出。

(2)左延拓数据输出：移位寄存器正常移位，在第四个周期，输出D0寄存器数据，后几个周期依次输出D2和D4寄存器，之后进入中间数据输出状态。

(3)中间数据输出：输入使能有效期间，移位寄存器正常移位，输出D4寄存器数据。输入使能无效，进入右延拓数据输出状态。

(4)右延拓数据输出：输入使能无效，则流水线里保存了尚未输出的中间数据以及待右延拓的数据，此时将寄存器的使能端拉低，依次输出D4到D0寄存器中的数据，最后输出需要延拓的D1寄存器里的数据。

如图6，做提升运算时，本发明采用单射输入结构，该结构每个周期接收一个小波变换输入样本数据，样本数据依次经过寄存器D0和寄存器D1，经过路选器mux1和mux2进入提升步骤的D2和D3寄存器，每个周期输入提升结构中一个数据，数据的奇偶分离由延迟寄存器D0和D1完成。这样在偶数据D2和D5完成求和、并与α或μ相乘的操作时，再与奇数据D3求和得到一个小波系数；下一个周期从流水线输出的偶数据D5则是另一个小波系数。该结构每个周期吞进一个输入并输出一个系数，流水线有效负载一直保持平衡。

在做尺度变换时，本发明在某一级小波变换产生小波系数时判定是否为高频系数，若是高频系数则进行归一化操作，若是低频系数则直接送到低频系数存储，不进行归一化操作，在做下一级时对高频系数的尺度系数K进行调整，抵消上一级低频系数不归一化带来的取值范围增益，使各个子带变换系数仅需要做一次乘法运算。

具体操作如下：在做第n(n不是最后一级变换)级小波变换时，得到的低频系数保持不变，高频系数中HL和LH子带与K^2(n-1)做一次乘法，高频系数中HH子带与K^2(n-2)做一次乘法。在做第n(n是最后一级小波变换)级小波变换时，高频系数与前几级做同样的处理，低频系数与K²ⁿ相乘，送到小波系数存储。

由于K是个常数，可以将K²ⁿ的取值做成查找表的形式，便不需要进行额外的运算，用到时查表即可。

本发明经过在Modelsim SE 6.5a平台上仿真测试，仿真文件激励为256*256大小的图像，对基于提升格式的9/7小波变换和5/3小波变换算法都能够根据程序配置得到正确的变换结果。在逻辑资源消耗上，本发明比一般9/7长流水线结构节约近一半资源，仅与5/3提升结构相当，硬件实现效率100％。

以上对本发明所述的基于提升格式的9/7和5/3小波变换优化实现方法进行了详细的说明，但显然本发明的具体实现形式并不局限于此。对于本技术领域的一般技术人员来说，在不背离本发明的权利要求范围的情况下对它进行的各种显而易见的改变都在本发明的保护范围之内。