摘  要: 小波" title="小波">小波分析是信息处理领域的一种重要处理方法,但是小波分解巨大的运算量却严重束缚了其在实时处理领域中的应用。提出了一种基于FPGA实现的高速小波分解方法,该方法采用新的小波分解结构,使多层分解得以同时进行,从而使小波分解的速度达到高速输入图像的数据率;并适当选取了数据结构,使得经分解、重构" title="重构">重构后所得图像的峰值信噪比达到无穷大。这种方法大大提高了硬件系统进行小波分解的速度,在小波分解的性能和硬件实现的资源消耗上找到了一个较优的结合点。

　　关键词: 小波分析  图像处理  图像压缩  实时处理  FPGA

　　目前,小波分析在许多科学与工程领域中得到了广泛研究和应用。由其引出的多分辨分析方法,更是成为图像压缩、图像分割、特征提取、语音识别等方面的一种有力工具。但是,随着它在实际工程中应用的不断深入,研究人员发现,在数据速率很高的情况下,现有的硬件系统很难承担实时处理的巨大运算量。因此,研究适合硬件实现的小波分解算法和改进小波分解的硬件实现方法" title="实现方法">实现方法,便成为小波分析应用于工程实际的两大关键课题。

　　本文将阐述一种基于FPGA(现场可编程逻辑阵列)芯片实现的高速图像小波分解方法,较好地解决了运算量大和要求实时处理的矛盾。

1 二维小波分解和重构算法

1.1 Mallat算法

　　当前,在小波分析的研究领域,通常采用多分辨分解和合成的金字塔算法,即Mallat算法。Mallat算法的基本思想是:将一个分辨率为1的原始信号F(n)进行N层分解,分解成一个分辨率为2^-N的低频信号和一系列高频信号。其流程如图1所示。

　　分解算法的公式如下:

　　重构算法是分解过程的逆过程,经过逆滤波就能恢复出原始的信号序列。

　　重构算法的公式如下:

1.2 二维Mallat算法

　　在图像处理领域,需要进行处理的通常是二维图形。因此,将Mallat算法扩展到二维空间,适当地选取一组行和列变换正交的小波系数,对图像(或分解后的低频子图)分别进行行变换和列变换。然后,根据后续的具体应用对N次分解所得的图像在不同的分辨率下进行分析、处理或数据压缩。二维Mallat算法的结构如图2所示。

1.3 CDF9/7系数

　　在进行二维Mallat分解时需选取一组正交的小波系数。经过小波算法研究人员的多年研究,目前已经找出了多组小波系数。其中以CDF9/7系数应用最为普遍,已成为JPEG2000图形压缩标准推荐使用的系数。但是,CDF9/7系数通常采用浮点进行计算,在进行高速处理时不便于硬件实现。因此,选取α=0.5的CDF9/7系数,如公式(3)和(4)所示,滤波器的系数可以表示成分母为2的幂、分子为2的幂之和的形式,在保证小波分解性能的情况下更适合用FPGA实现。

1.4 图像的边缘延拓

　　对图像进行行或列分解可以看成是一个对有限长序列进行滤波的过程,在行变换和列变换时需要进行首尾数据延拓。常用的延拓方式包括:对称延拓、“0”延拓、恒等延拓、周期延拓等。经多次实验证明,图像恢复效果以对称延拓为最好,而且实现也比较方便。

2 普通的FPGA实现方法

　　在数据输入速率很高(100MHz量级)、系统连续工作的情况下,要实时地完成小波分解,需要即时完成大量的乘法和加法运算、数据读写操作等。只支持单流水线工作的普通DSP系统在数据处理" title="数据处理">数据处理时受处理器频率、数据输入输出带宽等因素的限制,而支持并行处理的高性能DSP在算法的分割、数据交换上存在较大的困难。因此,在进行高速数据处理时,通常基于FPGA设计一个可以并行运算的专用处理器,从而达到较高的数据处理速度。

　　目前,在工程领域通常采用顺序逐级分解的方法。即在对图像进行缓冲后,逐次在FPGA中进行各级的行变换和列变换。其系统结构如图3所示。

　　这种结构的主要优点是占用的FPGA资源较少。但这种设计方法的致命缺陷是,每次处理都必须将各级分解作完,才能对下一帧图像进行处理。限于FPGA和RAM的接口带宽,其处理速度不可能太高,而且占用的外部RAM空间较大。

3 改进的FPGA实现方法

　　针对普通的顺序逐级分解方法的缺陷,充分利用Xilinx公司VertixE系列FPGA的特性,设计一种数据串行输入(不需进行帧缓冲)、多级变换同时进行的结构,可以大大提高整个小波分解系统的数据处理速度并节省大量的外部RAM空间。

3.1 FPGA内部的功能划分

　　本方法主要是利用VirtexE系列FPGA内部有大量Block RAM资源和逻辑资源的特点,直接在FPGA内部进行多级分解。按逻辑功能的不同,FPGA内部将实现如图4所示的几个功能模块。

　　全局控制模块接收外部控制信号(芯片使能、数据时钟等),由内部计数器进行计时、产生各级分解模块的控制信号(模块使能、起始终止信号等)。各级分解模块则在全局控制模块的控制下,对外部数据或前一级的LL输出数据进行锁存、处理、缓冲、输出等操作。

　　图4中的每一级小波分解模块需要完成图像的行和列两次变换。如果选择先进行完整的行变换再进行列变换的方法,将需要大量的缓冲空间并且需要更多的时钟周期。因此,必须采用行变换和列变换同时进行的形式,如图5所示。图像数据输入到分解模块的数据输入端,由行数据缓冲器进行移位、锁存。锁存后的数据并行输出到行变换滤波器,进行低通和高通滤波,然后进行抽样、缓冲输出。行滤波器的输出与存储在8行数据缓冲RAM内相同位置的数据锁存到列数据缓冲器1中。缓冲器1的输出与列变换滤波器的输入相连,时间靠后的8个数据被锁存到列数据缓冲器2。列数据缓冲器2的数据将送到内部RAM进行缓冲,下一个行周期将前8个数据输出到列缓冲器1,从而实现列方向上的数据移位。列变换滤波器输出的LH、HL、HH直接或经缓冲后输出,LL则输出到下一级分解模块进行处理。

　　本方法相对普通实现方法的主要优势在于:首先,在分解过程中数据的存储在片内进行,不受芯片接口带宽的限制,数据交换速度达到最快;其次,多级分解同时进行,进一步提高了分解的整体速度;再次,中间数据不必输出片外,节省了外部RAM的空间。此外,在FPGA的设计过程中还加入了流水线、分布式算术^[3～4]等优化技术,进一步提高了FPGA器件进行小波分解的速度。

3.2 中间数据动态范围" title="动态范围">动态范围及精度

　　在进行FPGA设计时,为了保持中间数据长度一定,每次变换完成后都必须进行数据的首尾截取,中间结果的数据动态范围和数据精度将直接影响到分解的效果和硬件的开销。动态范围不够,将出现数据溢出,动态范围选取过大又会浪费硬件资源。保留中间结果的精度将直接影响到分解后数据的有效性。

3.2.1 动态范围分析

　　根据公式(3)、(4)中选取的CDF9/7系数h(n)和g(n),,以最坏的情况计算,数据动态范围每次变换扩大到原来数据范围的1.5倍。经8次变换(4层分解,每层两次变换)后,数据的动态范围将扩大到原来的(1.5)8≈25.63倍。若图像的原始数据为8位,要含盖所有的情况则需要用13位表示整数。

3.2.2 累计截尾误差分析

　　设每次中间结果保留n位小数,则截尾引起的误差为:Δx=2^-(n+1)。经过8次变换,每次变换的截尾误差会逐级累加放大,最坏情况的累计误差为:Δx⁽⁸⁾=Δx=(1+1.5+1.5²+…+1.57)。考虑到第一次进行运算的数据小数部分为0,而且每次变换要除以64(2的6次幂),若小数位数大于等于6位，则第一次变换的截尾操作将不会带入误差,因此,Δx⁽⁸⁾=Δx=(1+1.5+1.5²+…+1.5⁶)≈32.2Δx。在小波分解的后续处理中,往往要先进行取整运算。因此,若Δx⁽⁸⁾<1,即Δx<32.2^-1<2^-6,n≥5,截尾带来的累计误差将不会影响后续处理的精度。

3.2.3 数据动态范围与精度的确定

　　经过上述分析,若要同时保证动态范围和精度,则中间数据需保留13+5=18位。通常数据长度选取16、24或32等。显然,选取后两种数据长度可以满足要求,但是要消耗更多的硬件资源。而选取16位似乎又不能满足动态范围和精度的要求。

　　上述动态范围和精度分析都是考虑到最坏的情况。而实际情况并非如此,最坏情况出现概率微乎其微。表1是几幅标准图像的动态范围统计。

　　可见,实际图像的处理中数据的动态范围并不大。9位(±256)已经可以满足绝大多数应用,而小数部分要求n≥5,各保留1 位的余量(即10位整数、6位小数),16位数据长度正好可以满足需要。

3.3  设计、实现与测试

　　基于Virtex E 系列的XCV600E-7芯片,设计了一套512×512象素图像的四级小波分解系统。XCV600E器件内部共有6912个Slices(逻辑功能块)、13824个Registers(寄存器)、13824个4 Input LUT(四输入查找表)和72个Block RAM,适用于较复杂的处理器设计。芯片的接口速率达到200MHz(Xilinx数据手册提供的数据),能提供足够的输入输出带宽。经过设计、仿真与实现,完成小波分解的资源消耗和性能基本达到了预想的效果。

　　用VHDL语言描述的设计版本,共消耗了

　　Slices: 6344个(91%)， Register: 4970个(35%),

    4 Input LUT: 10311个(74%)， Block RAM: 40个(55%)。

　　用Xilinx公司例化元件的设计版本,共消耗了

　　Slices: 3524个(51%)， Register: 4668个(34%),

　　4 Input LUT: 6345个(46%)， Block RAM:40个(55%)。

　　从资源的消耗情况来看,该芯片完全可以进行1024×1024大小图像的分解以及进行第5级分解。

通过对系统进行的实际测试可知,系统的数据处理速率高达120MHz;根据仿真的波形可知,最大的数据不稳定时间≤2.5ns。而系统正常稳定工作时要求数据的不稳定时间小于工作周期的一半,因此系统的工作频率完全可以提升到200MHz甚至更高。在实际的系统中,此项性能主要受限于FPGA的接口速率,若选用更高档的芯片,将达到更好的效果。

　　经过FPGA的分解和重构,得到的结果如图6所示。经测试,重构图像在进行取整运算后,重构图像与原始图像完全无失真,即峰值信噪比PSNR为无穷大。可见,由于设计中正确地选取了数据的动态范围和数据精度,在节省了中间存储器空间的同时使分解和重构运算的截尾误差未给图像的恢复带来损失。

3.4 改进后的FPGA实现方法的显著优势

　　为了对改进后的方法进行性能比较,采用普通的FPGA实现方法设计了一套512×512图像的4级小波分解系统。经过测试,得到表2所示数据。

　　由表2的前两项数据可见,需要设计8个相同的滤波器,而普通方法只需设计一个16位的滤波器和几个控制模块,因此前者比后者消耗了更多的FPGA资源;改进方法将中间数据在芯片内作缓冲,消耗了40个Block RAM块。改进方法在资源的消耗上虽然不及前者,但是在大规模FPGA芯片成为设计主流载体的今天,资源的消耗问题已经不象以往那样至关重要。

　　目前大家最关心的问题,也是改进后方法的主要优势,就是对图像的处理效率高、节省了外部的存储器资源。在图像数据连续进入系统的情况下,普通的方法为了解决中间数据在外部RAM中的存储问题,只有设计多条(3条以上)单独的数据通道和多块独立的RAM来分别完成数据的缓冲、中间结果存储、结果缓存。由于图像处理的中间结果都要缓冲到外部存储器并要多次通过分解模块进行处理,若要实时地完成数据处理,就要求器件的工作频率以及与存储器的接口速率能够达到图像数据输入速率2.5倍左右。而改进后的方法,在处理图像数据时将中间结果存储于FPGA内部,而且中间数据依次通过各级分解模块,FPGA的工作频率只要和图像数据的输入速率一致即可以满足要求。当图像的输入速率达到100MHz量级时,普通方法要求FPGA的工作频率和存储器接口速率都要达到250MHz,这对大多数FPGA和RAM都是难以突破的瓶颈。因此,在器件相同的情况下,改进后的系统可达到普通系统处理速度的2.5倍。

　　由此可见,普通方法适合于图像数据率比较低、对系统的成本要求比较严格的情况,改进方法则适合应用于对性能要求很高而对成本要求不高的情况。

　　本文提出的基于FPGA的高速图像小波分解实现方法比传统的实现方法在处理速度方面有了很大的提高。特别是在对连续图像进行处理时,可以不进行图像数据的分割和缓冲而进行连续的处理,节省了分块缓冲的时间和存储空间。在图像重构系统中采用同样的结构即可连续地恢复出原始图像。在实际的应用中,小波分解模块并不是孤立存在的,经过小波分解后的数据还要进行数据压缩、数据融合、边缘检测等处理。根据后续模块实现方案的具体情况,在FPGA中设计与后续处理模块匹配的数据通道,小波分解模块即可方便地与相应的图像处理系统进行级联。因此,本文提出的高速小波分解模块可以广泛应用于基于小波分解的各种图像处理算法的实时处理系统,使小波分解部分不再成为整个图像处理系统的瓶颈。

参考文献

1 Thomas W. Fry. Hyperspectral Image Compression on Reconfigurable Platform. Washington University,2000

2 Jonathan B. Ballagh. An FPGA Run-time Reconfigurable 2-D Discrete Wavelet Transform Core. Virginia， June 2001

3 K. Chapman.Fast Integer Multipliers Fit in FPGAs. Electronic Design News， May 12， 1994

4 Spaniol. Computer Arithmetic: Logic and Design,John Wiley & Sons,1981

5 Xilinx. Xilinx VirtexE Data Book.San Jose CA,2000

6 李在铭.数字图像处理、压缩与识别技术.成都:电子科技大学出版社,2000

7 Castleman,K. R著，朱志刚译.数字图像处理.北京:电子工业出版社,1998