视频和图象数据压缩的整型双正交小波变换电路

摘要

本发明涉及一种用于视频和图象数据压缩的整型双正交小波变换电路。该小波变换电路含有一维小波变换电路、多层二维双正交小波变换控制电路和数据传输接口电路,是一个满足视频和图象数据压缩技术要求的、具备无损和有损压缩双重功能的、使用集成电路资源相对较少、能够集成到一片价格低廉的集成电路之中的整型双正交小波变换电路。它能够实时地完成任意常用尺寸一帧或一块视频或图象数据的多层二维双正交小波正变换和逆变换。

说明书

本发明涉及视频和图象数据的压缩变换电路。

在视频和图象数据压缩中，为提高压缩效率通常使用数学变换技术，目前所采用的数学变换包括离散余弦变换和小波变换。其中小波变换一般是对整帧图象进行，小波变换后的低频子带区域包含了图象的大部分信息，集中了大部分的大绝对值小波变换系数；高频子带区域包含图象灰度突变处的细节信息，具有相对很少的大绝对值小波变换系数。为提高图象压缩效率，一般进行所谓“多层小波变换”，即对所产生的低频子带再次进行小波变换，使大绝对值小波变换系数进一步集中；而高频子带区域由于大绝对值小波变换系数相对很少，故不再进行小波变换。由于大绝对值小波变换系数集中到一定程度再进行小波变换通常不会有显著效果，因此小波变换的层数一般为3层到5层。

目前通常采用的小波变换是1996年Daubechies等人提出的二维双正交小波变换方法，具有有损和无损压缩双重功能。至今，已经设计出小波变换电路的只有美国Analog Devices公司，但是他们所采用的是非整型二维双正交小波变换方法，该电路不具备无损压缩功能，而且耗费的集成性电路资源较多[美国专利US5838377]。日本Ricoh公司和其他国家的一些公司和科研机构提出了许多进行小波变换的方法，但是没有设计具体的集成电路。因此目前还没有利用上述整型双正交小波变换方法设计出的集成电路产品，本发明就是基于整型双正交小波变换方法设计了具备无损压缩和有损压缩双重功能的小波变换电路，而且通过分时技术共用运算单元，所耗费的集成电路资源较少。

本发明的目的是设计一个满足视频和图象数据压缩技术要求的、具备无损和有损压缩双重功能的、使用集成电路资源相对较少、能够集成到一片价格低廉的集成电路之中的整型双正交小波变换电路，实时地完成任意常用尺寸的一帧或一块图象数据的多层二维双正交小波正变换和逆变换。

本发明的内容与技术方案如下：

本发明所依据的原理是Daubechies等人于1996年提出的整型小波变换方法。其基本思想是基于欧几里德算法将小波变换分解成提升的形式，再通过取整对每一步提升所产生的浮点数进行处理，直至最后完成整型小波变换。

整型小波正变换具体运算步骤是：

首先，用LAZY变换将待变换数据按其存储器中的奇、偶地址进行分离，s表示偶地址的数据，d表示奇地址的数据。

然后利用提升算法，即将一维小波变换分解为几个一阶多项式的运算，一阶多项式的数目根据所用小波基的性质决定；奇或偶地址的数据通过滤波器滤波后，再与偶或奇地址的数据相加。

经过一定次数的提升运算，偶地址的数据就相应于低频子带数据，奇地址的数据相应于高频子带数据。最后还经过一次以K为比例因子的伸缩变换：

逆变换的运算步骤恰好相反：

首先做伸缩变换的逆变换。

然后利用提升算法进行相应的逆变换：

经过一定次数的提升运算，最后获得原始奇地址和偶地址的数据。

由于LAZY变换本身就是整型可逆的，因此提升运算的整型处理可以按照下面的方式进行简单处理(其中代表取整运算)。

通过以上处理，可以将小波变换写成可逆整型变换的形式。

图1是一维小波变换示意图，图中左半部执行正变换，右半部执行逆变换。一维小波正变换时，原始图象数据由总线顺序输入到低通滤波器L和高通滤波器H，滤波后顺序输出的第n个数据根据n是奇数或偶数分开存储，若n是偶数则属于低频子带数据，否则为高频子带数据。这两个频带的数据量分别是原图象数据量的1/2，其中低频子带一般包含原图象的大部分信息，高频子带包含原图象的边缘细节信息。由这两个频带的数据通过一维小波逆变换可以恢复原始图象数据。一维小波逆变换是正变换的逆过程，上述低频子带和高频子带的数据分别经各自低通和高通滤波后，迭加可形成原始图象数据。一维小波变换如果采用浮点运算，不仅运算量较大，而且由于精度误差，可能带来恢复的原始图象数据的偏差。由于提升运算的一阶多项式的运算差别仅在于滤波参数的不同，因此使用一个一阶多项式运算电路时，利用分时技术可以分别执行偶地址的数据s和奇地址的数据d的运算，即一阶多项式电路在奇脉冲时进行d的运算，偶脉冲时进行s的运算。由于通过分时技术共享运算电路，因此小波变换所需的电路资源的很少。本发明根据上述整型小波变换原理，首先对偶地址的数据进行滤波运算，滤波后的数据加上奇地址的数据，从而得到奇地址的高频子带数据；然后对此奇地址的高频子带数据进行滤波运算，滤波后的数据加上偶地址的数据，从而得到偶地址的低频子带数据。

本发明所设计的整型双正交小波变换电路含有一维小波变换电路、多层二维双正交小波变换控制电路和数据传输接口电路。

其中一维小波变换电路如图2所示。它含有边界处理电路和由几个一阶多项式运算电路组成的运算电路，分时地完成数据的低通和高通滤波，分时地执行小波行变换和列变换，分时地执行多层二维双正交小波正变换和逆变换。图中左边为寄存器电路，四组寄存器R201、R202、R203和R204分别控制偶地址的数据延时1、偶地址的数据延时2、奇地址的数据延时和高频子带数据延时等四路数据流，使它们在特定的时刻流入中间的运算电路A205。由于奇地址数据先行产生高频子带数据，因此由右边的寄存器R206对其加以缓存，待偶地址数据产生低频子带数据后再由选通器M207根据奇、偶时钟周期仍按原来的奇、偶地址顺序输出高、低频子带数据。行变换时逐行顺序输入待变换数据，列变换时逐列顺序输入待变换数据，数据输入一维小波变换电路后的处理步骤行、列变换基本相同。

具体的，运算电路A205首先对偶地址数据进行提升滤波：偶地址数据一路直接送入运算电路，另一路送入寄存器R201延时后再送入运算电路，以保证运算电路中偶地址数据同步相加运算。偶地址数据提升滤波后与对应奇地址数据相加，产生奇地址上高频子带数据。由于滤波运算必然会消耗几个时钟周期，而奇地址数据夹在偶地址数据之间顺序输入，因此需要将奇地址数据先送入寄存器R203延时后再送入运算电路，以保证运算电路中与偶地址滤波后数据的相加运算。然后运算电路A205再对奇地址数据进行提升滤波：运算电路A205产生奇地址上高频子带数据后，高频子带数据一路输出到寄存器R206做缓存，一路再直接送入运算电路与另一路高频子带数据送入寄存器R204延时后进行提升滤波。提升滤波后，滤波结果与寄存器R202送出的对应偶地址数据相加，产生偶地址上低频子带数据输出。由于偶地址数据需要等待两次滤波运算完成后才送入运算电路，以保证运算电路中与提升滤波后数据的相加运算，因此偶地址数据的寄存器R202延时比奇位置数据的寄存器R203延时长两倍时间。运算电路A205产生偶地址上低频子带数据后直接送入选通器M207，M207奇、偶时钟周期分别选通A205送出的偶地址上低频子带数据或寄存器R206延时后奇地址高频子带数据，并且仍按原来的奇、偶顺序输出。

一维小波变换电路中的一阶多项式运算电路如图3所示。它将小波变换分解成提升运算，并在奇、偶时钟脉冲时分别独立执行相应的提升滤波。其中通过加法器执行提升滤波加法运算，然后通过乘法器执行前一步加法器所产生的和与滤波系数的乘法运算，接着再通过加法器执行乘法器所产生的乘积与原存储器中相应数据的加法运算；乘法器对乘数的选通由选通器根据所进行的提升滤波进行控制。

具体的，加法器A301执行小波变换公式中的提升滤波加法运算，乘法器A302执行加法器A301产生的和与滤波系数的乘法运算，加法器A303执行乘法器A302产生的乘积即滤波后数据与奇(或偶)位置数据的加法运算。这样通过对提升滤波进行因式分解，先做加法运算再做乘法运算，可以减少乘法运算的次数，因为乘法运算消耗资源和时间均较多。

由于送到加法器A301的待运算数据除了首先作提升滤波的两路数据即偶地址数据和其经过R201延时的数据以外，还有随后要作提升滤波的两路数据即奇地址上高频子带数据和其经过R204延时的数据，因此需要两个选通器M304和M305对二者进行选通。具体的，M304选通偶地址数据或奇地址上高频子带数据，M305选通偶地址延时数据或奇地址上高频子带延时数据。在偶时钟周期M304和M305让两路偶地址数据通过，而在奇时钟周期M304和M305则让两路奇地址上高频子带数据通过。随后相应地，在奇时钟周期加法器A301执行偶位置数据的加法运算，在偶时钟周期A301执行奇位置上高频子带数据的加法运算。加法器A301产生的和数送入后续的乘法器A302。乘法器A302的被乘数端口相应地接收加法器A301产生的和，并与进入乘数端口的提升滤波系数作相应的乘法运算。因此由选通器M306根据奇、偶时钟周期，分别选通提升滤波系数，送到乘法器A302的乘数端口。随后乘法器A302输出的乘积送入加法器A303的一个输入端，A303的另一个输入端输入由延时寄存器R202或R203输出的奇地址或偶地址数据，这是通过选通器M307根据奇、偶时钟周期分别选通奇地址或偶地址的数据完成的。A303产生的和就是偶地址上低频子带数据或奇地址上高频子带数据。

本发明中的一维小波变换电路在处理边界问题时，是通过一个三选一选通器来执行提升运算行首、列首、行尾和列尾处理的。当要做行首或列首处理的数据运算到行首或列首时，三选一选通器由选通延时后的数据改为选通未延时的数据，一个时钟周期后恢复原选通；当要做行尾或列尾处理的数据运算到行尾或列尾时，三选一选通器由选通未延时的数据改为选通延时后的数据，一个时钟周期后恢复原选通；而且三选一选通器可以用两个二选一选通器代替。边界问题的产生是因为实际图象的每一数据行或列均是有限长，因此运算电路在数据行或列开始和结束时需要一些特殊处理。如PAL制式电视图象按CIF格式数字化，数据行长352，数据列长288。以CIF格式的行变换为例，每一行的数据地址排列是0-351。由小波变换公式，在首先进行的求解高频子带数据d的提升滤波中，当求解数据行结束时的351地址高频子带数据d₃₅₁时，需要352地址的数据s₃₅₂，可是实际上s₃₅₂不存在。由此本发明采用对称延拓方法，以348地址的数据s₃₄₈代替s₃₅₂数据。同样在随后进行的求解低频子带数据s的提升滤波中，求解数据行开始时的0地址低频子带数据s₀时，需要-1位置的高频子带数据d_-1，而d_-1也不存在，由此本发明以地址3的高频子带数据d₃来代替。小波变换电路中的运算首先是加法，那么在求解高频子带数据d的提升滤波执行到数据行结束时，采用对称延拓方法进行边界处理后的加法器A301产生的和是，…，(s₃₄₆+s₃₄₈)，(s₃₄₈+s₃₅₀)，(s₃₅₀+s₃₄₈)；在随后进行的求解低频子带数据s的提升滤波中，边界处理后的加法器A301在数据行开始时产生的和是(d₃+d₁)，(d₁+d₃)，(d₃+d₅)，…。可以看出，求解高频子带数据d的提升滤波中，加法器A301产生的最后两个和是相同的；而求解低频子带数据s的提升滤波中，加法器A301产生的最初两个和是相同的。因此只需要将(s₃₄₈+s₃₅₀)与(d₁+d₃)的和多保留两个时钟周期，再使用一次即可分别满足高频子带数据d₃₅₁与低频子带数据s₀的求解要求。为进行边界处理，在加法器A301与乘法器A302之间插入边界处理电路U308。

边界处理电路如图4所示。具体的，加法器A301的输出数据送到三路，一路直接通到选通器M403，另两路经寄存器R401、R402延时后再送入选通器M403。选通器M403由逻辑电路U404根据计数器U405的计数在高频子带数据d₃₅₁与低频子带数据s₀的运算时刻产生相应的选通控制信号。高频子带数据d的提升滤波中，当计数器U405计数到行结束时，逻辑电路U404产生选通切换信号，使选通器M403由选通加法器A301的输出数据改为选通经寄存器R401延时后的输出数据，此时钟周期后M403恢复选通A301的输出数据；低频子带数据s的提升滤波中，当计数器U405计数到第一个和第二个奇地址上高频子带数据的和产生时，逻辑电路U404产生选通切换信号，使选通器M403由选通寄存器R402延时后的输出数据改为选通加法器A301的输出数据，此时钟周期后。M403恢复选通寄存器R402延时输出数据。由于两种子带数据的提升滤波分别工作在不同的奇、偶时钟周期，因此它们的选通控制不会发生冲突。

对于二维双正交小波变换来说，对于正变换小波变换电路首先做行变换，然后再做列变换，即可完成二维双正交小波正变换；对于逆变换，小波变换电路首先做列变换，然后再做行变换，即可完成二维双正交小波逆变换。本发明的多层二维双正交小波变换控制电路采用状态比特表示小波正或逆变换、行或列变换以及处于第几层变换。行、列变换的差别主要在于数据行与列的长度不同，因此使边界处理电路中的逻辑电路产生选通切换信号的时刻根据行或列的长度自动变化就可以满足行、列变换的要求，这一点通过控制计数器U405的计数值很容易实现。U405在正变换时产生读信号和地址，将待变换数据从存储器中顺序读出，同时产生写信号和地址按低频子带数据在前、高频子带数据在后的顺序将变换后的数据写入存储器；在逆变换时U405产生读信号和地址，将待变换数据从存储器中按低、高频子带交替的顺序读出，同时产生写信号和地址将变换后的数据按顺序写入存储器。

对于彩色图象或彩色视频，可以通过一维小波变换电路分时执行彩色图象的R、G、B分量图象或Y、U、V分量图象的多层二维双正交小波正变换和逆变换。如果是R、G、B三基色分量图象，则三基色分量图象处理完全相同，由一维小波变换电路分时、分别一一执行R、G、B三基色分量图象的小波变换。如果是Y、U、V三分量图象，小波变换电路同样分时、分别一一执行三基色分量图象的小波变换，只是U、V分量图象的尺寸可能会与Y分量图象的尺寸不同，需要相应地调整小波变换电路中的边界处理。

说明书附图说明

图1：一维小波变换示意图。

图2：一维小波变换电路框图。

图3：一维小波变换电路一阶多项式运算电路框图。

图4：一维小波变换电路边界处理电路框图。

图5：二维小波变换频带示意图。

图6：四层小波变换频带示意图。

本发明用于实时完成任意常用尺寸的一帧或一块图象数据的二维双正交小波正变换和逆变换。下面结合实施例进行进一步地说明。

二维双正交小波正变换后的频带分布如图5所示。第一层一维小波行变换完成后，左半部是低频子带Lx，右半部是高频子带Hx；对低频和高频子带再做列变换，将产生图中所示的四个频率子带，左上部是低频子带LxLy，右上部是次高频子带HxLy，左下部是次高频子带LxHy，右下部是高频子带HxHy。大多数的普通图象中边缘信息不是很多，因此经过二维双正交小波正变换后，图象信息主要存在于低频子带LxLy之中，其余高频子带仅包含少量的边缘信息，即通过小波变换，大绝对值小波变换系数主要分布在左上部的低频子带区域，其余区域大绝对值小波变换系数很少。在视频数据压缩和图象数据压缩技术中，为获得较好的压缩效果，通常对图象数据执行多层二维双正交小波变换。小波变换一般做三到五层，不再进行更高层小波变换的原因是，当大绝对值小波变换系数集中到一定程度，再对其进行小波变换，一般不会再有显著效果。实质上，小波变换增加一层或减少一层，并不会对小波变换电路产生本质上不同的要求，因此本发明可以应用于常用的三到五层小波变换方案之中。下面对采用了四层小波变换的实施例加以说明，如图6所示，第一层小波变换完成后对低频子带LxLy再做第二层小波变换，然后再对第二层小波变换的低频子带做第三层小波变换，最后对第三层小波变换的低频子带再做第四层小波变换。对于(5，3)小波基的二维双正交小波变换，本发明只需要一个一阶多项式的运算电路和少量控制、接口电路，即可完成多层二维双正交小波变换及其逆变换。因此以下实施例以(5，3)小波基为例。

以CIF格式的图象数据为例，四层二维小波正变换的过程是：

(1)执行352×288整帧图象数据的一维小波行变换；

(2)执行352×288整帧行变换数据的一维小波列变换；

(3)执行176×144一层变换的低频子带数据的一维小波行变换；

(4)执行176×144低频子带的行变换数据的一维小波列变换；

(5)执行88×72二层变换的低频子带数据的一维小波行变换；

(6)执行88×72低频子带的行变换数据的一维小波列变换；

(7)执行44×36三层变换的低频子带数据的一维小波行变换；

(8)执行44×36低频子带的行变换数据的一维小波列变换；

四层二维小波逆变换的过程是从(8)-(1)的反向操作过程。

如果某项应用只需要三层二维小波变换，则(7)(8)步骤不需执行。如果某项应用需要五层二维小波变换，则增加如下(9)(10)步骤。

(9)执行22×18四层变换的低频子带数据的一维小波行变换；

(10)执行22×18低频子带的行变换数据的一维小波列变换；

上述一维小波变换均是依次分别顺序进行，而且不同行、列长度的一维小波变换只是在边界处理上不同，因此一个一维小波变换电路可以完成所有上述运算。

要保证四层二维小波变换依次正确完成，需要一个控制电路产生状态控制信号和一个接口电路准确输入和输出数据。控制电路根据外部命令进入四层二维小波正变换或逆变换，同时发出状态位标志，并使得各部分电路开始工作。工作过程中，当电路工作在某一层的行或列变换时，状态位标志出相应的状态信号。如用1个比特的信号表示正变换或逆变换，用3个比特的信号表示上述8个某一层的行或列变换状态，将(1)-(8)的状态分别标志为000，001，010，011，100，101，110，111。接口电路针对两个外部存储器的情况。其他情况可类似地进行设计。设两个外部存储器分别是RAM1和RAM2，其中RAM1存放了原始图象数据，RAM2存放行变换产生的中间数据。接口电路根据控制电路的状态控制信号，确定要执行哪一层的行或列变换，相应的行、列长度是多少。

当进行二维小波正变换的行变换时，接口电路产生对RAM1的读数据信号和地址，将待变换数据逐行顺序地从RAM1中读出，并输入到小波变换电路。同时，接口电路还要产生对RAM2的写数据信号和地址，将变换后数据按奇、偶地址，即按高、低频子带分开，低频子带数据顺序地输出到RAM2的每行的前半部，高频子带数据顺序地输出到RAM2的每行的后半部。

类似地，当进行正变换的列变换时，接口电路产生对RAM2的读数据信号和地址，将待变换数据逐列顺序地从RAM2中读出，并输入到小波变换电路。同时，接口电路还要产生对RAM1的写数据信号和地址，将变换后数据按奇、偶地址，即按高、低频子带分开，低频子带数据顺序地输出到RAM1的每列的前半部，高频子带数据顺序地输出到RAM1的每列的后半部。

对于二维小波逆变换，当列变换时，接口电路产生对RAM1的读数据信号和地址，将待变换数据逐列按低、高频子带交替顺序地从RAM1中读出，并输入到小波变换电路。即，读一个低频子带数据后，读一个高频子带数据，再读一个低频子带数据，依此类推。同时，接口电路还要产生对RAM2的写数据信号和地址，将变换后数据按奇、偶地址排列，顺序地输出到RAM2的每列地址之中。

当进行逆变换的行变换时，接口电路产生对RAM2的读数据信号和地址，将待变换数据逐行按低、高频子带交替顺序地从RAM2中读出，并输入到小波变换电路。同时，接口电路还要产生对RAM1的写数据信号和地址，将变换后数据按奇、偶地址排列，顺序地输出到RAM1的每行地址之中。

本发明的优点与积极效果在于：

本发明完成的整型双正交小波变换电路将小波变换分解为提升形式，并利用分时技术共用运算单元，是一个对集成电路资源要求相对很少的电路。对于使用(5，3)小波基的二维双正交小波变换只需要一个一阶多项式的运算电路和少量控制、接口电路，即可实时地完成多层二维双正交小波变换及其逆变换。其中“实时”是指数据处理与数据流动同步进行，即有多少数据来到马上就能处理多少数据，不会无限累积以至数据丢失。本发明的优点在于：

1．成本低廉，它对集成电路资源的要求相对很少，并且不需要专门的电路结构和片内存储器，因而能够集成到一片价格低廉的集成电路之中。

2．可靠性好，由于结构简单、紧凑，具有良好的实用性和可靠性。

3．通用性强，可以完成任意常用类型、尺寸的一帧或一块图象数据的多层二维双正交小波正变换和逆变换。

此集成电路已经设计完成，并且通过美国Altera公司的EPF10K200E集成电路进行了实验验证，与理论结果完全符合。